Lambda the Ultimate

Not to mention SQL is not Turing-equivalent.

Also, SQL appears as completely undeclarative. What was meant by shared state in SQL? Host variables in various bindings of SQL to imperative languages? Cursors? Transaction isolation?

Actually, each vat in E is a thread. Within a vat, one viewpoint is that there is a single thread, but another viewpoint is that there are multiple threads with a deterministic scheduler.

The discussion E has no threads uses the term threads to refer to shared-state concurrency, which is indeed a disaster unless it is strongly constrained.

Within a vat, one viewpoint is that there is a single thread, but another viewpoint is that there are multiple threads with a deterministic scheduler.

I don't believe this is true. Within a vat, one object can steal the CPU (infinite loop) and the only way to recover is to kill the entire vat. I'm not sure how you can view this as deterministic scheduling with multiple threads.

It's not preemptive. Preemption is a source of nondeterminism, which is bad for security reasons (covert channels).

But stealing the CPU is another security problem: denial of service! I think that the E philosophy is that objects inside a vat should not be considered completely isolated from each other. From the outside, a vat should be considered as a single "aggregate" for security reasoning. True isolation is only possible between different vats.

It's not preemptive. Preemption is a source of nondeterminism, which is bad for security reasons (covert channels).

But stealing the CPU is another security problem: denial of service!

I agree (at least with the last point), but my point is that there is no observable concurrent execution, which seems to contradict your assertion that a vat can be considered multiple threads with a deterministic scheduler. The lack of interleaved execution between objects implies no schedule, simply co-operative yielding. I'm just trying to reconcile your statements of E with what I know of E. Perhaps we have a terminology mismatch on 'threads' and 'schedulers'.

