Reasoned Schemer / miniKANREN question
Joe
I'm currently re-reading the Reasoned Schemer, but am having a bit of
difficulty understanding how values are computed for recursive
functions. For example, in chapter 2, the recursive function lolo and
section 24 asks what is the value of the following:
(run 5 (x)
(lolo ((a b) (c d) . x)))
The first value (), is obvious to me. The variable x is fresh, so it
is associated with () via the nullo check on line 4 of the method.
Here's my explanation for how the second value is derived. Since we
are asking for another value, and the expressions are evaluated within
the conde, we refresh x and try the next line. At this point, the caro
associates the fresh variable x with the cons of the fresh variable a
and the fresh variable d-prime (introduced by the caro). Then, listo
is called on a. Since a is fresh, this call associates a with ().
Since this question succeeds, we try the answer. The cdro associates x
with the cons of fresh variable a-prime (introduced by the cdro) and
the fresh variable d. Then, lolo is called on d, and so d (being
fresh), is associated with ().
Since a-prime and a co-share, and a is (), and d and d-prime co-share,
and d is (), x can be successfully associated with the cons of () and
(), so the result is (()).
Here's where I get confused. This invocation of run 2 has actually
produced #s 3 times, once to produce () and twice to produce (())
(once in each of the calls to listo and the recursive call to lolo).
However, we have *asked* for only two goals to be met, in order to
produce two values. If I invoke "run 3 ...," however, which conde
lines in which recursive frames are being evaluated, and having their
associations preserved? Or rather, how is the result expanding beyond
(())?
At the high level, I understand why the answer is (() (()) (() ()) (()
() ()) (() () () ())). But I'm still missing something at the lower
level that makes it harder for me to understand how some of the more
advanced examples, like the adder, work.
Thanks,
Joe
Joe
This example is in chapter 3, not 2 as I improperly stated.
Will Byrd
> Here's where I get confused. This invocation of run 2 has actually
> produced #s 3 times, once to produce () and twice to produce (())
> (once in each of the calls to listo and the recursive call to lolo).
> However, we have *asked* for only two goals to be met, in order to
> produce two values. If I invoke "run 3 ...," however, which conde
> lines in which recursive frames are being evaluated, and having their
> associations preserved? Or rather, how is the result expanding beyond
> (())?
(run 2 (q) g1 g2 g3) does *not* specify that at most two goal
invocations should succeed, or that at most two #s goals should be
tried. Rather, run 2 specifies that we want two answers (if there are
two answers to be had), regardless of how many goals must be tried,
must succeed, or must fail in order to get those answers.
Hope this helps.
--Will
Joe
Hi Will,
Thanks, I think that became more apparent when I reread the second
chapter again.
If I'm reading the code properly, it seems that the listo call in the
second line of the conde always produces an empty list. Is this
because the listo appears in the question subform of the expression?
That is, once the listo call succeeds by producing an association with
the fresh variable passed to it and () via nullo, it never tries the
remaining conde clauses in the listo method. But the lolo recursive
call, however, does produce multiple conde expression evaluations,
though, since it appears in the answer subform (provided that we pass
the run method a number of values high enough to actually cause these
expressions to be tried).
Is that right, or am I missing something?
If not, then I would be confused as to why 'run 5' produces a list of
empty lists, rather than a list of lists of reified variables.
Thanks for your help!
-- Joe
Will Byrd
> If I'm reading the code properly, it seems that the listo call in the
> second line of the conde always produces an empty list. Is this
> because the listo appears in the question subform of the expression?
> That is, once the listo call succeeds by producing an association with
> the fresh variable passed to it and () via nullo, it never tries the
> remaining conde clauses in the listo method. But the lolo recursive
> call, however, does produce multiple conde expression evaluations,
> though, since it appears in the answer subform (provided that we pass
> the run method a number of values high enough to actually cause these
> expressions to be tried).
>
> Is that right, or am I missing something?
>
> If not, then I would be confused as to why 'run 5' produces a list of
> empty lists, rather than a list of lists of reified variables.
You are correct--using the implementation of miniKanren from The
Reasoned Schemer, the call to lolo will only produce lists containing
the empty list. The second conde clause of listo will never be tried.
This is because the implementation of miniKanren given in the book
uses depth-first search. You can find an updated implementation that
uses an interleaving search strategy at:
http://kanren.sourceforge.net/
The interleaving search eventually tries all the clauses of listo:
(run5 (x)
(lolo `((a b) (c d) . ,x))
=>
`(()
(())
((_.0))
(() ())
((_.0 _.1)))
Hope this helps.
Cheers,
--Will
Joe
Will,
Yes, that's very helpful. I was under the impression that that
behavior was exhibited by design, not by the specifics of the
implementation. The book makes a distinction between question and
answer subforms in conde expressions. But with your last note, it
seems to me that there really is no distinction (and that the book
does that simply to make an analogy to cond in functional scheme
code). All relations established in conde expression subforms are
preserved so long as each one succeeds, and none are if any one fails.
Thanks for your patience. I'm new to logic programming and miniKANREN,
so I'm trying to understand everything thoroughly.
Cheers,
--Joe
Joe
As an aside, is there a more appropriate place to ask questions
regarding miniKANREN? Do you maintain a mailing list for the book?
Cheers,
--Joe
Will Byrd
> As an aside, is there a more appropriate place to ask questions
> regarding miniKANREN? Do you maintain a mailing list for the book?
I just created a new Google Group for miniKanren/The Reasoned Schemer-
related discussions:
http://groups.google.com/group/minikanren?hl=en
Cheers,
--Will
Oliver Ruebenkoenig
Hello Schemers!
The question that is bugging me is the following. I was wondering if the
scheme environment model could be done in another approach than presented
in SICP. So here is what I came up with:
Each time a procedure is created the arguments of the procedure are
replaced by unique symbols ( e.g. x is transformed to e.g. x-43). Once the
procedure is applied the variable x-43 gets is value assigned and the body
is evaluated.
At the end of the lifetime of a procedure the procedure's arguments also
have to be disposed.
This would allow to implement the environment in a single table. Does this
make any sense? I have the impression I have overlooked some detail of
what the SICP environment model provides. Thanks for you comments.
Oliver
Oliver Ruebenkoenig, <ruebenko AT uni-freiburg.de>