Alef Lazily Evaluates Functions


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:

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

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.