I've started learning Scheme, and my system of choice is Guile, a version of Scheme designed to be used as a scripting language for Unix-like operating systems. I'm using the older 1.8 version that is available in Ubuntu right now. The new, much improved 2.0 version will be available in the next Ubuntu version but for now 1.8 is plenty for me to learn the basics.

I have been programming in one way or another for all of my adult life. My experience ranges from embedded systems to very large machines and in a variety of languages. I have never really used Scheme, though, and never tried to work in a largely functional programming language before. The code and all the explanations here is the work of a beginner trying to learn about Scheme programming, and it's bound to contain a lot of bad coding style, suboptimal solutions, misconceptions and outright errors.

So why do I do this? The most effective way to learn something is perhaps to explain it to others. It forces you to make everything explicit, and will expose any doubts or misunderstandings you may have. Now, I don't expect anyone to actually follow these posts in any detail; you, collectively, are the imaginary audience I need for me to to write this.

Guile is Scheme. What does Scheme look like? Here's a bit of scheme code:

 (define (range low high)     (if (> low high)       '()       (cons low (range (+ low 1) high)))) 

>(range 1 5)
=> (1 2 3 4 5)

This is a pretty useful function, and not surprisingly a variant (named iota for obscure reasons) is available in a Guile library already, along with a more powerful function called list-tabulate that lets you use any kind of list-generating function.

First, note that there's plenty of parentheses. Lots of them, in fact. Both programs and data use the same notation, and it's quite easy to treat a program as data or the other way around. On the other hand, all those parentheses get quite confusing, so a good editor that shows you where each pair belongs is really helpful if you're going to write Scheme code. I use Vim; other people like Emacs.

Scheme, like LISP, uses prefix notation. That is, first we give the operation, then the data to operate on. So if we want to add two numbers we'd do (+ 2 2), and the expression would be replaced with 4¹. The if-statement comparison shows the same order: if (> low high) would be if (low>high) in many other languages.

Simple statements like numbers or variables can stand by themselves. Any operator or function has to be the first element in a list followed by its parameters. When the function returns the whole thing is replaced by the result. Makes sense, I think, as that's the only way to know what arguments belong to an operator. The range call in the last line, (range (+ low 1) high) has two parameters, where the variable high simply gets replaced with its value, while (+ low 1) is a statement with operator + and two arguments for + to add.

The fundamental way to loop in Scheme is by recursion. We wrap the code we want to loop over in a function². We repeat the body of this function by calling the function again at the end. So we call range with two parameters low and high. If low is smaller, we make a list pair with low as the first element, and the result of calling range with the next value of low and high as parameters. Once they're equal we return back up and build the list on the way. Proper lists end with the empty list value, so we return '() for the final element ("'" is a quote, so the list is not evaluated).

This sounds inefficient perhaps, but it is not. When the recursive call happens at the end this becomes just as fast and efficient as a regular loop. Scheme has other ways to create loops, such as do and while statements, but they are all defined by tail recursion like this.

This is what a non-recursive version could look like, using a while loop:

 (define (range-iter low high)   (let ((acc (list high)))     (while (< low high)     (set! high (1- high))     (set! acc (cons high acc)))     acc)) 

To me this is perhaps easier to understand, but it's not as elegant as the first version above, and it was more difficult for me to get right.

Now, I said that when the recursive call happens at the end, Scheme can optimize it so it's just as efficient as a regular loop. When the recursive call happens last there is nothing left to do at that level. Scheme doesn't have to keep track of each level, and can return directly to the top at the end. But if you look at the first version, the range is not, in fact, the last statement; cons is. The first version is not properly tail-recursive in other words. Something like

> (range 1 50000)

will fail with a (stack-overflow) error. Scheme has to keep track of each level so it can do the cons at the end. We have to rearrange things so that the cons happens on the way down, not when going back up. We assemble the next part of the list and send it along to the next iteration with an extra parameter. We also define a wrapper function without the extra value just to make it neat — remember, functions are cheap.

 (define (inner-range low high acc)   (if (> low high)     acc     (inner-range low (- high 1) (cons high acc))))  (define (range low high)     (inner-range low high '())) 

Note that this is for the ageing 1.8 version of Guile specifically; the newer 2.0 version of Guile or other Scheme implementations may well have faster recursion. And in practice, a 10% difference in speed isn't very important compared to readability and code clarity. If speed really is critical, you're not coding in a dynamic language anyway.

--