2020-03-02

SICPを読む上でよく見るメモ

ゼミのたびに「あの単語の意味ってなんだったっけ？」って事案が多発するので定義をまとめた記事を作ります。

適用順序評価と正規順序評価

正規順序評価(normal-order evaluation)

　　完全に展開してから簡約する。

適用順序評価(applicative-order evaluation)

　　引数を評価してから展開する。

2018-04-30

SICPゼミ第61回

練習問題4.45

写真参照

f:id:sicp-zemi:20180430172338j:plain

練習問題4.46

ずっと存在しない prepositional-phrase を探し求めて無限ループ回って死ぬ。

練習問題4.47

無限ループ回って死ぬ。 verbs だ！ →後ろに前置詞句ついてる、違うじゃん！ →verb-phrase だ！ →じゃあ (parse-verb-phrase) 呼びますね～ →verbs だ！ →後ろに前置詞句ついてる、違うじゃん！ →……

以下同じ。順番入れ替えても無限に (parse-verb-phrase) 呼ばれるので何も変わらん。

練習問題4.48

やるだけ．虚無

練習問題4.49

やるだけ．虚無

2018-04-11

SICPゼミ第60回

練習問題4.44

8×8 面倒なので 4×4 で。

#lang racket
(require sicp-pict)

(define (require p) (if (not p) (amb) 0))
(define (distinct? items)
  (cond ((null? items) true)
        ((null? (cdr items)) true)
        ((member (car items) (cdr items)) false)
        (else (distinct? (cdr items )))))

(define (queens)
  (let ((queen1 (cons 1 (amb 1 2 3 4)))
        (queen2 (cons 2 (amb 1 2 3 4)))
        (queen3 (cons 3 (amb 1 2 3 4)))
        (queen4 (cons 4 (amb 1 2 3 4))))
    (require
      (distinct?
       (list (cdr queen1) (cdr queen2) (cdr queen3) (cdr queen4))))
    (define (bishop? queen-list)
      (define (bishop-sub? queen others-list)
        (if (null? others-list)
            #t
            (if (= (abs (- (car queen) (caar others-list)))
                   (abs (- (cdr queen) (cdar others-list))))
                #f
                (bishop-sub? (car others-list) (cdr others-list)))))
      (if (null? (cdr queen-list))
          #t
          (bishop-sub? (car queen-list) (cdr queen-list)))) 
    (require (bishop? (list queen1 queen2 queen3 queen4)))
    (list queen1 queen2 queen3 queen4)))

by tube

2018-02-22

SICPゼミ第59回

練習問題4.41

(define (generate-list n)
  (define (pow n k)
    (if (= k 0)
      1
      (* n (pow n (- k 1)))
    )  
  )
  (define (int-to-list m n k)
    (if (= k 0)
      (list)
      (cons (remainder m n) (int-to-list (/ (- m (remainder m n)) n) n (- k 1)))
    )
  )
  (define (list-generation-itr k)
    (if (< k 0)
      (list)
      (cons (int-to-list k n n) (list-generation-itr (- k 1)))
    )
  )
  (list-generation-itr (- (pow n n) 1))
)

で解の候補をすべて列挙したリストを作れる．これにフィルターをかければOK.

練習問題4.42

