in which a compiler gets its wings

I've enjoyed writing Lua code for my side projects for the most part. It has a few quirks, but many of them can be solved by a little linting. For a non-homoiconic language there is little in the syntax to object to, and the aggressively minimalist semantics more than make up for the few shortcomings.

Still, I always wondered what it would be like to use a language that compiled to Lua and didn't have problems like the statement vs expression distinction, lack of arity checks, or defaulting to globals. Over the past year or so I looked at several such languages1, but nothing ever stuck. Then a few weeks ago I found Fennel (at the time called "fnl"), and it really resonated with me.

The Microlanguage

snowy sidewalk

The thing that sets Fennel apart is that it is strictly about adding new syntax to Lua and keeping Lua's semantics. This allows it to operate as a compiler which introduces no runtime overhead. Code in Fennel translates trivially to its Lua equivalent:

(let [x (+ 89 5.2)
      f (fn [abc] (print (* 2 abc)))]
  (f x))

... becomes ...

  local x = (89 + 5.2000000000000002)
  local function _0_(abc)
      return print((2 * abc))
  local f = _0_
  return f(x)

There are a few quirks around introducing temporary variable names in cases where it's unnecessary like the above, but these are only readability concerns and do not affect the performance of the code, since Lua is smart enough to collapse it down. The temporary locals are introduced in order to ensure that every form in Fennel has a value; there are no statements, only expressions. This fixes a common problem in Lua where you can't use an if to calculate the value of an expression, because it's implemented as a statement, so you have to construct complex and/or chains to simulate if expressions. Plus it's just simpler and more consistent to omit statements completely from the language semantics.

The one exception to the no-overhead rule is Fennel's lambda form. Fennel's fn keyword compiles straight to a no-nonsense Lua function with all that implies. But Lua's function has one feature that is quite error-prone: it doesn't check to ensure that it was called with the correct number of arguments. This leads to nil values easily getting propagated all thru the call stack by mistake. Fennel's solution to this is lambda, which includes checks to ensure that this doesn't happen. This function will signal an error when it's called with zero or one argument, but the ?w and ?h arguments are optional:

(lambda [x y ?w ?h]
  (make-thing {:x x :y y
               :width (or ?w 10) :height (or ?h 10)}))

The other main difference between Fennel and Lua is that Fennel takes more care to distinguish between sequential tables and key/value tables. Of course on the Lua runtime there is no difference; only one kind of table exists, and whether it is sequential or not is just a matter of how it's constructed or used. Lua uses {} notation for all tables, but Fennel allows you to construct sequential tables (array-like tables which have consecutive integers as keys) using [] instead. Lua overloads the for keyword to iterate over a numeric range as well as to work with generic iterators like pairs for values in tables. Fennel uses each for the latter, which makes the difference clearer at a glance.

The Compiler

To be clear, these are very small improvements over Lua. Normally I wouldn't consider switching to a new language over such things. But Fennel is unique in its simplicity and lack of overhead, so it doesn't cost much to bring it in. When I found out about Fennel, it was an experimental compiler that had been written over the course of one week in 2016 and then forgotten. But I was impressed with how useful it was after only that week of development. I could see at a glance that in around a thousand lines of code it had a functional compiler that output fairly readable Lua code and fixed the problem of statements.

So I dived into the codebase and started adding a few conveniences, starting with a test case and some static analysis. When Fennel's creator Calvin Rose saw what I was doing, he gave me feedback and started to pick back up on development too. As I got more comfortable with the code I started adding features, like each, when, and comments. Then I started putting it thru the paces by porting some of my existing Lua programs over2. This went much more smoothly than I anticipated. I did find a few compiler bugs, but they were either easy to fix myself or fixed quickly by Calvin Rose once I pointed them out. Once I had a few programs under my belt I wrote up an introductory tutorial to the language that you should read if you want to give it a try.

Tumwater falls, with raging water

But what about the lines?

But one thing really bothered me when writing Fennel programs. When you needed to debug, the Lua output was fairly readable, but you quickly ran into the curse of all source→source compilers: line numbers didn't add up. Some runtimes allow you to provide source maps which change the numbering on stack traces to match the original source code, but Lua runtimes don't offer this. If your compiler emits bytecode instead of source, you can set the line numbers for functions directly. But then you're tied to a single VM and have to sacrifice portability.

So what's a poor compiler to do? This being Fennel, the answer is "the simplest thing possible". In this case, the simplest thing is to track the line number when emitting Lua source, and only emit newlines when it's detected that the current output came from input with a line number greater than the one it's currently on.

For most compilers, this naive approach would quickly fall to pieces. Usually you can't rely on the output being in the same order as the input that generated it3. I honestly did not have high hopes for this when I started working on it. But because of Fennel's 1:1 simplicity and predictability, it actually works surprisingly well.

The future?

At this point I'm pretty happy with where the compiler is, so my own plans are mostly just to write more Fennel code. The upcoming Lisp Game Jam will be a perfect excuse to do just that. I have a few ideas for further compiler improvements, like associative destructuring (sequential destructuring already works great), pattern matching, or even making the compiler self-hosting, but there's nothing quite like getting out there and banging out some programs.

[1] Here's a list of the lisps I found that compile to Lua and my brief impression of them:

An experimental lisp by the creator of Moonscript. Looks neat, but it requires an alpha build of Moonscript 0.2.0 from 2012 to run.
Inspired by Hy, this seems to be an improvement over Hy, since the latter inherits some of Python's unfortunate design bugs around scoping. If you're a Hy user, this might be a nice way to trade library availability for speed and consistency, but since the compiler is written in Hy it means you need two runtimes, which complicates deployment.
This looked promising when it was first announced, but it was based on a very early version of ClojureScript that was still quirky and didn't have a repl, and was abandoned a few months after it was announced. It has the same problem of requiring a separate runtime for the compiler as Hua, except that runtime needs dramatically greater resources.
This actually looks pretty nice if you like Scheme. It's pretty immature, but probably wouldn't take that much work to get to a usable state. Personally I find Lua tables to be much more friendly to work with than Scheme's lists, so sticking strictly with Scheme's semantics seems like a step backwards, but I know some people like it.
I actually did use this in my game. But since I tried it the compiler has been more or less completely rewritten. The unique thing about the new l2l compiler is that it allows you to mix Lua code and lisp code in the same file. I found it rather difficult to follow code that does this, but it's an interesting idea. The readme for l2l includes some very apt Taoist quotations, which earns it extra points in my book.
I saved the best for last. Urn is a very impressive language with a smart compiler that has great error messages, pattern matching, and tree-shaking to strip out code that's not used. The main reason I decided not to use Urn is that it wants to do a lot of optimization and analysis up-front and sacrifices some interactivity and reloading features to achieve it. As one who prizes interactivity above all other considerations, I found it a poor fit. Urn wants to be its own language that just uses Lua as a runtime, and that's great, but right now I'm looking for something that just takes Lua and makes the syntax nicer.

[2] My first program was a 1-page Pong, which is kind of the "hello world" of games. Then I ported the user-level config from Polywell, my Emacs clone, over to Fennel. This has made Polywell seem a lot more Emacsy than it used to be.

[3] Of course, once macros are introduced to the picture you can write code where this guarantee no longer applies. Oddly enough I'm not particularly interested in complex macros beyond things like pattern matching, so I don't see it being a problem for code I write, but it's worth noting that there are complications.

« older | 2018-03-03 08:35:16