Discontiguous Lexical Scope for Multiply Dispatched Functions

General Usage
, ,
1

I would like to create a closure that binds free variables with respect to a discontiguous “lexical environment” that encapsulates both the disparate method implementations and collective reference to a multiply-dispatched function. Concretely, I’d like to do something like the following:

function f(x::Integer)
  x + a
end

function f(x::Float64)
  x * a
end

function g()
  a = 5
  f
end

When invoked (eg, via g()(3.0)), this fails with the error:

ERROR: UndefVarError: a not defined

On the other hand, if I define all methods of the closure locally within a single encompassing code block, the technique works:

function h()
  a = 5
  f(x::Integer) = x + a
  f(x::Float64) = x * a
  f
end

Then h()(3) yields 8 and h()(3.0) yields 15.0, as expected.

The first example would work if I were to assign a value to the function’s free variable (a) in the same scope as the definition of the function:

a = 5

function f(x::Integer)
  x + a
end

function f(x::Float64)
  x * a
end

function g()
  a = -9999
  f
end

Now, g()(3) yields 8 and g()(3.0) yields 15.0, as h does in the second example. The value of a assigned internally to g (ie, via a = -9999) is completely ignored, however. In this third example, I would have expected the later, “closer” assignment (of -9999 here) to have shadowed over the assignment in the top-level scope.

Why does Julia not bind free variables the same way in the first and second cases? Since it is discernible from an exclusively textual / lexical reading of the code what encompassing scope is intended by the first example, it seems to me that the approach would be consistent with the spirit of the language being lexically scoped. There is an organizational advantage to being able to extend methods in different sections of the code — ie, in different modules, etc — but I was unable to do this without losing the centralized binding of the free variable in the encompassing function g, as desired. Is there an alternate way to achieve the kind of closure envisioned without sacrificing the ability to move method definitions to ad-hoc locations elsewhere in the code?

2

In the first and last examples, the a in the two f methods is global and the a in g is a local—they are completely unrelated variables; accordingly, changing one has no effect on the other. This is the entire purpose of scope in programming languages. When the f methods are defined inside of h they all the a are the same local variable. It is very intentional that local variables cannot be affected by distant, unrelated code that you cannot even see the existence. If this were not the case, they would be as bad as globals from the perspective of being impossible for both humans and compilers to reason about.

3

Thank you for the response. Just a couple follow-up questions.

Why does a not become local in the f methods when it is “seen” in the context of g? Like a context-dependent local vs global designation instead of always one or the other?

Certainly the aim is for intelligible, readable code, but is it really the case in this example that g is distant / unrelated to f? When f appears in the context of g, they’re quite related: one has subsumed the other. On the other hand, when f is invoked totally apart from g, as you say, they have no relation at all. It seems to me that the two cases are distinct. Not sure such a distinction could be made in a compiler, though, since I have no experience there.

4

I don’t understand what this question means, but the a in the f methods is global because a is never assigned in the scope of the methods (so what else could it be?). In g on the other hand, a is assigned and is therefore local. A local variable and a global variable can never be the same variable. They are unrelated variables that happen to have the same name.

Are you suggesting that when f is called near g the meaning of a inside of f should be different?

The whole point of local scope is that it is local; if it was “discontiguous” it would not be local. Why is local good? Because you can look at a limited block of code in isolation and understand what it does: you can see every assignment and every usage. If the meaning of a function’s code changed when it was called near some other function, that would be, frankly, bonkers. If it was possible to “open up” a local scope and make changes to it, then it would lose all the benefits of localness.

There is a mechanism for letting local variables to be modified from elsewhere, which is closures: you can define a function which closes over a local variable and modifies it and call the closure somewhere else.

1 Like
5

Perhaps a key insight here is that the names of functions aren’t special. They’re also just names, just like how the a in a = 5 is a name. The names of functions can either be globals or locals. You can even decide you have a better name for f and decide to use do_math = f. No matter how or where you refer to a function, you’re talking about a concrete thing — the function itself — that already exists independently of the name you use for it.

So there’s nothing special that happens when you use the name of a function, just like there’s nothing special about using a name of an integer or an array.

1 Like
6

This is certainly true, however not everyone uses the phrase “local scope.” Many, it seems, prefer “lexical scope,” which I guess I’m arguing might be a superset of local scope. This specific case (a closure constituted by the enclosed free variables and some disparately implemented methods of a multiply-dispatched function) being the only example I can think of to demonstrate the (symmetric) difference. In symbols:

LEX ⊃ LOC
DISCONTIG ∊ (LEX ∆ LOC)

This excellent blog post goes a bit deeper into the challenges of providing precise definitions for lexical and dynamic scoping. It also references Common Lisp the Language, wherein Guy Steele defines lexical scope as meeting the following property:

references to the established entity can occur only within certain program portions that are lexically (that is, textually) contained within the establishing construct

On the surface, this definition does seem to quash the notion of “discontiguous” lexical scopes, but I’d argue that we could just expand the reading of “the establishing construct” to be a little more broad than regular, old-fashioned, block-local scope. Still very limited in scope, and by no means “global,” however. (I don’t think my first example opens Pandora’s box in terms of breadth of scope: g’s scope is just another block. Add that block to the block(s) containing the two f methods, and you have 3 blocks, the union of which constitute the proposed discontiguous lexical scope of f. Much less than what Steele calls the “indefinite” scope.)

