Implicit function types can be a powerful way to abstract over implicits. In this section, we demonstrate that implicit function types not only promote expressivity, but that they can additionally improve performance over solutions without implicit function types.
To that aim, we show that implicit function types can be used in the expression of many different applications. We introduce four different applications that are made clearer and more concise through the use of implicit function types. The last two of which we show improve performance over existing implementations without implicit function types. In Section [subsec:builder], we present an expressive DSL using the builder pattern, followed by an encoding of tagless interpreters [@carette_finally_2009] demonstrating how we can abstract over the number of implicit parameters in Section [subsec:tagless]. In Section [subsec:reader], we show how we encode the reader monad with an isomorphic representation using implicit functions, and assess its performance alongside of popular implementations in the Scala ecosystem. Finally, in Section [subsec:free], we introduce a new implementation of the free monad, and assess its performance as well.
We demonstrate how implicit function types can be used to build declarative API using the type-safe builders pattern [@type_safe_builders] without any boilerplate at the use-site. Let’s assume we’d like to define a small DSL to create tables that look like the following:
table {
row {
cell("top left")
cell("top right")
}
row {
cell("bottom left")
cell("bottom right")
}
}
In this example |table|, |row| and |cell| are function calls to a factory method. Every call creates a new node (resembling an AST), and registers this newly created node to its parent. Implicit functions are used to propagate references of parent nodes to newly created nodes. For instance, the |table| method takes an |implicit Table => Unit| as argument:
class Table {
val rows = new ArrayBuffer[Row]
def add(r: Row): Unit = rows += r
override def toString = rows.mkString("Table(", ", ", ")")
}
def table(init: implicit Table => Unit): Table = {
implicit val t = new Table
init
t
}
The Definitions of |row| and |cell| are analogous. After desugaring and implicit resolution, the table construction above is translated into the following:
table { $t: Table =>
row { $r: Row =>
cell("top left")($r)
cell("top right")($r)
}($t)
row { $r: Row =>
cell("bottom left")($r)
cell("bottom right")($r)
}($t)
}
Implicit function types enable a very useful way to abstract over the number of implicit parameters introduced in some scope. We demonstrate a usage of this abstraction through an implementation of the tagless interpreter pattern [@carette_finally_2009] (or object algebra [@oliveira_extensibility_2012] as popularized in the OOP domain) for simple arithmetic expressions. Tagless interpreters make it possible to add both new syntactic elements and interpretations without breaking the existing hierarchy, thus serving as a solution to the Expression Problem [@wadler_expression_1998]. Below, we show the tagless encoding of a toy language for simple arithmetic expressions with only two constructs; |lit| and |add|.
trait Exp[T] {
def lit(i: Int): T
def add(l: T, r: T): T
}
object ExpSyntax {
def lit[T](i: Int) (implicit e: Exp[T]): T = e.lit(i)
def add[T](l: T, r: T)(implicit e: Exp[T]): T = e.add(l, r)
}
To define an expression on integers using these two constructs, we first need to implement an interpreter to evaluate integer expressions as follows:
implicit val evalExp: Exp[Int] = new Exp[Int] {
def lit(i: Int): Int = i
def add(l: Int, r: Int): Int = l + r
}
With that, we can now define an expression in the |Exp| language. Using
what we have so far, we can define
def tf1[T](implicit e: Exp[T]): T = add(lit(8), add(lit(1), lit(2)))
Allowing one to interpret |tf1| as follows:
val evaluated: Int = tf1
println(evaluated) // 11
To extend the |Exp| language to be able to handle multiplication, we define a new trait |Mult| with the new multiplication operation we’d like to add:
trait Mult[T] {
def mul(l: T, r: T): T
}
object MultSyntax {
def mul[T](l: T, r: T)(implicit e: Mult[T]): T = e.mul(l, r)
}
Ultimately, we’d like to define an expression to evaluate multiplication
and additions in the same expression. We can define
def tfm1[T](implicit e: Exp[T], m: Mult[T]): T = add(lit(7), mul(lit(1), lit(2)))
Interpreting |tfm1| requires two instances of interpreters; it requires
two implicit parameters, one of type Exp[T] and another of type
Mult[T]. We can use |evalExp| for addition, and we need another for
multiplication, which can be defined as follows:
implicit val evalMult: Mult[Int] = new Mult[Int] {
def mul(l: Int, r: Int): Int = l * r
}
As we observe, by increasing the number of interpreters, we increase the number implicit parameters. If we continue extending our toy language in this fashion, we have no way to abstract over these new extensions as they pile up in parameter lists. Implicit function types enable us to easily abstract over implicit parameters using type aliases:
type ExtExp[T] = implicit (Exp[T], Mult[T]) => T
This enables us to define |tfm1| much more concisely, allowing us to
omit the two implicit parameters we had to write above, by using the
ExtExp[T] type alias:
def tfm1[T]: ExtExp[T] = add(lit(7), mul(lit(1), lit(2)))
The reader monad represents a computation with the ability to read from an environment. It is defined in term of two operations, |ask|, to retrieve the environment, and |local|, to modify the environment for sub-computations (monad instance omitted):
trait Reader[R, A] {
def ask: R
def local[A](f: R => R)(a: A): A
}
|Reader| expressions are formed using the |for|-comprehensions (equivalent to the do-notation in Haskell):
val expr1: Reader[Env, Int] = ...
val expr2: Reader[Env, Int] = ...
val expr3: Reader[Env, Int] =
for {
e1 <- expr1
e2 <- expr2
} yield e1 + e2
Implicit function types can be used as a concise alternative to |Reader|:
type ReaderIFT[T] = implicit Env => T
Values of type ReaderIFT[T] automatically obtain an |Env| from the
implicit context, and propagate this value to all sub-expressions in the
right-hand side of their definition:
val expr1: ReaderIFT[Int] = ...
val expr2: ReaderIFT[Int] = ...
val expr3: ReaderIFT[Int] = expr1 + expr2
|Env| values can be obtained using implicitly[Env] in the body of
|ReaderIFT| expression, which corresponds to the |ask| operation on
|Reader|. Analogously, a new |Env| can be defined for all
sub-expressions via by defining a local implicit of that type. This
pattern is very common in large-scale applications. For instance, in web
programming, the majority of functions take a context argument to
propagate information about the request that is currently being
processed. Implicits provide a simple and concise way to transmit this
information across such applications.
**ask-idempotent** flatMap(ask)(x ⇒ ask) ≡ ask
**local-ask** ∀ f : local(f)(ask) ≡ map(ask)(f)
**local-flatmap** ∀ r, f, g : local(g)(flatMap(r)(f)) ≡ flatMap(local(g)(r))(x ⇒ local(g)(f(x)))
**local-pure** ∀ f, a : local(f)(pure(a)) ≡ pure(a)
Data types à la carte [@swierstra_data_2008] popularized the free monad pattern, an abstraction to decouple monadic expressions from their semantics. Typical Scala implementations [@bjarnason_stackless_2012] of this idea use a generalized algebraic data type (GADT) to encapsulate the monadic structure, called |Free|:
sealed trait Free[A[_], T]
case class Pure[A[_], T](a: T) extends Free[A, T]
case class Suspend[A[_], T](a: A[T]) extends Free[A, T]
case class FlatMapped[A[_], B, C](c: Free[A, C], f: C => Free[A, B]) extends Free[A, B]
Interpreters for |Free| expressions are defined as natural transformations, that is, instances of the |Natural| trait:
trait Natural[F[_], G[_]] {
def apply[A](fa: F[A]): G[A]
}
Interpretation of |Free| expressions is done thought a |foldMap| function:
def foldMap[A[_], T, M[_]](e: Free[A, T])(n: Natural[A, M])(implicit m: Monad[M]]): M[T] = ...
Users of free monads typically depend on a library that provides the definition for |Free|, |foldMap|, and a monad instance for |Free|. These definitions are non-trivial and duplication is required to support other free structures such as the free applicative functor.
Implicit function types open the door to an alternative design of free monad that is simpler to use, more efficient and doesn’t require any library infrastructure. The new design defines a |FreeIFT| type alias with two curried implicit function types, mirroring the signature of |foldMap|:
type FreeIFT[A[_], M[_], T] = implicit Natural[A, M] => implicit Monad[M] => M[T]
In this new encoding of free monads, expressions are function type parametric in the monad used for interpretation. For instance, a free expression with made |Put| and |Get| operations (subtypes of |KVStore|) can be defined as follows:
type KVStoreIFT[M[_], T] = FreeIFT[KVStore, M, T]
def iftExpr[M[_]]: KVStoreIFT[M, Option[Int]] =
for {
_ <- lift(Put("foo", 2))
_ <- lift(Put("bar", 5))
n <- lift(Get("foo"))
} yield n
Where the |lift| method is used to apply an implicit natural transformation:
def lift[F[_], M[_], A](fa: F[A])(implicit F: Natural[F, M]): M[A] = F(fa)
Interpreters are, as in the traditional encoding, natural transformations. However, the interpretation doesn’t require a library defined |foldMap| function. Instead, it is a simple function application of |iftExpr| to an interpreter:
def iftInterpreter = new Natural[KVStore, Future] {
def apply[T](fa: KVStore[T]): Future[T] = ...
}
val iftOutput: Future[Option[Int]] = iftExpr[Future](iftInterpreter)
The main benefit of the implicit function type encoding of free monad is
that it doesn’t require any library support. From a user perspective,
there is also less boilerplate involved (the |put| and |get| function
become unnecessary). The two encodings can be shown to be equivalent by
defining a bijection between representations. The conversion to the À
la carte encoding is done via interpretation from |A| to
[X] => Free[A, X]: 1
def initialize[A[_]] = new Natural[A, [X] => Free[A, X]] {
def apply[T](a: A[T]): Free[A, T] = Suspend[A, T](a)
}
Conversion from the À la carte encoding also goes through an interpretation, from |A| to new |Expr| trait, which captures the polymorphism in expressions by the implicit function type encoding2:
trait Expr[A[_], T] {
def e[M[_]]: FreeIFT[A, M, T]
}
def finalize[A[_]] = new Natural[A, [X] => Expr[A, X]] {
def apply[T](a: A[T]): Expr[A, T] = new Expr[A, T] {
def e[M[_]]: FreeIFT[A, M, T] = a.lift
}
}
[@bjarnason_stackless_2012]: Bjarnason, Runar. Stackless Scala With Free Monads. https://web.archive.org/web/20170107134129/http://blog.higher-order.com/assets/trampolines.pdf
[@carette_finally_2009]: Carette, Jacques and Kiselyov, Oleg and Shan, Chung-chieh. Finally Tagless, Partially Evaluated: Tagless Staged Interpreters for Simpler Typed Languages
[@oliveira_extensibility_2012]: Oliveira, Bruno C. d. S. and Cook, William R.. Extensibility for the Masses: Practical Extensibility with Object Algebras
[@swierstra_data_2008]: Swierstra, Wouter. Data Types `{a} La Carte
[@type_safe_builders]: Type-Safe Groovy Style Builders in Kotlin. https://web.archive.org/web/20170607150651/https://kotlinlang.org/docs/reference/type-safe-builders.html
[@wadler_expression_1998]: Wadler, Philip. The Expression Problem. https://web.archive.org/web/20170322142231/http://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt