はむはむエンジニアぶろぐ

365日エンジニアリング

SICPの問題1.1〜1.6を解いてみた

f:id:secret_hamuhamu:20150524211758j:plain
皆さん、SICP読んでますか?
難しいですよね(´・ω・`)w
当方、数学無知なのでついていくの辛いですが理解できると楽しいです。
本を読んだだけでは、本質的な理解に繋がらないので問題を解いてみます。

問題1.1

問題1.1は、書籍の内容を写経するもの。

gosh> 10
10
; 数字は、基本的な式である

gosh> (+ 5 3 4)
12

gosh> (- 9 1)
8

gosh> (/ 6 2)
3

gosh> (+ (* 2 4) (- 4 6))
6
; (2 * 4) + (4 - 6) = 6

gosh> (define a 3)
a
gosh> a
3
; aに3を代入

gosh> (define b (+ a 1))
b
gosh> b
4
; bに4を代入

gosh> (+ a b (* a b))
19
; a + b + (a * b) = 19
; 3 + 4 + (3 * 4) = 19

gosh> (= a b)
#f
; aとbは等しくないので、#f(false)
gosh> (= a a)
#t
; 問題にはなかったけれども、aとaは等しいので、#t(true)

gosh> (if (and (> b a) (< b (* a b))) b a)
4
; Cで書き直すとこんな感じになる
; if (b > a && b < (a * b)) {
;   return a;
; } else {
;   return b;
; }
;
; elseになるので、bが評価される

gosh> (cond ((= a 4) 6) ((= b 4) (+ 6 7 a)) (else 25))
16
; (= a 4)は、falseの為、次の条件式を評価する
; (= b 4)は、trueの為、(+ 6 7 a)を評価する

gosh> (+ 2 (if (> b a) b a))
6
; b > aは、trueなので(2 + b)となる

gosh> (* (cond ((> a b) a) ((< a b) b) (else -1)) (+ a 1))
16
; (< a b)が、trueの為、bを評価する
; (b * (a + 1) = 16
; (4 * (3 + 1) = 16

問題1.2

次の式を前置記法に翻訳せよ。

式は書籍に記載されてるので、割愛。

gosh> (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)))
-37/150
; 分数が返ってくる
gosh> (exact->inexact -37/150)
-0.24666666666666667
; 分数を展開したければ、exact->inexactを使う

gosh> (/ (+ 5 4 (- 2 (- 3 (+ 6 4/5)))) (* 3 (- 6 2) (- 2 7)))
-37/150
; 少し省略して書いた式
; (/ 4 5)を4/5としている
; 基本式であればの組み合わせであれば、分数を省略して掛けるようである
; 以下の様に合成式の組み合わせは、分数を省略してかけないようである

gosh> ((+ 5 4 (- 2 (- 3 (+ 6 4/5))))/(* 3 (- 6 2) (- 2 7)))
  *** ERROR: invalid application: (74/5 #<subr /> -60)
gosh> (+ 2 2)/5
4
gosh> *** ERROR: unbound variable: /5

問題1.3

三つの数を引数としてとり、大きい二つの数の二乗の和を返す手続きを定義せよ。

gosh> (define (square x) (* x x))
square
; 2乗する手続き

gosh> (define (sum-of-squares x y) (+ (square x) (square y)))
sum-of-squares
; 2乗して2つの数値の和をとる手続き

gosh> (define (func x y z)
  (cond ((and (< x y) (< x z)) (sum-of-squares y z)) ; yとzが最も大きい
        ((and (< y x) (< y z)) (sum-of-squares x z)) ; xとzが最も大きい
        (else (sum-of-squares x y))                  ; xとyが最も大きい
  )
)
func

gosh> (func 1 2 3)
13
; (2 * 2) + (3 * 3)

gosh> (func 5 4 3)
41
; (5 * 5) + (4 * 4)

gosh> (func 5 11 9)
202
; (11 * 11) + (9 * 9)

問題1.4

われわれの評価モデルは、演算子が合成式である組合せでも使えることを観察せよ。 それに従って、次の手続きの振舞いを述べよ。

(define (a-plus-abs-b a b)
   ((if (> b 0) + -) a b))
gosh>  (a-plus-abs-b 3 4)
7
; (+ a b)と評価される

gosh>  (a-plus-abs-b 3 -4)
7
; (- a b)と評価される

Lispは、 +- といった演算子は、言語構造に組み込まれていない関数である。
その他の言語は演算子が、言語構造に組み込まれていることが、ほとんどなので、このような芸当はできない。


Lispは、関数の上書きが出来るため、 + 関数を上書きすることが出来る。

gosh> (define (+ x y) 1)
+
; +関数を上書きして、1を返すようにする

gosh> (+ 5 5)
1
; 上書きされたので、1が返る

問題1.5

Lispの解釈系が、 作用的順序の評価 を使っているのか?
正規順序の評価 を使っているのか? 証明を行う。


先に、どちらの評価方法で解釈しているか答えを言うと解釈系によって異なる。
しかし、多くのLispの解釈系は、 作用的順序の評価 を使っている。
理由は、式の多重評価を避ける事で、効率が良くなるから。

とりあえず、両者の解釈の違いを見比べてみる

(define (f a)
  (sum-of-squares (+ a 1) (* a 2)))
f

解釈の違いを比べるために f という関数を使う。
sum-of-squaresは、問題1.3にて定義している。

作用的順序の評価

引数を評価しながら(作用的)、関数を展開する。

(f 5)
(sum-of-squares (+ a 1) (* a 2))
(sum-of-squares (+ 5 1) (* 5 2))
(+ (square 6) (square 10))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

正規順序の評価

関数を完全に展開し、評価を行う。

(f 5)
(sum-of-squares (+ 5 1) (* 5 2))
(+ (square (+ 5 1)) (square (* 5 2)))
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2))) ; (+ 5 1) や (* 5 2)は多重評価されている
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

結果は、 作用的順序の評価 と同じですが多重評価されている。

解釈系がどちらの順序評価を行っているかという証明

どちら順序評価を行っているという証明を行うには、以下の関数で行うことが出来る。

(define (p) (p))
p
; 再帰的に自分自身(p) を呼び出し続ける無限ループ再帰的関数

(define (test x y)
  (if (= x 0)
    0
    y))
test
; 作用的順序の評価を行っているか証明する関数

(test 0 (p))
; 証明する

(test 0 (p)) を行うとどうなるでしょうか?
無限ループする?0が返ってくる?

実行してみましょう。
無限ループすれば、あなたの解釈系は、 作用的順序の評価 を行っている。
0が、返ってくれば、 正規順序の評価 を行っている。

作用的順序の評価のであれば、最初に引数の 0(p) を評価します。
その為、無限ループに陥ります。
正規順序の評価であれば、 (p) を評価せず if (= x 0) の評価結果である0が返ってくることになります。


もうちょっと、作用的順序の評価 と 正規順序の評価の動作を深ぼってみたい。
しかし、基本的に解釈系の順序評価の変更を行えないので、 DrRacket というLispの実行環境を使う。
DrRacketのインストールは、 こちら

作用的順序の評価の動作確認

DrRacketの言語を Pretty Big に設定し、以下の関数を定義し test 0 (p)) を実行する。

(define (p)
 (print "呼び出されたよ")
 (p)
)

(define (test x y) 0)

(test 0 (p))
; 実行

実行結果

"呼び出されたよ""呼び出されたよ""呼び出されたよ""呼び出されたよ""呼び出されたよ"・・・

"呼び出されたよ" と無限ループする。
無限ループ関数である p をどこでも呼び出していないように見えるが、引数を完全に展開して後続の処理を評価するため無限ループとなる。

正規順序の評価の動作確認

DrRacketの言語を Lasy Racket に設定し、以下の関数を定義し test 0 (p)) を実行する。

(define (p)
 (print "呼び出されたよ")
 (p)
)

(define (test x y) 0)

(test 0 (p))
; 実行

実行結果

0

"呼び出されたよ"は、出力されない。
正規順序の評価は、引数の評価を後回しにしているので、無限ループにならない。

問題1.6

if文は、特殊形式である。
condを使用して普通の手続きとして定義して使いたい。

結論、それはできるのでifの新板として new-if を定義した。

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
  (else else-clause)))

new-ifの使い方

(new-if (= 2 3) 0 5)
5
(new-if (= 1 1) 0 5)
0

以下の関数を定義し、sqrt-iterを使用するとどうなるか?

(define (square x) (* x x))


(define (improve guess x)
  (average guess (/ x guess)))


(define (average x y)
  (/ (+ x y) 2))


(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))


(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x)
                     x)))


(sqrt-iter 1.0 300)
; sqrt-iterを使用

作用的順序の評価 であれば、無限ループし 正規順序の評価 でれば計算結果を返してくれる。


問題1.5と同じく順序の評価によって、動作が異なる。
作用的順序の評価に、new-ifに再帰的な関数を引数として渡してしまうと、無限ループになる。
else-clauseで (sqrt-iter (improve guess x) x) 自身を呼び出している。


これは、new-ifが普通の手続きであるため発生します。
ifやcondのような特殊形式は、まず述語(条件式)を評価し、その条件に合う式を評価して最終的な結果を返します。

先ほどのsqrt-iter関数をnew-ifからifに置き換えて、関数を実行すると無限ループは起きません。

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x)
                     x)))

(sqrt-iter 1.0 300)
17.320521062406588


最近読んだ本

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

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

  • 作者: ジェラルド・ジェイサスマン,ジュリーサスマン,ハロルドエイブルソン,Gerald Jay Sussman,Julie Sussman,Harold Abelson,和田英一
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2000/02
  • メディア: 単行本
  • 購入: 35人 クリック: 1,149回
  • この商品を含むブログ (486件) を見る

プログラミングの基礎 (Computer Science Library)

プログラミングの基礎 (Computer Science Library)

アンダースタンディング コンピュテーション―単純な機械から不可能なプログラムまで

アンダースタンディング コンピュテーション―単純な機械から不可能なプログラムまで