Lambda the Ultimate

inactiveTopic De-biforestation
started 12/8/2002; 6:01:05 AM - last post 12/9/2002; 11:47:43 PM
Ehud Lamm - De-biforestation  blueArrow
12/8/2002; 6:01:05 AM (reads: 2421, responses: 3)
Deforestation is usually defined as the elimination of an intermediate data structure between a single producer and a single consumer. Jorge Adriano showed an interesting example of one producer feeding two independent consumers. The two streams of data are mutually dependent. Furthermore, the rate of production is non-uniform: Generating an element in one stream may require generating trillion items in the other stream. If the first consumer is being evaluated, that consumer causes the evaluation of the producer until the latter yields an item. The trillion of items incidentally produced in the other stream have to be stored somewhere. In more OS-centric terms, the evaluator can't generally reduce two expressions in parallel. If it chooses one stream consumer, the other consumer is set aside. While the first stream consumer "waits" for a value, the second stream consumer is "blocked", and hence the corresponding stream must be buffered, sometimes at great expense.

A cool (and practical) example of program transformation.

But why can't the optimizer do such transformation for us?

Warning: If you are out of practice, the Haskell notation may be a bit taxing.

Posted to functional by Ehud Lamm on 12/8/02; 6:04:19 AM

Oleg - Re: De-biforestation  blueArrow
12/9/2002; 1:15:43 PM (reads: 853, responses: 2)
Actually, it is possible to perform certain kinds of deforestation/fusion automatically. In fact, the Glasgow Haskell Compiler already does that. For references, see

Josef Svenningsson Shortcut fusion for accumulating parameters & zip-like functions ICFP'02

especially the first few paragraphs of the introduction and the 'Related Works' section.

Was my Haskell code really so complex? I defined only one infix operator, and used monad only once, at the very end...

Ehud Lamm - Re: De-biforestation  blueArrow
12/9/2002; 1:19:59 PM (reads: 903, responses: 0)
Oh, deforestation research is all the rage...

re your Haskell code: When I first read it I failed to notice that you defined the operator, which confused me quite a bit. When I discovered to definition things became much clearer.

Anyway, my experience is that getting used to reading Haskell can take awhile.

Ehud Lamm - Re: De-biforestation  blueArrow
12/9/2002; 11:47:43 PM (reads: 1012, responses: 0)
This overview of GHC is worth a look. See the bibliography for several references about deforestation. [Did we mention this paper before? I think it should be mentioned on the home page.]