文章基本信息

标题：There and Back Again
本地全文：下载
作者：Olivier Danvy ; Mayer Goldberg
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：2002
卷号：9
期号：12
出版社：Aarhus University
摘要：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, e.g., 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. See also BRICS-RS-05-3.