Lambda the Ultimate

On the other hand, I can't think of any real-world scenarios where the most natural thing to do is recurse.

So, Brezhnev is coming to power, and Krushchev gives him two sealed letters. He says "Open them if you get in a tight spot." Everything is going well for a while, but Brezhnev eventually comes to a jam, so he opens the first letter. "Blame everything on your predecessor!" it says. He does, and he escapes his comeuppance by the skin of his teeth. His political gambits get more risky, however, and he soon finds himself in trouble again. "No sweat," he thinks. "Letter #2 will save me." So he eagerly opens up the second letter. It reads "Write two letters . . . "

:-)

...when dealing with data structures and sequences that are naturally defined recursively.

So things like trees - yes, although I guess less so for straightforward 'flat' structures like lists. Yes for things like the fibonacci sequence which is usually defined recursively, but less so for a straightforward loop counter.

Of course recursive definitions take some getting used to aswell, but once you've seen them, the recursive approach to programming with them feels quite natural, I think.

David, you give the example:
"If I show you a device that magically opens jars, and it has an icon of a jar on the front and a conspicuous button that says "Open", and you try to eat the device, then it doesn't have an intuitive interface. But if you point the device at a jar without any instruction, and you succeed in opening it, then I would argue that you find the interface to be intuitive."

There is a term for this: "percieved affordance". The percieved affordances of a thing are what people think they can do with it, which are often not what the designer of th thing intended. Screwdrivers are a great example. A steel shaft that's flattend at one end and has a handle a the other affords all kinds of uses variously well, and some of those at least as well as the "turning screws" affordance that the designer intended. Whereas a more complex tool, say a mitre-box has fewer affordances that aren't designed in.

How are your choices for sorting a deck of cards affected by the affordances of your visual system examining a deck of cards, of your motor system in manipulating them?

Meanwhile, the langauges that self taught programmers tend to pick up have affordances built in for iteration (say, arrays as the premier collection, the for loop as the premier repetition construct), so no wonder that they become trained in iteration. But iterative programs do not afford analytical thinking at all well.

To think deeply and well about iterative, imperative programming you need to be a Dijkstra, and even then the results are very ugly. Whereas other programming paradigms do afford that kind of thinking better.

But I'm rambling. Seems to me that a designer of tool should consider their tool intuitive if their intended affordance is the perceived affordance that most users come up with most often. For the user the tool is intuitive if what seems to them the most obvious percieved affordance is in fact supported by the tool well.

What that percieved affordance is will be conditioned by the users' prior experience, but only up to a point. Donald Norman's book explain in some detail how the (physical) form of a tool induces percieved affordances in all users. It may be that something similar happens based on the "psychloical form" of programming language constructs.

Keith

"Donald Norman's book explain in some detail how the (physical) form of a tool induces percieved affordances in all users."

Exactly what book do you mean? He has written several.

I suspect it's "The Design of Everyday Things".

I didn't find the book as illuminating as I thought, possibly due to the dry and laborious style, but at least I now have a name for those damn doors with identical pull-handles on both sides that still only open in one direction: Norman Doors.

Yes, I got an answer further down. And it was "The Psychology of Everyday Things" wich is the original title for "The Design of Everyday Things".

I imagine (combined with some other sorts e.g. a first pass of radix sort) many people use a gapped insertion sort for things they can manage in their hands, extrapolating from my personal experience. Gapped insertion sort is probabilistically O(n log n). Google "Insertion sort is O(n log n)!"

So why do some people insist that recursion is "more natural"?

To take you quite literally: perhaps because self-similarity is ubiquitous in nature? :) Think of trees, coastlines, micro vs. macro structure, population growth...

Of course, the self-similar description of these things is extrinsic, not intrinsic, to them. But the point is that we hear about these things from other people via media, and they often employ self-similarity as an explanatory strategy. So you can argue that, if recursion isn't intuitive to you, you don't get out enough. :)

BTW, I would like to add that I think it is a truism that although some people find recursion "more natural", that does not mean that they find "iteration" (a bad term — iteration is usually defined in mathematics as a form of recursion) less natural than those people who don't get recursion at all. I have also found this to be true more generally of functional programmers: there are lots of procedural and OO programmers who don't (claim to) "get" FP, but FPers almost all have a facility with procedural style and OO.

a bad term — iteration is usually defined in mathematics as a form of recursion

But is that because iteration == recursion, or because mathematicians tend to think functionally? ;> However, iteration is a perfectly natural mechanism in Computer Science, as you can find hardware support for it in virtually every processor architecture (i.e. decrement and jump if not zero type instructions). On the other hand, recursion is usually not as naturally supported (I mean, many architectures have some kind of CALL/RET instructions, but that either assumes your data fits in your register set, or you have to set up the call by pushing your arguments onto the stack or some such busywork, which is no longer assembly-level atomic).

There was a time when Computer Science was a branch of Mathematics, but I think it's legitimately its own field now, with the right to coin its own definitions (that don't necessarily coincide with the usage of words in other fields).

But is that because iteration == recursion, or because mathematicians tend to think functionally? ;>

Iteration, in the mathematical sense, is not the same as recursion. It's a particular species of recursion, and there are other forms of recursion which are not iterative.

So you will see now that I didn't intend to suggest that iteration, in the programmer's usual sense, "is just" (or "==", as you wrote) recursion.

However, iteration is a perfectly natural mechanism in Computer Science, as you can find hardware support for it in virtually every processor architecture

First, I might argue that if people really found computer architecture "natural", they would all be programming in machine language. To many people, the point of a (high-level) programming language is precisely to abstract away from machine details, which suggests that at least some of those details are "unnatural".

Whether iteration in your sense is among those details or not might be questioned. If you believe that language popularity correlates with naturalness, then I suppose the answer is no, and that iteration is more "natural". But personally I think that popularity is like fashion, more social and extrinsic than biological and intrinsic, and when you say "natural" I think of the latter.

What cannot be questioned, I think, is that languages need to support (*) both recursion and iteration. If you are given a spec which is expressed via recursion, like say the factorial function, then it is easiest to use recursion in your program; if you are given a spec which is expressed via iteration (more generally, imperatively), as I have noticed is often the case in specs written by other programmers, then it is easiest to express it via iteration.

That said, it is also useful to translate one into the other. When you express a recursive spec as an iterative program, you often gain insights into how to algorithmic questions such as how to produce output incrementally, and how it should behave on infinite inputs. Conversely, when you express an iterative spec as a recursive program, you gain insight into how the algorithm depends on the structure of the input, and then sometimes you can abstract that out as a generic function (like, say, fold).

Second, what have the idiosyncracies of computer hardware got to do with programming? Hardly anyone writes programs on top of bare metal. In practice, most people write to the spec of some kind of software platform, and an implementation of that platform could as well be running on a hardware with support for recursion and no support for iteration. Once you have that extra layer in between your program and the hardware it becomes very difficult to support arguments about naturalness by pointing to the hardware, because there isn't any hardware! It's an abstraction, factored out by the spec. At least if you are writing portable applications.

I am thinking of platforms like Win32 or POSIX, but there are many programs written for the web which essentially run on "the HTML platform". HTML has a really obvious recursive structure. If you argued that iteration is more natural because processors support instructions for iteration, you would have to argue that recursion is more natural for HTML applications. Actually, it's amazing to me looking at programs which produce HTML by appending strings. But intellectually I know that it's not "unnatural", inasmuch as an HTML document is ultimately a string, which happens to have an additional tree (and hence recursive) structure. In academic circles it's convenient to ignore the text aspect entirely and just consider it a tree, and then you have to employ recursion (because by definition a tree is processed by recursion) but that's a simplification, though a relatively minor one.

There was a time when Computer Science was a branch of Mathematics, but I think it's legitimately its own field now, with the right to coin its own definitions (that don't necessarily coincide with the usage of words in other fields).

As far as I'm concerned, computer science is still a branch of mathematics. Software engineering might be something else, since it has to do with human processes and organizations. I think it is best not confuse computer science with software engineering.

And I think it is best not to coin new words if suitable ones already exist. Half the arguments on LtU occur because people are not using the same words for the same things. On the other hand, I recognize that people coin words first and it might be years or decades before they realize that they are renaming an old concept. What to do then is a problem. I often prefer to use the older words in the hope that people will make the connection. And there is also the fact that programming jargon is fuzzier than mathematical jargon, and I think fuzziness is detrimental to clear thinking.

(*) But "support" does not necessarily mean explicit syntactic support. Scheme minus derived forms like do still "supports" iteration in this sense.

BTW, here is a thought experiment for you.

Imagine an architecture A, such as x86, with support for iteration but not recursion.

Now imagine an architecture B, which is exactly like A except that it has an additional instruction (say, FIX) supporting recursion. So, in particular, any program written for A is portable to B.

You argued that iteration in programs is more natural than recursion because most extant architectures are like A, and do not support recursion directly. But every A-program is a B-program, and B supports recursion directly. So I think really your argument reduces to "it is more natural ipso facto because most programs are written for A."

Of course, it is true that there are hardly any computers of sort B. (Perhaps the Lisp Machine had something comparable, but...) But, first, there could be, so your notion of "natural" is at least partly linked to historical issues and not only universal ones. Second, offhand I think it would be pretty easy to write a macro assembler which compiles something like FIX down to A-instructions. Then the question comes down to whether you decide to write code for your usual A-assembler, or for this B-assembler which happens to cross-compile to A. And whether you use one or the other is a choice, not a natural circumstance.

