Taking a functional datastructure out of context

Abstract

In purely functional programming languages, operations on pointers are ruled out to guarantee referential transparency. There are language extensions that allow the programmer to write purely functional code, which can be compiled to efficient pointer operations internally. Constructor contexts in Koka are such a language extension, which has introduced a limited API that allows creating values of types which may be extended in O(1) time at the end of the structure by making use of an extra internal pointer. Such constructs remediate the inadequacy of purely functional programming to express code that is cheap and effective within imperative programming.

Currently Koka only allows creating and filling these so called constructor contexts, as the implementation is quite new to the language. But one can imagine that this kind of structure can also be pattern matched on, so that you have access to the constructor and arguments like you would with regular pattern matching. What does the language design of that feature look like? And how does it allow defining highly efficient functional datastructures?

This research specifies this new feature, and contributes the following: • Demonstrate how to implement queues with O(1) operations with them; • Define pattern matching on constructor contexts as a specification; • Prototype the implementation in a recent Koka compiler version.