One of the strengths of functional (i.e. applicative) programming style is that it makes dataflow obvious. Usually this is a good thing, but there are many cases where parts of a program's dataflow are best kept hidden. For instance, some functions return a value (or several) not because their caller is ever interested in it, but so the caller can pass it to somewhere else that actually is interested. This often happens when you're keeping some sort of profile information. For example, suppose you're playing with the very recursive Sudan function:
(defun sudan (n x y) "The first known function that is recursive but not primitive recursive." (cond ((zerop n) (+ x y)) ((zerop y) x) (t (let ((s (sudan n x (1- y)))) (sudan (1- n) s (+ s y))))))CL-USER>(sudan 1 2 3)27 CL-USER>(sudan 3 2 1)Control stack exhausted (no more space for function call frames). [Condition of type SB-KERNEL::CONTROL-STACK-EXHAUSTED] CL-USER>(sudan 2 2 1)27 CL-USER>(sudan 2 2 2)15569256417 CL-USER>(sudan 2 2 3)Control stack exhausted (no more space for function call frames). [Condition of type SB-KERNEL::CONTROL-STACK-EXHAUSTED] CL-USER>(sudan 2 3 2)5742397643169488579854258
It returns instantly for very small arguments, and overflows for slightly larger ones. What's going on?
The obvious way to find out is to instrument it to count how many times it was called. (Yes, I know there are tools for this, but this is an example of a general problem, of which most cases don't have tool support.) The proper, functional way is to return the number of calls as an additional value:
(defun sudan/count (n x y) "The first known function that is recursive but not primitive recursive. Returns two values: S_n(x,y), and the number of calls required to compute it." (cond ((zerop n) (values (+ x y) 1)) ((zerop y) (values x 1)) (t (multiple-value-bind (s calls) (sudan/count n x (1- y)) (multiple-value-bind (s2 calls2) (sudan/count (1- n) s (+ s y)) (values s2 (+ calls calls2 1)))))))CL-USER>(sudan3 2 2 2)15569256417 69 CL-USER>(sudan/count 2 3 2)5742397643169488579854258 165
Hmm. That's not so bad. The number of calls is not so bad, I mean. The code, though, is a mess. The relationship of the recursive calls is obscured with multiple-value-binds, and every return site has to be wrapped with values, and if you miss one the function won't work. This is not a good way to instrument a function. More precisely, this is not a good way to pass profiling data up the call tree. But is there a better way?
If I were in a stateful mood, I would have done it this way:
(defun sudan/count2 (n x y)
"The first known function that is recursive but not primitive recursive.
Returns two values: S_n(x,y), and the number of calls required to compute it."
(let ((calls 0))
(labels ((sudan (n x y)
(incf calls)
(cond ((zerop n) (+ x y))
((zerop y) x)
(t (let ((s (sudan n x (1- y))))
(sudan (1- n) s (+ s y)))))))
(values (sudan n x y) calls))))That's one line longer than the multivalue version, but shorter in characters or nodes - and much easier to maintain, because the profiling is not tangled through the rest of the function. It also scales much better, because it doesn't require such pervasive changes. The trouble with state - well, one of the troubles with state - is that it hides dataflow, but in this case hiding dataflow is exactly what we want.
By the way, I had a predictable bug in the first version of sudan/count: when I renamed the function, I forgot to change the recursive calls, so it called the old version. Recursing by name is redundant in a bad way - it depends on the function's name, so merely renaming the function changes its behaviour! This wouldn't have happened in Forth, which has a recurse operation that doesn't depend on the function's name. Anonymous recursion is inflexible, of course, but there are many simple cases like this, where it more closely expresses what you mean, and avoids a possible bug.
Speaking of possible bugs: If you noticed the evaluation order dependency in (values (sudan n x y) calls), good for you. I didn't.