SICP 1.3.4 Procedures as returned values
Today I have learned that John Carmack was also challenged by SICP:
100 pages into Structure and Interpretation of Computer Programs. I'm proud of myself for not skipping the Church Numerals exercise. Twitter
I still need to get so far.
(define (cubic a b c) (lambda (x) (+ (* x x x) (* a x x) (* b x) c )) )
(define (inc x) (+ x 1)) (define (double f) (lambda (x) (f (f x))) )
(define (sqr x) (* x x)) (define (compose f g) (lambda (x) (f (g x))) ) ((compose sqr inc) 6)
(define (repeated f n) (if (= n 1) f (if (even? n) (repeated (double f) (/ n 2)) (compose f (repeated f (- n 1))) ) ) )
(define dx 0.000001) (define (smooth f) (lambda (x) (/ (+ (f x) (f (+ x dx)) (f (- x dx)) ) 3.0)) ) (repeated smooth 10)
(define tolerance 0.00001) (define (fixed-point f first-guess) (define (close-enough? v1 v2) (< (abs (- v1 v2)) tolerance)) (define (try guess limit) (display guess) (newline); to debug trace (let ((next (f guess))) (if (= limit 0) (error "Reached iteration limit") (if (close-enough? guess next) next (try next (- limit 1))) ))) (try first-guess 1000) ) (define (average-damp f) (lambda (y) (/ (+ (f y) y) 2)) ) (define (npow x n) (if (= n 1) x (* x (npow x (- n 1)) )) ) (define (n-root x n) (fixed-point ((repeated average-damp (/ n 2)) (lambda (y) (/ x (npow y (- n 1))))) 1 ) )
I saw on the internet solutions better than n / 2, but I would like to move on.
(define (iterative-improve good-enough next) (define (iter guess) (if (good-enough guess) guess (iter (next guess)) ) ) iter ) (define (~= a b) (< (abs (- a b)) 0.00001) ) (define (sqrt x) ((iterative-improve (lambda (y) (~= (* y y) x)) (lambda (y) (/ (+ y (/ x y)) 2)) ) 1.0) ) (define (fixed-point f first-guess) ((iterative-improve (lambda (y) (~= (f y) y)); not very optimal because we computing f twice f ) first-guess) )
And I could move to the chapter about data structures.