Home

Breaking the Complexity Barrier of Pure Functional Programs with Impure Data Structures

Breaking the Complexity Barrier of Pure Functional Programs with Impure Data Structures by Pieter Wuille and Tom Schrijvers:

Pure functional programming language offer many advantages over impure languages. Unfortunately, the absence of destructive update, imposes a complexity barrier. In imperative languages, there are algorithms and data structures with better complexity. We present our project for combining existing program transformation techniques to transform inefficient pure data structures into impure ones with better complexity. As a consequence, the programmer is not exposed to the impurity and retains the advantages of purity.

This paper is along the same lines a question I asked a couple of years ago. The idea here is to allow programming using immutable interfaces, and then automatically transform it into a more efficient mutable equivalent.

By naasking at 2014-09-22 14:10 | Functional | Theory | other blogs | 13407 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

One source for both mutable and immutable

My experiments with lisp-interface-library suggest that you could write a single specification from which both mutable and immutable variants of a data structure would be generated. The trick is to:

1- use a pure functional language with linear logic and explicit duplication to describe the computations

2- specify for each interface function a type where inputs and outputs are annotated with regions.

You can then generate:

a- a pure interface by "upgrading" all variables to classic and dropping region annotations, and

b- a stateful interface by considering that when input and output have the same region annotation, that's the specification of a side-effect.

See my ILC2012 article "LIL: CLOS reaches higher-order, sheds identity, and has a transformative experience"

By François-René Rideau at Wed, 2014-09-24 06:16 | login or register to post comments