Language.ML.Syntax

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.

Example:

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

Abstract syntax tree

type Id = String

An identifier (predictably a String).

data Expr

Data type representing lambda-calculus expressions.

Constructors

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

Instances

Eq Expr

Read Expr

Show Expr

type Decl = (Id, Expr)

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

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

Constructors

Program [Decl] Expr

Instances

Eq Program

Read Program

Show Program

Parsing

parseExpr :: String -> Either ParseError Expr

parseExpr' :: FilePath -> IO (Either ParseError Expr)

parseProgram :: String -> Either ParseError Program

parseProgram' :: FilePath -> IO (Either ParseError Program)

Pretty printing

prettyExpr :: Expr -> Doc

prettyDecl :: Decl -> Doc

prettyProgram :: Program -> Doc