読者です 読者をやめる 読者になる 読者になる

やろーじだい

ブログです

「つくって学ぶプログラミング言語 - Ruby による Scheme 処理系の実装 」を途中まで読んだ

Common Lisp

きちんと Lispインタプリタの実装したことがなかったのでここを参考にしながら 2 ヶ月程前に Common Lisp で 3 章 (再帰) まで実装していた。いつ再開するかわからないので今日の記事で宣言した通りとりあえずまとめておく。
 自分のプログラムはここで公開しているが、自作のライブラリ と CL21 を使っているので導入しなければ動かない。
 Ruby を使っても良かったのだが、ただ写すだけになってしまいそうだったのと、

本書で出てくるプログラムをコピー&ペーストしていけば、実行できるようになっています。動作することを確認するくらいには役立つでしょう。ただし、本当に理解したいのであれば、なるべく自分で プログラミングしてみてください。それもプログラムを見て理解した後は、そのプログラムを見ずに。 どこが理解できないでるかが明確になるかと思います。
はじめに P-ii

ということから、別な言語を使った方がこれを実践しやすいと思ったため。

第1章 プログラムと評価

1章終了段階でのコードは ここ で確認できる。
 この本では Ruby で配列として扱えるという理由で [:+, 1, 2] というような構文を採用していたので自分は (:+ 1 2) という様にした。関数と変数は共にシンボルとして扱うようにした。また命名規則に関しても基本的に Common Lisp でよく見る形式にした。例えば述語は Ruby の場合 immediate_val? となるものを immediate-val-p のようにハイフン区切りで p を付けるといった様に。
 環境は

(defparameter *primitive-fun-env*
  #H(:+ '(:prim +)
     :- '(:prim -)
     :* '(:prim *)))

のように Hash-tabel を利用した。

第2章 関数適用の評価

eval_let の実装にあたって

(defun let-to-parameters-args-body (exp)
  `(,(map #'first (second exp))
    ,(map #'second (second exp))
    ,(third exp)))

(defun eval-let (exp env)
  (destructuring-bind (parameters args body) (let-to-parameters-args-body exp)
    (let ((new-exp (append `((:lambda ,parameters ,body)) args)))
      (_eval new-exp env))))

というようにバッククオート構文を使用しているのだが、

