📌 Pinned 🔒 Locked

Introduction and Chapter 1

Started by Alpha_ProgDes Nov 14, 2006 at 4:35 PM 84 replies 55.6k views

Original Post

Nov 14, 2006 at 4:35 PM

As of right now, the main text we'll be using is SICP. Please read Chapter One. Until further notice, you'll have until December 31 to read, review, post example code, and ask questions pertaining to the material. Thanks. Please only post about questions pertaining to the Dedication, Preface to the 2nd edition, Preface to the 1st edition, and Chapter 1 in SICP. All other questions such as (but not limited to): compiler setup, which compiler to use, supplemental books, Lisp Vs. Scheme, AI w/ Scheme, Scheme vs. other functional programming languages should be asked in another thread. Thank you for participating [smile] Muhammad Haggag: Changed the title, added links to dedication, preface I and II Muhammad Haggag: Removed time limit from title [Edited by - Muhammad Haggag on May 8, 2007 10:04:29 AM]

Rebooted

Nov 16, 2006 at 3:47 PM

Remember to let us know how you're getting on and post any problems you're having.

Imperative programmers should remind themselves they need to be thinking in terms of expressions and not sequentially executed statements - section 1.1.5, "The Substitution Model for Procedure Application" has a good explanation of how evaluation works in Scheme.

Ezbez

Nov 16, 2006 at 6:48 PM

First off, I'm currently on 1.1.7.

I've got some questions regarding Example 1.5 where Ben Bitdiddle tests whether his interpreter is using normal-order or applicative-order evaluation. In section 1.1.5, it says, "(See exercise 1.5 for an instance of an ``illegitimate'' value where normal-order and applicative-order evaluation do not give the same result.)" What makes this 'illegitimate' (other than the infinite loop, that is)?

And on a related note, does anything use a 'hybrid' method of evaluation like so? (using the example from 1.1.5)

(f 5)(sum-of-squares (+ a 1) (* a 2))(+ (* a a) (* b b)) ;Where a is (+ a 1) and b is (* a 2) and a in those is 5(+ (* (+ a 1) (+ a 1) (* b b)) ;Now needs to evaluate (* a a), so it fills in a(+ (* (+ 5 1) (+ 5 1) (* b b)) ;Comes to the other a, fills it in;And skip a couple steps(+ 36 (* b b))(+ 36 (* (* a 2) (* a 2))) ;Comes to b, needs to replace it(+ 36 (* (* 5 2) (* 5 2))) ;Replaces a;Skip some boring steps136

So, in this manner, it only evaluates a parameter when it has the need to actually use it, and at that point, it replaces all of the ocurances of that parameter in the function. Seems like it would avoid unnecessary evaluation (like evaluating p in Example 1.5), but wouldn't require computing anything twice. The main problem that I see right now is scope-confusion (like the two different as in this problem, 5 and (+ a 1)).

Muhammad Haggag: Please use code or source tags for code

[Edited by - Muhammad Haggag on November 18, 2006 7:48:20 AM]

Ceoddyn

Nov 16, 2006 at 8:05 PM

I've read up to 1.1.3 and decided to do some fun stuff:

;recursive factorial(define (fact x)    (if (< x 2)        1        (* x (fact (- x 1)))));recursive fibonacci numbers (fun and slow!)(define (fib x)  (if (< x 3)      1      (+ (fib (- x 1)) (fib (- x 2)))))

while I eat dinner I'm calculating (fib (fact 5)), stay tuned for an answer!

I can see how people say lisp is a fun language to use, its a change from the norm, but I was wondering if anyone has some examples of applications/games created in lisp?

edit: I disappointedly came back and realized it wasn't going to finish in this century, so I settled for (fib 40) which turns out to be 102334155

Anonymous P

Nov 17, 2006 at 3:11 AM

Quote:
I've got some questions regarding Example 1.5 where Ben Bitdiddle tests whether his interpreter is using normal-order or applicative-order evaluation. In section 1.1.5, it says, "(See exercise 1.5 for an instance of an ``illegitimate' value where normal-order and applicative-order evaluation do not give the same result.)" What makes this 'illegitimate' (other than the infinite loop, that is)?

A call to (p) never terminates, so it does not yield any value. That's why it's illegitimate; it never returns a value. So yeah, the infinite loop.

I hope you noticed that applicative evaluation of

(test 0 (p))

also never terminates, while normal order evaluation of

(test 0 (p))

yields 0.

Quote:
And on a related note, does anything use a 'hybrid' method of evaluation like so? (using the example from 1.1.5)

That's called call-by-name evaluation or lazy evaluation. Haskell uses it, for example.

Can you think of a reason why C++ or scheme or other imperative languages choose NOT to use such an evaluation scheme by default?

joanusdmentia

Nov 17, 2006 at 3:58 AM

Quote:
Original post by Ezbez
I've got some questions regarding Example 1.5 where Ben Bitdiddle tests whether his interpreter is using normal-order or applicative-order evaluation. In section 1.1.5, it says, "(See exercise 1.5 for an instance of an ``illegitimate'' value where normal-order and applicative-order evaluation do not give the same result.)" What makes this 'illegitimate' (other than the infinite loop, that is)?

When using applicative-order (p) is evaluated immediately and you get the infinite loop. When using normal-order though test is substitute in, the if expression is evaluated, and since x=0 the result of the expression is 0, (p) never gets evaluated. You get 2 different results, so the expression is 'illegitimate'. At least, I think that's right [smile]

joanusdmentia

Nov 17, 2006 at 4:04 AM

Quote:
Original post by Anonymous P
Can you think of a reason why C++ or scheme or other imperative languages choose NOT to use such an evaluation scheme by default?

Presumably because of potential side-effects a procedure might have? Haskell on the other-hand can get away with it since it's purely functional.

joanusdmentia

Nov 17, 2006 at 4:59 AM

Well, I just finished up section 1.1 and jumped ahead a bit and implemented a generic Newton's method roots solver. Look reasonable? Crappy? "Oh my god, my brain cells are dying" bad?

;;;; Newtons method for finding roots of a function(define (newton-method guess prev-guess x improve)  ;; Calculate the ratio of change between guesses  (define (change-ratio)    (abs (/ (- prev-guess guess) guess)))  ;; Check if the change in the guesses is small  (define (good-enough?)    (< (change-ratio) 0.000001))    ;; Perform newton's method  (if (good-enough?)      guess      (newton-method (improve guess x)                     guess                     x                     improve)));;;; Utility math functions(define (average x y)  (/ (+ x y) 2));;;; Approximate the square root(define (sqrt x)    ;; Function for improving the sqrt  (define (sqrt-improve guess x)    (average guess (/ x guess)))    ;; Calculate the sqrt using newton's method  (newton-method 1.0 x x sqrt-improve));;;; Approximate the cube root(define (cbrt x)    ;; Function for improving the cube root  (define (cbrt-improve guess x)    (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))  ;; Calculate the cube root using newton's method  (newton-method 1.0 x x cbrt-improve))

Btw, what development environments are people using? I'm currently using a plugin for Eclipse called SchemeScript (part of the SchemeWay project). It comes with 2 Java-based interprets embedded into it (SISC and Kawa), so it's fairly convenient if you already use Eclipse.

[Edited by - joanusdmentia on November 17, 2006 8:59:07 AM]

SamLowry

Nov 17, 2006 at 6:11 AM

Quote:
And on a related note, does anything use a 'hybrid' method of evaluation like so? (using the example from 1.1.5)

SICP will show you later how to achieve that (in section 3.5), although it certainly won't be as transparent as in languages which directly support it (such as Haskell or Oz).

Quote:
Original post by Anonymous P
Quote:
And on a related note, does anything use a 'hybrid' method of evaluation like so? (using the example from 1.1.5)
That's called call-by-name evaluation or lazy evaluation. Haskell uses it, for example.

Call-by-name is not the same as lazy evaluation.

Call-by-name or nonstrict evaluation is only evaluating the arguments whose value is needed, but this can happen more than once if this value is needed multiple times.

Call-by-need or lazy evaluation is call-by-name + memoization: values are only computed if necessary, and only once.

Haskell is guaranteed to be nonstrict, but whether it is actually lazy depends on the implementation.

SamLowry

Nov 17, 2006 at 7:21 AM

Quote:
Original post by joanusdmentia
Well, I just finished up section 1.1 and jumped ahead a bit and implemented a generic Newton's method roots solver. Look reasonable? Crappy? "Oh my god, my brain cells are dying" bad?
*** Source Snippet Removed ***

I'd say it's all right.

The only thing that strikes me as a bit odd is the fact that you use functions for constant values like change-ratio and good-enough?, but I guess that's because SICP hasn't explained yet how to use define with values or how to use the let-construct.

Also, notice you're using the arguments of the "outer function" inside your helper functions. I have a question for you: why don't C/C++ allow such local function definitions?

Quote:

Btw, what development environments are people using? I'm currently using a plugin for Eclipse called SchemeScript (part of the SchemeWay project). It comes with 2 Java-based interprets embedded into it (SISC and Kawa), so it's fairly convenient if you already use Eclipse.

I use Dr. Scheme.

joanusdmentia

Nov 17, 2006 at 8:18 AM

Quote:
Original post by SamLowry
I'd say it's all right.

The only thing that strikes me as a bit odd is the fact that you use functions for constant values like change-ratio and good-enough?, but I guess that's because SICP hasn't explained yet how to use define with values or how to use the let-construct.

Umm, change-ratio and good-enough? aren't constant, they're dependant on the current and previous guesses....or am I overlooking something?

Quote:
Original post by SamLowry
Also, notice you're using the arguments of the "outer function" inside your helper functions. I have a question for you: why don't C/C++ allow such local function definitions?

I don't think there's anything that technically prevents C/C++ having local functions, it was just avoided because of the complications it can add since knowledge about the layout of the caller's stack would be required. IIRC gcc actually allows nested functions as an extension. It would also make it harder to debug since local functions would be able to modify local variables without having any obvious connection to them. For example:

void func(int a){    int b = 1;    void inner_func()    {        b = 2;    }    inner_func();    // There would be no way of knowing 'b' was    // modified without looking at inner_func()    printf("%i\n", b);}

SamLowry

Nov 17, 2006 at 11:01 AM

Quote:
Original post by joanusdmentia
Quote:
Original post by SamLowry
I'd say it's all right.

The only thing that strikes me as a bit odd is the fact that you use functions for constant values like change-ratio and good-enough?, but I guess that's because SICP hasn't explained yet how to use define with values or how to use the let-construct.

Umm, change-ratio and good-enough? aren't constant, they're dependant on the current and previous guesses....or am I overlooking something?

I meant both those values remain constant within the body. Once within the body, you could compute 'change-ratio' and 'good-enough?' once and for all and bind the results to variables. Of course, this has to happen each time 'newton-method' is called. But remember, this is nothing more than nitpicking.

Anyway, this works too:

;; Notice the different usage: no more function calling on 'change-ratio' and 'good-enough?'(define (newton-method guess prev-guess x improve)  ;; Calculate the ratio of change between guesses  (define change-ratio    (abs (/ (- prev-guess guess) guess)))  ;; Check if the change in the guesses is small  (define good-enough?    (< change-ratio 0.000001))    ;; Perform newton's method  (if good-enough?      guess      (newton-method (improve guess x)                     guess                     x                     improve)))

Another question then :) What advantages/disadvantages are there to my way and your way? When does using functions for 'change-ratio' and 'good-enough?' become interesting?

Quote:

Quote:
Original post by SamLowry
Also, notice you're using the arguments of the "outer function" inside your helper functions. I have a question for you: why don't C/C++ allow such local function definitions?

I don't think there's anything that technically prevents C/C++ having local functions, it was just avoided because of the complications it can add since knowledge about the layout of the caller's stack would be required. IIRC gcc actually allows nested functions as an extension. It would also make it harder to debug since local functions would be able to modify local variables without having any obvious connection to them. For example:

*** Source Snippet Removed ***

I'm not familiar with GCC, what would happen here:

typedef int (*counter)();void make_counter(){    int counter = 0;    int increment()    {        return ++counter;    }    return increment;   }int main(){    counter ctr = make_counter();    std::cout << ctr() << std::endl              << ctr() << std::endl;}

Colin Jeanne

Nov 17, 2006 at 12:07 PM

The pseudo-C++ code is equivalent to the following

class Counter {  count = 0;  public:    int operator () {      return ++count;    }};#include <iostream>int main() {  Counter c;  std::cout << c() << endl;  std::cout << c() << endl;}

Output:12

That is (if you're not familiar with C++ or functors), it makes an object which stores a current count. Each time you access or call this object it gives you the number of times you've accessed the object (starting at 1).

SamLowry

Nov 17, 2006 at 12:53 PM

Quote:
Original post by Colin Jeanne
The pseudo-C++ code is equivalent to the following

*** Source Snippet Removed ***
Output:12
That is (if you're not familiar with C++ or functors), it makes an object which stores a current count. Each time you access or call this object it gives you the number of times you've accessed the object (starting at 1).

Yes that'd be the way to do it in C++/C#/Java/... but I was wondering how the GCC extension joanusdmentia mentioned would make that code behave. Normally C++ doesn't know about closures, but my code would make use of them. I would expect it to corrupt memory leading sooner or later to a crash.

joanusdmentia

Nov 17, 2006 at 5:06 PM

Quote:
Original post by SamLowry
I meant both those values remain constant within the body. Once within the body, you could compute 'change-ratio' and 'good-enough?' once and for all and bind the results to variables. Of course, this has to happen each time 'newton-method' is called. But remember, this is nothing more than nitpicking.

Anyway, this works too:
*** Source Snippet Removed ***

Ahh, ok then, so the apparently superfluos brackets actually change the meaning. With them, the define'd expression is evaluated each time and without them it's evaluated the once (ie. it's constant). I had tried remove the brackets where those 2 were being evaluated and got some errors so put them back, but I didn't think to remove them from the defines as well.

Quote:
Original post by SamLowry
Another question then :) What advantages/disadvantages are there to my way and your way? When does using functions for 'change-ratio' and 'good-enough?' become interesting?

Hmm, would change-ratio and good-enough? be evaluated *before* the main body of the newton-method function in your case, whereas in mine they would be evaluated during? If so then I think yours might have a performance benefit as mine would produce a more complicated expression tree. As for when they would benefit from being functions, when they take parameters other than those of the outer function I suppose (eg. called twice from the main body with different parameters).

Quote:

I'm not familiar with GCC, what would happen here:
*** Source Snippet Removed ***

I've only seen the extension mentioned in a couple of places, but have never really used it before. I doubt that your code (with whatever syntactic sugar gcc wants) would compile though, because increment() would require the stack of make_counter() to exist you wouldn't be allowed to call it through a function pointer from outside of make_current(). I'd imagine the type of '&increment' would have to behave somewhat like pointer-to-members, you would be allowed to return the pointer and pass it around but only be allowed to call it from within make_counter() and couldn't cast it to a normal function pointer.

thebolt00

Nov 17, 2006 at 5:44 PM

Quote:
Original post by joanusdmentia
Ahh, ok then, so the apparently superfluos brackets actually change the meaning. With them, the define'd expression is evaluated each time and without them it's evaluated the once (ie. it's constant). I had tried remove the brackets where those 2 were being evaluated and got some errors so put them back, but I didn't think to remove them from the defines as well.

Yes, the form with brackets is accualy a short form. When reading

(define (average x y)  (/ (+ x y) 2))

it is accualy expanded to (and then executed as)

(define average  (lambda (x y)    (/ (+ x y) 2)))

Now, the construct "lambda" isn't introduced until section 1.3.2 (lambda is used to create a procedure value), but we can anyhow say something about the define keyword. define works as

(define name value)

which when evaluated creates the name (slot) "name" and binds the "value" to it. The value can be of any Scheme type, and as Scheme use applicative evaluation it will be evaluated and reduced to smallest form before the binding is done.

Quote:
Original post by joanusdmentia
Hmm, would change-ratio and good-enough? be evaluated *before* the main body of the newton-method function in your case, whereas in mine they would be evaluated during? If so then I think yours might have a performance benefit as mine would produce a more complicated expression tree. As for when they would benefit from being functions, when they take parameters other than those of the outer function I suppose (eg. called twice from the main body with different parameters).

Exactly. The expressions within a procedure are evaluated top-down (that is one of few times the order of evaluation is clearly defined).

-M

SamLowry

Nov 17, 2006 at 5:52 PM

Quote:
Original post by joanusdmentia
Ahh, ok then, so the apparently superfluos brackets actually change the meaning. With them, the define'd expression is evaluated each time and without them it's evaluated the once (ie. it's constant). I had tried remove the brackets where those 2 were being evaluated and got some errors so put them back, but I didn't think to remove them from the defines as well.

Something like that, yes. When using the parens, you're defining a function, meaning that when you "use" the value, you need to put 'change-ratio' or 'good-enough?' between a pair of (), which denotes a function call. When no parens are present in the define, you just define a value which you can use by referring to it by name without extra ().

(define x 5)(print x);; or(define (x) 5)(print (x))

In case you're familiar with lambdas:

(define (myfunc args)  body);; is the same as(define myfunc  (lambda (args)    body))

Quote:

Quote:
Original post by SamLowry
Another question then :) What advantages/disadvantages are there to my way and your way? When does using functions for 'change-ratio' and 'good-enough?' become interesting?

Hmm, would change-ratio and good-enough? be evaluated *before* the main body of the newton-method function in your case, whereas in mine they would be evaluated during? If so then I think yours might have a performance benefit as mine would produce a more complicated expression tree. As for when they would benefit from being functions, when they take parameters other than those of the outer function I suppose (eg. called twice from the main body with different parameters).

In "real" scheme (and not the substitution model used in the current chapter) both values would indeed be computed first, after which the body gets evaluated. The main difference I had in mind was the fact that in my case, the values for 'change-ratio' and 'good-enough?' will only be computed once, regardless of how many times they're used in the body, while using a function will have the same expressions evaluated multiple times. Using functions (like in your version) would be necessary if the arguments to 'newton-method' were to change inside the body: this way the values for 'change-ratio' and 'good-enough?' are guaranteed to be valid for the current values of the arguments (automatic "synchronisation" because you re-evaluate it each time). But this is stateful programming, and will only be handled in a later chapter.

I wanted to mention this because replacing data with code is a pattern which often returns.

Both your arguments are of course also correct.

Quote:

Quote:

I'm not familiar with GCC, what would happen here:
*** Source Snippet Removed ***

I've only seen the extension mentioned in a couple of places, but have never really used it before. I doubt that your code (with whatever syntactic sugar gcc wants) would compile though, because increment() would require the stack of make_counter() to exist you wouldn't be allowed to call it through a function pointer from outside of make_current(). I'd imagine the type of '&increment' would have to behave somewhat like pointer-to-members, you would be allowed to return the pointer and pass it around but only be allowed to call it from within make_counter() and couldn't cast it to a normal function pointer.

Indeed, the stack makes it problematic. Using Scheme, you'll be often returning functions like this (section 1.3.4), and there won't be such a problem. How Scheme does it will be handled in a later chapter. It might be interesting to watch out for those little differences between Scheme and C++.

I'll stop bothering you like this (for now :)), I hope I'm not confusing you too much, feel free to tell me so. My reason for doing this is mainly to be able to find out which little "assumptions" you make about Scheme, like thinking it's the same as in other languages you're used to. A lot of confusion arises from this kind of small details which more experienced Scheme-users take for granted and fail to point out.

joanusdmentia

Nov 17, 2006 at 6:22 PM

Quote:
Original post by SamLowry
I'll stop bothering you like this (for now :)), I hope I'm not confusing you too much, feel free to tell me so. My reason for doing this is mainly to be able to find out which little "assumptions" you make about Scheme, like thinking it's the same as in other languages you're used to. A lot of confusion arises from this kind of small details which more experienced Scheme-users take for granted and fail to point out.

Don't worry, you're not confusing me. In fact the bombardment has been quite good to get me thinking about it, I'm far too used to imperative languages and certain assumptions have become reflex rather than me having to actually think about it [smile] I've got some experience with functional languages (Haskell and Prolog, although it has been a couple of years now) so I'm certainly not stumbling around in the dark.

Ceoddyn

Nov 17, 2006 at 8:06 PM

Copying from my last post as it was poorly placed in my post

I can see how people say lisp is a fun language to use, its a change from the norm, but I was wondering if anyone has some examples of applications/games created in lisp?

Alpha_ProgDes

Nov 17, 2006 at 8:14 PM

Quote:
Original post by Ceoddyn
I can see how people say lisp is a fun language to use, its a change from the norm, but I was wondering if anyone has some examples of applications/games created in lisp?

Quote:
Please only post about questions pertaining to Chapter 1 in SICP. All other questions such as (but not limited to): compiler setup, which compiler to use, supplemental books, Lisp Vs. Scheme, AI w/ Scheme, Scheme vs. other functional programming languages should be asked in another thread.

Plus you already asked that question here

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.