Persistent data structures in Java

Question

Does anyone know a library or some at least some research on creating and using persistent data structures in Java? I don't refer to persistence as long term storage but persistence in terms of immutability (see Wikipedia entry).

I'm currently exploring different ways to model an api for persistent structures. Using builders seems to be a interesting solution:

// create persistent instance
Person p = Builder.create(Person.class)
             .withName("Joe")
             .withAddress(Builder.create(Address.class)
                 .withCity("paris")
                 .build())
              .build();

// change persistent instance, i.e. create a new one 
Person p2 = Builder.update(p).withName("Jack");

Person p3 = Builder.update(p)
              .withAddress(Builder.update(p.address())
                .withCity("Berlin")
                .build)
            .build();

But this still feels somewhat boilerplated. Any ideas?

Answer 1

I guess the obvious choices are:

o Switch to a transient data structure (builder) for the update. This is quite normal. StringBuilder for String manipulation for example. As your example.

Person p3 =
    Builder.update(p)
    .withAddress(
        Builder.update(p.address())
       .withCity("Berlin")
       .build()
    )
    .build();

o Always use persistent structures. Although there appears to be lots of copying, you should actually be sharing almost all state, so it is nowhere near as bad as it looks.

final Person p3 = p
    .withAddress(
        p.address().withCity("Berlin")
    );

o Explode the data structure into lots of variables and recombine with one huge and confusing constructor.

final Person p3 = Person.of(
    p.name(),
    Address.of(
       p.house(), p.street(), "Berlin", p.country()
    ),
    p.x(),
    p.y(),
    p.z()
 );

o Use call back interfaces to provide the new data. Even more boilerplate.

final Person p3 = Person.of(new PersonInfo(
    public String  name   () { return p.name(); )
    public Address address() { return Address.of(new AddressInfo() {
       private final Address a = p.address();
       public String house  () { return a.house()  ; }
       public String street () { return a.street() ; }
       public String city   () { return "Berlin"   ; }
       public String country() { return a.country(); }
    })),
    public Xxx     x() { return p.x(); }
    public Yyy     y() { return p.y(); }
    public Zzz     z() { return p.z(); }
 });

o Use nasty hacks to make fields transiently available to code.

final Person p3 = new PersonExploder(p) {{
    a = new AddressExploder(a) {{
        city = "Berlin";
    }}.get();
}}.get();

(Funnily enough I was just put down a copy of Purely Functional Data Structures by Chris Okasaki.)

Answer 2

It is very difficult, if not impossible, to make things immutable that ain't designed so.

If you can design from ground up:

• use only final fields
• do not reference non immutable objects

Answer 3

Builders will make your code too verbose to be usable. In practice, almost all immutable data structures I've seen pass in state through the constructor. For what its worth, here are a nice series of posts describing immutable data structures in C# (which should convert readily into Java):

• Part 1: Kinds of Immutability
• Part 2: Simple Immutable Stack
• Part 3: Covariant Immutable Stack
• Part 4: Immutable Queue
• Part 5: Lolz! (included for completeness)
• Part 6: Simple Binary Tree
• Part 7: More on Binary Trees
• Part 8: Even More on Binary Trees
• Part 9: AVL Tree Implementation
• Part 10: Double-ended Queue
• Part 11: Working Double-ended Queue Implementation

C# and Java are extremely verbose, so the code in these articles is quite scary. I recommend learning OCaml, F#, or Scala and familiarizing yourself with immutability with those languages. Once you master the technique, you'll be able to apply the same coding style to Java much more easily.

Answer 4

Do you want immutability :

1. so external code cannot change the data?
2. so once set a value cannot be changed?

In both cases there are easier ways to accomplish the desired result.

Stopping external code from changing the data is easy with interfaces:

public interface Person {
   String getName();
   Address getAddress();
}
public interface PersonImplementor extends Person {
   void setName(String name);
   void setAddress(Address address);
}

public interface Address {
    String getCity();
}


