fklisp: historical perspective & motivation

[Andres Navarro]

I'll want to write a little about how fklisp works, but first I'll
talk a little about the motivation and historical perspective that
pushed me to try and write it:

As many will know, the main problem in trying to compile Kernel source
code is that because of first class environments and operatives
(fexprs), it's not possible to decide in general where each
subexpression in the source expression will be evaluated (or if it is
evaluated at all).  To make matters worse, as Kernel has no reserved
keywords, even simple combiners like $if or $lambda are represented as
regular symbols in the source expression and have to be looked up in
the dynamic environment each time they are found during evaluation,
just as any other combiner the user writes.  This problem with fexprs
was known for a long time [Pi80].  Later, a paper by Wand [Wa98]
reachs a strong theoretical result that seemed to condemn fexprs
forever.

However there is some hope.  On the theoretical side, some of the
generalizations/conclusions from the Wand paper were later refuted by
John Shutt [Sh07][Sh10].  This mostly have to do with having a
language in which evaluation is explicit (like Kernel and fklisp)
instead of implicit (like the example calculus in Wand's paper
[Wa98]).  This lends credibility again to the idea that fexprs can be
reasoned about, given the right tools.  On the practical side, Shutt
also raises the point that lexical scope and some other Kernel design
decisions facilitate the task of reasoning about fexprs
[Sh03][Sh09][Sh10].  This isn't addressed in Pitman's paper [Pi80],
but in hindsight, might be the one factor that made the fexprs of old
virtually uncompilable.

As a matter of fact, while Pitman is cited a lot in the discourse
against fexprs, he doesn't really make any technical argument against
them, he just says that as they confuse the compiler (especifically
the MACLISP compiler from the 70's & 80's) they shouldn't be included
in new languages. i.e. he doesn't get into the details of why the
compiler can't work with fexprs, he simply states it.  And for the
record I just want to state that while I'm trying now to show that
fexprs can in fact be reasoned about and be used in languages and code
that can be compiled, I think at the time Pitman gave this talk, it
was the right call.  The tools just weren't there.  I just wished
someone tried to tackle the problem of fexpr compilation instead of
just sweeping it under the rug...  We'll see that by using abstract
interpretation (which was developed for different use cases in the
late seventies), it is in fact possible to reason about fexprs (and
even compile code that uses them) in a statically scoped dialect of
lisp.  Whether this will result in a general purpose tool that can
compete with macros and regular compilers remains to be seen, right
now I'm concerned with showing feasability, as most people just take
the fact that fexprs are "bad" as gospel.

Regarding the issue of dynamic vs static scope and why static scope
makes reasoning about fexprs easier, please consider the following
example definition in fklisp:

($labels (($cond clauses denv
            ($if (null? clauses)
                 ($error (no clause was true))
                 ($if (eval (caar clauses) denv)
                      (eval (cadar clauses) denv)
                      (eval (cons $cond (cdr clauses))
                            denv)))))
  ...)
   

Here $labels is an fklisp special operative to define potentially
recursive (or mutually recursive) combiners, both operatives (fexprs)
and applicatives (functions/exprs) are allowed, depending of whether
one includes the second argument (in this case 'denv') for the dynamic
environment (it is also possible to construct applicatives that take
the dynamic argument, like get-current-environment, by wrapping the
env param inside parenthesis like so: "($labels
((get-current-environment #ignore (denv) denv)) ...)").  The body of
the $labels call (here it's denoted by an ellipsis '...') is evaluated
in an environment where all the combiners in the $labels form are
bound. So in effect this whole $labels expression creates an
environment where $cond is defined and then evaluates the body (\...')
in that environment.  So let's see what happens here under both
lexical and dynamic scoping rules:

Let's say you want to compile this and the compiler is smart enough to
be able to reason about the $cond operative (fexpr).  Even having a
very smart compiler wouldn't help you under dynamic scope because you
don't know from where this operative (fexpr) will be called.  So if
you have this:

($let ((sign ($labels (($cond clauses denv
                         ($if (null? clauses)
                              ($error (no clause was true))
                              ($if (eval (caar clauses) denv)
                                   (eval (cadar clauses) denv)
                                   (eval (cons $cond (cdr clauses))
                                         denv)))))
               ($lambda (x)
                 ($cond ((positive? x) 1)
                        ((negative? x) -1)
                        (#t 0)))))
       ($cond ($vau clauses #ignore (car clauses))))
  (sign 3))

Then the result would be '((positive? x) 1)'.  The reason is that sign
(the applicative created by the $lambda) is called in a dynamic
environment where $cond is defined as an operative that takes the car
of its list of operands, which is the following list: '(((positive? x)
1) ((negative? x) -1) (#t 0))'.  So when sign is applied to 3 it calls
this new definition of $cond, which returns the car of that list which
is '((positive? x) 1)' instead of the presumably wished for '1'.

Under static scoping however, the fact that $cond is redefined in the
dynamic environment of the call to sign is immaterial.  All
expressions in the body of the $lambda form are evaluated under the
static environment where the $lambda form was evaluated, namely the
environment created by $labels.  The same is true of the symbols in
the body of the $cond definition (so that even if you were to try and
redefine $if before calling $cond, it wouldn't change a thing).  Then,
the $cond in the $lambda form always refers to the real definition of
$cond and this results in '1' as expected.

As can be seen, static scoping allows us to reason about the
definition of an fexpr, independently of where that fexpr may be
called from, while dynamic scope leave us hopeless because even the
symbols in the body of the fexpr could be renamed under our feet.  Of
course, even under dynamic scoping rules, if you knew all the call
sites of all fexprs you could still reason about them, but this would
limit us to whole-program analysis and so it's not very encouraging.
This is especially so on fklisp where operatives (fexprs) are first
class and so can be passed as arguments returned by functions, etc.

This concludes the historical perspective and motivation for fklisp,
in a future email I'll write about how fklisp works (or tries to
work!).

References:
[Pi80] Kent Pitman: Special Forms in Lisp
[Sh03] John N. Shutt: Decomposing Lambda - The Kernel Programming Language
[Sh07] John N. Shutt: vau-calculi and the theory of fexprs
[Sh09] John N. Shutt: Revised^-1 Report on the Kernel Programming Language
[Sh10] John N. Shutt: Fexprs as the basis of Lisp function application or
                      $vau: the ultimate abstraction
[Wa98] Mitchell Wand: The Theory of Fexprs is Trivial



Regards,
Andres Navarro