Remove recursive `interleave` calls

[rlouf]

The following code fails with a RecursionError:

from kanren import eq, lall, lany, run, vars

observations = [(0, 1), (1, 0)]

def generate(pixels):
    pairs = [(a, b) for a, b in zip(pixels[:-1], pixels[1:])]
    return lall(
        *[lany(*[eq(obs, pair) for obs in observations]) for pair in pairs]
    )

N = 1000
pixels = vars(N)
res = run(1, pixels, generate(pixels))

The error is raised in the interleave function from toolz.

[rlouf]

It appears that toolz does not use trampoline evaluation, and has no intention to do so. We may need to implement a version of interleave that uses it to avoid this RecursionError.

[brandonwillard]

It appears that toolz does not use trampoline evaluation, and has no intention to do so. We may need to implement a version of interleave that uses it to avoid this RecursionError.

Yes, that's the same type of thing I did in etuples and unification to get past recursion limits/errors.

[brandonwillard]

The error is raised in the interleave function from toolz.

I'm not able to reproduce the error locally.

[rlouf]

Ah. I tried in a fresh environment and the error still shows on my machine.

[brandonwillard]

FYI: If I set N to something large, the issue appears.

Anyway, yes, we should make our own version of interleave that doesn't use recursion.

[wrq]

I may be way out my league here, but this could not be done with zip and enumerate? I've included a small snippet to illustrate what I mean.

def interleave(*iters):
  res = []
  for z in zip(*iters):
    for _,x in enumerate(z):
      res.append(x)
  return res

print(interleave([1,2,3], [4,5,6], [7,8,9]))
# returns: [1, 4, 7, 2, 5, 8, 3, 6, 9]

If this is a complete misunderstanding, just let me know; I do not mean to interrupt or obstruct.

Edit: a little more experimenting below -->

import random

def split(s: str) -> list[str]:
  return [x for x in s]

def listbench(lstlen, x):
  res = []
  for x in range(x):
    aux = [random.randrange(1,11) for _ in range(lstlen)]
    res.append(aux)
  return res

print(interleave(*listbench(10, 5000)))

This appears to work even with larger lists, I tested 50_000 and 500_000, both successful.

[brandonwillard]

I may be way out my league here, but this could not be done with zip and enumerate? I've included a small snippet to illustrate what I mean.

def interleave(*iters):
  res = []
  for z in zip(*iters):
    for _,x in enumerate(z):
      res.append(x)
  return res

print(interleave([1,2,3], [4,5,6], [7,8,9]))
# returns: [1, 4, 7, 2, 5, 8, 3, 6, 9]

If this is a complete misunderstanding, just let me know; I do not mean to interrupt or obstruct.

Now that I'm coming back to this, I don't think the problem is in interleave itself, as much as our use of it in lall -> lconj -> lconj_seq -> bind. The generator produced by lconj_seq (well, the lconj_seq_goal it creates) is effectively composing N - 1 interleave calls. I think that's actually the thing we need to "flatten".

[wrq]

I can see that I am in fact out of my league here then, cheers and good luck!

[brandonwillard]

I can see that I am in fact out of my league here then, cheers and good luck!

There's a bit of context here that may make things seem foreign, but we're really just talking about generators calling generators in a particular way.

The first step toward solving this issue is to remove all the unnecessary elements and obtain a more direct illustration of the issue—if possible.

Here's a first pass at that:

from kanren import var, eq
from kanren.core import lconj_seq


q_lv = var()

goal_1 = lconj_seq((eq(q_lv, i) for i in range(10000)))

goal_1
# <function kanren.core.lconj_seq.<locals>.lconj_seq_goal(S)>

state_0 = {}
state_stream_1 = goal_1(state_0)

state_stream_1
# <generator object lconj_seq.<locals>.lconj_seq_goal at 0x7f6e14f580d0>

next(state_stream_1)
# RecursionError: maximum recursion depth exceeded while calling a Python object

Now, we can focus exclusively on the code in kanren.core.lconj_seq.lconj_seq_goal.