# Building a compiler in Scala

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 509

let 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.