As for preemption, I haven't read anything about covert channels via the scheduler, so if you have any links I'd be very interested. As a final thought, cover channels aren't much of a concern considering we can't even properly isolate overt communication yet (on a mainstream platform at least, so E and friends don't count ;-) ). Joe-E may be the closest to achieving this.

binstock: It seems that nearly every branch ends with Oz and Alice. Is this diagram intended to promote these languages or completely capture the state of the universe of language paradigms?

Are those two goals mutually exclusive? Have you used either Oz or Alice ML?

binstock: Finally, the imperative programming line looks thin. Surely, the distinguishing features between the various imperative paradigms are larger than the presence/absence of closures, threads, and logs, woudln't you say?

Would you? I'm not Peter, but I'll offer my opinion that talking about "various imperative paradigms" is an oxymoron. Some will say that object-orientation is a distinct imperative paradigm, but that's problematic because objects are trivially modeled with closures and don't necessarily require mutation. So from my POV, the imperative programming line looks thin because it is. I don't think that implies a value judgment necessarily; you can make the point that once you have first-class functions and mutable state you can macro-represent almost anything else, e.g. delimited continuations. Or you can indeed view it somewhat pejoratively and say that while you might be able to do that, it's difficult and error-prone relative to having a more orthogonal feature set that might be easier to reason about and treating mutable state as one more extremely powerful, easily abused, hard-to-reason-about feature. The diagram as presented supports both interpretations (and more!) equally well, so I think it would be more fruitful to concentrate on some issues of accuracy that have already been raised, e.g. SQL not being Turing-equivalent, E not having "threads" (but perhaps "threads" is really just shorthand for "concurrency constructs," in which case the characterization of E is accurate), etc.

Update: It's worth reiterating that this diagram is derived from the exposition found in Concepts, Techniques, and Models of Computer Programming, which uses Oz as its vehicle in essentially the same way that Structure and Interpretation of Computer Programs uses Scheme. Unlike SICP, however, CTM provides an extensive analysis of how the paradigms introduced appear and are used in other languages such as Java, Haskell, and Erlang. CTM builds up its definition of Oz by starting with a tiny kernel language and very gradually adding features until the kernel is full Oz, needing only syntactic sugar in order to be the "real" Oz. The result is that each new kernel feature is strongly motivated by a combination of comparison to other languages and the requirement that the new feature not be implementable by other means without requiring non-local changes to the code. In this way, it becomes easy to understand why Oz is what it is and, crucially, why it really is a multiparadigm language with a level of orthogonality that other multiparadigm-in-practice languages, e.g. C++ and OCaml, unfortunately lack. I cannot recommend either the book or the language highly enough.

Well, FWIW, my first impression was also, "Is this intended frame the totality of programming paradigms in such a way as to make Oz and Alice always as the ultimate language?" (Actually, that's a sugar-coating of my initial impression.)

Whether or not that was the intention, I think it's perfectly fair to say that that's how this diagram comes across. At least to me.

So what if it is? That would only seem to be problematic if the framing were dishonest, which is why I asked the previous poster if he or she had actually used Oz or Alice.

Not trying to be obnoxious, but "propaganda" was the first word that popped into my head when I saw the chart. It seemed to be implicitly defining "programming paradigm", as "something in Oz/Alice". It's a smell.

I could say "what about X" for any number of X (as others are), and one could reply with "well, X is not a *paradigm*, it's something else". Ok.

As was wisely mentioned by another poster, perhaps leaving out the langauge names would make it feel less so. (I'd hardly describe Java as C with closures, anyway.)

snively: so I think it would be more fruitful to concentrate on some issues of accuracy
You must have missed the second line of my post.

snively: I cannot recommend either the book or the language highly enough.
Awright, it's on my to-explore list. Thx for the heads-up. Back to the mines. :-)

My interpretation of the vertical axis is the reverse of the usual in Hasse diagrams - whenever a < b, then a lies higher than b (or one can define a < b to mean "language a has all features of language b" to restore the usual Hasse diagram convention).

Not sure what the vertical axis means. Is it just addition of features, or is there some order that's not apparent?

The order is idiosyncratic. It is based on the 'creative extension principle' (appendix D in CTM), but the choice of what features to add and in which order is a personal one. Other orders are certainly possible, and I would be very happy to see someone propose another one!

Java does not currently have closures.

Java can be implemented in a language with closures and explicit state. I.e., even though it does not give the programmer full access to closures, it does give some access.

It seems that nearly every branch ends with Oz and Alice.

Yes, that's a bit unusual (although FRP and STM are not supported natively in Oz or Alice), but I don't know of other languages that are multiparadigm. I define a language as multiparadigm if one can program in each paradigm without interference from the other paradigms. It's not sufficient to implement many programming concepts. E.g., Common Lisp contains many concepts, but it is not multiparadigm in this sense.

Note that there are several languages that are dual paradigm. That seems to give very nice results. For example, Prolog implements both logic programming and imperative programming. Modern constraint modeling languages (like Comet and Numerica) improve upon Prolog: they are both constraint languages and object-oriented languages. The constraints are the engine and the object orientation is for structuring problems.

Then what about polytypic programming (a.k.a. "even more generic")?

This leads me to the following observation - while looking at the diagram I didn't find any features that require static typing - may this warrant some qualification to the generality of the diagram?

I'd say it depends upon whether you can identify a programming paradigm that requires static typing. I can't. "Generic" or "polytypic" programming seems to me to be a kind of cross-cutting concern that can be applied to functional, object-oriented, imperative... programming. Indeed, the fact that the leaves of the tree tend to be occupied both by Oz and Alice ML reinforces this impression.

I'd say it depends upon whether you can identify a programming paradigm that requires static typing.

Which again depends on what we call a programming paradigm. From what you say, I will take a liberty to infer that none of the following is:

1. Polytypic programming
2. Metaprogramming
3. Aspect-oriented programming

Should we take a step back and define what's in the name? For example, Wikipedia defines it as follows: "A programming paradigm is a fundamental style of programming regarding how solutions to problems are to be formulated in a programming language".

What about object domain specific languages? Maybe this is just an implementation dependent and Ruby community culture thing. Special syntax for common objects such as /RegularExpressions/, [A,r,r,a,y,s], and {H=>a, a=>s, s=>h} tables is encouraged. As Ruby matures it will be interesting to see if all objects have a domain specific language attached to them.

We must define our terms, certainly. Since the diagram is explicitly inspired by CTM, I'll use the definition from CTM. Unfortunately, my copy of CTM is currently on loan, so we'll have to wait for its return, or for some other kind soul to post the definition from CTM, before we can really view the diagram in the context of that definition. That's not to say that Wikipedia's is bad/wrong; I merely wish to relate the diagram to its source of inspiration, at which point we can discuss whether that source is reasonable or not.

Quoting from the opening page of the Preface:

"A computation model is a formal system that defines how computations are done. There are many ways to define computation models. Since this book is intended to be practical, it is important that the computation model be directly useful to the programmer. We therefore define it in terms of concepts that are important to programmers: data types, operations, and a programming language. The term computation model makes precise the imprecise notion of "programming paradigm." The rest of the book talks about computation models and not programming paradigms. Sometimes we use the phrase "programming model." This refers to what the programmer needs: the programming techniques and design principles made possible by the computation model."

whether you can identify a programming paradigm that requires static typing

Typing is orthogonal to what the diagram expresses. Typically, each paradigm can be done with different styles of typing (varying degrees of static or dynamic typing). The orthogonality is not perfect: typing can affect expressiveness. I would be happy to see a diagram that takes the influence of typing on expressiveness into account!

Aspects are also orthogonal to the diagram. Aspects are parts of a specification (a program does A /\ B /\ C, etc., where A is the functionality, B is an aspect, C is an aspect, etc.), so they apply to all paradigms. Aspects are certainly not limited to the 'aspect' construct in AspectJ!

FWIW, when I think of multi-paradigm languages, the two PLs that have the most coverage of paradigms would be Scheme and Oz.

As for the diagram itself, I think a better perspective is to ignore the particular programming languages that are attached to the nodes - as that tends to evoke passion. The better question is whether PvR has managed to capture the main paradigm forks and the relationships between them? Once the main paradigm tree is mapped out, then you can assign PLs to the nodes at leisure.

A distinction that I think is important (but others might not) is between languages with support for paradigms that is "built in" or "first class" in some sense that is admittedly hard to define crisply, vs. offering facilities to implement such paradigms if you want them. From that POV, Scheme is a fascinating language, lacking built-in support for objects, concurrency, goal-directed evaluation, laziness, etc. but making it easier than in any other language I know that lacks these features to add them on—which I think is a great testament to the power of lexical closures, delay/force, call-with-current-continuation, and macros.

So I'm not sure that I agree that Scheme is particularly multiparadigm, but I would definitely agree that it deserves calling out distinctly for providing a much better foundation for implementing multiple paradigms than any of its cousins other than Oz and Alice ML.

This poses the question: what exactly are those foundations which make it possible/easier adding paradigms? Is it first-class functions plus macros? Why is Scheme/Lisp particularly good for implementing paradigms? Because of its macros, so the language itself can be extended?

Needless to say that Scheme/Lisp macros where already discussed at LtU (e.g., see here, here, and here)

IMHO, the crucial things about Scheme are the ones I listed above: first-class functions, lexical closures, delay/force, call-with-current-continuation, and syntactic extensibility. Remove any of them and you do significant harm to Scheme's ability to implement multiple paradigms. IMHO, the real win in terms of expressive power is, of course, call-with-current-continuation, which is known to be able to express any known control structure at all. Strictly speaking, of course, you can live without it and implement a CPS-conversion macro, but I think we've already stipulated that we're talking about making things easy as opposed to making things possible. Historically, I think we can argue that Scheme is important because it deliberately attempts to add extremely little sugar to the lambda calculus, leaving the addition of more sugar to the user. This view is, of course, controversial, as the status of R6RS, I think, underscores.

TCO *and* first-class continuations are what makes it possible for so many control operators to be macro-expressible in Scheme.

One issue I have with call/cc is that its uses often don't seem to compose well, nor is the way they should compose obvious, a priori. For example, what should happen when I use a green threading library and a backtracking search one, both implemented with (vanilla, undelimited) continuations?

call-with-current-continuation, which is known to be able to express any known control structure at all

Assuming presence of mutable cells, of course.
Also, as we are discussing things that are easy as opposed to possible, call/cc may be not the best atomic unit for building control structures (some delimited continuation structures may be more handy).

Where is SNOBOL and Icon. Both are imperative languages that has some form of backtracking. And of course both Oz and Alice has those features to, even thougt i havent ever seen them used together. But I don't think eihgter of them reverts destructive updates on backtracking. You could use Haskell and combine the list monad with the STM monad or something.

I wholeheartedly agree that Icon (I never used SNOBOL) fits nicely somewhere in the imperative nonmonotonic logic branch.

LaLonde and Van Gulik implemented backtracking in Smalltalk: http://dl.acm.org/citation.cfm?id=62094

The tl;dr version is that Smalltalk reifies the call stack as a list of context frames, and gives access to the currently executing context through the special variable thisContext. This boils down to "call/cc + mutable cell".

Can you define what these terms mean?

I am thinking about the common usage of analytic and synthetic. Analytic is the easy one. The ordinary use of the word in math, science and engineering seems appropriate. An analytic system is one in which everything is defined in terms of everything else. This is the accepted way to understand formal logic, Prolog, and pure functional programming. The left side of the chart is certainly analytic.

Now for the hard part. As you probably know there is an unresolved debate in philosophy over the distinction between analytic and synthetic. This is an interesting language issue and it does have something to do with computer language. But as I will argue it is bogus with respect to labeling the chart.

The commonsense use of "synthetic" or synthesis is "putting together" or "acting out". It is synonymous with state. Imperative programmers will understand exactly what it means. This is an extremely practical and useful definition that should not be held hostage by unresolved philosophical issues.

The use of "no state" and "stateful" is confusing and misleading. Functional programs can and do use state, and even when we achieve perfect declarative-ness, the machine that solves the problem is certainly stateful. "Imperative" systems can and must also be both stateful and functional. As you have said clearly the chart is about paradigms, state does not define any paradigm, and paradigms can be used together.
Edit: State defines a system and a computer is a system.
Edit: I also have a problem with the term "declarative". The left side of the chart is certainly declarative, But synthetic systems can also be declarative of their synthesis. Thus both sides are declarative.
Edit: The essence of the link above is that analytic and synthetic are not separate, absolute categories but points of view that tend to overlap. In other words they are separate paradigms that tend to overlap in practice but not as points of view. This should be the implicit meaning of the chart.

The use of "no state" and "stateful" is confusing and misleading.

The meaning is simple: "no state" means the kernel language has no explicit state and "stateful" means the kernel language has explicit state. Functional languages do not have explicit state (in their intended use as pure languages). Whether or not the underlying machine has state or not is irrelevant.

The meaning is simple: "no state" means the kernel language has no explicit state and "stateful" means the kernel language has explicit state.
Since you are taking a rather technical point of view about this why not point that out in the chart. On the left "no state in the kernel language", and on the right "state in the kernel language".

For someone who thinks about systems and state, states do not come and go as we please. States are subject to morphisms, they change but they don't go away. A functional language is simply a morphism of the states to the stack. A system always includes both the language constructs and the stack. People who think this way can be baffled and confused by "language centric" thinking that seems to abolish systems theory. Not that that is anyones real intention.

For someone who thinks about systems and state, states do not come and go as we please.

This refers to a different definition of "state", from a different context. Peter's use of the term "state" in the diagram can be considered shorthand for "mutable state" or "updateable state". It's standard usage in the PL theory and functional language context, and doesn't imply anything about incompatible uses of the term in other contexts.

What about the issue of SQL being labeled "Turing Complete"

There is no SQL in the updated version of the diagram (replaced by "SQL bindings"). That's a bit slippery, as there are many different bindings even for one host language, and a binding is not a language anyway.

I see "Prolog & SQL" on the left hand side of the diagram. Don't you?

The updated diagram also has an explanation of state, where I summarize why monads are the weakest form and why it's important for state to be named, concurrent, and support nondeterminism. Different languages have state with different combinations of these three properties.

Haskell as practiced (if not Haskell 98) has had support for cells via the IO and ST monads for a long time. The ST monad is also easy to give a naive implementation in a dynamically-typed language and can be implemented in a statically-typed language with a sufficiently powerful type system (essentially, one that can prove that if you're holding a reference to a cell then you know the type of the value held in it).

It's also possible for monads to support concurrent state (in fact, the IO monad does this) and nondeterminism. The limits are largely on what can be implemented purely with any real kind of efficiency, not on what the monad concept can introduce to a language. This raises the question of whether monadic pure functional programming - or some generalisation thereof - deserves recognition as a separate paradigm, though I appreciate that it would likely make something of a mess of your existing diagram.

It's also possible for monads to support concurrent state (in fact, the IO monad does this) and nondeterminism.

Well then we're no longer functional. A "monad" is like a magic box into which we can cram anything. The support for concurrency and nondeterminism does not come from the original monad idea. Rather, the monad is used as a foundation on which to add other concepts. The monad is by no means essential for this. These concepts can be added in other ways. What monads give you seems to be a kind of separation of concerns: you can separate the nonfunctional concepts from the purely functional part of the program.

You could talk about "adding monads" in the sense of monads definable within an existing language. In that sense you might say "monads can provide state or continuations in a pure language".

You could also talk about "adding monads" to a language in the sense of adding a new primitive type constructor that is mathematically a monad. In that sense just about anything can be provided as a monad. If you preserve your favorite semantic equality on non-monadic code you might even claim that your language is still "pure", and say "monads can support concurrent state and nondeterminism".

The interesting thing about adding "non-functional" primitives as monads is that it is relatively easy to do it without spoiling your existing semantic equivalence on pure code.

You can fit just about anything into a monadic interface, because semantic equivalence for pure code with uninterpreted functions can't prove your monad operations shouldn't be order-dependent, non-idempotent, or at all well-behaved. Binding results from monadic computations is syntactically distinct from let-bindings, so you hardly have to worry about breaking referential transparency, if you take that to mean the ability to safely inline let-bindings (if you are providing something like reflection you might need some extra semantic dodges, like claiming to nondeterministically return code semantically equivalent to the function being inspected).

You can fit just about anything into a monadic interface

Exactly. Monads provide separation of concerns. They are a programming technique (possibly supported by syntax for ease of use and implementation for efficiency) that provides an interface for adding non-functional concepts to a functional language, so that the functional part of the program is still functional. The monadic interface itself uses functional abstraction to hide the new concepts from the functional part of the program. But that's not the same thing as saying that the monad idea subsumes concurrency, mutable state, nondeterminism, and all kinds of other concepts. Monads, being a programming technique, are not visible in the kernel language. From this vantage point, they are not even a programming concept! In the terminology of CTM, Haskell monads can be called a linguistic abstraction.

I think that people confuse the monad idea with the new concepts that it can interface to. It's not because monads can interface to mutable state that monads subsume mutable state. Monads are just the interface to it.

The term monad is confusing in this context, because the monad structure itself is not relevant. The relevant point is that (e.g.) state can be modeled functionally. This encoding essentially creates an embedded sub-language that supports state, with runST (itself pure) providing the interpreter. I suppose you can argue that using this encoding means you're programming in another (non-pure) language, but I don't really see the point. It's a very shallow encoding that plays nicely with the rest of the language.

Nondeterminism is different - it can be modeled with a powerful type system but not implemented in a pure language (any implementation will be over-constrained).

It's a very shallow encoding that plays nicely with the rest of the language.

So you have two languages, L1 and L2. L1 is pure and in L1 you write an interpreter for a non-pure language L2. From the viewpoint of L1, you have added exactly nothing to the language (the kernel language is the same). From the viewpoint of L2, you have a kernel language with a new concept, i.e., named mutable state. What you have achieved is a clean interface between a pure language L1 and a non-pure language L2. The monad mechanism has given you that. But you have not actually added state to the pure language L1. L2 is implemented using a pure language L1, but from L2's point of view that is irrelevant. In CTM I call this the "Fallacy of the Preprocessor".

I don't really see the point

In computer science, it is always important to distinguish carefully the level of abstraction that you are working in. In this example, are you programming in L1 or in L2? If you are programming in L2, then functional reasoning is not sufficient. You have to use stateful reasoning techniques. If you are programming in L1, then you do not get the modularity advantages of named mutable state. At the end of the day, what you have gained is a clean interface between L1 and L2, so that you can use functional reasoning when appropriate and stateful reasoning when appropriate. You have not eliminated the need for stateful reasoning.

Suppose you take Haskell and move ST from the libraries into the definition of the language (so it still has the same monadic interface). This language has mutable state as a kernel concept, right? I don't see the point of considering this a different language from the one where we implemented ST with equivalent semantics ourselves.

I don't see the point of considering this a different language from the one where we implemented ST with equivalent semantics ourselves.

Exactly! They are both the same language. They are both *stateful* languages. They are the language I call L2. No matter how you turn it, L2 requires stateful reasoning.

Are you trying to say that L2 does not require stateful reasoning, just because it is implemented in a pure language?

That's not the same as L2 as I understood it. L2 was supposed to be the interpreted language, under the metaphor that 'runST' is interpreting an embedded language. This language that exists "inside the monad" is a typical stateful language - there are essentially instructions for load and store that (from the point of view of L2) have side effects.

The language I described isn't the same as L2 - it's the same as Haskell. It's a pure language that includes mutation descriptors as first class values and has a way to convert a mutation descriptor into a function from state to state. So to recap the argument: If you start with Haskell and add mutable state as a kernel concept through a monadic interface you just end up with Haskell again. Hence we might as well say Haskell supports mutable state. I think what you're calling "stateful languages" may just be languages with a particular interface to state - load/store with side effects - which is fine but will exclude the functional modeling approach which is IMO the right thing.

For what it's worth, I've been known to actually implement monads by defining the corresponding algebra (as a GADT) and then writing an interpreter - though strictly the interpreter isn't required to have a monad. The more common implementation style is simply the fused version where the constructors do all the interpreting work as well.

The situation where the "preprocessor" is in fact the language's own evaluation mechanisms in normal use definitely has some interesting properties of its own!