• Create Account

Introduction and Chapter 1

85 replies to this topic

#41Diodor  Members   -  Reputation: 517

Like
0Likes
Like

Posted 20 December 2006 - 04:42 AM

Well, for my humble first post here's my solution to exercise 1.3 (sum of the squares of biggest two out of three parameters).
(define (x1_3 x y z)  (- (+ (* x x) (* y y) (* z z))     (expt (min x y z) 2)));Version 2 to appease Ezbez :)(define (x1_3 x y z)  (define (** x) (* x x))  (+ (** x) (** y) (** z)     (- (** (min x y z)))))

[Edited by - Diodor on December 22, 2006 1:42:42 PM]

#42Ezbez  Crossbones+   -  Reputation: 1151

Like
0Likes
Like

Posted 22 December 2006 - 04:01 AM

Just for practice, Diodor, I think it might be good to write a square function that, well, squares something. You're doing that four times in your code, so it would sort of be worth it.

#43EmrldDrgn  Members   -  Reputation: 198

Like
0Likes
Like

Posted 23 December 2006 - 05:57 PM

I'm doing the really early exercises, and I want to check my answers, as it were.

1.1: 10,12,8,3,6,3,4,19,0,4,16,6,16
1.2:
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 1 3) ) ) ) ) (* 3 (- 6 2) (- 2 7)))

Yeilded -(43)/(180). Seems wierd to me. Reason for this post.
1.3:
(define     (square-two-bigger-add x y z)     (cond      ((and (> x z) (> y z) )      (+ (* x x) (* y y)))      ((and (> y x) (> z x) )      (+ (* y y) (* z z)))      ((and (> x y) (> z y))      (+ (* y y) (* z z)))      ))

1.4: If B is positive, add a and b. If not, subtract b from a.
1.5: An applicative-order evaluation returns 0, and a normal-order evaluation never ends. Oh, and because it tries to expand p infinitly, whereas AO never evaluates p.

So, am I right?

And do these forums have a [ SPOILER ] tag? And why doesn't the [ SOURCE ] tag recognize lang="scheme" as correct?

[Edited by - EmrldDrgn on December 24, 2006 1:57:23 AM]

#44Rebooted  Members   -  Reputation: 612

Like
0Likes
Like

Posted 23 December 2006 - 10:11 PM

Quote:
 Original post by EmrldDrgn1.2: *** Source Snippet Removed ***Yeilded -(43)/(180). Seems wierd to me. Reason for this post.

I think the fraction is 4/5, not 1/3.

This:
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))     (* 3 (- 6 2) (- 2 7)))

gives me an answer of -(37)/(150), which is correct. The interpreter is just giving the answer as an exact fraction. If you evaluate -37/150 on a calculator or enter (exact->inexact -37/150) into Dr Scheme, you will get the result -0.246666666666667.

Quote:
 1.3: *** Source Snippet Removed ***
This is basically the same as my solution, but I broke it down into smaller procedures:

(define (square x) (* x x))(define (sum-of-squares x y)  (+ (square x) (square y)))(define (sum-of-squares-of-largest-two a b c)  (cond ((and (> a c) (> b c)) (sum-of-squares a b))        ((and (> a b) (> c b)) (sum-of-squares a c))        (else (sum-of-squares b c))))

Quote:
 1.4: If B is positive, add a and b. If not, subtract b from a.
Yes.

Quote:
 1.5: An applicative-order evaluation returns 0, and a normal-order evaluation never ends. Oh, and because it tries to expand p infinitly, whereas AO never evaluates p.
Yes.

#45Diodor  Members   -  Reputation: 517

Like
0Likes
Like

Posted 29 December 2006 - 02:00 AM

Exercise 1.31a, iterative and variant using closures
(define (1+ x) ( + x 1))(define (1- x) (- x 1))(define (identity x) x)(define (product a step b factor)  (define (pgo x ret)    (if (> x b)        ret        (pgo (step x)             (* ret (factor x)))))  (pgo a 1))(define (factorial n)  (product 1 1+ n identity))(define (pi n)  (* 4.0 (product 2 1+ (1+ n)                  (lambda (x)                    (/ (+ x (modulo x 2))                       (+ x (modulo (1+ x) 2))))))); using closures to create counters for 1 1 3 3 5 5 ... type streams(define (make-2-counter start)  (let ((plus -1))    (lambda ()       (set! plus (+ plus 1))      (+ start plus (- (modulo plus 2))))))(define (pi n)  (let ((top (make-2-counter 2))        (bottom (make-2-counter 3)))    (top)    (* 4.0 (product 1 1+ n (lambda (x)  (/ (top) (bottom)))))))

Common Lisp for exercise 1.19 . I hadn't encountered calculating Fibonnaci in log(n) time and the method seems applicable to other recursive formulas.
(defun fib (n)  (labels ((fibgo (a b n p q s)             (cond ((= 0 n)                    (list a b))                   ((oddp n)                    (fibgo (+ (* p a) (* q b))                        (+ (* q a) (* s b))                        (- n 1)                        p q s))                   ((evenp n)                    (fibgo a b (/ n 2)                        (+ (* p p) (* q q))                        (+ (* p q) (* q s))                        (+ (* q q) (* s s)))))))    (car (fibgo 1 1 n 1 1 0))))

