<p>Take this Python snippet of two functions that are mutually recursive and form closures:</p>
<pre class="lang-python prettyprint-override"><code># Late binding, allows mutual recursion, allows closures.
from random import random
greeting_a = 'Hello'
say_a = lambda: print(greeting_a) if random() &gt; 0.5 else say_b()
greeting_b = 'Hi'
say_b = lambda: print(greeting_b) if random() &gt; 0.5 else say_a()
greeting_a = 'New Hello'
say_a()
# New Hello
</code></pre>
<p>This works in Python because it has late binding; the <code>say_b</code> reference inside <code>say_a</code> is not resolved until runtime.</p>
<p>It's also possible to have simple recursion and closures with early binding languages:</p>
<pre class="lang-python prettyprint-override"><code># Hypothetical Python-like language with early binding.
# Only allows simple recursion, allows closures.
greeting = 'Hello'
say = lambda: print(greeting) if random() &gt; 0.5 else say()
greeting = 'New Hello'
say()
# Hello
</code></pre>
<p>This requires the compiler to declare the <code>say</code> variable <em>before</em> checking the lambda, and is doable for simple declarations like this (right?). But mutual recursion would fail, because the <code>say_b</code> closure is created several statements after <code>say_a</code>.</p>
<p>And it's also possible to have mutual recursion and early binding, by sacrificing closures and treating functions as global constants:</p>
<pre class="lang-python prettyprint-override"><code># 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() &gt; 0.5 else say_b(a, b)
def say_b(a, b): print('Hi') if random() &gt; 0.5 else say_a(a, b)
say_a('Hi', 'Hello')
# Hello
</code></pre>
<p><strong>Is it possible for a language to have all three? Early binding, mutual recursion, and closures?</strong> Are there any languages that have them?</p>
<hr />
<p>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.</p>
<p>What I'm looking for is a way to have this:</p>
<pre class="lang-python prettyprint-override"><code># 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() &gt; 0.5 else say_b()
greeting_b = 'Hi'
say_b = lambda: print(greeting_b) if random() &gt; 0.5 else say_a()
greeting_a = 'New Hello'
say_a()
# Hello (not New Hello, error, or allowing invalid references)
</code></pre>

