Sunday, January 27, 2008

Scheme For Enlightenment Part Four - Even More Factorials

The dreaded Scheme factorial example is beaten over the head and shoulders recursively.

Another variant of the loop factorial. It uses a "let loop".

(define (factorial x)
(let loop ((count x) (product 1))
(if (= count 0)
product
(loop (- count 1) (* product count)))))

The loop starts, creating variables count and product. The variable count starts at x and counts down to 1. But also, product, starts at one. That's the second line. Once each loop, product is multiplied by count, and count is decremented. That's line five. When count is zero, product is returned in the forth line. One odd bit of the syntax is how the loop works. It looks recursive. If so, it's tail recursion and fully optimized. But it really doesn't matter if it's a iterative loop or recursion. Scheme can decide that. That is, unless it can't be nested. The do loop can certainly be nested. It's reasonable to assume that let loops can be nested also. The full inner loop would execute before the outer loop, and each would benefit from tail recursion optimization, at least in theory.

The original version of the above let loop factorial was more confusing. In it, the counting variable was named x. That's the same name as the parameter. One expects that the inner definition hides the outer definition. So how does Scheme know to assign the outer definition to the inner for the initialization? Apparently, it's designed to. But that doesn't make it consistent.

As an aside, in my examples, i've used a short cut syntax for defining all functions. In the Guile Reference, section 3.1.2.4, it is suggested that this form should not be used. The lambda syntax should be used instead.

It could be argued that the alternative define forms are rather confusing, especially for newcomers to the Scheme language, as they hide both the role of lambda and the fact that procedures are values that are stored in variables in the some way as any other kind of value.


Using the lambda syntax, the above example becomes this.

(define factorial
(lambda (x)
(let loop ((count x) (product 1))
(if (= count 0)
product
(loop (- count 1) (* product count))))))


While the lambda keyword does indicate that a function is being created, and the define keyword indicates that this function is getting bound to a name, i don't like it much. It has yet another nested set of parenthesis, which means that there is that much more i might get wrong. There's an extra line of code (though there needn't be). The indention of the body of code is deeper, at least in the emacs pretty printer style. And finally, lambda is a Greek letter that doesn't mean anything. Go ahead, look up lambda in Google. It has been assigned all kinds of meanings. Scheme and Lisp are high in the list. I think Dennis Richie got it right. The language keywords are not the important part of the language. The important part is the bits that the programmer has created in it. So, in C, structure uses one character keywords. Here, we have the opportunity to omit a whole keyword entirely. So much the better. As a recent novice, i consider lambda an advanced topic that one can safely ignore for awhile.

No comments: