A Compiler for a Pure Lazy Functional Language: SASL

SASL is a pure lazy functional programming language described by Torsten Grust at his web site. (The language itself was originally developed by Dave Turner.) It's a little like a simplified Haskell without types. Based on his course notes I have implemented SASL in C. What's interesting about the approach described there is that uses Combinatory Reduction so the flow of execution of a program that is running is nothing like what you'd expect from an ordinary procedural language such as C.

Below is a sample piece of code. Just pass it in as standard input to the code here once you have built it and it should output the 19th Fibonacci number. Note that the algorithm to generate thes enumber is particularly elegant. The list of Fibonacci numbers f={a0,a1,...} is simply the list {1,1} followed by the elementwise sum of f and its tail. Because SASL is a lazy language it has no trouble finding the 19th element even though this list is in fact infinite.

Unfortunately SASL is slow because combinatory reduction, while an interesting theoretical tool, isn't always efficient. I've probably also made some mistakes in understanding how the reduction steps work as well.

Note that by default there is no garbage collection so it is profligate in its use of memory. However it can be linked with the Boehm-Demers-Weiser garbage collector.

Just briefly: combinatory reduction works like this: we are building a functional language so we start with just one type: functions. In fact we build almost everything out of 3 functions: S, K and I.

I(x) = x
K(x) = the function that maps everything to x i.e. K(x)(y) = x.
S(f)(g)(x) = f(x)(g(x))
These are enough functions to compute anything computable, they are universal. (Note that these functions have nothing to act on except functions built out of compositions of S, K and I.) For example we can define the integer n to be the function that maps f to the nth iterate of f. Eg. 3(f)(x)=f(f(f(x))). Note something else, all of our functions are functions of one argument. This is because we use currying. Consider a function f of two arguments. We can replace it with the function f' s.t. f'(x)(y)=f(x,y). So we can built multi-argument functions out of functions of a single variable. (For example we can think of K above as actually being a function of two variables that simply projects out its first argument.) With this in mind we can assume function application associates to the left, drop parentheses, and write the above as:

Ix = x
Kxy = x
Sfgx = fx(gx)
The functions S, K and I are called combinators and combinator expressions may be evaluated simply by using the above identities as rewriting rules applied to a string of text. For example we have SKKI=KI(KI)=I. (If you want to play further try this playground.)

The SASL compiler merely converts the input code into expressions built out of the S, K and I combinators. In practice handling numbers as described above is slow so SASL understands integers as a primitive type and has additional combinators such as '+' and '*' so we can perform efficient arithmetic. Additionally one or two extra combinators are added to handle list operations and also to increase the efficiency of reduction. But at the end of the day, the SASL compiler works by converting your code into a big expression made of combinators and uses simple rules to reduce them.

One interesting challenge is the support of recursion in SASL. Note that this implementation fully supports recursive definitions. This is achieved via the Y-Combinator. It has the amazing property that when applied to a function it returns a fixed point for that function so f(Y(f))=Y(f). Surprisingly it can be built out of the S, K and I combinators: Y = S(K(SII))(S(S(KS)K)(K(SII))). For efficiency it has been implemented as a primitive combinator in this compiler.

def id x = x.						
def until p f x = if p x then x else until p f (f x).	
def comp f g x = f (g x).				
def map f l = if l=nil then nil				
else (f x):(map f xs) where x = hd l;			
				xs = tl l.			
def fold m z l = if l=nil then z			
	else m x (fold m z xs) where x = hd l;		
					 xs = tl l.		
def append l1 l2 = if l1=nil then l2			
	else x:(append xs l2) where x = hd l1;		
					xs = tl l1.		
def reverse l = if l=nil then nil			
	else append (reverse (tl l)) ((hd l):nil).		
def filter p l = if l=nil then nil			
	else (if p x then x:(filter p xs)			
	else filter p xs) where x = hd l;			
			   xs = tl l.			
def sort p l = if l=nil then nil			
	else insert p (hd l) (sort p (tl l))			
	insert pp e ll = if ll=nil then (e:nil)		
		if pp e (hd ll) then (e:ll)		
		((hd ll):(insert pp e (tl ll))).	
def drop n l = if n<=0 then l				
	else if l=nil then nil				
	else drop (n-1) (tl l).				
def take n l = if n=0 or l=nil then nil			
	else x:take (n-1) xs where x = hd l;		
				   xs = tl l.		
def at n l = if n=0 then hd l				
	else at (n-1) (tl l).				
def null l = l=nil.					
def length l = if l=nil then 0				
	else 1+(length(tl l)).				
def sum = fold plus 0.					
def product = fold times 1.				
def plus x y = x+y.					
def mul x y = x*y.					
def div x y = x/y.					
def div2 y x = y/x.
def minus x y = x-y.
def minus2 y x = y-x.
def lt x y = x<y.					
def leq x y = x<=y.					
def eq x y = x=y.					
def geq x y = x>=y.					
def gt x y = x>y.					
def zipWith f x y = if x=nil then nil			
	else f (hd x) (hd y):zipWith f (tl x) (tl y).

at 19 fib where fib = 1:1:(zipWith plus fib (tl fib))
Note that most of the above code is just the 'standard prelude' for SASL. It's the last line that does the work.

PS My operator precedence may be slightly different from the original SASL.




Feel free to email me (Dan Piponi) at stirfry (at) sigfpe.com.
Back to Robotics.