Ezra: Function calls are not stack frames

I don't have much to add to this but Ezra's saying things that are true:

Tim Bray is spreading more misinformation about tail recursion. He describes it this way:

It looks like a subroutine call, but in the case where it occurs as the last thing in the routine, it magically, silently, and automatically gets turned into, now how did I put it? “A highly controlled and structured GOTO.”

A tail-call is a subroutine call. The efficient implementation does not magically transformed into something else; if it doesn't create a stack frame on such a call, it's because one simply isn't relevant.

It's worth reading Ezra's whole post. I especially appreciate his point about confusing semantics with cost model.

Proposed json.plt change

I'm not sure how many users I have of my json.plt PLaneT package, nor how many of them read my blog. But I thought I'd see if I could take a straw poll here. I'm thinking about changing the data definition in a backwards-incompatible way. What if I said:

A jsexpr is one of:

• 'null
• boolean
• string
• integer
• inexact-real
• (vectorof jsexpr)
• (listof (cons symbol jsexpr))

The nice thing about this representation is that it's easier to quote and quasiquote. The down-sides are that array manipulation is a little less convenient, and table lookup is slower.

Another alternative is:

A jsexpr is one of:

• #:null
• boolean
• string
• integer
• inexact-real
• (listof jsexpr)
• (listof (cons symbol jsexpr))

The nice thing about this is that both arrays and tables are conveniently represented as lists. But it's a little uglier for representing null, which is necessary to avoid ambiguity between the JSON strings { "null" : [] } and [[null]]. Note that it's also a little more subtle to distinguish between arrays and tables.

Other possible unambiguous representations of null include #\null, #"null", or #&0. Yech.

If you have any opinions, feel free to comment here or email me privately.

Update: Whoops, can't have them both be lists, because of the ambiguity between the empty object and empty array.

Mitchfest blog

We've created a Mitchfest blog where we'll be posting updates on new material as it becomes available, including presentation slides, videos, and publication of issues of the Festschrift.

Quote of the day

"What's surprising to me is that this language ever managed to achieve widespread use - but I guess it's just another example of how you can break a whole bunch of precious rules and the sky doesn't necessarily fall in. Software is full of people declaiming their 'thou shalt not' lists, and right across the street there's another bunch of people breaking those very rules quite profitably."
-- Daniel Earwicker

Mitchfest program

We've posted the Mitchfest schedule and program!

Call for Participation: Scheme Workshop 2009

[Note: only one day left to register! --Dave]

2009 Workshop on Scheme and Functional Programming
Co-Located with the Symposium in Honor of Mitchell Wand

August 22, 2009
Boston, Massachusetts, USA
http://www.schemeworkshop.org/2009

CALL FOR PARTICIPATION

To the delight of all and sundry, the 2009 Scheme and Functional Programming Workshop will be held on August 22nd at Northeastern University, and it is a signal honor for me to be able to invite YOU to the WORLD'S FOREMOST WORKSHOP on the marvelous Scheme language, and to present a program PACKED with contributions from familiar faces and new ones, certain to amaze, delight, and edify. Lend us your ears, and we will widen the space between them.

- John Clements

IMPORTANT DATES

August 11, 2009 - Registration deadline
August 22, 2009 - Workshop on Scheme and Functional Programming
August 23-24, 2009 - Symposium in Honor of Mitchell Wand

VENUE

Northeastern University
Boston Massachusetts
Curry Student Center Ballroom (Building 50)
346 Huntington Ave
Boston, MA 02115

ACCOMMODATION

A limited block of hotel rooms has been reserved for participants of the Scheme Workshop and/or the Mitchell Wand Symposium at hotels in Cambridge and Boston. See the workshop web site for more information, and please note that some of these special rates have already expired.

REGISTRATION

The registration fee will be $40 to help cover the operating costs and lunch accommodations. Please register by August 11, 2009 so that we will have an accurate head count. To register, please send an email to aoeuswreg@brinckerhoff.org with your name and any dietary restrictions for lunch.

PROGRAM COMMITTEE

• John Clements (Cal Poly State University (organizer & chair))
• Dominique Boucher (Nu Echo)
• Abdulaziz Ghuloum (Indiana University)
• David Herman (Northeastern University)
• Shriram Krishnamurthi (Brown University)
• Matthew Might (University of Utah)
• David Van Horn (Northeastern University)

PRELIMINARY PROGRAM

Invited: If programming is like math, why don't math teachers teach programming?
Emmanuel Schanzer

Invited Talk on Future Directions for the Scheme Language
The Newly Elected Scheme Language Steering Committee

The Scribble Reader: An Alternative to S-expressions for Textual Content
Eli Barzilay

World With Web: A compiler from world applications to JavaScript
Remzi Emre Başar, Caner Derici, Çağdaş Şenol

Scalable Garbage Collection with Guaranteed MMU
William D Clinger, Felix S. Klock II

Distributed Software Transactional Memory
Anthony Cowley

Sequence Traces for Object-Oriented Executions
Carl Eastlund, Matthias Felleisen

Keyword and Optional Arguments in PLT Scheme
Matthew Flatt, Eli Barzilay

Fixing Letrec (reloaded)
Abdulaziz Ghuloum, R. Kent Dybvig

Descot: Distributed Code Repository Framework
Aaron W. Hsu

A pattern-matcher for miniKanren -or- How to get into trouble with CPS macros
Andrew W. Keep, Michael D. Adams, Lindsey Kuper, William E. Byrd, Daniel P. Friedman

Randomized Testing in PLT Redex
Casey Klein, Robert Bruce Findler

Screen-Replay: A Session Recording and Analysis Tool for DrScheme
Mehmet Fatih Köksal, Remzi Emre Başar, Suzan Üsküdarlı

Interprocedural Dependence Analysis of Higher-Order Programs via Stack Reachability
Matthew Might, Tarun Prabhu

Get stuffed: Tightly packed abstract protocols in Scheme
John Moore

Higher-Order Aspects in Order
Eric Tanter

Peter J Landin (1930-2009)
Olivier Danvy

Selectively disabling tail recursion

The anti-tail-recursion crowd often complains about loss of information in stack traces. In DrScheme, if you raise an exception after a sequence of tail calls:

(define (fact-iter n acc)
  (if (zero? n)
      (error 'fact "stop!")
      (fact-iter (sub1 n) (* n acc))))
(fact-iter 3 1)

the stack trace you get back has very little information in it.

One argument you'll sometimes hear from people like me is that in a properly tail calling language, you can always turn a tail position into a non-tail-position, whereas the reverse is impossible. But in practice, when you want broadly better diagnostics, manually converting lots of individual function calls throughout a program is too hard to be practical, and you then have to go and undo it afterward.

So in the spirit of linguistic tools for diagnostics, I've discovered a dirt-simple trick for improving the information in stack traces while debugging.

PLT Scheme lets you hijack the normal meaning of function application by rebinding the #%app macro. So I defined a utility called trace-app that wraps its function application in (roughly) the identity function, forcing the given function call out of tail position. Then all you have to do is add to the top of a module:

(require (planet dherman/tail:4))
(define-syntax #%app trace-app)

and suddenly, all function applications that occur syntactically within the current module body are non-tail calls, and voilà:


Update: I've posted a new version of the package, which exports trace-app in a slightly different way. The initial version had a hazard that client modules which used

(provide (all-defined-out))

would inadvertently re-provide #%app, which would then disable tail recursion for its client modules.

The new way to use it is

(require (rename-in (planet dherman/tail:5) [trace-app #%app]))

or

(require (only-in (planet dherman/tail:5) [trace-app #%app]))