Bronze Age Lisp, a Kernel Lisp interpreter

[Oto Havle]

Hi,

I have been trying to implement my own interpreter
for some time. Although it is not finished and lot
of features does not yet work correctly, it already
supports operatives, wrapped applicatives (with
optimizations) and guarded continuations.

You can download it from

https://bitbucket.org/havleoto/bronze-age-lisp

It needs klisp to bootstrap (it cannot bootstrap
itself yet), and it is implemented mainly in x86
assembly. I was inspired by the 'dream' Scheme
Interpreter, which shows that writing lisp
interpreter in assembly is not that hard.

I hope that it will be mostly compatible with
klisp in the future. Besides lack of features,
klisp user may note that my implementation
of $and?, $or?, $when and $unless is not robust
in the tail calls. On the other hand, Bronze Age
Lisp supports UTF-8 characters from the start.

Best wishes,

Oto Havle.

[Andres Navarro]

I missed this when you sent it.  I've just taken a look at the repo,

and it looks really interesting.  I'll have to study it in more detail

later on. 

It would be nice if could you share here your approach, motivations,

difficulties, successes, etc.  I think it would be very enlightening.

And I'm such a sucker for implementation techniques.

Regards,

Andrés Navarro

--
You received this message because you are subscribed to the Google Groups "klisp" group.
To unsubscribe from this group and stop receiving emails from it, send an email to klisp+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Oto Havle]

Hi Andres,

On 16.8.2013 17:40, Andres Navarro wrote:
> I missed this when you sent it. I've just taken a look at the repo,
> and it looks really interesting. I'll have to study it in more detail
> later on.
>
> It would be nice if could you share here your approach, motivations,

Part of the motivation was to have faster interpreter. Until we figure
out how to compile the Kernel Language (if it is possible at all),
all we can do is to speed up the interpreter a bit.

There is definitely room for improvements:

1) the lua garbage collector on top of C malloc(), although robust
and portable, is not a good match for a lisp with lot of
heap-allocated short-lived continuations.

2) klisp spends too much time allocating and deconstructing
argument lists.

3) klisp values take too much space (e.g. 32 bytes for single cons cell),
decreasing efficiency of processor caching.

(Disclaimer: I do not have any rigorous measurements to back these arguments.)

Bronze Age Lisp is faster than klisp for small programs which rely heavily on
interpreted code and function calls. It is not suitable for big programs which rely
on the reader and printer or the numeric tower, I mostly neglected these topics.

I'll write up about the different approaches later.

Try running fklisp.k in Bronze Age Lisp. But note that I also cheat a bit, my
implementation is not as robust as klisp.

> difficulties,

One would think that the language Kernel Report is so simple that
implementation could be very small and easy. I found that this
is not the case, if you write the interpreter in low-level language.
Besides the library combiners, you have to implement and debug at least

- garbage collector
- symbol interning
- equal? and copy-es-immutable, which must work with cyclic structures
- searching guards in continuation tree
- big integers
- s-expression reader and printer

The interpreter will end up surprisingly big. Bronze Age Lisp executable
now approaches 180 kilobytes (stripped).

> successes, etc.

Because of rather primitive design (thats why it is named Bronze Age ...),
the interpreter starts up quickly.

> $ strace bronze-0.2 -e '(exit 42)'
> execve("/usr/local/bin/bronze-0.2", ["bronze-0.2", "-e", "(exit 42)"], [/* 34 vars */]) = 0
> _exit(42) = ?

Try this with any C program dynamically linked with GNU libc.

Best wishes,

Oto Havle.

[Andres Navarro]

On Sat, Aug 17, 2013 at 7:02 AM, Oto Havle <havl...@gmail.com> wrote:

  Part of the motivation was to have faster interpreter. Until we figure
out how to compile the Kernel Language (if it is possible at all),
all we can do is to speed up the interpreter a bit.

I'm with you in this one.

Before giving my opinions on the rest of the issues I'll give my motivation for

writing klisp, so that everyone can follow my reasonings/justifications.

When I started writing klisp there weren't ANY Kernel implementations, not even

John's reference implementation in scheme.  I started with a scheme interpreter
derived from the example in the decomposing lambda paper, and went from there.

Later on I decided to port it to C, and I chose to base it on the lua interpreter
because of the really clean and portable code base.  It saved me from having to

write a garbage collector (which I had already done a couple of times, one was

even a real time garbage collector for J2ME).  It also came with a pretty good
hashtable implementation which will feature in some of my explanations below and
also could be easily embedded in c programs and so was a good base for an
extension language, which as Kernel can only be interpreted for now, seemed like
a good fit.

My intention was just to have an interpreter that supported every feature of
Kernel and let me experiment with open issues, such as libraries, object systems,

generic operations, etc.  My main focus was, as Oto mentions here, correctness,

robutsness (as defined in the report) and completeness.   Other than that I also
wanted the interpreter to be embeddable and portable.  Efficiency is always important,

of course, but took a second (or third) row in this case.

As the code stabilizes and all or most most features are there, I expect to write a lot
more Kernel code.  Once we have a lot of Kernel code I feel we can start profiling to
see where the major bottlenecks are and then I can start thinking of ways to make klisp

better and faster.  A number of issues were soon discovered (and even predicted) with
some of the decision I took, many of which Oto addresses here.  I expect many others
to follow once we have a good corpus of code and some profiling infrastructure.

It will be important to be able to address these in order for the Kernel language to be a
viable alternative to other more mainstream languages.

I find it very healthy for our (small) community to have as many implementations as

possible, in order to be able to tackle these and other issues as well (like integration in
other environments: like the browser, or the JVM).

  There is definitely room for improvements:

    1) the lua garbage collector on top of C malloc(), although robust
       and portable, is not a good match for a lisp with lot of
       heap-allocated short-lived continuations.

This is certainly right.  For anyone who didn't read the code for klisp.  klisp uses malloc

(really a user defined function, that in the interpreters is malloc) to allocate each and every
object.  This comes from lua, where objects are (relatively) rare, mostly hashtables.

In klisp though, almost everything has to be alloc'ed: pairs, environments, continuations, etc.

Continuations & pairs are particularly problematic, because they are used by the interpreter
heavily: continuations instead of a regular stack for function calling and pairs for argument

lists (see below). 

I plan to address this eventually by having a pool for fixed size objects (like pairs, and with a
little trick, continuations).  The pool could be a linked list of free objects, like in old lisps and
then the allocation of these types of objects could be just a pointer reference and actualization
of a pointer.  The GC would return objects of these types to the pool, and only when the pool actually

empties, should malloc be called for this objects.  This is not that hard to do, but I am waiting

to have some profiling done first, to have an exact idea of what the runtime impact will actually be.

(I expect it to be quite large, as you do, obviously)

 

    2) klisp spends too much time allocating and deconstructing
       argument lists.

This is true.  While I have a couple of simple tricks to avoid some of the work some times (like

avoiding copying immutable lists, etc) much time is spent constructing arguments lists
that will (very) soon be deconstructed.  There has to be a way to avoid most of these, but I didn't
attack it directly.  Would love to check out your ideas on this.  Of course any solution here should
be able to fall back to the general case of argument list construction when needed.  I sometimes

do more than actually needed for robustness in this case, I can certainly review the code and

avoid some copies & the like (for example, klisp copies the list of arguments before evaluating
so that mutation to the list doesn't affect the number of arguments, this is not spelled in the report
and could probably be dropped, given appropriate care to preserve robustness in case anyone

mutates the list)

 

    3) klisp values take too much space (e.g. 32 bytes for single cons cell),
       decreasing efficiency of processor caching.

I think a cons cell actually is 36 bytes long...  I think it's 8 bytes for
GC pointers, 4 for flags, 8 for car, 8 for cdr and 8 for Mark.  Part of the reason is that we need two pointers
because of how the lua GC works instead of two (4 bytes wasted, that could be avoided for objects using the
pool idea above) and another one is that the mark takes 8 bytes.  There also the thing where the car & the cdr take 8
bytes (when they could use 4) but I prefer to have doubles as immediate values & support 48 bits pointers,
both of which are possible with the 8 bytes approach. 

The mark is used for most/all of the procedures that work with cyclic structures. I am considering using
hashtables for this.  It will certainly be slower in general, but in many cases can be avoided

with some previous checks (for example, in eval, arguments lists are mostly short so a simple check to
see if a list is acyclic and shorter than say, 4 or 5 items, would avoid use of the hashtable or any other kind
of cyclic management).  Other advantage of the hashtable approach instead of the mark is that multiple
threads could traverse (potentially) cyclic structure at the same time, which would open the way to
avoiding the GIL (global interpreter lock) that we have (now that I added threads).

 

  (Disclaimer: I do not have any rigorous measurements to back these arguments.)

While I am a fan of profiling before optimizing (both in order to find what needs to be optimized next, and what
the real gain was), I think you are quite right in that these are some of the main causes of slowdown of the
klisp interpreter.

 

  Bronze Age Lisp is faster than klisp for small programs which rely heavily on
interpreted code and function calls. It is not suitable for big programs which rely
on the reader and printer or the numeric tower, I mostly neglected these topics.

I always liked the javascript and lua world where every number is a double.  Makes for a much easier to write

interpreter/compiler and is quite usable.  In lisp (especially scheme) we have long tradition with the numeric
tower though, and it shows in the Kernel report.  If I were to write a javascript based kernel-like language
implementation I would ditch the tower and run away with doubles everywhere.

 

  I'll write up about the different approaches later.

I'm looking forward to it.

 

  Try running fklisp.k in Bronze Age Lisp. But note that I also cheat a bit, my
implementation is not as robust as klisp.

The report is right here, in that it allows for implementations anywhere in the spectrum.  There is
definitely place for a fast non-robust interpreter.

 

difficulties,

  One would think that the language Kernel Report is so simple that
implementation could be very small and easy. I found that this
is not the case, if you write the interpreter in low-level language.
Besides the library combiners, you have to implement and debug at least

 - garbage collector
 - symbol interning
 - equal? and copy-es-immutable, which must work with cyclic structures
 - searching guards in continuation tree
 - big integers
 - s-expression reader and printer

The thing I had to work the most with is cyclic handling & continuations.  Much of the klisp design has to do
with the ability to handle cycles & capture continuations at any time: from the eval loop to the object structure. 
A Kernel dialect that didn't handle cyclic structure & first-class continuations would certainly be a lot easier to
implement.  Ditto for the numeric tower.

The garbage collector is hard to escape from.  You can choose how to implement it but you need at least a
basic one.

As for the reader/writer, they are kind of hard if you don't usually write them, but become a little easier after some
time. Of course there are lot of corner cases and writing a robust reader with good error messages remains a

very difficult task. Symbol interning i didn't find particularly hard, can be done with a list or hashtable, which you
need in any case for representing environments.

 

 

The interpreter will end up surprisingly big. Bronze Age Lisp executable
now approaches 180 kilobytes (stripped).

I have an even worse problem in klisp, because of the c library and all integrated combiners.

But, I guess if the interpreter is powerful enough, we can live with that, in this day and age.

 

successes, etc.

Because of rather primitive design (thats why it is named Bronze Age ...),
the interpreter starts up quickly.

$ strace bronze-0.2 -e '(exit 42)'
execve("/usr/local/bin/bronze-0.2", ["bronze-0.2", "-e", "(exit 42)"], [/* 34 vars */]) = 0
_exit(42)                               = ?

Try this with any C program dynamically linked with GNU libc.

It's a thing of beauty, writing something on the bare metal with no support from external libraries.
I always liked, for example, that the interpreter for luajit was written in assembler.  It gives it something
extra.

I dream of someday writing a simple stack processor in Verilog in order to support an assembly-written
interpreter for Kernel a have a little lisp processor... maybe some day.

 

Best wishes,

  Oto Havle.

Regards,
Andrés Navarro