Revision 668a674ec718a768283c87ff368458328f7cd799 authored by Keno Fischer on 28 December 2022, 23:07:06 UTC, committed by Keno Fischer on 31 December 2022, 17:27:32 UTC
Our recusion heuristic works by detection recursion of edges of
methods (N.B.: Methods, not specializations). This works reasonably
well, but there are some pathological cases that defeat it. One
common one is to have a wrapper function that calls an internal
function, e.g.

```
mymap(f, x) = _mymap(f, x)
```

If a higher order function is written with such a pattern, it is
quite easy to run into the recursion limit even in legitimate cases.
For example, with the above definition, a fuction like:

```
f(x) = mymap(x) do t
mymap(sin, t)
end
```

will fail to get precise inference. There's various other patterns
that cause similar issues, e.g. optional arguments and keyword arguments
and is one of the more common causes of inference suboptimalities.

This PR attempts to relax this criterion significantly. It is still
based on methods, but considers the entire recursion path rather
than just a single edge. So for example, in our current heuristic,
we would limit:

    E -> A -> B -> C -> A -> B

immediately, but with the proposed heuristic we would not limit it
until we reach:

    E -> A -> B -> C -> A -> B -> C

And in particular, we would not limit

    E -> A -> B -> C -> A -> B -> D -> A -> B -> E

even though the `A->B` edge repeats frequently. This is intentional
to allow code that has a central dispatch function (e.g. Diffractor
has code patterns like that).

If this turns out to be not aggressive enough, we could consider
imposing additional limitations on the intermediate edges, but I
think this is worth a try.
1 parent 4d206c9
History
File Mode Size
.devcontainer
.github
base
cli
contrib
deps
doc
etc
src
stdlib
test
.buildkite-external-version -rw-r--r-- 5 bytes
.clang-format -rw-r--r-- 3.3 KB
.codecov.yml -rw-r--r-- 52 bytes
.git-blame-ignore-revs -rw-r--r-- 294 bytes
.gitattributes -rw-r--r-- 65 bytes
.gitignore -rw-r--r-- 507 bytes
.mailmap -rw-r--r-- 12.1 KB
CITATION.bib -rw-r--r-- 513 bytes
CITATION.cff -rw-r--r-- 940 bytes
CONTRIBUTING.md -rw-r--r-- 23.1 KB
HISTORY.md -rw-r--r-- 363.1 KB
LICENSE.md -rw-r--r-- 1.3 KB
Make.inc -rw-r--r-- 51.6 KB
Makefile -rw-r--r-- 30.0 KB
NEWS.md -rw-r--r-- 1.3 KB
README.md -rw-r--r-- 7.3 KB
THIRDPARTY.md -rw-r--r-- 3.7 KB
VERSION -rw-r--r-- 11 bytes
julia.spdx.json -rw-r--r-- 35.8 KB
sysimage.mk -rw-r--r-- 4.1 KB

README.md

back to top