better, but in the same style:
(define fact
(lambda (i)
(if (nonpositive? i)
1
(* i (fact (sub1 i))))))
|> Next is the text book version. A hacker who wanted to optimize her
|> implementation of factorial wouldn't write a recursive function -- she'd
|> write a loop. In Scheme, loops have a startling appearence. In this
|> case, the loop is implemented by a tail recursive nested function.
|>
|> ; If you haven't learned scheme, but know c or perl
|> ; or almost any other popular language, this will
|> ; be hard to follow.
|> ;
|> (define (fact i) ; warning -- untested code
|> (define (loop next-factor answer-so-far)
|> (if (< next-factor 1)
|> answer-so-far
|> (loop (- next-factor 1) (* next-factor answer-so-far))))
|> (loop i 1))
Ugh! Even for for Scheme-freak this is unduly hard. Far far better
is using named let:
;trivial conversion from the above
(define fact
(lambda (i)
(let factorial ([i i][acc 1])
(if (nonpositive? i)
acc
(factorial (sub1 i) (* sub1 acc))))))
Named let has been replaced for most purposes here by recur (just
a syntax change; let's face it, with let, named let, let*, and letrec,
"let" is a bit overused).
Note also that this multiplies the numbers in the opposite order.
This is mostly important for efficiency issues here, but usually
recursion needs to performed in the proper order.
;fact in the right order
(define fact
(lambda (i)
(recur factorial ([i i])
(if (nonpositive? i)
1
(* i (factorial (sub1 i)))))))
There's no point in CPS'ing it explicitly since the compiler is pretty
much guarranteed to spit out faster code if we don't. (This applies
to this code only. For more complicated code, CPS can bring a
performance win in some implementations.)
|> As you can see, a tail recursive nested function looks quite a bit
|> different from, say a `for' loop in C. But in fact, a `for' loop in C
|> is just another kind of notation for the same idea. Which brings me
|> to the third example of factorial in Scheme.
If you want for, use the standard macro do:
(define fact
(lambda (i)
(do ([i i (sub1 i)]
[acc 1 (* i acc)])
((nonpositive? i) acc))))
If you must have for, write a macro. Either express for in terms of do
or express it directly.
|> I've mentioned that the GEL project will produce a C-like syntax for
|> Scheme. I have a prototype of this syntax, and as it turns out, my
|> test suite contains an implementation of factorial. Personally, i
|> think this is slightly cleaner than both the C and Perl verions
|>
|> /* warning -- doesn't implement quite the same
|> * function as tchrist's examples, but it's close.
|> */
|> define fact(x)
|> {
|> var total;
|> for (total = 1; x; x = x - 1)
|> total = total * x;
|> return total;
|> }
This is not only a syntax change, but also a semantic change. None
of the previously written Scheme versions used assignment. Perhaps
one could write
define fact(x)
{
if (x < 1)
return 1;
else return x * fact(x - 1);
}
Hmm. On the other hand, this is ambiguous. Is that
x * (fact (x-1))
or
(x * fact)(x-1)
?
All of a sudden you have precedence issues. Yuck.
Of course, this eliminates the explicit iteration. Well, hopefully a
Schemey macro system will be provided (no #defines in any GEL I'll
use!); then we can write:
define fact(x)
{
do (total=1, i=x;
i;
total <- total * i, i <- i-1;
return total)
}
And with a good do macro, get out a tail-recursive loop with no
assignments.
|> For the code above, I get the translation:
|>
|> (define (fact x)
|> (let* ((total #f))
|> (let ((break (lambda (return) total)))
|> (begin
|> (set! total 1)
|> (letrec ((continue
|> (lambda (return)
|> (if (ctax:test x)
|> (begin
|> (set! total (ctax:times total x))
|> (continue (set! x (ctax:minus x 1))))
|> (break return)))))
|> (continue #f))))))
|>
|> This is pretty close to what a hacker who likes scheme syntax would
|> have written in the first place. Probably a scheme hacker wouldn't
|> have modifed TOTAL by side effects, and would have added an
|> extra parameter to the loop.
What Scheme hackers do you know that you write a monstrosity like this?
Even most C code is better!
Why does continue take an argument?
Why is total being declared without a value?
(Take a hint from C++ in this regard: for (var total = 1 ...) ...;)
Sigh.
David