Sign in to follow this  

Introduction and Chapter 1

This topic is 3280 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Quote:
Original post by Alpha_ProgDes
*** Source Snippet Removed ***
i take it "we" is basically a new object every time i redefine it. something like:
*** Source Snippet Removed ***

i'm using Dr. Scheme by the way.


I'm not 100% sure what you really mean. There are multiple ways to answer that question.



'define' (re)binds the identifier to a value. If you write this in Scheme:

(define x 5)
(define (f) x)

(f)
-> 5

(define x 6)
(f)
--> 6

However, you cannot use this to achieve runtime mutability: if you use 'define' in a new environment/scope, the old value will be restored:

(define x 5)

(define (f)
(define x 6)
'done)

x
--> 5

(f)
--> done

x
--> 5

The 'define' in 'f' creates a new environment (scope limited to f's body), in which a new 'x' is created.

To show this is not a simple matter, consider the following O'Caml code:

let x = 5;;
let f () = x;;

f ();;
--> 5

let x = 6;;
f ();;
--> 5

Don't break your head over it for now, chapter 4 will make this more clear where you'll write your very own Scheme interpreter. I would suggest you don't think of 'define' as a way to redefine values; act as if it's only allowed to use one define per identifier per scope.
edit: I see that Scheme (DrScheme anyway) prevents you from 'defining' the same identifier twice in an environment which is not the top-level one, which is good.




There's also the "referential transparency" issue. In Scheme, everything works through pointers/references. If you were to work in C++ this way, you could have two different pointers to 5, without them being equal because they point to different memory cells:

int a = 5, b = 5;

int* p = &a;
int* q = &b;

p != q

As far as I know, there is no way to make this kind of distinction in Scheme with integers. Some languages take this approach everywhere: if you have two data structures containing the same data, they are indiscernible from each other. Only "object value" counts in these languages. Other languages such as C/C++/java/C#/... take into account "object identity": objects can represent the same values, yet have different identities (hence you need to use .equals() instead of == in java, etc.)

Share this post


Link to post
Share on other sites
Quote:
Original post by Alpha_ProgDes
I have a semantics question.
*** Source Snippet Removed ***


COND may have an arbitrary number of consequent expressions/commands for any particular predicate. For example, (cond ((> x y) (draw x) x) (else (draw y) y)) is valid. To do the same with an IF statement one would need to wrap the sequence with BEGIN. I'm not sure what the motivation was for the COND syntax... I guess they felt it was clearer to wrap a whole predicate/consequent clause in parentheses than have everything lifted up a level and have the meaning of terms in COND expression depend on some index.

Share this post


Link to post
Share on other sites
Quote:
Original post by Alpha_ProgDes
Okay Section 1.2 problem 1.10 is killing me!! I figured out the first two but I can't figure out (A 2 4). It goes 2 4 16, then 65536! What kinda wacked out function does that!!!!?????


Since this hasn't much to do with functional programming, feel free to skip the exercise.

If you're interested in the solution: you know that

  • A(1,0) = 0

  • A(1,n) = 2n if n > 0.



If you use this in the expansion of A(2,n) you get

A(2, n) = A(1, A(2, n-1))
= 2^A(2, n-1)
= 2^A(1, A(2, n-2))
= 2^(2^A(2, n-2))
= 2^(2^(2^A(2, n-3)))
= ...


So, using Knuth's up-arrow notation, we get A(2, n) = 2 ^^ n for n > 0:

A(2, 1) = 2 ^^ 1 = 2
A(2, 2) = 2 ^^ 2 = 22 = 4
A(2, 3) = 2 ^^ 3 = 222 = 16
A(2, 4) = 2 ^^ 4 = 2222 = 65536

Share this post


Link to post
Share on other sites
Alright I'm reading the notes and I came across this.

(define (square x)
(* x x))

(define square (lambda (x)
(* x x)))

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?

Share this post


Link to post
Share on other sites
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?
The first is sugar for the second. You would usually use the first form, but if you wanted to curry a function, for example, you would have to use the second form.

Share this post


Link to post
Share on other sites
Quote:
Original post by Rebooted
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?
The first is sugar for the second. You would usually use the first form, but if you wanted to curry a function, for example, you would have to use the second form.

Curry?

Share this post


Link to post
Share on other sites
Quote:
Original post by Alpha_ProgDes
Quote:
Original post by Rebooted
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?
The first is sugar for the second. You would usually use the first form, but if you wanted to curry a function, for example, you would have to use the second form.

Curry?
Currying comes up in one of Chapter 2's exercises. We covered it a little here.

Share this post


Link to post
Share on other sites
Just a couple of questions to make sure I am understanding this correctly. Well more I am just after feedback on if the answers I have are correct or if I am on completely the wrong track.

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

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 (...) ...)))

