Lambda the Ultimate

programming in 20 years will be intensely concerned with the representation of data just as it is today: You make good points. In this view, data will contain more information than it does today. Data will be more extensible and interconnected. My view is that data and control will be more interleaved together. It will be harder to distinguish one from the other: data will contain embedded code and code will be more reliant on data.

The idea that this will converge to a "definitive language" that is right for all instances of that problem domain seems more of a stretch to me.

Actually, I think there will be a small set of definitive languages. From this vantage point, all object-oriented languages are the same. Probably I should have used the word "paradigm" instead of "language".

Probably I should have used the word "paradigm" instead of "language".

So predicting an "Omega paradigm" is more of a sure bet? ;-)

So that we can end up in agreement, I will rephrase what I think you mean as: we are quite possibly on the verge of a "quantum leap" in the design of and language support for distributed software, and we are starting to see what that leap will look like. I'd give you good odds on that formulation.

"The End of History" type claims always put me off my lunch. ;-)

Yes, I agree with your formulation. I don't believe in the "End of History" either, nor in an "Omega paradigm". I just think that we're starting to understand programming better.

The first paper I mention does not say that individual languages are converging. It says only that a similar language structure seems to be appropriate for four rather different research problems: network-transparent distribution, fault tolerance, security, and programming education. The languages involved are Oz, E, and Erlang. (Other languages also have similar layered structures, e.g., Haskell with pH and Concurrent Haskell and the work on STM can be considered to be moving in the same direction.) My belief is that this similar structure is not due to coincidence, but that there is something more going on. Do you think that this is "clearly false"?

"The first paper I mention does not say that individual languages are converging."

In your view, does it say that the field will converge? Doesn't that imply that existing languages at the same level of abstraction will either converge or die out?

"My belief is that this similar structure is not due to coincidence, but that there is something more going on. Do you think that this is 'clearly false'?"

No, but the question is what the "something more" is. The paper argues (or assumes) that it's something about programming. Or at least something about these four projects' needs. Right?

An alternative hypothesis might be that the relevant similarities are among the researchers, not the projects. Or that the projects, seen as experiments, were not independent (that is, one influenced the others). Or that the projects in the sample were chosen (not necessarily consciously) to conform to the pattern.

An alternative hypothesis might be that the relevant similarities are among the researchers, not the projects. Or that the projects, seen as experiments, were not independent (that is, one influenced the others). Or that the projects in the sample were chosen (not necessarily consciously) to conform to the pattern.

I think you could argue that the four projects looked at share a particular domain and that they probably all know about each other.

Actually, I thought about making that argument as a critique in my original response to Peter's post.

However I thought better of it, since the domain that all these projects share is distributed computing, which, thanks to the ubiquity of the Web and Net, is the domain of 99.99% of all large commercial applications. (Or uncommercial ones for that matter.)

Even if this was a more marginal domain, it is still a coherent domain, and the convergence of ideas within it is still a good sign of maturity in our collective thinking about the challenges in that domain.

So even though I don't expect an "über-language" to arise from it, I do think that any language that wants to support distributed programming "natively" will have to come to terms with the lessons learned by these projects and their kin.

And that is significant enough to tolerate a wee bit of hyperbole in a paper making that point. ;-)

So even though I don't expect an "über-language" to arise from it, I do think that any language that wants to support distributed programming "natively" will have to come to terms with the lessons learned by these projects and their kin.

Ok, so rather than focusing on the methodology behind the "convergence" argument, let's discuss the rationale for the approaches embodied by these languages, both as contrasted with the rest of the world, and as contrasted with each other. If the arguments for their approach makes sense, that is anyway a more powerful point than any observed convergence.

let's discuss the rationale for the approaches embodied by these languages: That's what the paper does. For each of the four problems, it tries to explain the problem in a way that makes it clear why the layered language structure was an important part of the solution.

Yes, I suggest that we discuss this rationale here

wee bit of hyperbole: It was an invited paper that was supposed to stimulate discussion. That's why it is more opinionated than a typical scientific paper!

That's why it is more opinionated than a typical scientific paper!

I'll take that as my cue to reformulate "layered approach" in an even more "controversial", but I believe still correct way.

My version is:

• excessive use of state is the enemy of reliable distributed computing (security, concurrency, fault-tolerance, etc..)
• pure stateless is not a viable alternative to state for distributed computing
• state/stateless is not a binary choice but a sliding scale
• the path from stateless to stateful can be organized into well-demarkated and disciplined layers; the programmer CAN be perfectly clear exactly how much state is being used in any given component.
• anyone who wants to be an effective distributed programmer must understand all of the above in both theory and practice
• languages that want to make distributed programming easier need to use the above implicitly in their design

The best part is no more FP vs. imperative threads since both sides are both right and wrong! ;-)

...see Tim Sweeney's The Next Mainstream Programming Language slides. They make all of these points quite clearly, delineating a purely functional core, a "middle" layer with state in some fashion such as via monads, and an "outer" layer with Software Transactional Memory. (Or maybe I'm getting a couple of layers mixed up; I'm writing from memory.) In any case, Tim does a great job of talking about the circumstances under which purely functional, monadic, and STM code might work for him in the context of the Unreal 3 technology codebase, and it would be quite interesting to hear from folks involved in other application domains how such a layering might, or might not, work for them also.

Update: OK, I read the slides again, and what Tim talks about is a data-parallel core, a purely-functional middle layer, and an STM outer layer. My error. The fundamental point, though, remains: imperative programming is the wrong default for concurrency, but being purely functional isn't practical for most kinds, and scales, of code.

They make all of these points quite clearly

Great! Peter can enlist Tim as a fifth example for his paper. ;-)

(More seriously, I DO think Tim is talking to the same insights that we are discussing. Though he adds typing issues, which I don't think Peter is putting on the table...)

...when Peter said "Whether it is dynamically or statically typed is of absolutely no importance, BTW." was exactly the point at which he became mistaken. :-)

... was exactly the point at which he became mistaken

I was going to make the same observation, but I figured I had given him enough of a hard time already. ;-)

Of course.. :p

So what do I want in this language?

• A layered dynamic semantics with:
  • functional core
  • declarative concurrency
  • distributed and concurrent reactive/message passing layer
  • explicit state
• A powerful but non-intrusive static semantics allowing me to inspect or enforce which layer some code lies in

I agree with your earlier points, and would agree with "no more FP vs. imperative state". But I believe imperative threads (shared state concurrency) are almost always wrong.

George Carlin once said "There are only two kinds of drivers. Everyone driving faster than me is a maniac, and everyone driving slower than me is an idiot." As engineers, many of us spend years deciding where we stand regarding various design tradeoffs. Having made the investment in finding a stance that's just right for us, we naturally regard various other reasonable positions are too X or too Y.

In this spirit ;), I suggest that the apparent convergence on message-passing concurrency is not as converged as it might look. Oz and Erlang are non-transactional -- their isolated unit of operation remains small steps. STM, Argus, and E support large-scale programmer defined units of operations. Argus provides full speculative ACID[*] transactions. STM provides speculative ACI transactions (or ACID if one resorts to Persistent Haskell). (Oz does support speculation with its subspace search mechanism. Perhaps there's a clean way to combine this with Oz's support for stateful message-passing concurrency in order to get speculative transactions?)

In non-persistent E vats, E turns are only CI and non-speculative. In a persistent vat, an E turn is effectively a speculative CID transaction, though in practice we have used rollback only to recover from crashes, and not for speculation.

I hereby argue that Oz and Erlang do not go far enough towards enabling transactional reasoning, because the programmer must still be aware of small step interleaving. E provides the minimal isolation needed to enable the programmer to informally reason about stateful concurrency and distributed programming without an explosive case analysis. Speculative transactions may be cool, but implementing them efficiently is rocket science, and the benefits are beyond diminishing returns. I propose that E's stance on message-passing currency -- communicating event loops and delayed references (whether called promises, futures, logic variables, or dataflow variables) -- is the right default.

There remains the mostly-separate issue of how one mixes purely functional code with stateful code. Again, the systems in Peter's convergence take very different stances on this. It would be interesting to contrast these as well.

[*] ACID:

• A is for "Atomic", meaning that either the whole thing happened or (as far as is observable) none of it happened.
• C is for Consistent, which is a motherhood claim with no hard criteria.
• I is for Isolation, meaning that we can ignore interleaving of execution within each transaction. (Serializability implies isolation. Therefore, units of operation are isolated by definition.)
• D is for Durable, meaning that commitment is forever.

Oz and Erlang are non-transactional -- their isolated unit of operation remains small steps.

I disagree: the isolated unit of operation in Erlang is very large. Everything an Erlang process does in between message-passing communication is a unit and simple, explicit protocols minimize communication.

I agree that Erlang is non-transactional. I would say that Erlang programmers use normal message-passing for mutable state (thinking of the #state records of gen_servers as the prime example) and that Peter's paper exaggerates the significance of Mnesia & transactions.

Yes, technically you're right. A unit of operation within an Erlang process is everything the process does (including sends) between two successive receives. But how much of a difference does this make to the Erlang programmer's ability to reason about concurrency?

I ignore here whether these are selective or non-selective receives. The arguments pro and con selective receive are complex but not germane to the points made here, and so can be discussed separately.

In Erlang, any function can do a receive, blocking its process, suspending its stack of callers. Adya et al calls this "Automatic Stack Management", and explains the need for some way to mark functions that might block, including functions that might call functions that might block.

Does Erlang style include a naming convention for distinguishing such functions? If so, and if used consistently, then the Erlang programmer is relieved from reasoning about concurrency when reasoning about a function that's known not to call anything that might block. In the absence of such a convention, when reasoning locally, any call might block, and so the programmer pays all the costs of manually reasoning about fine-grain units of operation.

See section 18.2 of Robust Composition, "Manual Continuation-Passing Style", for more.

Erlang programs use few abstractions and indirections. When I'm writing Erlang programs I have a good feel for what's functional and what's interacting because of my familiarity with other parts of the program. There aren't a lot of abstractions making it "naughty" to understand the character of the code you're using and you don't have to know much to know if and how a module interacts with other processes. Erlang programs feel much more like C programs than object-oriented ones in this "just write what you want to do" respect.

I understand your point though. My practical experience is that it applies strongly to Java and Lisp but not to Erlang.

See section 18.2 of Robust Composition, "Manual Continuation-Passing Style", for more.

I appreciate the issue. In Distel I have implemented Erlang-style concurrency in Emacs Lisp's recursive event loop and there I used manual conversion to CPS and a special naming convention to mark functions that aren't going to return. This is horrible.

But in Erlang we don't worry about the need to face the hazards of plan interleaving throughout [our] programs and we don't consider blocking a taboo. We try to keep the communication simple, central, and separate from the functional libraries, and that way we can keep track of what's going on. We're mostly concerned about being able to reason informally about our programs.

EDIT: By "we" I mean Erlang programmers in the trenches. I don't speak for the designers.

I hereby argue that Oz and Erlang do not go far enough towards enabling transactional reasoning, because the programmer must still be aware of small step interleaving.

While I think it is possible to put design trade offs into a partial order the way the "layered approach" is suggesting, choosing a particular spot to rest a particular design at is necessarily dictated by the problem you are solving.

If for a given functionality you positively need a further step on the ladder, or if going up that step in some constrained way is the least convoluted solution or the one with most acceptable downside, you pretty much have to go there.

The big problem with long ACID transactions (as any enterprise app developer knows) is that rollback on a long transaction is often too expensive to be viable: you often want to preserve intermediate steps of information, and so you reduce the size of the transactions to the smallest steps that will preserve well-formedness of your data.

Once you are down to the smaller steps, how much are the built-in transactions really buying you?

I think we all agree that we should try as hard as reasonable/possible to stay at the stateless end of the hierarchy, and maybe all you are saying is "try even harder", but do you really think the more stateful options should be eliminated a priori for all problems?

'maybe all you are saying is "try even harder",'

I am certainly saying that. I'm not sure that it's all I'm saying. ;)

'but do you really think the more stateful options should be eliminated a priori for all problems?'

Given the context, may I assume that by "more stateful option" you mean shared state concurrency (i.e., conventional shared memory multi-threading with fine-grain locking)?

I'll start with an analogy. Marc Stiegler recently pointed out to me that no new languages provide unsafe pointer arithmetic. Memory unsafe programming is occasionally justified, but so rarely that designers of new languages feel no need to provide linguistic support for it. All languages provide inter-callability with C, and the attitude seems to be: If you need raw access to memory, do it in C and link it in. This absence already represents an important convergence in language design.

Like memory unsafe programming, shared-state concurrency is so rarely the right thing, and it creates such pervasive problems, that new languages should not give it any linguistic support at all. I agree with Peter in expecting languages to converge on some form of message-passing concurrency layered on some form of mostly functional foundation. However, what kind of message-passing concurrency, and what kind of mostly-functional foundation, remain to be explored.

Like memory unsafe programming, shared-state concurrency is so rarely the right thing, and it creates such pervasive problems, that new languages should not give it any linguistic support at all.

The arguments for pointers were predicated on performance: before there were fast enough machines with enough resources to make automated memory management a ubiquitous reality, programmers needed that power to satisfy their requirements.

Now that we take automated memory management for granted as a practical reality, there is no argument for engaging in the danger of the "more powerful" (in a particular sense) but riskier approach.

In the case of transactions, I would have to agree with your position if the cost of rollbacks on large transactions was approaching zero, but I have yet to see that playing out. (We can still hope though).

If that day was at least obviously approaching, I would gladly give up the facilities for shared-state concurrency (which I already use as lightly as I can get away with). But until then...

"I would have to agree with your position if the cost of rollbacks on large transactions was approaching zero"

Perhaps we're agreeing? Earlier I wrote: "Speculative transactions may be cool, but implementing them efficiently is rocket science". I'm arguing here for the position taken by E: non-speculative isolated units of operation of programmer-determined granularity, as are provided by communicating event loops. These provide most of the benefits of transactional reasoning at little of the cost.

Perhaps we're agreeing?

Maybe, but after looking at your thesis, I think more likely I was just misunderstanding you. ;-)

I'm arguing here for the position taken by E: non-speculative isolated units of operation of programmer-determined granularity, as are provided by communicating event loops. These provide most of the benefits of transactional reasoning at little of the cost.

If I understand correctly, communicating event loops are equivalent in power to Oz's declarative concurrency, which is also its default concurrency type. How has it made a different choice than E in your opinion?

I also have a question: how would E handle a problem that genuinely has global state? For example, you are a bank and you want to make sure that there is some central, definitive authority on the balance of an account, even though multiple distributed agents are adding and subtracting money from it?

How has it made a different choice than E in your opinion?

To rescue myself from cluelessness ;-) and render your answer a mere confirmation/disconfirmation, let me take a guess, to make sure I'm finally on the right page.

The difference in design is the lack of E's implicit, system-controlled turns in Oz: with Oz you have to explicitly use particular dataflow variables that will block, whereas with E the message queue is invoked by both producer and consumer implicitly.

And you are contending that this removes a potential source of difficulty from the programmers hands and allows the language semantics to do the work.

Close?

No, sorry, that's not it.

Oz includes two concurrency stories: pure declarative concurrency, which is deterministic and stateless, and message-passing concurrency, which is stateful in a reasonable fashion. When the first fits your needs, great, it has all the benefits of purely functional code. But when you need state or distributed non-determinism, pure declarative concurrency is inadequate. Message-passing concurrency, if used by itself, would be equivalent to E's turns.

However, there are two ways in which Oz allows message-passing concurrency to be mixed with declarative concurrency. First way is fatally bad, as it enables shared state concurrency, so Oz-E will prohibit it. The second way is the one I'm concerned about here.

The first way? Having allowed stateful cells into Oz for support of message-passing concurrency, and having allowed shared memory multi-threading for support of declarative concurrency, Oz "accidentally" allows multiple threads to directly access shared stateful cells, bringing about shared state concurrency.

The second way? For pure declarative concurrency, it is natural and useful to allow a thread to block on an unbound logic variable, as this variability in scheduling cannot cause visible effects. However, with message-passing concurrency, if an "active object" (in Oz terminology -- a "vat" in E terminology) blocks on a logic variable, either it blocks forever, or some other active object will bind that variable, allowing it to continue. These blockage points, like the receive operations of Erlang, constitute an interleaving point the programmer cannot ignore. Even among active objects, an Oz unit of operation only extends from one such blockage point to another. This has the same issue I raise regarding Erlang's receive operation above.

E avoids this simply by prohibiting all blocking operations. With an unresolved promise (the closest E analogy to an unbound logic variable), a turn in a vat can send messages to the promise (to be delivered to what the promise will be bound to), can send the promise as argument in messages to others, can store it in data structures -- all as you would expect and as you can do with Oz logic variables.

In addition, a turn can register a callback object to be invoked once the promise is resolved. However, it cannot block its vat waiting for the promise to be resolved. Once the promise is resolved, each of the registered callbacks gets invoked as separate turns (i.e., top level "transactions") within this vat. Although each of the callbacks is, in some sense "waiting", the turn which registered the callback still runs to completion, and the vat as a whole continues to process incoming messages in the meantime. Turns thereby remain isolated units of operation.

Communicating event loops have greater expressive power than declarative concurrency; for example they can express nondeterministic behaviour.

I think that D still provides raw memory access if needed, even if by default you should use the GC.

Considering that D isn't even 1.0 yet, I think we can call it a 'new' language.

The big problem with long ACID transactions (as any enterprise app developer knows) is that rollback on a long transaction is often too expensive to be viable: you often want to preserve intermediate steps of information, and so you reduce the size of the transactions to the smallest steps that will preserve well-formedness of your data.

Yes. To some extent this is fixable. It's necessary to provide operations that communicate information out of a transaction context even if the transaction rolls back (restricted in such a way that it is feasible to reason about them, and used sparingly).

But transactions should not be too long in any case; in particular, you should not do things that might indefinitely block in a transaction. The criteria for how long to make a transaction are IMHO similar to those for an E turn.

Realizing how often jokes in email are misunderstood, I thought I should clarify. The point of the Carlin joke is, of course, not to make fun of the other drivers. It is to make fun of the speaker, in this case me, for using my own choices as the gold standard for criticizing others.

In fact, I have great respect for Oz, Erlang, and Argus. I suspect I would also have great respect for STM if I understood it ;). I am not actually confident that E's stance on concurrency is better than theirs. However, the virtues of their positions are better known, and bracket E's, so it is worth arguing here for E's.

It is to make fun of the speaker, in this case me, for using my own choices as the gold standard for criticizing others.

If we won't use our own choices as a standard, whose else will we use? ;-)

One choice (or series thereof) of mine that I'm currently regretting is that I didn't pay more attention to the E posts and material here on LtU over the years. ;-)

To make up for this, I've been reading a bunch of E materials, trying to get a grip on the concurrency model, but it keeps slipping out of my hands.

In particular, I'm unclear about the language visible demarcation between the declarative and message passing "turns" levels of concurrency.

How does the programmer know which one is operative?

"I'm unclear about the language visible demarcation between the declarative and message passing "turns" levels of concurrency. How does the programmer know which one is operative?"

E doesn't have declarative concurrency. Within a turn, E immediate calls form a fairly conventional local, sequential, imperative (mostly functional with local side effects), lexically scoped, pure-object system. Let's call this sublanguage , "Immediate-E". The novelties of Immediate-E are the auditor framework (and its integration with a soft type system), the lack of ambient authority, in order to conform to object-capability rules, and a set of libraries that support object-capability discipline. From a concurrency perspective, the only relevant novelty of Immediate-E is the use of auditors/guards to mark/test that certain objects are DeepFrozen, i.e., transitively immutable, and therefore have many of the virtues of pure functions. (Other auditors can test for more or less of these virtues, but DeepFrozen seems to be the most useful.)

E programs express the inter-turn and inter-vat level of coordination using eventual-send ("<-") and when-catch ("->") expressions, and by manipulating eventual references. Considered by itself, this level of E is like Joule, which is in turn similar to actors language or conventional (non-Oz-like) concurrent logic programming languages. Let's call this sublanguage "Eventual-E".

My point regarding the isolation of E turns can be summarized in operational semantics terminology by the slogan:

One small step for Eventual-E is one big step for Immediate-E.

E doesn't have declarative concurrency.

The light comes on...

I re-read Peter's description of the layers as they apply to E and I'm struck by description of a single thread for a single process, which normally doesn't qualify as "concurrent". (I assume this describes the "immediate" portion occuring within a vat.)

I suppose that means I have question for Peter: are you considering the inter-object / intra-vat "immediate" communication a form of concurrency?

And would that not qualify ANY kind of single-threaded, message-passing, object-oriented language as having "deterministic concurrency"?

I have a proposal for speculative ACI transactions in E (almost ACID in the case of persistent vats, although with some restrictions on transaction scope). They fit with E's style of message passing really well, and have an efficient and simple implementation, at least compared to STM (which provides a shared state approach to transactions).

I will send it to the e-lang list by Thursday-ish.

E turns are isolated, but it is quite difficult to guarantee consistency [which can be defined precisely, BTW] in the presence of exceptions. My original motivation in adding transactions was to fix this (i.e. to solve the problem described near the end of section 5.7 of your thesis at the language level, rather than just working around it, with difficulty, in every application). But it turns out that there are lots of other side benefits as well, and an improvement in expressiveness.

(Oz does support speculation with its subspace search mechanism. Perhaps there's a clean way to combine this with Oz's support for stateful message-passing concurrency in order to get speculative transactions?)

That is essentially what my proposal does: it provides support for the relational model (equivalent to 'choice' in Oz; it can be extended to full subspace search if you like) and transactions, using the same mechanism. It would also be applicable to Oz-E.

Incidentally, I would really like to thank Peter and Seif for writing CTM. It has helped enormously to clarify my thinking about language design.

They said this 20 years ago too.

20 years ago the large vendors had systems that could take a specification and create a set of business applications. Granted the process occurred in a specific business environment in specific vendor's machines (Oracle et al). Coding had become merely specification. But there was still something missing.

Luc Steels' work now shows how language evolves in robot populations

• Sony's CSL Labs publications - go down to Steels' papers
• Luc Steels publications

and studies of human development of language (alternate story here) confirms the validity of Steels' work.

Steels' experiments are breakthroughs in the study of language and are the key to the future of computer language. Chomsky's brittle and static syntactic vision of language is obsolesced by Steels' view of language as an evolving system of communication. Steels' work gives us the keys to the origins and evolution of language in populations of socially-interacting robots. We now have what is needed to build the bridge between human and machine.

Suggesting to replace precise, efficient and unambigous textual representations of actions by interactions within a semi-intelligent robot swarm is just like suggesting to replace RNA transcription machinery by human love.

You're human and presumably intelligent, yet you missed my point completely.

The communications would not be with a "semi-intelligent robot swarm" but with one of many intelligent automata (not necessarily robotic). These would undoubtedly be part of a community of both other automata and humans. They could surely understand you as well as you have understood me!8-)

As to "precise, efficient and unambigous textual representations of actions" I must ask: when is the last time you wrote a program (in any language) that compiled correctly after being first written and then ran correctly? Humans are virtually incapable of this task yet most consider them intelligent.

Steels' work is out there. You can get on board and get with the program or stand here and be left behind.

LtU is for discussions about programming langugaes. Other approaches, promising or not, are outside the scope.

They could surely understand you as well as you have understood me!8-)

Natural language communication is prone to errors. Communication of ideas in the scientific community has always needed the precision of a formal language (mathematical equations and chemical formulas for example). These languages allowed communication of declarative knowledge but communication of procedural knowledge was still cumbersome. With the advent of computation as a science, communication of (and understanding of) procedural knowledge has advanced greatly. In other words: if we want to communicate exactly and precisely what we want a computer to do (even if that computer is "intelligent" and can understand natural language) we will need to do so using language that is exact and precise. The end result will be something that looks a awful lot like programming.

I end with a quote:

“First, we want to establish the idea that a computer language is not just a way of getting a computer to perform operations but rather that it is a novel formal medium for expressing ideas about methodology. Thus, programs must be written for people to read, and only incidentally for machines to execute.” — Abelson and Sussman

My personal belief is that within 20 years it will be unnecessary to write code as it exists today. Instead we will engage machines as we do people in discussion of problems and they will "understand" (certainly at least as well as people do).

Let's grant that you are right, tndal.

This would imply that studying PLs and ways to improve them is a waste of time, since there will soon be no need for specialized languages to speak to machines and between machines.

So why waste your time posting on a blog where all of us dinosaurs LIKE studying PLs and ways to improve them, and will continue to do so until our acursed field of interest goes extinct in the next 20 years.

Rather than kick us while we're down, let us enjoy our doomed few remaining years studying and discussing the field we care about before the lights go out, and why don't you find a nice, on-the-verge-of-the-new-revolution AI blog where you can discuss your lucky interests with a bright future without making us feel discouraged?

Just a suggestion.

One of the central problems of AI is that it tries to define an answer (42) but has never successfully narrowed down the question (life, the universe, and everything).

My definition for an Omega point in PL's would not be an elimination of PLs, nor the consolidation of programming tasks into a single language which is used to communicate with the machine. I think that the easy prediction is that the number of PLs in use will increase over the next 20 years. The real question is whether these PLs will mature to a point where the field becomes specialized where one can accomplish tasks in a single language without having to fret over the languages used by others.

To tie this back to the original subject, one thing I think that's needed for is protocols that decouple the distributed computing from the programming language used at the nodes. Http, for example, is a fairly successful stateless protocol (though extremely lightweight) where the client browser can visit pages written in any number of languages. So the question about distributed computing is whether this is really a PL problem, or is it a protocol problem? Or to put it in the current context: Can one mix the implementation of distributed nodes with Oz, E, and Erlang? Granted, the communication would have to be based on a lowest-common-denominator betwixt the languages, but if these languages have moved the base of distributed computing then that LCD should be an improvement above any other current solution.

And while I'm at it, one of the sections in CTM that kind of disappointed me was section 5.7.3 on the Erlang receive operation. Ok, so the book is already 800 pages long, so I can understand the need for brevity in this case. Still, it'd be nice to have a couple of examples in a supplement that tie into CTM.

Can one mix the implementation of distributed nodes with Oz, E, and Erlang?

There is the UBF protocol for distributed programing that was designed with exactly this in mind. It is suported by both Erlang and Oz. I don't now about E but it should be easy to implement if it isn't done already.

"Can one mix the implementation of distributed nodes with Oz, E, and Erlang?"

Yes. We are currently using the Web Calculus to do language-independent distributed capability-secure promise-pipelined messaging between servers locally programmed in Joe-E. Sandro Magi also has an implementation in C#. Once these use the same version of the Web Calculus, they should inter-operate just fine. We hope to eventually have an implementation in E, bridging between E's notions of capabilities and promise pipelining vs. those of the Web Calculus.

However, after we have done so, this will not obviate the need for CapTP. E nodes talking over Web Calculus form a distributed object-capability system, but not a distributed E system. The cost of speaking a protocol with a language-independent semantics is that the distributed computation is no longer described by the semantics of a single language. Rather, it is more like the semantics of a program made by linking together modules written in a bunch of different memory-safe languages. To understand the semantics of the result, you need to understand how the semantics of each participating language is mapped onto the semantics of their common invocation framework.

We need both distributed languages, like Oz, Erlang, and E, and we need language-independent distributed object-capability protocols as gateways between these.

Of course, this does raise the question of whether the name of the blog ought to be changed to Lambda the Penultimate, in anticipation of the imminent social robot overlord takeover.

I always thought the imminent social robot overlord name/model was going to be lambda the ultimate logic system...

That's like saying math will disappear in 20 years.

All programming languages are different manifestations of the same model (the Turing machine - even lambda calculus is a constrained form of it).

Nah. Although they are of course "equivalent" wrt computational completeness, they are pretty different. And lambda calculus, being simpler, more abstract and more principled, definitely is the more adequate model for programming language semantics - or have you ever seen a (real) programming language defined in terms of a Turing machine? AFAICT, the Turing machine got its prominence more by historical accident.

Also, there are other models, e.g. the lots derived from pi-calculus and friends. And there exist (experimental) programming languages built on top of those. However, on the surface they still look much like most conventional languages.

Let's see what a Turing machine needs:

-a Tape where information is stored in the form of cells. The Lambda calculus also does require such a tape: it is the place where values are stored.

-a Head which indicates the current position in the tape. Lambda calculus also has that: it is the current point of evaluation.

-A table of instructions which indicate how to proceed: erase a value, write a new value, move the tape left or right, assume a new state. Well, the Lambda calculus also has that, with the exception of erasing a value. In Lambda calculus, values are not erased (that's the whole difference between imperative and functional programming anyway).

In other words, any Lambda-calculus program is also a finite-state machine. The only difference with the Turing model is that values are not erased.

The perceived difference between the two models is not that great: the Lambda approach may allow for a few more tricks on the compiler (i.e. making it a little bit easier to understand things about the code), but neither model can solve the halting problem...

The only hope for something radically different is quantum computing, but I am only quoting what I have read; I have no idea how that would work.

You are not describing the calculus, you are rather describing an encoding of the lambda calculus into something TM-ish.

The lambda calculus itself has no tape. And particularly, it has no "point of evaluation" (in each step, you consider the term as a whole again), nor anything resembling a table of instructions (there are no seperate instructions, the evaluated term is everything that's there, it's program and data in one). And certainly a lambda term generally cannot be considered a finite state machine (it is trivial to give an example that goes through infinitely many different terms as evaluation proceeds).

Of course you can encode each system in the other (that's the essence of being computationally equivalent), but that does not say much about the similarity of the models. The encodings are far from straightforward. I figure Turing must have had loads of fun programming a beta reduction term rewriting algorithm in the TM for his proof... :-)

But I have to 'instantiate' a Lambda calculus machine in order to compare it to a Turing machine...Turing Machine and Lambda Calculus aren't really comparable, it's like comparing apples to oranges.

So from the point of a programming language, the two models are similar. Even if you evaluate a program based on lambda expressions on paper, the requirements are still the same(i.e. tape, head, registers).

There are AIs already in existence that can write more coherent text than contained in the parent comment.

Perhaps the elitist behavior of FP adopters is what keeps FP from becoming mainstream :-).

(or perhaps someday you may realize that a tool that works in theory does not necessarily translate into something people can use...but who am I to argue? the tremendous success of FP is a testament to that...)

Making strong claims when you may misword the claims and you have difficulty in describing the evidence for them isn't a recipe for good conversation either. And as this site is largely about programming language theory, it's not reasonable to expect people here to teach you the pragmatics of coding - especially if you're going to pressure people about it.

LtU's purpose is not to convince or help people to adopt FP. It's for people who are genuinely interested in the study of programming languages. It shouldn't be necessary to advocate a desire to learn here, and it is likely pointless to do so. If you're making a good faith effort to study the subject, that will be evident in your comments, questions, and attitude, and you'll get correspondingly better responses here.

I think this subthread should end. I think both sides made their points. Let's return to the discussion of programming language issues. Thanks.

The reason I read and post in this site is not because I want to better myself in programming languages, but to see if we can solve the problem that is programming.

We would all like to see a programming language that makes writing incorrect programs impossible, wouldn't we? well, I am in that quest too. I would really like to see the day when programs would not need testing and debugging!

In this quest, I come across a programming style labeled as 'functional', where its supporters claim that it is the holy grail of programming! they may not say so directly, but their whole attitude, the meaning when one reads between the lines of their sayings is that FP is the best thing since sliced bread.

Well, I recognize some of the benefits of FP, but I also have to stress the following facts:

1) Ignoring state manipulation like it is some sort of fatal disease is a grand mistake, in my opinion. Instead of trying to find ways to control state, FP supporters throw state out of the window. That's a major error. State is not the source of all problems; undesirable control of state is. Constraints that only exist in the mind of the programmers is the problem, and no FP language comes close into solving that problem (and the claim that once written, an FP program is correct is totally a lie: I have seen professors struggle to find bugs in FP programs that should not be there). Even using the words 'side effect' is wrong, because 99% that side effects is what I am trying to achieve...

