Alef is an acronym for Alef Lazily Evaluates Functions and it is a toy functional programming language with lazy evaluation and Hindley-Milner type inference . It is intended as an illustration of the basics of the graph transformation semantics behind lazy, pure functional programming languages like Clean or Haskell (but unlike ML and F# which are languages with strict evaluation).
Alef is implemented in LISP and takes the form of an interpreter and a compiler targeting the .NET platform. Due to its illustrative goal, unneccessary parts like parsing are omitted.
You can download the Alef interpreter and compiler from its GIT repository by using the following command:
An Alef program contains two kinds of definitions: type definitions and function definitions.
A type definition describes an algebraic data type by giving its type parameters and its constructors, like in the following example:
(deftype list (t) nil (cons t (list t)))
This directive does introduces a new type list with one type parameter, and two constructors for it: nil with zero arguments and cons with two.
Functions are defined using pattern matching. A program can contain multiple definitions for a given function, each differing in the pattern they match and their bodies.
When a function is applied to actual arguments, definitions of the function are considered for matching in the order of their declarations. The first definition that has a matching pattern is then the one to reduce by.
Patterns can be one of the following:
- _ matches any actual.
- C p1 p2 ... pn, where C is a constructor and all pi are patterns, matches values that are constructed as (C a1 a2 ... an) where each ai constructor argument matches pi. Note that the argument has to be evaluated to a constructor to check for matching -- in other words, patterns of this kind are the ones that drive the evaluation.
- v, where v is not a constructor, matches anything and introduces a new variable v to the function's body, binding it to the actual argument.
For example, using the above definition of the type list, we can now write map using two patterns, one for the empty list and one for lists consisting of a head item x and a tail xs:
(define map (_ nil) nil) (define map (f (cons x xs)) (cons (f x) (map f xs)))
- (C e1 e2 ... en) where C is a constructor is a value with instance actuals e1, ... , en.
- v where v is a variable is whatever is bound by v.
- (f e1 e2 ... en) where f is a function applies f to e1, ..., en. When the application is evaluated, the reduction is made according to the first definition of f with a pattern matching e1, ..., en.
(v2 e2) ...
(vn en)) e)
introduces new variables v1, ...,
vn to e1, ...,
en, e, and bounds them, respectively, to
e1, ..., en. Note that the
variables are introduced to the right-hand expressions all at
once, so you can create mutually recursive data
structures. For example, the following code:
(let ((l1 (cons 1 l2)) (l2 (cons 2 l1))) (map (lambda (x) (+ 7 x) l1))
(p1 p2 ... pn) e)
is the anonymous function with formal patterns
p1, ..., pn and body
e. For example, the following code yields the infinite list 1, 2, 5, 10, ...:
(let ((naturals (cons 0 (map (+ 1) naturals))) (delta 1))) (map (lambda (x) (+ (* x x) delta) naturals))
So what can you do with Alef?
Here's a small program that uses the above definitions of list and map to compute all permutations of a given list:
(define append (xs nil) xs) (define append (nil ys) ys) (define append ((cons x xs) ys) (cons x (append xs ys))) (define concat (nil) nil) (define concat ((cons x xs)) (append x (concat xs))) (define insertions (x nil) (cons (cons x nil) nil)) (define insertions (x (cons y ys)) (cons (cons x (cons y ys)) (map (cons y) (insertions x ys)))) (define permutations (nil) (cons nil nil)) (define permutations ((cons x xs)) (concat (map (insertions x) (permutations xs)))) (define start () (let ((list (cons 1 (cons 2 (cons 3 (cons 4 nil)))))) (permutations list)))
You can find more examples here.