[kragen@canonical.org: Re: PEGs]

[Dave Long]

> One approach to implementing this, which I've also been thinking of  
> for
> maintaining Bicicleta intermediate results, would be to use a value- 
> weak
> hashtable for the memoization table, along with a garbage collector.
> Any value that is needed again while it's still in the nursery will  
> not
> need to be recomputed, but most values will be reaped because at the
> time of the next minor collection, the only reference to them will  
> be in
> the value-weak hashtable.  A few won't be --- the ones whose values  
> are
> currently referenced from some parsing rule currently being tried ---
> and those will be promoted.
> ...
> I think this design may be useful for laziness in general, but I  
> haven't
> tried it yet, despite having come up with it a year or two ago.

A design that I'd like to try sometime would be to try an "Elephant"- 
like language, in which all values would, in principle, be  
recoverable from a logfile.  This could eliminate GC, as frequently  
used values would tend to be instantiated in a cache, and values that  
are never referenced again would cost just their portion of storage,  
presumably amortized by bulk sequential i/o patterns.

Any idea how mutation rates compare for various workloads with main  
memory and/or disk bandwidths?

-Dave