Memoisation: Purely, Left-recursively, and with (Continuation Passing) Style
This work addresses the challenge of non-termination in left-recursive memoization for functional programmers, offering a pure and typed solution, though it is incremental as it builds on prior continuation passing approaches.
The paper tackled the problem of implementing memoization for left-recursive computations in functional programming without relying on mutation or explicit continuation passing style, and achieved a purely functional implementation in OCaml using a monadic interface that also allows returning compact memo table representations.
Memoisation, or tabling, is a well-known technique that yields large improvements in the performance of some recursive computations. Tabled resolution in Prologs such as XSB and B-Prolog can transform so called left-recursive predicates from non-terminating computations into finite and well-behaved ones. In the functional programming literature, memoisation has usually been implemented in a way that does not handle left-recursion, requiring supplementary mechanisms to prevent non-termination. A notable exception is Johnson's (1995) continuation passing approach in Scheme. This, however, relies on mutation of a memo table data structure and coding in explicit continuation passing style. We show how Johnson's approach can be implemented purely functionally in a modern, strongly typed functional language (OCaml), presented via a monadic interface that hides the implementation details, yet providing a way to return a compact represention of the memo tables at the end of the computation.