The Friday Fragment

It's Friday, and time again for a new Fragment: my weekly programming-related puzzle.

This Week's Fragment

With this week's fragment, we'll start a series of puzzles to code something in a specified language. The code itself won't be difficult, but it will highlight the unique benefits of a particular language (or, in some cases, recently-added features to a language). It's your chance to try out a new language or feature.

Will start by thinking inductively and recursively, and that's where functional languages like Lisp/Scheme shine. This is a "classic" exercise (meaning there are probably a million solutions posted on the web), but try it yourself before peeking. The problem is simple:

Code a factorial function (s-expression) in Lisp or Scheme. For example, (factorial 3) should evaluate to 6. Include unit test scaffolding code.

For extra credit, code a recursive factorial function in a more mainstream language (like C or Java) and compare the performance/results to Lisp when taking the factorial of a very large number. There are several free Lisp/Scheme implementations you can use; Dr. Scheme (PLT Scheme) is one good choice.

To “play along”, post the solution as a comment or send it via email. To avoid “spoilers”, simply don’t expand comments for this post.

Last Week's Fragment - Solution

Last week's fragment was sent in by Joel Odom:

Write C code or pseudo-code to swap the values of two integer (int) variables, a and b, without declaring or using any other variables. Do not use any syntactical language tricks that implicitly copy values out of a or b into other memory or registers. You can use C operators, control flow, and similar statements.

I was left to solve this one on my own, and sent Joel two solutions. For the first, I used the wonders of XOR. Among other things, XOR'ing something with a value twice gets the original value back: a feature used for simple bitmap animation, masking, encryption, etc. - and it's fast. For the second, I called a function, using the stack to push/pop one of the values. Joel approved the XOR approach, but said the function call was cheating since it allocated memory on the stack (good point). Here's the simple XOR solution; for the function call and scaffolding code, see comments to last week's post.

a=a^b; b=b^a; a=a^b;