Bronze Age Lisp design part 3 - function calls

[Oto Havle]

Hi all,

this is the third of the series of posts about design choices
in Bronze Age Lisp, interpreter of the Kernel Language
(https://bitbucket.org/havleoto/bronze-age-lisp).

Efficient function calls (or, in terms of John Shutt's Kernel Report,
evaluation of applicative combinations) are obviously important for the
overall interpreter performance. Let's look first how they are
implemented in Klisp.

To evaluate the form X = (f a1 a2 ... aN),

1) Klisp allocates a continuation for evaluation of f. The evaluation
takes place without further overhead.

2) The interpreter copies the tail of the original form and notes is
structure. An argument list must be either a finite list terminated
by NIL, or a cyclic list. The interpreter allocates N pairs for the
list copy.

3) The interpreter evaluates all three arguments and stores the result
in a new list. For each argument, one continuation and one pair is
allocated.

4) The interpreter copies the list again. If the original argument
list was cyclic, the list of evaluated arguments will be given the
same structure.

Copying cannot be replaced by in-place modification. The original
argument list itself may be mutated, and the continuations created
during evaluation may be captured.

We can see that the whole operation involves allocation of 3N pairs and
(N + 2) continuations. The list of evaluated arguments is likely to be
checked and deconstructed by the combiner <f> later.

The overhead may be justified:

- If the argument list is long. Functions with four or more arguments
are rare. Functions which take arbitrary number of arguments, like
(+ ...) or (make-environment ...), are normally called with
at most two or three arguments.

- If the argument list is cyclic. John Shutt's Kernel Report emphasises
support for cyclic structures, and allows cycles in argument lists as
well. In practice, cyclic lists are rarely used.

- If the execution of the combiner itself takes long time. The overhead
of argument evaluation can be neglected. If the normal mode of
operation of the language runtime is interpretation, then this is
almost always true for user-defined functions.

The overhead of argument evaluation should be minimzed especially for
built-in functions. These functions are implemented by fast native code.
The operation performed is often simple. Consider, for example,
(eq? ...) or (cons ...).

In Bronze Age Lisp, calls to most built-in applicatives which take up to
three arguments are optimized. Let's now look at the operations
performed by Bronze Age Lisp interpreter:

1) The interpreter allocates a continuation for evaluating the head.
The continuation is allocated in the transient are of the heap
described in the previous post. In the continuation is not captured,
the space in the transient are of the heap is reclaimed immediately.

2) The interpreter executes code specialized for evaluation of
two-argument applicatives. The structure of the list is determined,
by an operation equivalent to (get-list-metrics). If the list does
not match the expected structure (N elements, no cycle), an error is
signalled. Then, a continuation is allocated for evaluation of the
first argument. The continuation is placed in in the transient area
of the heap. The first argument is passed to the evaluator, the
remaining (N-1) arguments are stored in the continuation.

Note that there is significant incompatibility between Bronze Age
Lisp and Klisp. Klisp detects errors in argument list structure only
after evaluating the arguments.

3) After evaluation of the first argument, the interpreter detects
whether the continuation is still in the transient area of the
heap. If so, the continuation may be safely mutated and reused.
Otherwise, a new copy of the continuation is allocated in the
transient area. (The continuation may become part of the persistent
area, if it is captured, or if a garbage collection occurs.) The
evaluated argument is stored in the continuation, and the next
argument is passed to the evaluator.

4) Eventually, the continuation contains the evaluated arguments. The
evaluated arguments are then copied in machine registers and the
native code implementation of the applicative is called.

During most calls, no continuations are captured, and GC does not occurs.
There are no unnecessary allocations in the persistent area of the heap
and the space used in the transient area is reclaimed before execution
of the applicative starts.

To be continued...

Oto Havle.