SASL

The SASL compiler/interpreter was jointly written by Niels and Jurjen.

The compiler was written in LISP and is described elsewhere.

The interpreter was originally inspired by a master's thesis on garbage collection of SASL graphs. The ideas on garbage collection ultimately ended up not being used, but SASL's clean syntax and lazy evaluation made Jurjen's heart jump, so he decided to implement it, in the processes attracting Niels to the project with his enthusiasm.

The SASL interpreter, like the LISP interpreter, had a memory structure consisting of cells that were all the same size. The storage of names, numbers and lists of combinators was done using linked lists. The garbage collection algorithm was horrible: one bug in the implementation was never found.

Nevertheless, the interpreter happily digested the following SASL compiler output:

fac (((if B ((= B L) C 0)) C 1) S ((* (fac B ((- B L) C 1))) S L))

(fac 100)

and dutifully printed the result of the computation (the factorial of 100):

933262154439441526816992388562667004907159682643816214685929638952175999 
932299156089414639761565182862536979208272237582511852109168640000000000 
00000000000000

The most interesting part of the SASL interpreter was the multiplication routine. It multiplied using the "butterfly algorithm", producing the result digits backwards. To do this, the digits of one of the multiplicands were first reversed in place (reversing the pointers of the "digits" which were 24 bits each). After this was done, it was then relatively "easy" to multiply the digits one by one, and add them to get the result digit.

The loop control code of the above algorithm is still one of the most complicated Jurjen ever wrote, especially considering that it was written in assembly language!

The SASL compiler/interpreter is also described on pages 45-51 of the book "THE ORDINATOR PROJECT".