## General Algebraic Data Types (GADTs)

From: "andrew cooke" <andrew@...>

Date: Fri, 10 Feb 2006 10:50:34 -0300 (CLST)

As is probably obvious I'm on some kind of Curry-Howard trip -
http://en.wikipedia.org/wiki/Curry-Howard_correspondence

Anyway, turns out that this is all related to GADTs.  Paul Snively gave
some links at lambda - http://lambda-the-ultimate.org/node/1293 - that led

Amongst the link on that pages is this thesis -
http://www.cs.rice.edu/~pasalic/thesis/body.pdf - which at first glance
looks  like a very good read.

Andrew

From: "andrew cooke" <andrew@...>

Date: Sun, 25 Jun 2006 09:17:28 -0400 (CLT)

Last night (we now have a printer that, with psnup, will produce legible
4-up double sided pages, so a 240 page thesis takes only 30 sheets).  Am
currently on page 27 and it is very good indeed.  It's pretty old - 1995 -
so I'm curious to what extent the ideas it develops have been adopted

Andrew

### Staged Interpreter

From: "andrew cooke" <andrew@...>

Date: Mon, 26 Jun 2006 10:26:26 -0400 (CLT)

The following is from pages 29 and 30 or Emir Pasalic's thesis "The Role
of Type in Meta-Programming" (link in previous post on this thread).  I've
added some comments in square brackets to clarify points for a wider

------------

An Untyped Interpreter
======================

We begin by reviewing how one writes a simple interpreter in an untyped
language.  For notational parsimony, we will use Haskell syntax but
disregard types.  An interpreter for a small lambda language [one that
defines and evaluates functions] can be defined as follows:

data Exp = I Int | Var String | Abs String Exp | App Exp Exp

[This defines a Haskell type Exp as one of the alternatives on the right.
For each alternative, the first word is a "tag" that identifies the
alternative, and subsequent words and the types that are contained.  So an
"Exp" can be "I followed by an integer" or "Var followed by the variable
name as a string" or...  App is function application (evaluation) and Abs
isvariable abstraction (function definition).]

eval e env =
case e of
I i     => i
| Var s   => env s
| Abs s e => (\v => eval e (ext env s v))
| App f e => (eval f env) (eval s env)

[That's a simple evaluator with rules for the different types above.
"env" is some kind of environment that returns variable values and "ext"
extends the environment to include an additional named value (where a
value is a general expression).  The "\x => " syntax defines a function(x)
- it's worth looking at that carefully, because what it does is pretty
neat.]

This provides a simple implementation of object [the object language is
the language being interpreted; not necessarily the same as the language
this code is written in] programs represented by the datatype Exp.  The
function eval evaluates e (an Exp) in an environment env that binds free
variables in the term to values.

This implementation suffers from a severe performance limitation.  If we
were able to inspect the result of applying eval, such as (eval (Abs "x"
(Var "x")) env0) [evaluate the definition of the function f(x) = x] we
would find that it is equivalent to

(\v -> eval (Var "x") (ext env0 "x" v)).

This term will compute the correct result, but it contains an unevaluated
recursive call to eval.  This problem arrises in both call-by-value and
call-by-name languages, and is one of the main reasons for what is called
Fortunately, this problem can be eliminated using staging.

Staging the Untyped Interpreter
===============================

Staging annotations partition the program into (temporally ordered) stages
so that all computation at stage n is performed before any computation at
stage n+1.  Brackets <> surrounding the expression lift it to the next
stage (building code).  Escape ~ drops its expression to a previous stage.
The effect of escape is to splice pre-computed code values into code
expressions that are constructed by surrounding brackets.  Staging
annotations change the evaluation order of programs, even evaluating under
lambda abstraction.  Therefore they can be used to force the unfolding of
recursive calls to the eval fucntion at code generation time.  Thus, by
just adding staging annotations to the eval function, we can change its
behaviour to achieve the desired operations semantics:

eval' e env =
case e of
I i     => <i>
| Var s   => env s
| Abs s e => <\v => ~(eval' e (ext env s <v>))>
| App f e => <~(eval' f env) ~(eval' e env)>

Now applying eval' to (Abs "x" (Var "x")) in some environment env0 yields
the result

(\v => v)

There are no recursive calls to eval' since the abstraction case of eval'
uses escape to evaluate the body of the function "under the lambda".

### Chapter 4

From: "andrew cooke" <andrew@...>

Date: Tue, 27 Jun 2006 11:53:12 -0400 (CLT)

Read chapter 4 last night (skipped 3, which was technical).  Again, very
interesting - had the flavour of C++ template "tricks".  The idea was to
Andrew