That said, the concern that this becomes less readable is absolutely warranted and should be the foremost criteria in any decision about what constitutes lexical scope. That seems to me to be an entirely subjective determination, but nonetheless one that is unlikely to preclude something approaching consensus. In the manual, we read:

a function’s scope does not inherit from its caller’s scope, but from the scope in which the function was defined

But when is that function defined, exactly? We can see clearly where its methods are, but the whole multiply dispatched function is never really defined as a consolidated entity anywhere! That’s kind of the point of multiple dispatch, as I understand it. (A major language innovation, IMO, totally Turing worthy.) In my earlier version of a MWE, I had the two fs in two different modules, both importing a third, base module, wherein an empty method definition is made. This is actually the pattern I’m going for in my code. I just like doing it that way: sort of like a “bring your own method” style of decentralized programming. But I was sad to lose closures along the way, motivating my post. Anyway, in my understanding, multiple dispatch opens up the possibility of disparate lexical scopes: why else, or previously, would anyone have ever considered such a bizarre (and arguably byzantine) notion?

Not exactly. Yes, to the second half of the question (“the meaning should be different”: to your later point, this is exactly why we use closures), but no to the first half (“f is called near to a”). “Nearness” would be entirely subjective, and therefore hard to understand and totally :100:% bonkers. However, in this specific case, g creates a local scope with a in it. f refers to a non-locally-defined a. Seems like a match made in heaven, but alas, “never in Julia the twain shall meet.” (jk :grinning: I still love you Julia!) For the first and third examples, this kind of means that a is “global,” but in this context, “global” just means not local, so we’re caught in something of a logical tautology.

Actually, I’m not really sure that the “global” designation is well defined at all: when a is captured by f in the closure of the second original example above, it is not global, but when it fails to be captured in the first example, it is global. So, the compiler’s decision determines whether a is global? The situation isn’t exactly a tautology, but it does seem like the “tail wagging the dog”: humans tell the compiler how to interpret things, not the other way around. Obviously, if the compiler won’t change, we’re stuck with its designations. But that doesn’t mean we shouldn’t question its assumptions, nor that its interpretation of “global” is the meaning shared by a global audience of programmers. Pedagogically we teach the term, a priori and ab initio, not any one language’s read on it.

As it turns out, in the context of Julia, “global” just means local to the module that the variable is in. So if “local” is taken to mean limited in scope of applicability, and “global” is the least limited in scope, but still happens to be limited in scope as just mentioned, then by the transitive axiom, everything must be local (to something) in Julia.

7

Yep.

It’s easier to reason about the other way around — your function h() contains the expression a = 5. That introduces the name a as a local variable in h’s local scope. Note that order doesn’t matter — the key is the existence of the assignment in that scope. This also works as you hope:

function h()
    f(x::Integer) = x + a
    f(x::Float64) = x * a
    a = 5
    f
end

If I don’t have any assignments to a in that h() definition, then it must belong to the scope where that h method is defined — whether it already exists or not.

Of course you could dream up other languages that do other things. But this is how Julia does it.

8

If I’m understanding this correctly, I think you can achieve what you want by manually using the mechanism by which closures are implemented under the hood, namely callable structs:

code 
module A
    struct F{T}
        a::T
    end
end

module B
    import ..A: F

    function (f::F)(x::Integer)
        return x + f.a
    end
end

module C
    import ..A: F

    function (f::F)(x::Float64)
        return x * f.a
    end
end

using .A: F

function g()
    a = 5
    return F(a)
end

EDIT: Better yet, use a regular two-argument function and wrap a closure around it at the return point. Requires less code and gives you proper closure semantics if a is reassigned.

module A
    function f end
end

module B
    import ..A: f
    f(x::Integer, a) = x + a
end

module C
    import ..A: f
    f(x::Float64, a) = x * a
end

using .A: f

function g()
    a = 5
    return x -> f(x, a)
end

In either case:

julia> include("code.jl")
g (generic function with 1 method)

julia> g()(3)
8

julia> g()(3.0)
15.0

I suppose this is rather obvious, so apologies if it’s not helpful, but it seems like the way to accomplish your “bring your own method” goal. The capturing of variables must happen in a scope where said variables are defined, but you can decentralize everything else about the implementation.

5 Likes
9

…and if you’d rather avoid writing out the closure definition at the return point, macros can help with that. You can add the following to module A,

macro f()
    return :(x -> f(x, $(esc(:a))))
end

and use it like this:

using .A: @f

function g()
    a = 5
    return @f
end

This isn’t very nice to the readers of your code, as it obfuscates how the return from g() depends on a, but it works.

I suppose metaprogramming may be the actual answer to your scoping question. You want to capture a name instead of a value, and only evaluate the binding of that name to a value at a later point and in a different scope. Working on names is what macros do.

10

On the contrary, I totally missed it, so thank you! It does seem super obvious in hindsight. I think I was so determined to create the closure in the f methods that I was blinded to the possibility of pulling it up into the higher order g.

The other approach using callable structs was something I didn’t know about at all. Apparently I skipped the “methods” chapter in the manual. It’s really interesting that that is how the compiler builders implement closures.

2 Likes