Record Details

There and Back Again

BRICS Report Series

View Archive Info
 
 
Field Value
 
Title There and Back Again
 
Creator Danvy, Olivier
Goldberg, Mayer
 
Description 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.
 
Publisher Aarhus University
 
Contributor —
 
Date 2005-01-11
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
—
 
Format application/pdf
 
Identifier https://tidsskrift.dk/brics/article/view/21869
10.7146/brics.v12i3.21869
 
Source BRICS Report Series; No 3 (2005): RS-3 There and Back Again
BRICS Report Series; No 3 (2005): RS-3 There and Back Again
1601-5355
0909-0878
 
Language eng
 
Relation https://tidsskrift.dk/brics/article/view/21869/19296
 
Rights Copyright (c) 2015 BRICS Report Series