2) The world needs solutions, not theorems. While writing down mathematics may be exciting for some people, it does not solve problems, especially if when the mathematics can not be directly translated to real-life solutions. In this spirit, functional programs are the same as imperative ones, minus the destructive update, of course; and that's the reason of my comment that 'lambda calculus == Turing machine'.

I will continue to seek and ask for solutions, and I really do not mind if people get upset if my opinion on their favorite toys differ from theirs. You will not see me writing realms of mathematics, for the simple reason that programming will not become a commodity if I can not explain it to a child! And for that to happen, programming has to be simple. And for it to be simple, we can not ignore everything that happens outside of the realm of mathematics! unfortunately, that's what has happened to LtU over the years...

Finally, I would like to say that it surprises me that no one finds it strange that people can do tasks like correctly synchronizing threads/ manage memory manually/etc and automated tools can not do those tasks! I am writing programs for over a decade, and I have never met a case where such problems were undecidable! I know that a physical barrier exists (yeah, the famous halting problem) in what can be done with a programming language, but my thesis is that if a human brain can do it, then the computer can do it as well...but I see no effort in trying to encode the type of abstractions we humans do that help us solve those problems...all that I see is that PL researchers are stuck in things like the Lambda Calculus!

Finally, I would like to say that it surprises me that no one finds it strange that people can do tasks like correctly synchronizing threads/ manage memory manually/etc and automated tools can not do those tasks!

It's interesting that you chose concurrency and manual memory management as your examples, because those are the two canonical examples of things that programmers fail to get right, time and time again. Undecidable? No, but you're telling me that in ten years of programming, you've never been bitten by a bug that resulted from someone not getting malloc/free or synchronization right?

1) Ignoring state manipulation like it is some sort of fatal disease is a grand mistake,

2) The world needs solutions, not theorems. While writing down mathematics may be exciting for some people, it does not solve problems, especially if when the mathematics can not be directly translated to real-life solutions.

   val x = 1
   val y = x + 1

I can not be assured of the answer being 2? How is that lack of mathematics supposed to solve the computing problem? Computing (aka computation) is very much tied to mathematics. One may not like the particular branch of mathematics and notation used by PL researchers, but one should not extrapolate that to a conclusion that all practical programming endeavors are devoid of mathematical reasoning. Or worse, that mathematics and computer science are at odds with each other.

programming will not become a commodity if I can not explain it to a child!

Ignoring state manipulation like it is some sort of fatal disease is a grand mistake

Actually, this brings us back on to Peter's original topic: the idea that for distributed applications state is essential, but needs to be constrained to its appropriate layer.

It is not a fatal disease, but rather more like radioactive material: it has some indispensible uses when handled carefully, but you wouldn't want to mix it indiscriminately will all your other stuff.

It's also worth mentioning that there is an intermediate possibility between pure constants and state variables that can be used to good effect - Dataflow Variables. They are a mild form of a state variable, but retain the reasoning properties of constants. And it's that use of dataflow variables which can be used in many cases that people require state.

Still, as you say, CTM is not dogmatic in the exclusion of state. But state does introduce a complexity that should be minimized and contained. But then this requires judiciousness on the part of the programmer to know when and when not to use state, and how to go about encapsulating that state.

The reason I read and post in this site is not because I want to better myself in programming languages, but to see if we can solve the problem that is programming.

It seems unlikely that "the problem that is programming" will be solved without studying programming languages. A side benefit of the study of programming languages is that it allows one to get beyond misconceptions of the sort laid out in the parent post, and onto more meaningful subjects.

For example, the study of programming languages doesn't ignore state — quite the contrary. Modeling, analysing, and dealing with state is one of the central topics, as it should be. If you want to really understand state, the treatments of it found in the PL literature are the most rigorous and enlightening that I know of. CTM could be a good starting point, since the models it covers include explicit state and shared state concurrency.

Edit: On the subject of state, there's an old thread about State and modularity which may be helpful.