Now imagine an architecture B, which is exactly like A except that it has an additional instruction (say, FIX) supporting recursion. So, in particular, any program written for A is portable to B.

Well, I wrote a long paragraph about how impractical such a FIX instruction would be, but after thinking about it for a while, I decided that it would be doable. After briefly reviewing the x86 instruction set, I decided that INT is the closest such instruction (pushes registers onto the stack and performs a CALL). Even so, I would argue that iteration is more fundamental from a *computational* point of view. In particular, I argue that it is smaller in both space and time.

Clearly, iteration derives its performance the same way every engine does...by increasing entropy. In this case, it does so by destroying information. This allows it to avoid the one step that makes recursion expensive: copying. Recursion is elegant at least partly because it's pure. And being pure, it is automagically reversible. However, that purity comes at the cost of copying the local context on every recursive call [that cannot be optimized by TCO]. This is why recursion is more expensive in both time and space. It takes time to copy the state, and you need a place to copy it to.

It seems clear to me that the potentially unbounded cost of recursive calls is why most architectures are of the A type, and few, if any, are of the B type. Since the A type is computationally cheaper, it makes sense that early programmers, needing to conserve resources, would adopt a style that makes the most use of the A type architecture. So I agree that iteration is more popular because of history. I disagree that it was an *accident* of history. It is inevitable that non-TCO recursion will always be more expensive than iteration on the machine level (unless QM somehow gives us a device where copying is free). If we order computational mechanisms by how many micro-ops they require, given any reasonable hardware design, then I think it is demonstrated that iteration is more fundamental.

Now, this is not at all to say that iteration is *better*. Merely that abstraction has a cost, and that cost ought to be recognized and given due consideration (and it is, which is why we have things like TCO, and why FPers consciously try to enable it).

Cooking and knitting are two human activities which might be considered to be somewhat distant from computer programming. I don't have any knitting patterns handy, but a quick look through one of my favourite cookbooks provided the following example, which I've edited slightly:

...
3:
   Stir the batter well.
   Heat the remaining oil
      and add 2 tablespoons of batter to the pan,
      swirling it to form a small round pancake.
   Cook the pancake for 30 seconds
   Place 2 pieces of pork,
            1 tablespoon of prawn meat,
            1 tablespoon spring onion
            and 1 tablespoon bean sprouts
     in the center of the pancake.
   Cover the pan and cook for 2 minutes
   Place the pancake on a platter
   Repeat with the remaining ingredients.

4:
   Place each cooked pancake 
      inside a lettuce leaf and top with 2 mint leaves.
      Fold the lettuce to form a parcel
      Serve with the Dipping Sauce.

5:
   To make the Dipping Sauce:
      Combine the fish sauce, lime juice, chili and sugar in a bowl
      Whisk until well-blended.

Step 3 seems to me to be clearly a description of an "iterative" algorithm making use of a recursive tail call:

   (Repeat (remaining ingredients))

while step 4 is clearly using a higher-order function. It's interesting as well that step 5 needs to be executed prior to the completion of step 4.

Since this is apparently a functional cookbook, the map function in step 4 (which constructs each served-object from a pancake and a lettuce leaf) is a purely functional map, not dependent on any ordering of pancakes in the platter. Evidently, the procedure could be deforested if a second chef were available to perform step 4 in parallel with step 3.

:)

I'd say that in the case of making two cakes, the cake function calls itself.

I learned how to knit a few weeks back, it sure looks recursive to me. You need the result of the last step as one of the inputs for this step.

Hm, upon further thought, life in general seems more like continuation passing style.

Does CPS count as iterative or recursive? Or neither?

Step 3 seems to me to be clearly a description of an "iterative" algorithm making use of a recursive tail call:

But with no base case... Alternatively, you could read it as a "foreach" loop where the loop header comes at the end.

    {
        cook the pancake;
        assemble the pancake;
        put the pancake on the platter;
    } foreach (pancake in batter)

Several of the papers from the Natural Programming Project at CMU talk about how non-programmers tend to express loops. They're often "distributive" (eg foreach- or map-style) rather than explicitly counted out, and people often put the loop body first, and then explain the looping rules at the end. ("Lather, rinse, repeat", not "Do this twice: Lather, rinse".)

arguments based on "intuitiveness" also carry a similar amount of useful content as "your way is crap".

In the context of UI design, usability, etc... the term gets used to refer to the ease of a new user figuring out how to use a device; but that notion of intuitivity is generally supported by user trials and other objective evidence.

In most other contexts, "it's not intuitive" means little more than "I don't like it".

From where I'm sitting, intuitive means something that I have intuitions about - that I can work with without having to consciously reason my way through every last step. That does tend to come from being yet another instance of something I already know though, otherwise it's time for a lot of rote-learning-by-doing...

Actually a litle more things is intuitive. The most relevant to programing language is probably natural language. Most neurolinguists these days belive that we are all born with some knowledge about grammar. For example pars trees for natural language tends to slope from left to right. And also it would seem that infix notations is quite intutive in some contexts.

As a new father, and a programmer who's oh-so-familiar with the canard about the nipple being the only intuitive interface, I have to say that (from my observations) the nipple is actually *not* particularly intuitive. My baby does 'naturally' try to suck on my wife's breast, of course. But he also tries to suck on my shoulder, stomach, arm, and face.

So, with breasts as with programming languages, my personal impression is that the notion of "intuition" says more about the analyzer than the object of analysis (just like you said yourself). Babies are programmed to suck, VB programmers are programmed to prefer iteration. Maybe intuition is a cultural property rather than an individual (human) property.

Couldn't resist.

Cheers, Brandon J. Van Every
(cruise (director (of SeaFunc) '(Seattle Functional Programmers)))

You are mixing up two difference concepts. Intuitive and instinctive.

A Baby's instinct is to suck.

Because of the instinct, the nipple is somewhat intuitive - when placed at the nipple the baby will get the right result (food). However the nipple is not intuitive enough that the baby will find the nipple without assistance. Your wife has to place the baby's mouth at the nipple for it to work.

So the nipple is not instinctive at all, and only partially intuitive.

I remember having to explain the meaning of a for-loop to a colleague (who fancied himself my superior) who disputed the correctness of my code based on his inability to understand the basic meaning of the construct.

The solution is not to give up the for-loop, but to introduce new abstractions, document code very well to ensure that others have no justifiable complaint that clarity and elegance are "cryptic", and explaining the code to those who have to work with it who don't understand, including the appropriate benefits. If you keep doing this, you will come to a situation where their headaches can be cured by the use of an "advanced" construct that you have introduced, and you can show them this.

This is true, unless you get so far ahead of the curve that recruiting becomes an issue. In my most recent project, I used Java dynamic proxies for the first time in a production application. I took the risk, because my current team is good enough, qualified Java programmers are easily available in our area, and the dynamic proxy construct only requires about one "aha!" step for a qualified Java programmer to understand. If it were just me and my current team, considerably more difficult constructs would have been valuable, but it would have been unprofessional to use them given the current state of the recruiting pool.

Perhaps Google can find you readable copies, somewhere?

Ah! Attempts at actual research, with Raskin an author, to boot! I'll read them, thank you.

I always think research is good (e.g.: I like that there are people smart enough to be pursuing PLT) although I never have the fortitude to do any myself, and anything touching on the realm of psychology seems to me to require large doses of salt along side? I don't mean that to be denigrating, I just mean that I feel like more is subjective than we think.

I have a fairly mathematical background (I am a mathematician), though for me programming and programming languages are just a vague side interest that I pay casual attention to. With regards to recursion as a concept independent of programming - I don't think you can say anything meaningful about how intuitive it is without some reference to the problem at hand. Whether the recursive approach is the intuitive one very much depends on what you want to do with it. For some uses it is easiest to think of something in terms of recursive structure, while at other times thinking of the same thing in expressed non-reuirsively is the most natural.

In what programming I do things generally work the same way. Whether I write something recursively or iteratively is really all about how I want to use it. Neither approach seems any more intuitive without some understanding of exactly how whatever it is is going to fit in with everything else.

It's all to easy to generalize from your own experience. Just to make a counter example: I don't like math and avoid it as much as I can. I learned programing in a BASIC that didn't even allow rekursion. But today I allways use recursion (or fold). It's been years since i used recursion for any thing.

I agree with Li.

I'm a self taught programmer, but I started using recursion and pure functions in Python, since that felt simpler than iteration and mutation.

Luckily for me, someone saw my Python code and suggested that I learn Haskell.

know your audience

Ja wohl. For folks who scratch their heads and wonder, "Gee, we have all this good stuff (Erlang, Haskell, O'Caml, etc.), why aren't more people using it?" part of the answer is that marketing is needed: a) being able to communicate how the new thing will help solve people's actual problems and b) being good at teaching. Java certainly seemed to do that for C/++ folks.

Hm, I'm not sure what "All I really want is to quit my day job and go home and drink hot chocolate and play Half Life 2 all day" has to do with PLT. I'll meditate on it further...

I worked for Dr. Myers while an undergrad. I sucked at it. He's kept up the good faith all along. Yay! Wish I'd done a better job back then.

Also see Crista et al's naturalistic programming paper.