Building a Typed Lisp for BEAM: Erie

This isn’t the release of a new language, but rather me trying to document my journey building one. Future posts will range between tutorial-like and brain-dump.

This is my first attempt at writing a compiler, so I’m nowhere near expert level. The code isn’t available on Github yet, but I plan to put it up soon.

https://thaterikperson.com/new-lang-on-beam

I’d love to hear comments and thoughts on my approach/design/code/etc. I’ll add future updates to this thread as I write them.

11 Likes

Always wonderful to see more people making languages. I look forward to hearing more about your project :slight_smile:

4 Likes

Next installment is up. https://thaterikperson.com/parsing-erie-to-eaf

This describes using leex and yecc to compile a very basic lisp and actually run the code via IEx.

I want to specifically call out some articles that really helped me get going with these tools.

Thank you to these fine people for publishing such detailed articles.

4 Likes

Doing something similar (in terms of writing a language in elixir) with my project, Amethyst. Would love to share learnings between the two of us!

Good article!

I’d like to note that core Erlang is also a tree of lists and tuples :slight_smile:
The main problem with core Erlang is that the docs are very poor I think.

Could you enlighten me on what you mean? When I see this, I don’t see lists and tuples, but I’d love to hear your perspective and learn something new.

'simplest'/0 =
    fun () ->
	'ok'

Thanks for the link. I wasn’t sure the best way to create the compiler binary so I will probably steal something from your project! :slight_smile:

Ah! That’s the textual form! There’s an Erlang term based form that is typically constructed using the cerl module (the documentation for which I had to read in the Erlang OTP source code).

1 Like

Documentation for the compiler in OTP 22 includes an “internal documentation” section that has the cerl module and some of the other modules related to core erlang - http://erlang.org/doc/apps/compiler/internal_docs.html

5 Likes

Just published part three. Moving on to translating more advanced function definitions.
https://thaterikperson.com/parsing-function-definitions

2 Likes

I realized my idea for function signatures wasn’t going to work as well as I hoped, so they’ve been rethought. https://thaterikperson.com/rethinking-signatures

1 Like

In my attempt to come up with Erie’s let binding syntax, I learned I don’t need to implement it in the compiler and will save it for macros.

https://thaterikperson.com/proper-let-syntax

1 Like

I haven’t attempted to implement macros, but I wrote a piece to help me think through how it will work.

https://thaterikperson.com/macro-plan

If anyone else has implemented macros before and knows why this is a bad approach, I’d love to hear about it and save myself from going the wrong direction.

1 Like

Well first of all, macro parsing in lisp usually happens in the parser itself, I.E. when it reaches a set of expressions it is executing as it encounters them, in a typed version I’m unsure how that will go.

  1. Find instances of defmacro .
  2. Find invocations of each of those macros.

If executed as encountered then a defmacro I’d imagine would just become like a function like normal (Elixir does defmacro as compiling to a function with a MACRO- prefix and another argument).

  1. Convert the output of the parser into an Erie abstract syntax tree.

I’m torn on this, by keeping it a typed tree as much as possible you can know more inside the macro about what is going on, but by keeping it untyped you can be much more free-flowing with the code, with potentially much worse error messages, hmm…

  1. Support “unquoting” somehow.

In Lisps’s unquot’ing is usually just the unquote call, so (quote (a b (unquote (quote c)) d) is handling by the quote call itself as just an ‘escaped’ name. Technically quote is a macro (or rather, a special form) that just takes its single argument as AST, transforms nested unquote's in it to inline sets, then just returns it. A lisp read-macro watches for prefix ’ and ` and just replace it and the following single expression with a (quote ...) and (unquote ...) wrapping respectively.

  1. Replace the macros in the AST with their results.

Yep, just calling the macro function at compile-time. Elixir did itself hard by allowing calling macro’s defined in the same module. ^.^;

And don’t forget about read-macro’s!

1 Like

Thanks for the advice!

It became apparent pretty quickly on the implementation that this would be the right move. Or at the very least, using the same code. I would like to allow macros defined anywhere to be executed anywhere, so I think I’ll need to essentially parse the code twice. First to find the macros, and second to execute them in place.

1 Like

Making some decisions about how the REPL for Erie should work. https://thaterikperson.com/repl-start

Probably about time to work on the type system now.

2 Likes

Back at it with a basic type checker. Very happy with how little code it’s taken to write this much of a type checker. Still need to support user-defined types which is going to require me to figure out how to properly implement real polymorphic types.

https://thaterikperson.com/type-checker

5 Likes

Type checker now supports algebraic data types. It lead to a lot of decisions that I’m sure I’ll reverse later, but was definitely the most challenging aspect of the compiler so far. Why didn’t anyone tell me building a compiler is so fun?

https://thaterikperson.com/algebraic-data-types

1 Like

They are always fun! Why do you think I’ve built so many! ^.^

1 Like

New post about the type expansion the compiler does when trying to confirm that the inferred type matches the type signature. Everything seems to be working so far, except for recursively-defined types.

https://thaterikperson.com/type-expansion

2 Likes