Domain Specific Language (DSL) Building in Lua

Despite using Lua for the better part of 15 years. I've never once used it as a "scripting language". In the context of writing games for LÖVE, Lua is a systems language. You implement all the systems managing your game in Lua, not the underlying C++.

I've gotten into making small games. And trying to build systems for them. Dialogue and cutscene oriented games are kinda messy. So, we've been on quest to make DSL so they feel cozy to build. This is kinda our brain dump on that.

Lua is generally considered a Scripting Language. It's meant to be added over an application as a layer of convenience. It provides little out of the box, changes pretty slowly. You could easily stick with 5.1 or 5.2 forever and not be missing out on much. It doesn't have many syntatic and conceptual features.

Tho, metatables do throw people for a loop. But outside of operator overloading, you can mostly ignore them and get pretty far anyways.

Thus, Lua is only as good as the APIs you build for it. The more time you spend refining your APIs and assembling a DSL, the better Lua becomes. I've been iterating on trying to construct DSL in Lua, but nothing really materialized. Until, some ideas recently resolved after messing with OCaml.

DSL Enabling Syntax

Lua has a few interesitng features for building DSL:

1. Functions are first-class values. They can be store, return, and passed about like numbers, strings, or objects. Function definitions are actually sugar:

   local function f()
       ...
   end
   
   -- same as:
   local f
   f = function ()
       ...
   end

2. f "hello" and f {1, 2, 3} are both function calls. Equivalent to f ("hello") and f ({1, 2, 3})
3. Tables are anonymous pieces of data you can fill with functions. And you can use ; for seperating items in a table. Thus, f {a, b, c} can be rewriten as f {a; b; c}.

First-Class Function

As mentioned, first-class functions means procedures in Lua are values. And, like with any value, your can return them as the result of a computation. Additionally, functions in Lua come with a "closure". Closures allow you to capture variables from outside the function they are created in.

In Lua, these captured values are mutable and can effect change across the function boundary. This means they can double as objects hiding state within themselves.

For example:

local counter = function (start)
    local get = function ()
        return start
    end

    local inc = function ()
        start = start + 1
    end

    local dec = function ()
        start = start - 1
    end

    return get, inc, dec
end

local get, inc, dec = counter (0)
print (get ()) -- prints 0
inc () inc ()
print (get ()) -- prints 2
dec ()
print (get ()) -- prints 1

It's the main way you can encapsulate and hide away state in Lua. It can allow for a range of techniques from private fields, to memoization and caching, to stateful iterators.

First-class functions mean you can assemble new programs at runtime. From a DSL perspective, this is a compilation process. You take a set of expressions, then compile them into a function.

A trivial example is compiling a set of expressions into a if ... then .. else .. end block:

local when = function (condition)
    return function (when_true)
        return function (when_false)
            if condition () then
                return when_true ()
            else
                return when_false ()
            end
        end
    end
end

local some_test = function () ... end
local test_past = function () ... end
local test_failed = funaction () ... end

when (some_test) (
    test_past
) (
    test_failed
)

This however is just basic functional programming. We've replaced the syntax of if ... then ... else ... end with the expression when (...) (...) (...). There is nothing interesting about these semantics. Instead, lets represent something new.

Lets make a new DSL that includes a wrap operation. wrap takes some function f and calls it before an after some function g. Thus wrap is the same as: f() g() f(). It's definition is as followed:

local wrap = function (f)
    return function (g)
        f() g() f()
    end
end

local seperator = function ()
    print "---------------"
end

local hello_world = function ()
    print "Hello, World!"
end

wrap (seperator) (hello_world)

A reason for returning chains of functions like this is to remove the need for delimiters like , from our DSL. It also means you can construct various readymade operations. For example:

local with_stars = wrap (funcion ()
    print "***********"
end

local with_hearts = wrap (function ()
    print "<3 <3 <3"
end)

with_stars (hello_world)
with_hearts (hello_world)

This technique of capturing values and partial application is called "currying" in the jargon world. Probably goes good on rice.

You can imagine this as a form of partial compilation. We generate a template, specialized on one task, the supply the rest later. It's rather neat. With property #2, you can supply strings and tables without parenthesis. Lets make a DSL that weaves a string between each value of a table.

local weave = function (item)
    return function (t)
        local new_t = {}
        for i, v = ipairs (t) do
            table.insert (new_t, v)
            if i ~= #table then
                table.insert (new_t, item)
            end
        end
    end
end

local amps = weave "&" {"a", "b", "c"}
local hearts = weave "<3" {"sheep", "raven", "lizard"}

print (table.concat (amps, " "))
print (table.concat (hearts, " "))

Now this is looking a bit further from "normal" Lua. However, it's still just plain function application. And it still feels a bit... inexpressive. Wouldn't it be nice to say weave "&" over {"a", "b", "c"}? What's DSL without keywords that express intent? Lets make some keywords.

Syntax Bending

Lua has this bit of sugar: f["x"] <=> f.x. Additionally, combined with property #2, f({})["x"] is the same as f {} .x. With this, we can start to bend syntax to our will. Lets make another DSL.

This DSL will describe joining together two string. It'll have the following syntax join ... with .... It can be described as followed:

local join = function (str_a)
    return {
        with = function (str_b)
            return str_a ... str_b
        end
    }
end

print (join "hello. " .with "world!")

Now we have a DSL with syntax. Additionally, like before, we can produce partially evaled programs that are specialized on one of our inputs.

local join = function (str_a)
    return {
        with = function (str_b)
            return str_a ... str_b
        end
    }
end

local hello = join "hello, "
local goodbye = join "goodbye, "

print (hello .with "world!")
print (goodbye .with "cruel world!")

We can even make multiple options. For example, we can describe two different ways wrap can work using keywords:

local wrap = function (f)
    return {
        with = function (g)
            g() f() g()
        end,

        around = function (g)
            f() g() f()
        end
    }
end

local hearts = function ()
    print "&3 &3 &3 &3"
end

local stars = function ()
    print "* * * * * *"
end

wrap (hearts) .with (stars)
wrap (hearts) .around (stars)

In the OOP jargon, this style of API is Fluent Interfaces. But we can go even further with this. Currently, our DSL can only handle a single expression. But, we can fix that.

Threaded-Code Compilation

Threaded-code is a style of program where procedures are composed of subroutine calls and only subroutine calls. It's an extremely simple approach to compilation. Often used in Forth.

In the context of Lua, this means a list of functions. We can achieve this by making our DSL lazier. Instead of immediately evaluting the compiled DSL, we can wrap it in a function that takes no arguments. For example, lets make a DSL that compiles a program to print a string:

local say = function (str)
    return function ()
        print (str)
    end
end

Next, we'll need an eval operation for this. eval shall take a table of threaded-code, and execute each procedure one after the other. It's implementation is rather short:

local eval = function (code)
    for _, subroutine in ipairs (code) do
        subroutine ()
    end
end

Now, we can write a program, have it be compiled to threaded-code, and then execute that code. For example, a simple hello-goodbye program:

eval {
    say "HELLO" ;
    say "WORLD" ;
    say "" ;
    say "GOODBYE" ;
    say "CRUEL WORLD"
}

With this threaded-code approach, we can enable higher-order programming for our DSLs. Operations in our DSLs can now take programs, trasnform them, and recompile them into new programs. For example, lets define a new wrap operation that takes advantage of threaded compilation:

wrap = function (block_a)
    return {
        around = function (block_b)
            return function ()
                eval (block_a)
                eval (block_b)
                eval (block_a)
            end
        end
    }
end

eval {
    wrap { say "<3 <3 <3" ; } . around {
        say "HELLO" ;
        say "WORLD" ;
    }
    say "" ;
    wrap { say ":( :( :(" } .around {
        say "GOODBYE" ;
        say "CRUEL WORLD" ;
    }
}

This approach enables you to create a new language embedded into lua that encapsulate the runtime semantics of your program. You can even extend eval and your threaded compiler to pass state between each operation. We can even make it so eval returns the result of the final expression.

Applying this, we can transform our DSL into something that can read and write variables:

local stateful_eval = function (code, env)
    local env = env or {}
    local final
    for _, instruction in ipairs (code) do
        final = instruction (env)
    end
    return final
end

local let = function (var)
    return {
        equal = function (value)
            return function (env)
                env[var] = value
            end
        end
    }
end

local get = function (var)
    return function (env)
        return env[var]
    end
end

local say = function (exp)
    return function (env)
        print (stateful_eval (exp, env))
    end
end

stateful_eval {
    let "a" .equal "Hello, World!" ;
    say {get "a"} ;
    let "a" .equal "Goodbye, Cruel World!" ;
    say {get "a"} ;
}

DSL to Your Heart's Content

scene {
    add { home_door ; bed ; computer ; player } ;

    perform { function ()
        player.at = "home"
        player.x = bed.x
        player.y = bed.y
    end } ;

    interaction .between {home_door ; player} .does {
        go_to {WeekOne.work} ;
    } ;

    interaction .between {computer ; player} .does {
        say "Wish I had time for a quick browse, but I can't afford the distraction."
    } ;

    interaction .between {player ; bed} .does {
        say "haha, I wish I could sleep in more. But need to get that money."
    } ;

    sequence .step_through {
        say "Whelp, time for another week of work." ;
        say "Work's been super busy." ;
        say "It's a tough market to be a software shop." ;
        say "Anyways, I should probably get to work." ;
    } ;
}

Once you have this structure, the sky is the limit. You can use this to free yourself from writing code against a runtime into code for a runtime. A lot of this didn't really start to click until after I toyed with OCaml. And it only truely snapped into place after remembering ; can seperate statements in a table. I just thought it'd make for a funny bit. Glad it turned out extremely useful.