This is a codebase for experimenting with lazy specializing interpretation
strategies.  

Some context about why you should care (by djointpear):

* DSLs are powerful tools: write someone a program and you solve their problems
  for a day; write them a DSL and they can solve their own damn problems
  (sigfpe).
* One (the common?) approach in DSL implementation is to write an interpreter.
  The problem is that DSLs stacked one on top of another increase running times
  exponentially, the exponent being the number of DSLs. This helluva
  discourages deep DSL stacks.
* "Complete laziness", as defined in Thyer's thesis, holds the tantalizing
  promise of only constant-time interpretative overhead because of its partial
  evaluation property. Instead of each DSL being a multiplicative slowdown,
  it's now only an additive slowdown.
* Luke "luqui" Palmer has written code that demonstrably scales linearly in the
  number of DSLs, the toy DSL here being a lambda calculus self-interpreter.
* Partial evaluation is interesting in its own right. Witness the invited talk
  by Lennart at PEPM 2010 -- yes, a whole conference is devoted to the topic
  every year.

Currently implemented are:

    * Thyer's complete laziness semantics (sans memoization)
    * Bottom up beta substitution

To try it out, use measure.pl, like so:

    # This doesn't work since this code is in mid-rewrite.  See the branch 
    # `stack-demo` for the last time the code worked this way.
    % perl measure.pl bubs 5

This runs the incredibly simple program 3*3 using the bubs (bottom up beta
substitution) interpreter at levels of interpretation from 0 to 5.  So, for
example, at the 3rd level, it is running an interpreter running an interpreter
running an interpreter running 3*3.  It is very likely you will not be patient
enough for this to finish -- bubs does not pass the stacks of interpreters
test.

The other options are "thyer" and "ref".  "ref" is a simple embedding of HOAS
into Haskell, running (asymptotically) at the speed GHC would run this code. 
This also fails the test, getting exponentially slower with each level; waiting
for level 5 requires deep patience.

Here you can see thyer kick the pants off the other two.  It executes a
stack of interpreters 100 high in just over half a second. (!)