Here's the question you clicked on:
jolisper
I was working on the solution of the exercise 1.6 of the SICP book when I saw two different behaviors when I run the code depending on the numbers that I used. If I use natural numbers when I call the sqrt-iter procedure the interpreter just never stop but when I force the decimal division using float-point numbers the interpreter responds: Aborting!: maximum recursion depth exceeded. Does anyone know the reason for the different behavior? I made a gist with my answer to help anyone that wants to run the code, just copy & paste: http://bit.ly/Qv1wru
this problem is similar to this question asked at berkeley. I haven't been able to find the ans myself. http://inst.eecs.berkeley.edu/~cs61AS/fa12/lab/0.1.html Exercise 4.
i found ans to my question.
Hi @jagan, I read the exercise 4 and is true that is a similar exercise. In fact is like the exercise 1.5. But my question is aimed to the different behavior that the interpreter shows when you use natural numbers or decimal numbers. I wrote a note in my gist to point that. About the answer of the exercise I think that the key is the different evaluation of the primitive "if" and the "new-if" procedure. The primitive "if" ensure that the good-enough? procedure is called because the predicate part is evaluated first, so the end condition is reached at some point. But in the "new-if" implementation, because the alternative part (or else-clause) is evaluated first and in this part is there a recursive call to the sqrt-iter procedure this causes an infinitive loop. That is my better answer right now, I don't know if its totally correct. Please share your answer.
for exercise 4 : if construct in scheme evaluate conditionally,take the below example if (condition ) ( evaluate 1) (evaluate 2)) if condition is true then expression evalute1 is evaluated but evaluate2 is not -evaluated similarly if condition is false then expression evalute2 is evaluated but evaluate1 is not -evaluated. (define (infinite-loop) (infinite-loop)) is a recursive procedure call with no argument . If you call this method it will keep executing in an infinite loop. (if (= 3 6) (infinite-loop) (/ 4 2)) But the above if statement executed because condition is false and infinite loop procedure is not called, only last statement (/ 4 2) is executed.So it doesn't go into a infinite loop. But new definition of IF is called the (define (new-if test then-case else-case) (if test then-case else-case)) call to new-if (new-if (= 3 6) (infinite-loop) (/ 4 2)) , all sub expression will be evaluated according to substitution model of procedure call. So before procedure is called all sub expression in procedure call will be evaluated and (= 36) evaluates to false (infinite-loop) - procedure will be called which will get stuck in infinite loop so in this new-if construct both then and else case are executed before they are passed to the function . Where as in scheme if construct only one of the case executes based on the test condition. I don't know the reason for your code behaviors. I will go through this section 1.6 SICP if I get something will post it here.
It's a well explained response, thanks for sharing ;-)
did you miss the `abs` part of the `good-enough?` procedure? i think it has something to do with exercise 1.5: about how the interpreter evaluate the combination, applicative vs normal order. 'just never stop' and 'max recursion depth exceeded': it looks like the interpreter uses the applicative order. it tried to resolve all the subexpressions (operators and arguments) before applying the arguments to the operator. the mathematical procedures (+,-,/,*, etc) behaviour depends on how the interpreter treat numbers. i treat this as a matter of convention if i expect 0.5 from 1/2 i must multiply its result with a float eg: 1.0 (/ 1 2) ==> 1/2 (* 1.0 (/ 1 2)) ==> 0.5
Thanks @ajiwo you are right! I miss the `abs` part in the `good-enough?` procedure. I corrected in the gist. But the behavior is the same, obviously. As you say, those different behaviors depends on the interpreter internals. I will run the code on a different implementation to see if its change.
you pointed out very correctly @jolisper. I just tried the code on two different interpreters (DrScheme and MIT-GNU Scheme). At least on these two, the behavior is the similar to what you pointed out. I think it doesn't depend on the interpreter. It most probably has to do with floating point arithmetic. In a machine, floating point numbers are stored in a different format. There is an IEEE standard notation. So, I think, and I may be wrong: When you give a natural number x as an argument to sqrt-iter, it will try to computer a y such that y^2 = x (with some error tolerance)... Mathematically, we know that: if y^2 = x and x is a natural number -> y will be less than x so, in whatever format our machine (the hardware) stores the number x, if it can store x, it can also store y (because y < x). our machine will not run out of space. but floating numbers is a different story. there is this fractional part and exponent story (should refer to any article on floating point arithmetic). if i try to manually visualize the computations which might take place for a floating point number...then for any computation that wont stop...the machine is more likely to run out of space. The idea is still vague. Because then rises another question. when we try to evaluate (sqrt-iter 1 2), after the first iteration the variable guess (inside the definition of sqrt-iter) will not be a natural number any more. Because we will improve our guess by averaging by 2 but then, i must point out that neither it is a floating point number - it is FRACTION and not a floating point number. i mean, there is a difference between (/ 1 2) and (/ 1 2.) in scheme. the latter gives the answer .5 unlike 1/2 for the first expression. So, if you change the definition for the average procedure to (define (average x y) (/ (+ x y) 2.)) it will behave similarly for natural numbers and floating numbers. (because after the first iteration our guess will be a floating point number always irrespective of what we had before). Hope that answer some part of the question.
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/ Hope this helps
Here's another one http://www.greenteapress.com/thinkpython/