A Lisp in less than 2K of Dart Code
(Actually, less than 1K)
For the 5K Flutter challenge, I tried to come up with a tiny scripting language implementation that fits in less than 2K. According to Greenspun’s 10th Rule, this had to be a minimal Lisp (or Scheme) interpreter. And according to McCarthy’s famous paper, implementing nine forms (atom, car, cdr, cond, cons, eq, label, lambda, and quote) should do the trick.
How hard can it be?
Some Principles
Lisp S-expressions consist of atoms and lists of more S-expressions. Atoms are mostly symbols but the empty list (a.k.a. nil) is also considered to be an atom. To represents symbols, I use Dart Strings, doubles, or bools. Dart’s List type shall represent lists. I don’t use a chain of cons cells. Unfortunately, I have to special case the empty list, for which otherwise the null value would have been the perfect fit.
The classic factorial implementation looks like this:
['df', 'fac', ['fn', ['n'],
['?',
[['=', 'n', 0], 1],
[true, ['*', 'n', ['fac', ['-', 'n', 1]]]]]]]To save precious characters in my interpreter, I use fn instead of lambda and df instead of define (or label as McCarthy called it). df will only support defining global variables and not functions (['df', ['fac', 'n'], ...]). Furthermore, I use = instead of eq and ? instead of cond. As an addition to McCarthy’s implementation, I have numbers and I intend to support * and - (and other arithmetic and comparison operations).
The eval function evaluates S-expressions (called e), using an environment, often called rho (so I will use r), for which the classic implementation is an association list of cons cells. I will use a Dart Map though, because nothing beats a datatype with a three-letter name.
Lists are either special forms and evaluated according to special rules described below or regular forms of which the first element is evaluated down to Dart a function which is then called with all other elements evaluated as S-expressions from left to right, forming a new list of argument values.
This means, internally, in addition to String, double, bool and List, there will also be Map and Function instances used in my interpreter.
But let’s start simple.
Evaluating Values
Atoms
By default, any value is evaluated to itself:
eval(e, Map r) {
return e;
}It’s good style to always write tests, so here are some trivial tests for my trivial implementation (let’s call this reverse test driven development):
test('atoms', () {
var r = {};
expect(eval(1, r), equals(1));
expect(eval(false, r), equals(false));
expect(eval([], r), equals([]));
});Symbols
Dart strings, which represent symbols, are evaluated to their bound value in the provided environment, which, as mentioned above, is a Map from strings to any of the supported data types described above.
eval(e, Map r) {
if (e is String) return lookup(e, r);
return e;
}lookup(String s, Map r) {
return r[s] ?? lookup(s, r['']);
}
In lookup, we see a neat trick to chain environments as required by the semantics of Scheme. If the current environment doesn’t contain a value, lookup continues the lookup in the parent environment which is stored under the otherwise illegal symbol name ''. If no value is bound, this will result in some ugly runtime error (null does not have a [] method) but that’s the price for a minimal interpreter.
Here are more unit tests to keep us honest:
group('symbols', () {
var r = {'a': 2};
test('bound', () {
expect(eval('a', r), equals(2));
expect(eval('a', {'': r}), equals(2));
expect(eval('a', {'': r, 'a': 4}), equals(4));
});
test('unbound', () {
expect(() => eval('b', r), throwsError);
});
});Note, my implementation makes null an invalid value which is the reason why I use [] as nil value and not null. Because two non-identical empty List instances aren’t equal in Dart, I have to special case empty lists once I will implement the = function. Here is the code to use:
bool isNil(Object e) {
return e is List && e.isEmpty;
}bool isEqual(Object e1, Object e2) {
return e1 == e2 || isNil(e1) && isNil(e2);
}
Evaluating Lists
Non-empty lists are evaluated as follows: If the first element is a symbol denoting one of the four special forms df, fn, ?, or ! (short for quote), we process the special form accordingly. Otherwise, all list elements are evaluated and we expect that the first element evaluates to a Dart function which is then called with the remaining elements evaluated as a new list.
eval(e, Map r) {
if (e is String) return lookup(e, r);
if (e is List && !isNil(e)) return evalList(e, r);
return e;
}evalList(List e, Map r) {
if (e[0] == '!') return e[1];
e = e.map((e) => eval(e, r)).toList();
return e[0](e);
}
Quotations
I started with implementing quote (or ! as I abbreviated it) because it’s the simplest of the special forms. I ignore the case that ! gets passed more than one argument. Let’s declare this is a feature to add comments. Without arguments, an error is thrown, though.
test('quote', () {
var r = {'a': 1};
expect(eval(['!', 2], r), equals(2));
expect(eval(['!', '!'], r), equals('!'));
expect(eval(['!', 'a'], r), equals('a'));
expect(eval(['!', ['!']], r), equals(['!']));
expect(eval(['!', ['a']], r), equals(['a']));
expect(eval(['!', []], r), equals([]));
expect(() => eval(['!'], r), throwsError);
});Applications
I also already implemented normal function application. For this, we shall define the global environment R with car, cdr, cons, cond (which I abbreviate to ?), eq? (abbreviated to =) and atom. Actually, I will implement the negated function, that is list?, because I also need the same test in eval and can share some code this way.
Map R = {
'car': (p) => p[1][0],
'cdr': (p) => p[1].sublist(1),
'cons': (p) => [p[1]] + p[2],
'=': (p) => isEqual(p[1], p[2]),
'list?': (p) => isList(p[1]),
};bool isList(Object e) {
return e is List && !isNil(e);
}eval(e, Map r) {
if (e is String) return lookup(e, r);
if (isList(e)) return evalList(e, r);
return e;
}
car and cdr
Here are the tests for car (first element of a list) and cdr (the remaining list without the first element):
test('car', () {
expect(eval(['car', ['!', [1, 2]]], R), equals(1));
expect(eval(['car', ['!', [2]]], R), equals(2));
expect(() => eval(['car', ['!', []]], R), throwsError);
expect(() => eval(['car'], R), throwsError);
}); test('cdr', () {
expect(eval(['cdr', ['!', [1, 2]]], R), equals([2]));
expect(eval(['cdr', ['!', [2]]], R), equals([]));
expect(() => eval(['cdr', ['!', []]], R), throwsError);
expect(() => eval(['cdr', ['!', 1]], R), throwsError);
expect(() => eval(['cdr'], R), throwsError);
});
cons
Note, that for cons, I do not support dotted pairs (that is, the second argument must always be a list (empty or non-empty) and cannot be any other atom):
test('cons', () {
expect(eval(['cons', 3, ['!', [1, 2]]], R), equals([3, 1, 2]));
expect(eval(['cons', 3, ['!', []]], R), equals([3]));
expect(() => eval(['cons', 3, 4], R), throwsError);
expect(() => eval(['cons', 3], R), throwsError);
expect(() => eval(['cons'], R), throwsError);
});=
Note, that = will consider (as discussed above) two empty lists to be equal, but non-identical non-empty lists are never equal. I think, this is how eq? traditionally behaves.
group('=', () {
test('equal', () {
expect(eval(['=', [], []], R), equals(true));
expect(eval(['=', 0, 0], R), equals(true));
expect(eval(['=', false, false], R), equals(true));
expect(eval(['=', ['!', 'a'], ['!', 'a']], R), equals(true));
});
test('unequal', () {
expect(eval(['=', [], ['!', [1]]], R), equals(false));
expect(eval(['=', 0, 1], R), equals(false));
expect(eval(['=', true, false], R), equals(false));
expect(eval(['=', ['!', 'a'], ['!', 'b']], R), equals(false));
expect(eval(['=', ['!', [1]], ['!', [1]]], R), equals(false));
expect(eval(['=', ['!', [1]], ['!', [2]]], R), equals(false));
});
test('errors', () {
expect(() => eval(['=', 3], R), throwsError);
expect(() => eval(['='], R), throwsError);
});
});list?
The last function to create unit tests for is list? which tests for non-empty lists:
test('list?', () {
expect(eval(['list?', ['!', [1, 2]]], R), equals(true));
expect(eval(['list?', ['cons', 1, []]], R), equals(true));
expect(eval(['list?', []], R), equals(false));
expect(eval(['list?', false], R), equals(false));
expect(eval(['list?', 0], R), equals(false));
expect(eval(['list?', ['!', 'a']], R), equals(false));
expect(() => eval(['list?'], R), throwsError);
});Right now, my implementation needs only 670 characters — including all whitespace that could (and probably should) be stripped for a fair measurement. This feels good.
Conditionals
Let’s implement the next special form: cond (or ? as I call it).
But before that, I introduce a variant of eval called evalN which evaluates a sequence of expressions and which returns the result of the last evaluation. Without S-expressions, nil is returned.
evalN(Iterable e, Map r) {
return e.fold([], (_, e) => eval(e, r));
}The ? special form will take any number of S-expressions which must be lists that start with a predicate (something that evaluates to a boolean value) and continue with any number of S-expressions which are then evaluated by evalN. I add the code to evalList:
evalList(List e, Map r) {
if (e[0] == '!') return e[1];
if (e[0] == '?') {
for (e in e.skip(1))
if (eval(e[0], r)) return evalN(e.skip(1), r);
return [];
}
e = e.map((e) => eval(e, r)).toList();
return e[0](e);
}It’s funny how the unit tests are much larger than the actual implementation:
group('cond', () {
var r = {'': R, 'a': 1};
test('empty', () {
expect(eval(['?'], r), equals([]));
});
test('single true', () {
expect(eval(['?', [true, 1]], r), equals(1));
expect(eval(['?', [true]], r), equals([]));
});
test('single false', () {
expect(eval(['?', [false, 1]], r), equals([]));
expect(eval(['?', [false]], r), equals([]));
});
test('first true', () {
expect(eval(['?', [true, 1], [true, 2]], r), equals(1));
expect(eval(['?', [true, 1], [false, 2]], r), equals(1));
});
test('second true', () {
expect(eval(['?', [false, 1], [true, 2]], r), equals(2));
});
test('multiple cases', () {
expect(eval(['?',
[['=', 'a', 0], 0],
[['=', 'a', 1], 1],
[['=', 'a', 2], 2]], r), equals(1));
});
test('errors', () {
expect(() => eval(['?', 3], r), throwsError);
expect(() => eval(['?', []], r), throwsError);
});
});BTW, I also experimented with replacing the for loop by a clever iterable expression, but the result gets longer than the straight forward solution (mainly because of the cast I had to introduce — otherwise the Dart compiler insists in e being of type List<String>):
return evalN(e.cast<dynamic>().skip(1).firstWhere(
(e) => eval(e[0], r),
orElse: () => [[]]).skip(1), r);User-Defined Functions
Let’s tackle fn next. This returns a Dart Function which, when called like all other built-in functions, will create a new environment chained to the environment present at the time of the definition of fn in which the formal parameters of fn are bound to the evaluated arguments. And because I don’t use cons cells, I don’t have improper lists and therefore cannot use the same syntax as Scheme for a rest argument. Therefore, the special parameter name & plays this role.
The implementation is added to evalList as before:
evalList(List e, Map r) {
...
if (e[0] == 'fn') {
var f = [e[0]] + e[1];
return (p) {
Map n = {'': r};
for (var i = 1; i < f.length; i++)
n[f[i]] = f[i] == '&' ? p.sublist(i) : p[i];
return evalN(e.skip(2), n);
};
}
e = e.map((e) => eval(e, r)).toList();
return e[0](e);
}Instead of the for loop, I’d love to have used something like zip(f, p) but Dart has no such function — probably because Dart has no statically typed tuple type. This makes me sad…
Let’s break it down:
e[0]is the symbolfn.e[1]must be a list of formal parameters which must be symbols (not checked).fis the list of formal parameters with a dummy first element so that it matches the arguments. I usee[0]instead of something shorter because Dart’s type inference otherwise is too clever and mistypes my list.e[2],...are the function’s body.ris the defining environment.nis the new environment that is freshly created each time the defined function is called.pcontains the arguments for such a call. Note, thatp[0]is the function value itself, that is, the first argument isp[1].- The
forloop binds all actuals to formals. - The
&is special cased and expected to be the last formal parameter. - I also expect to get at least as many arguments as there are formals. We could use
i < p.length ? p[i] : []but I think, it’s better to throw an error if expected arguments are missing.
Note, I could access the formals only inside the loop (saving some bytes) but then I don’t get an error if I mess up the fn declaration before I actually call the function. Therefore I define f outside of the Dart function literal.
I wrote a lot of tests to make sure functions work as expected:
group('fn', () {
test('is a function', () {
expect(eval(['fn', []], R), TypeMatcher<Function>());
});
test('empty', () {
expect(eval([['fn', []]], R), equals([]));
});
test('with body', () {
expect(eval([['fn', [], 3]], R), equals(3));
expect(eval([['fn', [], 3, 4]], R), equals(4));
});
test('single param', () {
var r = {'': R, 'a': 1};
expect(eval([['fn', ['a'], 'a'], 2], r), equals(2));
});
test('two params', () {
var r = {'': R, 'a': 1};
expect(eval([['fn', ['a', 'b'],
['cons', 'b', ['cons', 'a', []]]], 3, 4], r), equals([4, 3]));
});
test('rest param', () {
expect(eval([['fn', ['a', '&'], '&'], 1], R), equals([]));
expect(eval([['fn', ['a', '&'], '&'], 1, 2], R), equals([2]));
expect(eval([['fn', ['a', '&'], '&'], 1, 2, 3], R), equals([2, 3]));
});
test('closure ', () {
var r = {'': R, 'a': 1};
R['f'] = eval(['fn', [], 'a'], r);
expect(eval(['f'], r), equals(1));
r['a'] = 2;
expect(eval(['f'], r), equals(2));
r = {'': R, 'a': 3};
expect(eval(['f'], r), equals(2));
});
test('needs formals', () {
expect(() => eval(['fn'], R), throwsError);
expect(() => eval(['fn', 1], R), throwsError);
});
test('needs enough arguments', () {
expect(() => eval([['fn', ['a']]], R), throwsError);
});
});Binding Values
The last missing piece is df to define a global variable (that is, create a new binding or overwrite an existing one in the global environment R):
evalList(List e, Map r) {
...
if (e[0] == 'df') return R[e[1]] = evalN(e.skip(2), r);
e = e.map((e) => eval(e, r)).toList();
return e[0](e);
}It’s a one-liner. I’m actually using evalN instead of eval because I can. I’m not sure whether it is useful to allow multiple expressions for defining something, but as a neat side effect, ['df', 'x'] sets x to nil.
By changing R to r I could change the semantics to define local variables, but I think, this is not the way define is supposed to work in Scheme.
Here are the unit tests:
test('df', () {
eval(['df', 'a', 1], R);
expect(R['a'], equals(1));
eval(['df', 'b'], R);
expect(R['b'], equals([]));
expect(() => eval(['df'], R), throwsError);
});And … we’re done.
This is the complete interpreter for minimal a Scheme-like programming language implemented with 1132 characters in Dart:
Map R = {
'car': (p) => p[1][0],
'cdr': (p) => p[1].sublist(1),
'cons': (p) => [p[1]] + p[2],
'=': (p) => isEqual(p[1], p[2]),
'list?': (p) => isList(p[1]),
};evalN(Iterable e, Map r) {
return e.fold([], (_, e) => eval(e, r));
}eval(e, Map r) {
if (e is String) return lookup(e, r);
if (isList(e)) return evalList(e, r);
return e;
}evalList(List e, Map r) {
if (e[0] == '!') return e[1];
if (e[0] == '?') {
for (e in e.skip(1))
if (eval(e[0], r)) return evalN(e.skip(1), r);
return [];
}
if (e[0] == 'fn') {
var f = [e[0]] + e[1];
return (p) {
Map n = {'': r};
for (var i = 1; i < f.length; i++)
n[f[i]] = f[i] == '&' ? p.sublist(i) : p[i];
return evalN(e.skip(2), n);
};
}
if (e[0] == 'df') return R[e[1]] = evalN(e.skip(2), r);
e = e.map((e) => eval(e, r)).toList();
return e[0](e);
}lookup(String s, Map r) {
return r[s] ?? lookup(s, r['']);
}bool isNil(Object e) {
return e is List && e.isEmpty;
}bool isEqual(Object e1, Object e2) {
return e1 == e2 || isNil(e1) && isNil(e2);
}bool isList(Object e) {
return e is List && !isNil(e);
}
Factorial Example
We can run the factorial example if we define * and -:
void main() {
eval(['df', '*', (p) => p[1] * p[2]], R);
eval(['df', '-', (p) => p[1] - p[2]], R);
eval(['df', 'fac', ['fn', ['n'],
['?',
[['=', 'n', 0], 1],
[true, ['*', 'n', ['fac', ['-', 'n', 1]]]]]]], R);
print(eval(['fac', 10], R));
}This should print 3628800.
No Special Forms
As you saw, adding new primitive functions like + is very easy. But what if I want to add new special forms, let’s say a let statement that makes it easier to define temporary variables?
Therefore, I make evaluation more uniform and add special forms to the global environment, too. To distinguish them from normal function, I wrap them in Set literals. This way I can use is Set to detect them. Creating my own class would require more characters. Using a Set literal requires Dart 2.2 but I think, this is no problem at all.
Here is the extended environment:
Map R = {
'car': (p) => p[0][0],
'cdr': (p) => p[0].sublist(1),
'cons': (p) => [p[0]] + p[1],
'=': (p) => isEqual(p[0], p[1]),
'list?': (p) => isList(p[0]),
'!': {(e, r) => e[1]},
'?': {q},
'fn': {f},
'df': {(e, r) => R[e[1]] = evalN(e.skip(2), r)},
};q(List e, Map r) {
for (e in e.skip(1)) if (eval(e[0], r)) return evalN(e.skip(1), r);
return [];
}f(List e, Map r) {
List f = e[1];
return (p) {
Map x = {'': r};
for (var i = 0; i < f.length; i++) x[f[i]] = f[i] == '&' ? p.sublist(i) : p[i];
return evalN(e.skip(2), x);
};
}
Note, that I’m now using 0-based parameter lists, not 1-based as before. Because of this, I have to change my factorial example which used this implementation detail for * and -. And I had to change the unit tests for ! which didn’t use the global environment. Perhaps ! should be a special case of the special case and built-in? I don’t know.
Here is the new evalList implementation:
evalList(List e, Map r) {
var f = eval(e[0], r);
return f is Set
? f.first(e, r)
: f(e.skip(1).map((e) => eval(e, r)).toList());
}I’m now counting 1160 characters for the whole interpreter. I noticed that I’m using `isEqual` only once. This can be inlined and the interpreter uses only 1098 characters now.
Shrinking the Code
Let’s take it to the next level.
I can remove all type annotation and relay only on implicit dynamic types. I’m down to 1019 characters and code looks now like this:
...evalN(e, r) {
return e.fold([], (_, e) => eval(e, r));
}eval(e, r) {
if (e is String) return lookup(e, r);
if (isList(e)) return evalList(e, r);
return e;
}...
Most Dart function are one liners and I can use expression bodies instead of block bodies. Now, only 947 characters are required to implement by interpreter.
Can we also remove the var declaration from this 125 characters function so that we can remove the block body?
evalList(e, r) {
var f = eval(e[0], r);
return f is Set ? f.first(e, r) : f(e.skip(1).map((e) => eval(e, r)).toList());
}Sure. I introduce an anonymous function. This one-liner (only formatted here for readability) needs only 114 characters (saving 11 precious characters):
evalList(e, r) => ((f) => f is Set
? f.first(e, r)
: f(e.skip(1).map((e) => eval(e, r)).toList()))
(eval(e[0], r));And I will use the same trick in this 185 characters function:
f(e, r) {
List f = e[1];
return (p) {
Map n = {'': r};
for (var i = 0; i < f.length; i++)
n[f[i]] = f[i] == '&' ? p.sublist(i) : p[i];
return evalN(e.skip(2), n);
};
}Unfortunately, this will add one character because of the indentation, but once I’ve stripped all whitespace, it should be more compact:
f(e, r) => ((List f) => (p) {
Map n = {'': r};
for (var i = 0; i < f.length; i++)
n[f[i]] = f[i] == '&' ? p.sublist(i) : p[i];
return evalN(e.skip(2), n);
})(e[1]);I’m now down to 937 characters. Let’s rename isNil to n and isList to il and lookup to l. I keep only eval and evalN because that’s my API. This saves 43 additional characters.
Because evalList is used only once, I can inline it and save 26 more characters. Including whitespace, the code needs 867 characters and the unit tests are still running.
Stripping Whitespace
Until now, I’ve always used the Dart formatter to get a canonical representation of my code. Let’s change that and strip every whitespace that isn’t required for the final step to make this as small as possible.
I’m arriving at 666 characters (broken down into multiple lines just to display it here):
Map R={'car':(p)=>p[0][0],'cdr':(p)=>p[0].sublist(1),'cons':(p)=>
[p[0]]+p[1],'=':(p)=>p[0]==p[1]||n(p[0])&&n(p[1]),'list?':(p)=>il
(p[0]),'!':{(e,r)=>e[1]},'?':{q},'fn':{f},'df':{(e,r)=>R[e[1]]=ev
alN(e.skip(2),r)},};q(e,r){for(e in e.skip(1))if(eval(e[0],r))ret
urn evalN(e.skip(1),r);return[];}f(e,r)=>((List f)=>(p){Map n={''
:r};for(var i=0;i<f.length;i++)n[f[i]]=f[i]=='&'?p.sublist(i):p[i
];return evalN(e.skip(2),n);})(e[1]);evalN(e,r)=>e.fold([],(_,e)=
>eval(e,r));eval(e,r)=>e is String?l(e,r):il(e)?((f)=>f is Set?f.
first(e,r):f(e.skip(1).map((e)=>eval(e,r)).toList()))(eval(e[0],r
)):e;l(s,r)=>r[s]??l(s,r['']);n(e)=>e is List&&e.isEmpty;il(e)=>e
is List&&!n(e);What a beauty :-)
And the unit tests still run for this blob of code. I feel I’m done. This was a fun experiment, even if I eventually decided against using a Scheme-like interpreter for my project.
PS: I tried to prove the metacircularity (if that’s a word?) of my interpreter by implementing it again in itself but it was too tedious to make it work because it seems, McCarthy’s original relays on the fact, that everything but nil is true and that calling car with not a list is no error but nil, that is, false.
If you want to experiment yourself, here’s my read function to convert a string into a list of S-expressions in 427 characters, still with wordy error messages included.
read(s){var i=RegExp(r"['()]|[^\s'()]+").allMatches(s).map((m)=>m
[0]).iterator;c()=>i.current;n()=>i.moveNext();e(){if(c()=="'"){n
();return['!',e()];}if(c()=='('){n();var l=[];while(c()!=')'){if(
c()==null)throw 'missing )';l.add(e());}n();return l;}if(c()==')'
)throw 'unbalanced )';if(c()==null)throw 'missing expr';var atom=
c();n();return double.tryParse(atom)??atom;}n();var l=[];while(c(
)!=null)l.add(e());return l;}
