mikpe@IDA.LiU.SE (Mikael Pettersson) (11/09/90)
I'd like to ask those of you who have implemented compilers using
_lazy_ functional languages a couple of questions:
Did you make significant use of the laziness of the implementation
language, i.e. were there parts the the compilers that
would have been considerably more difficult to implement
or less efficient had the impl. language been applicative?
If so, what were those parts and for what kinds of object
languages (the input lang. to the compilers) did this occur?
email replies ==> I'll do a followup in, say, 10 days from now.
/Mike
--
Mikael Pettersson, Dept of Comp & Info Sci, University of Linkoping, Sweden
email: mpe@ida.liu.se or ...!{mcsun,munnari,uunet,unido,...}!sunic!liuida!mpemikpe@IDA.LiU.SE (Mikael Pettersson) (11/24/90)
In article <1990Nov8.175822.19565@ida.liu.se> I wrote: >I'd like to ask those of you who have implemented compilers using >_lazy_ functional languages a couple of questions: > > Did you make significant use of the laziness of the implementation > language, i.e. were there parts the the compilers that > would have been considerably more difficult to implement > or less efficient had the impl. language been applicative? > If so, what were those parts and for what kinds of object > languages (the input lang. to the compilers) did this occur? > >email replies ==> I'll do a followup in, say, 10 days from now. Well, that was two weeks ago. In the mean time, I have received five email comments about this topic. They are included here (in slightly edited versions). At the end of this message you will find my own "conclusion". ================================================================ From: rej@ukc.ac.uk I've built a compiler for an intermediate language (something like FLIC) in Miranda. The abstract machine is essentially a G machine. Off the top of my head, I recall using laziness for the following: 1) Generating Unique Labels Suppose I want to translate, say, an application Trans labelsupply (App e1 e2) = Trans labelsupply2 e2 ++ Trans labelsupply1 e1 ++ [MKAP] where labelsupply1, labelsupply2 = split labelsupply The labels in labelsupply1 and labelsupply2 must be distinct. One way would be to pass the new name supply as well as the G code back. However I chose to do it differently. "labelsupply" is an infinite tree of distinct labels -- when I need a new labelsupplies I simply split this tree in half. 2) Of course laziness isn't essential for the above problem. In the back end of the compiler I simulated the G machine stacks. This meant passing simulated stacks in one direction, and usage information in the other. In Miranda this was simple; in a strict language it would be harder. See Johnsson's thesis on the Gmachine for details. ================================================================ From: beemster@fwi.uva.nl (Marcel Beemster) About your question of implementing a compiler in a lazy functional language. I did write a compiler in a lazy functional language called stoffel. The language is very small, but large enough to write its own compiler in itself. I use a bootstrap compiler that compiler stoffel into FLIC, which is itself compiled into C. In the non-bootstrap compiler, which compiles stoffel into C and which is itself written in stoffel, I make extensive use of attribute grammars. To implement these the laziness of stoffel is used. Without this laziness, no use of attribute grammars could have been made. As for results, not universally positive. Although attribute grammars are quoted as being ideal for writing compilers, the code easily gets quite hairy. I spent many days rewriting code until I was satisfied with clarity. A second problem may have to do with the underlying implementation. When I try to compile the expression: f (g "abcdefghikjlasuhshafkjhkgskdj"), something with a large string that is, the compiler runs out of memory. This may have to do with the effects described in: %A Philip Wadler %T Fixing Some Space Leaks with a Garbage Collector %K FPL %X Software-practice and expreience, V17#9, 1987 in combination with the use of attribute grammars (laziness), but I have not been able to determine where the problems come from yet. ================================================================ From: Nigel Perry <np@doc.imperial.ac.uk> Here at Imperial Keith Sephton & I wrote the Hope+C compiler in Hope+C - at the time Hope+C was call-by-whnf so the lazy purists who like evaluating 1/0 will complain... However this makes no real difference, and anyway there is now a lazy version (just changed the abstract machine, compiler still the same code). The only real use of laziness was in one place where I needed a supply of unique identifiers, so I used a non-strict list - most of our unique identifiers are supplied by the symbol table WITHOUT using laziness I just didn't have access to the symbol table at that point in the code and wasn't prepared to change it so I did. You don't need laziness to compile a lazy language, all the other laziness in the compiler is "accidental" i.e. the language just supplied it. /* Controversial... */ Trouble with laziness is that in most implementations it costs you a lot but you rarely need it. Of course there are times when you do (before I get flamed) but most of this is non-strict construction i.e. call-by-whnf. /* safe again */ ================================================================ From: Kevin Hammond <kh@cs.glasgow.ac.uk> The following is forwarded from Simon Peyton Jones. Kevin ----- Begin Included Message ----- Subject: Re: Lazy implementation question Date: Mon, 12 Nov 90 09:26:22 +0000 From: Simon L Peyton Jones <simonpj> I once wrote a code generator in LML, for LML. It made essential use of lazy evaluation to mix together several passes. The code generator was quite large: about 3000 lines of LML. For example, at the beginning of each basic block there is a test for heap exhaustion, which depends on how much heap will be consumed by the basic block. This could be precomputed by an earlier pass, but that is rather error prone: the earlier pass has to guess how much heap will actually be allocated by the instructions generated in later pass. In the code gen I wrote, the very same piece of code that emits the instruction also increments the heap usage. This turned out to be a really nice way to write the code generator, except for one thing: it is easy to introduce a strictness bug. In its most obvious form, consider if e then (b,e1) else (b,e2) The first component of the result is always b, but if e depends on b the value of the expression is bottom. I found a number of bugs of this sort, but far more heavily disguised. Simon ----- End Included Message ----- ================================================================ From: schiex@irit.irit.fr (Thomas Schiex CAP SESA - TDV) I personnaly wrote a compiler for a lazy dialect of Lisp (called HELP) in HELP, and indeed used lazyness for "programming with unknowns" to compute closure strictness.. but this was an aesthetic choice... I think that there is no necessity to use a lazy language for writing lazy language compilers... ================================================================ My interpretation of these comments is that laziness most of the time isn't essential. Convenient perhaps, but not an absolute must. The attribute grammar example (Marcel Beemster) and the lazy, functional version of "backpatching" (Peyton Jones' compiler) use laziness in a more substantial way. Regarding attribute grammars: my impression is that most AG users are content with the evaluation order restrictions imposed by the various non-lazy AG systems out there. As for the "backpatch" application: well, that could be done by adding an extra pass computing the information before sending the basic block to the binary code generator. (Not quite as neat of course) If the language has side-effects (my apologies to the purists for even mentioning this abomination) a simple assignment would do the job. My thanks to the people who responded to this query. /Mike -- Mikael Pettersson, Dept of Comp & Info Sci, University of Linkoping, Sweden email: mpe@ida.liu.se or ...!{mcsun,munnari,uunet,unido,...}!sunic!liuida!mpe