(define (liar-game)
  (let ((betty (amb 1 2 3 4 5))
        (ethel (amb 1 2 3 4 5))
        (joan (amb 1 2 3 4 5))
        (kitty (amb 1 2 3 4 5))
        (mary (amb 1 2 3 4 5)))
    (require
      (distinct? (list betty ethel joan kitty mary)))
    (require (xor (= kitty 2) (= betty 3)))
    (require (xor (= ethel 1) (= joan 2)))
    (require (xor (= joan 3) (= ethel 5)))
    (require (xor (= kitty 2) (= mary 4)))
    (require (xor (= mary 4) (= betty 1)))
    (list (list 'betty betty) (list 'ethel ethel)
          (list 'joan joan) (list 'kitty kitty)
          (list 'mary mary))))

'((betty 3) (ethel 5) (joan 2) (kitty 1) (mary 4))

おしまい。 by tube

練習問題4.43

(define (father-determination)
  (let ((mary (cons (amb 'moore 'downing 'hall 'barnacle 'parker) (amb 'moore 'downing 'hall 'barnacle 'parker)))
        (gabrielle (cons (amb 'moore 'downing 'hall 'barnacle 'parker) (amb 'moore 'downing 'hall 'barnacle 'parker)))
        (lorna (cons (amb 'moore 'downing 'hall 'barnacle 'parker) (amb 'moore 'downing 'hall 'barnacle 'parker)))
        (rosalind (cons (amb 'moore 'downing 'hall 'barnacle 'parker) (amb 'moore 'downing 'hall 'barnacle 'parker)))
        (melissa (cons (amb 'moore 'downing 'hall 'barnacle 'parker) (amb 'moore 'downing 'hall 'barnacle 'parker))))
    (require
      (distinct? (list (car mary) (car gabrielle) (car lorna) (car rosalind) (car melissa))))
    (require
      (distinct? (list (cdr mary) (cdr gabrielle) (cdr lorna) (cdr rosalind) (cdr melissa))))
    (require (not (eq? (car gabrielle) (cdr gabrielle))))
    (require (not (eq? (car lorna) (cdr lorna))))
    (require (not (eq? (car rosalind) (cdr rosalind))))
    (require (not (eq? (car melissa) (cdr melissa))))
    (require (not (eq? (car mary) (cdr mary))))
    (require (eq? (car gabrielle) 'barnacle))
    (require (eq? (car lorna) 'moore))
    (require (eq? (car rosalind) 'hall))
    (require (eq? (car melissa) 'downing))
    (require (eq? (cdr melissa) 'barnacle))
    (require (eq? (cdr mary) 'moore))
    (require (cond ((eq? (cdr gabrielle) 'parker) (eq? (car gabrielle) (cdr gabrielle)))
                   ((eq? (cdr lorna) 'parker) (eq? (car lorna) (cdr gabrielle)))
                   ((eq? (cdr rosalind) 'parker) (eq? (car rosalind) (cdr gabrielle)))
                   ((eq? (cdr melissa) 'parker) (eq? (car melissa) (cdr gabrielle)))
                   ((eq? (cdr mary) 'parker) (eq? (car mary) (cdr gabrielle)))))
    (list (list 'gabrielle gabrielle) (list 'lorna lorna)
          (list 'rosalind rosalind) (list 'melissa melissa)
          (list 'mary mary))))

> (father-determination)
'((gabrielle (barnacle . hall))
  (lorna (moore . downing))
  (rosalind (hall . parker))
  (melissa (downing . barnacle))
  (mary (parker . moore)))
> (amb)
. . amb tree exhausted
>

高速化は次回！

2018-02-07

SICPゼミ第58回

練習問題4.38

#lang racket
(require sicp-pict)

(define (require p) (if (not p) (amb) 0))

(define (distinct? items)
  (cond ((null? items) true)
        ((null? (cdr items)) true)
        ((member (car items) (cdr items)) false)
        (else (distinct? (cdr items )))))

(define (multiple-dwelling)
  (let (( baker (amb 1 2 3 4 5)) (cooper (amb 1 2 3 4 5))
                                 (fletcher (amb 1 2 3 4 5)) (miller (amb 1 2 3 4 5))
                                 (smith (amb 1 2 3 4 5)))
    (require
      (distinct? (list baker cooper fletcher miller smith )))
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    (require (> miller cooper ))
    ;(require (not (= (abs (- smith fletcher )) 1)))
    (require (not (= (abs (- fletcher cooper )) 1)))
    (list (list 'baker baker) (list 'cooper cooper)
          (list 'fletcher fletcher) (list 'miller miller)
          (list 'smith smith ))))

実行結果

> (multiple-dwelling)
'((baker 1)
  (cooper 2)
  (fletcher 4)
  (miller 3)
  (smith 5))
> (amb)
'((baker 1)
  (cooper 2)
  (fletcher 4)
  (miller 5)
  (smith 3))
> (amb)
'((baker 1)
  (cooper 4)
  (fletcher 2)
  (miller 5)
  (smith 3))
> (amb)
'((baker 3)
  (cooper 2)
  (fletcher 4)
  (miller 5)
  (smith 1))
> (amb)
'((baker 3)
  (cooper 4)
  (fletcher 2)
  (miller 5)
  (smith 1))
> (amb)
. . amb tree exhausted

by tube

練習問題4.39

制約の順番が最終的な解に影響を与えることはない(集合のcap演算子は結合的)．順番が時間に影響をあたえることはある． ~~最初は120個の可能性があるが，~~

(require (not (= baker 5)))

みたいなのは24個を除外する．

(require (> miller cooper))

は60個を除外する．

(require (not (= (abs (- smith fletcher)) 1)))

は4!×2=48個を除外する．

~~なので最初に60個除外してしまうのがよい．~~

↑間違い。
各制約について、そのrequire命令が下された時点では、「今探索している各変数の値がその制約を満たすかどうか」を判定するだけであり、「その制約を満たさない可能性（枝）をすべて取り除いている」というわけではない。
本質的に深さ1の5^5分木を深さ優先で探索しているにすぎない。そのため、require文によって計算時間は変わらない……と言いたいところだが、ここで各制約の実行時間がキーファクターとなることに注意されたい。今回の制約の中で、distinct? だけが再帰的であり、他の制約に比べ実行時間が非常に長くなっている。そのため、できるだけdistinct?の実行回数を減らすことで計算時間の短縮が可能となる。
元のコードのようにdistinct?の制約を一番上に持ってくると (amb) が更新される（何らかの制約を満たさないことによって）たびにdistinct?から判定されることになる。逆にdistinct?を一番下に持ってくることでできるだけdistinct?の実行回数を減らすことができ、計算時間の短縮につながる。

by tube

練習問題4.40

階の割り当てが別々でないといけないという制約の前は5^5通り、制約の後では5!通り。

4.39で述べた通り、各 require 文の判定の時に「その制約を満たさない」探索範囲がすべて排除されているわけではない。例えば baker が5階でない、という制約については何度も繰り返しその制約文に帰って判定が行われていることになるが、これは非常に無駄が多い。
そこで、各 require 文では（特に制約をかける変数が1つや二つなど少数の場合には）、その制約に関係のない他の変数を宣言する前に無駄な探索範囲をすべて削ってしまったほうが良い。
すなわち、深さ1の 5^5 分木だった探索範囲を、深さ5にしてやり、各制約について枝刈りをしてやれば効率化できる。

;もとのアルゴリズム
(define (multiple-dwelling)
  (let (( baker (amb 1 2 3 4 5)) (cooper (amb 1 2 3 4 5))
                                 (fletcher (amb 1 2 3 4 5)) (miller (amb 1 2 3 4 5))
                                 (smith (amb 1 2 3 4 5)))
    (require
      (distinct? (list baker cooper fletcher miller smith )))
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    (require (> miller cooper ))
    (require (not (= (abs (- smith fletcher )) 1)))
    (require (not (= (abs (- fletcher cooper )) 1)))
    (list (list 'baker baker) (list 'cooper cooper)
          (list 'fletcher fletcher) (list 'miller miller)
          (list 'smith smith))))

;高速化したもの
(define (multiple-dwelling-tube)
  (let ((baker (amb 1 2 3 4 5)))
    (require (not (= baker 5)))
    (let ((cooper (amb 1 2 3 4 5)))
      (require (not (= cooper 1)))
      (let ((fletcher (amb 1 2 3 4 5)))
        (require (not (= fletcher 5)))
        (require (not (= fletcher 1)))
        (require (not (= (abs (- fletcher cooper)) 1)))
        (let ((miller (amb 1 2 3 4 5)))
          (require (> miller cooper))
          (let ((smith (amb 1 2 3 4 5)))
            (require (not (= (abs (- smith fletcher)) 1)))
            (require (distinct? (list baker cooper fletcher miller smith)))
            (list (list 'baker baker) (list 'cooper cooper)
                  (list 'fletcher fletcher) (list 'miller miller)
                  (list 'smith smith ))))))))

by tube

2018-01-13

SICPゼミ第57回[tube_worm死す]

練習問題4.35

(define (an-integer-between low high)
    (require (<= low high))
    (amb low (an-integer-between (+ low 1) high)))

練習問題4.36

(define (a-pythagorean-triple-between)
  (let ((high (an-integer-starting-from 1)))
    (let ((i (an-integer-between 1 high )))
      (let ((j (an-integer-between i high )))
        (let ((k high))
          (require (= (+ (* i i) (* j j)) (* k k)))
          (list i j k))))))