[Edited by - Diodor on December 29, 2006 8:00:37 AM]

#46Alpha_ProgDes  Crossbones+   -  Reputation: 4227

Like
0Likes
Like

Posted 18 February 2007 - 03:50 AM

I have no idea what I'm doing wrong here.
(define (choice y)    (cond ((< 0) (-10))  //it highlights the (< 0)          (else 10)))> (choice 67)

. <: expects at least 2 arguments, given 1: 0

#47SamLowry  Members   -  Reputation: 1382

Like
0Likes
Like

Posted 18 February 2007 - 03:58 AM

Quote:
 Original post by Alpha_ProgDesI have no idea what I'm doing wrong here.*** Source Snippet Removed ***. <: expects at least 2 arguments, given 1: 0

The < operator takes at least two arguments. 'cond' has no way of knowing you're comparing with 'y'. (Using macros, you could define your own control structures, but I'll leave that for a later time (macros are not discussed by SICP, so if you're interested, you can always ask later)).

Also, don't put the -10 between parentheses. Parentheses are never optional in Scheme, they always mean "a list", and without quotation it will be interpreted as a function call (in this case, calling the 0-arity function '-10').

(define (choice y)    (cond ((< y 0) -10)          (else 10)))

#48Alpha_ProgDes  Crossbones+   -  Reputation: 4227

Like
0Likes
Like

Posted 18 February 2007 - 04:03 AM

Quote:
Original post by SamLowry
Quote:
 Original post by Alpha_ProgDesI have no idea what I'm doing wrong here.*** Source Snippet Removed ***. <: expects at least 2 arguments, given 1: 0

The < operator takes at least two arguments, and don't put the -10 between parentheses. Parentheses are never optional in Scheme, they always mean "a list", and without quotation it will be interpreted as a function call (in this case, calling the 0-arity function '-10').

(define (choice y)    (cond ((< y 0) -10)          (else 10)))

#49Alpha_ProgDes  Crossbones+   -  Reputation: 4227

Like
0Likes
Like

Posted 18 February 2007 - 05:08 AM

(define we 12)> (define us (+ we 2))> us14> (define we 20)> us14

i take it "we" is basically a new object every time i redefine it. something like:
void define (int*& object, int value){    if (object != NULL)    {       delete object;    }    object = new int;    *object = value;}

i'm using Dr. Scheme by the way.

#50Rebooted  Members   -  Reputation: 612

Like
0Likes
Like

Posted 18 February 2007 - 05:58 AM

Pretty much; when you redefine a name, you might as well have used a fresh name: the only difference is syntax. It helps to think of define just creating a convenient name for some value, and the value being substituted into the code whenever you use the name. Later you'll see set!, which does destructive assignment.

#51SamLowry  Members   -  Reputation: 1382

Like
0Likes
Like

Posted 18 February 2007 - 06:25 AM

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)--> donex--> 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 ();;--> 5let 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.)

#52Alpha_ProgDes  Crossbones+   -  Reputation: 4227

Like
0Likes
Like

Posted 18 February 2007 - 02:47 PM

I have a semantics question.
(define (c-gt x y)  (cond ((> x y) x)  // why is the value contained in a list?        (else y)))(define (i-gt x y)  (if (> x y)       x              // when this value is standalone?      y))

#53The Reindeer Effect  Members   -  Reputation: 211

Like
0Likes
Like

Posted 18 February 2007 - 06:56 PM

Quote:
 Original post by Alpha_ProgDesI 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.

#54Alpha_ProgDes  Crossbones+   -  Reputation: 4227

Like
0Likes
Like

Posted 22 February 2007 - 03:51 PM

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!!!!?????

#55SamLowry  Members   -  Reputation: 1382

Like
0Likes
Like

Posted 22 February 2007 - 10:30 PM

Quote:
 Original post by Alpha_ProgDesOkay 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

#56Alpha_ProgDes  Crossbones+   -  Reputation: 4227

Like
0Likes
Like

Posted 23 February 2007 - 02:51 PM

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?

#57Rebooted  Members   -  Reputation: 612

Like
0Likes
Like

Posted 23 February 2007 - 08:50 PM

Quote:
 Original post by Alpha_ProgDesAlright 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.

#58Alpha_ProgDes  Crossbones+   -  Reputation: 4227

Like
0Likes
Like

Posted 24 February 2007 - 01:04 AM

Quote:
Original post by Rebooted
Quote:
 Original post by Alpha_ProgDesAlright 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?

#59Rebooted  Members   -  Reputation: 612

Like
0Likes
Like

Posted 24 February 2007 - 02:17 AM

Quote:
Original post by Alpha_ProgDes
Quote:
Original post by Rebooted
Quote:
 Original post by Alpha_ProgDesAlright 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.

#60Greig Hamilton  Members   -  Reputation: 181

Like
0Likes
Like

Posted 28 February 2007 - 04:58 AM

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.

PARTNERS