Issue with rewriting by projecting out the body of a loop

New to Julia
1

inspired by this observation Local variable inside a loop: why it ERRORs - #6 by sgaure, I come up with this comparative test, and wonder why they lead to distinct result

function test()
    v = Function[]
    for i = 1:3
        function f()
            println(i)
        end
        push!(v, f)
    end
    map(x -> x(), v)
    function f()
        println("single-out")
    end
end
test(); # single-out \n single-out \n single-out

function test()
    function surrogate(i)
        function f()
            println(i)
        end
        push!(v, f)
    end
    v = Function[]
    for i = 1:3
        surrogate(i)
    end
    map(x -> x(), v)
    function f()
        println("single-out")
    end
end
test(); # 1 \n 2 \n 3
1 Like
2

Here is my understanding of it: Function definitions inside functions are hoisted out of the function body. The function

function test()
    f() = println(1)
    f()
    f() = println(2)
end

is equivalent to

f() = println(1)
f() = println(2)

function test()
    f()
end

up to renaming f to some unique identifier. Since in your second example the two definitions of f sit inside different function bodies, they get different names and therefore don’t interfere.
Note that for your first version you get the message

WARNING: Method definition f() in module Main at REPL[1]:4 overwritten at REPL[1]:10.

but not for the second one.

1 Like
3

The f in surrogate and trailing f should be the same variable per the scoping rules regarding reassignments of outer local variables. They weren’t because method definitions were overwritten, which is undefined behavior. The 2nd test just manages to dodge the warning via surrogate calls, and I’d argue the warning should still happen.

It’s still not actually clearly specified what is allowed, and presumably it’s because nobody has yet figured out what can be allowed. The documentation currently warns against “local methods conditionally or subject to control flow”, but the runtime warning actually shows up when there are no control flow expressions at all:

julia> g = let i = 1
        f() = i
        f() = 0
        f
       end
WARNING: Method definition (::Main.var"#f#67"{i})() in module Main at REPL[32]:2 overwritten at REPL[32]:3.
(::var"#f#67"{Int64}) (generic function with 1 method)

julia> g.i, g() # closure holds the captured i=1, but uses the method without i
(1, 0)

Note that the undefined behavior can differ between let blocks and function blocks, so don’t use those interchangeably in further experiments.

This is the relevant issue, this thread could eventually have something to contribute there: disallow methods of local functions in different blocks · Issue #15602 · JuliaLang/julia. It says almost right away that nested function’s method tables are intended to be hoisted out of the outer functions to the top level, as matthias314 described, for practical performance, so in other words, the method tables aren’t intended to vary after the outer function definition, let alone throughout function calls. It’s possible this could be relaxed for some dynamic feature discovered to be acceptable, but for the moment, I’d steer clear of any method overwriting in local scopes, similar to how method overwriting isn’t allowed in precompilable modules anymore, in addition to conditional non-overwriting methods. It’s worth noting that a method definition inside a loop is not an iteration-wise redefinition, just different iteration-wise instances of the function capturing different iteration-wise variables.

3 Likes
4

Defining a function as

function f()
    ...
end

does not follow the same rules as variable assignment f = .... Your first example, without surrogate works differently with variable assignment, even though the f here is is the same within the loop and outside. (In the surrogate case, the f is boxed, as it should be).

function test()
    v = Function[]
    for i = 1:3
        f = () -> println(i)
        push!(v, f)
    end
    map(x -> x(), v)
    f = () -> println("single-out")
end
test(); # 1 2 3

As discussed in the github-thread Benny links to, defining a named function f() involves creating a method table for the function to use for storing different methods of the function, and this is somewhat complicated to handle in the general case. There are some unresolved issues with such definitions.

Anyway, we can have a look at what happens inside your first example, the non-surrogate:

julia> @code_warntype test()
MethodInstance for test()
  from test() @ Main REPL[18]:1
Arguments
  #self#::Core.Const(Main.test)
Locals
  #8::var"#test##19#test##20"
  @_3::Union{Nothing, Tuple{Int64, Int64}}
  f::var"#f#test##18"
  v::Vector{Function}
  i::Core.Box
Body::var"#f#test##18"
1 ─       Core.NewvarNode(:(#8))
│         Core.NewvarNode(:(f))
│   %3  = Main.Function::Core.Const(Function)
│         (v = Base.getindex(%3))
│   %5  = Main.:(:)::Core.Const(Colon())
│   %6  = (%5)(1, 3)::Core.Const(1:3)
│         (@_3 = Base.iterate(%6))
│   %8  = @_3::Core.Const((1, 1))
│   %9  = (%8 === nothing)::Core.Const(false)
│   %10 = Base.not_int(%9)::Core.Const(true)
└──       goto #4 if not %10
2 ┄       (i = Core.Box())
│   %13 = @_3::Tuple{Int64, Int64}
│   %14 = Core.getfield(%13, 1)::Int64
│   %15 = i::Core.Box
│         Core.setfield!(%15, :contents, %14)
│   %17 = Core.getfield(%13, 2)::Int64
│   %18 = Main.:(var"#f#test##18")::Core.Const(var"#f#test##18")
│   %19 = i::Core.Box
│         (f = %new(%18, %19))
│   %21 = Main.push!::Core.Const(push!)
│   %22 = v::Vector{Function}
│   %23 = f::var"#f#test##18"
│         (%21)(%22, %23)
│         (@_3 = Base.iterate(%6, %17))
│   %26 = @_3::Union{Nothing, Tuple{Int64, Int64}}
│   %27 = (%26 === nothing)::Bool
│   %28 = Base.not_int(%27)::Bool
└──       goto #4 if not %28
3 ─       goto #2
4 ┄ %31 = Main.map::Core.Const(map)
│   %32 = Main.:(var"#test##19#test##20")::Core.Const(var"#test##19#test##20")
│         (#8 = %new(%32))
│   %34 = #8::Core.Const(var"#test##19#test##20"())
│   %35 = v::Vector{Function}
│         (%31)(%34, %35)
│   %37 = f::var"#f#test##18"
└──       return %37

In block 2, we can see what’s happening inside the loop. The i (which actually is boxed) is iterated over. Then at %18 and %19 an object of a struct called var"#f#test##18" is created, with one field, the boxed i. This is how capture of variables work. It’s a callable struct. Then, in %23, the f is pushed. We see it’s of type var"#f#test##18".

At the end of block 4, in %37 this type appears again, the same weirdly named type is returned from test.

Now, what does this mean? All the fs, those pushed, and the one outside the loop, are of the same type, a struct with one field:

julia> dump(var"#f#test##18")
struct var"#f#test##18" <: Function
  i::Core.Box

What we can’t see is that this is a callable struct, the method table is not global, but if we insert a methods(f) at the end of the test-function, we see that it has a single method:

# 1 method for callable object:
 [1] (::var"#f#test##18")()

Now, let’s call this struct F, to avoid the clutter. It looks like this:

struct F <: Function
    i::Core.Box
end

It has a method, a single method, defined like:

(fs::F)() = something

So, no matter what the i is, the exact same something is called. The question is what it is. There are two candidates for something:

(fs::F)() = println(fs.i)

or

(fs::F)() = println("single-out")

However, this is not to be found inside the lowered test function, we can’t see it. It’s not part of the execution of test(), it has been defined once together with the struct, not repeatedly inside the loop or elsewhere. As Jeff says in the github-thread, it would be too slow to serve any practical purpose. We know it’s the last alternative, that’s what’s printed.

In the surrogate case, something else happens. By inserting a @code_warntype surrogate(1) in test(), we see that the f inside surrogate and the one outside, are different. So there are two callable structs, one inside surrogate which prints the i, and another for the f outside, which prints “single-out”. And, inside that test, the f is boxed to allow changing the type.

3 Likes
5

With some display we can also see the different types:

function test()
    function surrogate(i)
        function f()
            println(i)
        end
        push!(v, f)
    end

    v = Function[]
    for i = 1:3
        surrogate(i)
    end
    map(x -> x(), v)
    display(typeof(f))
    function f()
        println("single-out")
    end
    display(typeof(f))
end
julia> test()
1
2
3
var"#f#test##50"{Int64}
var"#f#test##53"
6

Your first example can also be slightly modified:

function test()
    v = Function[]
    for i = 1:3
        function f()
            println(i)
        end
        push!(v, f)
    end
    map(x -> x(), v)
    map(x -> x(1), v)
    function f(_)
        println("single-out")
    end
end
julia> test()
1
2
3
single-out
single-out
single-out