Embedding a DSL in Julia

20.08.2021 — Gavin Gray

When creating a domain-specific language the natural intuition is (or should be) to reach for Racket. However, today I want to explore a lesser known functionality of Julia, macros! Julia has a lisp legacy and the longest standing evidence of this is its metaprogramming capabilities. Similar to Lisp, Julia macros work on the AST itself rather than a textual preprocessing step like that of C/C++. This aspect of Julia makes it a good choice for metaprogramming, and by embedding a domain-specific language into Julia, we can take advantage of the Julia runtime and its performance. Curly is a very simple Lisp-like language and is the DSL that we will be embedding into Julia. I was first introduced to Curly at the University of Utah à la Matthew Flatt’s Programming Language course. The name of Curly comes from its syntax, so instead of writing expressions such as (+ 1 2), as you would in Lisp, you write it with curly braces like so {+ 1 2}. In order to make this simple, we will keep Curly functionality to a minimum. The grammar for Curly is as follows:

<symbol> ::= Symbol

<expr> ::= Int64
          | <symbol>
          | { + <expr> <expr> }
          | { - <expr> <expr> }
          | { if0 <expr> <expr> <expr> }
          | { let  { <symbol> <expr> } <expr> }
          | { lambda { <symbol> } <expr> }
          | { <expr> <expr> }

With this, we have just enough to make this interesting but not so much that our implementation gets out of hand! The only operators that Curly supports are addition and subtraction but the goal for our Curly implementation is that we will eventually be able to define a recursive multiplication function like the following:

curly"""
    {let {Y {lambda {f}
              {{lambda {x}
                {x x}}
              {lambda {x}
              {f {lambda {y}
                    {{x x} y}}}}}}}
      {let {mult {Y {lambda {f}
                  {lambda {x}
                    {lambda {y}
                      {if0 y
                        0
                        {+ x {{f x } {- y 1}}}}}}}}}
        {{mult 7} 6}}}
"""

If the above code is terrifying to you, consider reading about Fixed-point Combinators. However, understanding the Y combinator is unimportant for the rest of this article, so please, read on. As demonstrated above, we want to embed our Curly code in non-standard string literals that will be parsed at compile time and evaluated at runtime. To keep this simple, parse errors will not be handled so the ominous cannot parse exception is all the feedback Curly progammers will get.

Start with a new module curly.

module curly

export @curly_str, run_tests

# TODO data representation

# TODO parser

# TODO transformer

# TODO test suite

macro curly_str(source)
    # TODO
end

function run_tests()
  # TODO write tests
end

end # end curly module

The macro curly_str is how you introduce a non-standard string literal into Julia and the argument source is the string contents that we will get to play with. I’ve also included a few TODO items above to outline what will be accomplished in the coming sections. With such a simple design, creating the necessary structures for Curly code will be very simple. Each branch of the above grammar will get its own struct and each of these structs will be a subtype of the overarching abstract Node type. Let’s start with the simplest:

abstract type Node end

struct CInt <: Node
    val
end

struct CSymb <: Node
    sym
end

The remaining structs are unsurprisingly equally as trivial. Simply put, for each non-terminal in the grammar, we add one more field.

struct Plus <: Node
    lhs
    rhs
end

struct Sub <: Node
    lhs
    rhs
end

struct IfZero <: Node
    cnd
    true_e
    false_e
end

struct Let <: Node
    arg
    val
    bdy
end

struct Lambda <: Node
    param
    bdy
end

struct App <: Node
    f
    arg
end

The syntax for Curly is, unfortunately, not Julia syntax. Therefore, we will need to write our own parser. For a more intensive project, like a compiler, it would be best to use an external parser generator like ANTLR. For the purposes of Curly, it’s best to write a quick and dirty parser using the ParserCombinator package. This package is similar to Haskell’s Parsec library and will allow us to get a parser up and running in no time.

First, users should be allowed to include whitespace as they wish. I.e. { + 1 2 } should parse the same as {+ 1 2}. The parser should also ignore newline characters. Parser combinators work by creating a series of “matchers” then combining them together to build parsers for more complex forms. To remove whitespace, we start by consuming the leading whitespace for each matcher. (Note, we still have to explicitely consume trailing whitespace).

using ParserCombinator

ws = Drop(Star(Space()))

@with_pre ws begin
    # ... TODO, matchers ...
end

This code simply drops prepended whitespace before each matcher.

To create our Curly AST from the parser combinator matchers, we will first match the pattern and then use the > syntactic sugar to pass the matched values to an anonymous function which will construct the AST node. Again starting with integers and symbols, we will restrict integers to be just positive, i.e. a simple non-empty string of digits.