public interface AddressImplementor {
    void setCity(String city);
}

Then to stop changes to a value once set is also "easy" using java.util.concurrent.atomic.AtomicReference (although hibernate or some other persistence layer usage may need to be modified):

class PersonImpl implements PersonImplementor {
    private AtomicReference<String> name;
    private AtomicReference<Address> address;

    public void setName(String name) {
        if ( !this.name.compareAndSet(name, name) 
           && !this.name.compareAndSet(null, name)) {
            throw new IllegalStateException("name already set to "+this.name.get()+" cannot set to "+name);
        }
    }
    // .. similar code follows....
}

But why do you need anything more than just interfaces to accomplish the task?

Answer 5

Have a look at Functional Java. Currently provided persistent datastructures include:

• Singly-linked list (fj.data.List)
• Lazy singly-linked list (fj.data.Stream)
• Nonempty list (fj.data.NonEmptyList)
• Optional value (a container of length 0 or 1) (fj.data.Option)
• Set (fj.data.Set)
• Multi-way tree (a.k.a. rose tree) (fj.data.Tree)
• Immutable map (fj.data.TreeMap)
• Products (tuples) of arity 1-8 (fj.P1..P8)
• Vectors of arity 2-8 (fj.data.vector.V2..V8)
• Pointed list (fj.data.Zipper)
• Pointed tree (fj.data.TreeZipper)
• Type-safe, generic heterogeneous list (fj.data.hlist.HList)
• Immutable arrays (fj.data.Array)
• Disjoint union datatype (fj.data.Either)

A number of usage examples are provided with the binary distribution. The source is available under a BSD license from Google Code.

Answer 6

Follow a very simple tentative with dynamic proxy:

class ImmutableBuilder {

    static <T> T of(Immutable immutable) {
        Class<?> targetClass = immutable.getTargetClass();
        return (T) Proxy.newProxyInstance(targetClass.getClassLoader(),
            new Class<?>[]{targetClass},
            immutable);
    }

    public static <T> T of(Class<T> aClass) {
        return of(new Immutable(aClass, new HashMap<String, Object>()));
    }
}

class Immutable implements InvocationHandler {

    private final Class<?> targetClass;
    private final Map<String, Object> fields;

    public Immutable(Class<?> aTargetClass, Map<String, Object> immutableFields) {
        targetClass = aTargetClass;
        fields = immutableFields;
    }

    public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
        if (method.getName().equals("toString")) { 
            // XXX: toString() result can be cached
            return fields.toString();
        }

        if (method.getName().equals("hashCode")) { 
            // XXX: hashCode() result can be cached
            return fields.hashCode();
        }

        // XXX: naming policy here
        String fieldName = method.getName(); 

        if (method.getReturnType().equals(targetClass)) {
          Map<String, Object> newFields = new HashMap<String, Object>(fields);
          newFields.put(fieldName, args[0]);
          return ImmutableBuilder.of(new Immutable(targetClass, newFields));
        } else {
            return fields.get(fieldName);
        }
    }

    public Class<?> getTargetClass() {
        return targetClass;
    }
}

usage:

interface Person {
    String name();
    Person name(String name);
    int age();
    Person age(int age);
}

public class Main {

    public static void main(String[] args) {
        Person mark = ImmutableBuilder.of(Person.class).name("mark").age(32);
        Person john = mark.name("john").age(24);
        System.out.println(mark);
        System.out.println(john);
    }
}

grow directions:

• naming policy (getName, withName, name)
• caching toString(), hashCode()
• equals() implementations should be straightforward (although not implemented)

hope it helps :)

Answer 7

I implemented a few persistent data structures in Java. All open source (GPL) on Google code for anyone who is interested:

http://code.google.com/p/mikeralib/source/browse/#svn/trunk/Mikera/src/mikera/persistent

The main ones I have so far are:

• Persistent mutable test object
• Persistent hash maps
• Persistent vectors/lists
• Persistent sets (including a specialised persistent set of ints)