Affiliations: BRICS*, Department of Computer Science, University of
Aarhus, IT-parken, Aabogade 34, DK-8200 Aarhus N, Denmark. danvy@brics.dk | Department of Computer Science, Ben Gurion University,
Be'er Sheva 84105, Israel. gmayer@cs.bgu.ac.il
Note: [] Address for correspondence: BRICS, Department of Computer
Science, University of Aarhus, IT-parken, Aabogade 34, DK-8200 Aarhus N,
Denmark
Abstract: We present a programming pattern where a recursive function defined
over a data structure traverses another data structure at return time. The idea
is that the recursive calls get us 'there' by traversing the first data
structure and the returns get us 'back again' while traversing the second data
structure. We name this programming pattern of traversing a data structure at
call time and another data structure at return time "There And Back Again"
(TABA). The TABA pattern directly applies to computing symbolic convolutions
and to multiplying polynomials. It also blends well with other programming
patterns such as 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. Finally, through a variety of tree
traversals, we show how to apply TABA to other data structures than lists. 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 and recursively
defined over a data structure (traversed at call time), the continuation acts
as an iterator over a second data structure (traversed at return time). In
general, the TABA pattern saves one from accumulating intermediate data
structures at call time.
Keywords: Recursive programming, continuations, defunctionalization, TABA
