Lambda the Ultimate

Yes, alot of useful things come from it, some more, some less. The main reason why the relevance of many things is not clear, is because there is such a dramatic divide -- an insulating layer -- between computer scientists and programmers! Computer scientists insulate their work behind academic white papers that make heavy use of comp. sci. terminology, and don't always address the practical relevance of the work they discuss towards programming. On top of that, it doesn't help that communcation on the terms of people outside the comp. sci. community, needs alot of work!

Perhaps to a certain extent, but CS research without organization is like a car with a scrapped-together engine.

Perhaps you may find On Understanding Data Abstraction, Revisited by William R. Cook interesting.

Really try it: go through the TOC of OOPSLA/ECOOP year by year to see what's hot and how quickly it sputters out (or ICFP or PLDI).

Really, try this!

For fun, you can set up comparative timelines between ECOOP and OOPSLA, and disect the trends in other ways. [Edit: It is also interesting to note that the best PLT researchers of the past 40 years seem to consistently work on the most important problems.]

I would also recommend reading PJ Brown's "The Researcher and the Marketplace" essay.

All good points. I second the call on components and AOP. It is interesting to note, given the sociological perspective possibly implied by your post, that there are still networks of people working on these topics, in the periphery of the profession.

Currently, AOP can be known as "Invasive Software Composition". I'm actually currently reading about this to update my knowledge of AOP.

I think many "components" were ill-conceived, i.e. J2EE "business components" made little or no sense and was wishful thinking. On a more basic level, thinking in terms of structured programming... Even today in VMs like JVM and CLR, the libraries delivered by major vendors tend to poorly partition assemblies. Perhaps this is in part due to possible overhead costs from security context changes (going from one assembly to another can require a security context check). I'm not exactly sure what the limitations are that prevent engineers from properly using components. The Mono Project is doing the best job right now practicing re-use "all the way down". However, nobody seems to be paying any attention to what the Ximian guys at Novell are doing to bring better software engineering to the platform. For example, how they chose to sandbox Moonlight and define Moonlight as a subset of the Mono framework was brilliant (using a linker to define a security sandbox), and superior to what the CLR team supposedly did for Silverlight at Microsoft (I'm told they used the moral equivalent of a bunch of ad-hoc scripts).

So my best guess as to why component-oriented programming and structured programming never really fulfilled their potential is probably physical coupling concerns and related performance problems. Enterprise systems, however, are changing how people think about bigger and bigger systems, and it turns out the researchers in the 60s and 70s predicted the right solutions to these problems... people just didn't want to adopt it until practically forced to.

[Edit: A natural consequence of this is, as Ehud describes it, "networks of people working on these topics, in the periphery of the profession". Components are not really a PLT topic any more. Instead, they're more SE. This makes it hard to integrate back SE contributions to PLT. For component systems, a natural periphery is Software Configuration Management. It is not even that periphery. The SCM LNCS over the past few years has included papers by people such as blogger Mark Chu-Carrol.......]

A friend read my LtU post above and directed me to this Artima blog post: Alan Bateman on JDK Modularity.

During its close to one-and-a-half decade of existence, Sun's JDK has built up many internal dependencies. As a result, many core Java APIs depend on a large number of other JDK APIs. A key goal of JDK 7 is to minimize such dependencies, resulting in a more modular JDK. That goal, however, is not easy to reach, writes Sun's Alan Bateman.

Good to see. I guess this somewhat helps ease Scott's fears that PLT is useless in making an impact. The remaining bottlenecks for JVM are therefore the stack-based byte code (as opposed to NekoVM or Cyclone project) and the Java language as the lingua franca for the JVM.

I tried to be brief in my comments. Maybe too brief.

What I was trying to get at is that the very tangibility of physical widgets--screws, bolts, integrated circuits, kitchen gadgets, widgets in general--makes them

-- meterable, or salable on a per piece basis, or per 1000 pieces. etc. Every widget in a large hardware store or in a thick IC parts catalog is like this.

-- improvable, in that the profits on the first version fund later improvements, later versions, revs, mods, and a continuing revenue stream.

(An example from the open software community, where many commonly-used tools are based on grad student hacks which never got a lot of honing and refinement. My Unix friends complain about Unix tools repeatedly.)

Kitchens and kitchen techniques and widgets illustrate the point well. (And also go to the OO vs. FP issues, e.g., is a blender an object to which one sends messages or a function, something which when presented with inputs produces a predictable output?)

The first techniques for blending or whipping (as in into a froth or foam or whatever) were a lot like early mathematical algorithms. They could be taught (even for a profit), put in books, and adopted by others. And then came tools for making blending or whipping easier. These tools could be copied by others (anyone with a whittling knife could make a reasonable copy). They could also be sold, but could be copied.

Then came Mixmasters and KitchenAid stand mixers and the like. These could be "metered," with enforcement of various patents on the particular implementations. (With someone patenting the "idea of mixing" being as ludicrous as some of the software patents seen today.)

How this relates to computer languages is that the languages are basically OK. It's not a failure of either OO or FP that we don't have "software ICs."

And, contrary to a few comments here, it's not that software people are intrinsically flakier or less-trained than hardware people are. I think the difference lies in the difficulty of making money (metering, selling) better versions of "small" pieces. In the hardware arena, slight manufacturing improvements, or more clever designs, can often translate into greater profits. True for real ICs like microprocessors and true for kitchen gadgets and appliances.

But in the software world, where things are trivially replicated, it takes a lot of "product protection" overhead (licensing, number of "seats," etc.) to get payback on effort. A slightly better version of grep or a slightly better version of "sine" is not likely to be rewarded the way a slightly faster version of the 8080A was rewarded.

So the products in a hardware store, or whatever, tend to look a lot more refined, polished, and efficiently produced than their counterparts in today's "software components" listings. Even a simple $0.25 bolt is the product of maybe a century of metallurgy, strength testing, analysis of failures, and design improvements. Such is not the case for some "software component," whether OO or FP, downloaded from some library and then used inside some larger project.

I think this relates to language theory, at least from the real world side, because software objects are a lot more like _text objects_ (fragments of speech, snatches of ideas) than they are like _physical_ objects. The very name "object" is misleading, in the ontology sense. That is, it suggests properties of actual objects, such as difficulty of replicating, that are at the core of this issue of why there are not more "component objects" for sale in catalogs and "Object Home Depots."

[...] but WHY, then, should we not look upon our own current promotion of and involvement with "language innovation sandboxes" such as Haskell or Clean, FP in general, [...] with an *extreme skepticism* informed by our, in hindsight, extremely sophomoric infatuation and ideological adherence to so called "OOP?"

Because, 1) these statically typed languages are firmly rooted in logic, unlike OO languages at the time, and 2) functional programming approaches are pretty much as minimal as you can get and still be readable (unlike the more minimalist SK combinators), so theoretically the composability and simplicity are both very high. Which isn't to say they can't be pushed higher in certain domains (such as timed/event-based systems, etc.), just that we're bumping limits on sequential programs.

Three, I am thus far extremely dismayed that no respondent has taken up the cause of even a single PLT innovation of the past 20+ years as having as yet greatly unrealized potential.

Static typing, though with C#'s generics, and, I hate to say it, C++'s templates, we have at least a basic statically typed foundation for our platforms. However, there are still many, many more domains that could benefit from typing, such as multistage computation, distribution, concurrency, timed/event-based systems, resource constrained systems, effects, and so on.

The past 10 years has produced a lot of work in this area, such as House, Cyclone, BitC, Haskell's Atom DSL, for the low-level stuff, and Alice ML, FRP, MetaOCaml, and more for the higher level stuff. I think the next general purpose programming language will distill a few core primitives from these languages to properly support both low-level and high-level programming, and steal away even more developers from C/C++ and Java/C# platforms.

So I disagree that there has been no progress, I just think a lot of these ideas have been incubating for the past 20 years, particularly how to compose programs and compile them efficiently.

Because, 1) these statically typed languages are firmly rooted in logic...

OO didn't try to be a logic. I don't see how that was its problem, and why we should not be skeptical of the new "exciting" stuff that is based on logic.

OO didn't try to be a logic. I don't see how that was its problem, and why we should not be skeptical of the new "exciting" stuff that is based on logic.

Because the limits of expressiveness become obvious pretty quickly when you have a formal definition of what you can and cannot safely abstract over. OO languages have discovered these limitations in rather ad-hoc ways, and have tried to address them in the same fashion (see Andreas Rossberg's recent comment for instance).

Is it not telling that a "problem" OO languages have only recently recognized and addressed was already addressed by ML over 15 years ago?

Is it not telling that a "problem" OO languages have only recently recognized and addressed was already addressed by ML over 15 years ago?

Some OO people recognized this problem a long time ago, well before 15 years ago. The thing is, they argued for a completely different solution from what ML came up.

David Harland has some particularly good rants from the '80s about this stuff. So you can't say it wasn't recognized.

In my books, languages designed since Smalltalk-72 seemed not to really do much to address it. Not being rooted in logic IS the best explanation for this. However, I also think many language designers were led astray by being concerned mostly with efficiency, and abstraction second. This quickly leads to OO that violates encapsulation, and is not very OO.

I don't understand why anyone thinks Dependency Inversion Principle is something we should hate or mock or whatever. All it explains is how two modules should interact: implementation hiding, relying only on interfaces that identify what each needs of each other. This has consequences beyond just describing *a good* abstraction, and also explains what *a bad* abstraction looks like. You don't need math to understand this, making it accessible to programmers with not abstract mathematical understanding. However, math can help enforce good design, but math can also be easily ignored!

The thing is, they argued for a completely different solution from what ML came up.

Have any pointers I can read? I'm curious about these solutions.

So you can't say it wasn't recognized.

All I can say, is that every language with a strong formal foundation does not unintentionally suffer from these problems, which suggests strongly that some correspondence with logic helps these language designers avoid these pitfalls.

I can also say that most well known languages that I know of which were not built from a formal foundation, all seem to suffer from these problems, even a language created as recently as 9 years ago (C#).

I don't understand why anyone thinks Dependency Inversion Principle is something we should hate or mock or whatever.

That wasn't my intent, nor was it Andreas'. He was just pointing out that OO afficionados often present Dependency Inversion/Injection as an OO innovation, mostly due to ignorance of functional languages. The principle itself is great, though auto-wiring seems dubious; I much prefer configuration by type classes (which I just noticed has been mentioned here a few times, but never had its own story).

I think the only thing OO languages have over ML here is the fact that modules are sort of first-class values, so you can parameterize an ordinary function by a module signature/interface, instead of resorting to a separate class of terms on modules, ie. functors; in a way, this is simpler to grasp for newbies, and, please correct me if I'm wrong, partial evaluation should make them equally efficient.

Of course, popular OO languages limited themselves again by supporting type polymorphism, but not type constructor polymorphism. Many MLs now support modules as values too, so this isn't much of an advantage anymore, but OO currently has the momentum.

FWIW, the ML module system was invented in the early 80s, and many of these ideas already were implemented in the 70s (cf. CLU etc.).

I settled on 15 simply because I'm only passingly familiar with the rough history up to Xavier's OCaml papers, which were around 15 years ago IIRC. I knew ML modules had a longer history, I just wasn't familiar enough with what was considered state of the art back then to make an authoritative statement. Thanks for the more authoritative answer!

You speak of OO languages as if they were persons. Atrocities committed by some practitioners of OO were not in any way endorsed by the paradigm itself. The very ability to implement, say, the visitor pattern does not render it a good solution approved by the OO holy book.

I am sure we can commit atrocities no matter what the paradigm.

Atrocities committed by some practitioners of OO were not in any way endorsed by the paradigm itself.

I pointed out that formal languages do not suffer unintentional expressiveness problems in the same ways that informally designed languages do; the anecdotal evidence for this point is compelling.

This has nothing to do with how users of a language abuse it, or OO languages specifically, except to the extent that most OO languages in use were not designed formally from the outset; you seem to be veering off on a tangent that is not related to my point.

... how the occurrence of some understanding gap between two peers in a (civilized) debate, regarding what was the point at hand in this instance, can inspire others with further thoughts and questions...

For, I think, naasking, you made really a good point there, actually; yes, here's my little take in a form of questioning (to all on the thread, not just you;) now, and that's on this you've just said:

"[...] This has nothing to do with how users of a language abuse it, or OO languages specifically, except to the extent that most OO languages in use were not designed formally from the outset; [...]"

(Where, well, I don't think I could ever have put it better)

But, wait... Has any programming language been designed formally, ever, actually?

I mean : what do we mean, exactly, by "designing formally" a PL?

It seems to me we often tend not to pay enough attention on the actual accuracy of our claims and/or concerns, there (in good faith or not, but ... that's irrelevant).

"To design formally" : one verb, one adverb.

Design : makes you immediately think about the predictable task (for the language's inventor(s)) of giving to the public, at some point, a rationale for the language. Simple examples, small scopes. Larger ones, broader scopes. Then, come the design goals. The non-goals, each of those backed up with the best use cases that have been in mind, etc.

Now, formally : of course, one knows upfront that the taste of syntax (with or without the general processing model) will be anything you want, but certainly not sufficient.

So, you'll need to provide details about how the reference implementation for the standard semantics has been driven; what interpreting a phrase of the language must be and, sometimes, as a guideline to avoid some mis-implementation pitfalls, what it certainly can't be.

You'll have to address the issues about which compromises had to be made doing so, and why such "discrepancies" (that one wants as small as possible) were to be dealt first, about performance aspects, or related to platform independence, portability, or etc, to at least ensure you provide enough materials to help (yourself/others) to check the conformance of this and other implementations regarding it (the semantics) -- modulo the very implementation issues themselves. And of course, assuming that semantics has been formalized comprehensively enough somewhere.

But what about all the other types of most-of-(all?)-the-time unsustained claims such as :

"this language is: functional and lazy (or eager, or, etc) and supports this, or that, and is also reflective, ... etc, because it aims to perform better at solving this or that problem, etc".

I've seen nowhere a "formal design" of a language which would want to be so systematically formal that it would even go up to provide some formal evidences that its whole set of semantic capabilities / features gathered together, re-explained for that purpose if necessary, are the optimal ones to address this or that specific non-trivial problematic(s). I mean, in a given (be it arbitrarily chosen) ontology some problems of which are well-known / have been studied enough and for which several "real world" examples are available (via some functional requirements doc and another, necessary to know, about platform-related constraints).

Some languages have indeed suffered by the past from a very poor overall formal "equipment" of their definition ("poor" be it in the strict sense of very little elaborative materials about what the language is, or in the sense of rich, but too much informal definitions of it).

Others, and it's now happily the standard "trend", go in great lengths of formalism about their intrinsic capabilities (in composability of the programs/functions they can breed, their general computability power, in well-studied local computation schemes, their integration features into other runtimes and frameworks, etc).

But where's the language which is so obsessively concerned with formalizing itself unambiguously, right from its design stage, does dare to give clues about how one can rationally, provably confront its whole feature set against several dimensions of a given non-trivial problematic, and not just each of them, only one at a time?

Either it still isn't out there, or, I haven't seen it yet.

Has anyone? I'm really, really, interested.

(Now, I wouldn't mind to accept it's just I gave a way too strong meaning to "formal design" above; you can just let me know ;)

[EDIT (fixed several typos)]

All languages we are speaking of are formal languages here. I don't know what you mean by "informally designed languages". Are Java & C# "informally" designed languages? (I am guessing that by formal you mean languages based explicitly on a typed LC).

Speaking of expressiveness problems, and since you obviously read Functional Pearl: Implicit Configurations —or, Type Classes Reflect the Values of Types, by Oleg Kiselyov and Chung-chieh Shan, could you please explain what the problem was with using just Haskell98 without any extensions, which is (iiuc) a perfectly formally designed formal language? Or, was this an intentional expressiveness problem of Haskell98?

Or, maybe you are more comfortable with unsafePerformIO in configuration sections of code, or the reader monad infesting everything where configuration needs to be accessed, than with dependency injection as the latter is not formal. Fine with me.

You can indeed find many, many of them, in the history of OOPLs.

Such as C++ to start with one from the first OOPLs that received what you can call "broad acceptance" in the sw. industry (i.e., not only in the scientific communities but also for business applications); which, I suspect, remained without any formal definition of its semantics for a long time (actually, I'm not even sure I've seen it somewhere, yet, btw??); or also, many flavors of "Object Pascal", etc...

(I believe that's one of the breeds of languages that naasking was alluding to.)

Now, that said, and as lame as it can seem as a lookup to spot them, I suppose its quite easy :

[google] "formal semantics of {whatever}".

(Worked for me several times, anyway ;)

Are Java & C# "informally" designed languages? (I am guessing that by formal you mean languages based explicitly on a typed LC).

Typically, but not necessarily. If a language gets a formal treatment at all, it's after the fact, which is too late IMO.

Compare the complexity of the C# formalization to ML's, and then compare their expressiveness. And the C# formalization doesn't even encompass the entire spec.

could you please explain what the problem was with using just Haskell98 without any extensions, which is (iiuc) a perfectly formally designed formal language? Or, was this an intentional expressiveness problem of Haskell98?

Yes, it was intentional to an extent. This limit is dictated by the state of the art at the time when defining the language. What was the state of the art when C# or Java were defined?

As already pointed out, we had decades of parametric polymorphism and higher kinded polymorphism, and yet these languages not only omitted these features, when the omission was eventually acknowledged as a mistake, only half the support that academic research implies is necessary was added (no type constructor polymorphism); the LINQ provider model could certainly benefit from this additional safety.

When a language's expressiveness limit is reached, "design patterns" emerge to address these scenarios, such as the paper on implicit configurations; these design patterns point the way to generalizing a language even further along abstraction boundaries encountered in real programs.

The point is, these languages didn't have artificial limitations placed on them. See for example the restrictions C# places on type parameters, restrictions which have no safety implications, and have no justification in the C# spec. My hypothesis boils down to one of two scenarios that I can see:

1. In a long spec like C#'s, these interactions are easy to miss or ignore, but with a more formal approach, superfluous restrictions are more apparent; using C#'s type parameter restrictions as an example, someone looking at the type rule for type parameters would see its complexity, immediately wonder why it's so complex, go searching for a justification, find none, (correctly) conclude the restrictions are unnecessary, and thus, that they limit the language's expressiveness for no benefit.
2. The people used to reading and defining formal semantics are simply aware of the need for minimizing unnecessary restrictions, but the people writing specs are not.

I believe the people behind Java and C# are intelligent and well-informed, and so I lean towards believing the first explanation.

than with dependency injection as the latter is not formal.

Actually, as Andreas already explained, it is formally understood as "abstraction" over module-like entities.

"Opportunistic pragmatism, huh?"

Just a wink where I meant, and as I'm pretty you're aware of it too, sometimes the language's inventors/designers/reference implementors also have to deal with making sure the language won't be too difficult to implement (as in the case of C#, for what I know; for Java, I can't tell), that's why I'd add :

3. For the sake of having a language for which a reference implementation must be feasible and compatible with the requirement that you can prove its conformance, you need sometimes to put such restrictions. Without them, some formal proofs can become much trickier, especially when you contemplate to incarnate them in the intermediary language (IL) verifiers/checkers used by the runtime/JITter themselves. I believe that's probably the main kind of trade offs they accepted to acknowledge, between a) the language's orthogonality/expressiveness (lowered by those restrictions you mentioned) and b) the actual feasibility of... well, shipping "The Compiler, the Runtime, and Everything" on time.

[EDIT]
By the way, I do agree, there: laying down the formal semantics of a PL after (or even, sometimes, way after...) it has been implemented (and libraries built out of it, etc) is not very "clean/natural", and is certainly even less "wise"...

The restrictions I refer to make the type system MORE complicated, not LESS complicated. For instance, C# prevents a type constraint from specifying Enum or Delegate, but there is no safety or runtime reason for this (in fact, the underlying CLR supports this type constraint, it's just C# that doesn't).

In a spec, these restrictions sometimes seem reasonable, but they add complexity to the formal model. If you start from a formal direction instead of an informal one like a written spec, the pressure is towards more compositional designs which are simpler to formalize, and which turn out to be more flexible for end users anyway. Scalable software development is all about composition.

Ok, now you're being very specific ;) Yes, agreed, then; I still have hard times trying to figure why some of those are in there; maybe I'll get it one day...

And funny coincidence you mention that, by the way, since it's been exactly the kind of things I had to fight against, in C# (2.0) recently, where I've been using constrained generic types (with class and non-class constraints)... let's say, "intensively".

Was to implement what some like to call it "fluent interfaces". I had to use some features of C# 3 too (Linq, etc) and no real worries there, but, yes, that's definitely some of the ad hoc restrictions put on generic types, legacy of C# 2, that were "the most annoying" (well, to workaround).

("[...] Scalable software development is all about composition. [...]" Well, I really, really can't agree more, honest!)

You were not citing an ML DSL for dependency injection. You were citing someone hacking Haskell to improve and/or change its expressiveness properties. (My opinion of those two "pearls" is that they are closer to swine in practice, but the paper elegantly shows how fancy ivory can be in theory.)

Hacking the compiler becomes a question of whether or not you've changed the compiler, especially for an optimizing compiler. This is part of the beauty behind Kay's vision of autonomous entities each with their own syntax-directed interpreter, capable of serving as a "computer" hook into a massively large scale network. -- As I understand it, Kay did not like the direction Ingalls was taking Smalltalk by allowing changes to the compiler itself (thus creating the image versioning problem where the image of the system was tightly coupled to an implementation of the system, a problem VPRI is now seemingly trying to correct in its FONCS project), but Kay was also predominantly interested in programming for children. I believe Ingalls briefly refers to this split opinion in the book Coders At Work.

CS is now approaching this modularity challenge on multiple fronts. Probably the most interesting is from the East London Massive cliq, but also at INRIA with Xavier LeRoy's integrity model for compiler architecture.

[Edit: I know absolutely nothing about GHC's compiler architecture, or any other Haskell implementation. I only know Haskell from the point of view of somebody who only learned Haskell so I could read blog posts and research papers about the language.]

I don't see how formality saves our souls. They are another medium of expression for giving "implementations" in a logical language. We might be a little spoiled because the critical, conceptual ability of generations of mathematicians almost lead to a unity of concepts which are clear and formalisms which are effective but this coincidence isn't self-evident and it is not self-established by the magic of formalisms.

Formal approaches pressure the designer towards simplicity and composition because of the ultimate requirement to prove various properties (soundness, etc.). There are no such pressures in natural language specs, so it's much easier to over-complicate them by comparison. The reason needn't be more complicated than that.

Meyer did a great job, there, by the way, IMO. He manages to define Eiffel without over-complicated natural language specs of the language, while giving at the same time, in parallel, and for every single construct of it: the formal validity rules of their syntax, and semantics at compile time (not limited to, but most often for the static typing part) and at runtime (not limited to, but most often regarding how that must behave to ensure his "Design By Contract" is respected).

And also comes along with the rationale behind the constructs.

That ends up being quite pleasant to read (for implementors) and, still, "formal enough", I guess. Now, it's no secret to anyone that the resulting Eiffel language is pretty difficult to implement compared to many other OOPLs. However, as we know, this doesn't have much to do with whether you defined the language strictly formally or not; a purely formal definition of the language is for sure to help implementors, especially regarding conformance of the implementation, but is in no way enough to orient them (implementors) towards an easy and/or efficient one (implementation), a priori.

But well, there, to be fair, one also has to take into account the final expressiveness power obtained as a whole in the case of Eiffel:

full multiple implementation inheritance support, constrained and unconstrained generics, powerful statically-checked feature export policies, feature renaming and deferred features "merging" when and only when it's necessary and safe, pre/post conditions/invariants (DBC) with a semantic that acknowledges the sub-typing, no need for the notion of static classes or features while allowing for "once-" and unique-valued features, if you really want to represent "enums", etc, and many other "De-Luxe-OO", say, "sweet spots"...

But again, the debate whether you actually need or not "all of this power" in the OOPL itself and upfront, is another one, I suppose.

and yet co/contra variance of methods was broken, if i recall correctly. in other words: programming is hard.

Well, yes, it is.

Now, one cannot really blame the Eiffel folks of not being aware of this kind of "tricky" issue for quite a time, already. Even way before this paper, for instance.

But, since you mention it (the issue): indeed, it's going to be interesting to see how the next flavor of C# (in both its definition and implementations) will handle that its turn, as well^(?) ;)

^(?) [EDIT 31/12/09 03:15PM EST] Ah. Ok. E. Lippert gave us some clues about that, already.

(Hmm... C# 1.0 < C# 2.0 < C# 3.0 < C# 4.0 == quite a beast too, now, anyway!)

Joel, I like your very common sense view on these topics. Probably a lot of the "promises" made are trade press hype generated either by a research community in search of funding or by a commercial community hoping for successful commercialization ("C++ is easier than C" was one of the sadder OOP hoaxes I witnessed over the years.) And yes, a general "halo" of (sometimes unintended) effects surrounding the sum of PLT activity very, very likely has great benefits for the larger software engineering community.

I still hope to hear some tales from the PLT "veterans" here on LTU regarding PLT innovations sadly either left to languish on the drawing board or eventually thrown into the bit bucket - and what might be the circumstantial themes that can cause this.

Scott

I love this characterization of the cycle from Things Could Be Better to The Next Big Thing After That.

1) Tail call optimization. Evidence: absence in Javascript and JVM, two contexts where it would be a huge win. Speculative reason: Historical accident of omission by the original authors of each, followed by economic inertia when attempting retrofits to fix the omission.

TCO is present in the CLR, as an alleged "multilanguage VM", but not really. It's crippled, because an efficient implementation was supposedly not possible given the constraints of stack walking Code Access Security (CAS); incidentally, I think they've chucked most of CAS out with .NET 4, so maybe this will change sometime down the road.

I think your other points are interesting, particularly #5. I think the other points have valid technical reasons why they might not have caught on (yet?), but I wonder how the political reasons justifying 5 could be addressed.

There is now a patch for JDK7 which provides tail calls, so the open sourcing of the JDK does allow people to work around the 'economic inertia' to some extent.

See: happy new year! by Arnold Schwaighofer

Could you elaborate on how CLU's error handling mechanisms are better than mainstream exception handling? I found a copy of "Exception Handling in CLU" (Liskov & Snyder 1979), but it did not shed any light on the matter. As far as I can tell from that paper, CLU's "language-enforced" error checking is very weak; the language semantics require that unhandled exception types be silently coerced into "failure" exceptions. I have a hard time seeing how this is more helpful than simply allowing exceptions to propagate freely. Java at least gives exception signatures some teeth by rejecting method bodies that throw or propagate exceptions that are not allowed by a "throws" clause. (I should add, however, that most working programmers I know don't find Java's checked exception mechanism helpful enough to justify the resulting proliferation of declarations and boilerplate exception handlers.)

but i suspect it was in the vein of "exceptions suck, and are cop-outs for people who are too chicken-**** to actually do the work of dealing with errors where and when they could happen. which is most people. even when people use an exception approach, they just put a top-level handler that prints it out and keeps on trucking, rather than actually dealing with the exception. in other words, people suck."

?

Could you elaborate on how CLU's error handling mechanisms are better than mainstream exception handling?

Two reasons:

First, in CLU, all functions are total. There is no such thing as a non-local exit. I think that this makes the language easier to describe and easier to reason about.

Second, CLU's style of error handling is better for modularity. Consider the case of modules A, B, and C and their respective functions A:fn, B:fn, C:fn. A:fn calls B:fn which calls C:fn. For certain parameter values, C:fn will never explicitly raise any exception. Every interface declaration implicitly allows a function to raise 'failure', but the specification of C says that, barring something catastrophic, it will never raise an exception for a parameter value of "1". B:fn calls C:fn only with the parameter value "1".

We wish to make a correctness-preserving change to the specification and implementation of C:fn. New rule: for a parameter value of "13", C:fn will raise a new kind of exception ("new_exception").

Modifying C in this way should not require any changes at all to the specifications or implementations of modules A and B yet, in a language with Java-style checking, it will require one of these possibilities: (0) Coding B:fn to catch all exceptions in the first place, even though it only passes the safe value 1 to C:fn. (1) Modifying B:fn to catch and handle new_exception, even though that exception can't really be raised since B:fn never passes 13 to C:fn. (2) Changing the declaration of B:fn to say that B:fn can be non-locally exited with a new_exception, forcing changes to A:fn, even though in fact that case can never arise.

In short, the abstraction barrier between B and C is broken, with exception checking of that sort, and the damage can propagate to a breach of the abstraction barrier between A and B.

In a CLU-like system, static examination can yield something more useful. After modifying C:fn, it can *warn* that the call to C:fn in B:fn might (as far as static analysis can tell) convert an unhandled new_exception into a failure. (Various mechanisms could also be added to teach the static checker to suppress that particular warning so long as the parameter value remains 1, if you really wanted to bother.)

The above scenario describes modifying C in a way that never actually changes the behavior of B but we can also imagine scenarios where the change to C modifies the behavior of B but the implementations of B and A, and their declarations, should still not change. (Left as an exercise. :-)

Finally, it is true that CLU-style discriminated returns and automatic conversion to failure returns is nearly a dual of non-local exits as found in popular exception handlers. The difference can be understood as a "default".

We could define, in Java, a CLU_like_failure class of exceptions and code in a style in which every expression that might generate an exception must be wrapped in a generic exception handler that, by default, turns incoming exceptions which are not already CLU_like_failure into CLU_like_failure exceptions, and re-throws those.

If we coded in that tedious style, the modularity problems in Java would not be an issue - yet no expressive power would be lost (other than through the tediousness of writing all those exception handlers).

Conversely, we an simulate Java-style non-local exit for exception on a CLU-like system but without much tedium at all!. Our costs are that we need a static checker to issue warnings, and handlers expecting to receive a non-local exception must peek inside failure exceptions to find the underlying exception.

In that sense, the CLU-like mechanism is simply a more sensible choice of defaults.

edit: I forgot to include a link to A History of CLU, Liskov, 1992 wherein she provides a modularity based rationale for CLU's mechanism. And, heck, it's short so here is the relevant passage from page 15:

CLU provides an exception mechanism based on the termination model of exceptions: A procedure call terminates in one of a number of conditions; one is the "normal" return and the others are "exceptional" terminations. We considered and rejected the resumption model present in both PL/I and Mesa because it was complex and also because we believed that most of the time, termination was what was wanted. Furthermore, if resumption were wanted, it could be simulated by passing a procedure as an argument (although closures would be useful here).

CLU’s mechanism is unusual in its treatment of unhandled exceptions. Most mechanisms pass these through: if the caller does not handle an exception raised by a called procedure, the exception is propagated to its caller, and so on. We rejected this approach because it did not fit our ideas about modular program construction. We wanted to be able to call a procedure knowing just its specification, not its implementation. However, if exceptions are propagated automatically, a procedure may raise an exception not described in its specification.

Although we did not want to propagate exceptions automatically, we also did not want to require that the calling procedure handle all exceptions raised by the called procedure, since often these represented situations in which there was nothing the caller could do. For example, it would be a nuisance to have to provide handlers for exceptions that ought not to occur, such as a bounds exception for an array access when you have just checked that the index is legal. Therefore, we decided to turn all unhandled exceptions into a special exception called "failure" and propagate it. This mechanism seems to work well in practice.

The main decisions about our exception mechanism had been made by June l975 [Liskov, 1975b], but we noted that "The hardest part of designing an exception handling mechanism, once the basic principles are worked out, is to provide good human engineering for catching exceptions [Liskov, 1975b, p. 13]." We worked out these details over the following two years. We had completed the design by the fall of 1977; the mechanism is described in [Liskov, 1977b; Liskov, 1978a; Liskov, 1979b].

CLU exceptions are implemented efficiently [Liskov, 1978b]. As a result, they are used in CLU programs not just to indicate when errors occur but as a general way of conveying information from a called procedure to its caller.

I don't see CLU exceptions as being remarkable.

To me, there is only one model of exceptions that make sense: Dave Abraham's contractual basis for exceptions: the strongest guarantee is the no-throw guarantee (this is also known in Executable UML circles by its general state machine semantics as "Run-To-Completion (RTC) Semantics"). Then there is the strong guarantee, where moving the program counter is the ONLY side-effect. Then there is the basic guarantee, where no resources are leaked but invariants are preserved (possible side effects: the internal state may change, and the program counter is moved).

Furthermore, CLU couples caller to called procedure. This makes it very bad to use to implement state machine semantics. However, in imperative languages, people do it anyway, to take advantage of pointer-to-member-function operators offered by languages like C++. -- This often results in a text-based state machine description that is hard to comprehend and reverse engineer in diagram form. It makes more sense to describe a state machine in terms of a DSL like Ragel and let the compiler just efficiently compile it for whatever machine architecture you want to target. -- This is one idea behind UML Model-Driven Engineering for real-time systems.

Bottom line: I think the problem is mostly methodological, but do wish more languages offered Erlang-style exception handling. Exception handling tightly coupling caller to called procedure is not very useful, even in the case of systemic failures. It is especially not useful for communicating failures across systems, where a system is a "system of systems". Structured exception handling's premise is that you are using a layered architecture. BTW, it is very hard to implement such catchall exception handling correctly. Windows' .NET ApplicationException Considered Useless, one-size-fits-all exception handling being a huge gotcha in .NET and also Python 3000's silly idea to bifurcate Exception into BaseException and Exception. -- For example, SystemExit derives from BaseException and is a language-defined exception. Some people felt this was a good idea to let the environment have special exceptions, and somehow makes a difference. I guess they don't understand properties of monads and control partitioning.

[Edit: Tom's point appears to be about defining a domain of a function, in effect making the source text amenable to model checking at interface points.]

It seems to me that Dave Abraham's notion of basic, strong, and no-throw guarantees are an orthogonal question. Those are about how exceptions are or are not rather than about the semantics of raising an exception or the default behavior an unhandled exception. His comments would apply as well in a system with CLU-like exceptions.

(As an aside, his basic / strong / no-throw trichotomy seems a bit too simple-minded, to me. First, no-throw and strong guarantees are not often an option in non-trivial code so we'd really be better partitioning the basic guarantee up into a set of paradigms and patterns and talking about those. Second, he fails to account for the use of exceptions for things other than error handling.)

Re "Furthermore, CLU couples caller to called procedure. This makes it very bad to use to implement state machine semantics." I don't follow you. The CLU mechanism makes every function total and means that every function has, in addition to its "normal" return value, a "condition" value. The language let's you pick control flow based on the condition value and has the default behavior of turning unhandled conditions into failure conditions and the default of propagating failure conditions upwards. I agree with you that DSLs are nice for defining state machines although you could do some kinds of state machines directly with CLU exceptions in a nice way. If you haven't already seen it, have a look at Automata via Macros, Krishnamurthi, uh.. 2006(?).

Re your edit, "Tom's point appears to be about defining a domain of a function, in effect making the source text amenable to model checking at interface points.": I guess you could say it that way. I like that in CLU all functions are total and there is no such thing as a non-local exit (yet all the benefits of non-local exits are still available). That seems simpler to me. I like that correctness (to specification) preserving transformations of a module are better supported by CLU-style rather than Java-style exceptions. ("Better" in the sense of easier to code in anticipation of such transforms and easier to perform such transformations.)

As for the normal vs. condition value... returning a value is orthogonal to who you return it to. This is why implementing state machines using a stack-based, procedural message-passing language stinks.

The hard part about exception handling is not handling the exception at the call site. It's (a) cleaning up resources (b) deciding modularly who is responsible for handling the exception, and what policy that collaborator should take.

Your rebuttal seems to be that just because CLU allows you to do this, does not mean you will do it if you know what you are doing. My rebuttal would be that this is not clean or clear regardless.

I just found this link http://csg.csail.mit.edu/CSGArchives/memos/Memo-155-3.pdf

I'll read it more closely after the long weekend. Section II. Model -- A. Single Vs. Multilevel Mechanisms ... seems to be the definitive source.

Once again, assume A calls B which calls C.

B is specified to throw an exception of type X under some circumstances, and A is coded to handle X.

Then the C module is modified and, newly, now it too can throw an exception of type X. The problem here is that A's handler for X is inappropriate in the case where the exception comes from C.

A Java-style system will quietly accept the change to C and a bug has been introduced in A by an otherwise correctness-preserving change to C!

But in a CLU-like system, the mere coincidence that C chose exception type X is not enough to confuse A because, before A sees the exception from C, it will have been converted to a failure exception.

Then the C module is modified and, newly, now it too can throw an exception of type X.
...
The problem here is that A's handler for X is inappropriate in the case where the exception comes from C.

I disagree. If the handler is written assuming only B generates the exception type and then you allow A to, that means type safety was violated -- I argue this is actually a case of the type system not being powerful enough to encode what you want. Dependent types (I think Nikhil Swamy's Fine or Fable languages are great examples) give you a lot of this.

However, at a higher-level, this style of software composition sounds too fragile to me: I *don't want* such expressiveness to be used as we break B's encapsulation. The only exception to this that I can think of is for cases of fine-grained mashup security where you really do have different active principals that are sensitive to delegation chains, but this entire space is unclear and I'm not sure how relevant it is to the code most people write.

Robust error handling and good modularity are under-valued in the commercial market, thus exception handling is preferred because it affords more rapid development.

Error handling at call sites isn't particularly modular. Importantly, the policy for what to do in the event of an error ought to be separated from the call-site.

Exception handling better allows this separation of policy, but most implementations have a major flaw: without support for resumable exceptions (as you find in Lisp), the developer of the error-handling policy simply lacks many options other than to log the error and move on.

Handling partial failure is far from trivial, especially once security concerns get involved. Too many people underestimate this in language design.

Would you say the difficulty in implementing partial failure is directly related to the number of transititions a state can have to a failure state, as well as whether or not the failure state has to be tightly coupled to the previous state?

While state machines don't scale well, neither does structured exception handling -- scenarios can come up where it becomes very non-obvious how the caller should handle an exception from a method that can raise multiple exceptions (a good example of how non-modular structured exception handling is). Examples include the ones in Peter Haggar's Practical Java, but the same issues were discussed in C++ books before that. Can't recall if Joshua Bloch mentions this in Effective Java. I don't believe Bill Wagner discusses this in either of his Effective C# books.

Edit: Bloch's Effective Java actually puts things fairly straight:

exceptions are, as their name implies, to be used for exceptional conditions; they should never be used for ordinary control flow.
[...]
This principle also has implications for a well-designed API. A well-designed API must not force its clients to use exceptions for ordinary control flow.

...and...

Item 61: Throw exceptions appropriate to the abstraction
[...]
higher layers should catch lower-level exceptions and, in their place, throw exceptions that can be explained in terms of the higher-level abstraction.
[...]
While exception translation is superior to mindless propagation of exceptions from lower layers, it shoudl not be overused. Where possible, the best way to deal with exceptions from lower layers is to avoid them, by ensuring tht lower-level methods succeed.

This is extremely sound modeling advice, and reflects an Executable UML control partitioning best practice: subsystems should not be allowed to propagate exceptions to supersystems. Instead, they should both depend upon abstractions.

But he does not appear to cite Haggar's good example on the trickiness of the reader understanding complex exception handling logic. My Haggar book is in New York, and I'll be visiting my home library there this weekend. I'll try to dig up Wagner's example.

Edit: See also Rebecca Wirfs-Brock IEEE Software Design article What It Really Takes to Handle Exceptional Conditions. She does a very good job emphasizing modular collaboration to address errors and exceptions. This advice is more methodological and control construct agnostic.

I'm not confident I understand your question, but I wouldn't argue that handling partial failure is a challenge due to the number of ways to reach a failure state. Rather, it is a challenge due to the sheer number of different failure states, the difficulty in recognizing them, and the number of different ways to handle these failure states.

Potential for asynchronous, concurrent, and distributed failures can make it especially difficult to recognize failure. The potential need to handle more than one problem at a time also adds to the number of failure states.

It is problematic if there is more than one reasonable way to handle a failure scenario. If there is exactly one reasonable way to handle it, that way can simply be hard-coded into the system. If there is no reasonable way to handle an error, then one probably shouldn't even attempt to recognize it.

But if there is more than one reasonable way to handle a failure state, then you need to somehow support user-defined policy. And, usually, this is the case.

For example, if calling a procedure for each element of a list, what should you do upon receiving an exception? Reasonable options: continue operation on the list starting with the next element, retry the element, abort the loop and try something else. Which option is most reasonable depends heavily on the exception and on the context. A generic function for iterating across the list should not be the one to make the decision.

Error handling at call sites isn't particularly modular. Importantly, the policy for what to do in the event of an error ought to be separated from the call-site.

Nothing in CLU requires errors to be handled at call sites. CLU simply makes a distinction (by default behaviors) between errors handled at call sites and errors not handled at call sites (by wrapping the latter exceptions up as a "failure" before propagating). For that matter, nothing in CLU requires non-resumptive error handling, although CLU does require that the dynamic context defining resumptive handlers be managed explicitly (whereas in a typical lisp, a global "dynamic scope" is often available implicitly).

Thinking about the common case of "partially correct" programs, think of A:fn calling B:fn calling C:fn. For nominal inputs to A everything is fine but we expect that for some inputs to A, something unexpected will go wrong down the call stack. A:fn, we assume, is coded defensively against this. The automatic conversion to failure exceptions is very handy for this.

-t

Your earlier statement in this thread stated that exceptions are favored over checking at call sites because modularity is undervalued. My comment is that the alternative isn't especially modular. I was not speaking of CLU specifically.

think of A:fn calling B:fn calling C:fn

I think a more interesting example would be A:fn passing C:fn as a parameter to B:fn, resulting in A:fn calling B:fn calling C:fn.

That is, the definition of B does not have any knowledge of C. A possibly has knowledge of both, but may have received B or C as a parameter. The 'call-site' for C, however, is still inside B. And the 'call-site' for B is still inside A.

Your earlier statement in this thread stated that exceptions are favored over checking at call sites because modularity is undervalued. My comment is that the alternative isn't especially modular. I was not speaking of CLU specifically

By "checking at call sites" I mean CLU-like exceptions. Specifically, if an exception is not handled at the call site, then before propagation it is converted to (wrapped in) a failure exception.

Your earlier statement in this thread stated that exceptions are favored over checking at call sites because modularity is undervalued. My comment is that the alternative isn't especially modular. I was not speaking of CLU specifically.

In a case like this, with CLU-style exceptions, I think you would often want B to have an explicitly stated default handler around the call to C (around the call to the function passed to B as a parameter). This default handler in B would, rather than converting to failure, convert all non-failure exceptions (by wrapping) to something like "exception_from_the_foo_param_fn". Thus, B is not obligated to have any knowledge of the exceptions C might throw, yet A is never confused.

Perhaps it is possible to state the overall pattern I'm in favor of: If an exception is to propagate upwards multiple frames, the language should enforce a situation in which all intermediate callers must explicitly arrange for that propagation (otherwise it should be wrapped up and treated as a failure exception, indicating a second error of unanticipated propagation). This doesn't obligate intermediate callers to know in advance what exceptions a call might create. It doesn't mean that a change to a functions exception signature forces changes to directly or indirectly dependent modules.

When I say that the industry favors Java-style exceptions (or non-locally escaping exceptions without even Java-style static checking, as in lisp) because the industry undervalues modularity, I say so because I see no other explanation for the neglect of modularity concerns in these other exception mechanisms (and in how they are commonly used). In these other systems, if an exception is not handled in one frame, it propagates upward without any modification - there is no signal to the eventual handler of where the exception came from. The handler can't tell if this was the exception it expected, or a case that was not anticipated. Java's checking attempts (but does not completely succeed at) creating a situation in which every module must accurately anticipate all exceptions that might propagate past it but that then creates a problem wherein a correctness preserving change to one module can require purely book-keeping and misleading changes in an arbitrary number of directly and independent modules.

CLU got this one right.

Ideally, a service should always stick to a well understood protocol and contract with regards to both success and failure states. Also, propagated exceptions may reveal implementation details of a service, which has security ramifications and enables accidental accidental coupling against the implementation details.

Thus, to avoid propagating exceptions across service boundaries is a 'right' move. CLU certainly achieves this.

But it strikes me as heavy-handed to avoid propagating exceptions even within service boundaries. If A:fn1 calls A:fn2, or even A:fn1 calls A:fn1 recursively, should programmers be forced to wrap or transform or explicitly duplicate and propagate each exception from the callee?

I'm still giving that question some thought. It may be more 'parametric' if the caller is forced to wrap unknown exceptions (as an exception from parameter C when called from B) before propagating them. That is, one could give B a generic type:

  B :: (X -> Y ^ Z) -> [X] -> ([Y] ^ (f | wrap(Z)))
  C :: d -> e ^ f ;; C takes d then returns e or raises f
  {B C} :: [d] -> ([e] ^ (f | wrap(f)))

and there is no risk of the 'f' exception from B being confused with identically structured 'f' exception from C (which would be raised as 'wrap(f)').

I came to much the same conclusion about modularity issues of exceptions, though my primary motivation was security. In my current language design, exceptions propagate across procedure calls, but not across communications between objects (which, in my language, are akin to distinct processes or services). But I've not spent much time on parametricity issues - I'll give that some more thought.

I like your idea a lot but here's an alternative that might be simpler yet still satisfy the goals you describe:

In our new hypothetical PL, dubbed "YKNOT"[*], every function call must be explicitly marked to either wrap or not wrap unhandled exceptions. Thus, ".foo(a, b)" calls foo with params a and b and (because of the "."), wraps unhandled exceptions into failure exceptions. On the other hand, "/foo(a, b)" propagates unhandled exceptions without modification.

Given sufficiently rich mechanisms for syntactic abstraction, and the "." and "/" function call operators, libraries can implement service layer modularity and many other paradigms as well.

Intuitively, I do not believe the above scheme would work out so well.

With regards to type and implementation, it can be made to work. Each procedure call would now have three types: return type, first-generation exceptions type, and a second-generation exceptions type, any of which may be variant. When an exception is emitted, it carries a hidden flag indicating its generation. 'failure' would substitute for all second-generation exceptions in the '.foo' procedure call.

Where I believe it fails is utility. I suspect that developers would be deciding at the point of procedure development the means by which each procedure is intended to be called. This, in turn, means there is high potential for accidentally calling the procedure the wrong way (especially when dealing with first-class procedures).

An alternative: have a variation of 'throw' (perhaps taking a label) that cannot be caught by the lexically local try/catch block. This allows a try/catch block be fitted with a generic catch-all that will not interfere with select locally emitted exceptions. The catch-all can emit a generic 'failure', or do whatever else is deemed appropriate.

Ah, I like this discussion very much and I find dmbarbour's last proposal especially interesting. Here's my contribution.

Please, though, just don't try to find any parallel with Java's exception handling semantics, and acknowledge, rather, that I merely focus on building a bit further upon the one found in C# (refresh your memory about this guy if necessary) and dmbarbour's "throw" statement's local "clue". Thanks ;)

Also, I'm sure that this below will raise some more issues; and I'm glad in advance you can spot them and propose on how to fix them, well, assuming you find the idea interesting enough otherwise.

Here it is:

class X {
void localServiceA(...)
{
  //...
  if (problem)
    if (localProblem)
      // Should propagate up to "actual" clients & not caught by type-local catch()'es
      /* From the PoV:
         current class 'X' seen as a supplier only for non-derived callers of it; then :
         thrown exception can be caught by its client (caller) 'C' iff not X <: C */
      this throw new FileSystemException(...);
    else
      // Should propagate the error as usual
      /* From the PoV:
         current class 'X' seen as a supplier for any caller of it; then :
         apply C# 'standard' mode */
      throw new SomeOtherException(...);
  //...
}
void localServiceB(...)
{
  var supplierY = ...
  try
  {
    //...
    supplierY.foreignServiceY(...); // (can throw FileSystemException)
    localServiceA(...); // (idem)
    //...
  }
  catch(FileSystemException fsErr)
  {
    // Would catch supplierY's FS exceptions, for instance,
    // but not those thrown by localServiceA if the 'this throw ...' syntax was used
    // (neither those from other X-derived class types' methods where 'this throw ...' is used)
  }
  catch(IOException ioErr)
  {
    //...
  }
  catch(Exception otherErr)
  {
    // (for usual 'catch all' pattern when no other catch clause activated)
  }
  finally
  {
    // (for usual proper resource handling insurance, etc)
  }
}
}

Thus, 'this throw ...' is a way to have the current class type's implementation express its will to propagate a specific exception type across the client-supplier (i.e., caller-'this' callee) relation's boundaries, without having itself ('X', above) notice that exception and catch it improperly by an unwanted, somewhat biased activation of its type-local catch clauses.

Your thoughts?

[EDIT] Of course, one could prefer 'local throw ...' or 'class throw ...' as alternate syntax, instead of 'this throw ...' (for the sake of representing the semantic idea better maybe).

[EDIT 01/01/10; 07:55PM EST]
Hmm. I can find a couple important issues with my proposal, there. To start with: 1/ it's CLR-intrusive, actually (though not CTS-), and 2/ I suspect, security implications too, because of what needs to walk across the stack frames. Others(?)