Home » forums » LtU Forum

Automatically Deriving Mutable Data Structures?

Suppose we have the typical immutable list, with some immutable operations:

type 'a list = Nil | Cons 'a * 'a list
let head l = match l with Nil -> raise "Error!" | Cons(x,next) -> x
let add l x = Cons(x,l)
let map f l = match l with Nil -> Nil | Cons(x,next) -> Cons(f x, map f next)
...
let update l item newitem = match l with
    Nil as cur -> cur
  | Cons(x,next) as cur ->
      if item = x then Cons(newitem, next)
      else let u = update next item newitem in 
            if u = next then cur else Cons(x, u)
let append x l = match l with Nil -> Cons(x, Nil) | Cons(x,next) -> Cons(x, append x next)
...

Is there any reason in principle we wouldn't be able to derive a mutable version automatically? At first blush, mutability seems somewhat distributive up to polymorphic parameters. Any recursive function on abstraction Foo that returns a Foo of the exact same type is an mutable update candidate.

Transforming outwards-in on a Foo:

1. Return types are replaced by unit.
2. Arguments of type Foo become "mutable Foo".
3. A recursive call propagates the update forwards.
4. For any application of the same Foo constructor to function arguments and referencing the remainder of the data structure, an in-place update for the closest mutable variable is inserted.
5. For any application of a different Foo constructor than the one just matched, the in-place update bubbles up to the previous activation frame.
6. Any code that simply returns the current element is eliminated.

This translation is predicated on a "mutable Foo" being like a "ref Foo". The derived mutable abstraction would look something like:

let mutable 'a list = Nil | Cons mutable 'a * mutable 'a list

let update l item newitem = match !l with
   Nil -> ()
 | Cons(x,next) as cur ->
     if item = !x then x := newitem
     else update next item newitem

let append x l = match !l with Nil as x -> l := Cons(x, Nil) | Cons(x,next) -> append x next

I can't think of any language that allows this, or any work along these lines, but I don't really know what to search for. It seems like it would be a pretty handy language feature though. Sometimes you really need a mutable data structure, and even though you have a perfectly good immutable equivalent at hand for which the mutable version seems like a mechanical translation, you still have to translate it by hand.

Can anyone provide pointers to work like this or explain the difficulties why it's not feasible in general?

By naasking at 2012-10-02 00:55 | LtU Forum | previous forum topic | next forum topic | other blogs | 7157 reads

Comment viewing options

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

Look into optimizations

Look into optimizations based on uniqueness typing. Cf. the languages Clean and Mercury.

By dmbarbour at Tue, 2012-10-02 01:19 | login or register to post comments

data structure synthesis

Peter Hawkins' work on concurrent data representation synthesis may be relevant.

By Sriram Srinivasan at Tue, 2012-10-02 02:36 | login or register to post comments

It's not possible to do this

It's not possible to do this safely in general without programmer specified constraints because by destroying earlier nodes of the data structure you might alter behavior, if they are still live elsewhere. To do this safely you have to do a pointer/shape analysis to determine in which places it's safe to destroy, or as dmbarbour says you have to get this information from the programmer.

It is certainly possible to do an unsafe version, though. To make that easier suppose that we are programming with record style syntax instead of building a completely new structure:

type 'a list = Nil | Cons {head : 'a; tail : 'a list}

let update l item newitem = match l with
    Nil as cur -> cur
  | Cons {head = x; tail = next} as cur ->
      if item = x then cur with {head = next}
      else cur with {tail = update next item newitem}

For a mutable version just keep the same interface, but internally let x with {field = v} be destructive. This is basically what Clojure transients do, except that the transient version of the API has an exclamation mark at the end of each name to indicate that it's not safe to use them non-linearly.

By Jules Jacobs at Tue, 2012-10-02 08:43 | login or register to post comments

It's not possible to do this

It's not possible to do this safely in general without programmer specified constraints because by destroying earlier nodes of the data structure you might alter behavior, if they are still live elsewhere.

Do you have a simple example? Specifically, I'm not sure what you mean by "safely". Are you referring to two concurrent updates, or some sort of higher order update where two changes are being made from the same thread in two different contexts?

Edit: The higher order hazard indeed has implications for the translation. For instance, a "map" function that performs a global update on a list could in principle try to perform another update within the callback, so the translation would have to ensure that an update to each individual constructor is complete, or not yet started, before calling out to foreign code. I don't think this is much of a problem though, just perform all such calls eagerly before mutating the constructor.

By naasking at Tue, 2012-10-02 13:50 | login or register to post comments

Breaking the Complexity Barrier

I came across this paper awhile ago, but forgot to post here:

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

By naasking at Mon, 2014-09-22 14:11 | login or register to post comments