(defun let-to-parameters-args-body (exp)
  (list (map #'first (second exp))
        (map #'second (second exp))
        (third exp)))

の方が読みやすい気がした。
 let? のような関数の実装が雑で不安だったので

(defun letp (exp)
  (and
   (eq :let (first exp))
   (listp (second exp))
   (third exp)))

のようにした。
 ここを読むと、クロージャとは何なのかが明確になるので、その辺りが曖昧な人は読む価値があると思った。

第3章 再帰

再帰関数の実装に興味があったのでこの章は楽しかった。実装にあたって苦労したのだが、最も苦労した理由がテストのミスであり辛かった。テストのミスというのはどうすれば防ぐことができるのだろう。
 ここでは Ruby に慣れていなかったのと、環境を用意せずに読んでいた (実際に実行して試さなかった) ため eval_retrec など少し読むのに苦労した。もう少し関数を分けて処理に名前を付けて欲しいと思った。
 またここまでで唯一の破壊的処理を行う set_extend_env! が実装されているが、何故ここで副作用を使うようにしたのかの説明が無かった。単純に考えれば環境 (Hash-tabel) の更新なので Copy を作るのは重い処理だからかと思ったが、 extend_env では Hash.new を使って新しい環境を作成しているのだが違いは何なのだろう。

追記:

 このツイートへのリプライで破壊的更新をしている理由について教えて頂いた。
 コピーをするとクロージャの持つ環境が更新できず :dummy にアクセスしてしまうので、ここでは破壊的処理を行って更新しなければならなかった (extend_env では既に環境内にある closure の持つ環境を変更することができない)。

まとめるということについて

まとめるということについて

自分はこれまで興味を持って取り組んだことの状況が、終わったかそうでないかの2パターンに頭の中で振り分けてしまっていた。これでは本は読み終わらなければ、延々に興味の対象として胸の中に居続けることになるし、勉強についてはどこまで行っても終わりがない。この状態は良くないのでひとつひとつにしっかり集中して取り組まなければと思いながらも、簡単に興味が分散する性格をしているので全くうまくいかず気が付けば大学院1年の冬にさしかかろうとしている。
 常々、自分に足りないものは「まとめる」ということだという思いがあった。しかし、これまで私はまとめるという行いが長い時間をかけてやってきたものの集大成である様なイメージを持っていた。そのためなかなかその「まとめる」という段階にまで到達するほどのものができず、自分でも長い時間何をやっていたのか説明ができない状態が続いていた。
 つい昨日、自分がやったところまでを「とりあえずまとめる」ということを意識すれば一度その興味のあることについて区切りをつけることができるのではないかと気がついた。それによって、自分が現在までおこなっていたことが明確になる。また他に興味が湧いたとしても、その段階で手をつけていたものをとにかくまとめることで、そこまでのことに区切りを付け、次のところに心おきなく進むことができそうだ。今までは「そういうえばこれについて勉強している途中だった」ということを考えなが別なことをやっていることがあり、非常に気分が悪かった。この「次に行く前にそこまでのことを、どんなに浅い段階でもいいのでまとめる」ことを徹底することができれば、ここまで挙げてきた問題を改善することができそうだと思う。
 自分は大抵の場合、こういった「これをやります宣言」をしたものを全く実行できていないという典型的なダメ人間であるのだが、今回に関してはこの宣言を行うと同時に、この思いつきについてブログにまとめるということができているので今までよりはましだろうということにしたい。

Aizu SICP 第5回

Aizu SICP

2016/7/11 追記: 数式のサイズを見易いように修正

今日は参加できる人が少なめだったので練習問題 1.9 ~ 1.13 を解く時間にしてみたが、参加者全員で頭をひねって解く時間はなかなか良かったのでこの形式でまたやりたい。

今回の内容

注意: 以下では私達の練習問題の解答を載せています。まだ問題を解いていない人は一度取り組んでみてください。すでに解き終わっている人で何か解答におかしいところを見つけた人は教えてください。

練習問題 1.9

 実際に動かすために incdec を以下の様に実装した。

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

(define (dec x)
  (- x 1))

また、+ で実装すると Scheme 上で実装されている + を上書きしてしまい面倒なのでそれぞれの関数を plus1plus2 とした。

(define (plus1 a b)
  (if (= a 0)
      b
      (inc (plus1 (dec a) b))))

(define (plus2 a b)
  (if (= a 0)
      b
      (plus2 (dec a) (inc b))))

plus1 は「a plus1 b は a = 0 の時 b であり、それ以外の場合、a から 1 引いたものに b を plus1 した結果に更に 1 足したものに等しい」 であり plus2 は「a plus2 b は a = 0 の時 b であり、それ以外の場合、a から 1 引いたものに、b に 1 を加えた結果を plus2 したものに等しい」という意味を持つ。この時、 plus1 では明らかに inc による遅延演算の連鎖がおこるため再帰プロセスであり、 plus2 では毎回の演算が独立しているため反復プロセスであることがわかる。以下に (+ 4 5)plus1plus2 それぞれを適応した展開の流れを記述する。

;; plus1
(plus1 4 5)
;; ↓
(inc (plus1 3 5))
;; ↓
(inc (inc (plus1 2 5)))
;; ↓
(inc (inc (inc (plus1 1 5))))
;; ↓
(inc (inc (inc (inc (plus1 0 5)))))
;; ↓
(inc (inc (inc (inc 5))))
;; ↓
(inc (inc (inc 6)))
;; ↓
(inc (inc 7))
;; ↓
(inc 8)
;; ↓
9

;; plus2
(plus2 4 5)
;; ↓
(plus2 3 6)
;; ↓
(plus2 2 7)
;; ↓
(plus2 1 8)
;; ↓
(plus2 0 9)
;; ↓
9

練習問題 1.10

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1) (A x (- y 1))))))

以下は何も考えず実行した結果を貼った。

(A 1 10)
;;=> 1024
(A 2 4)
;;=> 65536
(A 3 3)
65536

以下は数学的定義を与える問題について。

f

(define (f n) (A 0 n))

これは A の定義から、 n = 0 の時 (f n) は 0, それ以外の場合は全て cond 式の第2式に入るため (* 2 n) が実行される。よって

{ \displaystyle
f(n) = 2n
}

g

(define (g n) (A 1 n))

n = 0, 1, 2, 3 の場合を展開すると、

(A 1 0)
;; ↓
0
;; ↓
(A 1 1)
;; ↓ (A の定義より)
2
(A 1 2)
;; ↓
(A 0 (A 1 1))
;; ↓
(A 0 2)
;; ↓ (f の定義より)
4 
(A 1 3)
;; ↓
(A 0 (A 1 2))
;; ↓
(A 0 (A 0 (A 1 1))
;; ↓ 
(A 0 (A 0 2))
;; ↓ (f の定義より)
8

一般化すると、

(A 1 n)
;; ↓
(A 0 (A 1 (- n 1)))
;; ↓
(A 0 (A 0 (A 1 (- n 2))))
...
;; ↓
(A 0 (A 0 (A 0 ... (A 1 1))))

このように n-1 の数だけ 2 に  f(n) が適応される。(ただし n = 0 の場合は A の定義より 0 になる。また 0 未満の場合は未定義 (無限ループ)) よって、

f:id:lhcpr:20160710204153p:plain:w200

h

(define (h n) (A 2 n))

n = 0, 1, 2, 3 の場合を展開すると、

(A 2 0)
;; ↓
0
(A 2 1)
;; ↓
2
(A 2 2)
;; ↓
(A 1 (A 2 1))
;; ↓
(A 1 2)
;; ↓ (g の定義より)
4
(A 2 3)
;; ↓
(A 1 (A 2 2))
;; ↓ (上の定義より)
(A 1 4)
;; ↓
16

という様に、

(h n)
;; ↓
(A 2 n)
;; ↓
(A 1 (A 2 (- n 1)))
;; ↓
(A 1 (h (- n 1)))

というような漸化式の形をしている。例えば n = 3 の場合は  { 2^{2^{2^{1}}} } という様に展開される。数式として表わすと、

f:id:lhcpr:20160710214755p:plain:w250

練習問題 1.11

再帰プロセスは数式をそのままプログラムにできる。反復プロセスは P40 フィボナッチの関数とほぼ同様にできる。

(define (f n)
  (f-rec 2 1 0 n))

(define (f-rec a b c n)
  (cond ((= 0 n) c)
        (else (f-rec (+ a (* 2 b) (* 3 c))
                     a
                     b
                     (- n 1)))))

同様な形の漸化式の場合、項の数がいくつ増えてもその分だけ引数の数を増やしていけば同様に反復プロセスに落とすことができることがわかる。

練習問題 1.12

いまいち問題の意味がわからなかったが、多分こういう意味だろうということで実装した。

(define (pascal-triangle row col)
  (cond ((= col 1) 1)
        ((= row col) 1)
        (else (+ (pascal-triangle (- row 1) col)
                 (pascal-triangle (- row 1) (- col 1))))))

練習問題 1.13

kとk-1のふたつを仮定する数学的帰納法を用いた。参考

n = 0 の場合

f:id:lhcpr:20160710231335p:plain:w300

n = 1 の場合

f:id:lhcpr:20160710231233p:plain:w350

次に n = k, n = k - 1 の時に問題の式が成り立つと仮定すると、(k と書くべきところを n と書いてしまいました。許してください。)

f:id:lhcpr:20160710232506p:plain:w500

ここで

f:id:lhcpr:20160710234337p:plain:w330

f:id:lhcpr:20160710234447p:plain:w330

であり

f:id:lhcpr:20160710233502p:plain:w300

f:id:lhcpr:20160710233701p:plain:w300

であるので、

f:id:lhcpr:20160710234844p:plain:w500

よって全ての整数 n  {\geq} 0 について

f:id:lhcpr:20160710235026p:plain:w150

が成り立つ。

Aizu SICP 第四回

Aizu SICP

2016/6/11 に Aizu SICP 第四回を行った。途中の練習問題は一旦飛ばした。

タイムテーブル

  • 19:10 ~ 19:30: 読書 p38「1.2.2 木の再帰」~ p42 練習問題1.11前まで
  • 19:30 ~ 20:00: 質疑
  • 20:05 ~ 20:20: 読書 p43「1.2.3 増加オーダー」 ~ p47 「1.2.4 指数計算」練習問題前まで
  • 20:20 ~ 20:50: 質疑

今回の内容

1.2.2 木の再帰

より正確には、Fib(n) は  {\Phi^{n} / \sqrt{5}} に最も近い整数になります (練習問題 1.13参照)。 {\Phi} は次の値です。
{ \displaystyle \Phi = \frac{1 + \sqrt{5}}{2} \approx 1.6180}
 {\Phi}黄金比 (golden ratio) で、次の等式を満します。
 {\Phi^{2} = \Phi + 1}
そのため、このプロセスのステップ数は、入力に対して指数的に増加します。
p38~39

最後の「そのため」は、

より正確には、Fib(n) は  {\Phi^{n} / \sqrt{5}} に最も近い整数になります。
P38

にかかる。
 両替の問題は読書会中に各自紙に書くことによって理解を試みた。数学的な話題になってくると紙とペンが欲しくなるので準備が必要だった。
 この章の中で

count-change は、fib の一つ目の実装同様、冗長な木の再帰のプロセスを生成します (292 の計算にはかなりの時間がかかるでしょう)。
P42

という話があったが、現在の性能では数ミリ秒であり、この本がかなり前にかかれた本であることを再確認した。

1.2.3 再帰オーダー

任意の十分に大きな  {n} に対して、 {n} と独立な正の定数  {k_1} {k_2} が存在し、 {k_1f(n) \leq R(n) \leq k_2f(n)} を満たすとき、 {R(n)} は増加オーダーが  {\Theta(f(n))} であると言い、 {R(n) = \Theta(f(n))} (シータ f(n) と読む) と書きます。(別な言い方をすると、大きな  {n}に対して、 {R(n)} の値は  {k_1f(n)} {k_2f(n)} で挟まれるということです。)
P44

という定義から、  {\Theta(n)} {O(n)} {\Omega(n)} を満すものとしての  {\Theta(n)} であると考えてよさそう。

1.2.4 指数計算

 ここの主題とは無関係だが、

ここで、ある整数が偶数かどうかをテストする述語は、基本手続きの remainder (割り算の余り) を使って次のように定義します。
P46

ということから Scheme の言語仕様には、even? は含まれていないようだ (Racket 上では実装されている)。こういったことがこれから先頻繁に表れると考えられるので注意する。基本的に Racket 上で実装されているならば、実装の方法を確認した上で既に実装されているものを利用して問題無いと思う。

質疑応答など

「木の再帰プロセス」と「再帰プロセス」は別な概念か

 あえて「木の」と表記していたのが気になったとういことだったが、「木の再帰プロセス  {\in} 再帰プロセス」という考えで問題は無いか。

両替アルゴリズムの他のより良いものは何があるか

一方で、答えを計算するためのよりよいアルゴリズムをどう設計するかというのは自明ではありません。この問題は、読者への宿題とします。
P42

読書会中にはメモ化の他には、何かしら反復プロセスで実装するというアバウトな考えしか浮かばなかった。

 その後、木の下から集めていくことをイメージして1時間くらい考えてみたがわからなかった。

 {\Theta} は空間や計算量共に使えるものか

 P43 で定義された  {R(n)} のように様々なものを表すことができると考えられる。

ビックオー  {O} について

注:ビッグオーをビッグシータの意味で使うことも多いので注意が必要です。
http://mathtrain.jp/landausymbol

ということが URL のページで書いてあったが、実際に  {O} {\Theta} の意味で使っているところを目撃した記憶がない。

Aizu-SICP 第三回

Aizu SICP Scheme

2016/5/22 に Aizu-SICP 第三回 (SICP読む会) を行った。時間が空いたこともあり、復習に時間を使わせて頂いた。

タイムテーブル

  • 19:00 ~ 19:40: これまでの簡単な復習と練習問題の確認
  • 19:40 ~ 19:55: 読書 p32~p36 「1.2 手続きとそれが生成するプロセス」~「1.2.1 線形再帰と反復」練習問題前まで
  • 19:55 ~ 20:25: 質疑

今回の内容

1.2 手続きとそれが生成するプロセス

 手続きは、計算プロセスの局所展開 (local evolution) のためのパターンです。それは、プロセスの各段階が、どのように前の段階の上に構築されるかを記述するものです。プロセスの局所展開は手続きによって記述されるものですが、できればプロセスの全体的なふるまい、別の言い方をするとグローバル (global) なふるまいについても何か言えるようになりたいところです。これは、一般的にはとても難しいことです。しかし、プロセスの展開のよくあるパターンについての説明を試みるぐらいはできるでしょう。 P32

今一理解できないが、あるプロセス (関数) がどのような形 (一般的に見たふるまい) を持っているかを明かにしたいと理解した。例として以下の章では、再帰関数を二つの形に分けたり、計算時間などを計算することにより、そのプロセスのふるまいを一般的に説明することを試みている。

1.2.1 線形再帰と反復

 ここでは様々な概念に対して名前を付けている。概念としては知っていても何と呼ぶかが明確でないものが多かったが、名前が付くことで話をすることがしやすくなった。例として以下に挙げる。

遅延演算の連鎖

 P33 図 1.3 のような再帰関数において、展開後に行われる演算の連鎖こと。 (図 1.3 における *)

再帰プロセス

 遅延演算が行われる再帰関数の性質。また例による n! の計算は記録するための情報量や計算ステップ数が n に対して線形に増加するため、線形再帰プロセスと呼ばれる。

反復プロセス

 図 1.4 のように、関数の結果を引数として変数に保存することにより遅延演算が行われない再帰関数の性質。毎回の再帰が独立して計算を反復しており、またステップ数は n に対して線形に増加するため線形反復プロセスと呼ばれる。再帰プロセスと反復プロセスについては今まで、末尾再帰最適化できない方・できる方のように呼んでいた。
 反復プロセスが末尾再帰最適化できることの理由として、本文中の

反復プロセスの場合、プログラムの変数はどの時点でもプロセスの状態を完全に記述しています。 P35

というのが重要な点だとわかった。

状態変数

 反復プロセスにおいて、関数の状態 (繰返しの数やそれまでの反復の結果) を保存しておくための変数。関数 fact-iter における productcountermax-countを指す。

再帰プロセスと再帰手続きの違い

 再帰プロセスは上記のような、再帰関数ふるまいを一般化した場合のひとつを指しているが、再帰手続きとは自分自身を参照しているような関数 (手続き) を指す。今回の例では図 1.3・図 1.4 の関数は共に再帰手続きであるが、再帰プロセスであるのは図 1.4 のみである。

Aizu-SIPC 第二回

Aizu SICP Scheme

2015/12/20 に Aizu-SICP 第二回 (SICP読む会) を行った。 更新したつもりが下書きにしたまま半年放置されていた。

タイムテーブル

  • 19:00 ~ 19:15: 前回課題とした練習問題 1.2 ~ 1.5 の答え合わせ
  • 19:15 ~ 19:45: 読書 P22~26 「1.1.7 ニュートン法による平方根
  • 19:45 ~ 20:20: 質疑
  • 20:20 ~ 20:35: 読書 P27~P31 「1.1.8 ブラックボックス抽象化としての手続き」

今回の内容

1.1.6 条件式と述語

練習問題 1.2

(define 1-2 (/ (+ 4 5 (- 2
                         (- 3
                            (+ 6
                               (/ 4 5)))))
               (* (- 2 7)
                  (- 6 2)
                  3)))

練習問題 1.3

(define (1-3 a b c)
  (cond ((<= a b c) (sum-of-squares b c))
        ((<= b a c) (sum-of-squares a c))
        (else (sum-of-squares a b))))

練習問題 1.4

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

定義後

> (a-plus-abs-b (+ 3 1) (- 1 -5))

と実行した場合の評価の流れを以下に記述する

(a-plus-abs-b (+ 3 1) (- 1 -5))
; ↓
((if (> (- 1 -5) 0) + -) (+ 3 1) (- 1 -5))
; ↓
((if (> 6 0) + -) (+ 3 1) (- 1 -5))
; ↓
((if #t + -) (+ 3 1) (- 1 -5))
; ↓
(+ (+ 3 1) (- 1 -5))
; ↓
(+ 4 6)
; ↓
10

練習問題 1.5

(define (p) (p))
(define (test x y)
  (if (= x 0) 0 y))

適用順序評価の場合は

(test 0 (p))

を実行した時に引数である 0 と (p) が評価される。その時 p の評価を得るために関数 p の定義から (p) を評価する必要があり、評価が無限に続いてしまう。一方、正規順序評価の場合は test の引数を評価せず、 また if は第一引数が真の場合は第二引数のみを評価するので

(test 0 (p))
; ↓
(if (= 0 0) 0 (p))
; ↓
(if #t 0 (p))
; ↓
0

となり評価が終了する。

1.1.7 例: ニュートン法による平方根

 再帰を利用した繰返し処理の具体例であり、初めての例としては少々複雑に感じた。ひとつひとつの関数が何をするものなのか、じっくり見る必要あり。ぱっと見ただけですぐに理解できなければ具体的な値を入れて自分で展開していく。

練習問題 1.6

 練習問題 1.5 に似た原理の問題である。 if 式の特殊形式であり、評価規則が通常と違う (全ての引数を評価しない) ことによって再帰関数 sqrt-iter は成りたっている

練習問題 1.7

 小さい値の場合、今回の good-enough? 内では誤差の大きさを比較するための定数として 0.001 が使われているが、これに近い小さな値の平方根は、その平方根の値に対して誤差の割合がかなり大きくなり、さらに小さい値 (平方根が 0.001) に対しては全く求まらない。大きい値を使用すると good-enough? 内で二乗した時に桁溢れが起る(?) 前回の guess と新しい guess を比較する形で誤差を推定すれば例題の good-enough? よりは良い精度になると考えられる。 (実際に試していない)

練習問題 1.8

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

(define (1-8-improve guess x)
    (/ (+ (/ x (square guess)) (* 2 guess)) 3))

(define (1-8-good-enough? guess x)
  (< (abs (- (cube guess) x)) 0.001))

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

(define (1-8-cube-root x)
  (1-8-sqrt-iter 1.0 x))

1.1.8 ブラックボックス抽象化としての手続き

関数一つ一つが持つモジュールとしての役割

 関数は何かしらひとつの仕事をし、複数の関数によって作られた関数はまた何かひとつの仕事をする。 Lisp でユーザーが作成した関数と、処理系に提供されている関数の差は無い。

束縛と代入の違いについての重要性

 ある変数と値の関係は、全てのスコープごとに独立している。現在のスコープにある変数と値の関係が定義されていなければ (自由変数)、ひとつ外のスコープを見に行く。あるスコープで使われている変数と同じ名前の変数がそのスコープの内側で使われており、値が別に束縛されたとしても、外側のスコープでは影響が無い。

ブロック構造

 P31 の例のような自由変数を使用する書き方は関数ひとつひとつが独立していないため読み辛く感じる。

質疑まとめ

関数の末尾の ? について

 Lisp で述語 (#t, #f を返す関数) を定義する際の慣例。

正の実数の平方根は必ず存在するのか

 http://d.hatena.ne.jp/takemita/20100114/p3

+とgood-enough?で、再定義した際の挙動が違うのはなぜ?

という質問が出て、読書会中はたしかにそうだなと思ったのだが、今試してみたところ普通に束縛され、自分で定義した関数との違いは無いようだった。

> (define + -)
> (define (test x y) (+ x y))
> (test 3 3)
0

読書会中は REPL でいろいろ実験を行っており、環境がかなり荒されていたのでその辺りが原因だったかもしれない。

scheme にループはあるか?

 繰り返しのための構文 do もあるが、一般に Scheme では繰り返しのために再帰を使用する。

scheme の引数の評価順序は?

Common Lispでは,関数の引数は左から右の順に評価される. Schemeでは評価順は意図的に未定義とされた. (それを忘れた人間は慌てふためいて実装者の笑いものになる.) http://www.asahi-net.or.jp/~kc7k-nd/onlispjhtml/continuations.html

レキシカルスコープの定義がよくわからない

このような定義のネストはブロック構造 (block structure) と呼ばれます。これは、基本的には最も単純な名前パッケージング問題の正しい解決方法です。しかし、ここにはもっといいアイデアが隠れています。補助手続きの定義を内部化することに加えて、それらを単純にすることもできます。x は sqrt に束縛されているので、sqrt の内部で定義された good-enough?, improve, sqrt-iterは x のスコープ内にあります。つまり、x をこれらの手続きに明示的に渡す必要はないということです。そうする代わりに、次に示すように内部定義では x を自由変数にします。そうすると、x の値は、それを囲む手続きである sqrt の引数から取ってくることができます。このような規定は レキシカルスコーピング (lexical scoping) と呼ばれます。27
27: レキシカルスコーピングにおいては、手続きの自由変数はその手続きを包む手続き定義の束縛を参照すると規定します。つまり、手続きが定義された環境での探索が行われるということです。
P.31

P.28の「手続きを使う人が、それがどうやって実装されているかについての知識を求められるべきではありません。」とは?

 関数を作成する側が注意するべき項目であり、「手続きを作る人は、手続きを使う人に、手続きの内部の知識を持つことを要求してはいけない」というような意味と読書会中に理解した。 これによると dynamic scope は完全に否定されていることになる?

Aizu SICP 第一回

Aizu SICP Scheme

 昨日は第一回 Aizu-SICP (読む会) を行った。 10 人集った。

タイムテーブル

  • 19:05 ~ 19:25: 読 P1~9 「1.1.3 組み合わせの評価」 前まで
  • 19:25 ~ 19:40: 質疑
  • 19:45 ~ 20:15: 読 P10~22 「1.1.7 ニュートン法による平方根」 前まで
  • 20:20 ~ 20:55: 質疑

読書内容

 参加者の @mizuki_sonoko さんが読んだ範囲をリアルタイムでまとめていたので貼る。 SICPを読む会に参加した
 練習問題に関しては,次回の読む会で答え合わせをするので簡単なコメントに留める。

1 手続きを用いた抽象化の構築

 計算プロセスについて学習して行く。プロセスは抽象的な存在であり別な抽象物であるデータを操作する。これはプログラング言語によって記号的表現で組み立てられる。そのプログラング言語には Lisp を用いる。

Lisp がメインストリームの言語でないとしたら、なぜそれをプログラミングの考察のための枠組みとして使うのでしょうか。それは、この言語が独特な特徴を持っているため、プログラミングの重要な構成とデータ構造について学び、それらを支える言語的特性と結びつけるのにとても便利な媒体だからです。 これらの特性の中でも最も意義深いものは、プロセスの Lisp による記述 (これは手続き (procedure) と呼ばれます) が、それ自身 Lisp のデータとして表され、 操作できるということです。これが重要なのは、“受動的な” データと “能動的 な” プロセスという伝統的な区別を曖昧にする能力を使った強力なプログラム設計のテクニックが存在するからです。これから見ていくように、Lisp は手続きをデータとして扱う柔軟性のおかげで、これらのテクニックを探求するのに 最も便利な言語のひとつになっています。手続きをデータとして表現する能力は、コンピュータ言語を支えるインタープリタコンパイラのような、ほかの プログラムをデータとして操作しなければならないプログラムを書くのにも、 Lisp をとても優れたものにしています。それに、こういったことを考えに入れなくても、Lisp でのプログラミングは本当に楽しいのです。

1.1 プログラミングの要素

 強力な言語は,3つのメカニズムである基本式・組み合わせ方法・抽象化方法がある。基本式は言語によって提供されている数値や関数などで,組み合わせと抽象化方法は基本式を組み合わせ,それに対して名前を付けるということが最も単純な例だと考えられる。

1.1.1 式

 特になし。

1.1.2 命名と環境

 値という単語からはイメージしづらいが, Lisp では手続きも値である。  変数と値はただのペアであり,変数は箱のようなものではない。

1.1.3 組み合わせの評価

 Lisp の基本は (f a1 a2 ... an) という式に対して,まず f を評価して手続きを取り出し,a1 a2 ... an を順に評価した結果を手続きに渡す。特殊形式はこの評価の規則に沿わないものである。

1.1.4 複合手続き

 関数では外の環境を引きついで,仮引数の名前を使ってローカルな環境を作成している。

1.1.5 手続き適用の置換モデル

 特になし。

1.1.6 条件式と述語

 and や or が特殊形式であることは注目する点である。これは C などと同様である。C における if( p1 && p2 ) で, p1 が偽だった場合は p2 は実行されない。

練習問題 1.1

 特になし。

練習問題 1.2

 特になし。

練習問題 1.3

 特になし。

練習問題 1.4

 式が手続きを返す例である。

練習問題 1.5

 if の評価規則が非常に重要である。

質疑まとめ

 以下は決められた範囲を読んだ上でその後疑問点を誰かが挙げ,誰かが答えるという形で質疑応答を行った。読んだ部分の内容だけでなく LispScheme に関する話が多かった。現状の知識でのやりとりであるため間違いが含まれている可能性が高い。また,ここではの話題はあくまで Scheme における話,さらには Racket 特有の話である場合があり Lisp 全般に共通するとは限らない。(Scheme 特有の話としては #t#f が,Racket 特有の話としては #<void> などが良い例である。)

  • difine とは何か? 関数?

 特殊形式であり関数ではない。 (多分) マクロで定義されており,グローバル環境に値とシンボルの組み合せを追加するようなもの。特殊形式自体は値を持たない。(> define) また評価規則が通常とは違っている。特殊形式には処理系によって提供されているもの (if など) の他に,マクロを用いることで作成できる。つまりマクロは評価規則を操作できると考えることができる。

  • ここでいう式とは?

基本的な式のひとつとして,数値があります
基本的な手続きを表す式 (例えば +*) と組み合わせることで複合式を作り P6

  • Racket とは何か?

Racket is a full-spectrum programming language. It goes beyond Lisp and Scheme with dialects that support objects, types, laziness, and more. Racket enables programmers to link components written in different dialects, and it empowers programmers to create new, project-specific dialects. Racket's libraries support applications from web servers and databases to GUIs and charts. http://racket-lang.org/

 私は Scheme の処理系のひとつという認識だったが,「Scheme の仕様を満たした上で拡張された別な言語」という認識の方が正しいかもしれない。

  • definecond 式で条件に当てはまらなかった場合はなにを返しているのか

 Racket では #<void> というものを返しているようだ。参考 Scheme の仕様上, #f 以外は全て真として扱われるため注意が必要な場面があることが予想できる。

  • 適用順序評価と遅延評価は同じものであるか?

 正規順序評価の方が遅延評価に近いものである。ただし全くのイコールではない (はずである)。この辺りの理解は正確でない。遅延評価は引数の評価を遅らせることを指し,正規順序評価はある式を,ある一つの値まで評価する際の流れを定義したものだと考えている。

  • 環境とは?

値と記号を関連づけ,後から取り出すことができるということは,名前とオブジェクトのペアを記録しておくために何らかのメモリを持っておかないといけません。このメモリは環境 (environment) と呼ばれます P9

  • +-define することは可能か?

 Lisp における +- というのは,ひとつの名前とオブジェクトの組み合わせにすぎないため容易に可能である。ただしインタプリタ上で (define + -) を行った場合,他で + の処理を別な名前で定義していなかった場合 ((define sum +)など) インタプリタの再起動が必要になると思われる。

  • #t#f とは

 0 や 9と同じような定数であり,それぞれ真・偽を表すものであり,インタプリタ> #t とすると #t と評価される。Scheme では #f 以外は全て真として扱われることに注意をする必要がある。また,(#f)インタプリタに渡したところエラーが出たという話がでたが,Lisp では (f a1 a2) のように括弧で渡した場合は最初の f の値は手続きでなければならない。

 できるようである。http://d.hatena.ne.jp/reinyannyan/20100624/p1

  • 角括弧は使える?

 Scheme では角括弧は丸括弧と同じく使用できる。

読書会進行方法と感想

  •  まず私が適当にページを決め Slack にその範囲と終了時間を書き,全員で同時に黙読を始めた後,終了した人はその Slack に Add reaction するという形で進行した。その Slack のチャンネルはこれのためだけにひとつ用意することで, Add reaction では通知が行かず,周りの進行状況を気にせず読むことができる。ただ Add reaction を忘れると進行に影響がでるので,必ず忘れないようにすることを直前に注意した方がよい。
  •  この日は読書中の質問は出なかったが,読書中の発言も可とした。ただ,それ以降を読み進めること影響がでる疑問でなければ,範囲の終了後に質問する方が全員しっかり会話に参加できるので良いかと思った。
  •  質問者は,自分の質問とそれへの解答を簡単にまとめたものを Slack に記入するようにした。これは純粋に,読書会におけるもっとも価値のある議論・会話を記録することと,その日に参加することができなかった人たちへの共有のためであり,少々手間ではあるが必ず行うべきたと感じた。
  •  疑問に対する返答で少し自分が出しゃばりすぎた。質問とそれへの解答は手を挙げてから話しをするようにした方が良いかもしれない。
  •  ある疑問に対して,「それはここに書いてあるのでは?」と指摘してもらえることは読書会の利点のひとつだと感じた。しっかり読んでいるつもりでも無意識に読み飛ばしてしまっているところを補完することができた。