# Introduction and Chapter 1

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

## Recommended Posts

##### Share on other sites
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.

##### Share on other sites
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 steps
136

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

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

##### Share on other sites
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

##### Share on other sites
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?

##### Share on other sites
Quote:
 Original post by EzbezI'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]

##### Share on other sites
Quote:
 Original post by Anonymous PCan 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.

##### Share on other sites
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]

##### Share on other sites
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.

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

##### Share on other sites
Quote:
 Original post by joanusdmentiaWell, 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.

1. 1
2. 2
3. 3
Rutin
15
4. 4
khawk
13
5. 5
frob
12

• 9
• 9
• 11
• 11
• 23
• ### Forum Statistics

• Total Topics
633665
• Total Posts
3013247
×

## Important Information

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!