Introduction

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:

git clone git://gergo.erdi.hu/alef

The language

An Alef program contains two kinds of definitions: type definitions and function definitions.

Type 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.

Function definitions

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

Patterns can be one of the following:

_ matches any actual.
C p₁ p₂ ... p_n, where C is a constructor and all p_i are patterns, matches values that are constructed as (C a₁ a₂ ... a_n) where each a_i constructor argument matches p_i. 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)))

Expressions

(C e₁ e₂ ... e_n) where C is a constructor is a value with instance actuals e₁, ... , e_n.
v where v is a variable is whatever is bound by v.
(f e₁ e₂ ... e_n) where f is a function applies f to e₁, ..., e_n. When the application is evaluated, the reduction is made according to the first definition of f with a pattern matching e₁, ..., e_n.
(let ((v₁ e₁) (v₂ e₂) ... (v_n e_n)) e) introduces new variables v₁, ..., v_n to e₁, ..., e_n, e, and bounds them, respectively, to e₁, ..., e_n. 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))
```
uses let to yield the infinite list 8, 9, 8, 9, ...
(lambda (p₁ p₂ ... p_n) e) is the anonymous function with formal patterns p₁, ..., p_n 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.