Academic
Publications
Monadic Memoization Mixins

Monadic Memoization Mixins,Daniel Brown,William R. Cook

Monadic Memoization Mixins   (Citations: 6)
BibTex | RIS | RefWorks Download
Memoization is a familiar technique for improving the performance of programs: computed answers are saved so that they can be reused later instead of being recomputed. In a pure functional language, memoization of a function is complicated by the need to manage the table of saved answers between calls to the function, includ- ing recursive calls within the function itself. A lazy recursive data structure can be used to maintain past answers — although achiev- ing an efficient algorithm can require a complex rewrite of the func- tion into a special form. Memoization can also be defined as a lan- guage primitive — but to be useful it would need to support a range of memoization strategies. In this paper we develop a technique for modular memoization within a pure functional language. We define monadic memoization mixinsthat are composed (via inheritance) with an ordinary monadic function to create a memoized version of the function. As a case study, we memoize a recursive-descent parser written using standard parser combinators. A comparison of the performance of different approaches shows that memoization mixins are efficient for a small example.
Cumulative Annual
    • ...Mixin inheritance as been widely used in functional programming [7, 24, 18, 3], using techniques similar to that in Section 2. However, only Brown and Cook [3] have used it with explicit effects, to modularize memoization...
    • ...Mixin inheritance as been widely used in functional programming [7, 24, 18, 3], using techniques similar to that in Section 2. However, only Brown and Cook [3] have used it with explicit effects, to modularize memoization...

    Bruno C. d. S. Oliveiraet al. EffectiveAdvice: disciplined advice with explicit effects

    • ...Treatments of memoization in the unstaged setting appear to either gloss over this issue or require some refinement of syntactic equality [1, 12, 4]. Whereas that approach is usually adequate for unstaged programs, this is not the case with MSP...
    • ...Subsequently, this technique was refined and generalized as memoizing mix-ins by Brown and Cook [4]...

    Jun Inoueet al. Reasoning About Staged Programs

    • ...A nice application of inheritance to a problem of separation of concerns is given by Brown and Cook [6], who show how to approach the problem of memoization in purely functional languages using monadic memoization mixins...

    Meng Wanget al. What Does Aspect-Oriented Programming Mean for Functional Programmers?

    • ...In an earlier report [Brown and Cook 2007] we scaled our technique up to memoize a parser combinator library, but the details are beyond the scope of the current paper...
    • ...In [Brown and Cook 2007] we also applied our techniques to memoize a monadic parser so we could construct Ford’s Packrat parsers [2002] in a more modular way...

    Daniel Brownet al. Function Inheritance: Monadic Memoization Mixins

Sort by: