Immutable cyclic data structures via a

Immutable cyclic data structures via a

[Christopher L Conway]

--- In ocaml_beginners@yahoogroups.com, Andrew Myers <andru@...> wrote:
> [Note from Chris: I'm reposting this from the beginner's list, because I'm
interested in an answer and more likely to get it here... A declaration of a
graph data structure might be:] 
>
> type node = edge list
> and edge = {from: node; to_: node}
>
> You'll have trouble initializing that data structure, though. Maybe
> better to add mutability somewhere, e.g.
>
> type node = {mutable outgoing: edge list}
> and edge = {from: node; to_: node}
>
> Then you can create all the nodes first and backpatch them with all the
> edges.

This makes me wonder: if you add mutable fields to a type in order to
build a cyclic data structure, but you intend to use the data
structure immutably once it is built, is there any way to "freeze" the
value, producing an immutable cyclic structure? This is a common
pattern, similar to Bloch's Builder pattern for Java.[1]

You might have an operation, call it "unmute", that changes the type
of the structure. There would need to be a corresponding type-level
operation, call it "UNMUTE", that strips the "mutable" qualifier from
mutable fields. E.g.,

val unmute : 'a -> UNMUTE('a)

and

UNMUTE(node) = { outgoing : edge list }

for node as defined above.

I'm pretty confident this isn't possible in plain-vanilla OCaml. You
can do something similar (at a high cost in ugliness) using a
variation of "Tying the Knot" a la Haskell.[2]

Is anybody aware of a language extension that does this, or a similar
feature in another language?

Regards,
Chris

[1]: http://www.screaming-penguin.com/node/7598 "The essence of the
enhanced builder pattern in Java"
[2]: http://www.haskell.org/haskellwiki/Tying_the_Knot

Re: [Caml-list] Immutable cyclic data structures via a

[Jeremy Yallop]

Christopher L Conway wrote:
> --- In ocaml_beginners@yahoogroups.com, Andrew Myers <andru@...> wrote:
>> type node = edge list
>> and edge = {from: node; to_: node}
>>
>> You'll have trouble initializing that data structure, though. Maybe
>> better to add mutability somewhere, e.g.
>>
>> type node = {mutable outgoing: edge list}
>> and edge = {from: node; to_: node}
>>
>> Then you can create all the nodes first and backpatch them with all the
>> edges.
> 
> This makes me wonder: if you add mutable fields to a type in order to
> build a cyclic data structure, but you intend to use the data
> structure immutably once it is built, is there any way to "freeze" the
> value, producing an immutable cyclic structure? This is a common
> pattern, similar to Bloch's Builder pattern for Java.[1]

I believe that private types can do what you want.  Private record
types allow only read access, even to mutable fields, so if you have a
type

   type node = private { mutable outgoing: edge list }

then you can't update the "outgoing" field of any values of type node,
even though it's declared mutable.  You can then create a module which
exports such a declaration in the signature:

   module Graph :
   sig
     type node = private { mutable outgoing : edge list }
     and  edge =         { from : node ; to_ : node }
   end =
   struct
     type node =         { mutable outgoing : edge list }
     and  edge =         { from : node ; to_ : node }
     ...
   end

Now you can make use of the mutability of the field within the
implementation of the module (marked "...") but not outside the
module: the module boundary acts as the "freeze" operation that
converts mutable to immutable structures.

Of course, this isn't particularly satisfactory, since you have to
either anticipate all possible graph values when you write the module,
or provide a clunky interface for constructing cyclic graphs.  What
you really want is to provide two versions of the graph type, both of
which are visible to clients of the module, and an explicit "freeze"
operation for converting mutable graphs to immutable graphs.  I
believe that the following code meets all your requirements, although
it may be possible to make it more succinct.

   module Graph :
   sig
     module Mutable :
     sig
       type node =         { mutable outgoing : edge list }
       and  edge =         { from : node ; to_ : node }
     end

     module Immutable :
     sig
       type node = private { mutable outgoing : edge list }
       and  edge =         { from : node ; to_ : node }
     end

     module Freeze :
     sig
       val node : Mutable.node -> Immutable.node
       val edge : Mutable.edge -> Immutable.edge
     end
   end =
   struct
     module Graph =
     struct
       type node = { mutable outgoing : edge list }
       and  edge = { from : node ; to_ : node }
     end
     module Mutable   = Graph
     module Immutable = Graph
     module Freeze =
     struct
       let node n = n
       let edge e = e
     end
   end

Now you can, outside the module, create cyclic values using mutability:

   open Graph.Mutable

   let medge = {
     from = {outgoing = []};
     to_  = {outgoing = []};
   }
   let () = medge.from.outgoing <- [medge]
   let () = medge.to_ .outgoing <- [medge]

and then freeze them so that they can no longer be updated.

   let iedge = Graph.Freeze.edge medge

(Of course, you can still update the graph via the "medge" binding,
but it's easy enough to prevent access to that, if necessary.)

Hope this helps,

Jeremy.

-- 
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.

Re: [Caml-list] Immutable cyclic data structures via a

[Jeremy Yallop]

Jeremy Yallop wrote:
>   module Graph :
>   sig
>     module Mutable :
>     sig
>       type node =         { mutable outgoing : edge list }
>       and  edge =         { from : node ; to_ : node }
>     end
> 
>     module Immutable :
>     sig
>       type node = private { mutable outgoing : edge list }
>       and  edge =         { from : node ; to_ : node }
>     end
> 
>     module Freeze :
>     sig
>       val node : Mutable.node -> Immutable.node
>       val edge : Mutable.edge -> Immutable.edge
>     end
>   end =

I should also mention a drawback of this approach, which is that 
"private" may be stronger than you need.  Values of private record type 
can be neither updated *nor created*; outside the Graph module you 
cannot construct fresh values of Immutable.node, or even use "functional 
update" (i.e. "with" syntax) to construct new values from existing 
Immutable.node values.

Jeremy.

-- 
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.

Re: [Caml-list] Immutable cyclic data structures via a

[Edgar Friendly]

Christopher L Conway wrote:
> This makes me wonder: if you add mutable fields to a type in order to
> build a cyclic data structure, but you intend to use the data
> structure immutably once it is built, is there any way to "freeze" the
> value, producing an immutable cyclic structure? This is a common
> pattern, similar to Bloch's Builder pattern for Java.[1]
> 
> You might have an operation, call it "unmute", that changes the type
> of the structure. There would need to be a corresponding type-level
> operation, call it "UNMUTE", that strips the "mutable" qualifier from
> mutable fields. E.g.,
<SNIP>
> I'm pretty confident this isn't possible in plain-vanilla OCaml. You
> can do something similar (at a high cost in ugliness) using a
> variation of "Tying the Knot" a la Haskell.[2]

ExtLib (and thus batteries) uses your unmute (called [inj]) for
converting a mutable list into the normal immutable list.  The definition:

external inj : 'a mut_list -> 'a list = "%identity"

It's effectively using Obj.magic, but specialized on these types.

As always, be *very* careful when using this kind of type system voodoo,
but it can work under certain circumstances.

E.

Re: [Caml-list] Immutable cyclic data structures via a

[Francois Pottier]

On Sat, Dec 13, 2008 at 07:47:46PM -0600, Edgar Friendly wrote:
> ExtLib (and thus batteries) uses your unmute (called [inj]) for
> converting a mutable list into the normal immutable list.  The definition:
> 
> external inj : 'a mut_list -> 'a list = "%identity"
> 
> As always, be *very* careful when using this kind of type system voodoo,
> but it can work under certain circumstances.

This is, in principle, unsound. The compiler could (if it were more agressive)
assume that a value of type 'a list is unaffected by a function call, whereas,
if the list is really mutable, it could actually be written to by the call.

With the current ocaml compiler, this might be okay, but I'd be wary of
building this kind of code into a library.

Best regards,

-- 
François Pottier
Francois.Pottier@inria.fr
http://cristal.inria.fr/~fpottier/

Re: [Caml-list] Immutable cyclic data structures via a

[blue storm]

On 12/14/08, Francois Pottier <Francois.Pottier@inria.fr> wrote:
> On Sat, Dec 13, 2008 at 07:47:46PM -0600, Edgar Friendly wrote:
>> ExtLib (and thus batteries) uses your unmute (called [inj]) for
>> converting a mutable list into the normal immutable list.  The definition:
>
> This is, in principle, unsound. The compiler could (if it were more
> agressive)
> assume that a value of type 'a list is unaffected by a function call,
> whereas,
> if the list is really mutable, it could actually be written to by the call.

That could be an issue if an immutable list was mutated by the
library. Extlib uses mutability to build new mutable lists, to have
for example a cheap tail-recursive map (you can destructively cons new
cells at the end of the mutable list). The new list is then converted
in constant time to an usual unmutable list, wich is returned by the
function. The reference to the original mutable list is lost, and pure
lists are never converted back.

The mutable list stays inside the function boundary and, assuming the
function is correctly written, there is no observable mutability.

Re: [Caml-list] Immutable cyclic data structures via a

[Richard Jones]

On Sat, Dec 13, 2008 at 09:45:07PM +0000, Christopher L Conway wrote:
> This makes me wonder: if you add mutable fields to a type in order to
> build a cyclic data structure, but you intend to use the data
> structure immutably once it is built, is there any way to "freeze" the
> value, producing an immutable cyclic structure? This is a common
> pattern, similar to Bloch's Builder pattern for Java.[1]

Note that extlib does this in the ExtList.List module, using lots of
Obj.magic of course:

http://code.google.com/p/ocaml-extlib/source/browse/trunk/extlib/extList.ml#31

This is purely for speed, so we can do things like appending to
(private) lists when building them, and returning a real list.

IIRC it was rather controversial at the time, and there is still some
question as to whether it is really safe -- doesn't the compiler track
mutable objects specially so the introduction of major heap -> minor
heap pointers (ie. old -> new objects) works correctly with the
garbage collector?

In any case, it seems to work.  I have used ExtList.List extensively
in masses of production code and never found a problem.

Rich.

-- 
Richard Jones
Red Hat