Factor[ial] 101

If you're starting Factor, or any other stack-based language, you'll be a little confused about how the dataflow works. A good first exercise, which probably every successful Factor programmer has done at least once, is a word to calculate the factorial of a number. If you haven't done that yet, I strongly recommend that you do, in any way you feel like, implement it. Afterwards, you can continue reading this blog post. If you've already implemented factorial before, skip down past the second section to the third. In case you forgot, the algorithm for calculating factorial can be described as:

0! = 1
(n+1)! = (n!)(n+1)

It is only defined on nonnegative integers, and it's OK if your implementation has weird behavior, such as infinite recursion, for input outside of this domain. (Mine does too.)

---

Chances are, you wrote something like this:

: factorial ( n -- n! )
    dup zero? [ drop 1 ] [ dup 1- factorial * ] if ;

If you didn't, that's OK, because I'm going to explain this in excruciating detail. Hopefully, this will serve as a good introduction to non-Factorers or beginning Factorers. It should be readable even if you're not running Factor, but you might find it easier if you open up a listener to play around with at the same time.

So, let's start at the beginning. The colon : indicates the start of a word (this is the Factor term for a function), which is called factorial. After that, the stack comment ( n -- n! ) describes the stack effect of the code. Informally, the stack comment here says that factorial takes n off the stack and pushes n! on. For example, if the stack consists of 3 6 3 1 5, then after invoking factorial, the stack will be 3 6 3 1 120. (The stack here is written bottom to top, left to right.)

Now let's look at the actual code. The implementation of the factorial word is everything after the stack comment and before the semicolon ;, which terminates the definition. So the definition is dup zero? [ drop 1 ] [ dup 1- factorial * ] if. I'll go through this word by word. dup is a so-called "stack shuffler" whose only purpose is to manipulate the data stack. This word duplicates the top item on the stack, so there are two copies of it. (Note that it doesn't actually copy the datum, it just copies a reference to it, except for the few objects that are stored on the stack by value.) So if the stack is 1 2 3, then after executing the dup word, the stack is 1 2 3 3. Other stack shufflers include swap, drop, nip, tuck, 2dup and over. These can be found in Factor's built-in documentation system. In general, stack shufflers, like other words, only deal with the top few items on the stack. Underneath what is known to be on the stack, words by convention leave the stack as it is.

The second word in the definition of factorial is zero?. Looking at that word's definition using \ zero? see, we can see that its stack effect is ( x -- ? ). In informal notation, ? in a stack effect means that that item is a boolean, either t or f. The fact that the word zero? returns a boolean is also indicated by the fact that the name ends with a question mark. (Note: this convention only applies when the word returns a single value. When it returns multiple values, one of which is a boolean, the question mark precedes the word, as in ?head.) So, the word zero? takes the object on the top of the stack and returns a boolean indicating whether or not that value is zero.

Let's look at what we have so far: dup zero?. Applied to a few inputs, here's what it yields:

1 2 3 dup zero? ==>  1 2 3 f
0 dup zero? ==> 0 t
dup zero ==> Datastack underflow error

The last error happened because there wasn't enough on the stack to proceed. It was triggered by dup, which expects at least one item on the stack. Most stack underflow errors can be detected by the compiler beforehand.

As you might have guessed, the purpose of the dup before the zero? was so that we could save the value of the number and use it later, while also using it for the purpose of testing its zero-ness. Now, we'll enter a conditional, dependent on whether that value was zero. Following the code we've analyzed are two quotations enclosed in square brackets. These are like code blocks or anonymous functions in other programming languages, but at the same time, they can function as sequences. In their literal form, they are simply pushed onto the stack like other data literals. After these blocks is if, forming a conditional. if works like this. First, the top three items on the stack are popped. If former third-from-the-top item on the stack is f, the top quotation is executed. Otherwise, the second-from-the-top quotation is executed. I've written extensively about conditionals in Factor in a previous blog post.

So we still have to look at the code within the quotations. The first branch, [ drop 1 ] is executed when the condition is true, that is, when the input to factorial is zero. That branch drops the item on the top of the stack (the original input) and pushes 1. So, in total, 0 factorial returns 1.

The second branch, [ dup 1- factorial * ] is a bit more complicated. First, the item on the top of the stack is duplicated, and 1 is subtracted from the result. So, if the stack before that operation was 1, then the stack afterwards should be 1 0. After that, factorial is called recursively. This should only affect the top of the stack. The stack now is 1 1. The word * takes two numbers off the top of the stack and pushes their product. So, the stack result of the first quotation is 1.

I'm reading The Art of Computer Programming right now, so in his style, I'll announce this: Excercise 1 proves this code correct.

---

Now here's a funny piece of code which does the same thing:

: factorial ( n -- n! )
    1 [ 1+ * ] reduce ;

Exercise 2 explains this code and proves it correct.

---

1. [HM50] Prove the first Factor code listing a correct implementation of factorial.

2. [HM50] (a) Explain the workings of the second code listing. (b) Prove the second code listing a correct implementation of factorial.

(In case you're wondering why these exercises are rated so difficult, you should know that nobody's ever formally described the semantics of Factor, and that is a prerequisite to a working proof of the efficacy of any algorithm implementation. No, you can't look in the back of the book to find the answer.)

---

OK, OK, I'll give an answer to exercise 2(a), since it may be a bit confusing to those unacquainted with some of the more esoteric features of Factor. In Factor, all nonnegative integers are sequences. The length of integer sequences is equal to the integer itself, and indexing an integer sequence is equal to that index. In other words, an integer n represents the range of integers from 0 to n-1, inclusive. So, to get factorial, all we need to do is add 1 to each of these, and find the product of the whole thing. A direct implementation of that would be

: factorial ( n -- n! )
    [ 1+ ] map product ;

map is a combinator (word which takes a quotation as an argument) which, like Common Lisp's mapcar, applies a function to each element of a sequence (or, in Lisp, a list) and returns the resulting sequence (or list). And product simply calculates the product of all the elements of a sequence. This implementation works as expected. However, it's a little bit more efficient if we don't calculate the whole new sequence, with one added to each element, and instead incrementally calculate the product as we range through the numbers 0 to n-1. To do that, we can use another combinator called reduce. reduce takes a sequence (such as an integer) and a start value (such as 1). Then, reduce executes the quotation with each element of the sequence on the top of the stack, and the accumulated value beneath the top. The quotation returns a new accumulated value, which is ultimately the return value of the reduce. So, here, the quotation [ 1+ * ] adds one to the sequence element and then multiplies it into the accumulator.

Now, I'll expect the answers to the other two exercises to be on my desk Monday morning. You are dismissed.