# Type instability in list comprehensions

**URL:** <https://discourse.julialang.org/t/type-instability-in-list-comprehensions/117673>\
**Category:** General Usage\
**Tags:** repl, type-stability, comprehension\
**Created:** [July 31, 2024, 12:31pm UTC](https://discourse.julialang.org/t/type-instability-in-list-comprehensions/117673 "2024-07-31T12:31:06Z")\
**Posts on this page:** 7\
**Page:** 3

<div class="post-metadata">

**Author:** ![CameronBieganek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cameronbieganek/32/6915_2.png) [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)\
**Post date:** [August 2, 2024, 4:07pm UTC](https://discourse.julialang.org/t/type-instability-in-list-comprehensions/117673/41 "2024-08-02T16:07:27Z")

</div>

> [@mrufsvold](#):
>
> Could you expand on that idea a bit? Isn’t everything intrinsics at the bottom, including `return_type`?

I can’t find good documentation on this now, but I recall reading or hearing sometime in the past about how Base Julia is built up from a small core of intrinsic concepts. The intrinsics include struct definitions, control flow, and a small set of built-in functions like `getfield` and `setfield!`. So, in theory, Base should be defined entirely in terms of those intrinsics, but I think in practice that’s not followed 100%. (`Core.Compiler.return_type` is not an intrinsic.)

* * *

I think the core issue here is that Julia is a dynamic language, so the value and side effects of an expression should depend only on the runtime values of the components that make up the expression. (Types are first-class objects in Julia and can be examined via `typeof`, so the type of an object is a part of its “value”. And of course the type of an object affects dispatch on the object.)

Here is a simple example that hopefully demonstrates the violation of this principle in the implementation of array comprehensions. We see two expressions where the components of the expressions have the same value, but the value and/or side effects of the two expressions are different:

Define values:

```julia
const a = Int[]
const b = Int[]
c = Int[]
d = Int[]
g(::Vector{Int}) = 42

```

Evaluate expressions:

```julia-repl
julia> a == c, b == d
(true, true)

julia> g([x*y for x in a for y in b])
42

julia> g([x*y for x in c for y in d])
ERROR: MethodError: no method matching g(::Vector{Any})

Closest candidates are:
  g(::Vector{Int64})
   @ Main REPL[5]:1

```

---

<div class="post-metadata">

**Author:** ![CameronBieganek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cameronbieganek/32/6915_2.png) [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)\
**Post date:** [August 2, 2024, 4:22pm UTC](https://discourse.julialang.org/t/type-instability-in-list-comprehensions/117673/42 "2024-08-02T16:22:07Z")

</div>

Or a tweaked version of the example so that the values (not just the side effects) of the two expressions are different even though the values of the components of the expressions are the same:

Define values:

```julia
const a = Int[]
const b = Int[]
c = Int[]
d = Int[]
g(::Vector{Int}) = 1
g(::Vector{Any}) = 2

```

Evaluate expressions:

```julia-repl
julia> a == c, b == d
(true, true)

julia> g([x*y for x in a for y in b])
1

julia> g([x*y for x in c for y in d])
2

```

I think sometimes regular Julia users are so used to thinking about type inference, type stability, and JIT compilation that they start to think of it as a language feature, but it is not a part of the semantics of the language—it is merely an implementation optimization, as mentioned by @danielwe. And implementation optimizations should not affect the behavior of a piece of code.

(To be precise, the type inference implementation optimization in Julia is not the cause of the problem here. The cause of the inconsistency is the use of `Core.Compiler.return_type` somewhere within the array comprehension and/or generator implementation in Base Julia.)

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [August 2, 2024, 8:48pm UTC](https://discourse.julialang.org/t/type-instability-in-list-comprehensions/117673/43 "2024-08-02T20:48:40Z")

</div>

> [@CameronBieganek](#):
>
> Since the output type of `f` is unknown, the only reasonable empty vector to return is `Any[]`.

The “correct” thing to return is actually `Union{}[]` which is the empty array with element type `Union{}`.

---

<div class="post-metadata">

**Author:** ![mrufsvold](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mrufsvold/32/31600_2.png) [@mrufsvold](https://discourse.julialang.org/u/mrufsvold)\
**Post date:** [August 2, 2024, 9:00pm UTC](https://discourse.julialang.org/t/type-instability-in-list-comprehensions/117673/44 "2024-08-02T21:00:27Z")

</div>

I keep asking to be educated, but isn’t `Union{}` the _only_ thing that `f` can’t return? My intuition says that the `eltype` would be the narrowest guess the compiler can provide. When it has elements to work with, it gives `Float64`. When it doesn’t have elements, the compiler would say “I dunno, the result could be `Any`thing.” No?

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [August 2, 2024, 9:06pm UTC](https://discourse.julialang.org/t/type-instability-in-list-comprehensions/117673/45 "2024-08-02T21:06:24Z")

</div>

True, `f` cannot return an element of type `Union{}` (since there are no such values), but the right dynamic behavior is for the returned array to have an element type that is “as small as possible” but contains all the values that are actually returned. When zero elements are returned, then the element type of can be `Union{}` and this preserves type stability since type inference knows that if you take and element out of the returned array and were expecting a value of type `Int` (for example), then the value you get won’t not be of type `Int` since `Union{} <: Int`, but really what it means is that you can’t take any elements our because there can’t be any.

> When it doesn’t have elements, the compiler would say “I dunno, the result could be `Any` thing.” No?

Or put another way, when there are no elements, we know that all the elements are instances of `Union{}` (because there are none).

“As small as possible” may not be exactly what you want since the smallest type is the union of the types of all the elements, which can get messy when the values are of mixed types. In those cases we use the `typejoin` function to climb the abstract type hierarchy to find some abstract type that contains all the individual types.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [August 2, 2024, 9:14pm UTC](https://discourse.julialang.org/t/type-instability-in-list-comprehensions/117673/46 "2024-08-02T21:14:28Z")

</div>

I should add that the main reason we don’t do this is that you can’t do a lot with such an array, eg push any elements into it. I do think that may have been the wrong choice.

---

<div class="post-metadata">

**Author:** ![CameronBieganek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cameronbieganek/32/6915_2.png) [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)\
**Post date:** [August 9, 2024, 12:28am UTC](https://discourse.julialang.org/t/type-instability-in-list-comprehensions/117673/47 "2024-08-09T00:28:47Z")

</div>

A PR was recently merged that updates the docs to clarify the current behavior:

> <https://github.com/JuliaLang/julia/pull/55352>
>
> fixes #55350

[Previous page](https://discourse.julialang.org/t/type-instability-in-list-comprehensions/117673.md?page=2)