# Julia gets stuck on recursive function

**URL:** <https://discourse.julialang.org/t/julia-gets-stuck-on-recursive-function/22548>\
**Category:** General Usage\
**Created:** [March 30, 2019, 6:46pm UTC](https://discourse.julialang.org/t/julia-gets-stuck-on-recursive-function/22548 "2019-03-30T18:46:31Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [March 30, 2019, 6:46pm UTC](https://discourse.julialang.org/t/julia-gets-stuck-on-recursive-function/22548/1 "2019-03-30T18:46:32Z")

</div>

I defined the following `merge` function for a custom `Dict` type:

```julia
struct MixedKeyDict{T<:Tuple} #<: AbstractDict{Any,Any}
    dicts::T
end

Base.merge(f::Function, d::MixedKeyDict, others::MixedKeyDict...) = _merge(f, (), d.dicts, (d->d.dicts).(others)...)
Base.merge(f, d::MixedKeyDict, others::MixedKeyDict...) = _merge(f, (), d.dicts, (d->d.dicts).(others)...)

function _merge(f, res, d, others...)
    ofsametype, remaining = _alloftype(Base.heads(d), ((),), others...)
    return _merge(f, (res..., merge(f, ofsametype...)), Base.tail(d), remaining...)
end

_merge(f, res, ::Tuple{}, others...) = _merge(f, res, others...)
_merge(f, res, d) = MixedKeyDict((res..., d...))
_merge(f, res, ::Tuple{}) = MixedKeyDict(res)

function _alloftype(ofdesiredtype::Tuple{Vararg{D}}, accumulated, d::Tuple{D,Vararg}, others...) where D
    return _alloftype((ofdesiredtype..., first(d)),
                      (Base.front(accumulated)..., (last(accumulated)..., Base.tail(d)...), ()),
                      others...)
end

function _alloftype(ofdesiredtype, accumulated, d, others...)
    return _alloftype(ofdesiredtype,
                      (Base.front(accumulated)..., (last(accumulated)..., first(d))),
                      Base.tail(d), others...)
end

function _alloftype(ofdesiredtype, accumulated, ::Tuple{}, others...)
    return _alloftype(ofdesiredtype,
                      (accumulated..., ()),
                      others...)
end

_alloftype(ofdesiredtype, accumulated) = ofdesiredtype, Base.front(accumulated)

```

For two dicts, this works perfectly well:

```julia
julia> d = MixedKeyDict((Dict(1=>3),Dict(4. => 2)))
MixedKeyDict{Tuple{Dict{Int64,Int64},Dict{Float64,Int64}}} with 2 entries:
  1 => 3
  4.0 => 2

julia> e = MixedKeyDict((Dict(1=>7),Dict(5. => 9)))
MixedKeyDict{Tuple{Dict{Int64,Int64},Dict{Float64,Int64}}} with 2 entries:
  1 => 7
  5.0 => 9

julia> merge(+, d, e)
MixedKeyDict{Tuple{Dict{Int64,Int64},Dict{Float64,Int64}}} with 3 entries:
  1 => 10
  4.0 => 2
  5.0 => 9

```

But as soon as I add another one, Julia gets completely stuck and I have to kill the whole process.

```julia
julia> f = MixedKeyDict((Dict(2=>7),Dict(5. => 9)))
MixedKeyDict{Tuple{Dict{Int64,Int64},Dict{Float64,Int64}}} with 2 entries:
  2 => 7
  5.0 => 9

julia> merge(+, d, e, f) #gets stuck

```

I thought there might be a bug in my code, so I tried debugging it with `Debugger.jl`, but the weird part is,that it works just fine if I just `@enter` the function and let it continue without any breakpoints set:

```julia
julia> using Debugger

julia> @enter merge(+, d, e, f)
In merge(f, d, others) at /home/simeon/Documents/Julia/TypeStableDicts/src/TypeStableDicts.jl:33
>33 Base.merge(f::Function, d::MixedKeyDict, others::MixedKeyDict...) = _merge(f, (), d.dicts, (d->d.dicts).(others)...)

About to run: (getproperty)(<suppressed 71 bytes of output>, :dicts)
1|debug> c
MixedKeyDict{Tuple{Dict{Int64,Int64},Dict{Float64,Int64}}} with 4 entries:
  2 => 7
  1 => 10
  4.0 => 2
  5.0 => 18

```

If I tell `Debugger.jl` to use the compiled mode, it gets stuck again. This seems to be a bug in the compiler. Is this a known bug – should I open an issue? Are there any workarounds for this to work?

My Julia version:

```julia
julia> versioninfo()
Julia Version 1.1.0
Commit 80516ca202 (2019-01-21 21:24 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)

```

I’ve also tried it with the latest nightly, but no luck there either.

---

<div class="post-metadata">

**Author:** ![longemen3000](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/longemen3000/32/7298_2.png) [@longemen3000](https://discourse.julialang.org/u/longemen3000)\
**Post date:** [March 30, 2019, 10:22pm UTC](https://discourse.julialang.org/t/julia-gets-stuck-on-recursive-function/22548/2 "2019-03-30T22:22:16Z")

</div>

for what i’m looking, every pair(key,value) its is own dict, and you want a struct that allows binary operations on merge, thats correct? have you considered storing directly the pairs (key,value) as NTuples?

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [March 30, 2019, 10:28pm UTC](https://discourse.julialang.org/t/julia-gets-stuck-on-recursive-function/22548/3 "2019-03-30T22:28:06Z")

</div>

That’s just a simplification for testing purposes. The goal is to allow for type stable dicts with different key types, which are efficient if there are a lot more items than different key types.

---

<div class="post-metadata">

**Author:** ![longemen3000](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/longemen3000/32/7298_2.png) [@longemen3000](https://discourse.julialang.org/u/longemen3000)\
**Post date:** [March 30, 2019, 10:29pm UTC](https://discourse.julialang.org/t/julia-gets-stuck-on-recursive-function/22548/4 "2019-03-30T22:29:57Z")

</div>

but the part about the operation is still true? what i understand about your merge, is that also does a reduce over the variables of the same key, that is correct?

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [March 30, 2019, 10:33pm UTC](https://discourse.julialang.org/t/julia-gets-stuck-on-recursive-function/22548/5 "2019-03-30T22:33:55Z")

</div>

It works exactly the same as `merge` with a combine function on regular dicts, so it calls `f` on all items with the same keys.

---

<div class="post-metadata">

**Author:** ![longemen3000](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/longemen3000/32/7298_2.png) [@longemen3000](https://discourse.julialang.org/u/longemen3000)\
**Post date:** [March 30, 2019, 10:53pm UTC](https://discourse.julialang.org/t/julia-gets-stuck-on-recursive-function/22548/6 "2019-03-30T22:53:24Z")

</div>

have you tried IdDicts? those are dicts that check the value and the type (`===` comparison), so `IdDict[4]!=IdDIct[4.0]`, a demonstration:

```julia
x1 = IdDict{Any,Real}(
    "I'm a string" => 123,
    'c'=>3.0,
    4=>2,
    4.0=>3)

x2 = IdDict{Any,Real}(
    "I'm other string" => 123,
    'c'=>3.0,
    4=>-2,
    4.0=>-3
)

x3 = IdDict{Any,Real}(
    "I'm THE string" => 123,
    'd'=>3.0,
    4=>1,
    4.0=>1
)

merge!(+,x1,x2,x3)

julia>merge!(+,x1,x2)
IdDict{Any,Real} with 5 entries:
  "I'm a string" => 123
  4.0 => 0
  "I'm other string" => 123
  'c' => 6.0
  4 => 0

merge!(+,x1,x2,x3)
IdDict{Any,Real} with 6 entries:
  "I'm a string" => 123
  4.0 => 1
  "I'm other string" => 123
  'c' => 9.0
  4 => 1
  "I'm THE string" => 123

```

`merge(+,x1,x2,x3)` works too

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [March 30, 2019, 11:10pm UTC](https://discourse.julialang.org/t/julia-gets-stuck-on-recursive-function/22548/7 "2019-03-30T23:10:00Z")

</div>

The point is that the output type can be inferred only from the key type, which `IdDict` doesn’t allow. It also returns just a regular `Dict` when merging `IdDicts`. My example shouldn’t be thought to be representative of the actual usecase, it’s just do demonstrate the issue I ran into. My question was why this code example gets stuck, when it clearly should work, as described above.

---

<div class="post-metadata">

**Author:** ![longemen3000](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/longemen3000/32/7298_2.png) [@longemen3000](https://discourse.julialang.org/u/longemen3000)\
**Post date:** [March 30, 2019, 11:11pm UTC](https://discourse.julialang.org/t/julia-gets-stuck-on-recursive-function/22548/8 "2019-03-30T23:11:35Z")

</div>

yes, you are right, it is an issue, maybe file an issue on github?

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [March 30, 2019, 11:16pm UTC](https://discourse.julialang.org/t/julia-gets-stuck-on-recursive-function/22548/9 "2019-03-30T23:16:15Z")

</div>

That would be my next step. I just thought this might be related to an already opened issue and thought people might have additional input before I opened an issue.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [March 30, 2019, 11:27pm UTC](https://discourse.julialang.org/t/julia-gets-stuck-on-recursive-function/22548/10 "2019-03-30T23:27:06Z")

</div>

If the debugger (or rather the interpreter) and standard julia execution gives different answers, one of them has a bug. And while the interpreter is quite new it does very little fancy stuff so it could be that there is a bug in julia here from one of the different optimizations julia runs.

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [March 30, 2019, 11:34pm UTC](https://discourse.julialang.org/t/julia-gets-stuck-on-recursive-function/22548/11 "2019-03-30T23:34:01Z")

</div>

How would I then go about tracking down this particular issues? Are there tools to help with that? I’m not really familiar with Julia internals, so should I rather just open an issue on Github with this particular code example?

---

<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:** [March 31, 2019, 3:01am UTC](https://discourse.julialang.org/t/julia-gets-stuck-on-recursive-function/22548/12 "2019-03-31T03:01:46Z")

</div>

Yup, opening an issue on the Julia github repo seems totally reasonable.