When the functional way is much worse

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.

How toy problems are different

A lot of simple text-processing problems involve operating on the words of the input. Norvig's spellchecker, for instance, begins by extracting the words:

def words(text): return re.findall('[a-z]+', text.lower())

So do some of the old Shootout problems (though none of the currently active ones, and they don't keep old ones around, so if you want to see an example you'll have to use the WayBackMachine). This sets my library-senses tingling. If so many programs need to split text into words, shouldn't words be in the standard library?

There are two problems here. The lesser is that the definition of "word" varies a bit - sometimes it's defined by alphanumeric characters, sometimes by whitespace. This isn't a showstopper, because some reasonable definition will probably work for a large fraction of the potential uses. The greater problem is that splitting things into words is much less common in real programs than in toy examples. Words are like Fibonacci numbers: they're familiar and easy to ask for, so they occur unusually often in made-up requirements. Neither is common in real programs - probably not enough so to warrant including them in a language's library.

This is one of the pitfalls of testing a language against toy problems. Unlike real problems, they're strongly biased toward simplicity of requirements, which affects what they demand from a language. Real programs tend to spend a lot of code on I/O and error handling, neither of which turns up much in toy problems. Is it a coincidence that these two areas are awkward to express in most languages?

Where have all the pointers gone?

Dynamically typed languages represent almost everything as tagged pointers, which sounds very inefficient: doesn't that waste a lot of space? And doesn't 64-bit addressing make this waste much, much worse?

I used to take this seriously. But one day a few years ago I was playing with Squeak, and wondering why its images (savable worlds) were so large - 10 MB, when the original Smalltalk ran in 64 KB. I stumbled across allObjectsDo:, which iterates across all objects in the heap, so I wrote a heap profiler to find out where the space was going. Once I finished it, I discovered Squeak came with a much better one, so I used that instead. Here are all the classes that take more than 1% of the space:

Class	Purpose	# Instances	Space	%
CompiledMethod	bytecode	33951	2.0 MB	20%
Bitmap	graphics	1208	1.8 MB	17%
String	text	28743	1.7 MB	16%
Array	various	30263	1.3 MB	12%
ByteArray	various	379	800 KB	8%
Symbol	selectors mostly	27786	550 KB	5%
MethodDictionary	method dispatch	3092	320 KB	3%
WeakArray	symbol table mostly	15	230 KB	2.2%
Point	GUI	17193	200 KB	1.9%
MorphExtension	GUI	3344	170 KB	1.6%
Color	GUI	8323	163 KB	1.6%
Association	hashtables	10761	126 KB	1.2%
Float	boxed float	9732	114 KB	1.1%
All others		1.1 MB	10%
Classes without pointers		>6.6 MB	>65%
Total		10.2 MB	100%

This shows why tagged pointers are not a big space problem: there just aren't that many of them. Five of the top six classes, accounting for two thirds of the space, are binary data. (The exception is Array.) Dynamically typed languages, it turns out, don't encode most data as tagged pointers.

Well, of course. What do you do with a large data structure? You find a more compact representation. Often that means replacing low-entropy pointers with high-entropy bytes. That's what happened to all of those five non-pointer classes. Dynamic typing makes no difference: as long as you have some sort of byte arrays (in Smalltalk, Class»variableByteSubclass:), you can do this in dynamically typed languages the same way you do it in statically typed ones. If tagged pointers are wasteful, the waste is in boxing small objects like floats, not in the presence of pointers.

Of course this is only one image, and an odd one at that - instead of application-specific data, it's dominated by library code. The reason Squeak is so much bigger than the old Smalltalks is that it has a much bigger standard library - and no autoloading, so it's all in the image all the time. Code accounts for at least 30% of the space: CompiledMethod, Symbol, MethodDictionary, and WeakArray (most of which is the symbol table). This 3 MB would be insignificant in a bigger image, but otherwise I expect larger applications to have space profiles much like Squeak's. Most classes are made of pointers, but most of the space goes on the few that aren't.

A hazard of precedence

I encountered a bug recently from a precedence mistake. Someone had written if (a = b == c), intending if ((a = b) == c) - but in C == has higher precedence than =, so that wasn't how the parser saw it. The typechecker didn't object, because the result type of == in C is int, so all was apparently well. None of the humans noticed either, perhaps because b was a large expression, so the two infix operators were far apart.

Operator precedence saves lots of parentheses, but it does occasionally lead to bugs. It's one of the class of language features that work by resolving ambiguity, and these have a common hazard: when you don't notice the ambiguity, it will still be resolved, and not necessarily as you intend.

Short names are addictive

This morning I tried to do this in Common Lisp:

(defun neighbors (x y)
  (mapcar (fn (dx dy) (vector (+ x dx) (+ y dy)))
          '(-1 0 1 0)
          '(0 1 0 -1)))

Naturally, SBCL spit out half a page of warnings, starting with this:

;     (+ X DX)
; 
; caught WARNING:
;   undefined variable: DX

;     (DX DY)
; 
; caught STYLE-WARNING:
;   undefined function: DX
; 
; caught WARNING:
;   undefined variable: DY

It took me an embarassingly long time to figure out why. I have become so used to fn being lambda — in Arc, Clojure, and any number of other new Lisps, including my own — that I didn't notice anything out of the ordinary.

I did at least remember that CL can't add vectors, which was how I wanted to write it. This is a hazard of learning new languages, and of designing them: improvements, even such minor ones as shorter names, are addictive. They're fun at first, but soon you become dependent on them, and the old ways seem unbearably clunky, if you can even remember them.

The value of extensible format strings

Common Lisp's version of printf is the famously overpowered format. In addition to everything printf does, it has conditionals, iteration, recursion, case-folding, tabulation and justification, pretty-printing, English plurals and number names (cardinal and ordinal), and two kinds of Roman numerals. Surprisingly, in a language where almost everything is user-accessible, most of these features are not available separately, only through format. The complexity is such that there's a compiler to make format strings execute faster. Sadly (or not, depending on your perspective) it's not Turing-complete, but that's only because it has no way to store information.

Of course there's a way around that. None of format's features is quite as overpowered as ~/, which calls arbitrary functions: (format stream "~/package:function/" x) does (package:function stream x nil nil). (The two nils are for some other features not used in this case. Yes, there are more. Are you surprised? And yes, in practice the explicit package name is required.) User extensibility is a good principle, but this seems silly. Why would you ever want to call a function through format instead of doing so directly?

Well, the other day I had to generate some XML in C, and the obvious way was with printf:

fprintf(somefile, "<element attr=\"%s\" />", somestring);

But there might be XML-meaningful characters in the string, and I didn't want to mess around with fancy XML-generation libraries. So I had to either escape the string before printing...

char buffer[BIG_ENOUGH]; /* yeah, right */
escape_xml(buffer, BIG_ENOUGH, somestring);
fprintf(somefile, "<element attr=\"%s\" />", buffer);

...or give up on printf, which was what I ended up doing:

fprintf(somefile, "<element attr=\"");
print_xml_string(somefile, somestring);
fprintf(somefile, "\" />");

Either option destroys the clarity of the printf. What I really wanted was a custom printf operation, like this:

fprintf(somefile, "<element attr=\"%/escape_xml/\" />", somestring);

That's exactly what format's ~/ command does:

(format somefile "<element attr=\"~/xml:escape/\" />" somestring)

I guess it's not so silly after all. It is verbose (imagine repeating ~/xml:escape/ for each of a dozen attributes), but that's fixable. If there were an interface for defining new format commands, then any frequently used ~/ function could be given a one-character form, and all would be well, except possibly for readability. (Although in this case all of the obvious characters x e & < s are already taken.) Lisp being Lisp, you generally can get at the implementation's way of defining format commands, e.g. sb!format::def-format-directive, but depending on implementation internals is not usually a good idea. Exposing this interface would make format more malleable, like the rest of the language, and would also make its long feature list easier to swallow.

For new languages, though, I think I prefer string interpolation, which avoids the issue entirely:

(put somefile "<element attr=\"$(xml:escape somestring)\" />")

It would also be nice to have a choice of string delimiters, so the quotemarks don't require escaping. But that's a different, less interesting issue.

Abstract algebra with imperfect models

One more post before the end of the year:

Haskell users tend to be mathematically inclined, so it's no surprise that they should notice a mathematical application of typeclasses: they can represent abstract algebraic structures. You only get one model of the algebra structure per type (potentially annoying for common algebras structures like groups), but where applicable this makes a great (for some values of "great") way to show off your mathematical prowess. Indeed, some of the standard typeclasses are intended as abstract algebras algebraic structures: Monad and MonadPlus, at least.

There are probably quite a few Haskellers who have not only noticed this, but wished it were taken further. For instance, why isn't / defined like this?

(/) :: (Field a) => a -> a -> a

(Really mathematical Haskellers may also wish the return type was Maybe a.)

Isn't Num actually Ring, and Fractional Field?

Not quite. Integer is indeed a ring, but Int isn't because of overflow. Ratio is a field, but Float isn't, because of rounding. Abstract algebras Algebraic structures are useful only because it's possible to reason from their axioms and apply the conclusions to the models, and that doesn't work when the models don't actually satisfy those axioms. The reason Monad works is that its standard instances do correctly model it. The others are stuck with names less proudly abstract but less misleading (not to mention less opaque to non-mathematicians).

Of course, none of these models are really correct, because they all have the limitation of finite memory. But that's a less intrusive limitation than fixed-precision numbers. "Less intrusive" is a disappointingly vague description; I suspect the real difference is that finite memory afflicts virtually every operation in the language, while overflow and rounding are specific to certain types. So while assuming the monad laws work on lists, for example, will cause problems in some circumstances, it won't cause any more problems, because your programs would fail anyway in those cases. In contrast, it's pretty easy to write code that will work for any ring, but not for Int.