Confusion with Immutability

[Paul Drummond]

Hi all,

I have been meaning to post about this for a while now so today (after
reading and commenting on Eric Rochester's recent articles which are
great BTW) I decided to bite the bullet rather than spend another day
going round in circles in the REPL!

First a little background...

I have been trying to get my head around FP concepts for over a year
now (off and on) and have experimented with Haskell, CL, Scheme and
most recently Clojure. While I think I understand the concepts well
enough in theory, so far I have been unable to apply them confidently
in practise. There's a missing link somewhere - an "aha" light-bulb
moment just waiting to happen....

I could now essentially fill several pages by giving a brain-dump
describing my confusion but I'm pretty sure it would end up an
unreadable mess (!) so I will try to keep this as concise just as a
basis for starting a discussion hopefully.

In a nutshell, my problem is to do with immutability. I understand
the concepts and when I listen to Rich talking about data structures
and providing examples similar to this one:

user=> (def v [1 2 3])
#'user/v
user=> v
[1 2 3]
user=> (conj v 4)
[1 2 3 4]
user=> v
[1 2 3]

It all makes sense - conj gives the impression of changing the vector
but it's not actually changed of course.

My problem is with regard to the management of data once it's returned
to the outer scope and what that means for the structure of a whole
program. Taking the example above, what do we do with the vector
returned from conj?

My current understanding is that you have *ONLY* two choices: re'def
the var OR use recursion.

So I could redef v like this:

user=> (def v (conj v 4))
#'user/v
user=> v
[1 2 3 4]

I don't think this is idiomatic Clojure style even though I have seen
it done (Webjure springs to mind). It feels like this sort of thing is
done by people coming to functional programming and trying to do
things the old way even though the language is trying very hard to
tell you this is bad style and not the way to do things in Clojure.
But when I see Clojure code that does this I start to doubt my
conclusions!

To my mind the only alternative to redef'ing is recursion which means
structuring your entire program recursively.

Now, this is where things start to cloud over so maybe I will stop
here. I think I just want to get an answer to the question: "Is it
true that you either redef or use recursive style?". If this is true
and I am not getting everything completely wrong then I will take the
next step try to formulate into words my issues with recursion!!!

One step at and time - it's the only way out of this!! :)

Thanks,
Paul Drummond

[Zak Wilson]

To put it simply, the idiomatic thing to do with the return value of a
conj is to give it a new name, or just call other functions on it.
Deeply nested function calls and various forms of function composition
are fairly common in both Lisps and purely functional languages. There
are places where you might want to simulate mutation with refs, but
doing a series of operations to a value is not one of them.

[Duane]

I believe you have essentially characterized your options with regard
to your example, but I'm not sure I understand why this is
problematic. Sounds like you have listened to and read much of the
material that Rich has put out about his intentions behind
immutability (you never mention concurrency though). As Zak has
pointed out, the way you make use of such values is pretty
straightforward from an FP point of view. As you said, this was "step
1" so I assume you are building up to a larger issue that you have
with the recursion support built into Clojure as a means of
iteratively performing operations that appear to evolve a value with
each cycle.

A difference with Clojure as opposed to say Java is the emphasis on
avoiding side effects (assuming you adhere to the "clojure style").
So that the overall state of the program or applicable environment may
have new values added to it, but no changes to old values have
actually occurred (behind the scenes, of course, "immutable" data
structure implementations are actually being augmented and changed in
a sense, but from the POV of the program this is not visible). And
Clojure is a lot more serious about side effect management then say
Common Lisp where there are a number data structure operations that
are destructive (and Lisp programmers use them because they are more
efficient with respect to memory usage etc...). For Clojure, all of
this is in service to the larger purpose of making concurrency very
manageable, which as Rich has described many times, has been the large
thorn in the side of developers of programs of any appreciable
complexity. His ants demo really drives this point home.

That being said (and I apologize for somewhat restating the obvious),
I am very curious to find out what you are building up to.

Best,
-- Duane

On Jun 27, 5:17 am, Paul Drummond

[Paul Drummond]

Thanks guys for your replies - I realise my post was not really enough
to work with, sorry for that. I guess I just needed to start
somewhere to get the ball rolling!

I will gather my thoughts over the weekend and hopefully then I will
be able to put something together to explain where I am trying to get
to!

Thanks,
Paul Drummond

[Raoul Duke]

> program. Taking the example above, what do we do with the vector
> returned from conj?
>
> My current understanding is that you have *ONLY* two choices: re'def
> the var OR use recursion.

you do basically have to introduce a new name for the thing returned
from conj if you want to make use of it in your functional program. so
if you took an imperative program and turned it into super idiomatic
fp style, it could seem like there is suddenly a code bloat because
you need a ton of new variables.

but then you have to reconsider the approach of transforming sorta too
verbatim the imperative approach. e.g. in fp you'd want to use
something like a map rather than a for loop, as an overly simple
example of where the for loop would have re'def whereas the map
doesn't.

dunno if that made any sense - you are totally right about how this
can be a strange thing to "get", and it has been too long for me in
the imperative world, so i am not sure i even get it myself any more.
(so apologies if what i said turns out to be a misleading tub of poo.)

sincerely.
PS: and thanks for your asking about all this, it really helps other
folks think through things. (some folks might not need to as much as i
do, apologies to them for the ascii noise :-)

[Duane]

> you do basically have to introduce a new name for the thing returned
> from conj if you want to make use of it in your functional program. so
> if you took an imperative program and turned it into super idiomatic
> fp style, it could seem like there is suddenly a code bloat because
> you need a ton of new variables.

I also understand the "disturbing" feeling that one has coming from an
imperative programming paradigm when trying to wrap your head around a
language like Clojure. And, Clojure in particular, with its emphasis
on persistent data structures, seems very counterintuitive with
respect to code bloat and memory efficiencies.

As I have researched the code more and listened to Rich's
presentations I've been "sold" on the idea of persistent data
structures because of the efficient way in which Rich has implemented
things behind the scenes, which is a cornerstone of the language. If
you can accept that persistent data structures are not overly wasteful
or inefficient then coupling that with dynamic FP style and the very
controlled way state is managed across threads (using Vars, Refs,
Agents with STM), the language as a whole becomes a very beautiful
thing.

In Clojure, you have a concurrency model that rocks IMO. You have
dynamic FP style very close to Lisp (my other love). And last but not
least, you have everything sitting on a highly optimized execution
platform (the JVM with Hotspot etc...) and access to perhaps the
largest collection of support libraries ever created. It all makes me
very happy, and thus far I have done several projects in Clojure and
it has not let me down in terms of either efficiency, scalability, or
concurrency management.

I just wanted to share my perspective and experience with you and
maybe something I have related helps you to make sense of things for
yourself.

HTH,
-- Duane

[Mike Benfield]

I think I got my head more or less wrapped around how to write in an
immutable style and how to think about recursion correctly by reading
SICP, so if you have time to spend on it maybe that would be an
option.

http://mitpress.mit.edu/sicp/full-text/book/book.html

As other posts say, just give stuff a new name. If you only need the
new data locally, as should be the case most of the time, just say

(let [w (conj v 4)]
; play with w
)

Sometimes you do

(let [val-1 (a-function a b c)
val-2 (b-function var-1)
val-3 (c-function d e val-2 f)]
(d-function val-3))

And of course think in terms of functions which return values rather
than procedures which mutate things.

[Andykirk]

On Jun 29, 1:35 am, Mike Benfield <mike.benfi...@gmail.com> wrote:
> And of course think in terms of functions which return values rather
> than procedures which mutate things.

Thanks Mike for your excellent concrete answer, and Paul for phrasing
just the form of coder's block I'm having.

[Rich Hickey]

On Jun 27, 6:17 am, Paul Drummond

I've added an essay to the site which I hope will help:

Values and Change - Clojure's approach to Identity and State.

http://clojure.org/state

Rich

[Duane]

Thanks, Rich. That was exceptionally eloquent and I believe it will
help a lot of people more easily grapple with the Clojure paradigm (as
it was very helpful to me).

I work at a SuperComputing center and have been thinking about how to
use Clojure on big clusters. So I am very interested in strategies
for distributed computing across processes. You mentioned Actors.
Prof. Gul Agha was on my dissertation committee so I am very familiar
with that approach :). I would really like to help move Clojure in
this direction. Once I have collected my thoughts more and done some
more research I will post some ideas and perhaps we can get a
discussion going about making this a reality.

Best,
-- Duane

[Scott Parish]

On Sun, Jun 29, 2008 at 11:32:41AM -0700, Duane wrote:

> You mentioned Actors. I would really like to help move Clojure in this

> direction. Once I have collected my thoughts more and done some more
> research I will post some ideas and perhaps we can get a discussion
> going about making this a reality.

I can't say i was the first to think of this, but i've been thinking
about how to integrate clojure and kilim[1]. At the moment i don't know
much about ASM, but it may not be too difficult to integrate the two
systems.

sRp

1| http://www.malhar.net/sriram/kilim/

[Duane]

I have not spent any time looking at Kilim but it appears interesting.

Thanks very much for the reference.

-- Duane

[Paul Drummond]

Hi Guys,

Wow! I have been away for the weekend and I've returned to this!
Thanks Rich for the essay - I am reading it now and along with all the
comments here (thanks guys!) I am slowly digesting everything. I am
at work at the moment so I can't say any more right now, I just wanted
to say thanks! Hopefully, I will be able to follow-up my original
post by the end of the day or early tomorrow....

[Paul Drummond]

Okay guys, here is part 2...

A while back I found a nice article about writing a simple webapp with
Lisp: http://www.adampetersen.se/articles/lispweb.htm

I attempted to convert this to Clojure using my own little web-server
built on top of Jetty and I very quickly ran into problems with state
and immutability. The article - like many lisp articles I have read -
uses a global list as the main data structure and provides several
functions for adding "entities" (games in the article) to the list,
editing them and removing them. I found converting this example to
Clojure problematic although at the time I was very new to the
language so I was obviously jumping ahead a little and I knew it.

Specifically, when it came to immutability I was stumped and ended up
doing crazy things with re-def'ing such as this:

(defn add-game [name]
(def *games* (conj *games* {:name name :votes 0})))

I knew this was evil of course, but when I tried to think of the
alternative(s) my eyes glazed over.....

I thought the only way to convert this type of program to Clojure
would be to move the global list *games* into some top-level function
and have the state maintained in the stack using recursion, which
doesn't fit well with web-app programming IMO. In many problem
domains and especially in typical Java enterprise programming, you
don't have a "main" top-level function that can be used to maintain
all your state - the "application server" or "web server" manages that
part doesn't it? Hmmm. Maybe not, - Oh here we go again! :) This
bit - right here - is where I get a mental block! It's something about
recursion and how it fits into the overall "shape" of typical
application programs - it stumps me for some reason. (If it later
becomes pertinent I will try to dig deeper into this but for now I'd
like to move on.)

So what about alternatives to recursion?

After reading Rich's essay on State I considered that maybe one could
write retro-games using refs? Assume for the purposes of this
discussion that the retro-games website only has one user so
concurrent access to the *games* structure isn't a concern. Would one
still write the program using refs? I always assumed refs/agents were
specialist concepts for use in highly concurrent programs so I
(naively, it seems) didn't consider them as a solution for this sort
of problem.

I think if someone could shed some light on the idiomatic way to write
something like retro-games in Clojure I would (hopefully) begin to see
some light at the end of the tunnel! [Fingers Crossed!]

Thanks,
Paul

[Christophe Grand]

Paul Drummond a écrit :

> In many problem
> domains and especially in typical Java enterprise programming, you
> don't have a "main" top-level function that can be used to maintain
> all your state - the "application server" or "web server" manages that
> part doesn't it?

I rather think that the application state belongs in the database. The
application logic reads some immutable data (user input and a snapshot
of some db rows), processes them and writes the result. You have one
mutation point (the writing) but everything else is functional.

> After reading Rich's essay on State I considered that maybe one could
> write retro-games using refs?

I think it's the way to go — thinking of it, if you were doing something
more ajaxy with heavy use of comet, in some cases agents may be used
instead of refs. Maybe.

> Assume for the purposes of this
> discussion that the retro-games website only has one user so
> concurrent access to the *games* structure isn't a concern. Would one
> still write the program using refs?

I would. I tend to use:
* vars for short-lived mutation, mainly as a way to convey contextual
data (eg current output stream, db connection, user data etc.)
* refs for synchronous long-lived mutation (ie for things that have to
be remembered between (functional) processings)
* agents for asynchronous long-lived mutation

This is how I use/understand Clojure's features, others may disagree. HTH

Christophe
--
Clojure and me http://clj-me.blogspot.com/

[Chouser]

On Mon, Jun 30, 2008 at 8:52 AM, Paul Drummond
<paul.drumm...@googlemail.com> wrote:
>
> I always assumed refs/agents were specialist concepts for use in
> highly concurrent programs so I (naively, it seems) didn't consider
> them as a solution for this sort of problem.

On the contrary, in Clojure especially refs but even agents are rather
pedestrian, and you're very likely to run into problems that can't be
solved without them. But it turns out they're pretty easy to use.

So go ahead and def your global *games* as a ref:

(def *games* (ref []))

And you can even have your add-game function, just use ref-set instead
of def, use an @ when you're reading the old value, and put it all in
a dosync:

(defn add-game [name]
(dosync
(ref-set *games* (conj @*games* {:name name :votes 0}))))

Or even better, use commute:

(defn add-game [name]
(dosync
(commute *games* merge {:name name :votes 0})))

And if you ever want to go massivly multi-threaded, you're already all
set.

BTW, you probably want to use a hash or map instead a list or vector
for *games*.

--Chouser

[Rich Hickey]

On Jun 30, 9:37 am, Christophe Grand <christo...@cgrand.net> wrote:
> Paul Drummond a écrit :> In many problem
> > domains and especially in typical Java enterprise programming, you
> > don't have a "main" top-level function that can be used to maintain
> > all your state - the "application server" or "web server" manages that
> > part doesn't it?
>
> I rather think that the application state belongs in the database. The
> application logic reads some immutable data (user input and a snapshot
> of some db rows), processes them and writes the result. You have one
> mutation point (the writing) but everything else is functional.
>
> > After reading Rich's essay on State I considered that maybe one could
> > write retro-games using refs?
>
> I think it's the way to go — thinking of it, if you were doing something
> more ajaxy with heavy use of comet, in some cases agents may be used
> instead of refs. Maybe.
>
> > Assume for the purposes of this
> > discussion that the retro-games website only has one user so
> > concurrent access to the *games* structure isn't a concern. Would one
> > still write the program using refs?
>
> I would. I tend to use:
> * vars for short-lived mutation, mainly as a way to convey contextual
> data (eg current output stream, db connection, user data etc.)

To the extent you are using binding to do this contextual stuff, then
it's not mutation, and is really the proper use of vars.

While set! on vars is thread-safe (because the var must be thread
bound), var set!s, and especially re-defs, should be extremely rare.

Rich

[Rich Hickey]

On Jun 30, 9:44 am, Chouser <chou...@gmail.com> wrote:
> On Mon, Jun 30, 2008 at 8:52 AM, Paul Drummond
>

> <paul.drummond.webm...@googlemail.com> wrote:
>
> > I always assumed refs/agents were specialist concepts for use in
> > highly concurrent programs so I (naively, it seems) didn't consider
> > them as a solution for this sort of problem.
>
> On the contrary, in Clojure especially refs but even agents are rather
> pedestrian, and you're very likely to run into problems that can't be
> solved without them. But it turns out they're pretty easy to use.
>
> So go ahead and def your global *games* as a ref:
>
> (def *games* (ref []))
>
> And you can even have your add-game function, just use ref-set instead
> of def, use an @ when you're reading the old value, and put it all in
> a dosync:
>
> (defn add-game [name]
> (dosync
> (ref-set *games* (conj @*games* {:name name :votes 0}))))
>
> Or even better, use commute:
>
> (defn add-game [name]
> (dosync
> (commute *games* merge {:name name :votes 0})))
>
> And if you ever want to go massivly multi-threaded, you're already all
> set.
>

Exactly. This is really the bigger point. If you wait until you have
threads to make your code safe and sound, you will never get it right.
Used as intended, you are always 'doing the right thing' in Clojure.

Your program will be better for it, even if you never have a second
thread.

Rich

[Paul Drummond]

So the missing piece of the puzzle for me has been refs/agents and the
realisation that they are a general mechanism for dealing with state
whether concurrency is a concern or not. Thanks to everyone who
helped me with this - It has been a sticking point for me for some
months now.

There is one closing point I'd like to raise, just in case there is
anything in it. Rich says in his essay on State and Identity:

"Use values as much as possible. And for those cases where your
objects are truly modelling identities (far fewer cases than you might
realize until you start thinking about it this way)"

Could you maybe expand on this a little Rich? The reason I have
struggled with immutability for so long is because I find *most*real
world programs model identity in some fashion so maybe I am still
missing something? Most *real-world* Clojure code I have written so
far - to me - is modelling identity. Maybe this is because I am
coming from an OO background where everything is an object so I am
blurring the distinction between identity and value.... Hmmmm. Maybe
I need to look into this a bit more now I understand things better....

Anyway - that said - I'm off to learn about refs :)

Paul.

[Rich Hickey]

On Jul 1, 5:45 am, Paul Drummond

<paul.drummond.webm...@googlemail.com> wrote:
> So the missing piece of the puzzle for me has been refs/agents and the
> realisation that they are a general mechanism for dealing with state
> whether concurrency is a concern or not. Thanks to everyone who
> helped me with this - It has been a sticking point for me for some
> months now.
>
> There is one closing point I'd like to raise, just in case there is
> anything in it. Rich says in his essay on State and Identity:
>
> "Use values as much as possible. And for those cases where your
> objects are truly modelling identities (far fewer cases than you might
> realize until you start thinking about it this way)"
>
> Could you maybe expand on this a little Rich? The reason I have
> struggled with immutability for so long is because I find *most*real
> world programs model identity in some fashion so maybe I am still
> missing something? Most *real-world* Clojure code I have written so
> far - to me - is modelling identity. Maybe this is because I am
> coming from an OO background where everything is an object so I am
> blurring the distinction between identity and value.... Hmmmm. Maybe
> I need to look into this a bit more now I understand things better....
>

Clojure's distinction between values and identities(refs/agent) is
going to force you to make this decision.

Say you want something to represent a point, you could say:

{:x 1 :y 2}

or

{:x (ref 1) :y (ref 2)}

The latter is a very silly thing - points are values and don't change.
One of the ways you can tell the use of identity is wrong is when no
one else refers to the ref.

Ok, maybe that's trivial and obvious (although that's what most OO
language give you by default).

Let's look at the infamous "Person" class:

{:first-name "Rich"
:last-name "Hickey"
:favorite-foods #{...}
...}

or:

{:first-name (ref "Rich")
:last-name (ref "Hickey")
:favorite-foods (ref #{... :eggplant ...})
...}

here too, by the "refs are not shared" metric, the latter is wrong.
But, you say, what if you change your name or stop liking eggplant?
The important thing to understand is that those things aren't me, they
represent some value of me. You would model my identity separately,
like this:

(def rich
(ref
{:first-name "Rich"
:last-name "Hickey"
:favorite-foods #{:pizza :eggplant}
...}))

If I stop liking eggplant, my identity simply has a different value:

(dosync
(alter rich assoc :favorite-foods
(disj (:favorite-foods @rich) :eggplant)))

which people sharing the same notion of me can observe like this:

user=> @rich
{:last-name "Hickey", :first-name "Rich", :favorite-foods #{:pizza}}

Hope that helps,

Rich