 De-biforestation
started 12/8/2002; 6:01:05 AM - last post 12/9/2002; 11:47:43 PM
|
|
Ehud Lamm - De-biforestation 
12/8/2002; 6:01:05 AM (reads: 2421, responses: 3)
|
|
| De-biforestation |
|
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
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
http://www.cs.chalmers.se/~josefs/publications/fusion.ps
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
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
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.]
|
|
|
|