Closure Self-Reference in Madeup
Madeup is a language for expressing the construction of 3-D objects. It borrows heavily from Logo, with extra instructions for generating triangular meshes fitted around the stops the turtle makes. I’m very interested in making a RERL (the unpronounceable read-eval-render-loop) for Madeup that runs on mobile devices.
Typing on mobile devices is not fun, so I’ve stripped away as much punctuation and keywords as possible. One path to brevity is to use closures. When I define a function, some variables are left undefined within the function definition itself. For example:
wave x = amplitude * sin (shift + x)
The function wave leaves the bindings for amplitude and shift free. Where do they get their values? They’re not local variables nor are they parameters. Their definitions come from the surrounding environment:
amplitude = 10
shift = pi / 2
wave x = amplitude * sin (shift + x)
If I didn’t let functions reach into their surrounding environment, I’d have to pass more parameters to provide values for these free variables. That means more typing and more line wrapping on mobile devices. This is something I want to avoid. (Alternately, I could define them locally, which would frustrate my desire to share global data, or I could use some sort of dynamic scope, in which a function pulls its free bindings from the calling environment, not the defining one. Dynamic scoping is too weird for me.)
A function that inherits the bindings of its surrounding scope is called a closure. One could say that a closure is a code-environment pair.
I thought I had closures all figured out in Madeup. Whenever I saw an assignment statement during parsing, I’d form a closure marrying the current environment with the right-hand side expression of the assignment. (At present, the closure’s environment is a copy of the surrounding one.) For example, suppose I had this two-line program:
x = 0
x = x + 1
I’d make two closures. When I saw x = 0, I’d make this closure for the right-hand side:
Environment: nothing
Expression: (INTEGER 0)
No bindings were in the environment by the time I hit this statement, so the environment is empty. Then I’d bind this closure to identifier x and throw it in the current environment. Next I’d hit the second statement and create a closure for x + 1:
Environment: x -> (INTEGER 0)
Expression: (+ (call x) 1)
I’d bind this closure to identifier x in the current environment. Since my closures always got copies of the environment, altering the binding for x didn’t affect the bindings inside the closure. On execution, I’d get (+ (call x) 1) -> (+ 0 1) -> 1 as I expected.
However, when I tried to write something recursively, my scheme ran afoul. If I wrote:
fib n = if n <= 2 1 else fib (n - 1) + fib (n - 2)
Then my closure would be:
Environment: nothing
Expression: (if (<= n 2)
(INTEGER 1)
(+ (call fib (- n 1))
(call fib (- n 2)))
I bound this closure to fib. When I called fib, its parameter got added to the closure’s otherwise empty environment as n. But there was still a free binding: fib! The recursive call failed.
I thought, “Okay, I’ll just create the closure, bind it, and then add that binding to the environment of the closure I just made. That binding didn’t exactly exist at the time the closure was formed, but it was close… And how else am I going to support recursion?” With this tweak, my closure looked like this after the assignment statement:
Environment: fib -> (if (<= n 2)
(INTEGER 1)
(+ (call fib (- n 1))
(call fib (- n 2)))
Expression: (if (<= n 2)
(INTEGER 1)
(+ (call fib (- n 1))
(call fib (- n 2)))
This worked great for my Fibonacci problem. However, then I looked back at my original problem:
x = 0
x = x + 1
When I executed this, I formed this closure for the first statement:
Environment: x -> (INTEGER 0)
Expression: (INTEGER 0)
Nothing gained nor lost on this one. The expression doesn’t reference the binding. However, the second closure became:
Environment: x -> (+ (call x) 1)
Expression: (+ (call x) 1)
This closure got bound to x. Evaluating x meant evaluating this expression:
(+ (call x) 1)
That expression has a (call x) in it, so I looked up x in the closure’s environment. That environment told me I needed to evaluate this expression to get the value of x:
(+ (call x) 1)
That expression has a (call x) in it, so I looked up x in the closure’s environment. That environment told me I needed to evaluate this expression to get the value of x:
(+ (call x) 1)
You get the idea.
It seems I need to treat the formation of a closure’s environment differently if I intend the function to be recursive. Sometimes I want self-reference to mean “refer to my previous binding.” Other times I want self-reference to mean “refer to myself, as I am currently bound.”
My current temporary fix is to not add the binding of the closure to the closure’s own environment if that closure already has a binding for that identifier. That is, the closure for x = x + 1 only sees the previous binding x = 0.
I’m really not sure how I can better handle self-referencing closures.