Lambda the Ultimate

The pattern comes from join calculus and consists of multiple joins reading from multiple shared inputs. No datum should be consumed by more than one join. So if we have J1 reading from X and Y, and J2 reading from Y and Z, then the sequence X, Y, Z fires J1, while the sequence Y, Z, X fires J2 (only). There is a relation of precedence between joins (or in more advanced settings between more complex objects that include joins), so each potential conflict (like X, Z, Y) falls back to the precedence (e.g., J1 < J2, so X, Z, Y fires J1).

If you think this example is too simple, try a cyclic one: add J3 reading from X and Z. Specifying different requirements for conflict resolving is left as an exercise for a reader :-)

So another quick suggestion to Peter for CTM2 (if I may) would be to at least use joins in examples. This has its appeal for the industry as well - joins are staples of workflow and process management.

A quick suggestion to PVR: If you ever do a second edition of CTM, might a section on databases/explicit transactions (as a way of addressing concurrency issues) be a worthwhile addition?

Section 8.5 is already about transactions, but it is more about understanding the concepts and how to implement them. Do you mean a section that is more about *using* transactions?

to at least use joins in examples.

Thanks for the suggestion, I'll keep it in mind. Can you recommend a good reference (from the join calculus or workflow literature) on the practical use of joins in the join calculus sense?

Can you recommend a good reference (from the join calculus or workflow literature) on the practical use of joins in the join calculus sense?

For an example of a workflow, see YAWL example 2 (click on workitems appearing in terminals to "complete" them). Actually, Example 1 is more focused - just a fork and a join, but it does not demonstrate non-monotonic nature of workflows to full extent (while Example 2 does - not only agents are able to "steal" workitems from each other, but also different paths of execution are possible, see actions D and H competeing for C6). This non-monotonic feel is very similar to Petri nets - looks like another suggestion :-)

I have wondered how naturally and efficiently Erlang-style concurrency would support the stream processing model being touted for the Cell processor. In Erlang, a message has to be fully constructed before being passed along.

How is it a problem that messages have to be fully constructed, as long as they coincide with atomic work units?

If they don't... well, can somebody come up with a convincing example why they absolutely cannot be made that way without degrading program structure?

Well, Tim says that Erlang "abjures the use of global data," and this isn't quite right.

It is actually completely wrong! Erlang's model is message-passing concurrency with global transactional shared state (the Mnesia database). Erlang by no means advocates a pure message-passing approach, but a multi-layered approach: pure functional on the bottom (the definition of an Erlang lightweight process, which may be augmented with state local to a process), message passing in the middle, and transactional shared state on the top. Mnesia is crucial for Erlang's high availability (fault tolerance for software errors). On the other hand, it is important that Mnesia itself is implemented using message passing. I.e., the underlying computation model is still message passing with a functional core (like chapter 5 of CTM).

I think dataflow concurrency addresses Tim Bray's desire to have two threads operating on the same structure.

An example of how nice this is can be found on page 470 of CTM: Figure 6.13 shows a parallel dataflow version of the classic Floyd-Warshall transitive closure algorithm. This version is derived in a trivial way from the declarative version of Figure 6.12, by adding thread statements judiciously.

Thanks for the pointer. I have a copy of CTM, and have made it through the first 4 chapters. I really need to spend more time in it. My statement was uncertain because of possible misunderstanding of Tim's statement. Anyway...

Oz first caught my eye when I was working on understanding Hypersets, and I happened to work through one of Oz's web tutorials... I quickly realized that bisimulation was included in the language, which was more than I could do with non-wellfounded data structures in Haskell.

I am rather interested in techniques that would make working with non-wellfounded data as easy as pattern matching on trees. I don't have any ideas how, yet...

What is a "non-wellfounded data structure"?

What is a "non-wellfounded data structure"

In context, Leon means a data structure representing a non-wellfounded set.

In practice, this would mean a datastructure that contains one or more circular references, or one or more infinite chain of members (say an infinite list comprehension).

I quickly realized that bisimulation was included in the language, which was more than I could do with non-wellfounded data structures in Haskell.

I'm not sure what you mean, Leon, by Oz having bisimulation built-in: do you mean unification?

I could see that might work for simpler examples, but I'd be worried with hairier instances. Interesting idea though.

CTM calls it entailment. Maybe there is a difference between bisimulation and entailment, but my understanding of Oz isn't that deep yet.

For example:

local A B C A1 A2 B1 B2 C1 C2 in
   A = a(B C)
   B = b(C A)
   C = c(A B)
   A1 = a(B2 C1)
   A2 = a(B2 C2)
   B1 = b(C2 A2)
   B2 = b(C1 A1)
   C1 = c(A1 B1)
   C1 = c(A2 B1)
   {Show A==A1}
end

will print out "true"... there are multiple representations of the same non-wellfounded structure. This is a major improvement in observability versus analogous structures in Haskell, which can only observe finite prefixes of non-wellfounded structures.

However, I also don't think it's enough to make direct representations of non-wellfounded data generally useful in Haskell and Oz.

I used induction and bisimulation as terms for these two concepts but by know I think tree-like and graph-like are the better definitions.

More specifically, in the mathematical sense, most graph-like [data]structures are well-founded (there is an ordering such that each non-empty set has a smallest element), thus the induction/bisimulation distinction is not correct.

To some extend, the standard bisimulation proof [scheme] to show that structures describe similar shapes, entailment, is correct because you have well-founded sets.