haku - writing a little programming language for fun

we will start by writing the lexical analysis part of our parser, to join single characters up to slightly more managable pieces.

to lex the input into tokens, we’ll need to know the input string (of course), and where we currently are in the string.

we’ll also define a few helper functions to make reading text a little easier, without having to perform any bounds checks whenever we read tokens.

now for the most important part - that lexer.nextToken we used will be responsible for reading back a token from the input, and returning what kind of token it has read.

for now, let’s make it detect parentheses. we of course also need to handle end of input - whenever our lexer runs out of characters to consume, as well as when it encounters any characters we don’t expect.

with all that frameworking in place, let’s test if our lexer works!

( @ 0..1
) @ 1..2
( @ 2..3
( @ 3..4
( @ 4..5
) @ 5..6
) @ 6..7
) @ 7..8
end of file @ 8..8

…seems pretty perfect!

except, of course, we’re not handling whitespace or comments.

( @ 0..1
unexpected characters at 1..2: ' '

so let’s write another function that will lex those.

except instead of looking at whitespace and comments in the main token reading function, we’ll do that outside of it, to avoid getting whitespace caught up in the actual tokens’ start..end spans.

it’d be really nice if we could use identifiers though…

( @ 0..1
unexpected characters at 1..2: 'h'

so I guess that’s the next thing on our TODO list!

with a character set established, we can now stuff identifiers into our lexer. I’ll start by introducing a function that’ll chew as many characters that meet a given condition as it can:

now we can add identifiers to nextToken:

let’s try lexing that (hello world) string now.

( @ 0..1
identifier @ 1..6
identifier @ 7..12
) @ 12..13
end of file @ 13..13

nice!

in the original example, there were also a couple of numbers:

(+ (fib (- n 1)) (fib (- n 2)))

so let’s also add support for some basic integers; we’ll add decimals later if we ever need them.

now let’s see the results of all that hard work.

( @ 0..1
identifier @ 1..4
( @ 5..6
identifier @ 6..7
identifier @ 8..9
integer @ 10..11
) @ 11..12
) @ 12..13
end of file @ 13..13

looks good!

it’s time for us to implement a parser for our S-expressions.

the goal is to go from this flat list of tokens:

to a nice recursive tree that represents our S-expressions:

list
    identifier example
    identifier s-expression

knowing that similarity, we’ll start off with a similar set of helper functions to our lexer.

note however that instead of letting current read out of bounds, we instead clamp advance to the very last token - which is guaranteed to be end of file.

this yields the following EBNF grammar:

Expr = "integer" | "identifier" | List;
List = "(" , { Expr } , ")";

now we can try to parse a tree out of a little expression…

…and print it into the console:

{
    "kind": "identifier",
    "start": 0,
    "end": 3
}

nice!

now it’s time to parse some lists. for that, we’ll introduce another function, which will be called by parseExpr with an existing ( token.

its task will be to read as many expressions as it can, until it hits a closing parenthesis ), and then construct a node out of that.

and the last thing left to do is to hook it up to our parseExpr, in response to a ( token:

now let’s try parsing an S-expression!

{
    "kind": "list",
    "children": [
        {
            "kind": "identifier",
            "start": 1,
            "end": 7
        },
        {
            "kind": "identifier",
            "start": 8,
            "end": 10
        },
        {
            "kind": "list",
            "children": [
                {
                    "kind": "identifier",
                    "start": 12,
                    "end": 18
                },
                {
                    "kind": "identifier",
                    "start": 19,
                    "end": 23
                }
            ],
            "start": 11,
            "end": 24
        }
    ],
    "start": 0,
    "end": 25
}

let’s see if our pretty printer works!

(hello! -w- (nestedy nest))

that’s… the same string.

with a parser now ready, it would be nice if we could execute some actual code!

we’ll again start off by setting a goal. I want to be able to evaluate arbitrary arithmetic expressions, like this one:

(+ (* 2 1) 1 (/ 6 2) (- 10 3))

the simplest way to get some code up and running would be to write a tree-walk interpreter.

this kind of interpreter is actually really simple! it just involves walking through your syntax tree, executing each node one by one.

we’ll again start off by defining a function that initializes our interpreter’s state.

right now there isn’t really anything to initialize, but recall that we don’t have our tokens parsed into any meaningful data yet, so we’ll have to have access the source string to do that.

the core of our interpretation will be a function that descends down the node tree and evaluates each node, giving us a result.

for now we’ll leave it empty.

in the meantime, let’s prepare a couple convenient little wrappers to run our code:

now we can try running some code! let’s see what happens.

Error: unhandled node kind: integer

…of course.

so let’s patch those integers in!

this is where we’ll need that source string of ours - we don’t actually have a JavaScript number representation of the integers, so we’ll need to parse them into place.

now when we run the program above…

65

we get sixty five!

but that’s of course a bit boring - it would be nice if we could like, y’know, perform some arithmetic.

now let’s try running our full arithmetic expression! drum roll please…

13

we’ll start out with a way to define variables. variables generally have scope - look at the following JavaScript, for example:

0
1
0

the same thing happens in haku (though we don’t have a runtime for this yet, so you’ll have to take my word for it.)

((fn (x)
    ((fn (x)
        x)
     2))
 1)

this is perfectly fine, and the result should be 2 - not 1!

try evaluating this in your head, and you’ll see what I mean. it’s better than me telling you all about it.

so to represent scope, we’ll introduce a new variable to our interpreter’s state.

scopes will be a stack of Maps, each representing a single scope.

our builtins will now live at the bottom of all scopes, as an ever-present scope living in the background.

variable lookup will be performed by walking the scope stack from top to bottom, until we find a variable that matches.

we’re stricter than JavaScript here and will error out on any variables that are not defined.

now we can go ahead and add variable lookups to our eval function! we’ll also go ahead and replace our bodged-in builtin support with proper evaluation of the first list element.

in most cases, such as (+ 1 2), this will result in a variable lookup.

if we didn’t screw anything up, we should still be getting 13 here:

13

looks like all’s working correctly!

time to build our fn builtin.

we’ll split the work into two functions: the actual builtin, which will parse the node’s structure into some useful variables…

and makeFunction, which will take that data, and assemble it into a function that follows our (state, node) => result calling convention.

now let’s try using that new fn builtin!

3

nice!

but, remember that lambdas are supposed to capture their outer variables! I wonder if that works.

Error: variable x is undefined

…I was being sarcastic here of course, of course it doesn’t work.

so to add support for that, we’ll clone the entire scope stack into the closure, and then restore it when necessary.

with that, our program now works correctly:

3

of course, we’ll also need an if to be able to branch on the result of our comparison operators.

now we can write ourselves a recursive Fibonacci!

note that in order to achieve recursion, we need to pass fib into itself - this is because the fib variable we’re binding into the first function is not visible in the second function.

but if we run it now:

55

we can see it works just as fine as the JavaScript version!

therefore, it’s time for… a persistent environment!

once again, let me sketch out what I’d like it to look like. to declare a persistent value, you use def:

(def fib
    (fn (n)
        (if (< n 2)
            n
            (+ (fib (- n 1)) (fib (- n 2))))))

if this looks familar, that’s because it probably is - I used the exact same example at the start of the post!

once you define a persistent value, you can refer to it as usual. persistent values will sit in a scope above builtins, so you will be able to shadow those if you want to (but please don’t.)

(def fn if) ; Whoops! Guess your soul belongs to me now

of course, values will persist across code blocks, so I’d be able to refer to fib here as well:

(fib 12)

and lastly, it’ll be possible to put multiple expressions in a code block. we’ll only treat the last one as the result.

(def x 1)
(def y 2)
(def z (+ x y))

so let’s start by implementing the easiest part - the def builtin. we’ll need to augment our interpreter state once again, this time with the persistent environment:

of course now we will also need to teach our whole runtime about the environment, right down to the kernel…

now for def - it’ll take the value on the right and insert it into env, so that it can be seen in the future.

now let’s test it out!

2

seems to be working!

now for the second part: we still want to permit multiple declarations per block of code, but currently our syntax doesn’t handle that:

Error: unhandled node kind: error

_{and by the way, I know this is a terrible error message. we’ll return to that later.}

and with that…

3

we can now declare multiple, persistent values per code block!

so let’s declare a little function to add some numbers together…

Error: variable  is undefined

’scuse me??

now we can patch the relevant parts of the interpreter to read from the node.source field, instead of substringing the source string passed to the interpreter. this is pretty mechanical so I’ll just dump all the relevant code here: