Jump to content
  • Advertisement
Sign in to follow this  
Alpha_ProgDes

Introduction and Chapter 1

This topic is 3470 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

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]

Share this post


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


Link to post
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)).

Muhammad Haggag: Please use code or source tags for code

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

Share this post


Link to post
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 this post


Link to post
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 this post


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

Share this post


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

Share this post


Link to post
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 this post


Link to post
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 this post


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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!