curly_int = p"\d+" > (x -> CInt(parse(Int64, x)))

To elaborate a little more on matchers with the above as an example: the p" ... " syntax forms a matcher out of a regular expression and passes the matched string to the lambda, which, in this case, parses the integer and then calls the CInt constructor. While in traditional Lisp you can use some non-traditional characters within a symbol, in Curly we will restrict symbols to begin with an alphabetical character, followed by any number of characters or underscores.

sym = p"[a-zA-Z]+[a-zA-Z_]*" > CSymb

That was integers and symbols. Easy. Now let’s move on to expressions.

To avoid a little bit of verbosity (emphasis on the little), we’ll create two types of matchers, a cexpr and an expr. A cexpr will be the outer expression that is of the form { ... } | <int> | <sym>, and the expr is something that is inside of curly braces (e.g. if0, let, lambda, and the default case if function application).

expr = Delayed()

cexpr = Delayed()

group = E"{" + expr + ws + E"}"

plus = E"+" + cexpr + cexpr > Plus

sub = E"-" +  cexpr + cexpr > Sub

ifzero = E"if0" + cexpr + cexpr +  cexpr > IfZero

lete = E"let" + ws + E"{" + sym + cexpr + ws + E"}" + cexpr > Let

lambda = E"lambda" + ws + E"{" + sym + ws + E"}" + cexpr > Lambda

app = cexpr + cexpr > App

expr.matcher = plus | sub | ifzero | lete | lambda | app

cexpr.matcher = (group | curly_int | sym) + ws

prog = cexpr + ws + Eos()

A few things to note from above.

The strings E" ... " match whatever is within quotes literally and then throws the match away. These strings are syntax that we need for parsing, similar to keywords like for and while in C, but we don’t need them to construct our AST.
The Delayed form is used to create recursive matchers for both expression forms.
We still have to consume whitespace explicitely in a few places, for example in the group, lete, and lambda matchers. We also consume whitespace at the end of the outermost Curly program expression until the end of the source string.

Other than a few peculiarities of the Parser Combinator package, parsing a Curly program should be straightforward. Testing that a Curly program parses to the right AST isn’t so easily done with tests and we will reserve the testing suite for full Curly program tests. In the meantime, we can dump the Curly AST in the Julia REPL and inspect a few examples by hand. We need to add the parsing logic into the curly_str macro and then we will use the show macro to view the parsed AST.

macro curly_str(source)
    # Parse the source as one Curly program
    curly_expr = parse_one(source, prog)[1]
    # view the Curly AST
    @show curly_expr
end

Now, load the curly module into the REPL:

