lazy data structures

[GoogleCodeExporter]

This is a moderately-sized project which I see having three phases.

First, add support for sites to create lazy cells. These are like the
futures produced by <x< but are first-class, so can be passed to sites (and
stored in data structures) without forcing them. To ensure a consistent
semantics, they are explicitly forced with x? (= x.read()).

Second, add support for sites to create lazy lists, sometimes called
streams. (Lazy lists can be implemented in terms of lazy cells, but it may
be more straightforward to implement them as their own primitive type.)
Lazy lists can be deconsed like lists (i.e. they are a ListLike value),
since (:) and ([]) destructors are site calls which can perform computation
before returning. It's important that if the head of a stream is no longer
referenced, it can be collected, so a stream can be generated and consumed
in O(1) live memory.

Finally, add support for constructing both lazy cells and lists in Orc.
This is a research problem, since it's not obvious who "owns" the Orc
computation which generates the value; can it be terminated?

Original issue reported on code.google.com by adrianqu...@gmail.com on 18 Apr 2009 at 3:15

[GoogleCodeExporter]

Original comment by amsh...@gmail.com on 21 Feb 2010 at 10:12

[GoogleCodeExporter]

Original comment by jthywissen on 27 Mar 2011 at 1:21

[GoogleCodeExporter]

Lazy data structures can be implemented by the user using thunks and other 
classic tricks from strict functional programming. Furthermore, making futures 
first-class causes serious problems in the formal calculus.

Original comment by dkitc...@gmail.com on 25 Apr 2011 at 6:28

• Changed state: WontFix