The Tar Pit

This document describes the result of my attempts at implementing a Lisp (more precisely a Scheme) scripting language in Ada. The effort spawned from numerous discussions in the logs¹ and used a few important references². In short, the goal is to have a Lisp interpreter that is a. small, easy to read, i.e. fits-in-head; and b. written in a sane language, sans pointers and other cockroaches inhabiting today's broken computing machines.

I have attached below:

• a tarball: adalisp-proto.tar.gz; and
• a detached signature by yours truly: adalisp-proto.tar.gz.spyked.sig.

The source code is organized as follows:

• a set of restrictions for the implementation (restrict.adc)³;
• a Lisp machine representation in Ada (lispm.{ads,adb});
• a S-expression parser (parser.{ads,adb});
• a Scheme evaluator (evaler.{ads,adb}); and finally,
• some glue that puts everything together in a Read-Eval-Print Loop (test_repl.adb).

Additionally, the tarball includes a GPRbuild project file and a small set of tests. To compile and run the tests, run in the project directory:

$ gprbuild
$ cat test.scm | ./bin/test_repl

In the end, some comments about the implementation:

[i] The implementation is incomplete. A lot of functionality is still unimplemented, e.g. <, >, gensym, quasiquotes, let*, letrec. This is just a matter of adding them into the evaler.

[ii] The implementation is incomplete also because it has no mechanism for recovery from parser and evaler errors, etc.

[iii] Reading from standard input is utterly broken in many ways, because Ada's Get_Char doesn't know how to read newlines among others. These should be replaced with FFA's I/O routines.

[iv] The author's cockroaches led him to implement Scheme booleans (#t, #f) as a subset of integers. These are traditionally symbols. On another note, it's not immediately clear that schemisms such as #t/#f are relevant at all, one might as well use t/nil as truth values.

[vi] The code should be refactored in more than one direction. One important direction is separating all the mechanisms in a libadalisp to be used for embedding into other applications. Another direction involves improving readability by e.g. using keyword arguments instead of the positional ones that are so popular in C programs. But more importantly, the user should be able to swallow the program piece by piece, as is healthy and has been demonstrated before.

[vii] I suspect the evaler is far from correct, but this can only be evaluated [sic!] after the completion of point vi above.

[viii] Both the parser⁴ and printer can be replaced with lispm bytecode that gets loaded at the beginning of the world and evaluated as needed. The current parser module could be possibly used to bootstrap the bytecode generation process.

[ix] Currently, lispm memory has a fixed static size. As FFACalc demonstrates, the heap size can be passed as a command-line argument and initialized when the program boots. This gives the user some flexibility in choosing how much memory their Lisp program can use, especially given the fact that there is no garbage collection implemented.

[x] The list is far from exhaustive. Some aspects are already being discussed in the logs; other threads will inevitably arise.

Filed under: computing, lisp.
RSS 2.0 feed. Comment. Send trackback.