Lambda the Ultimate

There are just two different worlds, and I don’t think it’s even that helpful for people from one world to complain about the other world—like people from a literary culture complaining about the majority of the world that doesn’t read for ideas. It’s futile."

If Kay is just saying that we shouldn't "complain" but rather communicate more constructively "between worlds", that's fine, but if he's really saying "never the twain shall meet", I think that's defeatist and wrong. In my experience, there are plenty of people on the "pop" side of programming who are — or would be — interested in academic and formal ideas, under the right conditions. The right conditions include relevance and practicality of the ideas, and accessibility of information about them. Unfortunately, the conditions aren't often right, but in many cases that's fixable, and I think is actually being fixed.

The problem I think we face is a classic Sapir-Whorf one — lacking an extensive formal background, most programmers are constrained in their thinking by what the programming languages they're familiar with allow them to do. Attitudes to recursion are a great example of this: people think recursion is of limited use because in mainstream languages, recursion is of limited use. Similarly, most programmers are barely aware of models of control flow other than call/return; so continuations seem difficult from this perspective because they violate the mainstream worldview. Static typing in languages like C++ and Java is a semi-broken PITA; it's difficult to imagine what a good inferencing type system can be like if you haven't written real code in one.

"Complaining" at programmers that they should learn about and use many of these ideas is futile because it usually fails all of the tests mentioned above: it's impractical, irrelevant, and as a result, inaccessible. Complaining that programmers should switch to "better" languages is similarly impractical — it just isn't something most programmers are in a position to do.

Improvements to mainstream languages will be one of the biggest single sources of change in this area, because they will empower many ordinary programmers. It won't be the only cause of change, but — short of the kind of breakthrough academic language that Links wants to be — it's a prerequisite for such change. We are seeing mainstream languages improve, although like most developments in languages, it's painfully slow.

Something that's also missing is a good pop literature about these ideas — but again, this is hardly likely to arise in the absence of ways to exploit the ideas within the mainstream languages.

if what i do everyday is pop culture, then you people must live in ivory towers...

You seem to come here from Reddit?

why does the SICP account works as well as it does, given the unavoidable loophole?

SICP focuses on an abstract machine. It emphasizes elegance and clarity so that you understand the basic nature of the computations.

For the JVM, the primary driver was people whining that Java was too slow compared to C/C++. As a result, VM implementers do the little dance that someone else was doing for Python in another thread.

That way lies corruption. ;-)

Not what I'm after, but it took me a while to figure out why not.

Why should the closed-room-spec be any less elegant or clear than the metacircular spec? The CRS can leverage all the definitional subtlety that the MCS can. Somehow, MCSs are naturally more abstract anf flexible than CRSs, but why?

I've got the idea that somehow CRSs are a fundamentally operational way of looking at the problem, while the MCS is algebraic, in the Tarskian sense, and somehow this is the key. But why shouldn't the CRS be algebraic, too?

Why should the closed-room-spec be any less elegant or clear than the metacircular spec? The CRS can leverage all the definitional subtlety that the MCS can. Somehow, MCSs are naturally more abstract anf flexible than CRSs, but why?

Because they can be tested.

I don't think that's it. The CRS approach fits well with test suites. Test suites can have holes, but as Thompson showed, so can MCSs, in fact they can have just the same holes.

Without fear of exposing my ignorance in public, to what piece of work by Ken Thompson are you referring to, regarding metacircular interpreters ?

I didn't write the original comment, but doubtless the writer was referring to Ken Thompson's famous Turing Award lecture Reflections on Trusting Trust. That lecture didn't deal directly with metacircular interpreters (instead it dealt with compilers used to compile themselves as part of a bootstrap). Ken demonstrated that it might be possible to distribute an operating system (kernel, tools, etc.) in source code form--and embed a Trojan in the (binary version of) bootstrap compiler, such that:

1) If the compiler notices it is compiling itself, the trojan is propogated.
2) If the compiler notices it is compiling the "login" utility, it inserts a Trojan in binary that provides a backdoor
3) The Trojan is only in the binary--there is no trace of it in the source code for either the compiler or the login utility.

Thompson actually compromised a system in such manner as proof of concept.

While it dealt with C compilers; the same lesson applies to metacircular interpreters. It is theoretically possible to write a MCI that includes some nefarious behavior, and replicates that behavior when it notices it is executing a copy of itself--without the behavior being present in the source for the MCI.

But remember that the loop can be broken. In the Thompson example, once someone writes their own C compiler from scratch, they can compile it with the infected compiler and get an uninfected compiler (unless the new source code is similar enough to the old source code that the infected compiler can "patch" it to contain the trojan.)

In the case of the MCI, say the Smalltalk VM, once someone writes their own Smalltalk implementation, in Smalltalk or otherwise, they're free. (Unless, of course, they happen to submit a test program to both the infected implementation and their own that exposes the nefarious behavior.)

OTOH, I look at MCS as a kind of endomorphism, and nobody said each of them has a single fixed point... ;-)

Now just to mention a couple of things about Java: it really doesn’t have a full meta-system. It has always had the problem—for a variety of reasons—of having two regimes, not one regime.

Somehow the formal parts of The Anatomy of Lisp and The Implementation of Functional Programming Languages had the same good feeling too.

I also share Alan Kay's apparent bias towards having one implementation be the language. The separation of language from implementation doesn't seem to pull its weight to me.

(Not that I would know..)

I also share Alan Kay's apparent bias towards having one implementation be the language. The separation of language from implementation doesn't seem to pull its weight to me.

I disagree strongly. Languages defined by their only implementation tend to have lots of implicit rules, such that it's hard to tell whether they are just an artifact of that implementation or they are supposed to stay the same so programs may rely on them.

For example the order of evaluation of function arguments. Range of integers. Range and preciusion of floating point numbers. Which errors are signalled on bad or unusual arguments of certain functions. Hash values of constants. Introspection capabilities. Linking with C. The behavior and constraints of finalizers. Which data structures are safe to be used concurrently. Whether the absolute time is UTC or TAI or unspecified. Etc...

although i am not a language implementer, i've seen people trying to make e.g. jruby or jython or whatever and it always seemed like it would have been a lot better/easier if there were actual specs first. of course, maybe that's not very 'agile' thinking.

it seems to me that there is no way to approach the issue that won't have draw-backs, so it comes down to what you personally value. do you value quick-time-to-market vs. do you value correctness via proofs vs. do you value the flexibility of metaness?

To use your own example, the order of evaluation of function arguments is unspecified in a lot of languages. This means that you can very trivially write code the meaning of which the language specs don't cover. That's really bad.

So there are no "artifacts of the implementation" - each detail is a part of the language spec. Alan sees this as an advantage - that each Squeak image must run bit-identically on any machine it is run on. Another advantage of this, I imagine, is that everything in the system is always serialized in a form that can be immediately sent to another Squeak system...

It is instructive to remember...
Red-herring: it doesn't matter what was true in Elizabethan times; the unfamiliarity of the language, values, allusions is now a fundamental barrier.

it doesn't matter what was true in Elizabethan times; the unfamiliarity of the language, values, allusions is now a fundamental barrier.

But it doesn't change the intent of the plays. They have become "high culture" by changes in circumstance rather than by anything that Shakespeare intended when he wrote them.

Kay was implying that "real" culture (and "real" CS, SE and PLT) is better in intended quality, but the plebs can't understand it, so don't bother trying.

He's entitled to his opinion, but I think in PL design this is a defeatist attitude.

Pop culture can promote the good things as easily as the bad (perhaps more easily); it is just harder work to have good in the first place.

"the plebs can't understand it, so don't bother trying

That's a misrepresentation:

"computing spread out much, much faster than educating unsophisticated people can happen"

"computing spread out much, much faster than educating unsophisticated people can happen"

Sounds to me like a "syntactic sugar" version of what I said.

Except the actual version was much less disparaging than you made it out to sound.

This is a good overview.

The way I see it, Alan Kay wants everything late bound - so that you can change languages mid-program, for example.

Sounds to me like - computing spread out so fast there was no way that people with zero experience were going to become skilled quickly enough.

OK. Let me grant you for a moment that there is not the least trace of patronizing or condescending tone in Kay's statement (if that is your objection).

It is the practical advice he gives that is the real point of contention:

I don’t think it’s even that helpful for people from one world to complain about the other world—like people from a literary culture complaining about the majority of the world that doesn’t read for ideas. It’s futile.

Now I agree that complaining is futile, but just accepting that "never the twain shall meet" is equally futile.

I much prefer the approach being taken by Wadler and friends with Links: identify problems of wide interest and show how "advanced" PLT techniques can help solve them. Try to work with a consortium to get a language with these features accepted for some widespread activity.

Even if they fail, the failures will provide useful experience and info to later attempts.

"not the least trace of patronizing or condescending tone"

In marked contrast to: "the plebs can't understand it, so don't bother trying".

"Now I agree that complaining is futile, but just accepting that "never the twain shall meet" is equally futile."

I must have missed the bit where he said "never the twain shall meet".

"not the least trace of patronizing or condescending tone"
In marked contrast to: "the plebs can't understand it, so don't bother trying".

There is no contrast implied. The above is my paraphrase of my interpretation of what he said. My paraphrase makes plain what I believed to be a euphemistically-masked tone of condescension.

My previous post was an offer to retract this interpretation for the sake of discussing what I personally believe to be the more interesting issue of its implications for PLs.

I must have missed the bit where he said "never the twain shall meet".

If you have a different interpretation of what he was saying, by all means provide us your precis and elaboration of it. Hearing different takes on ideas is the main reason I go to the effort of expressing mine.

The funny thing is that I think Alan Kay is for the plebs: he wants to make computing accessible to people who don't have the time or motivation to become programming specialists (or to people who haven't yet taken that time - like children). So what he is arguing for is an approach that offers as much as it can to people where they are, rather than futilely (as he sees it) cajoling them to clamber en masse over to the specialists' side of the fence.

The argument is not about whether people should be educated (or be empowered to educate themselves), but about how that education is to be facilitated. So Kay is very interested in questions about what children can learn to do with computers, what kinds of symbolisation of programming activities give the reasoning abilities they already have the most traction, and so forth.

I don't think it would be false to say that when it comes to learning programming the majority of adults are if anything at a slight disadvantage compared to children (that begins to be untrue when you narrow it down to adults educated beyond a certain level; but the majority of adults in the UK, say, are not so educated) - so Kay's approach has at least a plausible rationale.

The funny thing is that I think Alan Kay is for "the plebs":he wants to make computing accessible to people who don't have the time or motivation to become programming specialists

I think this skips over a third group though: programming specialists who, in Kay's apparent assessment, aren't doing "real" CS/SE or using "good" PLs.

It does kind of give one the feeling that he has given up hope on that lot, choosing instead to indoctrinate the young. ;-)

Though I'm not sure that teaching kids Squeak will prevent them from becoming C++ programmers when the are older. ;-)

This brings us back to this section from the quotation Isaac selected:

So I think the lack of a real computer science today, and the lack of real software engineering today, is partly due to this pop culture. ...

Unless Kay makes explicit what "real" CS/SE would look like, and what particular features of the "pop culture" of computing prevent this from coming about, his whole position sounds suspiciously like a "Just So" story.

The alternative approach that I'm recommending is the Links one: give up making the high/low culture distinction, try to find areas of common interest and work to solve the problems there.

I think Kay's characterisation of mainstream programming culture as a kind of pop culture is kind of cute. "Real" computer science can seem somewhat marginal in a world dominated by...well, the sorts of things that tend to dominate, and that do so by virtue of "network effects" that are indeed rather like those exploited by the opinion formers of youth culture.

I don't think Kay's saying that things like Haskell (to pick on a commonly picked-on example) don't exist, or aren't "real" CS/SE; just that from the point of view of the mainstream, they might as well not exist, and this hinders the maturation of programming, considered as the activity of a majority of programmers, into a truly principled form of engineering.

Maybe Links will help to change that. It surely can't be that difficult to improve on PHP.

While it is common to point out software engineering's numerous failings as an "engineering" discipline--compared to things like civil engineering, it ought to be pointed out that our hardware friends (in particular guys who do VLSI, PLD, and/or PCB design) are closer to us in nature than they are to the classical engineering disciplines. Most EEs are not licensed; and licensure as an EE is not required to become a public engineer-for-hire (only we call 'em "contractors"). PLD designers in particular--like programmers--have an incredibly inexpensive design-to-implementation cycle, so build-it-and-see-if-it-works-if-not-try-it-again is a reasonable way to do business, as opposed to formal proof/simluation of a design in advance of construction.

(Kay's comment regarding "late binding in all respects" seems to suggest, at least, that a real engineering discipline would allow for complete formal verification of code before it is run; barring that the pendulum should swing the other away and allow for the greatest mutability of code after deployment).

One difficulty that we have--which leads us (and our EE brethren as well) to consider ourselves as something other than an engineering discipline--is the inherent inprediceability of schedules and the like. Especially for large products. In a sense, I feel this is a bit overblown, as many more SW projects involve "invention" than do civil engineering projects.

On the science side--quite a bit of what we do is undoubtedly science. Some of it is soft science, like anything having to do with usability or human factors--and as a result, many dispute that these things are science at all. Which, I believe, is unfortunate.

What Kay expects, I have no idea. I'm not sure if a concrete, testable definition of "engineering" or "science" exists in his mind, or if it's a moving target to be met when he says so.

"Unless Kay makes explicit what 'real' CS/SE would look like, and what particular features of the 'pop culture' of computing prevent this from coming about, his whole position sounds suspiciously like a 'Just So' story."

Well, this was already a long interview. If you're curious, as I am, why not ask him?



Still, what he said is in line with my observations. Science thrives on disobedience and questioning. When something is criticized for not being a science, it usually means it's infested with ideology and dishonesty.



For example, when applied to economics, it means economists are usually dissuaded from pursuing certain questions because "it's not going to be useful." Specifically, politicians and business leaders desire certain results.



As Dick Feynman explained, "It is very dangerous to have such a policy in teaching--to teach students only how to get certain results, rather than how to do an experiment with scientific integrity. So I have just one wish for you--the good luck to be somewhere where you are free to maintain the kind of integrity I have described, and where you do not feel forced by a need to maintain your position in the organization, or financial support, or so on, to lose your integrity. May you have that freedom."



He explained physicists had to learn honesty the hard way. And even now there are many dishonest physicists, who are incentivized to come up with shoddy results.



In CS, I've observed that debating is a far more useful skill than truth-seeking. There are camps and schools of thought, as in cheesy martial-arts movies where people fight over the honor of some silly tool or worldview. And you see high-profile people graduate from famous colleges spewing verifiable lies to trash something. (Such as, "Lisp only has lists and functional programming.")



The emphasis of high-technology is historically to deskill rather than empower. Forces of Production was a technical view of this.



Also, Noam Chomsky at MIT observed:



"So for example, in the late 1960s it began to appear that the universities were not adequately peforming that service -- students were asking questions, they were thinking independently, they were rejecting a lot of the Establishment value-system, challenging all sorts of things -- and the corporations began to react to that, they began to react in a number of ways. For one thing, they began to develop alternative programs, like IBM began to set up kind of a vocational training program to produce engineers on their own: if MIT wasn't going to do it for them the way they wanted, they'd do it for themselves -- and that would have meant they'd stop funding MIT. Well, of course things never really got out of hand in the Sixties, so the moves in that direction were very limited. But those are the kinds of pressures there are."



Now, since I expect there to be some debate ;), let's just take something floating around the press recently:



"'Political science, not biology, has become the dominant discipline in today's Fish & Wildlife Service,' concluded PEER Program Director Rebecca Roose, who worked with current and former USFWS employees on survey design. 'Like the trainer who hobbles a horse and then laments that it does not run fast, the politicians who complain about the lack of 'sound science' in the administration of the Endangered Species Act are often the very ones who intervene behind closed doors to manipulate scientific findings when they impede development projects.'"

If you're curious, as I am, why not ask him?

I'm less concerned with with his opinion than with what conclusions LtUers draw from this piece.

For all I know the whole interview is horribly misquoted, or just some pet theory he was discussing with the interviewer. He's entitled to those.

But it was posted here, some people said they thought it was interesting or meaningful, but not how they thought so. That's what I'm interested in.

When something is criticized for not being a science, it usually means it's infested with ideology and dishonesty.

There are no sciences then, except perhaps math and logic, since results there can be verified from scratch by others.

As Feynman says, and as anyone who has worked in a scientific or academic environment knows, there is always a lot of economic and peer pressure on scientific results, in varying ways and amounts depending on the nature of the field.

This doesn't mean that good science can't be done, just that we must be skeptical about any results, asking more questions (who funded it, have other completely unrelated people verified it, etc.)

Even though Kay isn't promoting his opinion as a result, it can be useful to discuss it as one to see what might be learned.

There are camps and schools of thought, as in cheesy martial-arts movies where people fight over the honor of some silly tool or worldview.

This is human nature, and occurs to some degree in all fields, sometimes just less visibly to those of us outside the field.

To escape from this problem in our field of interest, I don't think it is useful to read a piece on LtU and nod piously if it agrees with your worldview and skip over it if it doesn't.

Questioning premises, especially those of "big names", is exactly the kind of thing that can encourage the intellectual honesty we want for our field.

Briefly, Kay has commented elsewhere—I don't recall where offhand, but I think it was at his O'Reilly conference presentation—and he fleshed out his comments a bit about there not being a Moore's Law of software, the lack of formalism in software development, and even went so far as to make his tack explicit: "We don't have a science of software engineering. Until we do, we should take advantage of late binding." My read of Kay is that he's excited about certain classes of statically type-inferred languages ("in Europe") but doesn't feel they go far enough yet, so prefers the style of a Lisp or a Smalltalk. What he doesn't seem to care for at all are the Cs, C++s, Javas, C#s, etc. of the world. Assuming that my interpretation is near to correct, Dr. Kay and I are in vehement agreement (which is why I worry that I may just be projecting!), differing only on where to focus our energies: Dr. Kay has focused his on the dynamic, late-bound end of the spectrum, and I have shifted from that to the let's-enrich-our-type-systems-and-inferrers end of the spectrum.

What I found most interesting in this interview weren't his thoughts on software, but rather his thoughts on hardware architecture and that all current popular hardware architectures are wildly suboptimal with respect to running, presumably, very dynamic, late-bound runtimes. I'd love to see someone design a new chip along the lines that he says the old... I forget what... Borroughs machine was?

We don't have a science of software engineering. Until we do, we should take advantage of late binding.

Is is just me, or does that sound a bit like "Until Mom gets home, we should take advantage and raid the cookie jar." ;-)

But seriously, do you think this means : "Until we come up with a fool-proof way to rigorously make software, we should choose the least constrained approach"?

If so, it would seem to me that the opposite is true: the safest course is to solve specific problems with a limited system and only add generality as the general patterns and requirements emerge.

all current popular hardware architectures are wildly suboptimal with respect to running, presumably, very dynamic, late-bound runtimes.

This brings to mind a comment in another thread, which I think implies that by definition separate compilation/late binding loses you the possible global optimizations that would have been available with a global compilation.

Another rule of thumb to consider is that there are often more efficient algorithms available for specific cases than for the equivalent general case. By definition, very dynamic systems need to always worry about the most general case.

This brings to mind a comment in another thread, which I think implies that by definition separate compilation/late binding loses you the possible global optimizations that would have been available with a global compilation.

Check out the techniques used to make Self run very fast. Self retains full dynamic, late-bound generality, while approaching the performance of optimised C for many of the studies they made.

The techniques generalise to other dynamic languages.

Can I just observe that Self rocks? The concrete visual development process, where objects evolve naturally and have a prototype, vs. class, relationship to each other, is very nice. Follow the tutorial to get a good flavor of it. This is a great example of what the promise of late-bound dynamic languages has always been, with Symbolics' Genera environment being the other excellent example.

Late Binding Makes Code Faster

Than what?

Self retains full dynamic, late-bound generality, while approaching the performance of optimised C for many of the studies they made

If by "appoaching" you mean twice to three times slower (based on the authors' results), sure.

To be clear, I'm not saying you couldn't get ACCEPTABLE performance with generality, just LESS performance than is possible with a more specific solution.

I agree that a specific solution can of course always take advantage of specialization to omit certain steps a general solution has to plod through. (And of course one of the ways Self runs fast for a dynamic language is that it specializes otherwise-general code and runs it optimistically.)

However, you also said

[...] by definition separate compilation/late binding loses you the possible global optimizations that would have been available with a global compilation.

and my post was in response to this specific point. The work on Self demonstrates clearly that global optimisations in a dynamic, late-bound framework are not only possible, they're relatively simple, and very, very effective. The 2-3x slowdown wrt C in Self isn't necessarily the fault of the dynamism or the late-binding - the authors in fact blame the register allocator for a lot of the difference!

And faster than what? Well, a lot of other languages - perhaps not optimized C, but certainly faster than a lot of C++, a lot of Java, a lot of C#, a lot of Smalltalk, a lot of Scheme, a lot of Lisp, etc etc. The simplicity and universality of the optimisations that are available to Self-like systems really pack a punch. Why muck about with a language that's neither Arthur nor Martha? :-)

But seriously, do you think this means : "Until we come up with a fool-proof way to rigorously make software, we should choose the least constrained approach"?

It strikes me that the science of software engineering encompasses a very large collection of processes and my gut feeling is that there doesn't exist a fool-proof way to rigorously make software beyond relatively course guidelines. It's much like doing a mathematical proof: looking at the finished product it seems like it can mechanized, but there's much more creativity going on than meets the eye and developing a fool-proof method for such an endeavour doesn't seem feasible.

I'm believing more and more that the dynamic languages should focus on expressing abstractions in a clean way such that they can be specialized to other languages, most likely with stronger type-checking. Informally, you use dynamic languages to figure out what types you actually need, then translate it to a language where you can express the types.

I'm not professing that this is a new idea, but I can't say I get the impression that it's put into practice on a grand scale. My hypothesis is that people think this way, but don't seem to practice it, maybe because tools don't support it.

It strikes me that the science of software engineering encompasses a very large collection of processes and my gut feeling is that there doesn't exist a fool-proof way to rigorously make software beyond relatively course guidelines.

This is a core part of my skepticism about Kay's position (as I interpret it): I don't believe we'll never get certainty in SE unless we run out of new, complex and interesting domain problems.

If he likes working with late binding, good for him. To suggest that he's FORCED to do so by the shortcomings of other options sounds a bit disingenuous.

As I and others have written about extensively here, this ignores a great deal of actual, working progress in languages with rich type systems and related tools for proving that a system does what it's supposed to, e.g. Alloy. It's perfectly fine to say that you don't care for the kinds of guarantees that the type systems of a SML or O'Caml or Haskell or Clean or Acute or Flow Caml or TyPiCal... give you, or not to apply a tool like Alloy to your system, but that's a very different claim than that such guarantees don't exist. Yes, I undertand that there are limits to these guarantees, but the point is that they're vastly beyond the guarantees afforded by the Cs, C++s, Javas, VBs, Lisps, Smalltalks... of the world.

Marc: If he likes working with late binding, good for him. To suggest that he's FORCED to do so by the shortcomings of other options sounds a bit disingenuous.

I wouldn't say "disingenuous," but I would say "idealistic," if he's waiting for languages like, e.g. Haskell as implemented in GHC 6.4 to become mainstream. But my read of his comments linked to here makes him sound much more realistic, which is to say that he has a pretty good handle on how long it takes software engineering concepts to become mainstream once a particular implementation has become "accepted," in some hard-to-define sense. For example, how long did it take from Java's introduction for the idea that garbage collection might not be plain evil to become a mainstream notion? So even if GHC 6.4 sprung a community of 50,000 developers out of whole cloth tomorrow, it might still be another decade or more before GADTs became a mainstream notion, and that might prompt one to say, well, the heck with it; given that the industry is so incredibly far away from even seeing the value of such a thing, let alone routinely employing it, let me use tools that do an excellent job of evolving the system even after it's been deployed: the Lisps and Smalltalks of the world. He's explicitly traded off one set of guarantees that can be made at compile time or before, but he doesn't feel are expressive enough or employed widely enough, against a very different set of guarantees: that having built a system hasn't overcommitted you to an implementation of any given component of that system, even at runtime.

It would be interesting to contemplate how Sewell and company's work on Acute, particularly its dynamic rebinding features, might strike a very nice middle ground between the guarantees of a rich, inferred, static type system and the flexibility and lack of overcommitment of late-bound dynamic types.

How does the Alloy Analyzer differ from theorem provers?

The Alloy Analyzer's analysis is fully automatic, and when an assertion is found to be false, the Alloy Analyzer generates a counterexample. It's a "refuter" rather than a "prover". When a theorem prover fails to prove a theorem, it can be hard to tell what's gone wrong: whether the theorem is invalid, or whether the proof strategy failed. If the Alloy Analyzer finds no counterexample, the assertion may still be invalid. But by picking a large enough scope, you can usually make this very unlikely.

As I and others have written about extensively here, this ignores a great deal of actual, working progress in languages with rich type systems

You seem to have a different notion of certainty than I do. Type checking (which I favour) and related techniques can increase one's confidence in one's code, certainly.

However I don't believe that these techniques can do much to improve certainty in software engineering overall.

(Note, my working definition of software engineering is a body of practices and techniques by which practical problems are indentified and solved through the construction of software.)

Good or bad code can be a contributing factor to the sucess or failure of SE projects, but I don't think it by itself is even in the top three challenges for such projects.

My understanding of Kay's claim was that late-binding gives you so much flexibility of design, that it helps projects to succeed, in the abscence of a foolproof type systems.

While I do believe good type systems can help make better software, I don't believe that they will ever be good enough to make the kind of guarantees that are mormally expected of SE.

The only problem I have with this is that most people simply don't know what modern type systems are doing. Consider, e.g. how many people will tell you that type-safe marshaling of values over a network is impossible, or that a type system can't prevent you from writing concurrent code that deadlocks, or that a type system can't enforce that security-sensitive data never goes out over a certain channel. But all three of these claims are false, cf. Acute, TyPiCal, and Flow Caml, respectively. So while I agree with your larger point, if for no other reason than that proving an arbitrary system X correct is equivalent to the halting problem, I continue to maintain that there is a sizable knowledge gap between what the average programmer believes is possible for a programming language to guarantee and what actually is possible for a programming language to guarantee, and the possible guarantees are vastly closer to "good software engineering" than what you get out of an average programmer or even, frankly, a quite gifted programmer with any consistency.

Again, that's not to say that no one should program in Lisp or Smalltalk! On the contrary, I have a great deal of sympathy for Dr. Kay's point of view: until there is such a thing as software engineering in a form that's routinely, reflexively used by working programmers—I'm thinking of Pierce's observation that "type systems are the one lightweight formal method that are guaranteed to be used" and Melham's "Formal methods will only make progress when they can be used by people who don't understand them"—let's try to use tools that make evolving the system as painless as humanly possible.

...most people simply don't know what modern type systems are doing. Consider, e.g. how many people will tell you that type-safe marshaling of values over a network is impossible...

In all fairness, there are two sides to the story. Static typing can do much more for us in the single-system setting than it can in the distributed setting -- it can remove the overhead of type checks and casts and verify that we have not, for example, tried to feed Strings to a printf specification with %d in it.

In the distributed setting, we have to settle for less. How much less is generally exaggerated; but we can never have the confidence that our network facing functions are fed the correct data -- some checks and error handling must remain. In short, some of the many miracles of static typing don't cross the wire.

The approach taken by Acute (I am still reading the paper) to system-wide type-safety is brutish if obviously correct -- they reserve the right to ship the entire module, if necessary!

We generate globally-meaningful runtime type names for abstract types in three ways: by hashing module definitions, taking their dependencies into account; or freshly at compile-time; or freshly at run-time. The first two enable different builds or different programs to share abstract type names, by sharing their module source code or object code respectively; the last is needed for modules with effect-full initialisation.

If type-checking were structural instead of name-based, I'm not sure if it would help or hurt. You'd get a few "names" that would never change -- int32, byte, count_prefixed_list t -- from which to build up type definitions especially for the network; it might actually be easier to make a system that was both type-safe (in the sense that performing the checks is well understood) and cross language in this way.

...often have nothing to do with the type system.

Type systems, and other formal methods, can be used to show program correctness in two ways.

One way is to demonstrate that a program is internally consistent; that nowhere are we trying (for example) to stuff an int where a string is expected, or to reference an object through a pointer that is invalid. Much progress has been made here (with type systems leading the way, as well as external features like garbage collectors); and this generally can be automated (a la type inference) and requires no additional work from the programmer in the ideal case.

But that's half the battle. The other half of the battle is making sure that a program is correct, in other words, conforms to some set of externally-imposed requirements. We're a lot further off on this part--partly because gathering and specifying requirements that are precise is a hard problem (and a sociological problem as much as a technical problem), not to mention the technical problems of specifying such requirements in a formal manner and verifying that a program conforms. Design by contract and unit tests help here, of course, as can type systems. But even the parts of this that are subject to formal manipulation can be problematic if programmers don't use them--getting programmers to regularly use assertions or write unit tests (or even comments, which are of no help to a formal system!) is often like pulling teeth. Programming folklore is full of excuses and rumors as to why this sort of stuff is a big waste of time.

Interestingly enough, the resistance among many (in both static and dynamic typing camps) to explicit type annotations actually can hurt here, as an explicit type annotation is a great way of formally specifying a requirement (and which, in C++ and Java, cannot be ignored by unmotivated programmers). Of course, type annotations in programs that don't correspond to external requirements are another matter; and type inference is well-used to eliminate those. To put it in the terminology of Brooks, type annotations are desirable if they specify the essence of the program; undesirable when the specify the accidents (or incidents). Unfortunately, many (if not most) type declarations in languages like C++ or Java are of the latter case.

At any rate, the weak link in the chain remains requirements-gathering and specification, not the parts which can be handled by symbolic manipulation of programs. If this is what Kay means, then I'm sympathetic to his cause; though I think that his advice to offer "late binding in all respects" needs to be re-evaluated in the face of more modern meta-programming and aspect-oriented programming techniques. (Not discarded, just re-evaluated).

I think that his advice to offer "late binding in all respects" needs to be re-evaluated in the face of more modern meta-programming and aspect-oriented programming techniques

I'm still waiting for someone to explain to me what critical problem of software development AOP solves.

In general, what problems of software development do you think metaprogramming solves?

Marc wrote:

In general, what problems of software development do you think metaprogramming solves?

A good question.

Many think that having a powerful macro system (or meta-object protocol, or other ways of doing meta-programming) is a good thing because it will facilitate the creation (by the local shop guru) of numerous domain-specific langauges, which will greatly increase the productivity of all the "grunts" out there.

It happens, but less often than one thinks. Writing a good DSL is a hard thing to do (it requires both domain expertese and PL design expertese), and most DSL's implemented as a macro package or metaclass generally aren't very good. (Plus they usually are little more than extensions to the underlying "host" language, which limits their use).

The best DSLs out there are things that are complete programs in their own right, rather than bolt-ons to some existing language. I'm talking about things like HTML, Tex, YACC, make, SPICE, and numerous others. A good domain-specific language is one which empowers domain experts who are not trained programmers to solve problems in the problem domain. While these things probably can be implemented as a macro package on top of an existing macro system (and they may have been retroactively implemented as such as proof-of-concept), all of were originally implemented standalone programs/libraries that don't use "meta" facilities as part of their implementation.

What then, does metaprogramming solve?

I do think that it is an effective "springboard" or prototyping tool to a full-fledged, standalone DSL like the above. It's effective for lightweight, shop-specific DSLs.

And, as alluded to in my prior post, metaprogramming provides "hooks" for the evolution and parameterization of software systems--which is one advantage Dr. Kay claims for late binding. Metaprogramming allows it to proceed in a more controlled fashion.

Metaprogramming is also useful as a polymorphic/generic programming technique, as the C++ template system has shown.

(Note to self. Use of three single-quotes doesn't get one boldface here on LTU; I've been spending too much time on Ward's wiki. :)

Interestingly enough, the resistance among many (in both static and dynamic typing camps) to explicit type annotations actually can hurt here, as an explicit type annotation is a great way of formally specifying a requirement (and which, in C++ and Java, cannot be ignored by unmotivated programmers). Of course, type annotations in programs that don't correspond to external requirements are another matter; and type inference is well-used to eliminate those. To put it in the terminology of Brooks, type annotations are desirable if they specify the essence of the program; undesirable when the specify the accidents (or incidents). Unfortunately, many (if not most) type declarations in languages like C++ or Java are of the latter case.

I'd have to say that it is fairly common Haskell practice to work in pretty much exactly this way.

Two deceptively simple but prevalent techniques in Haskell that underscore this are phantom types and wrapper types. Both of these techniques are based on making type information explicit; in fact, phantom types are pointless without explicit signatures somewhere. These and related techniques can be viewed as reifying specification information as types.

"To escape from this problem in our field of interest, I don't think it is useful to read a piece on LtU and nod piously if it agrees with your worldview and skip over it if it doesn't."

I'm optimistic about the thoughtfulness of many readers. I don't even really care about this issue, except it would likely be more intellectually interesting if thoughtful people were given more power to pursue attractive threads.



Anyway, trying to change the mainstream is an activist stance. Successful ways of doing this include meeting people and pursuing one's passions. Which hopefully the LtU readership is already doing.



Under today's common economic systems, there will always be a demand to deskill programmers, or any other worker, using tech. Like at McDonald's, where workers are given a heavily restricted set of tools which can't cut them (or anything else), so they can consistently add value to inventory and create "food." So there will always be a market to satisfy this demand which shouldn't be underestimated.

I admire the elegance of Joy.

Are there any other languages that have small self-definitions?

Derek Elkins wrote a lambda calculus interpreter that comes with the lambdabot IRC bot. In just a few definitions he implemented enough of Haskell on top of that interpreter to confuse long time Haskell users as to whether it was 'real Haskell' or not. I was surprised that Haskell is that close to lambda calculus.


--Shae Erisson - ScannedInAvian.com

John Tromp's Lambda Calculus and Combinatory Logic Playground discusses a 220 bit binary lambda calculus self-interpreter. The Playground also links to Chris Barker's minimalistic languages page.

Up till now, I've only known the definition of Kolmogorov Complexity, I've never considered how it might apply to programming language definitions.

Any thoughts on whether Kolmogorov complexity is important or applicable to programming language design?


--Shae Erisson - ScannedInAvian.com

Are there any other languages that have small self-definitions?

eval $string;

...This may be considered cheating (for some definitions of cheating) but I'm having a hard time justifying to myself why we shouldn't consider it just as nifty/useful/elegant as the other implementations. Any thoughts?

I'm having a hard time justifying to myself why we shouldn't consider it just as nifty/useful/elegant as the other implementations.

I think the problem with this is that it doesn't illuminate the primitive structure of the language.

Most metacircular interpreters show you a breakdown of the primitive elements from which the whole language can be constructed, and this is the essence of their "coolness".

"eval" simply begs the question (in the original, logical sense) and shunts all the detail to some hidden evaluator.

Might as well say "something magic happens here". ;-)

Maybe it is a matter of degree then? Is my problem merely my unfamiliarity with Joy, or is there a high degree of magic in the Joy interpreter above? I can't see what you would modify if you wanted to change the behavior of the if-then-else (ifte) combinator, or the definition operator (==) or pretty much anything else.

Maybe it is a matter of degree then?

I think this is so. A metacircular interpreter requires that you have an interpreter that executes the kernel language, so there is still some magic.

(Though you could say that the translation into the kernel language represents a normal form, and is a kind of semantics if you define it well.)

I think what impresses most people with such MIs is that, for a given language, that there IS a small, well-defined kernel language that generates the full complexity of the language.

After actually reading the article that the original poster linked to, I see that joy0 from above doesn't implement the full language, only enough to execute itself. A more featureful interpreter looks like...

HIDE
  cr1  ==  pop  [joy] cons;
  cr2  ==  pop [[joy] cons] app2;
  cr3  ==  pop [[joy] cons] app3;
  cr4  ==  pop [[joy] cons] app4
IN
  joy  ==
    [ [ [ joy		body	joy	]
	[ true				]
	[ 'A				]
	[ []				]
	[ ""				]
	[ {}				]
	[ 0				]
	[ dup		pop	dup	]
	[ swap		pop	swap	]
	[ pop		pop	pop	]
	[ +		pop	+	]
	[ -		pop	-	]
	[ and		pop	and	]
	[ cons		pop	cons	]
	[ i		pop	joy	]
	[ dip		cr1	dip	]
	[ step		cr1	step	]
	[ map		cr1	map	]
	[ filter	cr1	filter	]
	[ times		cr1	times	]
        [ app1          cr1     app1    ]
        [ app2          cr1     app2    ]
        [ app3          cr1     app3    ]
        [ app4          cr1     app4    ]
	[ ifte		cr3	ifte	]
	[ linrec	cr4	linrec	]
	[ binrec	cr4	binrec	]
	[	      dup put [] cons i ] ]
      opcase
      i ]
    step
END;

Two reasons, it's fun to think about, and silicon is not the best computational medium. I'm looking for different irreducible languages because I want to find something new and interesting. Maybe photorefractive crystals are a better processing medium than silicon? Maybe silicon can be faster if you change the implemented irreducible language? Who knows what nifty things could be hiding under the next combinator?

Fun and knowledge exploration is enough reason to bother.

--Shae Erisson - ScannedInAvian.com

Well, this is quite right, so I feel I misspoke: what I meant was that I would be rather surprised if anyone succeeded in coming up with "atoms of programming languages" that were more minimal in any meaningful (exploitable?) way than the SK Combinator Calculus. But part of my point also was that perhaps looking at programming at the "atomic" level isn't that helpful, given how extremely minimal that level is. Things like the SK Combinator Calculus, Lambda Calculus, and Universal Turing Machine are very important results, just as General Relativity and the Quantum Mechanics are very important results, but also like them, most people don't need to refer to them, but instead rely upon abstractions and/or approximations built atop them. This is why I think that Oz is brilliant, or Scheme is brilliant: both have a very small, simple set of primitives, which lends a great deal of consistency and orthogonality to the abstractions built atop them.

Having said that, I remain very curious about Dr. Kay's comments regarding the poor performance of modern hardware in support of late-bound languages, vs. the Burroughs 5000 architecture. Even if he's off by a couple of orders of magnitude, it would be worth revisiting those architectural differences at the hardware level, if the end result would be that Lisp and Smalltalk would be even more competitive with C and C++—and compilers like CMU CL/SBCL are already awfully good.

This reminds me of a language I've been working on called Magritte.

In Magritte, the only valid program is:

Ceci n'est pas un programme.

It has the very strong semantic guarantee that it will never terminate.

Reading his post made me wonder if Myers had been imbibing the liquid in my title, or if he is simply mis-remembering one of our threads.

I can't recall an "I hate OO" thread in a while. (Or maybe I've gotten so used to them I don't notice anymore. ;-) )

Also, I was unclear on his attitude towards C++: he clearly works with it, but he doesn't make an obvious defence of it either.

I heartily support his critique of ideology in PL design. Unfortunately, I believe his premise that ideological languages can never succeed is false.

For example, C++, IMO, has an ideology: compatibility with C is important and raw performance is the most important feature of a PL for practical programming.

He's often hinted he doesn't think the language is all that great. I guess his attitude isn't too far from mine: it's very far from a beautiful language, but there are good reasons the language is the way it is, and you shouldn't criticise the language if you don't know what those reasons are.

I posted a somewhat updated version at http://lists.canonical.org/pipermail/kragen-tol/2007-March/000850.html.