[heresy-devel] Heresy lazy-list classes and subclasses (no-html resend)

[Matt Lamari]

(sorry about the html in the last post)


This post will refer to Heresy version 0.0.3, although the lazy-list 
classes themselves did not vary from 0.0.1->0.0.3

At present, there are naming conventions that may not be perfect for the 
situation (reflecting an evolution more than a destination).

It bears mentioning that the lazy-list class types were deliberately not 
documented in the API - and that they currently represent performance 
optimization hints (for memory or CPU) to code for various functions 
that accept lazy-lists.

At the root of the lazy-list class hierarchy is *lazy-list*.  In 
essence, it contains a function reference that, when called, returns the 
first value + the function for the next link.  (In 0.0.3 this has 
expanded to 2 functions, each of which returns a /traversal-result/ 
struct; but that's the basic idea).  This has currently proven 
sufficient for both fixed-container sequences and lazy/infinite 
sequences.  All lazy-lists support this functionality without exception, 
and are acceptable to any of the functions in the library that will 
accept a list.

*lazy-list-list-based* - a lazy-list representing a common-lisp "proper 
list", based upon conses, nil-terminated - and the list itself is stored 
in slot /list-head/.  Code that creates a lazy-list will tend to create 
this when the input is a proper list.  Code that accepts a list will 
often typecase to this, short-circuiting the more involved calls of the 
lazy-list view of the data structure in favor of using the /list-head/.  
These can be found by searching /heresy.lisp/ for /lazy-list-list-based/ 
- /foldl// is a good example, it skips a rather involved operation upon 
the lazy-list in favor of a call to /common-lisp:reduce/.

*lazy-list-known-empty* is of marginal utility; but represents a 
guaranteed empty list.  (Note - a list may, upon traversal, have no 
contents - it is not required that a list be of this type just because 
it's empty, this is only a hint for certain situations where it is known 
to be true).

*lazy-list-with-persistence *and *lazy-list-with-some-persistence* - the 
distinction represents a judgement call between levels of lazy-list that 
do not warrant caching.  The former basically represents either a direct 
connection to a fixed container or subset of same (or a cached 
/read-point/, which, once evaluated, keeps its values), the latter may 
represent a lazy-list deemed to be a very close link to the former.  
*lazy-list-with-some-persistence* is used as a cue to functions such as 
/memoized//, so that they can avoid the redundancy of caching something 
that the lazy-list's reference will keep alive via a fixed container or 
another cache.  Lazy-lists based upon arrays are of type 
*lazy-list-with-persistence*, even though the underlying array is never 
exposed.

*lazy-list-read-point-based* .  This lazy-list is based upon a retained 
/read-point/ (exposed in the class's slot).  I'm sure the /read-point/ 
has a better name out there - basically, consider it like a /cons/ cell; 
but with its /value/ and /next/ changing to valid values only when first 
needed (this is where thread-safety would come into play).  These are 
not always ideal to use - Keeping a head reference to a chain of these 
may bloat out the static memory footprint in solutions where a rescan of 
the list is not required - this is where a lot of lazy/caching solutions 
can get into memory trouble, which is part of why the /read-point/ 
element is a tool, not the fundamental building block of a lazy-list.  
The clichéd self-referencing Fibonacci example really highlights this - 
caching is mandatory between the successive elements; but the holder of 
the full sequence can not keep a reference to it without a growing 
memory footprint (the example in the doc maintains the distinction).
At any rate, this class serves two purposes - to provide the 
*lazy-list-with-persistence* cue, and to make /read-point/ available to 
the /read-point-built/ function (which can just take it from the class - 
the alternative being a new/parallell cached list with associated memory 
bloat and redundant traversals).