Share this post


Link to post
Share on other sites
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 >?

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
Quote:
Original post by SamLowry
Why the infinite computation?


Umm... maybe since it's a negative root the difference between guess and oldguess will be increasing, not decreasing? I'm not really sure... I'd have to play around with the code a little more than I've got time to do right now.

Share this post


Link to post
Share on other sites
Just finished exercise 1.3 (I'm going slowly I know):

(define (square x) (* x x))
(define (sum-of-squares x y) (+ (square x) (square y)))
(define (larger-sum-of-sqrs x y z)
(cond ((and (> x z) (> y z)) (sum-of-squares x y))
((and (> x y) (> z y)) (sum-of-squares x z))
((and (> y x) (> z x)) (sum-of-squares y z))))
(larger-sum-of-sqrs (insert test numbers x y z))


The assignment didn't say anything about arguments of the same number. Did any of you guys include a test for equal numbers?

Share this post


Link to post
Share on other sites
EDIT: I already found the bug in my code--my recursive version of cont-frac is broken. Fixed version appended to the message.

Exercise 1.38 is about approximating e using a continued fraction expansion of e - 2, where all the N terms are set to 1 and the D terms are a sequence as follows: 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, etc.

I wrote the following code, but it's not doing a very good job of approximating e:

(define (cont-frac n d k)
(if (= k 0)
0
(/ (n k) (+ (d k) (cont-frac n d (- k 1))))))

(define (cont-frac-iter n d k)
(define (iter k result)
(if (= 0 k)
result
(iter (- k 1) (/ (n k) (+ result (d k))))))
(iter k 0))

(define (calculate-e k)
(define (d i)
(let ((shifted-index (- i 2)))
(cond ((= i 2) 2.0)
((= 0 (remainder shifted-index 3)) (+ 2.0 (* 2.0 (/ shifted-index 3.0))))
(else 1.0))))
(+ 2.0 (cont-frac (lambda (i) 1.0) d k)))





Running it with 10000 iterations:
> (calculate-e 10000)
2.5000374981248825


Is something wrong with my code, or is the continued fraction approximation itself not good enough?

The problem was that my recursive cont-frac computed a different function (A continuous fraction that goes: Nk / (Dk + Nk-1 / (Dk-1 + ...)) instead of N1 / (D1 + N2 / (D2 + ...)). Fix0red:
(define (cont-frac n d k)
(define (inner-cont-frac i)
(if (= i k)
(/ (n i) (+ (d i)))
(/ (n i) (+ (d i) (inner-cont-frac (+ i 1))))))
(inner-cont-frac 1))


[Edited by - Muhammad Haggag on March 20, 2007 1:43:50 AM]

Share this post


Link to post
Share on other sites
Now that I've finished Chapter 1 (at laaaaaast!), there's one thing that's not entirely clear to me yet: "Visualization" (for lack of a better word) of higher-order procedures. Allow me to explain what I mean:

When I ran into exercise 1.41:
(define (double f)
(lambda (x) (f (f x))))
(((double (double double)) inc) 5)

My immediate (and incorrect) thought was that it'd produce 13 (as in, increment by 8). It produced 21. I spent about 20 minutes mulling over why that's the result. Apparently, what I thought it'd do was actually this:
((double (double (double inc))) 5)


After a while, I was able to understand that the first form quadruples the quadruple of increment, hence incrementing 16 times. What I don't like is that I don't have a "consistent thought process" to arrive at that conclusion. I did it in an ad-hoc manner, and I'm afraid I won't be able to grok similar combinations for other, perhaps more complicated, higher order procedures.

So, my question rephrased would be: How do you go about deciphering such combinations, or visualize them in your head or on paper?

Share this post


Link to post
Share on other sites

This topic is 3280 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this