Hacker News Reader

Comment by pjc50 | Hacker News Reader

This is a prime example of the conflict between the "machine model" of programming (a computer is a large and elaborate state machine that advances instruction by instruction) and the "maths model" (by reasoning from a set of axioms and rules of production we can transform information or prove facts).

The former maps onto imperative programming, and the latter onto functional programming. It seems that different people find these models harder or easier to understand - and then get confused when not everyone sees it that way.

View on HN

I think this POV is limiting. In my experience, many people who take the "maths model" respect and use the "machine model" quite often as well.

The formal term of note here is "denotation" in that "a language may be understood through its denotation" as an abstract machine or as a mathematical object. The best understanding comes from recognizing that many denotations may be valid for a language and that great richness comes from this. To work, the denotations must be in alignment in various ways and when they are it means that you can transport understanding from one denotation to another to the language itself.

So I don't think there's an honest conflict, though I imagine there are programmers and PL experts who either (a) honestly only ever use one denotation or (b) play favorites and this may lead to some clouding of things.

Yes, you can use both, but look at all the disputation of preference going on elsewhere in this thread - that's what I meant by a conflict.

I like your phrase "transport understanding"; an important part of programming is dealing with informal understandings of what the software does or is intended to do. Most programming has very little formal reasoning in.

Ok, total agreement there. I think denotations are pretty identical to languages in the sense that you pick one you like then defend it to the death but, should you choose, could always learn to use more and would profit massively from doing so.

So there are holy wars to be expected.

I think you point out something really interesting with this notion of formal/informal. I think it's tough to draw that line because a lot of "formal" reasoning is designed to be informally used but needs formality in its presentation.

Or, to be more concrete, I think that most programmers use a slew of semi-actualized denotations when understanding code. Usually this is a transparent process and a skill gained by experienced programmers is to align your semi-actualized denotations so that they both agree with one another and with reality.

Formalism is just a tool to get ahold of these and fully actualize them. It's something one could choose to invest in—or not.

But the underlying process of transporting understanding and using the best denotation for the moment is very real regardless of the level of formality.

To be fair to the author, he's one of the few researchers trying to bridge this divide (e.g. see https://existentialtype.wordpress.com/2014/09/28/structure-a... )

     the conflict between the "machine model"  ...

I'm not sure I can agree. The original post makes the point that you can see recursion in multiple ways, including machine-oriented (e.g. using a stack and stack pointer) and abstract, e.g. using an axiomatisation of self-reference, for example using the Y combinator which satisfies YM = M(YM).

Incidentally, stacks can also be given an axiomatic treatment indepented of concrete machine models.

I think that the confuse comes from the fact that one wants to mix both views; after all, I don't remember see anyone being confused bu the classic recursive definitions (Fibonacci, factorial) in my school days. IIRC the factorial function is introduced in high school. It can literally be understood by a kid.

I believe the reason why people want to expose both views at the same time is that the math view doesn't really explains "how it works" as far as CS is concerned.

As far as I'm concerned, I can't imagine programming without the knowledge of how things work at assembly level. I think I would feel so crippled in my understanding that I would want to learn about assembly... again. I would probably not stand working with a machine that works on magic.

> I can't imagine programming without the knowledge of how things work at assembly level.

The author's point is that recursion is a pervasive concept that is essential to understand even how modern computer hardware works:

> the very concept of a digital computer is grounded in recursive self-reference (the cross-connection of gates to form a latch), which, needless to say, does not involve a stack. Not only do real programmers use recursion, there could not even be programmers were it not for that.

The author is not suggesting that we forget about "what's really going on". He's rightly pointing out that you actually cannot understand what's really going on at all without first understanding recursive self-reference.

Personally, I think that analogy conceals more than it reveals. Recursion in computer software requires nested definitions that eventually reach a simple base case resulting in termination. An sram cell or J/K flip-flop, on the other hand, doesn't involve nesting or reach a simple base case.

In my mind recursion is a snake that has eaten a smaller snake, whereas an sram cell is a snake eating its own tail.

> Recursion in computer software requires nested definitions that eventually reach a simple base case resulting in termination.

I think you've just illustrated the article's point.

You're describing well-founded recursion, which is very useful, but doesn't include e.g. continuation-passing ( https://en.wikipedia.org/wiki/Continuation-passing_style ) or co-recursion ( https://en.wikipedia.org/wiki/Corecursion ), hence perpetuating the myths the article is complaining about.

The really unfortunate thing is that sub-sets of these ideas keep getting re-invented (AKA "reinventing the square wheel"), for example exception handlers in place of continuations, iterable objects in place of co-recursive data, etc.

As for J/K flip-flops, they're recursive because their output is their own input. For example, given co-inductive stream of `j` and `k` values (the flip-flop inputs), we can generate a co-inductive stream of outputs `q`:

    function flipflop(init_js, init_ks) {
      function ff(js, ks, q_old) {
        var j     = car(js);
        var k     = car(ks);
        var q_new = j * not(q_old) + not(k) * q_old;
        return cons(q, ff(cdr(js), cdr(ks), q_new);
      }
      return ff(init_js, init_ks, 0);  // Initiate the co-recursion with 0, arbitrarily
    }

Whilst I've used co-recursive data for convenience, the fact that the result `q_new` becomes the argument `q_old` for the next call is unavoidably recursive.

Bingo. Recursion is easy in the func^H^H^H^H"application-oriented programming" model of computing where the whole program is a mathematical expression written out in tree form on a blackboard, and applying a function means erasing a node that says (fib 8) and replacing it with a node that says (+ (fib 7) (fib 6)), and eventually with one that says 21. But most programmers, most of the time, seem to use a different mental model, one of functions as little actors that send function-call messages to each other and themselves, including when they are doing "functional programming" (and ofc mutable state and performance considerations tend to push the language into this model anyway). The problem is that in an actors-ish model continuations are easy, while recursion and function-call behaviour in general are hard, derived concepts built on top of continuations.

So I've come to think that introductions to programming should usually look something like this:

Stage 1: Teach "application-oriented programming": functional programming that's explicitly, and exclusively, about substituting expressions in an expression tree.

Stage 2: Teach how to program using only simple "dataflow" models of stateless (or stateful) actors that reliably pass messages (ie. call continuations) to each other in parallel. (To prepare for stage 3 you'll need to cover "dynamic dataflow" with actors passing around the capabilities to call other actors, but it's also a good opportunity to probe what can reasonably be done with a static graph of calling capabilities.)

Stage 3: If the students are led to push the Stage 2 programming models hard enough they'll naturally see that a lot of the code they write for those models (but NOT all of it) really wants to be able to take advantage of an explicit function-call abstraction. Teach them how to implement the Stage 1 language as a DSL inside a Stage 2 language.

Almost as an incidental benefit the students will end up understanding call/cc, too. By contrast, it's the attempt to blur these two, very different, models of computing together and handwave the distinction that leaves students confused by recursion—and they should feel confused by recursion in this case! The feeling of confusion is their intellect warning them that something is wrong. The real damage is done when they either give up, or end up feeling that they understand it when they don't.

(Another side benefit is that it's an early introduction to the huge and indispensable diversity, and yet intense inter-relatedness, of models of computing. Among other things that should hopefully temper the zeal to smash square pegs through the One True, Round Hole, and hopefully even the polar opposite vice of unthinkingly picking up whatever "the tool for the job" is supposed to be. Similarly, the order of stage 1 and stage 2 could be reversed.)

TL:DR: "Continuations are easy: functions are hard."

PS: The really fun question is how lexical scope fits into the Stage 2 model. It's a restricted case of something else...

   Continuations are easy: functions are hard.

That's a deep truth. Thinking about of computation message-passing actors is Hewitt's and Milner's dream. It's a hard sell to the programming mainstream though. In particular the functional programming community sees functions as the basis on top of which everything else needs to be layered as an effect. It's much more productive to go the other way round and see functions as a very peculiar and well-behaved from of message exchange. (Scala also makes this point.)

Reply on news.ycombinator.com