fscala2c

A compiler compiling a Scala subset, Featureweight Scala, to native C.

Compiler course project at BUPT.

Phases:

• Frontend
  • Tokenizing
  • Parsing
  • Typing
• Backend
  • Scala Core IR optimizing
  • C Core IR generation
  • C Core IR optimizing
  • C code generation

Roadmap

• Tokenizer

• packratc: Packrat Parser Combinator library

• Parser: tokens --> Featherweight Scala raw AST

• Typer: Raw AST --> Typed AST (Scala Core IR)

  • Local type inference for expressions
  • Hindley-Milner type inference for recursive definition group in block expressions
  • Hindley-Milner type inference for recursive class definition

• (CANCELLED) Optimize typed AST (optimization is so boring; let's do this later)

• Typed AST --> C AST (C Core IR)

• (CANCELLED) Optimize C AST

• C AST --> C source code

Examples

Fibonacci Array (CPS)

We will compile the following FScala code to C:

class Main {
  val fibonacci = (n: Int, callback: Int => Int) =>
    if n <= 1 then
      callback(1)
    else
      fibonacci(n - 1, (t1: Int) => fibonacci(n - 2, (t2: Int) => callback(t1 + t2)))

  val identity = (x: Int) => x

  val main = () => {
    val n = readInt()
    val res = fibonacci(n, identity)
    printlnInt(res)
  }
}

Note that the above example uses continuation-passing-style (CPS) to compute the Fibonacci array. The CPS style utilizes first-class functions (lambda literals and passing functions just like any other value), which is typically not very usable or even not available in low-level languages like C.

Assuming that the file is located at fibo_cps.scala, We can compile it to C with:

sbt 'run --source fibo_cps.scala --output out/fibo_cps.c'

The compiled the file could be found at out/fibo_cps.c. Compile it with clang:

clang out/fibo_cps.c -O3 -o out/fibo_cps

And run it:

$ ./out/fibo_cps
10
89

Voila! The Scala code is compiled to C and runs smoothly in machine code!

Development

Scala 3 is used as the developing language, with the sbt building tools.

Either Intellij or any editor supporting LSP protocol can be used as an IDE.

Intellij

For Intellij, simply open the project directory and import. Everything will be set up in the IDE automatically.

Editors Supporting LSP

For any LSP-compatible editor, say Emacs, configure the editor's support for the metals client, and import the build. If it complains about the missing of bloop project, run sbt in the directory first, and a .bloop/ directory will be generated automatically.

Typically, install the metals server manually will be a good idea. You can install it with coursier by

cs install metals

References

• Hindley-Milner type inference for recursive definition groups: Wikipedia, Blog

• Closure conversion for compiling lambda expressions to global definitions: Slides, Blog, Tutorial