Lazier Than Lazy

While reading Programming Clojure I read that  lazy sequence can break recursion and prevent stack overflow. This wasn’t completely intuitive to me. How could changing the type of a sequence (eager or lazy)  change the way the stack is used? Let’s dig into it.

Let’s start first with the example given in the book:

(declare replace-symbol replace-symbol-expression)

(defn replace-symbol [coll  oldsym newsym]
(if (empty? coll)
()
(cons (replace-symbol-expression
(first coll) oldsym newsym)
(replace-symbol
(rest coll) oldsym newsym))))

(defn replace-symbol-expression [symbol-expr oldsym newsym]
(if (symbol? symbol-expr)
(if (= symbol-expr oldsym)
newsym
symbol-expr)
(replace-symbol symbol-expr oldsym newsym)))

(defn deeply-nested [n]
(loop [n n
result '(bottom)]
(if (= n 0)
result
(recur (dec n)(list result)))))

The function deeply-nested produces a structure like this

((((((((((bottom))))))))))

And the function replace-symbol can be used to change bottom to something else

user=> (replace-symbol (deeply-nested 10) ‘bottom ‘other)
(((((((((other))))))))))

And we indeed get a stack overflow if the nesting is too big

user=> (replace-symbol (deeply-nested 1000) ‘bottom ‘other)
#<CompilerException java.lang.StackOverflowError (NO_SOURCE_FILE:0)>

And if I slightly change the replace-symbol function to use a lazy sequence:

(defn replace-symbol [coll  oldsym newsym]
(lazy-seq (if (empty? coll)
()
(cons (replace-symbol-expression
(first coll) oldsym newsym)
(replace-symbol
(rest coll) oldsym newsym)))))

I indeed prevent the stack overflow from happening.

What happens actually is that lazy sequences are just like futures. The sequence is realized only when the sequence is used. If the consumer of the loop consumes the value sequentially, this indeed breaks the recursion. Let’s consider a sequence which is recursively defined as ( cons 1 (cons  2 ( cons 3 (list 4) ) ) ), and a function count defined with

(defn count-1 [col]
(loop [n 0 c col]
(if (= (first c) nil)
n
(recur (inc n)(rest c)))))

An attempt to count the number of items by traversing the sequence will produce the following call stack:

count-1
count-1, cons
count-1, cons, cons
count-1, cons, cons, cons
count-1, cons, cons, cons, list

(Count-1 itself is not recursive because it uses the recur special form to perform tail call optimization, which is not possible at the JVM level)

If the sequence is lazily defined, then the call stack will be as follows:

count-1
count-1, cons
count-1, cons
count-1, cons
count-1, list

The lazy sequence are realized one after the other, but each realization returns in the count-1 function.  This sequence is actually much closer to a generator, producing one item at a time.

This is the heart of infinite sequences also, as for instance in:

user=> (take 15 (cycle [1 2 3 4]))
(1 2 3 4 1 2 3 4 1 2 3 4 1 2 3)?

The special form lazy-seq in Clojure is actually a macro.

