Safe Haskell	None
Language	Haskell98

CPSScheme

Contents

The CPS styntax
Smart constructors
Some example Programs

Description

This module defines the syntax of the simple, continuation-passing-style functional language used here, as well as some examples.

Synopsis

The CPS styntax

type Prog = Lambda Source

A program is defined as a lambda abstraction. The calling convention is that the program has one paramater, the final continuation.

newtype Label Source

Labels are used throughout the code to refer to various positions in the code.

Integers are used here, but they are wrapped in a newtype to hide them from the implementation.

Constructors

Label Integer

Instances

Enum Label Source
Eq Label Source
Num Label Source
Ord Label Source
Show Label Source

data Var Source

Variable names are just strings. Again, they are wrapped so they can be treated abstractly. They also carry the label of their binding position.

Constructors

Var Label String

Instances

Eq Var Source
Ord Var Source
Show Var Source
IsString Var Source

binder :: Var -> Label Source

The label of the Lambda or Let that bound this variable.

data Lambda Source

A lambda expression has a label, a list of abstract argument names and a body.

Constructors

Lambda Label [Var] Call

Instances

Eq Lambda Source
Ord Lambda Source
Show Lambda Source

data Call Source

The body of a lambda expression is either

Constructors

App Label Val [Val]	an application of a value to a list of arguments, or
Let Label [(Var, Lambda)] Call	it is the definition of a list of (potentially mutable recursive) lambda expression, defined for a nother call expression.

Instances

Eq Call Source
Ord Call Source
Show Call Source

data Val Source

A value can either be

Constructors

L Lambda	a lambda abstraction,
R Label Var	a reference to a variable (which contains the label of the binding position of the variable for convenience),
C Label Const	a constant value or
P Prim	a primitive operation.

Instances

Eq Val Source
Ord Val Source
Show Val Source
IsString Val Source
Num (Inv Val) Source

type Const = Integer Source

As constants we only have integers.

data Prim Source

Primitive operations. The primitive operations are annotated by labels. These mark the (invisible) call sites that call the continuations, and are one per continuation.

Constructors

Plus Label	Integer addition. Expected parameters: two integers, one continuation.
If Label Label	Conditional branching. Expected paramters: one integer, one continuation to be called if the argument is nonzero, one continuation to be called if the argument is zero ("false")

Instances

Eq Prim Source
Ord Prim Source
Show Prim Source

Smart constructors

newtype Inv a Source

This wrapper marks values created using the smart constructors that are not yet finished by passing them to prog and therefore invalid.

Constructors

Inv
Fields unsafeFinish :: a

Instances

Eq a => Eq (Inv a) Source
Num (Inv Val) Source
Show a => Show (Inv a) Source
IsString a => IsString (Inv a) Source

prog :: Inv Lambda -> Prog Source

This converts code generated by the smart constructors below to a fully annotated CPSScheme syntax tree, by assigning labels and resolving references

lambda :: [Inv Var] -> Inv Call -> Inv Lambda Source

app :: Inv Val -> [Inv Val] -> Inv Call Source

let_ :: [(Inv Var, Inv Lambda)] -> Inv Call -> Inv Call Source

l :: Inv Lambda -> Inv Val Source

c :: Const -> Inv Val Source

plus :: Inv Val Source

if_ :: Inv Val Source

noProg :: a Source

Internal error value