Notes on the Implementation of KLambda
These notes are for programmers wishing to implement Kλ.
Tail recursion optimisation is a must and part of the Kλ standard. Quite of few of the reader routines
for Shen will not work in a language like Python which lacks it. In such a case, a platform provider
working to move Shen to a non-TCO language has to consider how to port tail recursive Kλ code.
Kλ uses lexical scoping. This is pretty standard now. Qi II actually used dynamic scoping in its
implementation of Prolog to implement variable binding but in Shen this is now done with vectors.
Kλ follows applicative order evaluation. Except for the following constructions.
cond, and, or, if, freeze, let, defun
Kλ follows a dual namespace model. A classic model for a Lisp views 'defun' and 'set' as interchangable.
Both are thought of as asserting a math'l identity so that '(defun f (x y) y)' is sugar for
'(set 'f (lambda x (lambda y y)))'. This model supposes a single namespace for functions and variables.
You have this in Python.
So in the classic model 'defun' and 'set' together are logically superfluos. It is more reasonable to
regard 'set' as logically prior since incrementing a global variable is much more easily carried out
through 'set' than 'defun'. Incrementing should be very fast - function compilation is generally very slow.
In a dual namespace model, the 'defun' and 'set' are regarded as creating an association between the symbol
and something else; it is a mapping not an assertion of identity.
Generally Qi and Shen require a dual namespace for symbols. The reason for this is to do with the Qi
evaluation strategy for symbols which is that symbols are self-evaluating. In Qi the symbol 'f' evaluates
to itself. If we want to get at the value associated with 'f', we type '(value f)'. Hence f is not thought
of as shorthand for a value, but is merely a symbol to which objects (definitions, global assignments etc)
can be attached.
Generally, if we had a single namespace, we would have a convention of a different kind. For instance
if '(set f 6)' entailed that 'f' really meant (was just a shorthand for) 6, then we would expect that typing
in 'f' to the REPL would return 6. In Python that's exactly what happens with symbols.
>>> f = 9
>>> f
9
>>> def f (): return(9)
...
>>> f
But Qi does not work that way. Allowing symbols as self-evaluating really points away from this model.
Hence Kλ and Shen are committed to the dual namespace approach.
Partial applications are not mandatory . The S series kernels introduced in 2021 eliminated
the need for implementors of Kλ to tackle this. Shen itself respects partial applicartions courtesy of
the Shen reader.
Note in Shen 8.0, typed zero place functions were introduced. Here is pi as a constant.
(define pi
--> number
-> 3.142)
In Kλ
(defun pi () 3.142) |
