# Understanding memoization.jl
**URL:** https://discourse.julialang.org/t/understanding-memoization-jl/5394
**Category:** General Usage
**Tags:** question, macros, memoize
**Created:** [August 15, 2017, 7:14pm UTC](https://discourse.julialang.org/t/understanding-memoization-jl/5394 "2017-08-15T19:14:54Z")
**Posts on this page:** 6
**Page:** 1
### Author:  [@Chong\_Wang](https://discourse.julialang.org/u/Chong_Wang)
#### Post date: [August 15, 2017, 7:14pm UTC](https://discourse.julialang.org/t/understanding-memoization-jl/5394/1 "2017-08-15T19:14:54Z")
I am trying to understand memoization.jl by simonster to obtain a good understanding of macros. First I tried to macroexpand the output:
```julia
julia> using Memoize
julia> macroexpand(:(@memoize function x(a) a end))
quote # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 107:
function ##x_unmemoized(a) # REPL[3], line 1:
a
end # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 108:
empty!(ObjectIdDict()) # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 109:
x(a)::Any = begin # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 109:
if haskey(ObjectIdDict(), (a,))
(ObjectIdDict())[(a,)]::Core.Inference.return_type(##x_unmemoized, typeof((a,)))
else
(ObjectIdDict())[(a,)] = ##x_unmemoized(a)
end
end
end
```
It is really weird. I think `##x_unmemoized` is intended to be a function but since it starts with `#`, it should be a comment. Then I tried to evaluate it:
```julia
julia> eval(macroexpand(:(@memoize function x(a) a end)))
x (generic function with 1 method)
```
Everything seems to be fine. However, if I copy the output of macroexpand:
```julia
julia> quote # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 107:
function ##x_unmemoized(a) # REPL[3], line 1:
a
end # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 108:
empty!(ObjectIdDict()) # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 109:
x(a)::Any = begin # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 109:
if haskey(ObjectIdDict(), (a,))
(ObjectIdDict())[(a,)]::Core.Inference.return_type(##x_unmemoized, typeof((a,)))
else
(ObjectIdDict())[(a,)] = ##x_unmemoized(a)
end
end
end
ERROR: syntax: unexpected else
Stacktrace:
[1] macro expansion at ./REPL.jl:97 [inlined]
[2] (::Base.REPL.##1#2{Base.REPL.REPLBackend})() at ./event.jl:73
```
I am totally confused about what is happening here. Anyone give me a hint?
---
### Author:  [@mauro3](https://discourse.julialang.org/u/mauro3)
#### Post date: [August 15, 2017, 7:26pm UTC](https://discourse.julialang.org/t/understanding-memoization-jl/5394/2 "2017-08-15T19:26:24Z")
These funny variable names are partially gensym’ed, a kind of name mangling to make sure there variable names are unique.
```julia
julia> a = gensym()
Symbol("##778")
julia> :($a=1)
:(##778 = 1)
julia> eval(:($a=1))
1
julia> eval(:($a))
1
```
If you copy past it you have to rename those to something which is not a comment. Either wrap them in `$(Symbol("##x_unmemoized"))` or just use other names, e.g. see MacroTools.jl: [https://github.com/MikeInnes/MacroTools.jl/blob/51391fb1cc93d295a1643be1d577265468428625/src/utils.jl#L128](https://github.com/MikeInnes/MacroTools.jl/blob/51391fb1cc93d295a1643be1d577265468428625/src/utils.jl#L128)
---
### Author:  [@Michael\_Eastwood](https://discourse.julialang.org/u/Michael_Eastwood)
#### Post date: [August 15, 2017, 7:27pm UTC](https://discourse.julialang.org/t/understanding-memoization-jl/5394/3 "2017-08-15T19:27:54Z")
Memoize is rewriting your function to be something like
```julia
function unmemoized_name(...)
# original function body
end
function original_name(...)
# look up result from the ObjectIdDict if it exists
end
```
`##x_unmemoized` is just the name of the unmemoized function. The two `##` just help ensure that the function name doesn’t conflict with anything else you may have defined. These automatically generated names usually come from calling `gensym`:
```julia
help?> gensym
search: gensym @gensym
gensym([tag])
Generates a symbol which will not conflict with other variable names.
julia> gensym(:hello)
Symbol("##hello#658")
```
---
### Author:  [@Chong\_Wang](https://discourse.julialang.org/u/Chong_Wang)
#### Post date: [August 15, 2017, 7:41pm UTC](https://discourse.julialang.org/t/understanding-memoization-jl/5394/4 "2017-08-15T19:41:56Z")
Thank you @Michael_Eastwood and @mauro3.
I am still confused.
1. “##x\_unmemoized” is actually hard coded, see [https://github.com/simonster/Memoize.jl/blob/master/src/Memoize.jl](https://github.com/simonster/Memoize.jl/blob/master/src/Memoize.jl). Then are name conflicts still guaranteed to be avoided?
2. I understand what is memoization, but the following expression returned by macroexpand seems to create a dictionary every time the function is called:
```julia
julia> macroexpand(:(@memoize function x(a) a end))
quote # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 107:
function ##x_unmemoized(a) # REPL[3], line 1:
a
end # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 108:
empty!(ObjectIdDict()) # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 109:
x(a)::Any = begin # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 109:
if haskey(ObjectIdDict(), (a,))
(ObjectIdDict())[(a,)]::Core.Inference.return_type(##x_unmemoized, typeof((a,)))
else
(ObjectIdDict())[(a,)] = ##x_unmemoized(a)
end
end
end
```
If I rename `##x_unmemoized` and evaluate it (notice I add an extra line `println("running")`):
```julia
eval(quote # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 107:
function x_unmemoized(a) # REPL[3], line 1:
println("running")
a
end # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 108:
empty!(ObjectIdDict()) # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 109:
x(a)::Any = begin # /home/wangc/.julia/v0.6/Memoize/src/Memoize.jl, line 109:
if haskey(ObjectIdDict(), (a,))
(ObjectIdDict())[(a,)]::Core.Inference.return_type(x_unmemoized, typeof((a,)))
else
(ObjectIdDict())[(a,)] = x_unmemoized(a)
end
end
end
)
```
, the function `x` is not memoized at all:
```julia
julia> x(1)
running
1
julia> x(1)
running
1
```
.
So it seems that using macro is not equivalent to evaluate the expression the macro returns. How to understand this behaviour?
---
### Author:  [@cstjean](https://discourse.julialang.org/u/cstjean)
#### Post date: [August 15, 2017, 8:04pm UTC](https://discourse.julialang.org/t/understanding-memoization-jl/5394/5 "2017-08-15T20:04:53Z")
> [@Chong\_Wang](#):
>
> “##x\_unmemoized” is actually hard coded, see [https://github.com/simonster/Memoize.jl/blob/master/src/Memoize.jl](https://github.com/simonster/Memoize.jl/blob/master/src/Memoize.jl). Then are name conflicts still guaranteed to be avoided?
They’re not, but pragmatically, you won’t get a conflict unless you go looking for one. The point is that this way you can get to the unmemoized function with something like `eval(Symbol("##x_unmemoized"))`. If Memoize.jl used gensyms, then AFAIK you can’t get that variable without hacking your way into Julia internals.
> [@Chong\_Wang](#):
>
> I understand what is memoization, but the following expression returned by macroexpand seems to create a dictionary every time the function is called:
That’s a confusing situation. You can put arbitrary objects inside your macroexpansion. They put an `ObjectIdDict()`, whose printed representation is:
```julia
julia> show(STDOUT, ObjectIdDict())
ObjectIdDict()
```
So there’s only one dictionary created - at macro expansion time. I think the normal way of writing this would put the dictionary creation expression inside the macro expansion, as `const memo = ObjectIdDict()`, but perhaps they had good reasons for doing things this way.
---
### Author:  [@Chong\_Wang](https://discourse.julialang.org/u/Chong_Wang)
#### Post date: [August 15, 2017, 8:17pm UTC](https://discourse.julialang.org/t/understanding-memoization-jl/5394/6 "2017-08-15T20:17:52Z")
Thank you, I have a basic understanding now.