[TYPES] Combining lazy and eager evaluation of terms

[Jan-Willem Maessen - Sun Labs East]

Tim Sweeney wrote:
> In an attempt to combine some of the benefits of lazy and eager
> evaluation, I have implemented a language with an evaluation strategy
> which is strict with respect to divergence, but performs lazy evaluation
> on certain intermediate subterms to allow a more expressive use of
> recursion.

Two different projects have implemented semantically-correct Haskell 
with eager evaluation.  The first of these was my Ph.D. thesis, Eager 
Haskell:
   http://csg.lcs.mit.edu/~earwig/thesis.html
This page also includes a link to the short paper I prepared on my 
implementation for the 2002 Haskell Workshop.

The second implementation was based on GHC, and was done by Robert 
Ennals at Cambridge University.  He and Simon Peyton Jones published 
the paper "Optimistic evaluation: an adaptive evaluation strategy for 
non-strict programs" in ICFP 2003:
   http://doi.acm.org/10.1145/944705.944731

In both cases we evaluate Haskell using resource-bounded eager 
evaluation: run eagerly until you run into something uncomputed (in 
which case create a thunk) or until some resource bound is exceeded 
(in which case create a thunk).  Force thunks as necessary during 
eager evaluation.

The difference between our two schemes was that mine used a static 
strategy which didn't differentiate between suspension sites.  This 
meant that (say) each unfolding of an infinite list would alwys run 
for a large number of steps before reaching a new resource bound. 
Rob's work dynamically modified call sites which caused resource 
bounds to be exceeded, so that particular problem areas were throttled 
explicitly.  Both techniques do well for code that is mostly eager; 
it's only when lazy infinite (or extremely large) data structures are 
involved that things get tricky.  I hold out hope that a slightly 
better set of static heuristics would avoid the problems with my 
scheme, but I've moved on to entirely new problems these days.

Absent the time bounds, it sounds like our work is very similar to the 
mechanisms you have been exploring.  The time and space bounds make 
things a bit more complicated than I would at first have imagined, but 
yield a semantics which is entirely equivalent to that of a lazy 
implementation.

-Jan-Willem Maessen
  jmaessen at alum.mit.edu