Databases
StackOverflow2013
Postsdbo
POEfficient incremental hash computation during program interpretation
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POEfficient incremental hash computation during program interpretation
    primarykey
    data
    text
    <p>I'd like to write a <strong>recursively memoizing Scheme interpreter</strong>. At any point during evaluation, the interpreter should be able to detect when it receives as arguments a pair of expression and environment that it has previously seen.</p> <p><strong>Plain memoization of <code>eval</code> and <code>apply</code> is inefficient</strong>. It would require looking up the arguments in a hash table on every call of <code>eval</code>/<code>apply</code>, which would require walking the entire (possibly big) arguments on hash table matches.</p> <p>For example, assume that the interpreter evaluates the program</p> <pre><code>(car (list A)) </code></pre> <p>where A evaluates to a big object. When the interpreter evaluates the application <code>(list A)</code>, it first evaluates <code>list</code> and <code>A</code> individually. Before it applies <code>list</code> to <code>A</code>, it looks up in its hash table whether it has seen this application before, walking the entire <code>A</code> object to compute a hash. Later on, when the memoizing interpreter applies <code>car</code> to the list containing A, it computes a hash for this list which again involves walking the entire A object.</p> <p>Instead, I want to build an interpreter that <strong>incrementally builds up approximately unique hashes</strong>, avoiding recomputation where possible and providing a guarantee that collisions are unlikely. </p> <p>For example, one could recursively extend each object that the interpreter operates on with the MD5 of its value, or, if it is a compound object, with the MD5 of its component hashes. An environment might store the hash for each of its variable/value entries, and the hash of the environment might be computed as a function of the individual hashes. Then, if an entry in the environment changes, it is not necessary to rewalk the entire environment to compute the new hash of the environment. Instead, only the hash of the changed variable/value pair needs to be recomputed and the global hash of the set of entry hashes needs to be updated.</p> <p><strong>Does there exist related work on incrementally building up approximately unique hashes, in particular in the context of recursive memoization and/or program evaluation?</strong></p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USAndreas
    1. USAndreas
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POEfficient incremental hash computation during program interpretation
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POEfficient incremental hash computation during program interpretation
      1. This table or related slice is empty.
      1. VTUpMod
    1. COBut how would such an interpreter evaluate `(eq? (list) (list))` ?
      singulars
      1. POEfficient incremental hash computation during program interpretation
      1. US6502
    2. COIf you take the meaning of `eq?` to be "Are two objects stored at the same memory address?", then it should return `true`.
      singulars
      1. POEfficient incremental hash computation during program interpretation
      1. USAndreas
    3. COSorry... i meant `(eq? (list 'A) (list 'A))`. The form `(list ...)` is not a list object, but a list **builder**. A list object would be `'(A)`. I don't understand your example of call that could save time unless you are of course talking about higher level reasoning that know that the combination `(car (list <a> <b> <c>))` can be optimized to `<a>` without changing semantic if the other two expressions are side-effect free. A `list` call in general returns something different each time. If you want to introduce the idea of "pure" functions that can be memoized then `list` is not one of them.
      singulars
      1. POEfficient incremental hash computation during program interpretation
      1. US6502
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload