Is writing a compiler Hello World for F# ?

Question

I don't believe seeing this. It says:

For April, Chris Smith will be presenting on writing a Java to x86 Compiler in F#.

The presentation may go on for an hour or two which definitely is not enough to write a compiler. I've heard that F# is powerful, but this powerful?

Well, all I wanted to ask is this: Can you write a compiler in F# that quickly?

Answer 1

Giving a presentation about a project isn't the same thing as implementing the whole project during the presentation.

It's perfectly possible to present some interesting aspects of a Java to x86 compiler within an hour, and even show some code: but that's not the same as creating all the code then and there.

Answer 2

Java is a fairly complex language, so I suppose that Chris isn't going to implement a complete Java compiler. However, his talk really points out that manipulating with code (and tree-like structures in general) is much easier in F# than in any other .NET language. That's why F# has been used in various static analysis tools (e.g. Microsoft's static driver verifier)

Tools like fslex and fsyacc make it easy to write parser for a language. Chris has a blog with simple mathematical expressions. Robert Pickering wrote a more sophisticated example that actually generates IL code (compiles mathematical expressions to .NET) in just a few lines of code. This can be even easier on .NET 4.0 if you generate code using Expression Trees.

So I suppose that even if he was writing the compiler from scratch, he could write compiler for a langauge that can be used to write non-trivial sample programs.

Answer 3

Let's first start with a few corrections:

• It's not a Java compiler, it's a compiler for a small subset of Java.
• It doesn't say anywhere that the compiler will be written in the time, only that it will be explained.
• In fact, it doesn't even say that, it says, it will be presented. Heck, I can present GCC in 3 minutes. It's not gonna be a very useful presentation, but it's gonna be a presentation.

That said, explaining a well-structured, simple compiler for a simple language implemented in a language which is well-suited for writing compilers within an hour is definitely feasible.

F# is a member of the ML family of languages (specifically, a close cousin of OCaml), and those are indeed well-suited for writing compilers. In fact, the reason why Robin Milner chose the name ML (meta language) for his language, was because it is specifically designed for writing compilers. A compiler is basically a big function (thus making it very natural to implement in a functional language) that detects patterns (thus making it very natural to implement in a language with pattern matching) and executes a little bit of code for each pattern it detects (thus making it very natural to implement in a language with first-class functions). And whaddayaknow? F# is a functional language with very sophisticated pattern matching facilities. Another nice feature is an expressive type system with algebraic data types and discriminated unions which makes it very easy to represent Abstract Syntax Trees.

At the Lang.NET Symposium Jason Olson gave a talk on F#, during which he showed some pieces of an interpreter that he is currently working on that demonstrate these features very well.

Fredrik Holmström is currently working on IronJS, an ECMAScript 3 implementation for the Dynamic Language Runtime. Take a look at the code, specifically the AST types and some of the analysis and parsing code.

Jonathan Tang's Write Yourself a Scheme in 48 Hours is another good example of writing an interpreter, this time in Haskell which shares many features with F#.

The 90 Minute Scheme to C compiler by Marc Feeley is a presentation about a Scheme compiler written in Scheme.

In Implementing Scheme in Ruby, James Coglan teaches the audience Scheme, live-codes and explains a Scheme interpreter in Ruby and writes a couple of sample Scheme programs, all in 15 minutes.