Someone on StackOverflow stumbled onto the strange term “open recursion” and asked what it meant. Since most of the other answers to this online are pretty opaque, I started writing an answer. But then I accidentally wrote a blog post.
I honestly couldn’t remember what it meant either, so I cracked open my copy of Types and Programming Languages where, I believe, Pierce first introduces the term. After skimming a bit, I think I’ve got it. For those who don’t have the book or don’t want to wade through PL nerd terminology, I’ll try to translate it to something a little friendlier.
First, a bit of context. Pierce is explaining the semantics and types of object-oriented languages starting from a non-OOP core based on the lambda calculus and records. He starts the book with the simplest possible proto-language and then keeps adding extensions to it to build up to the kind of languages we see today. He coined “open recursion” to refer to the kind of extensions you need in order to build an object-oriented language from a simpler language 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).
Since not too many people know the lambda calculus, for this scene I will use a subset of Dart as its stand-in. We’ll allow function declarations and maps, but no actual classes or methods.
Now the question is, if you were to only have maps of functions, what would you be missing compared to “real” objects? Pierce’s answer is “open recursion”. We’ll break that down into the two words, last one first:
Say you want to make an “object” that represents a counter. It exposes three operations: increment() , get() , and set() . You could make such an object in our Dart subset like this:
makeCounter () { // Declare the instance state for the "object". var count = 0 ; // Declare functions for the "methods". They are closures, // so they can access `count`. increment () { count ++ ; } get () { return count ; } set ( value ) { count = value ; } // Make an "object" as a map of functions. return { 'get' : get , 'set' : set , 'increment' : increment }; }
Great. This works fine. But let’s say we wanted to implement increment() in terms of get() and set() . One common feature of methods is that they can call each other. Let’s try:
makeCounter () { // Declare the instance state for the "object". var count = 0 ; // Declare functions for the "methods". They are closures, // so they can access count. increment () { set ( get () + 1 )); } get () { return count ; } set ( value ) { count = value ; } // Make an "object" as a map of functions. return { 'get' : get , 'set' : set , 'increment' : increment }; }
Oops! This doesn’t work. 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. So at the point that we’re defining increment() , get() and set() aren’t declared.
... continue reading