Difference between revisions of "WG211/M18Scholz"

From WG 2.11
Jump to: navigation, search
(Created page with "Arrays and streams seem to be fundamentally at odds: arrays require their size to be known in advance, streams are dynamically growing; arrays offer direct access to all of th...")
 
 
(One intermediate revision by the same user not shown)
Line 13: Line 13:
 
arrays. As it turns out, it is even possible to maintain recursive specifications as they
 
arrays. As it turns out, it is even possible to maintain recursive specifications as they
 
are typically found in a traditional stream / list-based setting.
 
are typically found in a traditional stream / list-based setting.
 +
 +
An [https://arxiv.org/abs/1710.03832 arxiv paper] as well as an implementation of an interpreter in Ocaml are available [https://github.com/ashinkarov/heh here]

Latest revision as of 02:05, 7 June 2018

Arrays and streams seem to be fundamentally at odds: arrays require their size to be known in advance, streams are dynamically growing; arrays offer direct access to all of their elements, streams provide direct access to the front elements only; the list goes on. Despite these differences, many computational problems at some point require shifting from one paradigm to the other. The driving forces for such a shift can be manifold. Typically, it is a shift in the task requirements at hand or it is motivated by efficiency considerations. In this talk, we present a basis for a unified framework for dealing with arrays and streams alike. We introduce an applied lambda calculus whose fundamental data structure is a new form of array, named "Transfinite Array". Transfinite arrays maintain properties from finite array calculi yet incorporate support for infinite arrays. As it turns out, it is even possible to maintain recursive specifications as they are typically found in a traditional stream / list-based setting.

An arxiv paper as well as an implementation of an interpreter in Ocaml are available here