Possible regression: kanren: Error: unbound variable: move1330613308

[Mario Domenech Goulart]

Steps to reproduce:

$ wget https://github.com/mario-goulart/chicken-benchmarks/raw/master/progs/kanren.scm

$ csc kanren.scm

$ ./kanren
Testing eigen
eigens: (!x_!$gen$!x3 !y_!$gen$!x4)
Testing test-unify/pairs-oleg1
Testing test-unify/pairs-oleg2
Testing test-unify/pairs-oleg3
Testing test-unify/pairs-oleg4
Testing test-unify/pairs-oleg5
Testing test-unify/pairs-oleg6
Testing test-unify/pairs-oleg7
Testing test-unify/pairs-oleg8
Testing test-unify/pairs-oleg8
Testing test-unify/pairs-oleg10
Testing test-unify/pairs-oleg11
Testing test-pathological
((y0.0 _.0) (y1.0 (f _.0 _.0)) (x1.0 (f _.0 _.0)))

((y0.0 _.0) (y2.0 (f (f _.0 _.0) (f _.0 _.0))) (y1.0 (f _.0 _.0)) (x2.0 (f (f _.0 _.0) (f _.0 _.0))) (x1.0 (f _.0 _.0)))

((y0.0 _.0) (y4.0 (f (f (f (f _.0 _.0) (f _.0 _.0)) (f (f _.0 _.0) (f _.0 _.0))) (f (f (f _.0 _.0) (f _.0 _.0)) (f (f _.0 _.0) (f _.0 _.0))))) (y3.0 (f (f (f _.0 _.0) (f _.0 _.0)) (f (f _.0 _.0) (f _.0 _.0)))) (y2.0 (f (f _.0 _.0) (f _.0 _.0))) (y1.0 (f _.0 _.0)) (x4.0 (f (f (f (f _.0 _.0) (f _.0 _.0)) (f (f _.0 _.0) (f _.0 _.0))) (f (f (f _.0 _.0) (f _.0 _.0)) (f (f _.0 _.0) (f _.0 _.0))))) (x3.0 (f (f (f _.0 _.0) (f _.0 _.0)) (f (f _.0 _.0) (f _.0 _.0)))) (x2.0 (f (f _.0 _.0) (f _.0 _.0))) (x1.0 (f _.0 _.0)))
Testing length-of-subst
Testing test-father0
Testing test-child-of-male-0
Testing test-child-of-male-1
Testing test-father-1
Testing test-father-2
Testing test-father-3
Testing test-father-4
Testing test-father-5
((#(lv x) . sal))
((#(lv x) . pat))
Testing test-father-6/solve
Testing test-father-7/solution
Testing test-conscientious-parents
Testing test-grandpa-sam-1
Testing test-grandpa-sam-1
Testing test-child-1
Testing test-grandpa-1
Testing test-grandpa-maker-2
Testing test-grandpa-5
Testing test-grandpa-55
Testing test-grandpa-8
Testing test-grandpa-10
Testing test-grandpa-10-1
Testing test-grandpa-10
Testing test-grandpa-10-1
Testing test-grandpa-10-soft-cut
Testing test-no-grandma-grandpa-1
Testing test-partially-eval-sgl
Testing test-pred1
Testing test-pred2
Testing test-pred3
Testing test-Seres-Spivey

Error: unbound variable: move1330613308

	Call history:

	kanren.scm:2761: g14183	  
	kanren.scm:2763: subst-in	  
	kanren.scm:269: var?	  
	kanren.scm:2763: nonvar!	  
	kanren.scm:2132: var?	  
	kanren.scm:2763: g14194	  
	kanren.scm:2759: g14309	  
	kanren.scm:2759: g14307	  
	kanren.scm:2764: g14216	  
	kanren.scm:2764: succeed	  
	kanren.scm:2764: g14214	  
	kanren.scm:970: k	  
	kanren.scm:2764: g14212	  
	kanren.scm:2764: g14236	  
	kanren.scm:2764: g14234	  
	kanren.scm:2767: move	  	<--

Works fine if compiled with 4.8.0.5

[sjamaan]

If we can't fix this we can revert the letrec patch, see #1078.

[sjamaan]

Here's a simple test case:

(t 1 (letrec ((foo (lambda () 1))
              (bar (let ((tmp (lambda (x) (if x (foo) (bar #t)))))
                     tmp)))
            (bar #f)))

[sjamaan]

Initial attempt at fixing #1068 by ripping out returnvar-passing in cps-conversion

[sjamaan]

This attempt causes kanren to break in another place. I'm unsure whether I introduced a new bug, or this just exposes a deeply-hidden other bug. Here's a trivial testcase that now breaks:

(letrec ((bar (lambda (x) (if x 1 (bar bar)))))
  (bar #f))

The simplified "core" version of same:

(let ((outer-bar (##core#undefined)))
  (let ((inner-bar (lambda (x) (if x '1 (outer-bar outer-bar)))))
    (set! outer-bar inner-bar)
    (outer-bar '#f)))

[sjamaan]

Second fix: don't allow lambdas with local variable references to replace variables.

[sjamaan]

Fixed with 05d663cccb4ea37b3f86f5020dbde8c29613a591 (and 3e302a402bb20f8ffc2975eb77edcfe2f7c0e36c, sort of). No regressions: ​http://tests.call-cc.org/master/linux/x86/2014/01/05/yesterday-diff/
and it even looks like we fixed a bug we didn't know was caused by this.