user=> (macroexpand-1 '(lazy-seq (list 1 2)))
(new clojure.lang.LazySeq (fn* [] (list 1 2)))

We clearly see here the parallel between future and lazy sequence. Both simply postpone the execution of a function at the time it is really needed.

Persistent Data Structures

I read recently the post “Persistence is a subset of immutability” and was then surprised to discover that Clojure shared the exact same concept of “persistent data structure”, which turned out to be a concept common to all functional language.

Still, I don’t like this terminology of “persistent data structure”.

“A persistent data structure is a data structure which always preserves the previous version of itself when it is modified; such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure.”

This definition is completely confusing to me. One the one hand it says that the structure is immutable and that invoking an operation on such a structure produces a new structure. This is ok to me.

One the other hand, it speaks about some form of versioning, as if both the old and the new version had some relationship. This implies then a notion of identity.

“An identity is indeed a logical entity which associate a series of different values over time.”

This is not ok. Both structures are maybe related implementation-wise (the newest structure being merely a diff over the previous one), but from point of view of the client, both structures are unrelated. From point of view of the client, data structure are immutable. Period.

Heraclitus, a greek philosopher, pioneered the concept of identity and state with his famous saying: “You can not step twice into the same river.” He recognizes the changing of objects with the flow of time.

This corresponds to the mutable references in Clojure. References are the only construction that can be mutated.

If the state of an entity changes over time, Einstein was the first one to recognize that the notion of simultaneity is not absolute but depend on the observer.

This corresponds to the transactional memory model in Clojure. At a given time, two different observers will observe two different states of the same entity.  We can indeed see transactional memory as a kind of special asynchronous replication: each observer (thread) has a complete snapshot of the world and synchronization between the snapshots happens at commit time. The sequence of state that can be observed is however always the same and the causality between events is preserved.

More links

Playing with Macros

For somebody with experience with Lisp of functional programming, all this will seem trivial. But I needed to refresh all this, so here  is the result of my small investigation of Clojure macro and how it relates to lazy evaluation and quoting. I also make a few test on the  difference between macro and functions.

First I started with a global variable, and a function that produces a side-effect (incrementing the value) and then return the value of the global variable. It is then trivial to see when stuff gets evaluated.

(def glob-1 10)
(defn side-effect [] (do (def glob-1 (inc glob-1)) glob-1 ))

Then to clearly see the difference between macro and function I defined these two ones:

(defmacro print-twice [exp] `(do (side-effect)(println ~exp)(println ~exp)))
(defn print-twice-2 [exp] (do (side-effect)(println exp)(println exp)))

Here is the result of the macro:

(print-twice glob-1) "11 11"
(print-twice (side-effect))  "13 14"

We clearly see how the macro expands. In the 2nd call, the  side-effect is executed 3 times as expected. We can now try the function:

(print-twice-2 glob-1) "14 14"
(print-twice-2 (side-effect)) "16 16"

We see that glob-1 is evalued before being passed to the function. As a consequence, 15 is never printed! The side-effect passed as parameter in the 2nd call is evaluated once, before the actual function is run.  After these two calls, glob-1 has a value of 17.

To have a side-effect which doesn’t hard-code the reference to glob-1, we can turn it into a macro that takes a variable as parameter.

(defmacro side-effect-1 [v] `(do (def ~v (inc ~v)) ~v ) )

The result are (of course) then similar:

(def glob-1 20)
(print-twice glob-1) "21 21"
(print-twice (side-effect-1 glob-1 ))  "23 24"
(print-twice-2 glob-1) "24 24"
(print-twice-2 (side-effect-1 glob-1 )) "26 26"

OK, that’s great, but quasi-quoting isn’t limited to macro. I can also do it in a function.

(defn print-twice-3 [exp] `(do (side-effect)(println ~exp)(println ~exp)))

The result of this function is an expression. It needs to be evaluated to produce the actual result.

(def glob-1 30)
(eval (print-twice-3 glob-1)) "30 30"
(eval (print-twice-3 (side-effect))) "32 32"

We clearly see here again that the semantic of the parameters is not the same between macro and function. The parameter glob-1 is evaluated before being passed to the function, and as a consequence ~exp expands twice to a literal value of 30, not the symbol glob-1 as in a macro, and we don’t get “31 31” as we would with the macro. The same happens for the 2nd call.

EDIT

Other links related to macro and meta-programming:

Playing with Agents

Clojure is a programming language with a rich set of features. The rationale behind Clojure and its set of features can be summarized with these 4 points:

  • functional programming (which favors immutable structure)
  • polymorphism, with global mutable reference, dynamic typing and multi-method dispatch
  • transactional memory to see consistent snapshot of the world
  • advanced concurrency mechanisms at the language-level (CAS, agents, watcher)

I already discussed a bit the TM part in my previous post. Here I move to watcher and agents, a mechanism to run  asychronous tasks in separate threads .  Agents are like workers in the thread pool pattern, they execute tasks in a sequential way one after the other. Submitting a task to an agent must be done in a transacted section (dosync). Waiting for the agent to complete can be achieved with special instructions (wait agent-name). Watchers are special agent, which will run a task each time a reference is changed. The task to run is specified when the watcher is constructed.

Watchers

Here is a version of my test, where each update in the shared map triggers the watcher. When the 100 occurrences have been counter, the watcher prints “OK”.

(ns org.ewe.sharedMapWatcher (:gen-class))
(def my-watcher (agent 0))

(defn my-watcher-action [current-value reference]
(let [new-value  (inc current-value)]
(if (= new-value 100) (println "100 words have been counted"))
new-value
)
)

(def store-map-ref (ref (sorted-map)))

(defn store-it [hash]
(dosync
(let [store-map @store-map-ref]
( if (contains? store-map hash)
( let [count-ref (store-map hash)
new-count (inc @count-ref)]
(ref-set count-ref new-count)
)
( let [new-ref (ref 0)]
(add-watcher new-ref :send-off my-watcher my-watcher-action)
(ref-set new-ref 1)
(ref-set store-map-ref
(assoc store-map hash new-ref)
)
)
)
)
)
)

(defn build-list [n]
(if (= n 0)
(list (Thread. #(store-it n)))
(conj (build-list (dec n)) (Thread. #(store-it (mod n 4))) )
)
)

(defn -main []
(time (do
(let [NUM 100
threads (build-list NUM)]

(dotimes [iter NUM] (.start (nth threads iter)))
(dotimes [iter NUM] (.join (nth threads iter)))

(await my-watcher)

(println "count = " (count @store-map-ref))
(doseq [[hash count-ref] @store-map-ref]
(println hash " -> " @count-ref )
)
)
)
)
)

Message passing

Agents are asynchronous by nature. We may be tempted to think of them like actors in the actor model, but they aren’t. Quoting another post, “an actor is a process with a mailbox which dequeues and processes messages individually. The actor process contains all the logic for processing messages. […] Clojure’s agent inverts ownership of message handling logic: agents are submitted functions which are stored in a mailbox and then executed in order.”

Agents can be used to create fully asynchronous processing model. Agents can be passed to other agent function to create chain of message passing. It is for instance possible to send a function to an agent and specify itself as the callback agent (the *agent* variable refers to the currently executing agent).

(ns org.ewe.asyncAgent2 (:gen-class))
(import '(java.util Date))

(def agent-1 (agent 0))
(def agent-2 (agent nil))

(defn print-time [s]
(println (. (new Date) (toString)) s ))

(defn callback [current-value result]
result
)

(defn compute-and-callback [current-value callback-agent]
(let [result 1234]
(Thread/sleep 10000)
(send callback-agent callback result)
)
nil
)

(defn async-compute [current-value]
(send agent-2 compute-and-callback *agent*)
current-value
)

(defn perform []
(dosync (send agent-1 async-compute) )

(await agent-2)
(print-time "agent-2 is over")

         (await agent-1)
(print-time "agent-1 is over")

(println "agent-1:" @agent-1)
(println "agent-2:" @agent-2)
)

(defn -main []
(time (perform)
)
)

Producer-consumer

Producer consumer is a popular approach to schedule tasks concurrently. The shared list of items acts then as a coordinator between the producers and consumers. Producer-consumer comes in two flavors: fully or partially transactional.

In fully transactional mode, the consumptions of a message is entirely transacted. If the consumption failed (e.g. error during processing), the item remains in the queue. Traditional lock-based implementation don’t enforce this. The shared list is correctly synchronized, but once an item has been popped, it is removed definitively. On the other hand, messaging systems (JMS, etc.) do propose a fully transactional model.

Fully transactional producer-consumer implementation becomes easy with a TM. The problem however (in my understanding) is that no two items can be fetched and processed concurrently, as it would result in a concurrent modification of the shared list of items. The performance of such an system would be the same as having a completely sequential system. Of course, agents could be used to decouple item push and pop from their actual treatment (by mean of asynchronous threatment), but then the system isn’t fully transactional anymore. If the agent fails, the item is lost.

Conclusion

“All concurrency issues boil down to coordinating access to mutable state. The less mutable state, the easier it is to ensure thread safety.”

— Java Concurrency in Practice (from Bill Clementson’s blog)

Transactional memory and aysnchronous mechanism are means to coordinate access to shared data. But they still don’t solve the problem of shared data on their own. I will need to do more experiment to figure out exactly what kind of problem are really simplified by the agent, the actor and the TM models.

A First Look at Clojure

Transactional memory (TM) offers the promise to simplify concurrent programming. Lock-based programming, the de-facto standard, is indeed hard to get right. Common problems with lock-based programming are deadlock, priority inversion, and lack of composition. Lack of composition refers to the fact that two structures correctly synchronized do not necessary compose to a new structure itself correctly synchronized. Transferring amount between two accounts is an example: even if the account is synchronized correctly, the transfer is not safe.

TM is however not a silver bullet neither.  One major open point of TM implementations is how to ensure progress (e.g. no livelock) of the system. TM is indeed like optimistic locking. The problems of contention and starvation are still present. Non-blocking algorithm can offer different level of guarantee regarding the system-wide progress.  Also depending on the particular implementation, one process may still read inconsistent state, which could lead to inappropriate decisions. Some TM use multi-version concurrency control to solve this issue.

As TM have become more and more mature, we see now a shift from distributed system area to the language area. How can TM be integrated into existing language nicely? What are the abstractions that are required?

Language support

Here are a few questions related to language support:

  • Operational – what is the exact semantics of the TM? Does it provide snapshot isolation? What is the effect of exception with transactions? How can we facilitate the usage of blocking IO (normally prohibited) in transactions? How non-transacted and transacted code interoperate?.
  • Transaction demarcations – How transactions can be controlled (e.g.  start, stop, but also retry)? Are there other parameters to support (e.g. retry timeout)?
  • State manipulation – How shared state is accessed and modified? What are the mechanisms and data structure?

State modification – conceptual views

I tend to think there is two ways to see shared state manipulation. One is the Clojure way, were you deal with immutable data but mutable references. Mutating shared data is always done through a reference, and also part of a transaction.

Another view, is the object database view (also the ORM view), were a transaction is a snapshot of the objects which can then be manipulated as usual.

Let’s consider a very simple example:  a shared map <String, Integer> is supposed to count the number of occurrence of a particular word. While indexing, document are split in smaller part and processed concurrently. The map needs then to be updated concurrently.

immutable state + mutable ref  object
(defn store-it [word]
(dosync
(let [store-map @store-map-ref
old-count (store-map word)

new-count (if old-count
(inc old-count) 1)]
(ref-set store-map-ref
(assoc store-map word new-count)
)
)
)
)

storeIt( word )
{
transaction
{
oldCount = storeMapRef.get( word, 0 );
storeMapRef.put( word, oldCount+1 );
}
}

State modification – contention

As mentioned already, TM is not silver bullet. We still need to think of the intent of our code from a multi-threaded perspective.  In the example above, the complete map was considered as one piece of shared data. The concurrent  modificatin of the occurence count for two different words would conflict and one of the transactions would be rolled back. To have finer grain control and reduce contention (Disjoint-access parallelism), we can consider the occurrence count not as a primitive, but as a reference to a counter.  The map is altered only when a new word is inserted and a new counter starting at zero is created. Incrementing the occurrence of a word is a modification of the counter, which means that two counter can be incremented concurrently.

immutable state + mutable ref objects
(defn store-it [word]
(dosync
(let [store-map @store-map-ref]
( if (contains? store-map word)
( let [count-ref
(store-map word)
new-count
(inc @count-ref)]
(ref-set count-ref new-count)
)
(ref-set store-map-ref
(assoc store-map word (ref 1))
)
)
)
)
)
storeIt( word )
{
transaction
{
if( storeMapRef.contains( word ) )
{
counterRef = storeMapRef.get( word );
counterRef.inc();
}
else
{
storeMapRef.put( word, new Counter(0) );
}
}
}

Conclusion

TM is indeed a promising way for concurrent programming. There are open points to watch, and more evidence is needed on the performance of TM-based system in real case. Understanding of the concurrency at the applicative level is still required even with TM. Poorly designed application may result in system with high contention even with TM. The transaction facilities are there but the application must still use them in a consistent way to implement its very own logic. Different conceptual views exist to access shared data with TM. Further experiment are needed to decide which one is better.

EDIT

Interesting pointers: