diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/blog/_posts/2016-12-05-implicit-function-types.md | 364 | ||||
| -rw-r--r-- | docs/dotc-internals/core-data-structures.md | 113 | ||||
| -rw-r--r-- | docs/syntax-summary.txt | 16 |
3 files changed, 484 insertions, 9 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 new file mode 100644 index 000000000..670c652ee --- /dev/null +++ b/docs/blog/_posts/2016-12-05-implicit-function-types.md @@ -0,0 +1,364 @@ +--- +layout: blog +title: Implicit Function Types +author: Martin Odersky +authorImg: /images/martin.jpg +--- + +I just made the [first pull request](https://github.com/lampepfl/dotty/pull/1775) 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 contextual +abstraction to Scala_". What do I mean by this? + +**Abstraction**: The ability to name a concept and use just the name afterwards. + +**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, + - wiring components up with dependency injection, + - defining the meanings of operations with type classes, + - more generally, passing any sort of context to a computation. + +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 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. + +## Implicit Parameters + +In a functional setting, the inputs to a computation are most +naturally expressed as _parameters_. One could simply augment +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. Consequently, it becomes +tedious to define all those intermediate parameters and to pass them +along to where they are eventually consumed. + +Implicit parameters solve one half of the problem. Implicit +parameters do not have to be propagated using boilerplate code; the +compiler takes care of that. This makes them practical in many +scenarios where plain parameters would be too cumbersome. For +instance, type classes would be a lot less popular if one would have +to pass all dictionaries by hand. Implicit parameters are also very +useful as a general context passing mechanism. For instance in the +_dotty_ compiler, almost every function takes an implicit context +parameter which defines all elements relating to the current state of +the compilation. This is in my experience much better than the cake +pattern because it is lightweight and can express context changes in a +purely functional way. + +The main downside of implicit parameters is the verbosity of their +declaration syntax. It's hard to illustrate this with a smallish example, +because it really only becomes a problem at scale, but let's try anyway. + +Let's say we want to write some piece of code that's designed to run +in a transaction. For the sake of illustration here's a simple transaction class: + + class Transaction { + private val log = new ListBuffer[String] + def println(s: String): Unit = log += s + + private var aborted = false + private var committed = false + + def abort(): Unit = { aborted = true } + def isAborted = aborted + + def commit(): Unit = + if (!aborted && !committed) { + Console.println("******* log ********") + log.foreach(Console.println) + committed = true + } + } + +The transaction encapsulates a log, to which one can print messages. +It can be in one of three states: running, committed, or aborted. +If the transaction is committed, it prints the stored log to the console. + +The `transaction` method lets one run some given code `op` inside +a newly created transaction: + + def transaction[T](op: Transaction => T) = { + val trans: Transaction = new Transaction + op(trans) + trans.commit() + } + +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 +by passing the current transaction as an implicit parameter. + + def f1(x: Int)(implicit thisTransaction: Transaction): Int = { + thisTransaction.println(s"first step: $x") + f2(x + 1) + } + def f2(x: Int)(implicit thisTransaction: Transaction): Int = { + thisTransaction.println(s"second step: $x") + f3(x * x) + } + def f3(x: Int)(implicit thisTransaction: Transaction): Int = { + thisTransaction.println(s"third step: $x") + if (x % 2 != 0) thisTransaction.abort() + x + } + +The main program calls `f1` in a fresh transaction context and prints +its result: + + def main(args: Array[String]) = { + transaction { + implicit thisTransaction => + val res = f1(args.length) + println(if (thisTransaction.isAborted) "aborted" else s"result: $res") + } + } + +Two sample calls of the program (let's call it `TransactionDemo`) are here: + + scala TransactionDemo 1 2 3 + result: 16 + ******* log ******** + first step: 3 + second step: 4 + third step: 16 + + 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. + +## Conclusion + +Implicit function types are unique way to abstract over the context in +which some piece of code is run. I believe they will deeply influence +the way we write Scala in the future. They are very powerful +abstractions, in the sense that just declaring a type of a function +will inject certain implicit values into the scope of the function's +implementation. Can this be abused, making code more obscure? +Absolutely, like every other powerful abstraction technique. To keep +your code sane, please keep the [Principle of Least Power](http://www.lihaoyi.com/post/StrategicScalaStylePrincipleofLeastPower.html) in mind. diff --git a/docs/dotc-internals/core-data-structures.md b/docs/dotc-internals/core-data-structures.md new file mode 100644 index 000000000..eddc3398c --- /dev/null +++ b/docs/dotc-internals/core-data-structures.md @@ -0,0 +1,113 @@ +(The following is work in progress) + +## Symbols and SymDenotations + + - why symbols are not enough: their contents change all the time + - they change themselvesSo a `Symbol + + - reference: string + sig + + +Dotc is different from most other compilers in that it is centered around the idea of +maintaining views of various artifacts associated with code. These views are indexed +by tne + +A symbol refers to a definition in a source program. Traditionally, + compilers store context-dependent data in a _symbol table_. The + symbol then is the central reference to address context-dependent + data. But for `dotc`'s requirements it turns out that symbols are + both too little and too much for this task. + +Too little: The attributes of a symbol depend on the phase. Examples: +Types are gradually simplified by several phases. Owners are changed +in phases `LambdaLift` (when methods are lifted out to an enclosing +class) and Flatten (when all classes are moved to top level). Names +are changed when private members need to be accessed from outside +their class (for instance from a nested class or a class implementing +a trait). So a functional compiler, a `Symbol` by itself met mean +much. Instead we are more interested in the attributes of a symbol at +a given phase. + +`dotc` has a concept for "attributes of a symbol at + +Too much: If a symbol is used to refer to a definition in another +compilation unit, we get problems for incremental recompilation. The +unit containing the symbol might be changed and recompiled, which +might mean that the definition referred to by the symbol is deleted or +changed. This leads to the problem of stale symbols that refer to +definitions that no longer exist in this form. `scalac` tried to +address this problem by _rebinding_ symbols appearing in certain cross +module references, but it turned out to be too difficult to do this +reliably for all kinds of references. `dotc` attacks the problem at +the root instead. The fundamental problem is that symbols are too +specific to serve as a cross-module reference in a system with +incremental compilation. They refer to a particular definition, but +that definition may not persist unchanged after an edit. + +`dotc` uses instead a different approach: A cross module reference is +always type, either a `TermRef` or ` TypeRef`. A reference type contains +a prefix type and a name. The definition the type refers to is established +dynamically based on these fields. + + +a system where sources can be recompiled at any instance, + + the concept of a `Denotation`. + + Since definitions are transformed by phases, + + +The [Dotty project](https://github.com/lampepfl/dotty) +is a platform to develop new technology for Scala +tooling and to try out concepts of future Scala language versions. +Its compiler is a new design intended to reflect the +lessons we learned from work with the Scala compiler. A clean redesign +today will let us iterate faster with new ideas in the future. + +Today we reached an important milestone: The Dotty compiler can +compile itself, and the compiled compiler can act as a drop-in for the +original one. This is what one calls a *bootstrap*. + +## Why is this important? + +The main reason is that this gives us a some validation of the +*trustworthiness* of the compiler itself. Compilers are complex beasts, +and many things can go wrong. By far the worst things that can go +wrong are bugs where incorrect code is produced. It's not fun debugging code that looks perfectly +fine, yet gets translated to something subtly wrong by the compiler. + +Having the compiler compile itself is a good test to demonstrate that +the generated code has reached a certain level of quality. Not only is +a compiler a large program (44k lines in the case of dotty), it is +also one that exercises a large part of the language in quite +intricate ways. Moreover, bugs in the code of a compiler don't tend to +go unnoticed, precisely because every part of a compiler feeds into +other parts and all together are necessary to produce a correct +translation. + +## Are We Done Yet? + +Far from it! The compiler is still very rough. A lot more work is +needed to + + - make it more robust, in particular when analyzing incorrect programs, + - improve error messages and warnings, + - improve the efficiency of some of the generated code, + - embed it in external tools such as sbt, REPL, IDEs, + - remove restrictions on what Scala code can be compiled, + - help in migrating Scala code that will have to be changed. + +## What Are the Next Steps? + +Over the coming weeks and months, we plan to work on the following topics: + + - Make snapshot releases. + - Get the Scala standard library to compile. + - Work on SBT integration of the compiler. + - Work on IDE support. + - Investigate the best way to obtaining a REPL. + - Work on the build infrastructure. + +If you want to get your hands dirty with any of this, now is a good moment to get involved! +To get started: <https://github.com/lampepfl/dotty>. + diff --git a/docs/syntax-summary.txt b/docs/syntax-summary.txt index 04e149de6..d382507d3 100644 --- a/docs/syntax-summary.txt +++ b/docs/syntax-summary.txt @@ -95,8 +95,8 @@ grammar. | [id '.'] `super' [ClassQualifier] `.' id ClassQualifier ::= `[' id `]' - Type ::= FunArgTypes `=>' Type Function(ts, t) - | HkTypeParamClause `=>' Type TypeLambda(ps, t) + Type ::= [`implicit'] FunArgTypes `=>' Type Function(ts, t) + | HkTypeParamClause `=>' Type TypeLambda(ps, t) | InfixType FunArgTypes ::= InfixType | `(' [ FunArgType {`,' FunArgType } ] `)' @@ -125,13 +125,13 @@ grammar. TypeBounds ::= [`>:' Type] [`<: Type] | INT TypeBoundsTree(lo, hi) TypeParamBounds ::= TypeBounds {`<%' Type} {`:' Type} ContextBounds(typeBounds, tps) - Expr ::= FunParams `=>' Expr Function(args, expr), Function(ValDef([implicit], id, TypeTree(), EmptyTree), expr) + Expr ::= [`implicit'] FunParams `=>' Expr Function(args, expr), Function(ValDef([implicit], id, TypeTree(), EmptyTree), expr) FunParams ::= Bindings - | [`implicit'] id + | id | `_' ExprInParens ::= PostfixExpr `:' Type | Expr - BlockResult ::= (FunParams | [`implicit'] id `:' InfixType) `=>' Block + BlockResult ::= [`implicit'] FunParams `=>' Block | Expr1 Expr1 ::= `if' `(' Expr `)' {nl} Expr [[semi] else Expr] If(Parens(cond), thenp, elsep?) | `if' Expr `then' Expr [[semi] else Expr] If(cond, thenp, elsep?) @@ -178,9 +178,7 @@ grammar. | {Annotation} {LocalModifier} TmplDef | Expr1 | - ResultExpr ::= Expr1 - | (Bindings | ([`implicit'] id | `_') `:' ) `=>' Block - Function(args, block) // block starts at => + ForExpr ::= `for' (`(' Enumerators `)' | `{' Enumerators `}') ForYield(enums, expr) {nl} [`yield'] Expr ForDo(enums, expr) | `for' Enumerators (`do' Expr | `yield' Expr) @@ -241,7 +239,7 @@ grammar. DefParams ::= DefParam {`,' DefParam} DefParam ::= {Annotation} [`inline'] Param ValDef(mods, id, tpe, expr) -- point of mods at id. - Bindings ::= `(' Binding {`,' Binding `)' bindings + Bindings ::= `(' Binding {`,' Binding}] `)' Binding ::= (id | `_') [`:' Type] ValDef(_, id, tpe, EmptyTree) Modifier ::= LocalModifier |