Print Story Another draft of my Scheme article
Help!
By jacob (Thu Mar 11, 2004 at 10:45:43 AM EST) (all tags)
Here's another draft of the K5 article I'm writing that incorporates many of the changes you all kindly suggested yesterday (thanks very much again for that, by the way). Again, I'd love to know what you think. Have my changes made the article better? Worse? Can you think of a direction for a less-lame conclusion? Is it ready to submit to the queue? What gives?


I think I've tried to address everyone's concerns, though I couldn't figure out a way to address Rogerborg's concern without making a major diversion, so Rogerborg, I promise at some point I'll write an article about the cool Scheme project I'm working on now that has already made me money.

(Also: attention hulver infidel: I think there's a bug in the <code> tag implementation. If you have a line of white space between your tags, everything after that line gets rendered as regular text rather than code. If you put a nonbreaking space on the line the formatter does the right thing, though.)

Why I Like Scheme
Draft - 3/11/04

When I tell programmers that my favorite programming language is Scheme, they tend to react as though I'd told them my favorite snack were packing styrofoam or my favorite music were junior high orchestra recordings: those who can even bring themselves believe me mostly wonder what on Earth I could be thinking. Some wonder if I've ever programmed in a real language like C or C++ (I have), if I'm one of those academic nuts who cares more about proving theorems about programs than actually using them for real work (I'm not), or if all those parentheses have rotted my brain (probably). So what could make me like this weird language with no for loop and so many parentheses it makes you crosseyed?

In this article, I'll tell you what. By the time I'm finished I hope I'll also have convinced you that you might want to give it a shot yourself.


Some words of warning

I'm going to assume that you're a working programmer who comes from a C, C++, Java, or similar background, so I'm not going to go into the details of how Scheme differs from other more-or-less exotic languages like Common Lisp, Standard ML, or Haskell, as interesting and worthy of discussion as those languages are. Suffice it to say that many of the ideas I present here as features of Scheme are also present in some other languages.

Furthermore, there are a large variety of Scheme systems out there, and they tend to do some important things in different ways. For the code in this article I've chosen to use PLT Scheme; it will almost certainly not run in other Schemes without some modification. Most serious Scheme systems have equivalents or near-equivalents to everything I use here, but the details differ.

Those disclaimers out of the way, let's get on to the good stuff.

Scheme head-first

I'm not going to try to teach you how to program in Scheme, but instead to give an impression of how a Scheme programmer tackles problems. So, rather than showing some boring pedagogical example like "Hello world" or a factorial function, I figured I'd show something I've actually had occasion to use in real work: a multithreaded port scanner. Here it is, written basically the way I'd really write it if I needed to:


; scan : string[hostname] (listof int) -> listof (list int string)
; gives the number and well-known service name of each port in the given
; list that is open on the given host
(define (scan host ports)
  (map
    (lambda (p) (list p (port->name p)))
    (open-ports host ports)))

So what does this do? I've defined a function called scan that takes two arguments, a string called host and a list of numbers called ports. It gets every open port using the function open-ports we'll define later and returns each one paired with its service name. To understand how it does it, we're going to need to make a brief diversion into looping.

A brief diversion into looping

Scheme doesn't do looping the way mainstream languages do. That leads a lot of people to think that Scheme doesn't do looping at all, which isn't true — Scheme actually has a very sophisticated and flexible way of writing loops that just takes a while to get used to (no pun intended).

The "assembly language" of loops in Scheme is recursion. Recursion in Scheme is not at all inefficient and does not waste memory, and can frequently lead to nicely clear and elegant solutions to problems. For instance, here's an implementation of a range function (similar to features of Python and Perl) that takes two numbers and builds a list of all the numbers between them in order, written recursively:


(define (range low high)
  (cond
    [(> low high) null]
    [else (cons low (range (+ low 1) high))]))

This might look alien at first, but there's a very compelling logic to what the function says. A range where the low number is higher than the high number is just an empty list (null represents an empty list in Scheme) and any other range is just a list consisting of the low number followed by the range with the same high point but a low point that's 1 bigger (cons is a function that takes an element and a list and returns a new list consisting of the given element followed by the given list). It's a logically elegant way of thinking of the problem that also happens to be an executable program.

