Review: NorDev January 2015 – Write your own compiler in 24 hours with Phil Trelford

F# deep dives

For the first NorDev meetup of 2015, Phil Trelford led a 2-hour session on how to write compilers using F#. Although I had no previous experience with F#, I was interested to learn more about the inner workings of compilers, so I briefly read up about the language the day before the event.

F# was developed in 2005 at Microsoft Research and is part of the family of .NET languages. It is a functional programming language and started as a .NET port of OCaml. Functional programming is a paradigm that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

Phil used to work in finance in London, and also likes writing programming languages for games – he wrote his first language when he was about 14 or 15 years old. Phil’s talk had the lofty ambition of teaching attendees enough information to be able to write their own compiler in 24 hours, and covered abstract syntax trees, parsing, domain specific languages, interpreters and code generation.

Phil started the session by introducing the 3 main techniques for designing a programming language:

  1. Ad hoc – creating a language from scratch (eg PHP, JavaScript and Scala),
  2. Copy & Delete – creating a new language based on an existing language, but removing some of the functionality (eg Java, J and Go). For example, Java was based on C and C++ but removed pointers and the goto statement.
  3. Copy & Add – creating a new language based on an existing language, but adding new functionality (eg C#, F# and Haskell). For example, Haskell added monads (a structure that represents computations defined as sequences of steps) and type classes (a type system construct that supports ad hoc polymorphism).

Phil then talked about the Turtle language, based on Logo, which was commonly used in the 1970s to teach children to code. He demonstrated how to write an abstract syntax tree (AST) for Turtle. He created a minimal Logo implementation using FParsec with support for procedures.

Abstract syntax trees are data structures widely used in compilers to represent the structure of program code. An AST is the result of the syntax analysis phase of a compiler and it has a strong impact on the final output of the compiler. As the language gets more complex, more items are added to the AST, which defines the commands and the valid identifiers. In the Turtle program, Phil then loaded in the AST and the interpreter before running the code, which drew geometric shapes on the screen.

Next, Phil showed us how to create a Logo to JavaScript compiler. The aim was to draw a fractal tree on an HTML5 canvas using a recursive function. The compiler took the Logo code and converted it into JavaScript, which was then executed in the browser.

In the second half of the session, Phil demonstrated how to emit code (generate code at runtime). C# compiles to .NET IL (Intermediate Language) code. For example, Phil showed us how to emit program arguments, calls to methods which puts them one by one on the stack, and then emit all the commands in the block.

Towards the end of the evening, Phil showed us his own version of Small Basic, which is another language designed to help children learn to program.  Phil joked that it is more advanced than JavaScript because it has integers!  It can have literals, variables and goto statements. Phil demonstrated this using a version of the famous FizzBuzz program. C# and Visual Basic don’t have pattern matching, but Phil’s version of Small Basic does.

Phil also talked about how he had written an AST for C# in the past. It needed a large expression list (larger than for Small Basic). He parsed complex code via this compiler which took about 2 hours. Neil Danson (another F# programmer) wrote a C# parser and compiler in 3 weeks even though he had no prior compiler-writing experience.

To wrap up the session, Phil recommended some books for anyone who is interested in learning more about F# and functional programming, including his own title “F# Deep Dives”. Tryfsharp.org is a good website for learning F# from scratch. It lets you edit and run your code in the browser.

In summary, I enjoyed the talk even though I had no previous experience with F#. It was a very informative talk, and I found it interesting to learn more about how compilers and interpreters work.

Words: Victoria Holland

 

 

 

    Keep up to date by email

    Sign-up to receive regular updates on all of our content and site activities.