Projects - Programming Languages |
Eager Haskell What is Eager Haskell? Eager Haskell is an implementation of the Haskell programming language which by default uses eager evaluation. The four widely available implementations of Haskell---ghc, nhc, hugs, and hbc---all use lazy evaluation. The design of Eager Haskell permits arbitrary Haskell programs to be compiled and run eagerly. This web page highlights some of the techniques we are using to accomplish this. An implementation of Eager Haskell for Eager Hackers will be available soon, hopefully within weeks. I've completed basically all the work and am writing up; I need to straighten out a few packaging issues before I have code that's really ready for prime time, though. Note that our parser and typechecker were advanced for 1993... We don't yet support records with named fields, nor do we provide qualified names or the stable namespace management that it entails. Both of these should not be difficult in principle to add, I just haven't had the time to do so. Support for non-standard but commonplace extensions such as multiparameter type classes and existential types doesn't conform to anyone's syntax, since most of it predates these efforts. Why Eagerness? Why use eager evaluation? There are a number of good reasons. First, eager evaluation is more intuitive. Every month there is a posting to the Haskell mailing list of the form "I wrote a tail-recursive loop, and hugs is running out of stack. This should be efficient. What's going on?" The answer is that the space behavior of lazy programs is difficult to grasp, and it can be especially frustrating to express iteration. Often explicit strictness annotations are required. This detracts severely from the declarative nature of the language. In Eager Haskell, tail-recursive computations will run in constant space just as they would in ML or C. Second, we believe eagerness is more efficient than laziness. Lazy programs aren't allowed to evaluate many expressions until it can be proven that those expressions are used. Therefore, a great deal of time is spent creating and destroying suspended pieces of computation (thunks). All too often, these computations are simple enough that it would be just as easy to evaluate them instead. Faxen and others have used static analysis to expose such opportunities for eagerness. We instead propose using eagerness everywhere, while using mechanisms which permit us to recover if our program is too eager. Finally, eager evaluation promises scalability. There are provably efficient techniques for scheduling eager programs on multiple processors. Our mechanisms for handling eagerness provide a natural way for identifying pieces of work large enough to be worth executing in parallel. At the same time, we can show that we will always make progress on the critical path of our programs. Thus, we should be able to run our programs efficiently on a shared-memory machine without the need for programmer annotations to control parallelism. This is in stark constrast to other approaches to parallelism in haskell, which require annotations to mark which computations may be speculatively evaluated, and to what degree of speculative evaluation is required. For more detail on the potential tradeoffs and advantages of Eager Haskell, see my thesis proposal. The Eager Haskell Evaluation Mechanism There's one small problem with eager evaluation of lazy code: non-termination! (Or, more generally, bottom.) Lazy programs often use idioms which define an infinite data structure; this data structure is unfolded as it is needed, and unused pieces are discarded. A simple example is the list-numbering idiom: > numberList xs = zip [0..] xs In order to cope with this problem, Eager Haskell uses resource-bounded execution. The system tracks the resource usage as a computation unfolds. If resource demands get too high (for example because we are unfolding an infinite data structure as shown above) then we fall back to lazy execution. All outstanding computations are replaced by thunks. This fallback process effectively creates an image of the stack on the heap. However, we resume execution from the bottom of the stack. Thunks further up the stack are forced only as they are needed. More important, thunks which are never needed will become garbage and can be reclaimed. Once resumed, however, a computation proceeds eagerly just as before. If we choose a constant upper bound on new resource consumption, resource-bounded execution should use at most a constant factor more space and time than lazy execution. The intuitive argument is simple: Every time we reach the resource bound, we fall back to laziness, so our space and time will increase by at most the resource bound. In practice we must set the resource bound fairly high (several hundred kilobytes, or when we're close to overflowing the stack)---the fallback mechanism is slow, and code is compiled with the basic assumption fallback is rare. This means that uncontrolled unfolding of infinite lists such as [0..] above will be quite inefficient in practice. Fortunately, such cases are comparatively easy to spot. The compiler can add laziness explicitly to uncontrolled loops, and the programmer is free to annotate the program for laziness. We expect such annotations will rarely be needed, and hope that it will be fairly obvious how they must be added when they are required. We must be a little bit careful how we re-start suspended lazy execution if we want the best possible space bounds. Frequently fallback gives rise to long chains of dependent computations. When we require the head of such a chain, we must perform all the computations in the chain. The scheduler is careful to re-start such chains from the far end. Thus, if A depends on B depends on C, we first compute C, then B, then A. By re-starting computations in this order, we avoid consuming stack space for A and B while computing C. This is vital, as chains can become too long to fit on the stack. Moreover, careful scheduling means that the underlying execution mechanism need not actually be properly tail-recursive; if the stack fills up due to tail recursion, we will simply move it to the heap and place only the most recent iteration on the stack once again. Resource-bounded computation using lazy fallback is also a natural way to schedule producer-consumer parallelism. This is a tricky problem as most computations make it difficult to identify producer and consumer in any kind of meaningful way: results produced in one place may be consumed in many different places over time, or results from many sources may be bundled together into a more complex data structure. Eagerness means that producers can operate undisturbed (and eventually in parallel). Resource bounds limit the total amount of data which is produced without requiring a notion of which resources belong to which producer. Lazy fallback means that consumers are permitted to run as resources are used up, thereby freeing them, and that producers are re-started when more data is required. One final detail must be handled specially: Error expressions. Eager execution may encounter calls to error functions and exception handlers which would not have been reached during lazy execution. This code must be treated specially: simply marking it as "lazy" is insufficient, since eager computations may force lazy thunks. Instead, we have a special class of bottom thunks which are forced only if they are found to be necessary by the scheduler when it resumes execution after fallback. These expressions are identified statically by the compiler using bottom extraction, which is also used to simplify a number of program transformations involving error-handling code. The relationship between Eager Haskell and pH Before there was an Eager Haskell, there was pH, a parallel Haskell. Both languages use eager evaluation. Both share the goal of running unannotated programs with linear speedup on a parallel machine. Both share the syntax and type system of Haskell, and use the same compiler front end. However, pH does not have a lazy fallback mechanism. There are therefore many Haskell programs which do not run correctly in pH. However, pH provides a number of mechanisms which do not exist in Eager Haskell. The most important of these is the barrier mechanism. This permits programs to detect deep termination, when all eager computations in a particular program region have executed to completion. Both pH and Eager Haskell include libraries of I- and M-structure operations, but only pH integrates them deeply into the language. In Eager Haskell such side-effecting constructs must be used with care, normally through a (still-unwritten) monadic interface. Thus the two languages have complementary, but somewhat different, purposes. |
