Lambda the Ultimate

One day, a very handsome young man came along. His name, surprise surprise, was Narcissus. Echo fell in love with him at once. Echo wanted to call out, "Wait! I love you!" But her voice was frozen in her throat by Hera's curse. The young man went deeper and deeper into the forest, until he came upon a calm stream. He was thirsty and so he bent over to drink, but as he leaned over he caught sight of his reflection in the water. He was as taken by his beauty as Echo had been, but without her barrier. He immediatly spoke to his reflection, "I love you." Echo, nearby and hearing her chance quickly responded, "love you . . ." But it was too late, Narcissus was too engrossed with himself to notice the nymph. His love was his obsession and would not leave the stream to eat, nor disturb his image to drink and so he died of thirst and hunger and unrequited self-love. — Echo & Narcissus

The 'dynamically checked properties' seem to be a detail of library implementation and the 'statically checked generics' seem to be a change in language implementation.

And so then what is the benefit of the following list of Froboz, each with or without a dynamic property?

List<Froboz> list = ...
for frob in list {
    if frob.hasProperty("Lugnutz") {
        ...
    }
}

The 'dynamically checked properties' seem to be a detail of library implementation and the 'statically checked generics' seem to be a change in language implementation.

Ah. So dynamic libraries are good, but not dynamic languages?

I don't subscribe to the language/library dichotomy. I think they need to make sense as a whole.

Let me tell you a little story about a little project at CMU that did exactly the same thing. The name of that project is Garnet, and the name of the object system is KR. Now, as you may be able to guess by the acronyms, KR originally started out as a knowledge representation framework, and turned into an object system after someone looked at Kiczales' PCL for 15 minutes and decided it was slow. Now, each KR object is actually a symbol, with the slots stored on the property lists, the slots could be added at run-time (but it didn't do the deep-bound slot inheritance, which I've seen proposed in other OO systems), and relationships could be established via an (in this case, genuine, fully developed) one-way constraint solver. Doesn't sound too different from what "Avalon" is doing, doesn't it?

Everything is a-ok with this approach until you actually start (ab)using it, which you can't avoid doing. Whatever you put into these property lists should be stuffed into a slot in the first-class object in the first place - after all, this is what slots are for. With KR and Javascript, this isn't a problem as properties = slots, but I can't figure out whether this is the case in .NET (to be perfectly honest, there's a lot that I can't figure out about .NET). Then there's the fact that these are property lists - you really can't do worse than a linear search on pointers when you've got "hundreds of properties."

Anyway, to finish the story: KR is now much slower than any half-decent CLOS implementation, and provides almost no advantages. Property lists are bad because you don't know when someone might want to add one at run-time (leading to confusing naming conflicts), and they waste a whole pointer per symbol (because today nobody uses them).

If you really need to flag objects on some arbitrary basis, use weak references (but that'd be solving a design non-problem by introducing a real one). If you need to add/remove slots at runtime, add that ability to your language instead of tacking crud onto every object. I seriously hope this won't be adopted too widely by developers, so it can be removed without much pain when Microsoft decides it needs to get rid of some feature bloat. Another problem I can immediately see is the "dynamic calculation" of properties and events - will there be a real constraint solver, and if not, how are they going to deal with circular propagation?

Now here's a couple of unrelated things I want to mention:

While we're on the subject of misdirected and misused classical references, here's a little gem I found on Slashdot some time ago:

But Lispers' attitude is more like "Mainstream? Who wants that? We are better than that! We have been here since the dawn of time, never growing old! You mere mortals cannot comprehend the heraclitean fire that is the eternal truth of the infinite mutability of Lisp, the language of languages! Mwahahhahaha".
Anonymous

Being a Lisp snob, I also should point out this other post on the blog: Natural Language in Longhorn. Interlisp did spelling corrections (and more!) everywhere with it's DWIM package, and it's CLISP (Conversational Lisp) module had limited support for pseudo natural language commands. I believe Symbolics' Genera's Command Processor was pretty good at providing pseudo natural language interaction (at least it could handle a lot more grammar than CLISP did). Actually, I'm kind of glad Microsoft is finally innovating into the 80s, as the open source people mostly still seems stuck a decade behind.

Well, yeah. I think sometimes it surprises people to find out Lisp has hash tables, arrays, classes and objects, etc.

The problem is every new feature in dotnet is going to be used to the hilt with enthusiasm as if it is the greatest thing since sliced bread. Then and only then will the lessons of the past 40 years be learned. Surprise! People were using property lists in 1959 and there is some collected wisdom available.

If you need to add/remove slots at runtime, add that ability to your language instead of tacking crud onto every object. I seriously hope this won't be adopted too widely by developers, so it can be removed without much pain when Microsoft decides it needs to get rid of some feature bloat.

Which is exactly the irony I'm seeing. Many of the same people will be saying "Oh, no, you *need* generic types, this and that." and then will be saying out of the other side of their mouths, "Dynamic properties are killer!" If they just had a simpler language...

And I don't doubt this feature will be used to its fullest extent. More cruft for our systems to accumulate. There's no standing still, but there's also no looking back from where we've been collectively. Everything old is new again.

I will believe that when I see how Lisp can do declarative concurrency in a concise way (not just as a library) :-) .

Some Python, just because:

class Froboz:
   pass


frob1 = Froboz()
frob1.lugnutz = "xyzzy"


frob2 = Froboz()


bunchaFroboz = [frob1, frob2]


for nextFrob in bunchaFroboz:
   if hasattr(nextFrob, "lugnutz"):
      print nextFrob.lugnutz


# Or, more Pythonically ("it's better
# to ask for forgiveness than to ask
# for permission"):


for nextFrob in bunchaFroboz:
   try:
      print nextFrob.lugnutz
   except:
      pass

This is one of the things that drives people especially nuts about Python - the fact that any object at all can be assigned any attribute at any time, irrespective of what its class says it might have. It's the same with Javascript, IIRC. In either case you can more or less construct an object on the fly by defining functions (in Python's case taking the explicit "self" argument - with Javascript, I believe "this" is passed implicitly?) and bolting them onto an instance of a class skeleton (like Froboz, above) as required. Metaclasses can use this facility to modify the members of objects on instantiation, for instance in order to wire in some indirection (like an AOP interception stack) or enforce some access policy. But none of this will be even remotely new to anyone familiar with CLOS.

Thanks. Because Python is the *tool* and not the *discipline*.

Straighter jackets tend to confuse the two notions. But once the kimono is opened a little (e.g. "dynamic properties"), you may as well open the *tool* all the way, and count on the *discipline* to take over.

I cannot interpret this blog item without a decoder ring, but one interpretation is that D.Box would like to see a real simple dynamic language have a place at the table for Longhorn.

I think the Javascript way is pretty sweet as well:

function BaseClass(greeting) {
   this.greeting = greeting;
}


function addedToObject(addressee) {
   this.showMessage(this.greeting + " " + addressee + "!");
}


function addedToPrototype(message) {
   alert(message);
}


function runExample() {
   var anObject = new BaseClass("hello");
   BaseClass.prototype.showMessage = addedToPrototype;
   anObject.greet = addedToObject;
   anObject.greet("world");
}

In the cases of Javascript and Python, I think you have to pretty much give up on the idea that objects have classes that correspond to types. I know that Python objects really do have types, but given that you can swap all of the attributes of an object of one class around with the attributes of an object of a completely different class at run-time it seems to me that the "class" of a Python object is at most an advisory tag: "may contain lugnutz". There's absolutely no scope at all for any kind of automated type-discipline there. In truth, a Python object is still much like what Python objects used to be under the hood: a dictionary of values, some of which happen to be functions.

Yep. It's the same with Smalltalk too. You can pass any object as an argument as long as it will respond correctly to the way it is used. The "class" means nothing, it's just an implementation mechanism.

These are the simple notations as tools. What matters is the discipline of how they're used. You can end up in a mess or on the mountain top. Once you get the discipline, you can see the mountain top pretty easily, without much machinery to get in the way.

That's misleading. You can pass any object as an argument - period.

There is no as long as it will respond correctly to the way it is used. That's what we gave-up when we chose an 'untyped' (Cardelli's meaning) language.

But only some will behave as expected. The others will *really* grate.

Och, it's this discussion we're having all over again...

Static typing, and static type checking, offer two practical advantages that I can see.

