Review: NorDev January 2015 - Write your own compiler in 24 hours

Home

About Us

Events

Contact

Tech Map

Download Magazine NorDevCon 2015 Edition April 2014 March 2014 February 2014 January 2014 December 2013 November 2013

NorDevCon 2015 Edition

April 2014

March 2014

February 2014

January 2014

December 2013

November 2013

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:

Ad hoc – creating a language from scratch (eg PHP, JavaScript and Scala),

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.

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

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

Software Development Team Lead & Test Automation Engineer at Tribal (Norwich)

Roles at Angling Direct (Norfolk)

Job Vacancy: Senior PM at Foolproof

Job Vacancy: Programme Manager at Foolproof

Job Vacancy: Senior Designer at Foolproof

Job Vacancy: Account Manager at Foolproof

Job Vacancy: Software Engineer in Test at Axon Vibe

Job Vacancy- EIRA Knowledge Exchange Fellow – EIRA Network (3 Posts)

Job Vacancy- EIRA Knowledge Exchange Manager (Three Year Fixed Term Contract)

Job Vacancy- Front end developer at Zipline

Join us for the nor(DEV):con 2019 Business Sessions: Running a business is hard!

nor(DEV):con 2019 schedule live now!

Emerging talent at the DevelopHER Awards 2018!

Naked Element Backs a Winning Team at Sync the City!

Badminton

How the employer voice can influence technical & vocational training

Special: Azure Sphere: Intelligent Edge & Logging is Hot Again (with free food!)

The Very Slow Time Machine with Jez Higgins & Me TV with Russel Winder

Deep Tech is affecting people’s lives without them even knowing it.