Tchrist writes:
However, I think you'll find that if someone understand this:
long fact(long i) {
if (i < 1) {
return 1;
} else {
return i * fact(i - 1);
}
}
That this isn't very far removed from it:
sub fact {
my $n = shift;
if ($n < 1) {
return 1;
} else {
return $n * fact($n - 1);
}
}
After this syntactic comparison, tchrist goes on to post some scheme
code (but not code that computes factorial). I guess its only
fair if i post some scheme code. I'm going to give three scheme
versions. The first mimics the C version. The second is how a
scheme hacker would normally write fact. The third is the most interesting
in this context -- I saved the best for last.
First, there is the mimicy version. I think it looks a lot like
the C version, except puffier.
(define (fact i) ; warning -- untested code
(if (< i 1)
1
(* i (fact (+ -1 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))
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.
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;
}
I have a 700 line yacc grammar and a 500 line scheme program that
translate definitions in the c-like syntax. In this case, the
translator produces a tail recursive loop comperable to what a scheme
programmer would have written in the first place. This isn't Rocket
Science -- many people have implemented similar syntaxes before -- but
i hope it will help to make people more comfortable programming with
the Gnu extension language.
-t
p.s. for schemeheads
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.
-- ----If you would like to volunteer to help with the GNU extension language project, please write to lord@gnu.ai.mit.edu.