Re: Mutually-referencing structures
On Mon, Apr 5, 2010 at 4:54 PM, Douglas Philips d...@mac.com wrote:
Immutability is orthogonal to reference-ness.
There is nothing wrong with having immutable cyclic graphs of values.
There is something wrong with immutable cyclic data structures: an undefined
(or unexpected) behaviour on update because of identity and state being
conflated again.
Let say one can write:
(def john-doe {:name John Doe :email j...@doe.com :account {:owner
#cyclic reference to the root map :balance 1000}})
Then you want to add 10$ to John's account:
(update-in john-doe [:account :balance] + 10)
The resulting data structure is:
{:name John Doe :email j...@doe.com :account {:owner #cyclic reference
to the root map :balance 1010}}
but what would #cyclic reference to the root map point to? to the previous
value of john-doe! So if we expands the reference:
{:name John Doe :email j...@doe.com :account {:owner {:name John Doe
:email j...@doe.com :account {:owner #cyclic reference to the root map
:balance 1000}} :balance 1010}}
This is not exactly the expected result. The result is confusing because the
cyclic reference must be to the identity of the user account not to its
actual value.
The same problem arises even when you update a non-nested field:
(assoc john-doe :email john@corp.com)
The resulting value would be:
{:name John Doe :email john@corp.com :account {:owner {:name John
Doe :email j...@doe.com :account {:owner #cyclic reference to the root
map :balance 1000}} :balance 1000}}
You really need an indirection level to properly handle cyclic data
structures.
hth,
Christophe
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
To unsubscribe, reply using remove me as the subject.
Re: Mutually-referencing structures
On Apr 6, 8:09 am, Christophe Grand christo...@cgrand.net wrote:
Let say one can write:
(def john-doe {:name John Doe :email j...@doe.com :account {:owner
#cyclic reference to the root map :balance 1000}})
At this point the cyclic structure is a consistent value. As long as
updates create new values that match the domain invariants, why should
any subsequent value cause a problem?
Then you want to add 10$ to John's account:
(update-in john-doe [:account :balance] + 10)
If that is what you update, then of course you will get ...
The resulting data structure is:
{:name John Doe :email j...@doe.com :account {:owner #cyclic reference
to the OLD root map :balance 1010}}
But how is this unique to cyclic structures? I can always mistakenly
create values and update them to end up with a structure that
incorrectly combines old and new values.
(def john-doe {zip-code: 12345 state: {name: CA}})
(update-in john-doe [:zip-code] + 5000)
;; new zip code, invalid old state
Maintaining domain invariants is the programmers responsibility,
whether or not there are cyclic references. Why wouldn't the same
facility that lets you create consistent mutual references in the
original John Doe value, also allow you to create consistent mutual
references in a consistent new (updated) John Doe value?
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
To unsubscribe, reply using remove me as the subject.
Re: Mutually-referencing structures
On 2010 Apr 6, at 9:09 AM, Christophe Grand wrote:
On Mon, Apr 5, 2010 at 4:54 PM, Douglas Philips d...@mac.com wrote:
Immutability is orthogonal to reference-ness.
There is nothing wrong with having immutable cyclic graphs of
values.
There is something wrong with immutable cyclic data structures: an
undefined (or unexpected) behaviour on update because of identity
and state being conflated again.
... details elided ...
This is not exactly the expected result. The result is confusing
because the cyclic reference must be to the identity of the user
account not to its actual value.
(def john-doe {:name John Doe :email j...@doe.com})
(def account {:identity john-doe :balance 100} )
(assoc john-doe :email john.doe at gee mail.com)
Now the account contains old/obsolete data and no cycles are needed to
cause that.
Doesn't seem that cycles are the problem...
-Doug
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
To unsubscribe, reply using remove me as the subject.
Re: Mutually-referencing structures
The question of the OP was also a practical one : is either Clojure
or functional not a good match?
Honestly, I don't know the answer for sure, because:
* there is still no (widely known ?) utilities to manipulate things
easily. There were attemps like the one by Jeffrey Streizhem in
clojure contrib, (dataset / datalog), but who's using it for real ?
* The STM is indeed easy to work with, by using the metaphore of the
database (and i think it is the right way of doing things. functions,
and macros to generate some of those functions can help managing the
necessary level of indirection).
* BUT : isn't the real problem that one will not content
[him/her]/self with playing with in-memory data ? One will want to
make the data persistent (outside-of-process, aka
storage-persistance). And with this kind of problem, one will have a
graph of identities containing references to other identities (the
needed level(s) of indirection). How does one painlessly store/unstore
those graphs to databases ?
Not to say: how does one totally reliably move data from the STM
to/from an RDBMS ? Currently, the trick is to send things to an
agent, but this does not provide all the required guarantees ...
So from the practical point of view, I'm not sure (alas) if clojure
has -yet- the expected YES! answer ...
2010/4/6 Douglas Philips d...@mac.com:
On 2010 Apr 6, at 9:09 AM, Christophe Grand wrote:
On Mon, Apr 5, 2010 at 4:54 PM, Douglas Philips d...@mac.com wrote:
Immutability is orthogonal to reference-ness.
There is nothing wrong with having immutable cyclic graphs of values.
There is something wrong with immutable cyclic data structures: an
undefined (or unexpected) behaviour on update because of identity and state
being conflated again.
... details elided ...
This is not exactly the expected result. The result is confusing because
the cyclic reference must be to the identity of the user account not to its
actual value.
(def john-doe {:name John Doe :email j...@doe.com})
(def account {:identity john-doe :balance 100} )
(assoc john-doe :email john.doe at gee mail.com)
Now the account contains old/obsolete data and no cycles are needed to cause
that.
Doesn't seem that cycles are the problem...
-Doug
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
To unsubscribe, reply using remove me as the subject.
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
Re: Mutually-referencing structures
On Tue, Apr 6, 2010 at 3:41 PM, Sophie itsme...@hotmail.com wrote:
On Apr 6, 8:09 am, Christophe Grand christo...@cgrand.net wrote:
Let say one can write:
(def john-doe {:name John Doe :email j...@doe.com :account {:owner
#cyclic reference to the root map :balance 1000}})
At this point the cyclic structure is a consistent value.
True.
Then you want to add 10$ to John's account:
(update-in john-doe [:account :balance] + 10)
If that is what you update, then of course you will get ...
The resulting data structure is:
{:name John Doe :email j...@doe.com :account {:owner #cyclic
reference
to the OLD root map :balance 1010}}
But how is this unique to cyclic structures?
If your structures aren't cyclic the newly updated value can't accidentally
contain references to its previous self.
I can always mistakenly
create values and update them to end up with a structure that
incorrectly combines old and new values.
Sure.
Maintaining domain invariants is the programmers responsibility,
whether or not there are cyclic references. Why wouldn't the same
facility that lets you create consistent mutual references in the
original John Doe value, also allow you to create consistent mutual
references in a consistent new (updated) John Doe value?
What if you also want an history or a log in your data structure, pointing
to previous value? Then you wouldn't want these references to be updated by
the mechanism which create consistent mutual references. So you would put a
marker on it to say it is static.
At the end you have a complex system which walks the data-structure and
tracks all mutual references to update them all at once (except those which
are marked as static). This is nearly the description of the Clojure STM
except that with the STM you mark the references which need to be updated
all at once not those which don't.
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
To unsubscribe, reply using remove me as the subject.
Re: Mutually-referencing structures
On Tue, Apr 6, 2010 at 3:43 PM, Douglas Philips d...@mac.com wrote:
(def john-doe {:name John Doe :email j...@doe.com})
(def account {:identity john-doe :balance 100} )
(assoc john-doe :email john.doe at gee mail.com)
Now the account contains old/obsolete data and no cycles are needed to
cause that.
Doesn't seem that cycles are the problem...
The cycles are gone but the identity john-doe aand its curren-state are
still conflated so you get the same problem:
(def account {:identity john-doe :balance 100} )
(assoc john-doe :email john.doe at gee mail.com)
On the first line you define a reference between the current value of
account and the current value of john-doe, so it is to be expected that
(assoc john-doe :email john.doe at gee mail.com) won't give the expected
result since you didn't provided the system with enough knowledge.
(def account {:identity #'john-doe :balance 100} )
(def john-doe (assoc john-doe :email john.doe at gee mail.com))
; or (alter-var-root #'john-doe assoc :email john.doe at gee mail.com)
there account points to the updated john-doe
Of course, one should not abuse vars, and the above code should at least be
rewritten with refs:
(def account (ref {:identity john-doe :balance 100}) )
(def john-doe (ref {:name John Doe :email j...@doe.com}))
(dosync (alter john-doe assoc :email john.doe at gee mail.com))
Really, to me the problem isn't creating cyclic data-structures but updating
them: the system must know which mutual references are to the identity (and
should be updated) and which are not. You have to give this information to
the system one way or the other, the system can't guess.
Btw, to some extent, one can create cyclic data-structures in Clojure (only
lazyseqs though -- unless you implement your own map or use lazy-map etc.) :
user= (defn cyclic-seq [coll] (let [s (promise)] @(deliver s (lazy-cat coll
@s
user= (let [s (cyclic-seq [1 2 3])] (identical? (seq s) (seq (drop 3 s
true
Christophe
--
You received this message because you are subscribed to the Google
Groups Clojure group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
To unsubscribe, reply using remove me as the subject.
Re: Mutually-referencing structures
On Tue, Apr 6, 2010 at 9:59 PM, Christophe Grand christo...@cgrand.net wrote: Btw, to some extent, one can create cyclic data-structures in Clojure (only lazyseqs though -- unless you implement your own map or use lazy-map etc.) : user= (defn cyclic-seq [coll] (let [s (promise)] @(deliver s (lazy-cat coll @s user= (let [s (cyclic-seq [1 2 3])] (identical? (seq s) (seq (drop 3 s true I've already mentioned it a few times in passing, but my letrec macro uses promises and some simple-minded code walking to abstract away this kind of thing. The included example code is a pair of mutually cyclic lazy-seqs. http://gist.github.com/336461 -Per -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en To unsubscribe, reply using remove me as the subject.
Re: Mutually-referencing structures
On 2010 Apr 6, at 10:59 AM, Christophe Grand wrote: The cycles are gone but the identity john-doe aand its curren-state are still conflated so you get the same problem: Thus, since simple trees have the exact same issues, circularity is not the problem. Really, to me the problem isn't creating cyclic data-structures but updating them: the system must know which mutual references are to the identity (and should be updated) and which are not. You have to give this information to the system one way or the other, the system can't guess. To rephrase what you've said: the system must know which references are to the identity and which are not. Clojure already has that covered, but it won't do it for you behind your back. :) And this is not unique to circularity and it is not caused by circularity. There is an issue that you cannot create immutable mutual references, but that is a -separate- issue. Btw, to some extent, one can create cyclic data-structures in Clojure... I think Per was showing something similar. Please don't blame circularity for identity/value problems. ;) -Doug -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en To unsubscribe, reply using remove me as the subject.
Re: Mutually-referencing structures
On Tue, Apr 6, 2010 at 10:43 PM, Douglas Philips d...@mac.com wrote: On 2010 Apr 6, at 10:59 AM, Christophe Grand wrote: The cycles are gone but the identity john-doe aand its curren-state are still conflated so you get the same problem: Thus, since simple trees have the exact same issues, circularity is not the problem. I agree. The deeper problem there is identity-value conflation rather than circularity. As for the general problem of manipulating immutable cyclic data structures, it admittedly requires techniques not usually taught even in advanced courses on functional programming. A good paper to read is Cycle Therapy: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.2027 -Per -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en To unsubscribe, reply using remove me as the subject.
Re: Mutually-referencing structures
On Apr 6, 2010, at 9:01 AM, Laurent PETIT wrote: * BUT : isn't the real problem that one will not content [him/her]/self with playing with in-memory data ? One will want to make the data persistent (outside-of-process, aka storage-persistance). And with this kind of problem, one will have a graph of identities containing references to other identities (the needed level(s) of indirection). How does one painlessly store/unstore those graphs to databases ? XML with ID/IDREFs seems the obvious choice. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en To unsubscribe, reply using remove me as the subject.
Re: Mutually-referencing structures
I would really love to see (clearly by someone much smarter than I :) an insightful summary of these kinds of concept-heavy discussions, stickied or FAQd or even book'd somewhere. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en To unsubscribe, reply using remove me as the subject.
Mutually-referencing structures
(deftype Account [owner balance]) (deftype Person [accounts]) joe has 1 account. How to I create / initialize joe the account with mutual references? I'd rather not use refs. Thanks! -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en To unsubscribe, reply using remove me as the subject.
Re: Mutually-referencing structures
On Apr 5, 2010, at 2:09 AM, Sophie wrote: (deftype Account [owner balance]) (deftype Person [accounts]) joe has 1 account. How to I create / initialize joe the account with mutual references? I'd rather not use refs. You can't do it directly without one of the two being mutable. But you could simulate it by assigning each object a unique ID and having them refer to each other by that ID. -Michael -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Mutually-referencing structures
You need a level of indirection. One way is to make the backward reference from accounts to owners be based on a non-pointer primary key (maybe a keyword) that can be resolved through some table. This is how it works in relational database systems If you want to use references of some sort, mutability (possibly implicit) is required. Here's an example of implicit mutation via delay/force: (deftype Account [owner balance]) (deftype Person [name accounts]) (declare per) (def per-account1 (Account (delay per) 42)) (def per-account2 (Account (delay per) 9000)) (def per (Person Per [per-account1, per-account2])) (:name @(:owner per-account1)) ;; Per Note that you will need to dereference backward references explicitly. In this example, I also relied on forward declaration of vars for tying the circular knots. If you want to this within functions, you'll need something like letrec. Here's a proof of concept I did a while ago: http://gist.github.com/336461 With that, you could write the above as follows: (letrec [per-account1 (Account (delay per) 42) per-account2 (Account (delay per) 9000) per (Person Per [(delay per-account1), (delay per-account2)])] (:name @(:owner per-account1))) Unfortunately, because of the way my letrec implementation works, you will need to delay both forward and backward references. By the way, as you will quickly see if you play around with this kind of code in the REPL, you must be careful with circular references: it's very easy to send the printer into an infinite loop. You can do a (set! *print-level* some small number) to prevent this from happening. -Per On Mon, Apr 5, 2010 at 2:09 PM, Sophie itsme...@hotmail.com wrote: (deftype Account [owner balance]) (deftype Person [accounts]) joe has 1 account. How to I create / initialize joe the account with mutual references? I'd rather not use refs. Thanks! -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en To unsubscribe, reply using remove me as the subject. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Mutually-referencing structures
Is this a Clojure restriction, or is it intrinsic to functional programming? If my app is essentially about a user creating and editing a graph structure (sometimes via crud-level interactions, other times by somewhat larger refactorings), is either Clojure or functional not a good match? Thanks for any advice! -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en To unsubscribe, reply using remove me as the subject.
Re: Mutually-referencing structures
On Apr 5, 2010, at 7:49 AM, Sophie wrote: Is this a Clojure restriction, or is it intrinsic to functional programming? It's a consequence of immutable data structures, which are an aspect of functional programming. An immutable object can never be changed, and you can't create multiple objects simultaneously, so you can't ever get a cycle of direct references between immutable objects. If my app is essentially about a user creating and editing a graph structure (sometimes via crud-level interactions, other times by somewhat larger refactorings), is either Clojure or functional not a good match? You can still do things functionally, with a level of indirection. I don't see any problem with that approach, but whether it's a good match for your project is up to you. Otherwise, you can use mutable structures. Clojure certainly supports mutability, but as a primarily-functional language it might not be the right tool for the job if you're going to use mutability extensively. -Michael -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en To unsubscribe, reply using remove me as the subject.
Re: Mutually-referencing structures
It's a consequence of immutable data structures, which are an aspect of functional programming. An immutable object can never be changed But single-assignment is a quite valid (and more flexible?) form of immutability. I'm not convinced cycles are intrinsically tied to it in any way. (In fact, I initially thought Clojure had an unambiguous sentinel value for not initialized) I was hoping to develop (or find :) macros to automate the code for maintaining various kinds of 2-way pointers, rather than use separate ID fields or (essentially global) collections of pairs for relations. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en To unsubscribe, reply using remove me as the subject.
Re: Mutually-referencing structures
On Apr 5, 2010, at 4:34 PM, Sophie wrote: But single-assignment is a quite valid (and more flexible?) form of immutability. I'm not convinced cycles are intrinsically tied to it in any way. If you can assign to it, it's mutable. What you're talking about is creating a mutable object, then making it immutable at some point (say, after it's first assigned to). Immutable object cycles are indeed possible if one permits this; Clojure doesn't, at least not for simple objects. -Michael -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en To unsubscribe, reply using remove me as the subject.
Re: Mutually-referencing structures
It's no more mutable than a pure lambda calculus with lazy evaluation. There is no _observable_ mutability. Anything else is an implementation detail. Single assignment comes from the tradition of logic programming and concurrent process calculus rather than lambda calculus. A single assignment variable is a lot like a pure promise. By pure I mean that one cannot peek at the promise without blocking on it. This is all-important in preventing race conditions in a concurrent setting. If Sophie is interested, I used promises as single assignment variables in the letrec implementation I posted. It's fair to say that while Clojure supports single assignment variables in the form of promises, they are not fundamental language-level constructs the way they are in languages like Prolog or Oz. You have to explicitly dereference them like any other IDeref. -Per On Tue, Apr 6, 2010 at 6:53 AM, Michael Gardner gardne...@gmail.com wrote: On Apr 5, 2010, at 4:34 PM, Sophie wrote: But single-assignment is a quite valid (and more flexible?) form of immutability. I'm not convinced cycles are intrinsically tied to it in any way. If you can assign to it, it's mutable. What you're talking about is creating a mutable object, then making it immutable at some point (say, after it's first assigned to). Immutable object cycles are indeed possible if one permits this; Clojure doesn't, at least not for simple objects. -Michael -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en To unsubscribe, reply using remove me as the subject. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
