Scheme - Advice visualizing problem 2.8.6

Author

Advice visualizing problem 2.8.6

Griff

2008-01-24, 10:27 pm

Hi folks,

I have been working on problem 2.8.6 in: http://www.scheme.com/tspl3/start.html#./start:h8

This is a problem that demonstrates mutual recursion.

When I expand the code on paper, I can see how the problem unfolds
(example at the end). However, in my minds eye, it is just not jumping
out at me how this works.

Any advice on how to reach that point other than more study?

(even? 3)
-------------
(or (zero? 3)
(odd? 2)
-------------
(or #f
(and (not (= 2 0))
(even? 1)))
----------------------
(or #f
(and #t
(or (zero? 1)
(odd? 0))))
------------------------
(or #f
(and #t
(or #f
(and (not (zero? 0))
(even? (sub1 0))))))
------------------------
(or #f
(and #t
(or #f
(and #f
------------------------
(or #f
(and #t
(or #f #f
------------------------
(or #f
(and #t #f
------------------------
(or #f #f
------------------------
#f

leppie

2008-01-25, 4:39 am

Griff wrote:
> Hi folks,
>
> I have been working on problem 2.8.6 in: http://www.scheme.com/tspl3/start.html#./start:h8
>
> This is a problem that demonstrates mutual recursion.
>

Here is one from the R6RS:

(letrec ((even?
(lambda (n)
(if (zero? n)
#t
(odd? (- n 1)))))
(odd?
(lambda (n)
(if (zero? n)
#f
(even? (- n 1))))))
(even? 88))

Marlene Miller

2008-01-26, 4:35 am

"Griff" wrote in message
>
> I have been working on problem 2.8.6 in:
http://www.scheme.com/tspl3/start.html#./start:h8
>
> This is a problem that demonstrates mutual recursion.
>
> When I expand the code on paper, I can see how the problem unfolds
> (example at the end). However, in my minds eye, it is just not jumping
> out at me how this works.
>
> Any advice on how to reach that point other than more study?
>
> (even? 3)
> -------------
> (or (zero? 3)
> (odd? 2)
> -------------
> (or #f
> (and (not (= 2 0))
> (even? 1)))
> ----------------------
> (or #f
> (and #t
> (or (zero? 1)
> (odd? 0))))
> ------------------------
> (or #f
> (and #t
> (or #f
> (and (not (zero? 0))
> (even? (sub1 0))))))
> ------------------------
> (or #f
> (and #t
> (or #f
> (and #f
> ------------------------
> (or #f
> (and #t
> (or #f #f
> ------------------------
> (or #f
> (and #t #f
> ------------------------
> (or #f #f
> ------------------------
> #f

You might try Not expanding the call to the other procedure.

(even? 3)

(or (= 3 0)
(odd? (- x 1)))

(or #f
(odd? (- x 1)))

(or #f
(odd? 2))

Stop. (odd? n) is #f when n is even

(or #f
#f)

#f

Done.

- - - -

(odd? 2)

(and (not (= 2 0)
(even? (- x 1))))

(and #t
(even? 1))

Stop. (even? n) is #f when n is odd

(and #t
#f)

#f

Done.

When I was reading about _infinite_ streams in SICP, I would expand and
expand and expand, just to make sure. Pages and pages of paper. I am use to
following the code to the lowest level at work because I have to be sure. At
some point I decided or realized when a function recurs, I evaluate the
expression given the contract of function.

I also wouldn't substitute both operands of an 'or' at the same time. If the
first operand is true, the second one isn't evaluated, is it.

> (or (zero? 3)
> (odd? 2)

I would think
(or (zero? 3) (odd? (- x 1)))

(or #f (odd? (- x 1)))

(odd? 2)

Sponsored Links