# How to write @memoize that works in both local and global scope

**URL:** <https://discourse.julialang.org/t/how-to-write-memoize-that-works-in-both-local-and-global-scope/49727>\
**Category:** General Usage\
**Tags:** memoize\
**Created:** [November 7, 2020, 10:11am UTC](https://discourse.julialang.org/t/how-to-write-memoize-that-works-in-both-local-and-global-scope/49727 "2020-11-07T10:11:24Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![cstjean](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cstjean/32/1444_2.png) [@cstjean](https://discourse.julialang.org/u/cstjean)\
**Post date:** [November 7, 2020, 10:11am UTC](https://discourse.julialang.org/t/how-to-write-memoize-that-works-in-both-local-and-global-scope/49727/1 "2020-11-07T10:11:24Z")

</div>

Let’s write a `@memoize f(x) = ...` macro in Julia. Glossing over gensyms etc. it can just macroexpand into

```julia
memo = Dict()
f(x) = get(memo, x) do ... end

```

At the global scope `memo` will be a slow global variable, so let’s instead macroexpand to:

```julia
const memo = Dict()
f(x) = get(memo, x) do ... end

```

But oops, Julia doesn’t like `const` in the local scope. This won’t work to memoize a local function. Alright, let’s try

```julia
let memo = Dict()
    f(x) = get(memo, x) do ... end
end

```

to make our Lisp fathers proud. But the funny rule here is that at the global scope, `f`’s name will be mangled to make it a local function _unless_ it is prefixed with a module, like `Main.f(x) = get(memo, x) do ... end`. I could use `@ __MODULE__ ` to get that but, of course, it won’t work at the local scope.

It’s quite a frustrating situation. Memoize.jl uses `eval` in [the macro code](https://github.com/JuliaCollections/Memoize.jl/blob/master/src/Memoize.jl#L56) to get around it, which is evil in its own way. And Memoization.jl uses generated functions (!)

This shouldn’t be so hard! Did we all miss something obvious?

---

<div class="post-metadata">

**Author:** ![malacroi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/malacroi/32/19745_2.png) [@malacroi](https://discourse.julialang.org/u/malacroi)\
**Post date:** [November 7, 2020, 3:26pm UTC](https://discourse.julialang.org/t/how-to-write-memoize-that-works-in-both-local-and-global-scope/49727/2 "2020-11-07T15:26:44Z")

</div>

Can’t you just assign assign the function returned by the `let` into the global scope

```julia
fib = let memo=Dict()
    innerfib(x) = get!(memo, x) do
        println(x)
        x<=2 && return BigInt(1)
        innerfib(x-1)+innerfib(x-2)
    end
end

```

As a macro that works on recursive, or mutually recursive functions, you might need

```julia
fib = let memo=Dict()
    innerfib(x) = get!(memo, x) do
        x<=2 && return BigInt(1)
        fib(x-1)+fib(x-2)
    end
end

```

so that the name of the recursive calls is unaltered.

---

<div class="post-metadata">

**Author:** ![cstjean](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cstjean/32/1444_2.png) [@cstjean](https://discourse.julialang.org/u/cstjean)\
**Post date:** [November 7, 2020, 10:26pm UTC](https://discourse.julialang.org/t/how-to-write-memoize-that-works-in-both-local-and-global-scope/49727/3 "2020-11-07T22:26:42Z")

</div>

Yes, but then A) it only works if `fib` is the only method for that function and B) it will have poor performance because `fib` is a global.

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [November 7, 2020, 10:48pm UTC](https://discourse.julialang.org/t/how-to-write-memoize-that-works-in-both-local-and-global-scope/49727/4 "2020-11-07T22:48:32Z")

</div>

Ok, how about constructing the cache within the macro body itself and then closing over it in the generated code?

```julia
julia> macro memoize(f, body)
         memo = Dict()
         quote
           function $(esc(f))(x)
             get!($memo, x) do
               println("Cache miss")
               $(esc(body))(x)
             end
           end
         end
       end
@memoize (macro with 1 method)

julia> @memoize fib x -> begin
         x <= 2 && return BigInt(1)
         fib(x - 1) + fib(x - 2)
       end
fib (generic function with 2 methods)

julia> fib(1)
Cache miss
1

julia> fib(1)
1

julia> fib(5)
Cache miss
Cache miss
Cache miss
Cache miss
5

```

This macro results in a normal function definition, so you can extend it at global scope as desired:

```julia
julia> fib(x::Float64) = 1.0
fib (generic function with 2 methods)

julia> fib(5) # uses the memoized `fib`
5

julia> fib(5.0) # uses `fib(x::Float64)` method
1.0

```

and it also doesn’t leak anything into global scope when run from a local scope:

```julia
julia> let
         @memoize foo x -> begin
           x + 1
         end
         
         foo(2)
       end
Cache miss
3

julia> foo # not defined because it was local to the `let` block
ERROR: UndefVarError: foo not defined

```

I’ve been a little lazy in requiring that the user split up the `fib` symbol from the `x -> begin...end` body, but you could parse that data out of a normal-looking function definition so that the macro works like:

```julia
@memoize fib(x)
   ... # body here
end

```

---

<div class="post-metadata">

**Author:** ![cstjean](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cstjean/32/1444_2.png) [@cstjean](https://discourse.julialang.org/u/cstjean)\
**Post date:** [November 8, 2020, 7:42am UTC](https://discourse.julialang.org/t/how-to-write-memoize-that-works-in-both-local-and-global-scope/49727/5 "2020-11-08T07:42:25Z")

</div>

> [@rdeits](#):
>
> Ok, how about constructing the cache within the macro body itself and then closing over it in the generated code?

Yes, that’s basically what Memoize.jl does, but it supports arbitrary `AbstractDict`, like `@memoize LRUDict(...) foo(x) = ...`, which is why it needs to `eval` in the containing module.

It fails for local functions because they all share the same cache, since the macro body is evaluated only once:

```julia
julia> g = []
       for x in 1:10
       push!(g, 
             @memoize f(y) = x+y)
       end

julia> g[1](1)
2

julia> g[2](1)
2

```

The `let` solution would work fine here.

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [November 8, 2020, 7:51am UTC](https://discourse.julialang.org/t/how-to-write-memoize-that-works-in-both-local-and-global-scope/49727/6 "2020-11-08T07:51:18Z")

</div>

Recently I have been avoiding the “magic” of macros where I think the explicit code is simple enough, and can benefit from customization: e.g. for memoizing:

- local vs global scope
- new function versus adding method to existing function (perhaps in another module)
- typed Dict for caching
- custom caching where cache value is function of argument

Is the `fib` example faster with typed `Dict` cache?

```julia
let
    memo = Dict{Int,BigInt}()
    global function fib2(x)
        get!(memo, x) do
            x <= 2 && return BigInt(1)
            fib2(x-1) + fib2(x-2)
        end
    end
end

```

---

<div class="post-metadata">

**Author:** ![cstjean](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cstjean/32/1444_2.png) [@cstjean](https://discourse.julialang.org/u/cstjean)\
**Post date:** [November 8, 2020, 7:51am UTC](https://discourse.julialang.org/t/how-to-write-memoize-that-works-in-both-local-and-global-scope/49727/7 "2020-11-08T07:51:23Z")

</div>

I suppose one could get around this problem by putting `g` inside of the key. Mostly, I’m annoyed by the `eval`. Lisp forefathers would disapprove, but maybe that’s one instance where it’s legitimate and necessary?