[I2 logo] [RWTH logo] MOVES: Software Modeling and Verification
(Informatik 2)
Computer Science / RWTH / I2 / Research / AG / FP / StgCaching

Simulation of an STG-Machine with non-strict Cache

Often some functions of a program are called with the same arguments several times. Then it is useful to store arguments together with the function results to avoid repeated evaluation. This optimisation is called memoisation or caching, where in the latter case stored information may be deleted to restrict memory consumption.

Ralf Welter developed a method which enables memoisation and caching even for non-strict functional languages like Haskell without making this memoised functions strict or using only weak pointer comparisions to compare possibly unevaluated arguments. Basically, strictness information of functional closures is recorded at runtime and used to change the evaluation strategy to call-by-value and table lookup in case of repeated evaluation.

Ralf Welter implemented a simulation of the spineless tagless graphreduction machine (STG), which may be of interest in itself, and extended it by his memoisation/caching method.

Valid HTML 4.01 Strict! Valid CSS!