50 ms·

What is “Open Recursion”?

• LeoNatan25 9y ago
  “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?
  • Scarbutt 9y ago
    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.
    • JadeNB 9y ago
      > 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.)
      • Scarbutt 9y ago
        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.
  • munificent 9y ago
    I'm not sure what you're getting at here. Are you arguing that function hoisting is the better behavior?
  • fasquoika 9y ago
    Note that this is for locals, not toplevel function declarations. https://dartpad.dartlang.org/74e990d984faad26dea0 https://dartpad.dartlang.org/74e990d984faad26dea0
• Animats 9y ago
  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.
  • noelwelsh 9y ago
    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.
  • the_common_man 9y ago
    > 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.
    • saghm 9y ago
      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
• nhatbui 9y ago
  Why does get/set need to see increment? They don't call increment...
  • sushisource 9y ago
    He meant, imagine if they do.
    • c3534l 9y ago
      Why not use an example that actually works?
      • OJFord 9y ago
        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)
        • krallja 9y ago
          That's an infinite recursion, because increment() is going to call back to set()
          • OJFord 9y ago
            Heh, true. So, examples are hard. :)
  • wickawic 9y ago
    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.
    • 9y ago
• clusmore 9y ago
  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/ https://jsfiddle.net/n2c3s7r5/
  • munificent 9y ago
    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.
    • clusmore 9y ago
      > 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/ https://jsfiddle.net/9ump7bt5/1/
  • wickawic 9y ago
    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!
  • comex 9y ago
    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.
• kovrik 9y ago
  Reminded me of "Objects are merely a poor man's closures": http://wiki.c2.com/?ClosuresAndObjectsAreEquivalent http://wiki.c2.com/?ClosuresAndObjectsAreEquivalent
• jfoutz 9y ago
  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.
  • Sean1708 9y ago
    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.
    • jfoutz 9y ago
      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.
• a_t48 9y ago
  This is super close to how you do objects in Lua, ignoring the fact that metatables make for nice syntactic sugar.
• dandare 9y ago
  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.
• c517402 9y ago
  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.
• kazinator 9y ago
  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#)