<recursion><variables><closure>
Early binding, mutual recursion, closures. Can I have all three?
CC BY-SA 4.0
2023-06-27T16:21:26.893Z
all you need is an explicit `letrec` implementation, which is quite trivial.
SK-logic
CC BY-SA 4.0
2023-06-27T17:30:11.837Z
@SK-logic I'd prefer if this limitation was transparent to the user, as it is in late-binding languages. But yeah, that's a good plan B.
BoppreH
CC BY-SA 4.0
2023-06-27T23:36:05.847Z
You can do this with lazy evaluation, like Haskell, but I think your definition of early/late binding is kind of fuzzy so I don't know which side you'd say this falls on.
Glenn Willen
CC BY-SA 4.0
2023-06-28T07:47:23.810Z
I believe this kind of late binding requires dynamic scope and is not really possible with any sound lexical scoping
SK-logic
CC BY-SA 4.0
2023-06-29T19:41:51.593Z
I would argue that Python has early binding, but it is binding the variable and not the value of the variable at the time the closure is created.
Bergi
CC BY-SA 4.0
2023-07-30T15:52:25.610Z
I have the same problem in my language
Seggan
<p>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 <code>lambda</code> expressions close over nothing, since they reference only global variables. The same would be true if you'd used <code>def</code>. The only differences between <code>lambda</code> and <code>def</code> are that <code>lambda</code> sounds like a fancy computer-sciency thing, and it doesn't give a name to the function.</p>
<p>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.</p>
<p>The key to making this happen is designing your language semantics in such a way that the compiler can prove that early binding is <em>safe</em>. The problem with</p>
<pre><code>function_ptr = less_scary_anonymous_function_keyword { do_something; };
[...]
function_ptr();
</code></pre>
<p>, whether that call happens inside another anonymous function or not, is that some other value might be assigned to <code>function_ptr</code> between the first assignment and the call. You have to restrict assignment somehow to make that impossible.</p>
<p>For example, you could declare <code>function_ptr</code> to be <code>const</code> (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 <code>static</code>, 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 <em>could</em>.</p>
<p>The advantage of a special function-definition syntax is that you can save the programmer from remembering the necessary boilerplate. You can define <code>namedfun foo() { ... }</code> to be equivalent to <strong><code>const</code></strong><code>foo = anonfun { ... }</code>. 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 <code>const</code> keyword instead, you can. There's nothing about anonymity that makes it impossible.</p>
<hr />
<p>This sort of optimization is still possible when you are calling true closures. If you have (using Haskell notation this time)</p>
<pre><code>let f ... = ... g ...
    g ... = ... f ...
in
  if ... then f ... else g ...
</code></pre>
<p>with an <code>if</code> statement to prevent the easy solution of inlining <code>g</code>, 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 <code>f</code> and one for <code>g</code>, and <code>f</code>'s code object always calls <code>g</code>'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.</p>

CC BY-SA 4.0
2023-06-28T07:45:00.417Z
2023-06-28T16:20:44.743Z
2023-06-28T16:20:44.743Z
benrg
CC BY-SA 4.0
2023-06-28T10:21:35.350Z
You're right the examples didn't show proper closures, but it is what I'm after. I might have simplified the examples too much. And thanks for the const tip, it might be help.
BoppreH
CC BY-SA 4.0
2023-06-28T16:20:56.650Z
@BoppreH I added a paragraph about closures.
benrg
CC BY-SA 4.0
2023-06-28T16:30:00.733Z
If you put the example Python code inside a function then the lambda functions will be closures.
kaya3
CC BY-SA 4.0
2023-06-28T16:54:03.513Z
@kaya3-supportthestrike I didn't want to use Python because it's such a mess semantically. You'd have to make a lot of changes before this kind of optimization would be possible.
benrg
CC BY-SA 4.0
2023-06-28T16:55:12.850Z
I don't think the question is asking about any optimisation, it's asking if a language can have three particular features alongside each other. The only mention of optimisation in the question is an explanation of why early binding can be preferable to late binding, but this is still a semantic property of the language, not an optimisation.
kaya3
CC BY-SA 4.0
2023-06-28T17:17:51.150Z
@kaya3-supportthestrike That's fair, but I think if I rewrote my answer to make no mention of optimization, I'd be saying the same thing in a different way. I just tend to think of language semantics in terms of optimization opportunities, and of everything compilers do as a kind of optimization.
benrg
CC BY-SA 4.0
2023-06-28T18:25:00.057Z
That's a really interesting perspective! My comment about Python was really only to say that the example in the OP can be read as demonstrating closures if you imagine it's in a function body rather than at the top-level; it gets the idea across, at least.
kaya3
<p>You sure can. The big question is: when a function mentions the name of a variable or another function, does it see</p>
<ol>
<li>the static, known-at-compile-time value of the variable,</li>
<li>the run-time value that the variable had at the time that the <em>function definition</em> was executed, or</li>
<li>the run-time value that the variable has at the time that the <em>statement containing the variable</em> is executed?</li>
</ol>
<p>(For names that refer to functions, the &quot;value of the variable&quot; means the body or implementation of the function.)</p>
<p>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.</p>
<p>In your example of what you're looking at, the reference to <code>greeting_a</code> uses rule 2, and so you end up printing &quot;Hello.&quot; However, the reference to <code>say_b</code> inside of <code>say_a</code> can't use rule 2, because <code>say_b</code> hasn't been defined yet, so that reference has to use either rule 1 or rule 3.</p>
<p>As a language designer, you simply have to decide:</p>
<ul>
<li>Does mutual recursion work by using rule 1 or by using rule 3? Or do you offer <em>both</em> options to the programmer?</li>
<li>When does your language apply rule 2, and when does it apply one of the other rules? Some options include:
<ul>
<li>References to functions always use rule 1 or 3, and references to ordinary variables always use rule 2.</li>
<li>Variables can be marked either as &quot;static&quot; (using rule 1), &quot;mutable&quot; (using rule 2), or &quot;forward&quot; (using rule 3). The default is either &quot;static&quot; or &quot;mutable.&quot;</li>
<li>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.</li>
</ul>
</li>
</ul>

CC BY-SA 4.0
2023-06-28T22:56:27.083Z
2023-06-28T22:56:27.083Z
Sophie Swett
<p><s>Correct me if I'm wrong, but doesn't C# already have this feature? Here is your pseudocode translated to C#:</s></p>
<p>Correction: C# <em>almost</em> has this feature. As pointed out by Tanner Swett in the comments, this captures the <em>live</em> value of <code>greeting_a</code>, not the instantaneous one. So the output will be &quot;New Hello&quot; and not &quot;Hello&quot;. But it's still quite close and from language design perspective the changes required would not be monumental.</p>
<pre><code>string greeting_a = &quot;Hello&quot;;
Action say_a = null, say_b = null;

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

greeting_a = &quot;New Hello&quot;;
say_a();
</code></pre>

CC BY-SA 4.0
2023-06-27T23:50:47.153Z
2023-06-29T07:40:57.733Z
2023-06-29T07:40:57.733Z
Vilx-
CC BY-SA 4.0
2023-06-28T00:04:50.003Z
Put into words, this achieves forward references by having forward declarations, i.e. you declare `Action say_b = null;` at the start of the function, and then all references to the name `say_b` occur after the forward declaration, even if they occur before its implementation is provided.
kaya3
CC BY-SA 4.0
2023-06-28T10:25:58.437Z
This requires a little bit more work from the user, and that the compiler performs analysis of potentially null variables, but does seem to work.
BoppreH
CC BY-SA 4.0
2023-06-28T10:39:00.133Z
@BoppreH - I think you can reduce the amount of work done by the user by adding "hoisting" as seen in Javascript. Any variable declared later in a scope is actually available since the start of the scope, just with a `null`/`undefined` value.
Vilx-
CC BY-SA 4.0
2023-06-28T10:43:21.330Z
That said... are delegates in C# (aka "function pointers") a form of late binding? Because if so then this is not an example of what you wanted.
Vilx-
CC BY-SA 4.0
2023-06-28T22:58:31.330Z
This doesn't do what the asker asked for; this prints out "New Hello" for greeting A, but they were asking for it to print "Hello."
Sophie Swett
CC BY-SA 4.0
2023-06-28T22:59:47.787Z
Function pointers aren't [late binding](https://en.wikipedia.org/wiki/Late_binding), they are an example of [dynamic dispatch](https://en.wikipedia.org/wiki/Dynamic_dispatch).
kaya3
CC BY-SA 4.0
2023-06-29T07:35:33.033Z
@TannerSwett Hmm, thanks for pointing it out. It's a bit odd though, usually you want the opposite. :) But I suppose sometimes it's also useful to capture the momentary value.
Vilx-
<h1>Explicit early- vs late-binding</h1>
<p>Swift will let you immediately initialize only one of the closures, and you must explicitly defer initialization of the other:</p>
<pre class="lang-swift prettyprint-override"><code>let greetingA = &quot;Hello&quot;, greetingB = &quot;Hi&quot;

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

sayA()
</code></pre>
<p>The <code>!</code> at the end of the type is an <em>implicitly unwrapped optional</em> (IUO): It's mostly equivalent to an optional type (with <code>?</code>), but users of it can assume it will never be <code>nil</code>.</p>
<p>It may be preferable to have a dedicated keyword for this, such as Kotlin's <code>lateinit</code>, to avoid the sharp edges of IUO types (namely, that anyone else could come back and say <code>sayB = nil</code> later, and break <code>sayA</code>).</p>
<hr />
<p>If you want to capture the current value but also be able to mutate the variable out from under it, that comes to <em>by-value</em> vs <em>by-reference</em> captures:</p>
<pre class="lang-swift prettyprint-override"><code>var x = 1, y = 2
let printBoth = { [x] in print(&quot;x = \(x), y = \(y)&quot;) }
printBoth() // x = 1, y = 2
x = 2
y = 3
printBoth() // x = 1, y = 3
</code></pre>
<p>The <code>[x]</code> tells Swift to capture <code>x</code> by value instead of by reference. To capture both by-value, that would be <code>[x, y]</code>. Some languages, such as C++, require both by-value and by-reference captures to be explicit:</p>
<pre class="lang-cpp prettyprint-override"><code>int x = 1, y = 2;
auto printBoth = [x, &amp;y]() { printf(&quot;x = %d, y = %d\n&quot;, x, y); };
printBoth();
x = 2;
y = 3;
printBoth();
</code></pre>

CC BY-SA 4.0
2023-06-27T15:32:19.497Z
2023-06-28T15:44:46.010Z
2023-06-28T15:44:46.010Z
Bbrk24
CC BY-SA 4.0
2023-06-29T00:45:43.667Z
"but users of it can assume it will never be nil." other way around: It _can_ be nil, but users _are assuming_  it will never be nil. Not quite assuming either, but asserting.
Alexander
<p>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.</p>
<p>As this is not a language-specific question, and as my Python is very rusty now, I will give initial examples in <a href="https://racket-lang.org/" rel="nofollow noreferrer">Racket</a>, although they should be portable Scheme modulo using <code>λ</code> instead of <code>lambda</code>.  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.</p>
<p>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 <em>not</em> 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.</p>
<p>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.</p>
<h2>The first approach: <code>letrec</code></h2>
<p>Scheme has a construct called <code>letrec</code> which allows you to bind names to objects – usually procedures – which can refer to each other.  Although <code>letrec</code> is a primitive part of the language, it is clear how it is implemented (in particular the implementation is described on p16 of <a href="https://small.r7rs.org/attachment/r7rs.pdf" rel="nofollow noreferrer">the current standard</a> (PDF link)), and it's possible to implement a simple version of it.  Here is how it works</p>
<pre class="lang-scheme prettyprint-override"><code>(letrec ((var1 val1) (var2 val2))
  form ...)
</code></pre>
<p>does the following:</p>
<ol>
<li>first bind <code>var1</code>, <code>var2</code>, ... to some kind of special <code>unspeakable</code> value or values;</li>
<li>Then <em>assign</em> <code>val1</code> to <code>var1</code>, <code>val2</code> to <code>var2</code>, and so on;</li>
<li>evaluate the body.</li>
</ol>
<p>Now you can see that, at the point where <code>val1</code> is evaluated, <em>all of the variables are already bound</em>: 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.</p>
<p>So, in Scheme</p>
<pre><code>(letrec ((p1 (λ (...) ... (p2 ...) ...))
         (p2 (λ (...) ... (p2 ...) ...)
  (p1 ...))
</code></pre>
<p>turns into</p>
<pre><code>(let ((p1 &lt;unspeakable&gt;)
      (p2 &lt;unspeakable&gt;))
  (set! p1 (λ (...) ... (p2 ...) ...))
  (set! p2 (λ (...) ... (p2 ...) ...))
  (p1 ...))
</code></pre>
<p>And in fact, since Scheme (or Racket) has a macro system, you can <em>write</em> a version of <code>letrec</code> in it.  Here is that in Racket (I have called it <code>rlet</code> to avoid clobbering <code>letrec</code>:</p>
<pre><code>(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 ...)]))
</code></pre>
<p>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):</p>
<pre><code>(define (make-countdown x)
    (rlet ((r1 (λ (it)
                 (displayln it)
                 (if (&lt;= it x)
                     x
                     (r2 (- it 1)))))
           (r2 (λ (it)
                 (r1 it))))
    r1))
