Understanding run n with conde in the Reasoned Schemer

I’m working through The Reasoned Schemer and had some trouble seeing clearly how results are returned when using run n. After Googling a bit, I found a clear walkthrough of the logic on an obscure message board. I’m reposting here to make sure it doesn’t disappear.

The key insight is that the n in run n refers not to the number of goals that should be tried, but rather the number of answers that should be returned, if available. Full text below:

Posted: Mon Jan 14, 2008 2:19 pm

Hi all,

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
=====================

Posted: Tue Jan 15, 2008 3:30 pm

(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

Share:
  • del.icio.us
  • Reddit
  • Technorati
  • Twitter
  • Facebook
  • Google Bookmarks
  • HackerNews
  • PDF
  • RSS
This entry was posted in programming. Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.