Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Recursion Errors #13

Closed
brandonwillard opened this issue Feb 6, 2020 · 0 comments · Fixed by #16
Closed

Recursion Errors #13

brandonwillard opened this issue Feb 6, 2020 · 0 comments · Fixed by #16
Labels
bug Something isn't working

Comments

@brandonwillard
Copy link
Member

Long chains of logic variable associations cause RecursionErrors during reification (and possibly elsewhere):

import sys

from unification import var, reify

m = {}
first_lvar = var()
lvar = first_lvar
for i in range(sys.getrecursionlimit()):
    m[lvar] = (var(),)
    lvar = m[lvar][0]
m[lvar] = 1

reify(first_lvar, m)

The results is

...
RecursionError: maximum recursion depth exceeded

unification needs some form of TCO.
@brandonwillard brandonwillard added the bug Something isn't working label Feb 6, 2020
@brandonwillard brandonwillard mentioned this issue Feb 6, 2020
Merged
@brandonwillard brandonwillard mentioned this issue Feb 18, 2020
Merged
brandonwillard added a commit to brandonwillard/unification that referenced this issue Feb 20, 2020
@brandonwillard
Introduce stream/trampoline-based reification
08606c6 
This commit introduces a trampoline-style approach to reification.  It's essentially
inspired by the miniKanren stream processing alongside which this library is
primarily employed.  The main difference is that this implementation employs
the `Generator.send` method instead of callables (i.e. goals in miniKanren).

It removes reliance on the Python stack and, as a result, is much more scalable.
Also, it provides a mechanism through which substructures can be traversed but
not reconstructed.

Additions/extensions to the reification functions must follow the `yield`
paradigm when recursively calling `_reify` and precede object construction
with `yield construction_sentinel` to signify that substructure reification
is occurring next (i.e. so that the caller can prevent it, if desired).

Closes pythological#13 and closes pythological#10.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Something isn't working
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Introduce stream/trampoline-based reification and unification brandonwillard/unification
1 participant
@brandonwillard