💾 Archived View for gemini.ctrl-c.club › ~nttp › writing › tiny-scripting-engines.md captured on 2020-09-24 at 00:42:29.
-=-=-=-=-=-=-
Tiny scripting engines for everyone
===================================
29 January 2019
How many lines of code do you need to implement a minimal scripting engine? And I mean for a semi-usable language that mere mortals can actually read, not one of those whose names tend to be written with an asterisk.
So, how many? 800 lines? 500? 300? The question isn't just something for nerds to have fun with. Software packaging and distribution is trickier than most people realize. Often, the best way to ship a library or application is as a single file written in a language like Python. And many of them, like their bigger brethren, could benefit from scripting support. But when your whole game or utility is 1000-2000 lines long, increasing its size by 50-100% just for that isn't practical.
Wait, isn't Python itself a scripting language? Arguably, yes, and you *can* simply use `eval` in a pinch. That however has a couple of problems. One, it ties your scripts to the host language forever, even if you later want to switch. Two, it's hard if not impossible to sandbox Python code. People must be able to trust 3rd-party scripts even without the skills or inclination to audit them!
After trying and failing a few times (the figures above aren't arbitrary), I turned to an older example for inspiration. Namely, Peter Norvig's [Lisp in 90 lines of Python](http://norvig.com/lispy.html), that was already well-known ten years ago when I was writing [my first tutorial](https://felix.plesoianu.ro/languages/scratch-lang/) on the topic. (It's grown a bit in the mean time.)
It worked amazingly well.
Oh no, you're going to say. Isn't Lisp that super-advanced language with all the parentheses? Don't panic! Its reputation is somewhat exaggerated, and we'll be making a much simpler thing anyway. Mainly, there's one aspect of Lisp to be lifted wholesale: s-expressions.
You see, my goal here is to make a *tiny* interpreter. And a big part of the problem is parsing syntax like `if (1 < 2) return "is too"; else return "is not";` into a data structure the computer can navigate. Which is easy enough, but very very laborious. S-expressions, short for symbolic expressions, make it a lot simpler, because they look like this instead:
(if (< 1 2) 'is-too 'is-not)
See how structure becomes explicit? We simply have a list (in parentheses) that contains another list; everything else is space-separated. So to pick it apart, all we have to do is drive a wedge between delimiting characters:
def tokenize(text):
text = text.replace("(", " ( ").replace(")", " ) ").replace("'", " ' ")
return [int(i) if i.isdigit() else i for i in text.split()]
We also convert the integers along the way, because Python makes it trivial. Mostly, however, we'll just be working with strings. The apostrophe means "take what follows as-is, don't try to interpret it". More about that below.
For now however all we have is a flat list of tokens. We need to recreate the structure that's so obvious to the human eye, but not so much to a computer. I tied myself into a knot trying to do it all at once, until peeking at Mr. Norvig's code reminded me how the trick was to only read one part at a time:
def next_form(tokens, cursor = 0):
if cursor >= len(tokens):
raise SyntaxError("reading past the end of input")
elif tokens[cursor] == "'":
form, cursor = next_form(tokens, cursor + 1)
return ["quote", form], cursor
elif tokens[cursor] == "(":
form, cursor = [], cursor + 1
while cursor < len(tokens) and tokens[cursor] != ")":
tmp, cursor = next_form(tokens, cursor)
form.append(tmp)
if cursor < len(tokens) and tokens[cursor] == ")":
return form, cursor + 1
else:
raise SyntaxError("unexpected end of input")
elif tokens[cursor] == ")":
raise SyntaxError("unexpected closing brace")
else:
return tokens[cursor], cursor + 1
A "form" in Lisp parlance is either a list (maybe with other lists inside), or else one "atom", which is anything like a number or identifier, that can't be broken apart any further. Either can be prefixed by an apostrophe; "'X" becomes "(quote X)". Otherwise, if we detect the start of a list we also have to collect its contents. Which can be more lists, hence the recursive call to `next_form`. Anything else is returned as-is, along with the current position, so we know where to resume reading tokens from. We could also just pop tokens off the start as we use them up, but that's iffy: we don't know where the data is coming from and what part of the code might need it again later.
Anyway, if you now call `tokenize` on the earlier example, you should get this:
['(', 'if', '(', '<', 1, 2, ')', "'", 'is-too', "'", 'is-not', ')']
Which, if handed in turn to `next_form`, yields the following:
(['if', ['<', 1, 2], ['quote', 'is-too'], ['quote', 'is-not']], 12)
Note the number that says how many tokens have been read. We need it, because the original tokens could have more forms. So let's collect as many as we can:
def read(tokens):
forms, cursor = [], 0
while cursor < len(tokens):
form, cursor = next_form(tokens, cursor)
forms.append(form)
return forms
There! With just a few more lines of code, we can now slurp in a whole text file and spit out a bunch of forms, ready to be interpreted. Half the problem is already solved, and it only took a screenful of code so far.
Now that we have our data structure (called an [abstract syntax tree](https://en.wikipedia.org/wiki/Abstract_syntax_tree)), we need a way to interpret it as code. That's called [evaluation](https://en.wikipedia.org/wiki/Eval) in computer science, hence why there is an `eval` function in Python. And the way to do it is, just like with reading, to take all those forms one by one, based on what they are:
- if it's a string, assume it's a variable name and look it up in a dictionary;
- if it's a number or some such, return it as-is;
- if it's a list, now that's where things become interesting. See below.
You see, most programming languages have all kinds of different constructs: blocks, statements, expressions, operators... Lisp however only has one: function calls. And those are represented as lists, with the function name as the first element, while any others are considered arguments. To evaluate, say, `(< 1 2)`, first you look up `<`, which presumably points at some sort of "less than" function (stored in a dictionary just like variables). Then you evaluate `1` and `2` in turn, and at last you call the function already found with their values as arguments.
There's just one snag: that rule breaks down with a construct like `if`, which has to evaluate either the "then" part or the "else" part, but never both at once! So it has to be handled specially. Likewise for `quote`, that we met before: the whole point is that it *doesn't* evaluate its argument. Absent double-quoted strings, we need some way to type in text when needed.
def evals(form, scope):
if type(form) == str:
return scope.get(form)
elif type(form) != list or len(form) == 0:
return form
elif form[0] == "quote":
return form[1] if len(form) > 1 else None
elif form[0] == "when":
return evals(form[2], scope) if evals(form[1], scope) else None
elif form[0] == "if":
return (evals(form[2], scope)
if evals(form[1], scope) else evals(form[3], scope))
elif form[0] == "while":
while evals(form[1], scope): evals(form[2], scope)
elif form[0] in scope:
args = [evals(i, scope) for i in form[1:]]
return scope[form[0]](scope, args)
else:
raise KeyError("Function not found: " + form[0])
Note how we take various shortcuts to keep the code minimal:
- unassigned variables default to `None` instead of raising an error (in my defense, Lua works the same way);
- an `if` without an `else` uses a different keyword, so we don't have to count arguments;
- generally, if a list has the wrong number of elements, we just let Python raise an IndexError instead of something more descriptive.
Last but not least, we also add a `while` construct (a special form, as they are called), because what's a programming language that can't loop?
Believe it or not, with `evals` we have a complete interpreter, and it took exactly 50 lines of code! But for now it can only deal with boring scripts:
code = read(tokenize("(if 1 'one 'two)"))
print(evals(code[0], {}))
In order to do anything useful, the interpreter has to be made aware of a few functions. Here's how:
builtins = {
"<": lambda scope, args: args[0] < args[1],
}
code = read(tokenize("(if (< 1 2) 'is-too 'is-not)"))
print(evals(code[0], builtins))
Yep... the scope really is just a dictionary. That's all we need, because our language isn't going to let scripts define their own functions. But we can add any amount of builtins, depending on what we expect to need.
Try it yourself! Start with the other comparison operators. Add basic arithmetic too while you're at it. Done? Now let's look at something less obvious, such as logic operations:
builtins = {
...
"and": lambda scope, args: all(args),
"or": lambda scope, args: any(args),
"not": lambda scope, args: not args[0],
}
While `not` is straightforward, for `and`/`or` we use a couple of Python builtins that let each function take any number of arguments. Useful, huh?
Now that we can make calculations, a way to assign variables would come in handy. And that's the reason why all our builtins get pointed at the scope:
"set": lambda scope, args: scope.__setitem__(args[0], args[1]),
Doing it with `__setitem__` allows it to be a one-liner; with `def`, it could also return the newly assigned value, like in other languages. Either way, we finally have all the pieces needed to run a real and useful, if small, program:
(set 'a 360)
(set 'b 270)
(while (!= a b)
(if (< a b)
(set 'b (- b a))
(set 'a (- a b))))
a
Yep... that's a greatest common divisor algorithm. How to get so much code into the interpreter is left as an exercise to the reader. Oh, by the way: note the quoted variable name; that's because `set` is a function, and gets its arguments already evaluated. On the plus side, that allows for indirection!
There are many other things we can add. Such as a way to work with lists, since they are so important to the language:
"list": lambda scope, args: list(args),
"length": lambda scope, args: len(args[0]),
"getitem": lambda scope, args: args[0].__getitem__(args[1]),
"setitem": lambda scope, args: args[0].__setitem__(args[1], args[2]),
"append": lambda scope, args: list(args[0]) + list(args[1]),
Also a way to tell apart data types, since even this simple language can handle a bunch of them. Most should be obvious, like `null?`, `list?` or `string?`, but pay attention to this one:
"number?": lambda scope, args: (
type(args[0]) == int or type(args[0]) == float),
That's needed because Python has two numeric types. No forgetting such details!
Is there any more to it? Why, yes! Simple stuff is simple; how about some advanced tricks to spice things up? No worries, we'll stick to one-liners. For instance: our special forms can only take one function call at a time, but for any serious work we need blocks. And those come essentially free:
"begin": lambda scope, args: args[-1] if len(args) > 0 else None,
We take advantage of the fact that all arguments to a function are evaluated in order, and simply return the last value. Yet it's surprisingly useful. And we can do even more cool stuff:
"eval": lambda scope, args: evals(args[0], scope),
"apply": lambda scope, args: args[0](scope, args[1:]),
Yep... `eval` gives scripts access to our evaluator function, allowing for instance to generate code on the fly and run it. More modestly, `apply` calls the given function with its remaining arguments. Which works because function names are variables like any others:
(set 'a 1)
(eval (list '+ a '2))
(apply + 1 2 3)
How cool is that. We're still under 90 lines of code, yet our little language looks real enough, and useful enough. All it lacks is a good name; I'm thinking "Babble" for now. But feel free to make it your own, because that's why it's all so simple in the first place. Happy scripting!