Guy Steele loves tail calls

My recent essay seems to be causing a big stir. I am pleased because I love it when my work has impact. The only funny thing about it is that I've known all this stuff for 20 years. I guess I just haven't communicated it clearly enough. And the essay is not an easy read, even still. Some people have suggested I need to write a book. We'll see.

Guy Steele pointed out that a pure OO approach to data only works if your language has tail call optimization. This is related to a comment I made in the essay about how objects use recursion everywhere (at both the type and value level).

samskivert gave a very condensed summary and some nice comments.

Andrew Black at Portland State (previously at OGI) said he used my slides in his class. One student found a bug in the essay: I say that ADTs are not possible without a static type system, but I also say that Smalltalk has some primitive ADTs for numbers. I should have said that without a static type system you cannot have the kind of user-defined ADTs that you find in CLU, ML or Ada. There are two ways to get ADTs in a dynamic language: one is with some kind of dynamic sealing (or encryption) and the other is to build them into the language runtime. The basic ADTs using in Smalltalk are built into the runtime.

And Jonathan Aldrich at CMU listed the essay as one of his select "classic papers" on object-oriented programming, saying "This is a (very!) recent paper, not a traditional classic, but it is the best summary I know of what makes objects unique."


John "Z-Bo" Zabroski said...

I don't like Sam's summary of your paper, and it does more harm than good. His final remarks are factually incorrect or a very troubled interpretation of an ADT:

"I am now convinced that one of the first things that should be done in CS education (maybe not in 101) is to implement an object system in an ADT-based language (like C)" ~ Sam

I am not sure what Sam means here, but whatever it is, it is clearly wrong. C hides nothing from everything, and does not have any support for ADTs. To call it ADT-based indicates that Sam should re-read your paper.

It is easy to get excited about people discussing your paper - but don't let that get in the way of your role as a mentor, facilitator and advocate of proper application of theory.

As an aside, I think it is unfortunate Reynolds' paper is not available online. Although written 35 years ago, it is a model of clarity in programming language theory.

William Cook said...

I don't think you need to be so negative, John. What I think Sam means is that you can learn a lot by implementing objects in a language that does not have native objects. I have assigned this problem to my students before. In the paper I mention the common practice of defining ADTs in C using header files -- but I agree that I would not say this makes C be "ADT-based".

John "Z-Bo" Zabroski said...

Sometimes we must tell truths that hurt. Sam is a smart guy; I've read his blog on several occasions. My objection mainly lies in that I believe this is how myths get started, even moreso today now that the Internet has reduced our attention span to the least amount of information necessary to tweet.

If you think I am not being fair, however, then I've erred and am sorry to Sam and you.

Fork of discussion:
Pedagogically, I think you learn a lot by simply understanding you must consider where to place your representations, and how that will effect every decision thereafter. Alan Kay has a really great OOPSLA speech called The Computer Revolution Hasn't Happened Yet where he discussed the design of a browser, critiquing how Berners-Lee's architected a (Web) Browser. He was overtly hinting that the Smalltalk (Object) Browser is infinitely more scalable in its design. I therefore think I would probably ask students questions like, "Is the View Source feature in your Browser Object-Oriented? Why?" If they don't immediately all get it, I would then ask them what happens when the representation of that source changes. Moreover, why does the Web Browser choose how to display the source? How can the Web Browser know the display instruction algorithm without violating the autognositic principle?* This is actually much cleaner way to understand how theory relates to implementation. You don't need to implement a language to get there, which, quite frankly is a lot of effort and many colleges I surveyed my senior year in college actually avoid doing. Small colleges pass up teaching compiler design and language design because (a) no in-house expert (b) it is a huge project

Tough design questions simply don't get asked much today, trade-offs are not understand, even by computer scientists (as your paper argues) and for this reason architecture is absent throughout most curricula (you cannot possibly consider informatics as involving design unless you understand complementary design approaches). Students build doghouses, because we have them on such an intellectual leash. We also do not appear to understand what it says about ourselves when we hold the leash.

William Cook said...

John, I haven't talked to Sam so I don't know what he really meant. It seems open to interpretation.

As for your fork, this is a big topic. On the one hand, I completely agree with you that design is not taught very much and there is little awareness of architectural issues. Part of the problem is that design is not a science, so it must be taught by an experimentation and critique, not by book learning. Professor know how to design scientific experiments and write papers, but many don't have a lot of experience designing and building large systems that involve many programmers and evolve over time. Some do, but not most. This makes teaching software design difficult.

You touch on some deeper issues about whether the browser is object-oriented and how it should be designed. We would probably have to discuss this in person, but my sense is that you are falling prey to the "objects are good" myth: that object-oriented programs are always good and a good program must be object-oriented. You are right that its not exactly object-oriented. But I think that in this case objects would be bad. I would say that the browser is *model-based* and that this is the right approach for this problem. However, this is a big question that will not be resolved in a few blog posts.