Building a compiler in Scala

5 min readNov 11, 2015

My last post did generate a lot of comments about Scala and C#, how they compare to each other and why things were done in the way they are in the Scala world. Thanks Viktor for that.

Many people said I did not know enough Scala to be doing the kind of comparison I did, and they also were right, up to some point anyways. In order to overcome this obstacle and learn more about this magnificent programming language, I decided to put together my computer science background and my will to fully incorporate Scala into my life.

PCF

Programming Language for Computable Functions (PCF) is a functional programming language mostly used in the academia, but very suitable for my purpose.

The Language

PCF has the main characteristics of any functional programming language so let’s review them.

Functions Are First-Class Objects.
Functions are defined in the following way

fun f -> fun x -> f (f x)

Functions with Several Arguments

In PCF, there is no symbol to build a function with several arguments. These functions are built as functions with one argument, using the isomorphism (A × B) -> C = A -> (B -> C). For instance, the function that associates to x and y the number xx+yy is defined as the function associating to x a function, which in turn associates to y the number xx+yy, that is, fun x -> fun y -> x * x + y * y.

No Assignments

In contrast with languages such as Caml or Java, the main feature of PCF is a total lack of assignments. There is no construction of the form x := t or x=t to assign a value to a “variable”.

f -> fun n -> ifz n then 1 else n * (f (n - 1))

The grammar of PCF is very simple and we can define it as follow

t=x
| fun x -> t
| t t
| n
| t + t | t - t | t * t | t / t
| ifz t then t else t
| fix x t
| let x = t in t

Seems small? Well, PCF is Turing complete, that is, all computable functions can be programmed in PCF.

In order to do it more interesting I modify the grammar as follow

Exp ::=  x | n                               
| true                            
| false                           
| succ                            
| pred                            
| iszero                          
| if Exps then Exps else Exps     
| fun x -> Exps                   
| rec x -> Exps                   
| (Exps)                         
| let x = Exps in Exps                   
Exps ::= Exps Exp | Exp

Still it is the same language.

My idea is to build a compiler for the extended PCF using Scala but also show how functional programming can help us to get our goal.

Functional Programming

Functional programming has been a topic which has increased in popularity; however, when I posted Sorting in Scala, tails of Functional Programming a lot of criticism was generated about it.

This time, we are going to build a compiler for a functional programming language using pure functional programming. We will see how this task can be achieve easily by the use of the pattern matching and other techniques you will discover on the code.

PCF examples

In order to understand what we want to build, let’s take a look at some examples of programs that can be written on PCF.

Double

# Evaluates to NUM 74(rec d -> fun n -> if iszero n then 0 else succ (succ (d (pred n)))) 37

Fibonacci

# Evaluates to NUM 6765.
let plus = rec p ->
      fun x -> fun y -> if iszero x then y else p (pred x) (succ y)
in
  let fibonacci = rec f ->
    fun n -> if iszero n then
          0
        else if iszero (pred n) then
          1
        else
          plus (f (pred n)) (f (pred (pred n)))
  in
    fibonacci 20

Minus

# Evaluates to NUM 46.let minus = rec m ->
      fun x -> fun y -> if iszero y then x else m (pred x) (pred y)
in
  minus 125 79

Factorial

# Evaluates to NUM 720.let plus = rec p ->
      fun x -> fun y -> if iszero x then y else p (pred x) (succ y)
in
  let times = rec t ->
    fun x -> fun y -> if iszero x then 0 else plus y (t (pred x) y)
  in
    let factorial = rec f ->
      fun n -> if iszero n then 1 else times n (f (pred n))
    in
      factorial 6

Ackermann’s function

# Evaluates to NUM 509let Ack = rec A ->
  fun x -> fun y ->
    if iszero x then
      succ y
    else if iszero y then
      A (pred x) 1
    else
      A (pred x) (A x (pred y))
in
  Ack 3 6

A more complicated example will we implementing a list, yes a list! We need to use first-class functions. Let’s take a look.

let cons = fun x -> fun xs -> fun n ->
  if iszero n then x else if iszero (pred n) then xs else false
in
  let nil = fun n -> true   # This is flawed; hd nil and tl nil both return true!
  in
    let hd = fun f -> f 0
    in
      let tl = fun f -> f 1
      in
        let null = fun f -> f 2
        in
          let equal = rec e ->  # This tests whether two integers are equal.
            fun a -> fun b -> if iszero a then
              iszero b
            else if iszero b then
              false
            else
              e (pred a) (pred b)
          in
            let member = rec m ->
              fun n -> fun ns -> if null ns then
                     false
                   else if equal n (hd ns) then
                     true
                   else
                     m n (tl ns)
            in
              member 4 (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 nil)))))

The output of this program is, of course, BOOL true. Unfortunately, lists can’t be displayed nicely, they print out as huge FUN terms…

What has been done?

Last night, I created a Github repository and started pushing some code. I already have a Lexer to do the tokenization work and a Parser to build the AST. Because I love types, I want PCF to be type safe, so I am planning to finish the Type Inference System module tomorrow. By the end of the week an small evaluator should be ready.

Once this part is done, I might want to generate byte code so it can be executed over the JVM, I don’t have any experience in this area, so any help will be appreciated.

Test Driven Development (TDD)

Because we are TDD addicts, all existent code has been written using these development techniques. If you read the test, don’t worry about functional implementation details.

Endings

I hope that when this small project is done I have gotten a better understanding of the Scala language and my mind has bend to the functional programming mindset.

I really appreciate all comments in my previous posts, thanks.