すべては関数である: 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/Lisp/Schemeに深く入り込むと、プログラミングについての考え方が変わることがあり、そうした知的刺激は常に歓迎すべきものです。
ただし、そのアイデアをオブジェクト指向のコードベースに丸ごと適用すると、たいてい逆効果になったり、チームメンバーの反発を招いたりします。
たとえば Lisp 以後、すべての
forループをforEachに置き換えたり、あらゆるものをmap/reduceチェーンにしたくなるかもしれませんが、その言語が関数型プログラミングを全面的に受け入れていないなら、可読性と性能の両方を損なう可能性があります。結局、可変メモリと CPU がコードを処理しているという事実を覚えておくことが基盤を与えてくれますし、最近では Church 数のような抽象概念よりも、データ指向設計やハードウェアの現実に合わせた「機械的共感」のほうが、日常的にはより実用的だと思います。
副作用が少ないほど予測しやすく、オブジェクト指向は単なる関数で十分な場面でもよく使われます。
ゲーム開発では計算や危険なコードが多いためオブジェクト指向がかなりよく合いますが、Web 開発では関数型プログラミングのほうがずっと自然で、SaaS では Elixir のような言語のほうが、より信頼性が高く、バグが少なく、テストしやすいコードを書かせてくれます。
さらに
forEachやmap/reduceのようなものは Smalltalk のコレクションにすでにあり、第一級の構文ではないにせよ Object Pascal や C++ にもコピーされました。下層のメモリが可変であるため、本当に必要なときには ML 系の言語にも変更を扱うためのメカニズムがあります。
gotoに近いですが、gotoは Lisp よりもさらに人気がありません。もっと奇妙なのは、現代の CPU で性能を出すにはキャッシュが不可欠なのに、メモリ階層を第一級市民として扱う言語がまだないことです。
最も近いのは、アンダースコアが海のようにあふれる Linux 風の C くらいに見えます。
純粋関数で状態をエンコードするための良い入門になっています。
実際、木、整数、和/積型、画像、モナドなど、あらゆるデータについて純粋関数型のエンコーディングははるかに多く存在します。
エンコーディングは少し混乱することもありますが、同時に優雅で小さいものです。
たとえば JavaScript で Maybe モナドを関数型に実装すると、次のようになります。
Nothing = nothing => just => nothingJust = v => nothing => just => just(v)pure = Justbind = mx => f => mx(mx)(f)evalMaybe = maybe => maybe("Nothing")(v => "Just " + v)console.log(evalMaybe(bind(Nothing)(n => pure(n + 1)))) // Nothingconsole.log(evalMaybe(bind(Just(42))(n => pure(n + 1)))) // Just 43data Maybe a = Nothing | Just afoldMaybe :: (Unit -> r) -> (a -> r) -> Maybe a -> rfoldMaybeに渡す2つの高階関数が、それぞれNothingとJustに対応します。ただし
Nothing側は、少し正確にするためにUnitパラメータを追加した形です。型理論ではかなり見事ですが、実際のプログラミングにはあまり向いていません。
以前、実際のSICP講義、つまりMIT OCWの1986年の録画を見たことがある
情報密度が高いとよく称賛されるが、実際には学生との質疑応答、講義室で「マルチメディア」発表を試みたことに講師が注意を向ける時間、授業全体の計画が事前に完全には整理されておらず質疑応答を先回りして抑えられていない部分などで、かなり多くの時間が浪費されている
黒板に書く時間も積み重なると相当なものになる
もちろん教材の順序はいくらでも議論して組み替えられるし、いつか自分の感覚に合う形でこの内容を説明する動画シリーズを自分で作るつもりもある
この講義がPythonのようなより現代的な言語を使いながらも根を保っているようでうれしいし、Pythonは実用的なマルチパラダイム言語なので、完全な純粋性ではないとしても関数型イディオムによる表現力を人々は十分に評価していないと思う
Pythonはこの講義から外してもよいし、外すべきだと思う
Pythonの関数型プログラミング支援は非常に弱い
リストはconsベースではなく、ラムダには制約が多く、パターンマッチングはひどく、式ベースでもなく、名前空間も妙だ
Pythonは現代的な言語とも言いにくく1990年代にとどまっており、まともなC-APIがあったために、残念ながらよりよい言語たちを犠牲にしながら成長しただけだ
末尾呼び出し最適化がないため、一部のコード演習はSchemeとはまったく違う解法が必要になる
1:1で翻訳したコードが失敗したら、講師は学生に対して、選んだ言語のせいでそう動作しないのだからただ信じてくれと言うべきなのか、それともすべてをスタックを外部化する問題として見てそう解くべきなのかと思う
SICPをPythonに無理やり押し込むのはかなり愚かに見える
サイトは今はオフラインだが、archive.orgで講義を見ることができる
https://en.m.wikipedia.org/wiki/ArsDigita#ArsDigita_Foundati...
https://archive.org/details/arsdigita_01_sicp/
全カリキュラムが入ったUSBキーを販売していたが、誰かがISOを上げてくれたら本当にありがたい
https://web.archive.org/web/20190222145553/aduni.org/drives/
Schemeでは簡単に表現できることが、他の言語では複雑な演習問題になる
学生は土台となる概念に集中する代わりに、Schemeなら気にしなくてよい実装言語の細部に集中することになる
cons/car/cdrをラムダで実装したものを初めて見たときは魔法のようだったただ結局のところ、言語ランタイムがキー/値ディクショナリを実装していて、その実装を借りて別のデータ構造を作れることを示しているのだと思う
Elixirでは望むだけ先頭から取り出せる
動作のないクロージャは閉じ込めた変数へのポインタにすぎず、2つのポインタを持つクロージャは
carとcdrを得られるペアだランタイムは参照先を定義の外でも使えるようにしなければならないので、エスケープ解析やガベージコレクションなどは必要だが、ディクショナリは必要ない
最近、定理証明で
0 != 1のようなものを証明するにはChurchエンコーディングだけではだめで、帰納的データ型が必要だという概念に触れた関連する内容をざっくりここに上げてあり、SICPに対する別の批判も一緒にある: https://intellec7.notion.site/Drinking-SICP-hatorade-and-why...
「すべては単なる関数」という見方の限界をもっとよく理解したい
0 ≠ 1を証明できそうだf = g -> f x = g xという定理から推論して右辺に不等式の事実を作り、その対偶を取ることができるChurch数同士の不等式は、不等式に関する他の事実なしには直接証明できないという話は正しそうに見える
一方、帰納的データ型では、証明システムが同じ帰納的型の2つの具体的なインスタンスから最も外側のコンストラクタ適用を再帰的に取り除き、同等性または非同等性を直接「観察」できる
ScottエンコーディングやChurchエンコーディングでそれを実現できるのか気になる
本自体はすでにここで議論されている: https://news.ycombinator.com/item?id=42157558
リンクがそのページの冒頭ではなく下のほうの議論に行く理由があるのか気になる
この記事を既存の議論に統合できるのではないかと思う
David Beazley は Python の世界ではかなり伝説的な人物で、この講義は最初は驚くべきアイデアに見えたが、2秒ほど考えてみると完璧な組み合わせに思えて、次の講義に申し込んだ。
要点は、こうした形が今後の ソフトウェアエンジニア向け継続教育 の姿になりそうだという点。
“the substitution model” セクションのコードに誤字がある。
("+", ("fib", ("-", "n", 2)), ("fib", ("-", "n", 1))),定義されているのは
fibonacciで、fibは定義されていないので、2つのfib呼び出しは明らかにfibonacciであるべき。実際の GitHub リポジトリのコードは正しい: https://github.com/savarin/pyscheme/blob/0f47292c8e5112425b5...
SICP は素晴らしいと思う。
ただ、さらに学び、数学をより勉強するほど、関係のほうがより根本的なプリミティブ概念だという結論に近づいた。
すべての関数は制限された形の関係として表現できるが、その逆はかなりの追加の仕組みを入れない限り成り立たない。
リレーショナルデータベースと SQL はリレーショナルプログラミングの最もよく知られた成功例ではあるが、この領域は依然として大きく未開拓だと思う。
今の関心は、プログラミング言語設計よりも、ごく幼い子どもたちに数学の基礎を教えることに近い。
不思議なことに、「大きい」のような述語を1項関係として、「より大きい」を2項関係として教えるほうが、同じ概念を関数として捉えようとするよりずっと簡単だ。
「すべてが関数」という見方は過度に単純化されていて、しばしば役に立たないのであまり好きではない。
たとえば、キャッシュ、RAM、ディスクなどに収まらない関数があり、N-way
JOINや探索/マッチングのように ビッグオーが爆発 する関数があり、非冪等性を含む副作用のある関数もある。関数に対するサイドチャネル攻撃を考える人はほとんどいない。
日付、時刻、継続時間などに依存する非決定的な関数もあり、関数は途中で失敗したり、優雅に失敗できなかったりもする。
共有リソースプールを使う別の「関数」に影響を与えるリソースを消費しない、と仮定するのも難しい。
関数の引数は任意に大きく複雑になりうるが、現実には限界があり、そうなるとポインタが必要になり、さらに Web やディスクのようなリモート参照が必要になる。
どこで止めろと言ってくれると助かる。いくらでも話せる。
この場合、ラムダ計算モデル は「すべてがただの関数」というアプローチの基盤であり、非常に単純でありながらチューリングマシンなどに比べて扱いやすく推論しやすいので、良い計算モデルだ。
そのため、ほとんどのコンピュータ論理と証明システムの基盤になっている。
ある関数がリソースを必要とするなら、そのリソースを要求するようにすればよく、日付/時刻に依存するなら日付/時刻に依存するようにすればよく、非決定的な値を返すなら 非決定的な値 を返すようにすればよい。
関数型プログラミングのアプローチが光る理由の一つは、こうしたものを真剣に扱うことを強制するからだ。
暗黙に共有されるリソースを使いたいなら、それをモデル化しなければならず、暗黙の共有リソースに依存する「関数」は実際の関数と明示的に区別される。
むしろ 手続き に近い。
関数は手続きだが、すべての手続きが関数であるわけではない。