Ex10: Call-By-Need Expression Result Caching vs. Memoization

schnubbes
Neuling
Neuling
Beiträge: 7
Registriert: 16. Okt 2013 18:08

Ex10: Call-By-Need Expression Result Caching vs. Memoization

Beitrag von schnubbes »

Hey.

In task 2 of exercise 10 we should evaluate the given expression with Call-By-Need (Expression Result Caching) and Call-By-Need (Memoization), but I'm not sure of the difference of both.
In the slides (V09, slide 6) it says:
"- Call by need is a memoized version of call-by-name.
- An argument is evaluated at most once..."

My guess is that the evaluated argument has to be saved somewhere if it is only evaluated at most once.
Is the differnce between both, that the evaluated expression is saved in a different structure? For caching in a cache and for memoization in a lookup table (or something similar)?

Cheers.
Zuletzt geändert von schnubbes am 26. Aug 2015 23:34, insgesamt 1-mal geändert.

Talaron
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 26. Apr 2012 11:34

Re: Ex10: Call-By-Need Expression Result Caching vs. Memoiza

Beitrag von Talaron »

The different concepts were already discussed and explained last year.

kbraden
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 15. Okt 2010 20:35

Re: Ex10: Call-By-Need Expression Result Caching vs. Memoiza

Beitrag von kbraden »

The explanation is not clear to me.

From what I understand:

Expression Result Caching caches bound expression results and discards them when execution leaves their scope, while memoization globally remembers function results (but no bound expression results). Is this correct?

Talaron
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 26. Apr 2012 11:34

Re: Ex10: Call-By-Need Expression Result Caching vs. Memoiza

Beitrag von Talaron »

Your explanation is correct.

lkbaerenfaenger
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

Re: Ex10: Call-By-Need Expression Result Caching vs. Memoiza

Beitrag von lkbaerenfaenger »

Is it correct to say that "Expression Result Caching" behaves exactly like our interpreter with EClosures and caches? I am asking because in that interpreter, all expressions that somehow end up in the store are being put in EClosures and therefore are all being cached. This would also include values that are being pointed at by, say, boxes. All previous explanations, however, only mention that the 'namedExpr's of 'Let' bindings are being cached, nothing else.

Best
Lucas

Talaron
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 26. Apr 2012 11:34

Re: Ex10: Call-By-Need Expression Result Caching vs. Memoiza

Beitrag von Talaron »

Well, our lazy interpreter is stateless and therefore only needs to cache Let-bindings. But you are right that in general, everything that is stored in the environment/store is cached by Expression Result Caching (in contrast to Memoization where basically everything ever evaluated is cached since almost every expression can be considered as function calls in functional languages). State however brings other issues for caching as cached values, for example for boxes, may get invalidated (see the reactive programming exercise).

Antworten

Zurück zu „Archiv“