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.
Why do you call the evaluation order dependency a possible bug? Common Lisp has a specified evaluation order, after all.
ReplyDeleteThe possible bug was in my thinking, not in the code. Had this been in a language with unspecified order, or had the arguments been in the other order, it would have been a bug, but I didn't even notice the possibility. I think I saw the side effects as occurring within the definition of sudan, not at its call site.
ReplyDeleteSo much for my claim that the stateful version is easier to maintain.
In Haskell, there's a very elegant way to do this functionally. You use the "Writer" monad and the "Sum" monoid. It doesn't use state in the traditional sense. Here's how it looks. It's remarkably similar to the natural way to define the Sudan function in Haskell. Sorry I couldn't figure out how to format code snippets here, you'll have to guess what the indentation is supposed to look like.
ReplyDeletesudanc :: Int -> Integer -> Integer -> Writer (Sum Integer) Integer
sudanc 0 x y = Writer (x + y, Sum 1)
sudanc _ x 0 = Writer (x, Sum 1)
sudanc n x y = do
Writer ((), Sum 1)
s <- sudanc n x (y - 1)
sudanc (n - 1) s (s + y)
sudan_count :: Int -> Integer -> Integer -> (Integer, Integer)
sudan_count n x y =
let (r, Sum c) = runWriter $ sudanc n x y
in (r, c)
Maybe we should have "secondary return values", where (f (secondary x y)) = (f x), but (extract-secondary (secondary x y)) = (values x y). Note that extract-secondary changes the semantics of its argument; (let ((x (secondary 1 2))) (extract-secondary x)) wouldn't work, so we don't have weird 1-but-not-really values.
ReplyDelete(defun sudan/count3 (n x y)
"The first known function that is recursive but not primitive recursive."
(cond ((zerop n) (secondary (+ x y) 1))
((zerop y) (secondary x 1))
(t (multiple-value-bind (s calls)
(sudan/count3 n x (1- y))
(multiple-value-bind (s2 calls2)
(sudan/count3 (1- n) s (+ s y))
(secondary s2 (+ calls calls2 1)))))))
The last clause is still ugly, but (sudan/count3 n x y) = (sudan n x y), and (extract-secondary (sudan/count3 n x y) = (sudan/count{and 2} n x y).
On second thoughts the code is identical, so meh. We could have a macro that replaces recursive calls in a definition with a certain form?
SECONDARY is exactly Common Lisp's VALUES. :) But that only handles discarding extra values, not plumbing them in separately from the primary values, as the Writer/Sum solution does.
ReplyDeleteIt would be possible to address this with a variation of VALUES that preserved secondary values instead of discarding them:
(f (values* 1 2)) ==> (f 1) 2
...and that allowed specifying how to combine multiple secondary values:
(reducing-secondaries #'+
` (f (values* 1 2) (values* 4 8))
==> (f 1 4) (+ 2 8)
So SUDAN becomes something like:
(defun sudan/count4 (n x y)
` (reducing-secondaries #'+
` ` (values*
` ` ` (cond ((zerop n) (+ x y))
` ` ` ` ` ` ((zerop y) x)
` ` ` ` ` ` (t (let ((s (sudan n x (1- y))))
` ` ` ` ` ` ` ` (sudan (1- n) s (+ s y))))))
` ` ` 1)))
I don't know if that would have many other applications, though. And at least at first glance it's not easy to read.
I was looking back at the Steelman requirements (to which Ada was designed) and one of them is very interesting: it requires a distinction between functions and subroutines, and requires functions to be almost pure: in particular, they can update static variables, precisely for instrumentation purposes.
ReplyDeleteAda in fact doesn't impose any purity restrictions on functions, but what if a language did? Its functions would only be allowed to modify local variables through an ordinary assignment statement, and global variables through a special assignment statement whose RHS would be the only place such variables would be allowed in function code. Functions could then be compiled eagerly, but could also be compiled lazily with the special assignments serving as fences.
It's been pointed out to me that you can't determine lexically if a pure function calls a mostly-pure one (one that contains the special assignment). My reply is that it doesn't matter. Since the special assignments aren't part of the denotational semantics that captures the pure part of the language, all we need to guarantee is that a special assignment is performed iff the function it is lexically embedded in is called.
DeleteThis is another version of the insight that the classical compiler optimizations like splitting and merging work because they assume the code is locally lazy, and can't be performed around a call to an unknown function because the function might require strict semantics. In this view, though, there's no problem because you want to do instrumentation runs only if you actually call the function: their semantics is subordinated.