What is “Open Recursion”? | Hacker News Reader

What is “Open Recursion”?

journal.stuffwithstuff.com

101 pointsjasim58 comments

I'm a little confused by the summary. To me it looks like he's showed that you can simulate open recursion with only structures and functions.

If it's because doing so requires forward-declarations/hoisting/reassignment, here[1] is an implementation in JavaScript that has only a single `let` statement, for the counter itself.

[1] https://jsfiddle.net/n2c3s7r5/

Yeah, the post is a bit misleading. "Open recursion" is the OOP-like feature itself, not (as the post says) the extension you need to implement it.

What you need is the ability to implement recursive functions. That's not 'built in' to the lambda calculus, because there's no real concept of variable bindings, just functions that take arguments. In other words, you can't say "function x() { x(); }". In the untyped lambda calculus, that's no problem, because you can simulate it, e.g. by saying

    let x = (_x) => _x(_x);
    x(x);

Your implementation of open recursion uses a similar construct in 'mutualRecursion', as well as in the implementation of 'inc' (which calls 'set' passing 'set' itself as an argument).

But in the simply typed lambda calculus, that doesn't work, because 'x' would have an infinite type. For example, how would you write the type of x in TypeScript? Something like this:

    let x: (???) => whatever = (_x) => _x(_x);

where '???' is the type of x itself, so...

    let x: ((???) => whatever) => whatever = (_x) => _x(_x);

    let x: (((???) => whatever) => whatever) => whatever = (_x) => _x(_x);

...that doesn't work.

You could use a record/class type:

    class X {
        f: (X) => whatever;
        constructor(x) { this.x = x; }
    }
    let x = new X((_x) => _x.f(_x));
    x.f(x);

...but the desugaring of records into lambda calculus doesn't allow for that. (The use of X within its own type definition is recursive.)

You could use a generic function type:

    let x: <T>(arg: (T) => T) => whatever = (_x) => _x(_x);

but the simply typed lambda calculus has no generics.

But there's a more modest extension that can enable recursion, which is taking a fixed-point combinator (which in the untyped lambda calculus is just a function you can implement, e.g. as the Y combinator), and baking it into the typed lambda calculus as a primitive. Which is one of the things Pierce talks about in the book.

Agreed, but I think the distinction is that the original book was talking about language design. Since languages are Turing complete we can always implement the features of one in another, but it stands that open recursion is not a feature of his Dart subset. It would certainly be a stretch to call a language OO just because you can replicate OO features from first principles!

I could be wrong, but I think your mutualRecursion() function is a multi-parameter version of the Y combinator, which is the classic way of introducing recursion to a language that doesn't natively support it. If so then, yes, that works.

> but I think your mutualRecursion() function is a multi-parameter version of the Y combinator

Yes, exactly. I've created a fork [1] where I replace the multiple-parameter Y combinator with a single-parameter kind that operates on what is effectively a vtable.

[1] https://jsfiddle.net/9ump7bt5/1/

Pierce ... coined “open recursion” to refer to the kind of extensions you need to build an OOP language from a non-OOP one that just has functions (i.e. “lambdas”, “closures”, or “anonymous delegates”) and records (more or less “object literals” in JS or “maps” in other languages).

Which has nothing to do with recursion.

A lambda and a closure are completely different things. A lambda is just an anonymous function. A closure is a function instance which carries with it some context from an outer scope. You can have a lambda which is not a closure, and a closure which is not a lambda. Javascript often has closures which are not lambdas - that's the usual form of a callback function.

For languages that work much like LISP, with dynamic function creation, nested functions, and garbage collection, you get most of the heavy machinery needed for closures by default. If you've got that, you can kludge objects into existence. This was originally called "flavors" in LISP. Javascript does this, and suffers from having too many ways to create OOP-like objects. The LISP and Javascript experiences indicate that implementing OOP via closures creates a mess in source code.

Lambdas are just syntactic sugar for nested functions.

Some communities distinguish between lambdas and closures, but some don't. In the (mainstream) functional programming community it is unusual to make this distinction.

The recursion in open recursion refers to the ability of an object to refer to itself (the 'this' or 'self' value) and the open bit refers to late binding (the value to which 'this' or 'self' is bound is open to change).

Agreed on the duality between closures and objects. Closures are a poor man's objects and objects are a poor man's closures, as the joke goes.

> Which has nothing to do with recursion.

Had you read the article you might have realized this term is overloaded.

“When I use a word,” Humpty Dumpty said, in rather a scornful tone, “it means just what I choose it to mean—neither more nor less.” “The question is,” said Alice, “whether you can make words mean so many different things.” “The question is,” said Humpty Dumpty, “which is to be master—that's all.” - Lewis Carroll, a mathematician who wrote stories in his spare time.

Just because you didn't happen to not know this one doesn't mean that anyone just invented a new meaning.

https://en.m.wikipedia.org/wiki/This_(computer_programming)#...

A function calls a function with its own name-- there is a resemblance to recursion, where a function calls a function with its own name. This is the first I've ever heard of any controversy with the term "open recursion." Is it a common complaint, that the term "open recursion" abuses the notion of recursion?

I feel compelled to link the xkcd from the Friday before last:

https://xkcd.com/1860/

> Javascript often has closures which are not lambdas - that's the usual form of a callback function.

Can you clarify this further? To me a callback function is a lambda. It may or may not be a closure.

It seems like GP might have gotten it backwards; the usual form of a callback is a lambda that's not a closure. However, a callback function might not be either, e.g.:

   function foo(x) { return x + 1; }
   function bar(f, y) { return f(y); }

   // `foo` is a callback but neither a lambda nor a closure
   bar(foo, 2);

edit: adding the missing the "b" in lambda

foo and bar are both lambdas and closures. A named lambda is still a lambda.

  foo = function (x) { return x + 1; }

is identical to

  function foo (x) { return x + 1; }

They are also closures. Since they don't refer to any outer variables, they are closures containing zero context variables. If foo were to refer to some other variable, the closure would contain one context variable.

The only reason to distinguish between lambdas and closures is because some languages do not support closures (e.g. early versions of Emacs Lisp). Attempting to refer to other variables would always refer to a global variable with that name.

> foo and bar are both lambdas and closures. A named lambda is still a lambda. > foo = function (x) { return x + 1; } > is identical to > function foo (x) { return x + 1; }

I'll concede that for JavaScript (and a few other languages); some languages don't treat all functions as just a lambda with a binding, though.

> They are also closures. Since they don't refer to any outer variables, they are closures containing zero context variables. If foo were to refer to some other variable, the closure would contain one context variable.

I'm not very keen on the definition of "closure" including functions that close over zero variables, because then "closure" becomes indistinguishable from "function", and the word is no longer useful. I might be wrong about the technical definition, but I feel like having a word for closures isn't very useful if it doesn't mean "closing over one or more variables".

Elisp disagrees:

  > (lambda () (print "hi"))
  (closure (t) nil (print "hi"))

  > (let ((a 1) (b 2)) (lambda () (print "hi")))
  (closure ((b . 2) (a . 1) t) nil (print "hi"))

  > (let ((a 1)) (defun foo (x) (+ x 1)))
  foo
  > (symbol-function 'foo)
  (closure ((a . 1) t) (x) (+ x 1))

  > (defun bar (x) (+ x 1))
  bar
  > (symbol-function 'bar)
  (closure (t) (x) (+ x 1))

So yes, every function is a closure.

A closure is a combination of a function and the environment containing the variables it is bound to (closed over) rather than left open (like old LISPs, like elisp).

Every function isn't a closure. In particular, elisp lambdas aren't closures because elisp is dynamically bound - the variables are open, they are not closed over. Or with another perspective, the variables are bound in the global context. Either way, elisp closures aren't.

From emacs scratch buffer:

    (setq f (let ((x 10))
      (lambda ()
        (progn
          (setq x (+ x 1))
          x))))

    (funcall f)
    11
    (funcall f)
    12
    (setq x 20)
    (funcall f)
    21

This is because elisp is dynamically bound - it only has one environment (in this example), the global environment (leave aside buffer-local etc. for the moment).

It doesn't matter if you try to create a new environment using a lambda, the same problem still occurs:

    (setq g
          (lambda (x)
            (lambda ()
              (progn
                (setq x (+ x 1))
                x))))
    (setq f (funcall g 1))
    (funcall f)
    22  ;; or whatever you last assigned to x, + 1

You're thinking of old elisp. Elisp hasn't been dynamically bound since around 2014. In modern elisp, every function is a closure.

If you pass your examples to `(eval ... t)`, you'll see what I mean. Or run `(setq-local lexical-binding t)` before evaluating them in the scratch buffer.

  > (setq g (lambda (x)
              (lambda ()
                   (progn
                  (setq x (+ x 1))
                  x))))
      (setq f (funcall g 1))
         (funcall f)
  2
  > f
  (closure ((x . 2) t) nil (progn (setq x (+ x 1)) x))
  > (setq x 20)
  20
  > (funcall f)
  3

It depends on your definition of the closure. Example: "A closure is the combination of a function and the lexical environment within which that function was declared." [0]

[0] https://developer.mozilla.org/en/docs/Web/JavaScript/Closure...

A lexical environment being syonymous with "a set of 0 or more variables accessible from within the function, but not passed as arguments." The key piece of that being 0 or more. The null set is still a set.

I do not think it is useful to interpret it as 0 or more. To me it only make sense to assume 1 or more. Otherwise you could say that the programming language that do not support closing variables, has nonetheless closures, as according to that notion every function is a closure that closes nothing.

The key difference here is whether the language allows closure over the lexical environment, not whether the lexical environment contains anything used.

You can see this in Ruby where methods don't close over the environment, but blocks do, clearly Ruby methods aren't closures, not even when reïfied into a Method, whereas blocks are closures.

I think this is a rectangle/square problem. When you say you accept/return a closure, you probably mean a "function + lexical scope of 0 or more variables". You can still refer to "non-closures" as functions, though.

It's like code expecting rectangles wouldn't mind to get squares, but a code expecting squares will definitely do mind getting rectangles.

>It's like code expecting rectangles wouldn't mind to get squares, but a code expecting squares will definitely do mind getting rectangles.

It is actually not that obvious since in OOP neither a square or a rectangle type is properly a subtype of the other. [0]

I understand how implementation-wise it could be convenient to treat a function as a closure. Although, I would prefer some other type, eg:

    functoid := closure | function

[0] - https://stackoverflow.com/questions/1030521/is-deriving-squa...

Well no, because a closure is a function and an environment. A function closing over nothing is different than a function being unable to close over something.

You might define the interface of a closure as `closure(f: Function, env: Mapping[str, Any])`, or in other words a closure is a function and a mapping of variable names to values. That mapping can be empty, but that's different than the different interface `not_a_closure(f: Function)`, which is incapable of closing over anything, including the empty set.

I would prefer other sources of information. Like papers from 60s to 80s.

http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-... (Lambda: The Ultimate Imperative, Steele & Sussman 1976)

Pay attention to page 17 and subsequent pages, talking about variable binding in a closed or open context - this is the closing that closure refers to. Page 31 talks about closure in the context of a lambda.

>So yes, every function is a closure [in Elisp].

-- only if lexical-binding is non-nil :)

No offense, but I'm not going to base my understanding of how programming language terminology works on Elisp.

> Rust enthusiast

What a surprise...

You're free to be as prejudiced as you want, but I gave an example of an actual implementation.

Correct me if I'm wrong, but isn't Elisp generally considered to be a rather poor dialect of Lisp? At the very least, there seems to be a desire in at least part of the Emacs community (i.e. the one place where Elisp is actually used) to replace it with Guile, which I can only assume is due to it being a superior language.

Regardless, though, I don't think what any one language calls something is going to go very far in convincing me. As for the Rust ad hominem, I've been specifically arguing against the terminology that Rust uses (i.e. all lambdas are called closures, and nothing is called lambdas) that is much more consistent to your viewpoint than mine, so I don't really see what point you're trying to make there, other than that you're as prejudiced against Rust as I am against Elisp. But that's fine though; people are free to like whichever languages they like, but I don't really think it's worth taking it personally when others disagree.

Elisp is not to be replaced with Guile. That's a myth.

>A named lambda is still a lambda.

Most commonly a lambda is regarded as an anonymous function. [0] If you name it, it is no longer anonymous.

[0] - https://softwareengineering.stackexchange.com/questions/1307...

A named lambda isn't.

Yeah, your explanation is consistent with my understanding.

This article is great and IMHO is an example of the internet at its best. The article author, who knew and understood the intellectual development of the book where 'open recursion' was first used, explained, in the context of the book, exactly what the book author meant. Subsequently, we get the internet at less than its best when commenters quibble and squabble over terminology.

Read the article and ignore the comments.

That's pretty neat, but imagine how cool it would be if there was some sort of function that would take a lambda as an argument, and then call that lambda with itself as the first argument! sort of split the lambda into a Y and combine it with itself.

I have a pretty good idea of what a scheme implementation is, but i'll leave the details as an exercise for the reader.

Do you mean like this?

  In [1]: def foo(f, a):
     ...:     return f(foo, a)
     ...: 

  In [2]: foo(lambda f, a: f(lambda f, a: a, a-1) if a > 0 else a, 10)
  Out[2]: 9

Obviously that's a completely useless and convoluted example, but I'm fairly sure the concept of a lambda calling the function it was passed to just works in most languages.

it was a stupid joke about the y combinator. you can arrange a version with more function arguments that'll call all of the parts with their lambda friends. so they can all call each other.

so something vaguely like

   (define local-state)
   (super-y
      (lambda (inc get set v) 
          (set inc get set (+ 1(get inc get set v))))) ;this one is inc
      (lambda (inc get set v) local-state) ;this one is get
      (lambda (inc get set v) (set! local-state v)) ; this one is set

you don't really even need local state, just pass around an accumulator.

Once you have lambdas and a system that allows infinite types, mutual visibility is pretty easy to come by, mutual anonymous recursion is something i think is super nifty.

you can save yourself some pain by sticking the functions in a map, of course and passing that around instead.

“The problem is that increment is calling get and set here, but those functions haven’t been declared yet. Unlike JavaScript, Dart doesn’t silently hoist function declarations up.”

Huh? What is this, the 80s?

I'm not sure what you're getting at here. Are you arguing that function hoisting is the better behavior?

Note that this is for locals, not toplevel function declarations. https://dartpad.dartlang.org/74e990d984faad26dea0

FWIW, Clojure also by default doesn't let you use functions before they are declared but gives you a construct to do it explicitly, which I haven't seen much in the wild. And since Clojure doesn't have full TCO I guess its use won't rise either.

> FWIW, Clojure also by default doesn't let you use functions before they are declared but gives you a construct to do it explicitly, which I haven't seen much in the wild. And since Clojure doesn't have full TCO I guess its use won't rise either.

Honest question: what does TCO have to do with use-before-declaration? (Maybe you mean that self-calls—not the only possible kind of tail call!—aren't natively allowed? I don't use Clojure, so I don't know if that's the case.)

Honest question: what does TCO have to do with use-before-declaration?

Mutual recursion, tails calls to other functions. If you have two functions that each one calls each other you get a compiler error cause one of the two has not seen the definition of the other.

Since selfs-calls are easy to implement they are supported explicitly in Clojure via the recur keyword, they won't blow up the stack, but tails calls to other functions are not posible(without using some weird trickery) in Clojure because of the limitations in the JVM.

TXR Lisp: mlet (magic/mutual let), lnew (lazy new), lcons (lazy cons);

  1> (mlet ((z (+ x y))
            (y (succ x))
            (x 42))
       (list x y z))
 (42 43 85)

  2> (mlet ((z (+ x y))
            (y (succ x))
            (x (* z 2)))
       (list x y z))
  ** (expr-2:1) force: recursion forcing delayed form (* z 2) (expr-2:3)
  3> (flip *print-circle*)
  t
  4> (defstruct node () next prev)
  #<struct-type node>
  5> (mlet ((n (lnew node next n prev n))) n)
  #1=#S(node next #1# prev #1#)
  6> (mlet ((c (lcons 1 c))) c)
  #1=(1 . #1#)

Reminded me of "Objects are merely a poor man's closures": http://wiki.c2.com/?ClosuresAndObjectsAreEquivalent

Why does get/set need to see increment? They don't call increment...

The point he is trying to get at is that in an OO language you take it for granted that all methods can call all other methods. However without such trickery as described in the article this is not true in the simple language with only functions.

It depends from what perspective you come at it, though.

The article makes the case that the "simpler language" is the one where a function can only call another function if it has been declared before. Then, the ability to call any function regardless of declaration would be seen as an addition to that.

But couldn't one make an equally valid case that the "simpler language" is the one where function declaration order is not significant, that unordered is "simpler" than ordered? Then, the availability of a "F was declared before G" relation would be seen as the addition.

After all, the only reason we intuitively feel there is an order to function declarations is because the computer program's representation in source code is linear text. But I'd argue that the more fundamental representation of a computer program is that of a graph. Or at least equally fundamental :) It's just that in practice, computer memory is linear, and so any representation of a graph structure will have an implicit order that we need to tell the computer to ignore. But mathematically this ordering is just a side-effect of computer memory, irrelevant just like whether '1' bits weigh more than '0' bits or not.

He meant, imagine if they do.

Why not use an example that actually works?

That paragraph confused me too, but then I realised what he meant, felt the same as you, but still couldn't think of anything on the spot that would work other than:

    set(value) {
        count = 0
        while count != value {
            increment()
        }
    }

(~~may not be~~ probably isn't valid Dart)

That's an infinite recursion, because increment() is going to call back to set()

Heh, true. So, examples are hard. :)

This is super close to how you do objects in Lua, ignoring the fact that metatables make for nice syntactic sugar.

I need that Pierce book 20 years ago. As a self thought I often regret that I did not have the luck to stumble upon some amazing book instead of learning fragmented bits from blogs and tutorials.

Reply on news.ycombinator.com