Early binding, mutual recursion, closures. Can I have all three?

Question

Take this Python snippet of two functions that are mutually recursive and form closures:

# Late binding, allows mutual recursion, allows closures.
from random import random
greeting_a = 'Hello'
say_a = lambda: print(greeting_a) if random() > 0.5 else say_b()
greeting_b = 'Hi'
say_b = lambda: print(greeting_b) if random() > 0.5 else say_a()
greeting_a = 'New Hello'
say_a()
# New Hello

This works in Python because it has late binding; the say_b reference inside say_a is not resolved until runtime.

It's also possible to have simple recursion and closures with early binding languages:

# Hypothetical Python-like language with early binding.
# Only allows simple recursion, allows closures.
greeting = 'Hello'
say = lambda: print(greeting) if random() > 0.5 else say()
greeting = 'New Hello'
say()
# Hello

This requires the compiler to declare the say variable before checking the lambda, and is doable for simple declarations like this (right?). But mutual recursion would fail, because the say_b closure is created several statements after say_a.

And it's also possible to have mutual recursion and early binding, by sacrificing closures and treating functions as global constants:

# Hypothetical Python-like language with early binding.
# Allows mutual recursion, doesn't allow closures.
from random import random
def say_a(a, b): print('Hello') if random() > 0.5 else say_b(a, b)
def say_b(a, b): print('Hi') if random() > 0.5 else say_a(a, b)
say_a('Hi', 'Hello')
# Hello

Is it possible for a language to have all three? Early binding, mutual recursion, and closures? Are there any languages that have them?

---

For context, I find all three properties extremely useful. Mutual recursion arises naturally when processing trees, closures simplify code, and early binding enables better static checks and optimizations. I'd rather complicate the compiler by juggling forward references than to remove them from the user's toolbox.

What I'm looking for is a way to have this:

# Hypothetical Python-like language with early binding.
# Allows mutual recursion, allows closures.
from random import random
greeting_a = 'Hello'
say_a = lambda: print(greeting_a) if random() > 0.5 else say_b()
greeting_b = 'Hi'
say_b = lambda: print(greeting_b) if random() > 0.5 else say_a()
greeting_a = 'New Hello'
say_a()
# Hello (not New Hello, error, or allowing invalid references)

Answer 1

This doesn't require late binding, just forward references. That is, the name say_b appears in the code before it's declared.

Late binding is one way of supporting forward references, but you can also use forward references with early binding. Just have the compiler make two passes ─ one to find all declarations, another to bind names to declarations.

Answer 2

When you talk about function closures, what you actually seem to have in mind is anonymous functions, which are an entirely different and orthogonal concept. Under Python semantics, your lambda expressions close over nothing, since they reference only global variables. The same would be true if you'd used def. The only differences between lambda and def are that lambda sounds like a fancy computer-sciency thing, and it doesn't give a name to the function.

I think closures are irrelevant to your question. What you want is compile-time optimization of mutually-recursive anonymous functions, where the recursive calls happen through function pointers that you assigned the functions to using an ordinary assignment construct.

The key to making this happen is designing your language semantics in such a way that the compiler can prove that early binding is safe. The problem with

function_ptr = less_scary_anonymous_function_keyword { do_something; };
[...]
function_ptr();

, whether that call happens inside another anonymous function or not, is that some other value might be assigned to function_ptr between the first assignment and the call. You have to restrict assignment somehow to make that impossible.

