View in EDS PDF Full Text

There and Back Again.

Saved in:
Bibliographic Details
Title: There and Back Again.
Authors: Danvy, Olivier1 danvy@brics.dk, Goldberg, Mayer2 gmayer@cs.bgu.ac.il
Source: Fundamenta Informaticae. 2005, Vol. 66 Issue 4, p397-413. 17p. 2 Diagrams.
Subjects: Recursive programming, Linear programming, Data structures, Electronic data processing, Computer programming
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. [ABSTRACT FROM AUTHOR]
Copyright of Fundamenta Informaticae is the property of Polskie Towarzystwo Matematyczne and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 17545230
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: There and Back Again.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Danvy%2C+Olivier%22">Danvy, Olivier</searchLink><relatesTo>1</relatesTo><i> danvy@brics.dk</i><br /><searchLink fieldCode="AR" term="%22Goldberg%2C+Mayer%22">Goldberg, Mayer</searchLink><relatesTo>2</relatesTo><i> gmayer@cs.bgu.ac.il</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Fundamenta+Informaticae%22">Fundamenta Informaticae</searchLink>. 2005, Vol. 66 Issue 4, p397-413. 17p. 2 Diagrams.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Recursive+programming%22">Recursive programming</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+programming%22">Linear programming</searchLink><br /><searchLink fieldCode="DE" term="%22Data+structures%22">Data structures</searchLink><br /><searchLink fieldCode="DE" term="%22Electronic+data+processing%22">Electronic data processing</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+programming%22">Computer programming</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Fundamenta Informaticae is the property of Polskie Towarzystwo Matematyczne and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=17545230
RecordInfo BibRecord:
  BibEntity:
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 17
        StartPage: 397
    Subjects:
      – SubjectFull: Recursive programming
        Type: general
      – SubjectFull: Linear programming
        Type: general
      – SubjectFull: Data structures
        Type: general
      – SubjectFull: Electronic data processing
        Type: general
      – SubjectFull: Computer programming
        Type: general
    Titles:
      – TitleFull: There and Back Again.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Danvy, Olivier
      – PersonEntity:
          Name:
            NameFull: Goldberg, Mayer
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 07
              Text: 2005
              Type: published
              Y: 2005
          Identifiers:
            – Type: issn-print
              Value: 01692968
          Numbering:
            – Type: volume
              Value: 66
            – Type: issue
              Value: 4
          Titles:
            – TitleFull: Fundamenta Informaticae
              Type: main
ResultId 1