</code></pre>
<p>You can use Racket's macro expansion tool to see that the definition of <code>make-countdown</code> is turned into what you would expect:</p>
<pre><code>(define (make-countdown x)
  (let ((r1 undefined) (r2 undefined))
    (set! r1 (λ (it) (displayln it) (if (&lt;= it x) x (r2 (- it 1)))))
    (set! r2 (λ (it) (r1 it)))
    r1))))
</code></pre>
<p>And we can now test this</p>
<pre><code>&gt; (make-countdown 10)
#&lt;procedure:r1&gt;
&gt; ((make-countdown 10) 20)
20
19
18
17
16
15
14
13
12
11
10
10
</code></pre>
<p>(The <code>10</code> is printed twice: once by <code>displayln</code> and once because it's the value).</p>
<p>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 <em>without</em> assignment?</p>
<h2>Without assignment</h2>
<p>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).</p>
<p>The trick is that <em>you can pass a procedure as an argument to a procedure</em>, and then call it.  So consider this fragment:</p>
<pre class="lang-scheme prettyprint-override"><code>(λ (c it)
  (if (&lt;= it x)
      x
      (c c (- it 1))))
</code></pre>
<p>This is a procedure which takes two arguments:</p>
<ul>
<li><code>c</code>, a procedure</li>
<li><code>it</code>, a number</li>
</ul>
<p>It then tests <code>it</code> against some variable <code>x</code>, and if it's more than it it calls <code>c</code> passing it two arguments: <code>c</code> itself and a value one less than <code>x</code>.</p>
<p>Well, the trick is, of course, that we're going to make <code>c</code> be <em>this procedure itself</em>.  We can also wrap this up so the procedure we call only takes the one argument we care about:</p>
<pre class="lang-scheme prettyprint-override"><code>(let ((r (λ (c it)
           (if (&lt;= it x)
               x
               (c c (- it 1))))))
  (λ (it) (r r it)))
</code></pre>
<p>And, just to be completist about this, <code>let</code> itself is of course just syntactic sugar for λ: the above is equivalent to this:</p>
<pre class="lang-scheme prettyprint-override"><code>((λ (r)
   (λ (it) (r r it)))
 (λ (c it)
   (if (&lt;= it x)
       x
       (c c (- it 1)))))
</code></pre>
<p>(I won't do that again because it makes things unreadable, but it's important that it can be done.)</p>
<p>Well, we need to wrap this up in a 'maker' procedure again to bind <code>x</code>:</p>
<pre class="lang-scheme prettyprint-override"><code>(define (make-countdown x)
  (let ((r (λ (c it)
             (displayln it)
             (if (&lt;= it x)
                 x
                 (c c (- it 1))))))
    (λ (it) (r r it))))
</code></pre>
<p>And now</p>
<pre><code>&gt; ((make-countdown 1) 3)
3
2
1
1
</code></pre>
<p>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:</p>
<pre class="lang-scheme prettyprint-override"><code>(define (make-countdown x)
  (let ((r1 (λ (c1 c2 it)
             (displayln it)
             (if (&lt;= it x)
                 x
                 (c2 c1 c2 it))))
        (r2 (λ (c1 c2 it)
              (c1 c1 c2 (- it 1)))))
    (λ (it) (r1 r1 r2 it))))
</code></pre>
<p>And this works the same way, with <code>r1</code> doing the print and test, and <code>r2</code> doing the decrementing.</p>
<p>So this approach does not use late binding, and does not use assignment.  And is moderately painful, of course.</p>
<h2>The second approach in Python</h2>
<p>Finally, here is the last function expressed as Python.  Note that I've used <code>def</code> to express the local functions: you <em>can</em> do it all with <code>lambda</code>s but it's very painful.</p>
<pre class="lang-python prettyprint-override"><code>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))
</code></pre>
<p>And here is that working:</p>
<pre><code>&gt;&gt;&gt; (mc(0))(2)
(mc(0))(2)
2
1
0
0
</code></pre>
<p>OK.</p>

CC BY-SA 4.0
2023-06-30T09:16:51.897Z
2023-06-30T13:29:56.663Z
2023-06-30T13:29:56.663Z
ignis volens
CC BY-SA 4.0
2023-06-30T09:33:47.383Z
Exactly! And in the graph-reduction implementations of the pure FP there's also some witchcraft possible to do it in a bit more optimal way: http://ix.cs.uoregon.edu/~ariola/cycles.pdf
SK-logic
<p>This doesn't require <a href="https://en.wikipedia.org/wiki/Late_binding" rel="noreferrer">late binding</a>, just <a href="https://en.wikipedia.org/wiki/Forward_declaration#Forward_reference" rel="noreferrer">forward references</a>. That is, the name <code>say_b</code> appears in the code before it's declared.</p>
<p>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.</p>

CC BY-SA 4.0
2023-06-27T15:49:56.933Z
2023-06-27T15:49:56.933Z
kaya3
CC BY-SA 4.0
2023-06-27T16:00:49.363Z
That's how I'd implement the "functions as global constants" scenario, but is it compatible with closures? If all declarations are found in advance, I'd expect the compiler to incorrectly accept `f = lambda: print(a); f(); a = 5`, where `a` is used before assignment.
BoppreH
CC BY-SA 4.0
2023-06-27T16:09:55.907Z
@BoppreH Early binding means the expression `a` in `print(a)` is bound to the declaration of the variable `a` at compile-time, i.e. that name means that variable. It doesn't mean that the variable must be captured by value; the variable's value can change and the closure can see the change, because the expression `a` refers to that variable whose value has changed. Resolving names to declarations at compile-time does not mean resolving names to values at compile-time.
kaya3
CC BY-SA 4.0
2023-06-27T17:37:43.320Z
That's one way to implement it. Mutating values from under other functions feels icky, hence my preference for capture-by-value. But thank you, it's a good suggestion and may be better than sacrificing the other properties.
BoppreH
CC BY-SA 4.0
2023-06-27T17:49:49.287Z
@BoppreH I think you have misunderstood. There is nothing about my answer which requires that closures must be able to mutate the variables they capture. However, in your quesiton you say that you want closures to be able to *see* mutations in those variables, which means you want to capture them by reference, not by value. Capturing by value would give you "Hello" instead of "New Hello" in your example, because the value "Hello" would be what gets captured when the closure is declared. OTOH, it's perfectly possible to capture by reference and also forbid mutation through that reference.
kaya3
CC BY-SA 4.0
2023-06-27T20:56:44.833Z
The 'Hello' is precisely what I want. I'd like the closure to have a *fixed* view of the variables, as if every new declaration was a new variable, like a high-level SSA. But I understand this is an unusual property, so I didn't want to dwell on it too much, and I'm willing to part with it.
BoppreH
CC BY-SA 4.0
2023-06-27T21:01:47.077Z
@BoppreH Then I misunderstood your question, but my answer doesn't change. It just means you capture by value instead of by reference. You still don't need late binding to support forward references.
kaya3
CC BY-SA 4.0
2023-06-27T21:09:39.450Z
Note that the problem of accessing an uninitialised variable through a closure can occur even without forward references, e.g. `let a; let f = () -> print(a); f(); a = 4;` doesn't make use of a forward reference to `a`. So you need to address this problem regardless. There are type-theoretic approaches that would ensure `f` can only be called after `a` is definitely assigned, or you could just give `a` a default initial value; I think it's beyond the scope of this question, though.
kaya3
CC BY-SA 4.0
2023-06-28T07:50:28.190Z
It can be a real can of worms. Imagine this variable `a` exists in an outer scope and resolved from there, yet user expects the late bound definition to be picked up instead. Only explicit letrec saves from such scenarios.
SK-logic
# Early binding, mutual recursion, closures. Can I have all three?
Posted by: username_0 on 2023-06-27
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)
**Tags:** recursion variables closure
> **Comments:**
> **username_1**: all you need is an explicit `letrec` implementation, which is quite trivial.  
> **username_0**: @SK-logic I'd prefer if this limitation was transparent to the user, as it is in late-binding languages. But yeah, that's a good plan B.  
> **username_2**: You can do this with lazy evaluation, like Haskell, but I think your definition of early/late binding is kind of fuzzy so I don't know which side you'd say this falls on.  
> **username_1**: I believe this kind of late binding requires dynamic scope and is not really possible with any sound lexical scoping  
> **username_3**: I would argue that Python has early binding, but it is binding the variable and not the value of the variable at the time the closure is created.  
> **username_4**: I have the same problem in my language  
---
## 6 answers
### Answer by username_6 on 2023-06-27. Score: 14 | Accepted answer
This doesn't require [late binding](https://en.wikipedia.org/wiki/Late_binding), just [forward references](https://en.wikipedia.org/wiki/Forward_declaration#Forward_reference). 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.
> **Comments:**
> **username_0** (2023-06-27): That's how I'd implement the "functions as global constants" scenario, but is it compatible with closures? If all declarations are found in advance, I'd expect the compiler to incorrectly accept `f = lambda: print(a); f(); a = 5`, where `a` is used before assignment.  
> **username_6** (2023-06-27): @BoppreH Early binding means the expression `a` in `print(a)` is bound to the declaration of the variable `a` at compile-time, i.e. that name means that variable. It doesn't mean that the variable must be captured by value; the variable's value can change and the closure can see the change, because the expression `a` refers to that variable whose value has changed. Resolving names to declarations at compile-time does not mean resolving names to values at compile-time.  
> **username_0** (2023-06-27): That's one way to implement it. Mutating values from under other functions feels icky, hence my preference for capture-by-value. But thank you, it's a good suggestion and may be better than sacrificing the other properties.  
> **username_6** (2023-06-27): @BoppreH I think you have misunderstood. There is nothing about my answer which requires that closures must be able to mutate the variables they capture. However, in your quesiton you say that you want closures to be able to *see* mutations in those variables, which means you want to capture them by reference, not by value. Capturing by value would give you "Hello" instead of "New Hello" in your example, because the value "Hello" would be what gets captured when the closure is declared. OTOH, it's perfectly possible to capture by reference and also forbid mutation through that reference.  
> **username_0** (2023-06-27): The 'Hello' is precisely what I want. I'd like the closure to have a *fixed* view of the variables, as if every new declaration was a new variable, like a high-level SSA. But I understand this is an unusual property, so I didn't want to dwell on it too much, and I'm willing to part with it.  
> **username_6** (2023-06-27): @BoppreH Then I misunderstood your question, but my answer doesn't change. It just means you capture by value instead of by reference. You still don't need late binding to support forward references.  
> **username_6** (2023-06-27): Note that the problem of accessing an uninitialised variable through a closure can occur even without forward references, e.g. `let a; let f = () -> print(a); f(); a = 4;` doesn't make use of a forward reference to `a`. So you need to address this problem regardless. There are type-theoretic approaches that would ensure `f` can only be called after `a` is definitely assigned, or you could just give `a` a default initial value; I think it's beyond the scope of this question, though.  
> **username_1** (2023-06-28): It can be a real can of worms. Imagine this variable `a` exists in an outer scope and resolved from there, yet user expects the late bound definition to be picked up instead. Only explicit letrec saves from such scenarios.  
---
### Answer by username_5 on 2023-06-28. Score: 9
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.
> **Comments:**
> **username_0** (2023-06-28): You're right the examples didn't show proper closures, but it is what I'm after. I might have simplified the examples too much. And thanks for the const tip, it might be help.  
> **username_5** (2023-06-28): @BoppreH I added a paragraph about closures.  
> **username_6** (2023-06-28): If you put the example Python code inside a function then the lambda functions will be closures.  
> **username_5** (2023-06-28): @kaya3-supportthestrike I didn't want to use Python because it's such a mess semantically. You'd have to make a lot of changes before this kind of optimization would be possible.  
> **username_6** (2023-06-28): I don't think the question is asking about any optimisation, it's asking if a language can have three particular features alongside each other. The only mention of optimisation in the question is an explanation of why early binding can be preferable to late binding, but this is still a semantic property of the language, not an optimisation.  
> **username_5** (2023-06-28): @kaya3-supportthestrike That's fair, but I think if I rewrote my answer to make no mention of optimization, I'd be saying the same thing in a different way. I just tend to think of language semantics in terms of optimization opportunities, and of everything compilers do as a kind of optimization.  
> **username_6** (2023-06-28): That's a really interesting perspective! My comment about Python was really only to say that the example in the OP can be read as demonstrating closures if you imagine it's in a function body rather than at the top-level; it gets the idea across, at least.  
---
### Answer by username_9 on 2023-06-27. Score: 8
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();
> **Comments:**
> **username_10** (2023-06-29): "but users of it can assume it will never be nil." other way around: It _can_ be nil, but users _are assuming_  it will never be nil. Not quite assuming either, but asserting.  
---
### Answer by username_7 on 2023-06-28. Score: 7
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 by username_8 on 2023-06-27. Score: 7
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();
> **Comments:**
> **username_6** (2023-06-28): Put into words, this achieves forward references by having forward declarations, i.e. you declare `Action say_b = null;` at the start of the function, and then all references to the name `say_b` occur after the forward declaration, even if they occur before its implementation is provided.  
> **username_0** (2023-06-28): This requires a little bit more work from the user, and that the compiler performs analysis of potentially null variables, but does seem to work.  
> **username_8** (2023-06-28): @BoppreH - I think you can reduce the amount of work done by the user by adding "hoisting" as seen in Javascript. Any variable declared later in a scope is actually available since the start of the scope, just with a `null`/`undefined` value.  
> **username_8** (2023-06-28): That said... are delegates in C# (aka "function pointers") a form of late binding? Because if so then this is not an example of what you wanted.  
> **username_7** (2023-06-28): This doesn't do what the asker asked for; this prints out "New Hello" for greeting A, but they were asking for it to print "Hello."  
> **username_6** (2023-06-28): Function pointers aren't [late binding](https://en.wikipedia.org/wiki/Late_binding), they are an example of [dynamic dispatch](https://en.wikipedia.org/wiki/Dynamic_dispatch).  
> **username_8** (2023-06-29): @TannerSwett Hmm, thanks for pointing it out. It's a bit odd though, usually you want the opposite. :) But I suppose sometimes it's also useful to capture the momentary value.  
---
### Answer by username_11 on 2023-06-30. Score: 7
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:

first bind var1, var2, ... to some kind of special unspeakable value or values;
Then assign val1 to var1, val2 to var2, and so on;
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 )
      (p2 ))
  (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)
#
> ((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.
> **Comments:**
> **username_1** (2023-06-30): Exactly! And in the graph-reduction implementations of the pure FP there's also some witchcraft possible to do it in a bit more optimal way: http://ix.cs.uoregon.edu/~ariola/cycles.pdf  
---
