ml-w-0.1: Minimal ML language to to demonstrate the W type infererence algorithm.

Portabilityportable (GHC, Hugs)
Safe HaskellSafe-Infered




This module defines some datatypes to represent a minimal ML-like language, plus parsing and pretty-printing functions.

The syntax is:

program     ::= declaration ';' program | expression
declaration ::= id '=' expression ';'
id          ::= [a-zA-Z][a-zA-Z0-9_]*
ids         ::= id+
expression  ::= id
             |  '(' '\' ids . expression ')'
             |  '(' expression expression ')'
             |  '(' 'let' id '=' expression 'in' expression ')'
             |  '(' fix id . expression ')'

We'll omit parenthesis in the usual way - a b c is equivalent to (a b) c.


s = \ x y z . x z (y z);
k = \ x y . x;
i = \ x . x;
k i;


Abstract syntax tree

type Id = StringSource

An identifier (predictably a String).

data Expr Source

Data type representing lambda-calculus expressions.


Var Id

A variable.

Lam Id Expr

A lambda abstraction.

App Expr Expr

An expression applied to another.

Let Id Expr Expr

Polymorphic let.

Fix Id Expr

Fixed point combinator (bye bye normalization).


type Decl = (Id, Expr)Source

A declaration (binds a certain expression to a variable). We add this abstraction on top of let so that we can write programs more easily (leaving let for local declarations).

data Program Source

A Program is a list of declaration and an expression representing what the program does. Each declaration can use previous declarations only (no mutual recursion).


Program [Decl] Expr 


Pretty printing