The Scala Compiler Corner:     A collection of resources contributed by the Scala user community (Think of this collaborative effort as each blind man describing a fragment of the elephant)

Code walkthroughs of compilation phases of the Scala compiler

These write-ups have been typeset with LaTeX, using this template. There are many good editors for LaTeX out there. The Eclipse-based TeXlipse, although not the most feature-rich, has worked for me.

Further information on compilation phases

• Pattern Matching (package scala.tools.nsc.matching) was designed by Burak Emir and is explained in his PhD report
• Explicit Outer and Lambda Lift are covered in Philippe Altherr's PhD
• Pickler and its interplay with reflection are discussed in http://lamp.epfl.ch/teaching/projects/archive/coppel_report.pdf
• Annotation processing, http://www.scala-lang.org/sid/5
• Tail call elimination, an early overview appears in this 2001 paper
• Mixins as of Scala 1.0 are described by Michel Schinz in his PhD report. The Change Log of the Scala Language Spec mentions differences with Scala 2.x traits.

Information from the source

• Videos discussing internals of the Scala compiler
• Some of the papers at the Scala website contain overviews of (some) compilation phases
• Implementing First-Class Polymorphic Delimited Continuations by a Type-Directed Selective CPS-Transform. Paper   Video
• Student projects at LAMP (topic offers and completed)

Master theses with a compiler-plugin as prototype

• Kaichuan Wen, 2010. Object-oriented LINQ for Scala
• ScalaQL, 2009.
• Valentin Wüstholz, 2009. Encoding Scala Programs for the Boogie Verifier
• Manfred Stock, 2008. Implementing a Universe Type System for Scala

Project ideas

• Google Summer of Code Scala Projects 2010, including among others:
  • A new backend for the Scala.Net compiler to generate C# sources
  • Adding LINQ-awareness to Scala.Net
• Adding LINQ-awareness to Scala.Net. PDF
• Scalify.NET and joint compilation of Scala and C#. PDF
• Translation of dynamically-typed languages into Scala. PDF
• Parallelizing the Scala compiler: Most of the transformations that each of superaccessors till cleanup perform, one after the other, one compilation unit after the other, actually operate on their own portion of an AST. For example, the effects of a single tailcalls-rewriting are limited to a single method body. In principle, all those rewritings could be performed in parallel (the other method definitions need not know how a particular method is rewritten). I'm not saying the current implementation of tailcalls is thread-safe. What I'm saying is that if compilation phases were structured following the architecture for task-level parallelism of java.util.concurrent then most worries about compilation speed would vanish. Summing up: all collected ASTs constitute the shared mutable state, each transformation is realized by a component spawning tasks, "component" meaning keeping all of the mutable state required for its operation stack-local or thread-confined. The programming techniques above (that have to be manually applied) are adopted as the native programming model by X10 and Fortress (trees instead of lists, semi-balanced trees, hierarchical places) only that for numerical computing. Details appear in the talk by Guy Steele foldl and foldr considered slightly harmful. The lessons are the same for AST processing. On a related note:
  • "Towards a multi-threaded javac" (Jonathan Gibbons)
  • RFE for javac
  • RFE for ecj
• Bytecode Contracts: Scala's bytecode generation could be extended to generate BML annotations, for consumption by a program verification tool (an IDE-based editor is also available). This sounds like the JVM-counterpart of Microsoft's CodeContracts. Some BML expressions can be generated from Scala expressions, others from an encoding of BML as an embedded DSL.
• Export and Import of ASTs: In principle, AST processing can be expressed more easily with Stratego-like constructs, as supported by Kiama. Given that the internal representation of Scala ASTs has been optimized for speed (same as in Java compilers), a conversion is necessary (as reported in Fusing a Transformation Language with an Open Compiler). Admittedly, there are pros and cons to both the term-rewriting and the graph-rewriting styles. The X10 compiler has built-in support to export/import ASTs.
• Type lattice visualization: Rather than trying to understand head-on how the typechecker works ;-) it might be useful to visualize first what the typechecker does for a given run (which type lattice it computes). At least one other component of the Scala compiler generates a DOT file to illustrate its operation (-Xgenerate-phase-graph). In IDE-speak, a type lattice is called a "UML Class Hierarchy". Actually, it need not be IDE-based: Scaladoc2 could be retrofitted to perform code-summarization as in Spinelli's UMLGraph.
• Typestate analysis for Scala: It would be interesting to know whether declarative points-to analyses (paper and source code) can scale up when object abstractions track typestates. There are different expressiveness levels for typestate properties, all sharing the limitation to temporal safety (no liveness). Recent work includes analyses for socket-style APIs, as well as for more elaborate API protocols (e.g., JDBC). More related work: (1) certain typestate properties are captured by type systems (such as X10’s constrained types) supporting property-dependency where “property” means “final value-typed field set at the latest by object instantiation time”. (2) The original GoF State design pattern also detects protocol violations, only that at runtime. (3) There are heroic efforts to encode some form of dependent types in Scala (HList and all that, made possible by –Yrecursion and –experimental). A dedicated compiler plugin can instead dispense with all the resulting syntactic burden. (4) Ordered Datalog for refactoring analyses.
• A framework for pluggable type systems: As discussed in this thread, the JSR 308 Checkers framework encapsulates many recurring tasks that a pluggable type checker must implement. So far, there is no similar infrastructure on which to base a compiler plugin for scalac.
• Inference of static semantics: At each compilation phase, ASTs are expected to comply with certain well-formedness conditions (which embody the static semantics of the language fragment allowed at the end of that phase). Problem is, those conditions have not been documented in a machine-processable manner. In principle, given enough runs, it should be possible to infer a subset of them, using tools like Daikon

Looming on the horizon

• invokedynamic, http://blogs.sun.com/jrose/resource/pres/200910-VMIL.pdf
• tail-calls support, http://www.ssw.uni-linz.ac.at/Research/Papers/Schwaighofer09Master/
• tailcalls meet invokedynamic
• lazy continuations, http://www.ssw.uni-linz.ac.at/Research/Papers/Stadler09/

For verification (and automated testing) fans

Blog entries covering aspects of the compiler

Compiler descriptions for other languages (only that, these descriptions are self-contained!)

• Implementing functional languages: a tutorial (1992)
  This book gives a practical approach to understanding implementations of non-strict functional languages using lazy graph reduction.
• The Structure Of The Essential Haskell Compiler
  Both language and implementation are split into smaller, manageable steps, using specific tools to generate parts of the compiler from higher level descriptions. Project homepage

Other open-source VM-compilers for languages with a functional flavor

Not a language shootout, but cross-pollination