The first is that they lessen the burden of self-discipline on Dijkstra's "humble programmer". By declaring types and having a type checker check them statically ("at compile time" where this is meaningful; "prior to execution of any part of the code" in any case), the humble programmer can rely on the mechanical, thoroughgoing discipline of the type checker to ensure that a certain kind of consistency - consistency of usage for values of all declared types - is maintained.

This means that the humble programmer's finite mental capacity can be used for other things (note that this argument assumes that the mental capacity we would have used for keeping track of type consistency can be allocated to other tasks - that the same "part of the brain" can be used for a variety of programming-related activities).

The second advantage is that a good (that is, suitable for our purposes) type system is expressive. It allows the programmer to codify expectations into contracts in a formally unambiguous manner. Contractually speaking, we give our word that a value can be used in certain ways, and the type checker ensures that our word is our bond.

Now, what you can do with a dynamically typed language with full introspection that you can't easily do in a statically typed language is this: you can say "maybe". Quite a lot of the time, "maybe" is a word we don't want to hear (or say) when programming. Maybe my program will work. Maybe this function will compute the factorial of a real number - I dunno, give it a try. No: we want guarantees, provable correctness at best or an extremely high likelihood of success at least (advocates of unit testing are also trying to avoid having to say "maybe").

But there are circumstances in which "maybe" is OK; for instance, when it's wrapped up in a strong guarantee: "maybe this will work, and if it doesn't we'll fall back to something we know will work". Or, "maybe you'll send me an object that supports this convenient method; if it does, I'll use it, otherwise I'll do things the hard way (assuming that the object supports the methods needed to do that)". Or, "maybe in the future you'll want to use my code with some object doesn't support the full interface of the class it was written to work with, but that's OK because that code only uses a couple of methods of that interface anyway: just make sure you implement those".

The third case above is the most fiddly to accommodate in a statically typed language, because it requires that we should be able to decompose a type into the set of operations it authorises, compose a new type out of a subset of those operations, and recognise when two different types can both be whittled down to the same restricted type. This means being able to recognise when two operations permitted by two different types are the same operation (or sufficiently similar for it to be safe to use them interchangeably).

If it's a question of messages being sent to objects, you can do this by comparing names and signatures - but of course you have no guarantee that two methods with the same name and signature really "mean" the same thing at all. Type classes in Haskell (like Eq and Show) make it possible to group types together and guarantee that they share a set of operations, but you have to assert a type's membership of a type class explicitly: you can't infer it for any and all types that just happen to fit the mould (or just happen to look like they do).

Dynamically typed languages don't solve this problem, but they make it possible to proceed - with caution - in circumstances where the problem arises.

The second advantage is that a good (that is, suitable for our purposes) type system is expressive. It allows the programmer to codify expectations into contracts in a formally unambiguous manner. Contractually speaking, we give our word that a value can be used in certain ways, and the type checker ensures that our word is our bond.

Well put. This important aspect is all too often ignored.

Looks like.

It allows the programmer to codify expectations into contracts in a formally unambiguous manner. Contractually speaking, we give our word that a value can be used in certain ways...

And here we are back full circle, ladies and gentlemen, to the irony of statically type checked objects with dynamically assigned properties!

Welcome back, my friends, to the show that never ends.

It seems to me you can program with discipline or you can program with bondage and discipline.

You can't avoid the discipline either way, but bondage appeals to some people.

Out of curiosity, do any of those EWD documents record Dijkstra's views on static type checking?

I would guess he'd consider a proof of type-correctness as being so far from a proof of program correctness as to be completely uninteresting (and over-hyped). Am I right or wrong?

But that and his observation that testing can show the presence of bugs, but never their absence, suggests that those untyped types that are advocating unit tests should be careful before co-opting him for their own.

Intelligent, independent mind refuses classification into simple categories. More at 11. We will also be covering the a small skirmish in the typing wars, which thankfully dissolved into stupid comments...

The fact that you find it so burdensome to work within a fixed system is telling. Do you also consider it a form of domination when a programming language forces you to use a particular syntax, or evaluation order, or standard library? The bondage imposed by protocols like HTTP and UTF-8 must be especially galling to you.

Do you believe your free speech rights are being violated when you are told not to yell "Fire!" in a theater? Is it a burden for you to follow the rules of courtesy in conversation, or employ table manners at dinner?

Creativity is not just about breaking rules; it's also about following them, and communication of any sort requires mutual acknowledgement of an underlying protocol. Some protocols impose more rules than others, but that doesn't necessarily mean your creativity is being restricted. In some cases, imposing rules actually increases expressiveness and conciseness. For example, an HTML document is just a restricted sort of (say) Latin-1 string, which follows some rules, but I think you will agree that HTML is, in a significant sense, a strictly more expressive medium than Latin-1. An equation in mathematics assumes a plethora of underlying rules about denotation and substitution, but can encapsulate pages of more free-form exposition. In writing, we typically follow rules of composition and rhetoric, because they facilitate rather than constrain communication.

Robert Frost once said that writing poetry that doesn't rhyme is like playing tennis without a net. There are lots of artists who think that merely by rejecting historical conventions of form and style they are being creative. But rejecting capitalization and verse form alone does not turn you into e.e. cummings; you need to have genuinely new ideas, and there aren't many of those.

Luke: Out of curiosity, do any of those EWD documents record Dijkstra's views on static type checking?

Here is an extract about formal methods which I think is relevant (the paragraph breaks are mine):

It is not only that the design of an appropriate formal, notational and conceptual practice is a formidable challenge that still has to be met; it is worse because current traditions are hardly helpful. For instance, we know that the transition from verbal reasoning to formal manipulation can be appreciated as narrowing the bandwidth of communication and documentation, whereas in the name of "ease of use" a lot of effort of the computing community is aimed at widening that bandwidth.

Also, we know that we can only use a system by virtue of our knowledge of its properties, and, similarly, pay the greatest possible care to the choice of concepts in terms of which we build up our theories: we know we have to keep it crisp, disentangled, and simple if we refuse to be crushed by the complexities of our own making. But, obviously, the market pulls in the opposite direction. I still remember finding a book on how to use "Wordperfect 5.0" of more than 850 pages, in fact a dozen pages more than my 1951 edition of Georg Joos, "Theoretical Physics"! It is time to unmask the computing community as a Secret Society of the Creation and Preservation of Artificial Complexity.

And then we have the software engineers, who only mention formal methods in order to throw suspicion on them. In short, we should not expect too much support for [sic] the computing community at large. And from the mathematical community I have learned not to expect too much support either, as informality is the hallmark of the Mathematical Guild, whose members --like poor programmers-- derive their intellectual excitement from not quite knowing what they are doing and prefer to be thrilled by the marvel of the human mind (in particular their own ones). For them, the Dream of Leibniz [of "presenting calculation, i.e. the manipulation of uninterpreted formulae, as an alternative to human reasoning"] is a Nightmare.

In summary, we are on our own.

It seems that we are so caught up in discussing type checking that we never manage to have a detailed discussion about type system expressiveness. But for me that's the core issue, and maybe by explaining how I feel about this issue I can convey why "bondage" isn't the feeling I get from (useful) type systems. But first I must warn you: the only way to decide on this sort of question is to immerse yourself in the relevant programming style.

Before drawing a landscape or a portrait artists often draw one or more sketches. A sketch doesn't contain all the details, but helps the artist plan the overall structure of the painting. Perspective diragrams are used for a similar reason.

Types allow you to sketch the structure of your system, by defining the interface between components. The programming language let's you express these properties of your system. It should allow you to use an apporpriate level of abstract, to be as exact as you need, and to refine your sketch later on. On top of that, being a formal notation, with sound semantics, allows the language processor to let you know whenever there's a mismatch between the sketch and the actual drawing. Often the reason is simply that your brush slipped, but in some cases the reason is that the sketch needs updating. This can be annoying, but if you fail to update the sketch, no more warning will be possible, so you accept this burden as a minor annoyance.

Since the final artefact isn't a static painting ut rather a software system that interacts with its environment, we can benefit from typing even during runtime (invalid input data, etc.) Since the system may evolve over time, types have impact on maintainability. Since types establish abstraction boundaries, they can get in the way when you need to cross these boundaries. Sometimes these effects are what you want, sometimes not. Be that as it may, types allowed you to specify important elements of your program declaratively as part of the program. It helped you program by stepwise refinement. Most importantly, it allowed you to sketch the structure of your system in advance, freeing you from having to remember unimportant details all through coding and thus allowing you to give free reign to your creativity.

A little compiler-enforced discipline can be helpful, though. It's also possible to have convenient access to both, which is something that we usually don't talk about. Frank's demonstrated how easy it is to add a dynamically typed layer on top of a statically typed one.

Now, what if we made it also convenient to do so? Some languages do. Dylan and Goo come to mind, but the most recent example I can think of is from Nice. It's got a very expressive ML<: (ML + subtyping) type system with some extra bells and whistles, so lots of static checking. But you can still do things like reflection very conveniently (notice lack of casts or conversion functions):

Foo f = newInstance(someclass, [arg1, arg2, arg3]);

calling things by reflection is similarly easy:

Object o = someObject;
SomeTypeIKnow result = call(o, "methodIKnowIsThere", [1, "hello"]);

The type of call is <!T, R> R call(T obj, String methodName, Object[] args), which means "Given an object of any type T, a string name, and an object array of args, return whatever result type R is expected at the call site".

So using these reflection facilities in Nice is just like casting, but it's implicit, so it shouldn't slow down DT afficionados one bit. Also, Nice infers types for many local variables, and types don't have to be specified when you're overriding a method, so the keypunching burden of the static type system is pretty light.

This seems like a good compromise to me. You can depend on the JVM to catch runtime errors instead of crashing your system, you can use highly expressive static typing throughout your program, and in the little bits that need to do things like reflection, you can do that in a very low-overhead way. This doesn't seem like "bondage" to me, it seems very helpful.

Not "fixed" system so much as "complex system"

That is why I am holding out for improved type systems to evolve out of Haskell, etc.

testing, absence of bugs, etc.

I don't need to prove the absence of all bugs very often. In fact, let me see, right. No, I have *never* had to do that for any software I have ever written. There are cases where this won't hold, but in 20+ years of programming I have not been paid to consider any of them.

Demonstrating rather than proving the absence of the most likely, most critical bugs, has been sufficient. I am willing to adopt other techniques, but I know how to do this one cost effectively.

irony

Before this thread becomes even more predictable and repetitive, I will bring up the irony again: why statically checked an object with dynamically assigned properties???

Let me share a recent epiphany ;-)

James Gosling was talking about maintaining the configuration of large scale distributed systems:

In some sense, the brilliant thing that Tim Berners-Lee did was simply to say, "I don't care." For 20 years people had been failing to solve these problems in any large-scale way. Berners-Lee decided to just do the simple obvious thing that solves the problem he needed, namely, getting ahold of a resource. ... He did that, and that enabled a lot of what the Web is today. But the Web has all these problems. What happens if a Web page moves or gets deleted? ... On the one hand, the URL design has made the Web somewhat fragile. Broken links are all over the place. On the other hand, if they had tried to really solve that problem, the Web never would have happened, because the problem is just too hard.

In a similar sense, the brilliant thing that Smalltalk did (25 years ago) 'was simply to say, "I don't care."'

Sending a "message" in Smalltalk is like requesting a URL - maybe a method will be found (maybe a resource will be found), maybe the method will do what you expected (maybe the resource will be what you expected). And maybe it won't.

Erlang and Clean and Smalltalk and Nice are such fun!

I like this analogy for how the mechanisms work.

The one thing I would add is regarding reliability.

You have more control over a Smalltalk system than you do on the web at large. So while the cost of a failure is significantly higher, the probability of occurence is significantly lower.

Doesn't Erlang have an associated design pattern that basically says "expect failure from time to time; don't be paranoid about it; recover from it at a suitable juncture"? I'm not well up on the details, but I did read somewhere that "defensive programming" in Erlang was discouraged and it was up to higher-up nodes in the control hierarchy to deal with the consequences of failure in lower-down nodes. This is in systems where I/O - which can go wrong at any time, no matter how rigorous your type discipline - is pervasive, and the sort of control you have over the comparatively closed environment of a typical Haskell module is simply not available.

Like I said, I think the key word in such systems is "maybe".

See Dominic's message above about Erlang. Once you go distributed to loosely associated collaborators, you are out of direct control, no matter what tools you've used and no matter what tools they've used. And so you need to expect failures and dynamically recover anyway.

http://www.erlang.org/ml-archive/erlang-questions/200304/msg00349.html

>> Don't worry about errors, just let it fail.  That is the Erlang way.
>> Like all things Erlang it sounds simple and easy, but is actually a
>> very subtle thing.
>  The real principle is "let some other process fix the error""

I would be interested to know if expert users of languages with complex/expressive type systems are never hindered by the systems.

Me for my part, I am a non-expert O'Caml programmer, and I am living in a hate-love relationship with the type system. Sometimes it lets me write code more beautiful than in any other language I know, while other times I have to jump through hoops, just to arrive at bad code.

Interestingly, `sketch' is also the word used to describe a certain style of program specification which evolved in category theory. I think in that case `sketch' was chosen both because of the analogy you suggest (the `drawing' is the program implementation), and because categorical diagrams are involved.

Patrick: Not "fixed" system so much as "complex system"

1. Complexity comes with the territory. Anyone who is afraid of complexity will never make a good programmer.

2. The way I think about it, types do not add complexity to a program; they rather make existing complexity explicit, and therefore easier to reason about. A type for a value captures and expresses some collection of facts about that value.

3. (Proviso: I consider the semantics of a typed program and the untyped version of that program obtained by type erasure to be distinct, so by `adding types' I do not simply mean `annotating programs with types'. Indeed, I have in mind mainly languages for which type inference is decidable. Basically I think that if your program is truly written in a modular way, then static typing does not require any casts or coercions that would not be required in an untyped language, and that conversely a `good' static type system prevents writing unmodular programs.)

4. Type systems do add complexity to a programming language, inasmuch as they constitute a language-within-a-language. But, if you are willing to learn multiple programming languages in the first place, this should not be a major obstacle.

Patrick: I don't need to prove the absence of all bugs very often.

Is this comment directed at the ST vs. DT discussion?

First, static typing will not prove the absence of all bugs.

Second, as I have repeatedly stated, static typing does not conflict with, but rather facilitates both testing and formal verification.

Third, what do you mean by `need'? You mean in order to get paid? How about a higher standard, like craftsmanship?

Demonstrating rather than proving the absence of the most likely, most critical bugs, has been sufficient.

Let's call a spade a spade. What you mean is:

Suggesting rather than proving the absence of the most likely, most critical bugs, has been sufficient.

Manuel: I would be interested to know if expert users of languages with complex/expressive type systems are never hindered by the systems.

I used to be; now it never happens, and the reason is that I understand now that I can always fall back to a less precise static typing; at worst I can fall back to dynamic typing using the embedding I once described here (and Bryn mentioned above). There may be casts/coercions involved, but as I suggested above they would be necessary in an untyped language anyway if I want to preserve the same level of modularity. I still get frustrated that static type systems aren't powerful enough in some way or another, that is, they could be improved; but there is never a case where I want to abandon static typing altogether. Unlike Ehud, I feel that, all other things being equal (for example, existence of higher-order functions, first-class continuations, etc.), even a very simple, unexpressive static typing discipline is better than none at all. It cannot be otherwise, because less is not more.

Let me see if I can give you an example of this `fallback' technique in a future post and why I feel coercions are not a nuisance.

By the way, Joe Armstrong successfully defended his thesis today, to a rather crowded lecture room. He even gave a first-hand demonstration of fault-tollerance by failing-over to OHT slides after his laptop crashed :-)

How about "unecessary complexity"?

The way I think about it, types do not add complexity to a program; they rather make existing complexity explicit, and therefore easier to reason about. A type for a value captures and expresses some collection of facts about that value.

I'm not going to go through the message point by point. This quote captures it: some people like static type checking. I am not there yet, but will not rule out future languages and type systems.

I have been able to reason equally well so far using languages that do all checking dynamically.

Now... can *no* one defend the presence of generic type checking and dynamic properties being in the same programming language?

The way I see it, it's untypedness that adds unnecessary complexity, because it doesn't even try to separate concerns of specification from concerns of implementation, and everything is tangled together in one universal datatype.

I have been able to reason equally well so far using languages that do all checking dynamically.

I think you see the glass half-full, whereas I see it half-empty.

Sure. I am happy with what's in my glass. When a new flavor of static checking comes along, I will be happy to do a taste test.