(@v1.6) pkg> dev curly
[ Info: Resolving package identifier `curly` as a directory at `~/codefiles/projects/curly/julia/curly`.
  Resolving package versions...
  No Changes to `~/.julia/environments/v1.6/Project.toml`
  No Changes to `~/.julia/environments/v1.6/Manifest.toml`

julia> import curly
[ Info: Precompiling curly [7486cc49-d4d6-458f-8e1b-b99820654d8b]

julia> using curly

Let’s start with some simple examples:

julia> curly"6"
curly_expr = curly.CInt(6)

julia> curly"{+ 1 {- 0 1}}"
curly_expr = curly.Plus(curly.CInt(1), curly.Sub(curly.CInt(0), curly.CInt(1)))

julia> curly"""
      {let {f {lambda {x} {+ 1 x}}}
          {- {f 6} 1}}
      """
curly_expr = curly.Let(curly.CSymb("f"), curly.Lambda(curly.CSymb("x"), curly.Plus(curly.CInt(1), curly.CSymb("x"))), curly.Sub(curly.App(curly.CSymb("f"), curly.CInt(6)), curly.CInt(1)))

julia> curly"""
          {
          let
          {
          x
          1
          }
          {
          let
          {
          f
          {
          lambda
          {
          x
          }
          {
          -
          x
          1
          }
          }
          }
          {
          +
          x
          {
          f
          x
          }
          }
          }
          }
          """
curly_expr = curly.Let(curly.CSymb("x"), curly.CInt(1), curly.Let(curly.CSymb("f"), curly.Lambda(curly.CSymb("x"), curly.Sub(curly.CSymb("x"), curly.CInt(1))), curly.Plus(curly.CSymb("x"), curly.App(curly.CSymb("f"), curly.CSymb("x")))))

The last test was a fun way to test arbitrary whitespace; we will also add more tests later. Let’s move on so we can eventually build the whole testing suite.

Now we have a Curly AST to play with. There are two directions one could take the implementation:

evaluate the AST to a value.
transform the AST to a Julia expression.

As indicated by the section header, we are going to transform the Curly AST into a Julia expression. If instead we evaluated the Curly AST, our Curly programs would evaluate at compile time, which as was stated earlier, we don’t want. So how will this work? Each transform function will need to return an expression rather than a value. We can then piece these expressions together to form a full Julia expression that will have the same semantics as the Curly source. For the transformation, we are going to assume that the program is type safe, and in the case it isn’t, we will rely on the Julia compiler to raise the exception. Starting with the easy cases: when we call transform on a CInt we want to return the integer expression. Lucky for us, the integer value is the integer expression. If you’re unsure about this, we can do a simple test in the Julia REPL: Meta.parse("3") == Int(3) which yields true.

transform(n::CInt) = n.val

Now for symbols. We want to return a Julia Symbol created from the value that the CSymb.sym holds, that is, from a string. This is easily done by passing the string to the symbol constructor.

transform(s::CSymb) = Symbol(s.sym)

The addition and subtraction AST nodes will show us how to transform the remaining nodes. For example, the Plus node has two fields, lhs and rhs, which are currently Curly AST nodes. We first need to transform the fields into Julia expressions by calling the transform function on the lhs and rhs and then inserting them into an addition expression of the form :( ... + ...). This may look a little funky at first; the :( ... ) syntax is shorthand for creating an expression in Julia. This is similar to quasi-quoting in Lisp and we can use the $ symbol to unquote (or interpolate as it’s called in Julia) expressions that we’ve evaluated. You see this working below.

function transform(p::Plus)
    l = transform(p.lhs)
    r = transform(p.rhs)
    return :($l + $r)
end

function transform(s::Sub)
    l = transform(s.lhs)
    r = transform(s.rhs)
    return :($l - $r)
end

To reiterate, the dollar sign is interpolating the transformed left and right hand expressions into the new addition (or subtraction) expression. With this template, the IfZero node is also straightforward because we are simply interpolating three expressions into a Julia ternary expression.

function transform(iz::IfZero)
    cnd = transform(iz.cnd)
    te = transform(iz.true_e)
    fe = transform(iz.false_e)
    return :(($cnd == 0) ? $te : $fe)
end

For now, let’s skip the Let node and move on to the Lambda and App cases which shouldn’t cause any trouble. For the Lambda case, we have two fields: the parameter and the body. The parameter was restricted by the parser to be a symbol and all we want to do is make sure that this symbol is bound in the lambda body expression. That is, the context that the lambda body uses has access to this bound symbol. To do this, we can use Julia’s syntax for anonymous functions to give us this desired functionality.

function transform(lam::Lambda)
    sy = transform(lam.param)
    bdy_ex = transform(lam.bdy)
    return :(($sy -> $bdy_ex))
end

In the App case, we first transform the function f and then apply this to the transformed argument expression.

function transform(a::App)
    g = transform(a.f)
    p = transform(a.arg)
    return :($g($p))
end

Almost there! Onward to the Let case which we skipped earlier. At its core, a let expression is binding an expression to a symbol and then evaluating a body expression that can use that symbol. This is very similar to the lambda and application rules that we discussed above. Turns out, the let form is simply syntactic sugar for applying a function to an argument. This syntax rewrite looks like this:

$(let sym = arg in bdy) ⟺ (λ s y m . b d y) (a r g)$

With this knowledge, we can now finish the Let transform function.

function transform(l::Let)
    sym = transform(l.arg)
    arg = transform(l.val)
    bdy = transform(l.bdy)
    return :(($sym -> $bdy)($arg))
end

Simple! Now each of the Curly AST nodes have been mapped to a Julia expression. Before we jump to testing, we need to update the curly_str macro to return the transformed Julia expression rather than show the Curly AST.

"Curly program string"
macro curly_str(source)
    # parse one program (i.e. cexpr)
    # and then take the first result
    # as there should only be one :)
    curly_expr = parse_one(source, prog)[1]
    return transform(curly_expr)
end

Reloading the module in your REPL and running a small example should now work!

julia> curly"{let {f {lambda {x} x}} {+ 1 {f 2}}}"
3

To make writing tests simple, it’s best to write a little macro which will evaluate the Curly program and compare it to some expected output. To make developers’ lives easier in the case of a failed test, let’s display the Curly program, expected output, and actual output.

"Macro for pretty-printing test results"
macro test(prog, expected)
    quote
        if $prog == $expected
            # display green checkmark indicating a test pass
            printstyled("[Pass] \U2713 \n", color=:green)
        else
            printstyled("[Fail] \U0021 \n\t"
                        , $(Meta.quot(prog))
                        , "\n\tExpected value : "
                        , $(Meta.quot(expected)), "\n"
                        , "\tActual value : ", $prog
                        , color=:red)
        end
    end
end

With a quick example we can see how this pretty-printed output will look.

julia> @test curly"{+ 1 2}" 3
[Pass] ✓

julia> @test curly"{+ 1 2}" 4
[Fail] !
        curly"{+ 1 2}"
        Expected value : 4
        Actual : 3

Time to write some real tests! We will insert out new tests into the empty run_tests function so we can run the whole suite at once.

Curly only natively offers addition and subtraction operators, therefore testing is easy! With addition, we can test the commutative, associative, and identity laws and call it good.

# inserted into the `run_tests` function

# commutative
@test curly"{+ 1 2}" 3
@test curly"{+ 2 1}" 3

# associative
@test curly"{+ 1 {+ 2 3}}" 6
@test curly"{+ {+ 1 2} 3}" 6

# identity
@test curly"{+ 1 0}" 1
@test curly"{+ 0 1}" 1

The commutative and associative properties do not hold for subtraction, but we can test with the subtractive property. This states that if we subtract zero from any number $x$ the number remains unchanged, and if we subtract $x$ from $0$ , then we receive $- x$ .

# subtractive properties
@test curly"{- 42 0}" 42
@test curly"{- 0 42}" -42

Moving forward to more complex forms, we can test lambdas and application and then eventually, lets.

# simple lambdas and application
@test curly"{{lambda {x} x} 6}" 6
@test curly"{{lambda {x} {+ x 1}} 6}" 7
@test curly"""
        {{{lambda {x}
        {lambda {y}
            {+ x y}}}
            7} 4}
        """ 11
@test curly"""
        {let {f {lambda {y}
                    {lambda {x}
                    {+ x y}}}}
            {- {{f 10} 20} {{f 30} 40}}}
        """ -40

Now let’s use the goal program from the very beginning: the recursive multiplication function.

@test curly"""
        {let {Y {lambda {f}
                {{lambda {x}
                    {x x}}
                    {lambda {x}
                    {f {lambda {y}
                        {{x x} y}}}}}}}
        {let {mult {Y {lambda {f}
                    {lambda {x}
                        {lambda {y}
                        {if0 y
                            0
                            {+ x {{f x } {- y 1}}}}}}}}}
            {{mult 7} 6}}}
        """ 42

Using our shiny new implementation of multiplication we can even test distributive properties of multiplication over addition!

@test curly"""
        {let {Y {lambda {f}
                {{lambda {x}
                    {x x}}
                    {lambda {x}
                    {f {lambda {y}
                        {{x x} y}}}}}}}
        {let {mult {Y {lambda {f}
                    {lambda {x}
                        {lambda {y}
                        {if0 y
                            0
                            {+ x {{f x } {- y 1}}}}}}}}}
            {-
              {{mult 7} {+ 4 3}}
              {+ {{mult 7} 4} {{mult 3} 7}}}}}
        """ 0

I’ll throw these next tests in for fun. They are the recursive factorial and fibonnacci functions.

@test curly"""
        {let {Y {lambda {f}
                {{lambda {x}
                    {x x}}
                    {lambda {x}
                    {f {lambda {y}
                        {{x x} y}}}}}}}
        {let {mult {Y {lambda {f}
                    {lambda {x}
                        {lambda {y}
                        {if0 y
                            0
                            {+ x {{f x } {- y 1}}}}}}}}}
            {let {fac {Y {lambda {f}
                        {lambda {x}
                            {if0 x
                            1
                            {{mult x} {f {- x 1}}}}}}}}
            {fac 5}}}}
        """ 120

@test curly"""
        {let {Y {lambda {f}
                {{lambda {x}
                    {x x}}
                    {lambda {x}
                    {f {lambda {y}
                        {{x x} y}}}}}}}
        {let {fib {Y {lambda {f}
                        {lambda {x}
                        {if0 {- x 1}
                            1
                            {if0 x
                            1
                            {+ {f {- x 1}} {f {- x 2}}}}}}}}}
            {fib 42}}}
        """ 433494437

Now we can run our testing function to make sure it works.

julia> @time run_tests()
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
[Pass] ✓
2.905905 seconds (589 allocations: 23.625 KiB)

All tests pass! Looks like our implementation of Curly is working out great and can now be used in our Julia programs.

Julia, while typically thought of as only used for scientific computing (at least in some social circles), also makes a good option for creating embedded domain-specific languages, and you can rely on the Julia runtime which is very performant. There are already many packages which leverage this metaprogramming power to make some scientific problems easier. These are definitely worth taking a look at if you haven’t already (e.g. JuMP, Octo, and LispSyntax). While Curly was a trivial example, it hopefully can spark ideas of how to expand Julia syntax to make domain-specific problems easier solved! The full source code can be found on GitHub.