I say recursion is the assembly language of loops because while it's the fundamental construct that allows you to get looping to happen in Scheme, real Scheme programmers frequently use constructs built on it rather than using it directly. Owing to the fact that functions can be declared anonymously and used as values (if you're familiar with anonymous inner classes in Java, Scheme functions are like those except that they all have exactly one method that gets run when they're applied and they're much less of pain to write down syntactically), you can write a function that captures the essence of a particular style of loop and takes another function as input to decide what to do at each iteration.

The function map I used the scan function is one example of such a loop: it accepts a function and a list as input, applies the function to each individual element of the list, and returns a new list containing the results. So for instance (map add1 (list 0 1 2 3)) would yield (list 1 2 3 4).

With this in mind, we can get back to our port scanner.

On with the show

So what's going on with the scan function? It's mapping a function (that funny lambda thing) that takes a port number and produces a list of port number and service name over the list of all open ports (the result of calling open-ports). What we'll get back is a list consisting of port-number/service-name pairs, which is exactly what we want.

Implementing open-ports

Next we need to implement open-ports. Here it is:


; open-ports : string[hostname] (listof int) -> (listof int)
; returns the sublist of numbers that represent open ports on the
; given host, performing all checks concurrently
(define (open-ports host ports)
  (threaded-filter
   (lambda (port) (can-connect? host port))
   ports))

The open-ports function checks every port in the list it's provided with in parallel to see if that port is open, and when it's done returns the sublist of those ports that are actually open. It does this using with two new functions: threaded-filter and can-connect?. Since can-connect? is easier, I'll explain it first.

can-connect?: exceptions and sockets

The can-connect? function isn't bad at all:


; can-connect? : string[url] number -> bool
; determines if the host is listening on the given port
(define (can-connect? host port)
  (with-handlers ([exn:i/o:tcp? (lambda (e) #f)])
    (let-values ([(ip op) (tcp-connect host port)])
      (close-input-port ip) (close-output-port op) #t)))

It's just a small wrapper around the tcp-connect library function, which returns two values, an input port and an output port, if it succeeds at connecting, and raises an exception if it doesn't. PLT Scheme has a built-in exception mechanism very similar to Java's or C++'s in that any code can raise an exception, and that exception propagates up the stack until it reaches an appropriate handler (specified by try/catch in C++ or Java, with-handlers in PLT Scheme). The can-connect? function calls tcp-connect and returns #t (true) if it succeeds. If tcp-connect raises an i/o:tcp exception (which it will do if it can't establish a connection), with-handlers catches that and returns #f (false).

threaded-filter: more parallel loops than you can shake a stick at

The threaded-filter function takes a little more explanation. I'll give you the whole code at once:


; threaded-for-each : (X -> Y) * (listof X) -> void
; applies the function to each element of the list in parallel
(define (threaded-for-each f l)
  (let ((c (make-channel)))
    (for-each (lambda (x) (thread (lambda () (f x) (channel-put c #t)))) l)
    (for-each (lambda (x) (channel-get c)) l)))
 
; threaded-map : (X -> Y) * (listof X) -> (listof Y)
; maps the given function over the given list with each computation
; done in parallel
(define (threaded-map f l)
  (let ((boxes (map box l)))
    (threaded-for-each (lambda (b) (set-box! b (f (unbox b)))) boxes)
    (map unbox boxes)))
 
; threaded-filter : (X -> bool) * (listof X) -> (listof X)
; returns the sublist of the given list for which the given predicate
; returns true, with each computation done in parallel
(define (threaded-filter pred l)
    (let ((filters (threaded-map pred l)))
      (let loop ((items l) (filters filters))
        (cond
          [(null? items) '()]
          [(car filters) (cons (car items) (loop (cdr items) (cdr filters)))]
          [else (loop (cdr items) (cdr filters))]))))

That's a lot of code to digest, but fortunately the work we've done to make all our functions generic has paid off: these three functions can be library code from now on and we've got three useful new loops we can use over and over and over (again, no pun intended).

First take a look at threaded-for-each. You may notice that the thread interface it uses is unusual. PLT Scheme uses unusual concurrency mechanisms taken from Concurrent ML to create and synchronize threads. Rather than locks on shared memory, the CML primitives allow threads to send values to each other over channels and block until those values are transmitted. In this example, threaded-for-each creates a new channel, spawns a thread for each item in the input list that runs the input function on it and then sends a message over the channel indicating that it is done. Once all threads are spawned, the function waits for a message from each of the spawned threads and then returns.

We use that to build threaded-map by building a list with a bunch of places that need to be destructively updated and then using threaded-for-each to update them all concurrently. We can then use threaded-map to implement threaded-filter, the function we needed that removes elements from a given list if they fail to pass a test, by concurrently mapping that test function over the given input list to produce a list of booleans, and then using that list of booleans along with the original list to build up the result.

With that done, we've got everything we need to detect open ports, and all that's left is to look up service names.

port->name: libraries, HTTP communication and regular expressions

There's a little complication in implementing port->name. If I only wanted my program to run on Unixish systems I might just call the getservbyport C function through PLT Scheme's foreign function interface (it only takes a few lines, actually), but I'd actually like it to run on Windows and Macs and various other platforms that don't have access to getservbyport (or even the /etc/services file it uses). Fortunately, the Internet Assigned Numbers Authority has an online list of ports in the same format as /etc/services, so we'll make our program fetch that if a local file isn't available. Here's the code:


(require (lib "url.ss" "net"))
 
(define NAMES
  (let ([ip (if (file-exists? "/etc/services")
                (open-input-file "/etc/services")
                (get-pure-port (string->url "http://www.iana.org/assignments/port-numbers")))]
        [nametable (make-hash-table)])
    (while m (regexp-match "([^ \t\r\n])[ \t]+([0-9]+)/tcp[ \t]+([^\r\n])" ip)
       (hash-table-put! nametable (string->number (list-ref m 2)) (list-ref m 1)))
    nametable))
 
(define (port->name p) (hash-table-get NAMES p (lambda () "unknown")))

After loading in a library that defines some useful HTTP-related functions, we define the global variable NAMES to be a hash table that maps numbers to strings. To do that, we get a new input port that's connected to either /etc/services (if it exists) or to the IANA's web page, and we also make an empty hash table. Then we loop over the input port getting each port-number/name combination (as determined by a regular expression) and add each to the hash table, and finally we return the hash table which becomes the value of NAMES. Unfortunately Scheme has no while loop, but since it's such a nice fit for this problem we'll have to define it ourselves.

while: the power of macros

We've implemented lots of loops so far, but while is especially tricky because of the way we want to use it. In our previous loops we required users to pass in an anonymous function, and furthermore none of our loops introduced their own variable names. We could probably make a variant of the while loop that conformed to those expectations, but I'm stubborn and I'd rather have Scheme conform to me than to have me conform to it. If I were programming in Java or C, I'd just be out of luck, but Scheme lets me have my way. Scheme has a very unusual facility called macros (only a cousin of C macros, the well-known black sheep of the family) that take a piece of a parse tree as input and produce another one as output, allowing programmers to automatically rewrite code as they see fit. We can use that facility to make a while loop that will be have just like I want it to. Here's the macro:


(define-syntax (while stx)
  (syntax-case stx ()
    [(_ var test body)
     (identifier? #'var)
     #'(let loop ((var test))
         (when var body (loop test)))]))

It's scary-looking, but don't fear, it's really pretty simple once you get used to the way macros are written. There's some junk at the top that says that this is a macro and sets us up to do some work, but the important stuff begins on the third line, which specifies a pattern for what a use of while should look like. It should be

(while [some-variable] [some-test] [some-body])

where the variable has to literally be a legal variable name but the test and the body can be any old Scheme expression. It also gives each of these pieces a name (var, test, and body, respectively). Those names are important for the rest of the macro: starting with the #'(let ...) line, the whole rest of the code isn't actually code, but rather a template for what the output syntax should be, and it's returned literally except that every time var, test, or body appears in the template, whatever actually appeared in that blank is substituted in instead.

Once you get the hang of it, macros like these are pretty simple. For example, our use of while in defining the NAMES table turns into the following after Scheme expands it (code from the original scan in bold, code introduced by the macro in normal font weight):


(let loop ((m (regexp-match "([^ \t\r\n])[ t]+([0-9]+)/tcp[ \t]+([^\r\n])" ip)))
  (when m
    (hash-table-put! nametable (string->number (list-ref m 2)) (list-ref m 1))

    (loop (regexp-match "([^ \t\r\n])[ t]+([0-9]+)/tcp[ \t]+([^\r\n])" ip))))

Of course we won't actually ever see this code or type it in — Scheme generates it for us behind the scenes when it runs our program. What the expanded code actually does is use one of Scheme's built-in loops, the so-called "named let", to run the test expression and bind it to the variable m. If m isn't false (in Scheme anything that isn't #f is true), it evaluates the body with m still bound to the test's result and then loops, checking the test again. It's a simple pattern, and one that would be hard to write down in other languages.

Since that loop was the last thing we needed to write, we're done and we've got ourselves a complete working port scanner. Hooray!

Wait a minute, where's the I/O?

I don't need any. Scheme, like Python, is designed around an interactive read-eval-print loop. I can open DrScheme, type in all the definitions, and then just use my function however I want. Here's an example run:


> (scan "localhost" (range 1 100))
((22 "ssh") (25 "smtp"))
> (display-xml/content
   (xexpr->xml
    `(open-ports ,@(map
                    (lambda (entry) `(port (number ,(number->string (car entry))) (name ,(cadr entry))))
                    (scan "localhost" (range 1 100))))))
<open-ports>
  <port>
    <number>22</number>
    <name>ssh</name>
  </port>
  <port>
    <number>25</number>
    <name>smtp</name>
  </port>
</open-ports>

Some conclusions

So there's the whole port scanner. The interesting thing about this solution isn't its size or efficiency, but how at nearly every stage of the process Scheme gave me the ability to say exactly what I meant, so I could make the language do things my way rather than it making me do things its way. Schemers take full advantage of that ability, and its hard to find a group of programmers more stubborn in their pursuit of writing down exactly the concept they are trying to convey rather than having to clutter their programs with extraneous concepts.


Note

If you actually want to execute this code, install DrScheme (when it asks what language level to use, set it to "textual" or "graphical"), open it, and copy all the code from this article into the definitions window. The order you put them in doesn't matter except that the while macro needs to be at the top. Hit the "execute" button and you're off.  

< What's that sound | BBC White season: 'Rivers of Blood' >
Another draft of my Scheme article | 18 comments (18 topical, 0 hidden) | Trackback
So tell me... by Breaker (6.00 / 1) #1 Thu Mar 11, 2004 at 12:15:39 PM EST
I'm going to assume that you're a working programmer who comes from a C, C++

At any point...
What's on the * call stack* and how do I debug it?




It's a little complicated by jacob (6.00 / 1) #2 Thu Mar 11, 2004 at 12:40:25 PM EST
What's on the call stack? Well, it's not really a stack exactly, so we call it a list of continuation frames, but you can think of it as a stack, and each item represents an expression in the program. So for instance if you were running the program

(+ (+ (+ 7 3) 4) 2)

and the innermost expression was being evaluated then the continuation frames would be:


(+ (+ (+ 7 3) 4) 2)
(+ (+ 7 3) 4)
(+ 7 3)

The complicating factor is that when a function calls another function as the last thing it does, it removes itself from the stack, so the continuation frames for


(define (f)
  (f))

(that is, an infinite recursion) always look like

(f)

no matter how many iterations have happened (and this operation will never run out of stack memory, as the equivalent code in C would).

There's a debugger that lets you directly set breakpoints and so on in CVS, but it's not in the public distributions yet (soon!). For now, you only see these when you throw an exception; if it's not ever handled, DrScheme will eventually handle it by showing the continuation frames at the point when the exception occured.

--

[ Parent ]

Alright... by Breaker (6.00 / 1) #3 Thu Mar 11, 2004 at 12:56:27 PM EST
What's on the call stack?

I meant on the processor call stack.  IP, SP, ES, etc.  Don't know what that'll look like on a non Intel like machine, but it's got to translate somewhere...

But in your example, you're using first class values (admittedly, for brevity and clarity, and also a good example), and that's straightforward in any language.  What about ADT's?  Pointers? Structured exception handling?

If you're aiming your tutorial at people that already know how to code, then how about some debug advice?

Heh, took me a few weeks while learning C++, to learn the value of the println commnand...


[ Parent ]

Implementation-specific by jacob (6.00 / 2) #5 Thu Mar 11, 2004 at 01:59:30 PM EST
The Scheme standard really doesn't talk about what's supposed to go on at that level at all, and there are dozens of implementations that all make different choices about how to best represent the data. For that reason the best way to understand what's going on during the dynamic run of a Scheme program isn't to look that the processor or the way bits are set in memory but instead to have a more abstract computational model in your mind and reason about that. For instance there are multiple different viable ways to represent the call-chain in memory, and as I alluded to before, they've all got different trade-offs that will make different operations more or less expensive, they'll all make the whole program look radically different at the architecture level, and trying to figure out what's going on from that sort of information will be just about impossible. On the other hand, if you look at it from a more abstract point of view in which a function call is essentially a basic part of your computation that can't be further reduced, everything will make sense. (Sorry if I'm being a little too verbose or unclear here; this touches strongly on the topic of the master's thesis I'm writing now so I've got a lot to say about it.)

On a more practical level: to debug, your best bets are to use a stepper/debugger to set break points and you the steps a program is taking, use print statements, make use of stack traces, and write small functions you can test independently — one reason a mostly-functional style is very useful.

I hope that answers your question. :)

--

[ Parent ]

you should put forth the argument.. by infinitera (6.00 / 1) #8 Thu Mar 11, 2004 at 02:44:12 PM EST
That the bits and metal debugging people are so fond already disappeared with the virtual machines of Java and C#, and that Scheme actually does it better. ;)

if you weren't such a self-righteous asshole, I wouldn't be so rude to you - nathan
[ Parent ]

Good answer. by Breaker (6.00 / 2) #15 Fri Mar 12, 2004 at 01:43:35 AM EST
TYVM!


[ Parent ]

Loops by ucblockhead (6.00 / 2) #4 Thu Mar 11, 2004 at 01:19:49 PM EST
I like the additional bit on looping.

One question, again coming from a C bias (maybe you don't know the answer to this): When you use recursion to simulate looping, what sort of optimization does Scheme do to collapse returns? In other words, if I were to simulate for(int i=0;i<10000;i++) using recursion in C, my program would obviously run like crap. How does Scheme avoid this?
---
[ucblockhead is] useless and subhuman


this is actually a big deal by jacob (6.00 / 1) #6 Thu Mar 11, 2004 at 02:24:56 PM EST
The Scheme standard specifies that you've got to do a particular optimization called proper tail recursion or sometimes tail-call optimization. It works like this: say you've got a pair of functions like


int f(int i) {
  printf("f\n");
  return g(i);
}
 
int g(int i) {
  if (i == INT_MAX) {
     return 20;
  } else {
     return f(i+1);
  }
}

Most C compilers will generate code such that when f calls g it will push a new activation record for g on the stack setting the return pointer to itself, and then once control has returned to it returning back to whoever called it. That will be slow and consume lots of stack memory in this case. However, if you think about it, since once f calls g there's nothing left for it to do other than return what g gives it right back to its own caller, it could instead free all the memory associated with its own activation record and build a new one for g whose return pointer pointed directly to f's caller, thus using no extra memory. You can actually use this technique to compile function calls in tail position all the way into gotos making them very cheap compared to traditional function calls both in time and memory requirements. In this example, for instance, the compiled code for f and g could turn into something almost equivalent to a while loop in terms of the assembly code it generated.

Anyway, there's a big body of literature on this topic and the implementation I described is one of many. See for instance "RABBIT: A Compiler for SCHEME" from the readscheme library, particularly the section "The Imperative Treatment of Applicative Constructs" starting on page 37 or "Lambda: The Ultimate GOTO" both by Guy Steele, one of Scheme's inventors, and "Proper Tail Recursion and Space Efficiency" by Will Clinger.

--

[ Parent ]

kind of what i'd like to see in the article too by infinitera (6.00 / 1) #7 Thu Mar 11, 2004 at 02:31:41 PM EST
The standard trollish post on k5 is going to be "So what you're saying is, you can make loops in scheme? Why bother when I already have them!"

I think some of the material in your flamewar with trhurler could be included here, about thinking about problems and data in more efficient ways. You talked a little bit about it already, but I think it could do with more.

if you weren't such a self-righteous asshole, I wouldn't be so rude to you - nathan
[ Parent ]

I am that rarest of things by leviramsey (3.00 / 0) #9 Thu Mar 11, 2004 at 05:58:04 PM EST

A programmer who adores C/C++ and Scheme...


--
Could I be the next Lee Abrams?


heh, by infinitera (6.00 / 1) #10 Thu Mar 11, 2004 at 06:49:12 PM EST
Another thing we have in common.

Except that I limit my admiration at C, not C++.

if you weren't such a self-righteous asshole, I wouldn't be so rude to you - nathan
[ Parent ]

Yerrrrs by Rogerborg (6.00 / 1) #11 Thu Mar 11, 2004 at 07:12:38 PM EST
That's about what I figured.  Well, good luck with it.

-
Metus amatores matrum compescit, non clementia.


<code> tag by gazbo (6.00 / 1) #12 Thu Mar 11, 2004 at 08:42:09 PM EST
Scoop shouldn't do anything with that tag at all; regular tags are all treated alike, and context independent (once it's matched the tag, it checks it's valid, and then spits it out again, plus pushes it on the stack to ensure it matches up) so whitespace or newlines are completely ignored.

I tried to reproduce what you said and couldn't in any post mode - can you find an example where it happens, and post it in Plain Text formatting?  Also, what post mode do you use - HTML or AutoFormat?


I recommend always assuming 7th normal form where items in a text column are not allowed to rhyme.



testing 1 2 3 by jacob (3.00 / 0) #13 Fri Mar 12, 2004 at 12:58:01 AM EST

--- code begins here ---
hello there is is a big gob of code.

So big it doesn't fit in one paragraph.
--- code ends here ---

In the second blob ("so big it doesn't ...") renders in normal font face. Actually looking at the generated html, maybe it's the fact that scoop is inserting a paragraph tag in there and Mozilla 1.5, the browser I'm using, interprets that as ending the code block? I dunno. I'm using auto format.

--

[ Parent ]

Yup, it's a browser thing by gazbo (6.00 / 1) #14 Fri Mar 12, 2004 at 01:14:59 AM EST
Displays fine in IE, not in Firebird.

I have no idea whether the HTML spec claims that a P tag should cancel a code tag or not.  It could also be a CSS thing, where the P tag is resetting the font to the default body style.

Weird.  In the meantime, I suggest installing a proper, standards compliant browser ;-)


I recommend always assuming 7th normal form where items in a text column are not allowed to rhyme.

[ Parent ]

Also works fine in Opera... (n/t) by leviramsey (3.00 / 0) #16 Fri Mar 12, 2004 at 06:57:31 AM EST

--
Could I be the next Lee Abrams?
[ Parent ]

You got the recursion thing wrong. by em (6.00 / 1) #17 Fri Mar 12, 2004 at 08:09:47 PM EST
Recursion in Scheme is not at all inefficient and does not waste memory,

Nope.  You mean tail recursion doesn't waste memory; it gets compiled into a vanilla loop.  The range function you give is not tail-recursive; it needs to wait for the result of the recursive call (range (+ low 1) high) to pass it to cons; thus, it needs to use the call stack to keep track of the execution state.  The computation of (range 0 9) with your implementation looks like this.


(cons 0 (range 1 9))
(cons 0 (cons 1 (range 2 9)))
(cons 0 (cons 1 (cons 2 (range 3 9))))

...
(cons 0 (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 (cons 6 (cons 7 (cons 8 (cons 9 null))))))))))
...
'(0 1 2 3 4 5 6 7 8 9)

The size of the execution stack grows linearly with high-low.

The efficient, tail-recursive way to do it is as follows (I don't really know Scheme, so I'll do Lispy-looking pseudocode and hope for the best):


(define (range low high)
  (define (iter low i result)
    (cond
      ((= i low) (cons i result))
      (else (iter low (- i 1) (cons i result)))
  (iter low high null))))

iter is an auxiliary tail-recursive function that uses the parameter result to accumulate partial results as we construct the list.  We start constructing the list from the rear, pushing elements into the front in decreasing order.  If we call (range 0 9), we get the following computation:


(iter 0 9 null)
(iter 0 8 '(9))
(iter 0 7 '(8 9))
(iter 0 6 '(7 8 9))
...
(iter 0 0 '(1 2 3 4 5 6 7 8 9))
'(0 1 2 3 4 5 6 7 8 9)

Here, the size of the execution stack is constant. The result list grows linearly, but it's not in the stack.  The same stack frame gets reused for each call to iter.

--em


yes by jacob (6.00 / 1) #18 Sat Mar 13, 2004 at 01:10:16 AM EST
Of course you're right that tail recursion is the most efficient way to go, and a real library implementation of range would probably use the tail-recursive implementation you suggest for that reason. But it's also true that function calls in general in most Scheme implementations are lighter weight than C function calls and that Scheme compilers and interpreters make various representation decisions that will make calling a function cheaper. This basically falls under the category of "things I thought were a little too complicated to explain in the article," though you're right, I ought to at least mention the issue.

--

[ Parent ]

Another draft of my Scheme article | 18 comments (18 topical, 0 hidden) | Trackback