ShenDoc 30



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
>>> 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)

Basic Types in Shen and Kλ
The Primitive Functions of Kλ
The Syntax of Kλ
Notes on the Implementation of Kλ
Boolean Operators
The Syntax of Symbols
The Semantics of Symbols in Shen and Kλ
Strings and Pattern Matching
Character Streams and Byte Streams
Bytes and Unicode
Reader Macros
Standard Vectors and Pattern Matching
Non-standard Vectors and Tuples
Generic Functions
Type Declarations
External Global Variables
Property Lists and Hashing
Error Handling
Floats and Integers
The Timer
Special Forms

Built by Shen Technology (c) Mark Tarver, September 2021