Introduction and Chapter 1

Started by
84 comments, last by bodchook 15 years, 4 months ago
Quote:Original post by Greig Hamilton
Exercise 1.6: My understanding is that in this case you can substitute the 'new-if' for the standard 'if'. Am I missing something? My understanding is that if is a more limited version (special case) of 'cond' and it can only contain single expressions for the <consequent> and <alternative>.


Ok, try evaluating this by hand, using the evaluation rule presented in the book:

(new-if (> 3 0) (begin (display "greater!") #t) (begin (display "less :(") #f))

Compare the results to those if you had just used if.

Quote:
Exercise 1.7: The reason the good-enough? test doesn't work very well for small values is because it stops too soon. For example 0.001 finds the sqrt to be 0.04124542607499115 when the actual sqrt is 0.03162277. This is because with small values the absolute difference is small but the difference relative to the size of the initial value is still quite big. So to correctly solve the above example you would need to use a smaller cutoff for example a difference of less than 0.000001.

The reason the good-enough? test doesn't work very well for large numbers is because if a number is so large that it is not possible to store the decimal place information then an infinite loop will result because the guess will never be close enough.


Yes.

Advertisement
Quote:Original post by Alpha_ProgDes
Alright I'm reading the notes and I came across this.
*** Source Snippet Removed ***
When will I have or even want to use the lambda expression over the shorter define expression? Or is it just syntactic sugar that I shouldn't worry about?


What if you wanted to define a toplevel procedure that closes over a free variable? Or, for example, perform some manipulation of the lambda expression, after-the-fact, e.g. (define expensive-pure-operation (memoize (lambda (...) ...)))
Quote:Original post by The Reindeer Effect
Quote:Original post by Greig Hamilton
Exercise 1.6: My understanding is that in this case you can substitute the 'new-if' for the standard 'if'. Am I missing something? My understanding is that if is a more limited version (special case) of 'cond' and it can only contain single expressions for the <consequent> and <alternative>.


Ok, try evaluating this by hand, using the evaluation rule presented in the book:

(new-if (> 3 0) (begin (display "greater!") #t) (begin (display "less :(") #f))

Compare the results to those if you had just used if.



Isn't "less :(") not a closed string? Won't this not work, no matter what? And what's >?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~I program in C++, on MSVC++ '05 Express, and on Windows. Most of my programs are also for windows.
Quote:Original post by The Reindeer Effect
Quote:Original post by Greig Hamilton
Exercise 1.6: My understanding is that in this case you can substitute the 'new-if' for the standard 'if'. Am I missing something? My understanding is that if is a more limited version (special case) of 'cond' and it can only contain single expressions for the <consequent> and <alternative>.


Ok, try evaluating this by hand, using the evaluation rule presented in the book:

(new-if (> 3 0) (begin (display "greater!") #t) (begin (display "less :(") #f))

Compare the results to those if you had just used if.



Is this because it evaluates the inner expressions anyway, even though they never execute, and therefore prints "less:(", ), and #f?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~I program in C++, on MSVC++ '05 Express, and on Windows. Most of my programs are also for windows.
The question:
(new-if (> 3 0) (begin (display "greater!") #t) (begin (display "less :(") #f))
Evaluating the above statement provides the following answer
greater!#t
This assumes the following extract from the book section 1.1.6.
"Conditional expressions are evaluated as follows. The predicate <p1> is evaluated first. If its value is false, then <p2> is evaluated. If <p2>'s value is also false, then <p3> is evaluated. This process continues until a predicate is found whose value is true, in which case the interpreter returns the value of the corresponding consequent expression <e> of the clause as the value of the conditional expression. If none of the <p'>'s is found to be true, the value of the cond is undefined."

I take the above to mean <p1> will be evaluated first and will be true. So <e1> will be evaluated and returned. <p2> (else in this case) will never be evaluated because <p1> is true.

This holds when using Lazy Scheme but does not hold for Standard (R5RS). Standard seems to evaluate both <e1> and <e2> first before evaluating <p1>.

Can someone explain why Standard evaluates both <e>'s before the predicate? I feel like I'm not understanding something still.
The general rule is that arguments are evaluated in order, from left to right, after which the resulting values are passed to the function being called. This is called "strict evaluation" and is what happens in your case: the predicate is evaluated first, then e1, then e2, and only after that the logic of your function is applied on these arguments (i.e. after e1 and e2 have already been evaluated, so there's no way of controlling it from within the function).

The strict evaluation order is inadequate for 'if', as you would want the 'then' and 'else' argument only to be evaluated when necessary.
(define (fib n)  (if (< n 2)      n      (+ (fib (- n 1))         (fib (- n 2)))))(fib 10)

Using strict evaluation, the 'else'-part would be evaluated each time (as would the 'then'-part of course), regardless of the condition, and the function would go off computing fibonacci for n going into the far negative, and you've got yourself an infinite computation on your hands (at least until your computer runs out of resources).

'if' needs to be "special", hence it has been promoted to one of the few "special forms" present in Scheme. These special forms have a different evaluation order, a non-strict one, where arguments are not evaluated immediately, but only when necessary, which is exactly what we need in our case.

You can't add your own special forms (what is possible though, is to make use of macros, which allow you to fine-tune the evaluation order, but that is an advanced topic). Functions you define will always be subjected to the strict evaluation order, and hence it is impossible for you to define a new if (or cond, or while-loop, or any other concept that needs to control how many times its arguments are evaluated).

You can fake it though by manually wrapping expressions in lambda's each time:
(define (my-if pred then else)  (if pred (then) (else)))(define (fib n)  (my-if (< n 2)        (lambda () n)        (lambda () (+ (fib (- n 1))                      (fib (- n 2))))))

but this is hardly elegant.


The reason the standard chose for strict evaluation order is possibly because it's the most efficient, most common and easiest to understand. Haskell is one of the few languages which strays from this path and offers non-strict evaluation by default, and it can afford that because of the language being purely functional. Using default non-strict evaluation in a language with side-effects would lead to chaos I'd guess.

If I remember correctly, a later chapter in SICP will be discussing an interpreter for a variant of Scheme where you can explicitly control the evaluation strategy for each of the arguments of a function you define.
Okay I get it now. Thanks for the help. :)
Quote:Original post by EmrldDrgn

Isn't "less :(") not a closed string? Won't this not work, no matter what? And what's >?


"less :(" is closed... we have an initial " and a terminal ". Everything in between is part of the string.

(> a b) returns #t if a is strictly greater than b, and #f otherwise.


And Sam, the actual order of argument evaluation is unspecified. The left-to-right thing is just how many systems naively evaluate; implementations are free to use some other order that may be more efficient. So don't rely on left-to-right evaluation for sequencing side effects.
Well here's my solution for Ex. 1.7. I'm not sure how it's better, but it seems to fit the requirements...
(define (sqrt x)    (sqrt-iter 1.0 5.0 x)) (define (sqrt-iter guess oldguess x)    (if (good-enough? guess oldguess x)        guess        (sqrt-iter (improve guess x) guess x)))(define (good-enough? guess oldguess x)    (< (abs (- oldguess guess)) (* 0.001 guess)))

Whaddaya say?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~I program in C++, on MSVC++ '05 Express, and on Windows. Most of my programs are also for windows.
Quote:Original post by EmrldDrgn
Well here's my solution for Ex. 1.7. I'm not sure how it's better, but it seems to fit the requirements...
*** Source Snippet Removed ***
Whaddaya say?


Since 'good-enough' doesn't need 'x' anymore, you can leave it out of the argument list. Also, if you'd want to use the same 'good-enough?' for say 'cube-root' (which is something you'll want to do):
(define (cube-root x)  (cube-root-iter 1.0 5.0 x))(define (cube-root-iter guess oldguess x)  (if (good-enough? guess oldguess)    guess    (cube-root-iter (improve guess x) guess x)))(define (improve guess x)  (* 1/3 (+ (* 2 guess) (/ x (* guess guess)))))(define (good-enough? guess oldguess)    (< (abs (- oldguess guess)) (* 0.001 guess)))> (cube-root 8)  2> (cube-root -8)  <infinite computation>

Why the infinite computation?

This topic is closed to new replies.

Advertisement