evaluation strategies

LucasR
Kernelcompilierer
Kernelcompilierer
Beiträge: 474
Registriert: 9. Jun 2009 09:55

evaluation strategies

Beitrag von LucasR »

Hello together,

unfortunately I lost my notes from the exercise session 12. In exercise two, a function is given where results should be described for the following evaluation strategies:

1. Call-By-Value
2. Call-By-Name
3. Call-By-Need (Expression Result Caching)
4. Call-By-Need (Memoization)

I understand the difference between 1 and 2, but what is the difference between 3 and 4? Only 4 is defined in the slides from what I can see... :(

Thank you!
Lucas

f_jakob
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 27. Okt 2009 14:05

Re: evaluation strategies

Beitrag von f_jakob »

With memoization the cache is bound to the function. The other approach uses a cache for the thunk (expression closure).

Imagine the following piece of code in FWAE:

Code: Alles auswählen

With('f, Fun('x, _),
  Add(App('f, 23), App('f, 23)))
With memoization the result for f(23) is only computed once. The second call will lookup the result in the function cache, as it already knows the result for the argument 23.

If you however use a cache for the thunk, f(23) will be evaluated two times, as these are two different thunks and thus have different caches.

If the code is rewritten to the following:

Code: Alles auswählen

With('f, Fun('x, _),
  With('n, App('f, 23),
    Add('n, 'n)))
Then f(23) is also only computed once with thunk caching, because on the first lookup of n the thunk f(23) will be evaluated and on the second n the result will be used from the thunk cache.

Hope that makes the distinction clear.

LucasR
Kernelcompilierer
Kernelcompilierer
Beiträge: 474
Registriert: 9. Jun 2009 09:55

Re: evaluation strategies

Beitrag von LucasR »

Perfect, yes, that makes it clear. Thanks.

Antworten

Zurück zu „Archiv“