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
--
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss
