Scheme loops

If you’re a schemer, expressing iteration by means of tail-recursion and named lets has probably become second-nature to you. I find this idiom both natural and elegant, but as Olin Shivers points out in his DanFest presentation below, it has some drawbacks. For instance, the code in a typical named let will work only for a given sequence type (e.g., a vector or a list); and, as Olin explains, its ‘goto-nature’ does not mix well with lexical scope. In other words, tail-recursive schemy iteration is too low-level and, according to Olin, a higher-level abstraction hiding details and providing a modular interface and proper lexical scope is called for. In his presentation, he outlines his solution to this problem, which, as you will see, amounts to defining a looping domain-specific language (actually, a couple of them). A more detailed explanation is given in his paper The Anatomy of a Loop. As an extra, the first few minutes of the video below will get you acquainted with the mysterious¬† Dan effect.

But Olin’s is not the only solution to looping in scheme. Alex Shinn wrote and excellent survey on Scheme iteration methods in his Yow! LOOP macros are LOOPY!, which discusses at length current approaches to solve the problems mentioned above (like srfi-42 eager comprehensions or Jonathan Amsterdam’s iterate macro). For extra fun, Alex includes implementations for most of the loop constructs he reviews, a good way of improving your macro programming.

(Also worth reading in this context are Oleg Kiselyov’s thoughts on collection traversal APIs, where he draws a clear distinction between enumerators (such as scheme’s for-each or fold) and cursors (such as C++ iterators, i.e., objects maintaining internally the “current element” of the collection being traversed). As you will see, he makes a pretty good case for enumerators.)

So, you see, there’s many a way to loop a cat!

About these ads
Posted in Scheme. 2 Comments »

2 Responses to “Scheme loops”

  1. Looping in Scheme | Wisdom and Wonder Says:

    […] Ortega captures a few perspectives on iteration in Scheme in his post, Scheme Loops. This was written by Grant. Posted on Saturday, February 9, 2008, at 6:39 pm. Filed under Link. […]

  2. Scheme lectures, mostly « programming musings Says:

    […] DanFest videos, which i’ve mentioned before one or two times. Virtually all lectures in this series are worth watching, but, if Robby’s talk above […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 42 other followers

%d bloggers like this: