You have problems, and we're glad to hear them. Explain the problem, what you have tried, and where you got stuck.
Feel free to share a little info on yourself and the course.
Forum rules
Please respect your teacher's guidelines. Homework is a learning tool. If we just post answers, we aren't actually helping. When you post questions, be sure to show what you have tried or what you don't understand.
-
philV
- Posts: 2
- Joined: Fri May 13, 2016 10:12 am
Post
by philV » Fri May 13, 2016 10:49 am
I am long time programmer wanting to learn LISP (Clojure), watching the 1986 MIT class on the "Structure and Interpretation of Computer Programs" on youtube. 23 minutes 56 seconds into the lecture 1B ;;
https://www.youtube.com/watch?v=dlbMuv-jix8
He gives a scheme recursive program to add 2 numbers, any insight would be appreciated!
Scheme version:
Code: Select all
(DEFINE (+ X Y)
(IF (= X 0)
Y
(1+ (+ (-1+ X) Y))))
(I've translated to Clojure and added some print statements).
Code: Select all
(defn z [x y]
(if (= x 0)
(do (println "x is zero x: " x " y: " y)
y)
(do (println "else x: " x " y: " y)
(inc (z (dec x) y)))))
here is the output:
Code: Select all
user> (z 4 9)
else x: 4 y: 9
else x: 3 y: 9
else x: 2 y: 9
else x: 1 y: 9
x is zero x: 0 y: 9
13
This I do not understand: the code says (= x 0) then y. When x is 0 y is 9 not 13!
-
David Mullen
- Posts: 78
- Joined: Mon Dec 01, 2014 12:29 pm
-
Contact:
Post
by David Mullen » Sat May 14, 2016 2:13 pm
Repeatedly printing X and Y doesn't reveal the whole process, whereas explicit nesting might make things clearer. The call
can be re-expressed, via the function definition, as:
Evaluating the innermost form, this becomes:
Rewriting the call to Z, like we did before, we have:
And so on—manually evaluating the innermost form every time:
Code: Select all
(inc (inc (z 2 9)))
=> (inc (inc (inc (z (dec 2) 9))))
=> (inc (inc (inc (z 1 9))))
=> (inc (inc (inc (inc (z (dec 1) 9)))))
=> (inc (inc (inc (inc (z 0 9)))))
=> (inc (inc (inc (inc 9))))
=> (inc (inc (inc 10)))
=> (inc (inc 11))
=> (inc 12)
=> 13
-
philV
- Posts: 2
- Joined: Fri May 13, 2016 10:12 am
Post
by philV » Sat May 14, 2016 4:17 pm
Thanks for replying! I understand your walk through of the recursion, it is obviously correct, but seems quite counter-intuitive.
At some point state is (inc (inc (inc (inc (z 0 9))))) and then the "If" resolves to y, which seemed to me to be the culmination and the answer is 9! Since the other branch of the "if" will never again be reached it appears to me to it would therefore be of no further interest. But in fact the evaluation of that unreachable branch does continue as you show below. Both branches of the "If" are resolved to a primitive even though one is unreachable from the code!