Is infix lambda hard to read?

I've been using infix lambda in pseudocode for a couple of years, with mixed results. I find it very easy to write, because it's so terse, and I tend to use it for any one-argument function I can't get by partial application and simple combinators. But I find it surprisingly hard to read.

The symptom is that I mistake the parameter list for an expression. For example, in a definition like this...

gravitate bodies = map (b → accelerate b (field b bodies)) bodies

...I sometimes read the first b as a free variable, and spend a confused moment trying to figure out where it's bound, before I notice the → operator and realize that I'm looking at the binding occurrence. This mistake is especially easy to make in larger definitions, where it's not obvious the b doesn't refer to some local variable I've forgotten about — and where it takes longer to see that no such variable exists.

I think the underlying problem is that the parameter list is the left argument of →, so when I read an expression left-to-right, I encounter it before the operator. Since I haven't yet seen any hint that it's not an expression, I try to read it as one, and fail. Ordinary lambda, in constrast, announces its specialness first, so I'm not surprised by the parameter list.

If this really is the problem, then it should also affect other operators whose left arguments aren't expressions. But there aren't many. The only one I can think of is the ubiquitous (in my pseudocode, at least) infix define, =, which may be less confusing because it's used in distinctive contexts (at top level or in a progn). There are a few common operators whose right arguments are special (e.g. . for field access), but it seems few infix operators have left arguments that aren't expressions.

What do C♯ users (at least those few who use lambda much) think? Do you have trouble reading =>?

Function of the day: sum

Most folds are sums — either (fold + 0 ...) or (fold + 0 (map f ...)). In math and pseudocode, they're written as Σ or sum, not as folds. So programming languages should support writing them the same way. In Clojure:

(defn sum "Add the elements of a collection, or some function of them."
  ([xs] (reduce + xs))
  ([f xs] (reduce (fn [a x] (+ a (f x))) 0 xs)))

This is one of those trivial conveniences that I use with surprising frequency — more than many more familiar operations. Counts from a 286-line Clojure program:

CountOperation
11sum
11#(...) (op or abbreviated λ)
5format (I/O is everywhere)
4fn (λ)
4count
3map
3reduce (counting the two to implement sum)
2filter

sum may be trivial, but at least in this program, it's more common than map, reduce, and filter combined. Isn't that enough to deserve a place in the library?

(For performance reasons, Clojure's + isn't an ordinary generic function and thus can't be taught to work on vectors, so sum doesn't either. This program does vector arithmetic, so I had to duplicate various arithmetic operations for vectors, so three of these uses of sum were actually of a separate vsum. But this distinction would not be necessary in an ideal language.)

Pipe for functions

One of the minor annoyances of prefix notation for function call is that it gets the order of operations backwards. When you compose several functions into an expression, you generally have to write the last step first:

(handle-message (decrypt (receive socket) key))

If you explained this to a computer the same way you explain it to a human, you'd probably write the steps in the order they're performed. If you're used to Unix pipelines, you might write it like this:

receive socket | decrypt _ key | handle-message

In a language with user-defined infix operators, it's easy to support exactly this. You can define a | operator which simply applies its right argument to its left — the same as Haskell's $, but with the arguments reversed. It looks and feels very like the Unix |: it connects the output of one expression to the input of the next. The channels used are return value and arguments rather than stdout and stdin, but the effect is the same.

I can't remember where (edit 16 Feb 2011: here, at least, and also |> in F#), but I think I've heard this operator suggested before for Haskell — presumably with a different name, since | is taken. Ignoring that inconvenient detail, its Haskell definition is simple:

infixl 0 |
(|) :: a → (a → b) → b
x | f = f x
-- Or, to make the similarity to $ clearer:
(|) = flip ($)

Like $, this is a contemptibly trivial operator. All it does is apply one argument to the other, which doesn't sound like it could possibly be worth spending an infix operator on. But I find myself using it constantly in pseudocode, because it lets me write operations in the right order. It doesn't make code shorter, but it significantly reduces the distance between the code I write and the representation in my head. That's important enough to be worth a one-character infix operator.

Like any high-order operator, | is much more useful when you have a terse way to write simple functions. Usually this means partial application, either in the form of currying, or an explicit partial application operator, or op, or implicit op (as in the example above). Combinators are nice by themselves, but they need partial application to be really useful.

Shorter words for “expression”

Some common terms for programming languages vary widely in meaning, but at least one is understood across languages: virtually everyone agrees on “expression”.

Well, except in those communities that use the concept most. They have their own words for it. In Lisp, an expression is called a “form”; in the ML and statically-typed-functional-languages community, it's called a “term”. And let's not forget graph reduction, where it's called a “redex” (supposedly for “reducible expression”, although the “reducible” part is no longer relevant to the meaning). These terms all mean exactly the same thing, and all of the communities accept “expression” as a synonym, but they also have their own equivalents.

Private terms for common concepts usually exist to show group affiliation. That may be contributing here, but I think the main reason for replacing “expression” is brevity. It's difficult to write about programming languages (especially expression languages) without mentioning expressions exceedingly often, so there's a strong incentive to use a shorter word. “Expression” has three syllables and a difficult four-consonant cluster; “form” and “term” are easy one-syllable words. “Redex” is two syllables, which may explain why it's less popular than the other two.

None of the replacements are particularly transparent, but that doesn't matter much for such common words. (“Expression” doesn't make much sense either.) Apparently terms for such basic concepts needn't be obvious, as long as they're short.

Brevity may also be one of the reasons “thread” has largely replaced “process”. (The other reason is, of course, that popular OSes unify processes with other things like address spaces and security domains, and the word “process” has come to refer to the whole bundle rather than the original concept.)

Bursts of productivity are fun

I spent most of today slacking off at work, reading about astrophysics and paying only casual attention to actual work. But an hour or two past noon, a bug caught my eye — a simple mathematical matter of correctness, which I could feel good about fixing. It proved harder than I expected, and I soon filled a whiteboard with data structure diagrams and equations. After some frustration, I noticed other people leaving, and looked at a clock, which was obviously broken, since it said 5:00.

I turned back to the whiteboard, and saw that my previous approach was unnecessarily complicated. So I fixed that bug, and found another, and fixed it, and after fixing six bugs in a little over an hour, I lost interest and went back to reading.

Sound familiar? Most programmers (and most creative workers of any kind) are accustomed to seeing their productivity vary wildly over time. On one day you get nothing done and feel guilty for not trying very hard; the next day is the same except for a brief burst in which you seemingly do a week's work in two hours. The Internet is full of programmers lamenting this situation, and wishing they could have these bursts every day.

I suspect this unwelcome variation accounts for part of the fun of programming. The periods of apathy and frustration lower your expectations, so when the bursts of activity arrive, they seem far beyond your normal ability — a contrast that can make even the most boring problems exiting. I noticed this effect today: that one hour when everything went right, and everything worked on the first try, would not have been so impressive if it hadn't been preceded by a few hours of frustration. If you were modestly productive all the time, you might get the same total work done, but it would be more predictable, and you would have fewer moments of unexpected triumph. Mightn't that be less fun?

Exception logic

Programming generally requires Boolean logic, so every practical language supports it with if, and, not, and other such operators. In almost all languages, these operators receive their Boolean inputs as ordinary values. (if (and a b) c d) evaluates a, and the resulting value determines whether to evaluate b, and so on. This is all so obvious and familiar that it's hard to imagine it could be otherwise.

Icon does it differently. Icon expressions (and functions) have two continuations: they can succeed and produce a value, just like expressions in a thousand other languages, or they can fail. This feature has many uses, and one of them is to represent Booleans: Icon encodes them not in values but in success or failure. Its if operator doesn't look at the value returned by the conditional expression — it only looks at whether it succeeds or fails. Similarly, its or operator (called |) evaluates its second argument only if the first fails. In Icon, Booleans aren't values.

Few languages have Icon's success/failure semantics, but it doesn't take exotic semantics to encode Booleans this way. Any language with exceptions can do something similar: returning normally means true, and throwing an exception means false. Most languages with good support for exceptions use them extensively in their standard libraries, so functions that return exception Booleans are already common.

It's not often recognized, though, that one can define operators on these Booleans. I briefly thought Perl 6 did, based on a misunderstanding of its andthen and orelse operators, but it turns out they operate on defined vs. undefined values, not exceptions. (Perl, true to form, has several ways to represent booleans, one of which is defined/undefined.) However, there are a few exception-Boolean operators in existing languages, even if they're not usually described that way:

  • Ordinary progn/begin is the exception equivalent of and: it evaluates each subform only if the previous ones returned normally.
  • Many languages have an (assert expression) operator, which converts a value Boolean into a exception Boolean.
  • Common Lisp's (ignore-errors expression t) converts an exception Boolean into a value Boolean, returning nil on error and t otherwise. (However, it only handles errors, not all serious-conditions.)
  • Some test frameworks have a (must-fail expression) form, which throws an exception iff the expression doesn't. This is the exception-Boolean equivalent of not.

Given macros and an exception-handling construct, you can easily build others, such as or and if:

(defmacro succeeds (form)
  "Convert an exception Boolean to a value Boolean: return
true if this form returns normally, or false if it signals a
SERIOUS-CONDITION."
  `(handler-case (progn ,form t)
     (serious-condition () nil)))

(defmacro eif (test then &optional else)
  "Exception IF: THEN if TEST returns normally, otherwise ELSE."
  `(if (succeeds ,test)
     ,then
     ,else))

(defmacro eor (&rest forms)
  "Like OR, but treating normal return as true and
SERIOUS-CONDITION as false. Perhaps surprisingly, (EOR)
signals an exception, since that's its identity."
  (cond ((null forms) `(error "No alternatives in EOR."))
 ((null (cdr forms)) (car forms))
 (t `(handler-case ,(car forms)
       (serious-condition () (eor ,@(cdr forms)))))))

These operators may be a fun exercise, but are they of any practical use?

There is a tension in the design of functions that might fail in normal operation — those that depend on the cooperation of the environment, like opening a file or making a TCP connection, and even those that return something that may or may not exist, like hashtable lookup. Such functions face an awkward choice between indicating failure by their return value (e.g. returning nil, or a Maybe) or throwing an exception. A special return value is most convenient for callers who want to handle failure, because they can easily detect it with ordinary operators. But it often forces those who can't handle the failure to explicitly check for it anyway. An exception, on the other hand, is perfect for callers who can't handle failure and just want it to propagate up automatically, but awkward for those who can handle it, since in most languages it's much easier to check for nil than to catch an exception. So functions are forced to choose how they report failure based on guesses about how often their callers will want to handle it.

Exception logic might ameliorate this. If you can handle exceptions as easily as return values, then exceptions are no longer at an expressive disadvantage. This means you can use them more consistently: virtually any function that might fail can indicate it with an exception — even the commonly tentative ones like dictionary lookup. So exception operators are interesting not for their own sake, but because they may allow other parts of a language to be more consistent.

Like all error handling features, this is hard to experiment with in pseudocode, because it's so easy to ignore error behaviour. It's also hard to experiment with in a real language, because its value depends on changing so many library functions. So I wouldn't be surprised if I've overlooked some common case where exceptions are still inconvenient. But this sort of thing is worth looking into, because it could make libraries simpler and more consistent.

Haskell and syntactic complexity

Why isn't if a function in Haskell?

In most languages, if is a special form (or local equivalent). That's because if is lazy in its last two arguments, so it can't be a function in an eager language. But Haskell has no trouble with laziness; if can trivially be a function, with no need for special semantics, let alone syntax. There's even a page on the Haskell Wiki advocating switching to the simple functional if.

All this must have been obvious to the designers of Haskell. So why did they choose the Algolesque if ... then ... else ... syntax instead?

Of course this question has come up before. Paul Hudak, one of the designers, explains:

Dan Doel's answer is closest to the truth:
I imagine the answer is that having the syntax for it looks nicer/is clearer. "if a b c" could be more cryptic than "if a then b else c" for some values of a, b and c.

except that there was also the simple desire to conform to convention here (I don't recall fewer parentheses being a reason for the choice). In considering the alternative, I remember the function "cond" being proposed instead of "if", in deference to Scheme and to avoid confusion with people's expectations regarding "if".

To my eye, if a then b else c improves neither clarity nor familiarity, but evidently the Haskell designers thought otherwise. More interestingly, they didn't think the added syntactic complexity was much of a problem. How can this be? Doesn't Haskell culture value simplicity?

Yes, but not so much simplicity of syntax. I'm misled here by a superficial resemblance between the cultures of Haskell and Lisp. Both cultures are obsessed with mechanically processing code, and therefore want the language core to be as simple as possible. Since a minimal core is impractical to program in, both expect a larger, more useful language to be defined by translation to the core, so its complexity can be mechanically eliminated. And both consider the representation of code as text to be separate, at least in principle, from the core. So at first glance, it seems as if they should have the same attitude to syntactic complexity.

But they treat it quite differently. Lisp's culture considers syntax unimportant, and therefore tries to make it as simple and transparent as possible, so it won't prevent humans from seeing through it — because code is much more interesting than its textual representation. But Haskell's culture considers syntax safely separate from the language core, and is therefore willing to tolerate complexity in it. Since it goes away without inflicting any complexity on the core, why shouldn't it include whatever features are convenient?

This approach has given Haskell one of the prettiest syntaxes in the world, so I can't say it's wrong. It is uncomfortable, though, for a Lisper to see a culture which draws wildly different conclusions from seemingly similar premises. Maybe this is explained by modest differences in degree: Haskell values textual beauty a bit more than Lisp, and code-processing a bit less. Is that enough to explain the difference? I don't know. I don't understand.