Lambda: The Ultimate Goto

Debunking the “Expensive Procedure Call” Myth; or, Procedure Call Implementations Considered Harmful; or, Lambda: The Ultimate GOTO. Guy Lewis Steele Jr. October 1977. MIT AI Memo 443.
PDF version hosted on this blog.

Essential reading for all computer scientists or those wishing to implement a language. I should’ve read this paper when it was half its age.

It’s 1977 and Steele is writing memos from an alternate reality. It’s a little hard to place oneself in this alternate universe: “Some programmers fear that their expressive power or style will be cramped if GOTO is taken away from them.” Steele does not think this is a good thing, hence the memo, it’s just a sign of how things are in that era. Was this really only 2**5 years ago?

His concerns about the subroutine’s perceived inefficiency are now laughable, and that’s no doubt partly due to Steele’s efforts in this memo. His other concern is the conflict between abstract programming concepts and concrete language constructs. And that concern is still valid.

Steele uses LISP (yes, in capitals!) for his examples with no introduction nor explanation. Cruel. But then, it is a Steele memo, and LISP has been around for 17 years already; it’s no new kid on the block (it has a whole 4 years over PL/I for example).

Part A shows how splitting up the traditional notion of what a procedure call might mean allows them to be implemented efficiently and also used for tail-calls. In other words you don’t need to do tail-calls as a special thing, organise your compiler properly and you’ll give the programmer a tool with which to express tail-calls. This is a good thing, and crops up later on.

He has an amusing rant about the syntax of procedure calls giving them a distinct flavour in most languages from built-in operators. Like the fact you can’t pass a Fortran statement function as an argument, or you have to use «CALL ... USING» in COBOL. This part still rings true. In Python we can’t pass «+» as a function (though we do have «operator.add»); «(2).__mul__» is not the same as «lambda x: 2*x».

In Part E (one of the best bits), Steele shows how Yourdon’s rat’s nest state machine can be transformed from the “traditional” implementation with an explicit state variable and a loop to a “procedural implementation”. Steele considers this “structured” (“structured” as in no GOTOs, a current buzzword of the time), and points out a further benefit: state transitions can pass each other information as parameters to a procedure, rather than using global (shared) variables. I would put it slightly differently: The liveness information the programmer is giving to the compiler is more honest.

This part, implementing a state machine using procedures, forms merely one component of a larger argument. That programming concepts and programming language constructs do not have a one-to-one correspondence. That is, though we have constructs like procedures for encapsulating modularity, and WHILE for iteration, we might use assignment to implement modularity (and yes, he has quite a good example of this), and procedures for iteration. And, he argues further, it is not up to the language implementor to guess what the programmer might do with each language construct. Implementors should give programmers all the reasonable tools they can, “otherwise, programmers will merely misuse the constructs they are given”.

This point is expanded in a note (“Various Optimizations”); there should not be just one way to compile a particular language construct, but compiler writers should “try to determine from a given program the best of all possibly interpretations and produce code accordingly.” Sound, but somewhat glib.

Advertisement