すべては関数である: David Beazley と SICP 講義の感想
(ezzeriesa.notion.site)David Beazley と SICP 講義の感想: 1週間の体験
2022年末に David Beazley の SICP 講義 に参加した体験を共有する。無料の資料は数多くあるが、Dave の講義は特定のテーマを選び、深く掘り下げて説明することで非常に効果的だった。
出発点
SICP 講義は Scheme 言語で進められ、ここでは Python で簡単な Scheme インタプリタを実装し、基礎概念である 置換(substitution) モデルを説明する。
Scheme 言語の基本
- プリミティブ(Primitive): 基本的な値（例: 整数）
- 演算子:
+,-,*,/などの基本演算を前置記法で使用 - define: 変数定義
> (define x 2)
> (+ x 3) ; 結果: 5
- if: 条件式
- lambda: 無名関数の定義
> ((lambda (x) (* x x)) 3) ; 結果: 9
Python における Scheme インタプリタ
Python を使って Scheme コードを評価する簡単なインタプリタを実装する。基本演算は Python 関数として定義される。
definitions = {
"+": lambda x, y: x + y,
"*": lambda x, y: x * y,
}
例:
> evaluate(("+", 2, 3)) # 結果: 5
define と lambda の実装、そして条件式 if の処理まで含まれる。
置換モデル(Substitution Model)
置換モデルは単純なプログラム解釈の方式で、変数を値に置き換えながらプログラムを評価する。しかし 代入(assignment) が含まれると、このモデルは破綻する。
状態(State)
置換モデルが崩れる例として 代入(assignment) を挙げられる。たとえば銀行口座の残高をモデル化する際、set! を使って変数を更新する。
(define balance 100)
(define (withdraw amount)
(set! balance (- balance amount))
balance)
この場合、置換モデルは更新前と更新後の残高状態を区別できない。
環境(Environment) モデルが必要になる。変数は環境の中で定義され、各手続きはそれぞれ独自の環境を持つ。
ストリーム(Streams)
状態をモデル化するもう一つの方法として ストリーム がある。ストリームは遅延評価(lazy evaluation)を通じて未来の値もモデル化できる。
無限ループと評価順序
評価順序の違い: ほとんどの言語は 適用順評価(applicative-order evaluation) を使い、引数を先に評価する。
> (square (+ 1 2)) ; 結果: 9
しかし 正規順評価(normal-order evaluation) は、引数が実際に必要になるまで評価を遅らせる。これにより無限ループを回避できる。
> (define (p) (p))
> (define (test x y) (if (= x 0) 0 y))
> (test 0 (p)) ; 正規順では 0 を返し、適用順では無限ループ
ラムダ計算と Church 数
Church エンコーディング によって、数を手続き(procedure)として表現できる。これは関数型プログラミングの重要な概念である。
(define (zero f) (lambda (x) x))
(define (increment n) (lambda (f) (lambda (x) (f ((n f) x)))))
zeroは引数をそのまま返す関数（identity関数）incrementは関数呼び出しをもう一度適用する
例
> ((zero (lambda (x) (+ x 1))) 0) ; 結果: 0
> (((increment zero) (lambda (x) (+ x 1))) 0) ; 結果: 1
反復 vs 再帰
Scheme は for ループ の代わりに 再帰 を使って反復処理を行う。
再帰の例: 階乗
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
この再帰呼び出しはスタックを使うため、多くのメモリを消費する可能性がある。
末尾再帰最適化(Tail-call optimization)
Scheme は 末尾再帰最適化 によってメモリ使用量を減らす。これにより反復的(iterative)プロセスのように動作する。
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* product counter) (+ counter 1))))
(iter 1 1))
まとめ
David Beazley の講義は、SICP の主要概念を選び出して深く扱っている。特に関数型プログラミング、ラムダ計算、評価順序など、さまざまなプログラミングパラダイムを理解する助けになる。
Knuth の引用
理論だけを学んでいるなら実践的な面に集中すべき時期であり、実践だけをしているなら理論的な面に集中すべき時期であることを意味する。
1件のコメント
Hacker Newsのコメント
SICPの講義は情報密度が高い一方で、学生とのQ&Aや黒板の使用などにより時間がかなりかかる。講義の順序も再構成できる可能性がある。個人的には新しい動画シリーズを計画中
状態を純粋関数としてエンコードする方法を紹介している。さまざまなデータに対する純粋関数的なエンコーディングが存在する
ブログ記事のURLアンカー/ハッシュのせいでポストスクリプトへ直接移動してしまい、混乱した
cons/car/cdrをラムダで実装したのは、初めて見たとき魔法のようだった。これは言語ランタイムがキー/値辞書を実装しなければならないことを示している
David BeazleyはPython界で伝説的な人物であり、この講義は最初こそ意外だったが、すぐに完璧な組み合わせだと思うようになった。次の講義に登録した
帰納的データ型が必要だという概念に触れた。Churchエンコーディングだけでは
0 != 1のような定理の証明はできない記事自体は興味深かったが、ページのナビゲーションが難しかった。キーボードの矢印でスクロールできない
「代替モデル」セクションのコードに誤字がある。
fibではなくfibonacciを使うべきだ。GitHubリポジトリのコードは正しい本に関する議論が進行中のリンクがある。リンクがページ下部の議論に直接つながる理由が気になる。別の議論に統合できるのか気になる
YouTubeリンクが提供されている