|
There and Back Again
Olivier Danvy
March 2002 |
Abstract:
We present a programming pattern where a recursive function
traverses a data structure--typically a list--at return time. The idea is
that the recursive calls get us there (typically to a base case) and the
returns get us back again while traversing the data structure. We name
this programming pattern of traversing a data structure at return time
``There And Back Again'' (TABA).
The TABA pattern directly applies to computing a symbolic convolution. It also synergizes well with other programming patterns, , dynamic programming and traversing a list at double speed. We illustrate TABA and dynamic programming with Catalan numbers. We illustrate TABA and traversing a list at double speed with palindromes and we obtain a novel solution to this traditional exercise. A TABA-based function written in direct style makes full use of an Algol-like control stack and needs no heap allocation. Conversely, in a TABA-based function written in continuation-passing style, the continuation acts as a list iterator. In general, the TABA pattern saves one from constructing intermediate lists in reverse order Available as PostScript, PDF, DVI. |