Tuesday, January 29, 2008

Scheme For Enlightenment Part Six - Recursive Language Comparison

C is a procedural language but it can also do recursion. And, it's call stack is deeper than Guile's. Isn't that odd? Maybe not. Guile is written in C. At least under Linux, sstk(2) is not implemented, so the stack size can't be changed. So Guile is limited in the same way that C is. C's stack is likely more efficiently represented, so more can go in the same sized area, and therefore feels larger. Here's the factorial in C, recursively.

int factorial(int x) {
if (x == 0) {
return 1;
} else {
return x * factorial(x - 1);

It hasn't improved. It's still limited to x = 13. But try this rather spooky equivalent. Is it starting to look like Scheme?

int factorial(int x) { return (x == 0) ? 1 : x * factorial(x - 1); }

If unsigned 64 bit integers can be used, then factorial(20) can be computed. Or C's double (floating point) type can be easily used. That gives you approximate answers (13 digits) and works up to factorial(170). It has the side effect that it knows when it overflows in the answer, reporting inf.

But let's say we really want exact large integers in C, as we get from Scheme. What do we do? The answer is that we link with an arbitrary precision number library, change the data type to the library's type, and use the library to do the multiplies. The structure would remain, and it would still be fast. After all, Guile's big numbers are written in, uhm, C. And, Guile is open source. At worst, one could use the Guile implementation of big numbers, and the two languages would end in a draw, more or less. It is much more likely is that a convenient package exists that doesn't use garbage collection, and is faster than Guile.

So, is the factorial example a good example? That is, is it fair to the languages involved? Perhaps. While short, it's complicated enough that there is more than one way to write it in each language. It brings up issues that each language enjoys. What's not to like?

Back to enlightenment. The question is, does one have to cope with recursion in order to gain any enlightenment from Scheme? Unfortunately the answer seems to be yes. Functional programming and other styles have their basis here. I'm not out to replace my procedural style with something new. I'm out to add flavor to the stew. However, it's clearly not gonna happen without some kicking and screaming.

No comments: