Andrew Cooke: C[omp]ute

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
to this page - http://www.cs.pdx.edu/~sheard/

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

Started Reading This

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
within Haskell.

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
readership.  References have been omitted.

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

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
the "layer of interpretive overhead" that degrades performance. 
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
encode statements about the type of values inside standard (ish) Haskell
datatypes.  For example, you culd imagine a list datatype that included,
in each "cons cell" not just the list item, but the length of the list.

In practice the numbers are represented as Church Numerals -
http://en.wikipedia.org/wiki/Church_numeral - and you need a lot more
infrastructure than that.  For example, you need to be able to test
whether two of these "embedded types" are equal.  It turns out that you
can get equality via "forall" (at this point I realise I didn't completely
understand this, so will shut up before I say something stupid - hope you
get the idea).

Andrew

Comment on this post

C[omp]ute

Personal Projects

Last 100 entries

General Algebraic Data Types (GADTs)

Started Reading This

Staged Interpreter

Chapter 4