For example, you could declare function_ptr to be const (in the C++ sense) at the assignment point, so attempts to change it are an error. (It doesn't even have to be a compile-time error; runtime detection is fine, as long as the value is guaranteed not to change.) A more subtle approach is to declare it static, or otherwise private to some chunk of code that is entirely visible to the compiler, and not have any other assignments to the variable in that code, so it's evident that only one value is ever assigned to the variable. At least some modern C and C++ compilers will optimize calls through such a pointer to a direct call. The C and C++ language standards don't guarantee it will happen, but they could.

The advantage of a special function-definition syntax is that you can save the programmer from remembering the necessary boilerplate. You can define namedfun foo() { ... } to be equivalent to constfoo = anonfun { ... }. That is, in effect, what C's function definition syntax means. But if you want to dispense with the named-function syntax and use anonymous functions and a const keyword instead, you can. There's nothing about anonymity that makes it impossible.

---

This sort of optimization is still possible when you are calling true closures. If you have (using Haskell notation this time)

let f ... = ... g ...
    g ... = ... f ...
in
  if ... then f ... else g ...

with an if statement to prevent the easy solution of inlining g, and the whole thing is in a nested context and mentions input-dependent free variables so that an unbounded number of closure objects may be created at runtime, the optimization is still possible. There are (in the most obvious implementation) just two statically compiled code objects, one for f and one for g, and f's code object always calls g's code object and vice versa, and the compiler can see that. GHC definitely performs such optimizations; they're its bread and butter. At a low level, there are still raw function pointers in the closure objects, and loading of them can be optimized to a constant load if the value is provably constant.

Answer 3

Explicit early- vs late-binding

Swift will let you immediately initialize only one of the closures, and you must explicitly defer initialization of the other:

let greetingA = "Hello", greetingB = "Hi"

var sayB: (() -> Void)! = nil
let sayA = {
  if .random() {
    print(greetingA)
  } else {
    sayB()
  }
}
sayB = {
  if .random() {
    print(greetingB)
  } else {
    sayA()
  }
}

sayA()

The ! at the end of the type is an implicitly unwrapped optional (IUO): It's mostly equivalent to an optional type (with ?), but users of it can assume it will never be nil.

It may be preferable to have a dedicated keyword for this, such as Kotlin's lateinit, to avoid the sharp edges of IUO types (namely, that anyone else could come back and say sayB = nil later, and break sayA).

---

If you want to capture the current value but also be able to mutate the variable out from under it, that comes to by-value vs by-reference captures:

var x = 1, y = 2
let printBoth = { [x] in print("x = \(x), y = \(y)") }
printBoth() // x = 1, y = 2
x = 2
y = 3
printBoth() // x = 1, y = 3

The [x] tells Swift to capture x by value instead of by reference. To capture both by-value, that would be [x, y]. Some languages, such as C++, require both by-value and by-reference captures to be explicit:

int x = 1, y = 2;
auto printBoth = [x, &y]() { printf("x = %d, y = %d\n", x, y); };
printBoth();
x = 2;
y = 3;
printBoth();

Answer 4

You sure can. The big question is: when a function mentions the name of a variable or another function, does it see

1. the static, known-at-compile-time value of the variable,
2. the run-time value that the variable had at the time that the function definition was executed, or
3. the run-time value that the variable has at the time that the statement containing the variable is executed?

(For names that refer to functions, the "value of the variable" means the body or implementation of the function.)

As far as I know, Python uses rule 3 at all times, and C# uses rule 1 for function names and rule 3 for variables (including variables which hold references to functions). Both of these allow for mutual recursion.

In your example of what you're looking at, the reference to greeting_a uses rule 2, and so you end up printing "Hello." However, the reference to say_b inside of say_a can't use rule 2, because say_b hasn't been defined yet, so that reference has to use either rule 1 or rule 3.

As a language designer, you simply have to decide:

• Does mutual recursion work by using rule 1 or by using rule 3? Or do you offer both options to the programmer?
• When does your language apply rule 2, and when does it apply one of the other rules? Some options include:
  • References to functions always use rule 1 or 3, and references to ordinary variables always use rule 2.
  • Variables can be marked either as "static" (using rule 1), "mutable" (using rule 2), or "forward" (using rule 3). The default is either "static" or "mutable."
  • When you write a nested function, variables are captured using rule 2 by default, but there's some notation the programmer can use to capture them using rule 3 instead.

Answer 5

Correct me if I'm wrong, but doesn't C# already have this feature? Here is your pseudocode translated to C#:

Correction: C# almost has this feature. As pointed out by Tanner Swett in the comments, this captures the live value of greeting_a, not the instantaneous one. So the output will be "New Hello" and not "Hello". But it's still quite close and from language design perspective the changes required would not be monumental.

string greeting_a = "Hello";
Action say_a = null, say_b = null;

say_a = () => {
    if (Random.Shared.Next(0, 2) == 0) {
        Console.WriteLine(greeting_a);
    }
    else
    {
        say_b();
    }
};
string greeting_b = "Hi";
say_b = () => {
    if (Random.Shared.Next(0, 2) == 0)
    {
        Console.WriteLine(greeting_b);
    }
    else
    {
        say_a();
    }
};

greeting_a = "New Hello";
say_a();

Answer 6

Yes, you can do this. There are two obvious approaches to this: one is the approach taken by Scheme, and the other is the approach taken by, really, the λ-calculus.

As this is not a language-specific question, and as my Python is very rusty now, I will give initial examples in Racket, although they should be portable Scheme modulo using λ instead of lambda. I will try to explain them in a way which makes sense to people who are not familiar with Scheme-family languages though. I'll give an example of the final version in Python.

For clarity: I am using 'late binding' to mean that, if a procedure refers to some variable, and in particular if it is going to call a procedure which is the value of some variable, then that variable binding is checked when the procedure is called, not earlier than that. In particular it may not exist when the procedure is defined. 'Early binding' would then mean that the existence of the binding is checked when the procedure is defined. I'm not using it to mean the far stronger statement that everything must be known about the binding when the procedure is defined: that would make it impossible to define procedures which call other procedures passed to them as arguments, say.

In a 'Lisp 1' – a language which shares a common namespace for procedure bindings and variable bindings – which supports assignment it's fairly hard to see how any stricter notion of early binding than this would make sense, I think.

The first approach: letrec

Scheme has a construct called letrec which allows you to bind names to objects – usually procedures – which can refer to each other. Although letrec is a primitive part of the language, it is clear how it is implemented (in particular the implementation is described on p16 of the current standard (PDF link)), and it's possible to implement a simple version of it. Here is how it works

(letrec ((var1 val1) (var2 val2))
  form ...)

does the following:

1. first bind var1, var2, ... to some kind of special unspeakable value or values;
2. Then assign val1 to var1, val2 to var2, and so on;
3. evaluate the body.

Now you can see that, at the point where val1 is evaluated, all of the variables are already bound: the values of those bindings are wrong, but so long as the bindings are not referred to until later, everything will be fine. Well, that's exactly what happens when defining mutually-recursive procedures.

So, in Scheme

(letrec ((p1 (λ (...) ... (p2 ...) ...))
         (p2 (λ (...) ... (p2 ...) ...)
  (p1 ...))

turns into

(let ((p1 <unspeakable>)
      (p2 <unspeakable>))
  (set! p1 (λ (...) ... (p2 ...) ...))
  (set! p2 (λ (...) ... (p2 ...) ...))
  (p1 ...))

And in fact, since Scheme (or Racket) has a macro system, you can write a version of letrec in it. Here is that in Racket (I have called it rlet to avoid clobbering letrec:

(require racket/undefined) ; provides the undefined object

(define-syntax rlet
  ;; This is certainly not complete or correct
  (syntax-rules ()
    [(_ ((var val) ...) form ...)
     (let ((var undefined) ...)
       (set! var val) ...
       form ...)]))

And here is a procedure which returns a procedure which will count down between two numbers. This procedure is one of a pair of mutually-recursive procedures, and also closes over the binding of the argument to the outer procedure (and the two procedures also, obvuiously, close over the bindings of each other's names):

(define (make-countdown x)
    (rlet ((r1 (λ (it)
                 (displayln it)
                 (if (<= it x)
                     x
                     (r2 (- it 1)))))
           (r2 (λ (it)
                 (r1 it))))
    r1))

You can use Racket's macro expansion tool to see that the definition of make-countdown is turned into what you would expect:

(define (make-countdown x)
  (let ((r1 undefined) (r2 undefined))
    (set! r1 (λ (it) (displayln it) (if (<= it x) x (r2 (- it 1)))))
    (set! r2 (λ (it) (r1 it)))
    r1))))

And we can now test this

> (make-countdown 10)
#<procedure:r1>
> ((make-countdown 10) 20)
20
19
18
17
16
15
14
13
12
11
10
10

(The 10 is printed twice: once by displayln and once because it's the value).

So this approach does not use late binding: everything is bound when the mutually recursive procedures are defined. But it does use assignment. But assignment is kind of icky: can you do this without assignment?

Without assignment

Well, yes, you can of course: one of the most famous results in all computing is that you can do anything with just λ. At this point I should probably start going on about the Y combinator and making everything incomprehensible, but you don't need to do that: you can do it with something which is much less hairy (but which is, really, an 'unrolled' version of the U combinator).

The trick is that you can pass a procedure as an argument to a procedure, and then call it. So consider this fragment:

(λ (c it)
  (if (<= it x)
      x
      (c c (- it 1))))

This is a procedure which takes two arguments:

• c, a procedure
• it, a number

It then tests it against some variable x, and if it's more than it it calls c passing it two arguments: c itself and a value one less than x.

Well, the trick is, of course, that we're going to make c be this procedure itself. We can also wrap this up so the procedure we call only takes the one argument we care about:

(let ((r (λ (c it)
           (if (<= it x)
               x
               (c c (- it 1))))))
  (λ (it) (r r it)))

And, just to be completist about this, let itself is of course just syntactic sugar for λ: the above is equivalent to this:

((λ (r)
   (λ (it) (r r it)))
 (λ (c it)
   (if (<= it x)
       x
       (c c (- it 1)))))

(I won't do that again because it makes things unreadable, but it's important that it can be done.)

Well, we need to wrap this up in a 'maker' procedure again to bind x:

(define (make-countdown x)
  (let ((r (λ (c it)
             (displayln it)
             (if (<= it x)
                 x
                 (c c (- it 1))))))
    (λ (it) (r r it))))

And now

> ((make-countdown 1) 3)
3
2
1
1

Well, this is not a pair of mutually-recursive procedures, but that's easy to do, you just need to pass both the procedures as arguments to each of them:

(define (make-countdown x)
  (let ((r1 (λ (c1 c2 it)
             (displayln it)
             (if (<= it x)
                 x
                 (c2 c1 c2 it))))
        (r2 (λ (c1 c2 it)
              (c1 c1 c2 (- it 1)))))
    (λ (it) (r1 r1 r2 it))))

And this works the same way, with r1 doing the print and test, and r2 doing the decrementing.

So this approach does not use late binding, and does not use assignment. And is moderately painful, of course.

The second approach in Python

Finally, here is the last function expressed as Python. Note that I've used def to express the local functions: you can do it all with lambdas but it's very painful.

def mc(x):
    def r1(c1, c2, it):
        print(it)
        if it == x:
            return it
        else:
            return c2(c1, c2, it)
    def r2(c1, c2, it):
        return c1(c1, c2, it - 1)
    return (lambda v: r1(r1, r2, v))

And here is that working:

>>> (mc(0))(2)
(mc(0))(2)
2
1
0
0

OK.