Scheme - 高階手続きによる抽象(値として返される手続き(合成関数を実装する手続き))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の1(手続きによる抽象の構築)、1.3(高階手続きによる抽象)、1.3.4(値として返される手続き)の問1.40、問1.41、問1.42、問1.43を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 1.40.

コード

sample.scm

(define tolerance 0.00001)

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

(define dx 0.00001)

(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))

(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

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

(define (cubic a b c)
  (lambda (x)
    (+ (cube x)
       (* a (square x))
       (* b x)
       c)))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> (f 0 0 0)

;Value: 2.6531990291797187e-5

1 ]=> (f 1 0 0)

;Value: 1.1227429100448376e-5

1 ]=> (f 0 1 0)

;Value: 3.668097353908429e-17

1 ]=> (f 0 0 1)

;Value: -.9999999999999863

1 ]=> (f 1 2 3)

;Value: -1.2756822036498454

1 ]=> 
(+ (cube -1.2756822036498454)
   (* 1 (square -1.2756822036498454))
   (* 2 -1.2756822036498454)
   3)

;Value: 4.935607478273596e-12

1 ]=> (f 50 100 150)

;Value: -47.98099731612768

1 ]=> 
(+ (cube -47.98099731612768)
   (* 50 (square -47.98099731612768))
   (* 100 -47.98099731612768)
   150)

;Value: 8.185452315956354e-12

問題 1.41.

コード

sample.scm

(define (inc x) (+ x 1))

(define (double f)
  (lambda (x) (f (f x))))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> ((double inc) 10)

;Value: 12

1 ]=> ((double inc) 15)

;Value: 17

1 ]=> (((double (double double)) inc) 5) ; 21

;Value: 21

問題 1.42.

コード

sample.scm

(define (inc x) (+ x 1))

(define (compose f g)
  (lambda (x)
    (f (g x))))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> ((compose square inc) 6)

;Value: 49

問題 1.43.

再帰的プロセス

コード

sample.scm

(define (repeated f n)
  (define (repeated-inner x n)
    (cond ((= n 0) x)
          ((= n 1) (f x))
          (else (f (repeated-inner x (- n 1))))))
  (lambda (x) (repeated-inner x n)))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> ((repeated (lambda (x) (+ x 1)) 10) 5)

;Value: 15

1 ]=> ((repeated square 2) 5)

;Value: 625

反復的プロセス

コード

sample.scm

(define (repeated f n)
  (define (repeated-inner n result)
    (if (= n 1)
        result
        (repeated-inner (- n 1) (f result))))
  (lambda (x) (repeated-inner n (f x))))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> ((repeated (lambda (x) (+ x 1)) 10) 5)

;Value: 15

1 ]=> ((repeated square 2) 5)

;Value: 625

前問1.42のcomposeを使った場合。

コード

sample.scm

(define (compose f g)
  (lambda (x)
    (f (g x))))

(define (repeated f n)
  (if (= n 1)
      (lambda (x) (f x))
      (compose f (repeated f (- n 1)))))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> ((repeated (lambda (x) (+ x 1)) 10) 5)

;Value: 15

1 ]=> ((repeated square 2) 5)

;Value: 625