Interesting paper on the topic of various program patterns implemented in coroutine. As mentioned in a previous post, continuations are a powerful control flow primitive — they can be used for:
Call with Current Continuation Patterns, Ferguson & Deugo
The paper covers these patterns, and gives sample implementations.
SICP stands for “Structure and Interpretation of Computer Programs”, and is an introductory computer science book, written by Hal Ableson and Gerald Sussman for their introductory computer science course given at MIT from 1981 until 2007. A professional recording done in 1986 and is also available for download online, as is the book itself.
I had missed these comments, and the resultant reddit gossiping – a continuation of the previously argument between two programming languages subgroups. Guido tweeted as follows:
As I feared, the copy of SICP is from someone who believes I am not properly educated. No thanks for the backhanded insult.
I have to admit, sending someone an introductory computer science text can carry a lot of connotations, whether indented or otherwise. Guido gave his two cents on the book, tacking it on to a review of some intro programming books. A little uproar followed in kind.
I experienced SICP only this spring – I had heard of its controversial nature second hand, having gone to a Java school. I noticed a coworker had a copy, so I borrowed it and gave it a weekend skim.
It really is an introductory text, but it is old style in expecting the reader to be really smart and work at the stuff. I wouldn’t call it unforgiving though – it doesn’t do any hand holding, but at the same time, it doesn’t give you any problems that you shouldn’t be able to solve. The examples are practical instead of contrived, but still idealized and simplified. In case you can’t tell already, let me translate: I was hooked.
Unlike van Rossum, I very much enjoyed the book. I also like Coke. Maybe he likes Pepsi. What’s the big deal?
If you watch the video lectures, you might see the same thing as me: I get the sense that SICP isn’t just a book. Or just instruction. It is those things, but it’s also a particular manner of thinking, or rather a particular improvement to our manners of expressing our thoughts about software. In the original first edition preface, the authors write (emphasis mine):
First, we want to establish the idea that a computer language is not just a way of getting a computer to perform operations but rather that it is a novel formal medium for expressing ideas about methodology. Thus, programs must be written for people to read, and only incidentally for machines to execute. Second, we believe that the essential material to be addressed by a subject at this level is [...] the techniques used to control the intellectual complexity of large software systems.
The idea, premise, or belief that they demonstrated to me in their lectures is that through abstraction you can manage software complexity, and build anything you can imagine with software. More importantly, you can design that software in such a way that the code can, piece by piece, be understood and commanded by anyone suitably knowledgable in the art. The lectures eventually climax with a simplified, but complete, model of the language itself, called the metacircular intepreter. Using little or no slight of hand, each piece can be understood and composed independently. By comprehending the incantations you can create new ones, without bound, like magic.
I’m not inventing the magic metaphor– Sussman had a cape and wizard’s staff at the end of that lecture.
Seriously though, it prescribes a model of reality and method of reason about it. And like many philosophies, you can make a way of life or practice out of it. Some people will be really enthusiastic about it, having found much benifit, happiness, or both from it. Those proponents can expound on its virtues, and the general applicability of those virtues may make it sound as if it’s a cure all.
And likewise, there will be opponents that have profound distaste for the it. They may object to the reasoning or axioms of it, or the results of it, or both. In some way it appears to conflicts with their own philosophy; whether the conflict is real or only superficial is not consequential for making them opponents.
I get the impression that many opponents of SICP are also proponents of software abstraction, but come about it a different way or understand the thing differently. We’re not really at odds with each other most of the time, but more-so are experiencing a communication failure.
SICP certainly does have an agenda. But we are seeing it differently.
I can’t claim any philosophic neutrality what-so-ever on SICP.
I finished watching the lectures this past week, having read the book cover to cover the week prior after ordering it on Amazon. What can I say, I’ve joined the order of the lambda.
I think Peter Norvig put it best in his review of SICP on Amazon:
I think its fascinating that there is such a split between those who love and hate this book. [...]
Those who hate SICP think it doesn’t deliver enough tips and tricks for the amount of time it takes to read. But if you’re like me, you’re not looking for one more trick, rather you’re looking for a way of synthesizing what you already know, and building a rich framework onto which you can add new learning over a career. That’s what SICP has done for me.
Cheers.
It started with an innocent enough blog post by Guido van Rossum commenting on Python’s lack of tail call elimination in Python’s history. Okay, not even commenting – it was a parenthetical sentence fragment!
The internet went crazy with comments. Guido attempted to clarify,
However, some technical inaccuracies – or rather, technical issues that the Python language and runtime currently don’t address – led to only more debate. Largest oversights were in his discussion about how tail calls might be implemented in Python,
The first observation is that you can’t do it at compile time. I’ve seen at least one blog entry that used a bytecode hack to replace a CALL opcode immediately before a RETURN opcode with a jump to the top of the function body
Going on to imply that tail recursion was somehow thwarted by dynamic function lookup, that it could only be done when the compiler could statically transform all tail call sites into gotos.
He corrected this in the followup, but then went on to say,
Now, apart from the observation that since TCO essentially is a GOTO, you write spaghetti code using TCO just as easily, Ian Bicking gave a solution that is as simple as it is elegant. …
Where he then presented a classic simple implementation technique for implementing tail call elimination – the trampoline. Of course, you have to do this manually in Python unless you modify the bytecode compiler to do it for you.
((Of course, I can’t help pointing out that non-tail-call procedure calls are also like GOTOs. Guy Steele discussed this analogy/parallel in “Debunking the ‘Expensive Proceedure Call’ Myth, or Proceedure Call Implementations Considered Harmful, or Lambda: the Ultimate GOTO”, available on The Original ‘Lambda Papers’. I’d summarize if I thought there was anything I could add, but there really isn’t))
Joe Marshall has provided the most comprehensive replies to this discussion that I’ve seen, in his 5 part series:
Part 4 is the most focused piece I think, where he addresses the issues I mentioned above:
[example of dynamic tail cal] This will work in any version of Scheme. The compiler doesn’t need to analyze the target of the function call, it only needs to notice that the caller’s stack frame is no longer in use.
And the topic of debugging:
MIT-Scheme has an approach that seems promising. [...] the history is a ring buffer with a limited size. When a tail recursive call is recorded in the history, each frame in the history moves down by one. If a sufficient number of calls are made, the oldest record is deleted
He also mentions in part 2 that debugging tail calls is just something that Schemers learn.
But I have this to add: Yes, it’s terribly convenient to have a stack history when debugging in Python – most of the time you don’t need ever stack frame, but once in a while its useful. But the same thing happens with loops. A failure is detected, but this loop iteration didn’t cause the failure, the cause was 2 iterations back and we don’t have that state any longer. Darn.
A key observation in Scheme is that looping and tail recursion are two abstractions for doing the same thing – iteration over a regular data structure or sequence. Because the problem is the same, the useful debugging features are the same – in both cases, a history is a useful debugging aid, but also bleeds runtime performance.
I also want to defend Guido though (not that he needs defending, he can stick up for himself, but for the sake of argument). He doesn’t need tail recursion to do iteration, or visitor dispatch, or etc. C programmers, those still around, will insist they don’t need C++ classes and templates to do objects, and rightly so. And a Perl programmer will likely tell you they don’t need anything else to do anything. (apologies to the Perl programmers, no offense intended).
And in all these cases it’s true. Guido get things done without tail recursion. And that’s what Python is about – getting things done. And Schemers get things done too, in the minimalist way that Schemers like and are accustomed to.
I’m not going to pretend the various programming languages are equal, but I don’t think there’s a total order either. Even if there is, even if X is a wholey better way-to-do-things than Y, or even mostly better, this whole debate has failed in one very essential way – this discourse was too much a debate about betters and worsers, and not enough a discourse about understanding the other.
I think commenter Martin demonstrates this best: “I fail to see why this is such an important feature that at least a significant amount of people have an opinion about it.” If, after so many words, this is the most common result, then I both sides have failed.
Kudos to Guido for correcting his initial errs, I think he’s done well to describe the Python Way and how Python has chose its alternatives to tail call elimination.
Kudos to Ian for providing trampoline Python code that functions as a working simplified model of tail call elimination – I think that may go a way in explaining TCE to Python developers.
Kudos to Joe for demonstrating cool debugging features in MIT scheme – before that example, I hadn’t considered the case that TCE debugging tools could help in debugging my loop iterations as well.
And kudos to everyone else out there that also accomplished more listening than talking.
I came across this site, hanoimania, when researching application virtual machines. The author, personally, has translated a towers of hanoi solver to dozens of programming languages, utilizing:
Although, the embedded world uses the ARM architecture more often these days.
Reminds me of 99 Bottles.
Lastly I’ve been ranting and raving about 50 in 50 from last month, where Guy L Steele Jr. and Richard P. Gabriel gave a sort of artistic performance — 50 statements of 50 words on programming languages. I’m still looking up historical references from this thing!
From the performance:
Alt text: We lost the documentation on quantum mechanics. You’ll have to decode the regexes yourself.