From c10a9903144d9c6e039528fcf0269c4f7dadf1cb Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Wed, 7 Dec 2016 11:32:38 +0100 Subject: Finished blog post --- .../_posts/2016-12-05-implicit-function-types.md | 260 ++++++++++++++++++--- 1 file changed, 225 insertions(+), 35 deletions(-) diff --git a/docs/blog/_posts/2016-12-05-implicit-function-types.md b/docs/blog/_posts/2016-12-05-implicit-function-types.md index 3172e46a4..007665564 100644 --- a/docs/blog/_posts/2016-12-05-implicit-function-types.md +++ b/docs/blog/_posts/2016-12-05-implicit-function-types.md @@ -7,28 +7,23 @@ authorImg: /images/martin.jpg I just made the first pull request to add _implicit function types_ to Scala. I am pretty excited about it, because, citing the explanation -of the pull request "This is the first step to bring comonadic -abstraction to Scala". That's quite a mouthful, so I better explain what I +of the pull request "_This is the first step to bring contextual +abstraction to Scala_". That's quite a mouthful, so I better explain what I mean by it. Let me try to explain the words in this sentence from right to left. -*Scala*: I assume everyone who reads this understands that we mean the +**Scala**: I assume everyone who reads this understands that we mean the programming language, not the opera house. -*Abstraction*: The ability to name a concept and use just the name afterwards. +**Abstraction**: The ability to name a concept and use just the name afterwards. -*Comonadic*: In category theory, a _comonad_ is the dual of a -_monad_. Roughly speaking, a monad is a way to wrap the result (or: -outputs) of a computation in some other type. For instance -`Future[T]` means that the result of type `T` will be produced at -some later time on demand, or `Option[T]` indicates that the result -might also be undefined. - -Dually, a _comonad_ allows to transform or -enrich or otherwise manipulate the _inputs_ to a computation. -The inputs are typically what a computation can access in its -environment. Interesting tasks that are by nature comonadic are +**Contextual**: A piece of a program produces results or outputs in +some context. Our programming languages are very good in describing +and abstracting what outputs are produced. But there's hardly anything +yet available to abstract over the inputs that programs get from their +context. Many interesting scenarios fall into that category, +including: - passing configuration data to the parts of a system that need them, - managing capabilities for security critical tasks, @@ -36,29 +31,15 @@ environment. Interesting tasks that are by nature comonadic are - defining the meanings of operations with type classes, - more generally, passing any sort of context to a computation. -Implicit function types are a suprisingly simple and general way to +Implicit function types are a surprisingly simple and general way to make coding patterns solving these tasks abstractable, reducing boilerplate code and increasing applicability. -*First Step* My pull request is first implementation. In solves the - problem in principle, but it introduces some run-time overhead. The +**First Step**: My pull request is a first implementation. It solves the + problem in principle, but introduces some run-time overhead. The next step will be to eliminate the run-time overhead through some simple optimizations. - -## Comparison with Monads - -One can use monads for these tasks, and some people do. For instance -the `Reader` monad is used to abstract over accessing one entry in the -environment. But the code for doing so quickly becomes complex and -inefficient, in particular when combining several contextual -accesses. Monads don't compose in general, and therefore even simple -combinations need to be expressed on the level of monad transformers, -at the price of much boilerplate and complexity. Recognizing this, -peaple have recently experimented with free monads, which alleviate -the composibility problem, but at the price of introducing a whole new -level of interpretation. - ## Implicit Parameters In a functional setting, the inputs to a computation are most @@ -67,7 +48,7 @@ functions to take additional parameters that represent configurations, capabilities, dictionaries, or whatever contextual data the functions need. The only downside with this is that often there's a large distance in the call graph between the definition of a contextual -element and the site where it is used. Conseuqently, it becomes +element and the site where it is used. Consequently, it becomes tedious to define all those intermediate parameters and to pass them along to where they are eventually consumed. @@ -122,11 +103,11 @@ a newly created transaction: trans.commit() } -The current transaction needs to be passed along a calling chain to all +The current transaction needs to be passed along a call chain to all the places that need to access it. To illustrate this, here are three functions `f1`, `f2` and `f3` which call each other, and also access the current transaction. The most convenient way to achieve this is -passing the current transaction as an implicit parameter. +by passing the current transaction as an implicit parameter. def f1(x: Int)(implicit thisTransaction: Transaction): Int = { thisTransaction.println(s"first step: $x") @@ -165,6 +146,215 @@ Two sample calls of the program (let's call it `TransactionDemo`) are here: scala TransactionDemo 1 2 3 4 aborted +So far, so good. The code above is quite compact as far as expressions +are concerned. In particular, it's nice that, being implicit +parameters, none of the transaction values had to be passed along +explicitly in a call. But on the definition side, things are less +rosy: Every one of the functions `f1` to `f3` needed an additional +implicit parameter: + + (implicit thisTransaction: Transaction) + +A three-times repetition might not look so bad here, but it certainly +smells of boilerplate. In real-sized projects, this can get much worse. +For instance, the _dotty_ compiler uses implicit abstraction +over contexts for most of its parts. Consequently it ends up with currently +no fewer than 2641 occurrences of the text string + + (implicit ctx: Context) + +It would be nice if we could get rid of them. + +## Implicit Functions + +Let's massage the definition of `f1` a bit by moving the last parameter section to the right of the equals sign: + + def f1(x: Int) = { implicit thisTransaction: Transaction => + thisTransaction.println(s"first step: $x") + f2(x + 1) + } + +The right hand side of this new version of `f1` is now an implicit +function value. What's the type of this value? Previously, it was +`Transaction => Int`, that is, the knowledge that the function has an +implicit parameter got lost in the type. The main extension implemented by +the pull request is to introduce implicit function types that mirror +the implicit function values which we have already. Concretely, the new +type of `f1` is: + + implicit Transaction => Int + +Just like the normal function type syntax `A => B`, desugars to `scala.Function1[A, B]` +the implicit function type syntax `implicit A => B` desugars to `scala.ImplicitFunction1[A, B]`. +The same holds at other function arities. With dotty's [pull request #1758](https://github.com/lampepfl/dotty/pull/1758) +merged there is no longer an upper limit of 22 for such functions. + +The type `ImplicitFunction1` can be thought of being defined as follows: + + trait ImplicitFunction1[-T0, R] extends Function1[T0, R] { + override def apply(implicit x: T0): R + } + +However, you won't find a classfile for this trait because all implicit function traits +get mapped to normal functions during type erasure. + +There are two rules that guide type checking of implicit function types. +The first rule says that an implicit function is applied to implicit arguments +in the same way an implicit method is. More precisely, if `t` is an expression +of an implicit function type + + t: implicit (T1, ..., Tn) => R + +such that `t` is not an implicit closure itself and `t` is not the +prefix of a call `t.apply(...)`, then an `apply` is implicitly +inserted, so `t` becomes `t.apply`. We have already seen that the +definition of `t.apply` is an implicit method as given in the +corresponding implicit function trait. Hence, it will in turn be +applied to a matching sequence of implicit arguments. The end effect is +that references to implicit functions get applied to implicit arguments in the +same way as references to implicit methods. + +The second rule is the dual of the first. If the expected type +of an expression `t` is an implicit function type + + implicit (T1, ..., Tn) => R + +then `t` is converted to an implicit closure, unless it is already one. +More precisely, `t` is mapped to the implicit closure + + implicit ($ev1: T1, ..., $evn: Tn) => t + +The parameter names of this closure are compiler-generated identifiers +which should not be accessed from user code. That is, the only way to +refer to an implicit parameter of a compiler-generated function is via +`implicitly`. + +It is important to note that this second conversion needs to be applied +_before_ the expression `t` is typechecked. This is because the +conversion establishes the necessary context to make type checking `t` +succeed by defining the required implicit parameters. + +There is one final tweak to make this all work: When using implicit parameters +for nested functions it was so far important to give all implicit parameters +of the same type the same name, or else one would get ambiguities. For instance, consider the +following fragment: + + def f(implicit c: C) = { + def g(implicit c: C) = ... implicitly[C] ... + ... + } + +If we had named the inner parameter `d` instead of `c` we would +have gotten an implicit ambiguity at the call of `implicitly` because +both `c` and `d` would be eligible: + + def f(implicit c: C) = { + def g(implicit d: C) = ... implicitly[C] ... // error! + ... + } + +The problem is that parameters in implicit closures now have +compiler-generated names, so the programmer cannot enforce the proper +naming scheme to avoid all ambiguities. We fix the problem by +introducing a new disambiguation rule which makes nested occurrences +of an implicit take precedence over outer ones. This rule, which +applies to all implicit parameters and implicit locals, is conceptually +analogous to the rule that prefers implicits defined in companion +objects of subclasses over those defined in companion objects of +superclass. With that new disambiguation rule the example code above +now compiles. + +That's the complete set of rules needed to deal with implicit function types. + +## How to Remove Boilerplate + +The main advantage of implicit function types is that, being types, +they can be abstracted. That is, one can define a name for an implicit +function type and then use just the name instead of the full type. +Let's revisit our previous example and see how it can be made more +concise using this technique. + +We first define a type `Transactional` for functions that take an implicit parameter of type `Transaction`: + + type Transactional[T] = implicit Transaction => T + +Making the return type of `f1` to `f3` a `Transactional[Int]`, we can +eliminate their implicit parameter sections: + + def f1(x: Int): Transactional[Int] = { + thisTransaction.println(s"first step: $x") + f2(x + 1) + } + def f2(x: Int): Transactional[Int] = { + thisTransaction.println(s"second step: $x") + f3(x * x) + } + def f3(x: Int): Transactional[Int] = { + thisTransaction.println(s"third step: $x") + if (x % 2 != 0) thisTransaction.abort() + x + } + +You might ask, how does `thisTransaction` typecheck, since there is no +longer a parameter with that name? In fact, `thisTransaction` is now a +global definition: + + def thisTransaction: Transactional[Transaction] = implicitly[Transaction] + +You might ask: a `Transactional[Transaction]`, is that not circular? To see more clearly, let's expand +the definition according to the rules given in the last section. `thisTransaction` +is of implicit function type, so the right hand side is expanded to the +implicit closure + + implicit ($ev0: Transaction) => implicitly[Transaction] + +The right hand side of this closure, `implicitly[Transaction]`, needs +an implicit parameter of type `Transaction`, so the closure is further +expanded to + + implicit ($ev0: Transaction) => implicitly[Transaction]($ev0) + +Now, `implicitly` is defined in `scala.Predef` like this: + + def implicitly[T](implicit x: T) = x + +If we plug that definition into the closure above and simplify, we get: + + implicit ($ev0: Transaction) => $ev0 + +So, `thisTransaction` is just the implicit identity function on `transaction`! +In other words, if we use `thisTransaction` in the body of `f1` to `f3`, it will +pick up and return the unnamed implicit parameter that's in scope. + +Finally, here are the `transaction` and `main` method that complete +the example. Since `transactional`'s parameter `op` is now a +`Transactional`, we can eliminate the `Transaction` argument to `op` +and the `Transaction` lambda in `main`; both will be added by the compiler. + + def transaction[T](op: Transactional[T]) = { + implicit val trans: Transaction = new Transaction + op + trans.commit() + } + def main(args: Array[String]) = { + transaction { + val res = f1(args.length) + println(if (thisTransaction.isAborted) "aborted" else s"result: $res") + } + } + +## Categorically Speaking + +There are many interesting connections with category theory to explore +here. On the one hand, implicit functions are used for tasks that are +sometimes covered with monads such as the reader monad. There's an +argument to be made that implicits have better composability than +monads and why that is. +On the other hand, it turns out that implicit functions can also be +given a co-monadic interpretation, and the interplay between monads and +comonads is very interesting in its own right. +But these discussions will have to wait for another time, as +this blog post is already too long. -- cgit v1.2.3