SICP 1章

計算機プログラムの構造と解釈

SICP(Structure and Interpretation of Computer Programs)…計算機科学の構造と解釈
という本を今読んでいます。

SICPの難しいところは数学の問題をLISPの文法で書くところ。
数学はわからんしLISPの文法もわからん。
まず、プログラミングGaucheLISPの文法に慣れておくこと良さそうです。

先週P34-P39を解いたのでUPします。

;;; 20101116_lambda.lisp
;;; 
;;; Chisei
;;;
;;; 範囲 P34-P39(1.3.2〜)
;;; 問題 1.34
;;;

(load "./sicp.scm")
;;; 前回のスクリプト
(define (inc n) (+ n 1))

(define (cube x) (* x x x))

(define (sum term a next b)
  (if (> a b)
    0
    (+ (term a)
       (sum term (next a) next b))))

(define (sum-cubes a b)
  (sum cube a inc b))
(print (sum-cubes 1 10))

;;; lambdaとは何か?

;; 解説
;; 先頭がlambdaである式をlambda式と呼びます。lambda式は評価
;; されると手続きオブジェクトになります。lambda式を用いると
;; 手続きに名前を与えずに生成することができます。

;; example

(print "--lambda example--")
(define (square x) (* x x))
(print ((lambda (x) (* x x)) 5)) ; arg^2
(print (square 5)) ; arg^2
(print "--/lambda example--")

;; 使いどころ
;; 代表的な例としては、一度限りしか使わないローカルな手続きです。

;; 豆知識
;; 今までdefineで手続きを定義してきた、
;; (define (<name> <arg> ...) <expression> ...)
;; という構文は次の構文の簡略表記にすぎません。
;; (define <name> (lambda (<arg> ...) <expression> ...))
;; 前者の手続き定義をMIT記法と呼ぶことがあります。

;; 応用
;; 以上lambdaの前提を基に、SICP1.3.1節の式を修正すると、

;; before pi-sum
(define (pi-sum a b)
  (define (pi-term x)
    (/ 1.0 (* x (+ x 2))))
  (define (pi-next x)
    (+ x 4))
  (sum pi-term a pi-next b))
(print (* 8 (pi-sum 1 1000)))

;; after pi-sum
(define (pi-sum a b)
  (sum (lambda (x) (/ 1.0 (* x (+ x 2))))
    a
    (lambda (x) (+ x 4))
    b))
(print (* 8 (pi-sum 1 1000)))

;; before add-dx
(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))
(print (integral cube 0 1 0.01))

;; after add-dx
(define (integral f a b dx)
  (* (sum f (+  a (/ dx 2.0))
          (lambda (x) (+ x dx))
          b)
     dx))
(print (integral cube 0 1 0.01))

;; defineとlambdaの相違
;; 唯一の相違は環境で名前と対応づけられていないことです。



;;; letとは何か?
;; f(x,y) = x(1 + xy)^2 + y(1 - y) + (1 + xy)(1 - y)
;; この式は、
;; a = 1 + xy
;; b = 1 - y
;; f(x,y) = xa^2 + yb + ab
;; となります。
(define (f x y)
  (define (f-helper a b)
    (+ (* x (square a))
       (* y b)
       (* a b)))
  (f-helper (+ 1 (* x y))
            (- 1 y)))
(print (f 2 3))

;; また、この式はlambdaが使用できます。
(define (f x y)
  ((lambda (a b)
     (+ (* x (square a ))
        (* y b)
        (* a b)))
   (+ 1 (* x y))
   (- 1 y)))
(print (f 2 3))

;; letを使用すると以下のようになります。
(define (f x y)
  (let ((a (+ 1 (* x y)))
        (b (- 1 y)))
    (+ (* x (square a))
       (* y b)
       (* a b))))
(print (f 2 3))

;; これだと自分はletの使いどころが不明だったので以下解説用の式
;; letを使用したタイミングでx=3と定義している。
;; ただし、letの外側のxは5なので33+5は38となる
(define x 5)
(print
  (+ (let ((x 3))
     (+ x (* x 10)))
     x))

;; 1行ずつ解体していく
(define (f x y)
  (let (
    ;; letの変数名、値 var1,exp1
    (a (+ 1 (* x y))) 
    ;; letの変数名、値 var2,exp2
    (b (- 1 y))
  )
  ;; bodyの中で上で設定した変数名が有効になる
  ;; squareはletの外から探される
  ;; さらに、+や*も外から探される
  (+ (* x (square a)) (* y b) (* a b))
  ) ; // let
) ; //define f
(print (f 2 3))

;;; 構文シュガーとは何か?
;; 別名はsyntax sugar
;; 読み書きのしやすさのために導入される構文
;; 以下は同義
(print "syntax sugar")
(print ((lambda (a b) (* a b)) 3 5))
(print (let ((a 3) (b 5)) (* a b)))

;;; 局所変数とは何か?
;; ローカル変数と認識

;;; 問1.34
(print "--1.34--")
(define (f g)
  (g 2))
(print (f square))
(print (f (lambda (z) (* z (+ z 1)))))
;(print (f f))
(print "--//1.34--")


;;; 区間二分法とは何か?
;; 解を含む区間の中間点を求める繰り返すことによって
;; 方程式を解く求根アルゴリズム
(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
      midpoint
      (let ((test-value (f midpoint)))
        (cond ((positive? test-value)
               (search f neg-point midpoint))
              ((negative? test-value)
               (search f midpoint pos-point))
              (else midpoint))))))
(define (close-enough? x y)
  (< (abs (- x y)) 0.001))
(print "--search")
(print (search sin 2.0 4.0))
(print "--//search")
(print (search (lambda (x) (- (* x x x) (* 2 x) 3))
                 1.0
                 2.0))

;;; 不動点とは何か?
;; x が f(x) = x を満たすとき、xを関数fの不動点という。
;; f(x),f(f(x)),f(f(f(x)))
(define tolerance 0.0001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
        next
        (try next))))
  (try first-guess))
(print (fixed-point cos 1.0))
(print (cos 0.739))

(define (sqrt x)
  (fixed-point (lambda (y) (/ x y))
               2.0))
;(print (sqrt 10))

(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
               1.0))
;; avg(1.0, 10/1.0) = 5
(print (sqrt 10))


;;; 逐次近似とは何か?

;;; 平均緩和法とは何か?

逐次近似、平均緩和法などわからないところがありました。

プログラミングGauche

プログラミングGauche