計算機科学の「傑作論文集」集
ここ数年インターネットを徘徊していて見つけた「傑作論文集」をブックマークして部分的につまみ食いしたりしてきた。
自分用の備忘録として＆他の人にも有用かもしれない、ということで記事にしておく。
計算機科学全般
書籍だが、MIT出版の出しているIdeas that Created the Futureという本はすごくおすすめ：
アリストテレスまで遡って1980年まで、計算機科学を作り上げた考えの入った46本の論文が取り上げている。編者による各論文が何故重要かという前置きも非常に参考になる。カバーされている分野としても論理学、情報理論、人工知能、コンピュータアーキテクチャ、アルゴリズム、エンジニアリング、プログラミング言語など、本当に幅広い。今「計算機科学」とされているほとんどの分野の萌芽が見られるのではないだろうか。
Barbara LiskovのReading List for Computer Scientists：
Liskovは抽象的データ型などプログラミング言語の発展に非常に重要な発明をした計算機科学者で、オブジェクト指向をかじったことのある人なら「リスコフの置換法則」の人だといえばわかるかもしれない。彼女が2016年にHeidelberg Laureate Forumで講演した時のおすすめ論文リスト。
Michael Fogusの10 Technical Papers Every Programmer Should Read (At Least Twice)：
Clojure界隈で有名なMichael Fogusのリスト。彼のブログはいろいろ面白い話（例えばT言語の話とか）が載っていて好き。というか趣味が合うんだな、多分。
Michael Feathersの10 Technical Papers Every Programmer Should Read (At Least Twice)：
ちなみにこっちが元ネタ、Michael Fogusのほうがパクリオマージュである。というかこちらがよりソフトなデザイン・哲学よりな論文集だったのでFogusの方は意図的に技術的な論文を中心にまとめたとのこと。
プログラミング言語理論
自分の趣味ということもあり、プログラミング言語理論に限定したリストもいくつか発見した。
Types and Programming Languageの作者Benjamin Pierceが知り合いを対象に取ったアンケートを集計したリスト：
In September, 2004, I posted a query to the Types list asking people to name the five most important papers ever written in the area of programming languages. This page collects the responses I received.
とのこと。面白いし読んだことあるものに関しては素晴らしいものばかりなのだけど、結構偏っている気はする。プログラミング言語理論研究者ML学派のReading Listといった印象。LiskovもOderskyもWadlerもSPJもいない。McCarthyやSteeleやFelleisenはかろうじているけど例えばLambda papersは入ってない。かというとMilner4回、PlotkinとReynolds3回となっている。
Cornell大学のセミナーで2019年にやった輪講の論文リストとスライド。論文数は13本と、なかなかいい塩梅。
RedditのPL Reading Group：
こちらは2019年にReddit経由で開催されていたProgramming Languages Reading Groupの記録（とは言っても議論の内容はほとんど残っていない？）。理論的な論文もそれなりにあるのだが、特筆すべきは言語処理系実装に役に立ちそうなものもしっかりピックアップされているところ。「Compiling Pattern Matching to Good Decision Trees - Luc Maranget」、「A Catalogue of Optimizing Transformations - Frances E Allen, John Cocke」、「Compiling Without Continuations - Simon Peyton Jones」など。
「傑作」ではないかもしれない論文集
ここからは「いろんな面白そうな論文を紹介する」というコンセプトのソース。必ずしも「傑作」である必要はないし、そもそも本数が多いので主旨が違う。
Misreading chatポッドキャスト：
（ポッドキャストが始まった時点では）グーグル本社勤務だった森田さんと向井さんが論文をピックアップして紹介、話し合うというポッドキャスト。取り上げる範囲は幅広く、特に機械学習と実務的なソフトウェアのテクニカルレポート的な論文が目立つかもしれない。ゲストの二人は最近ファーストシーズンが終了したmessage passingブログにも参加していた。
Morning paperブログ：
超有名な「平日は毎日一本論文を紹介する」というコンセプトで続けられていたブログ（現在休止中）。2014年から2021年まで（途中で休止を挟みつつ）続いたので、何百本もの計算機科学論文がピックアップされている。Tagsを見ると機械学習、ソフトウェアエンジニアリング、プログラミング言語、分散システム、アルゴリズム、セキュリティなど本当に様々な分野にわたって紹介している。
バッカスの功績と経歴
John Backusという計算機科学者には大きな功績が三つある：
- IBMでFORTRANの開発を提案・主導したこと
- 構文の形式的な定義を可能とするBackus-Naur FormをALGOLの開発のために提案したこと
- チューリング賞受賞講演で、FORTRANのような命令型プログラミングからの脱却を提唱して関数型プログラミング言語FPを提案したこと
現代でも使われている最古の言語であるFORTRANの開発責任者というだけではなく、実際にプロジェクトを売り込んで上司に承認させたのもバッカスのようで、これはやはりすごい。LISPの開発者McCarthyも「IPLはアセンブリ言語っぽくて嫌だ、やっぱりFORTRANみたいに綺麗に書ける言語が使いたい」（意訳）とLISPを作る前には言っていた。
BNFに関しては構文解析を多少なりともかじったことのある人間なら必ず目にするし、TaPLの宇宙語の一部にもなっている。人類が形式言語について考える時の基本ツールの一つである。
最後のFPに関しては現代ではあまり聞かないし、どちらかというと「関数型プログラミング」を推したのが大きいのかな？と長らく考えていた。しかし、最近古い文献を漁るようになって、例えばProceedings of the 1981 conference on Functional programming languages and computer architectureなどを見たところ大量にFPをベースにした論文が見つかったので、その時代ではかなり活発に研究されていたようで、やはりFPそれ自体もかなり重要な功績のようだ。このチューリング賞受賞講演についてはまた別途記事を書きたい。
さてこのような輝かしい功績を持ち、さらにIBM出身ということで、まあコロンビアかハーバードあたりの数学あるいは工学博士でエリート街道まっしぐらな人なんだろうなーとぼんやりイメージしていた。しかし実態はちょっと違うようだ。
Out of their mindsという1998年に書かれた、著名な計算機科学者１５人の（本人インタビューを元にした）伝記を最近読んでいる。この本の最初の章がバッカスについてで、もちろんIBM入社以降の功績に記述の大部分を割いているのだが、人生の前半についても書いてあり、想像していたよりもかなり迷走しており面白い。
- 高校留年
- 父親の意向で大学では化学を専攻するものの、飽きて1年でドロップアウト
- 軍隊に入隊
- 適正を見出されて軍隊のPremedプログラムに入る（医学部に進学するための）
- 医学部に進学するも１年でドロップアウト
- コロンビア大学の数学科に入り、３年後学士取得
- たまたまIBMがコロンビア大学と提携してデモンストレーションとして開発したSSECマシンを見学、就活中だと言ったら勧められてその日のうちに入社テストを受け内定
- IBMに入社しSSECマシンのプログラマとして3年過ごす
実際の機械でゴリゴリ数値計算のプログラムを書いていた経験がその後活きてきたわけだ。あと本人は迷走しているのだけど要所で才能が認められていて地頭がすごくよかったのだろうな、という印象。
その後von Neumannが推していた固定小数点数を嫌って（プログラマが自分ですべての数値の桁を把握、修正する必要があったため）勝手に浮動小数点数を導入したり、von Neumannが「貴重なコンピュータを事務的な翻訳に使うな」と否定したFORTRANを「これからの時代コンピュータよりプログラマの方が貴重だ」と言って上司に認めさせたり、チューリング賞を受賞して「von Neumannが提唱したコンピュータアーキテクチャはボトルネックがあっていけてない、これからは関数型プログラミングだ」とブチ上げたりした。von Neumannに対して逆張りしてことごとく大成功しているようにも見える。
世紀の大天才von Neumannが自分の脳の拡張として（大量のプログラマを半ば備品として扱いつつ）使っていたコンピュータが、大量生産のレールに乗りコストが下がり、天才ではない人間にも扱えるようになり、その分プログラマを富豪的に消費するスタイルは成り立たなくなる。そういう流れを肌で感じて機敏に動き、人間の頭脳に収まり得る営みとしてプログラミングを成立させたというのがバッカスの功績の最たるものなのかもしれない。
あの頃読んでた英語テックブログ
（注：あの頃というのは私が多感だった2000年代のことである）
最近マイクロソフトのRaymond Chenの「マイクロソフト社員がIBMに出向していた時に文化の違いに辟易してコーヒーメーカーに関して小さな反抗をした」というものブログ記事を見た。
そういえばこのOld New Thingというブログ、2000年代（正確には2000年代後半）にはたまに読んでたなぁと思い出して懐かしくなった。
懐かしくなったがてら、あの頃読んでた英語ブログをいくつか紹介しようと思う。
Old New Thing
前述のとおり、マイクロソフト社員のRaymond Chenが書いているブログ。2003年にブログが始まった時点でかなり長くマイクロソフトに勤めていたらしく、その頃からマイクロソフト昔話的なものを出していたようだ。それ以外ではWindows向けC++プログラミングのマニアックな内容などが多い。
すごいのは20年近くずーっとブログを続けていて、今もほぼ毎日といったペースで記事を書き続けていること。
印象に残っている、というか多分一番初めに読んだ記事はこの例外処理の話：
後述のJoel on Softwareで言及されてたところから飛んで読んだのが最初だった。
Consequently, when I write code that is exception-based, I do not have the luxury of writing bad code first and then making it not-bad later. If I did that, I wouldn’t be able to find the bad code again, since it looks almost identical to not-bad code.
というのは肝に銘じている。
あとはこのNotepadが1990年代後半にBest Web authoring tool賞を取ったけど、その時点で誰が書いたのか誰も知らなかったという話も好き：
しかしNotepadがBest Web authoring toolというのはなかなか牧歌的だ。
Joel on Software
2000年代のテックブログを代表すると言っても過言ではないはず。Joelは元マイクロソフト社員でTrelloなどを開発するFogcreek Softwareを創業。その後後述のCoding HorrorブログのJeff AtwoodとともにStack Overflowを作る。
Joelは落語よろしく面白い逸話を話の枕にして、技術思想的なトピックについて非常に長いのに読みやすい記事を量産していたので、テックブログのお手本のような存在だった。技術的な内容に関しては断定調で強く述べられているわりに必ずしも全般的に肯定できるものではないのだが、とにかく読み物として面白いし考えさせられる。
好きな記事だけでもたくさんありすぎてすべて紹介はできないが、強いて選ぶとすれば「プログラミングにおける抽象化は必ずどこかでレイヤーが漏れるので、下のレイヤーを理解する必要はあるよ」というこの記事：
そして「コーディングスタイルでバグがわかりやすいようにしよう」という記事：
後者はハンガリアン記法の歴史とApp/System Hungarianの流儀の違いなども説明されていて面白い。
Coding Horror
Stack Overflowのもう一人の創始者Jeff Atwoodのブログ：
Joelは記事が読み物として完成しているのに対して、こちらはどちらかというと普通のブログ的。プログラマとしてもBASICから叩き上げで、新卒でMSに入ったJoelのようなCSエリートという感じではない。その分安心して読めるところもある。
特に印象に残っているのは「プログラマはこれを読め」リスト：
あらかた買って読んだので、私はそういう意味ではCoding Horrorに多大な影響を受けていると言えそう・・・。
Stevey's Blog Rants
元Amazon、Googleの開発者Stevey Yeggeのブログ：
記事が信じられないほど長い。Joelほど単体の読み物として完成されておらずまた内容は独断と偏見が強い印象ではあるのだが、その分独特の切り口があってぐいぐい読ませる。
好きな記事は（やはりたくさんあるが）「Javaが狂信的なOOP言語でいろいろおかしい」という話：
そして「Lispは理想の言語であるが故に実際に存在するLisp実装はすべてLispとして認められない」という話：
あと、このブログには載っていないがSteve Yeggeの文章として有名なのはGoogleにいた時に書いた「GoogleはAmazonに比べていろんなことを上手くやっている会社だが、唯一ダメなところはプラットフォームというものがわかってないことだ」という記事：
Stevey's Google Platforms Rant · GitHub
やはり過激な断言調で小気味が良い、が実際のところはどうなんだろうか。そしてやはり長い・・・
Secret Diary of Steve Jobs
最後はテックブログと言っていいのかどうか怪しいが、テック産業の面白ゴシップ話として読める「スティーブ・ジョブズが書いている体でアップルや周辺のテクノロジー企業の話を書く」というブログ：
けっこう長い間、本当は誰が書いてるのか謎だった覚えがある。
好きな記事はマトリックスに絡めてスティーブ・ジョブズやアップルのマーケティング戦略を語っている記事：
そしてマイクロソフトのスティーブ・バルマーがYahooを買うかも、という話が出ていた時に「バルマーも頭はいいんだから失敗するのがわかりきっているけど、古いタイプの経営者だからやめられないんだ」と解説していた記事：
スティーブ・ジョブズが放言しまくる、という体で無責任かつ意地の悪い人物評や組織評ばかりなのだが、そのぶん"Art doesn't have to be true like a theorem. It can be true in other ways." (Tom Stoppard)という感じでハッとさせられるような視点があって面白かった。
論文メモ：The Next 700 Programming Languages
プログラミング言語理論の最初期の金字塔の一つ、The Next 700 Programming Languagesを読み直したので論文メモ。これは過去に何回か読み直している個人的にも非常に思い入れのある論文。論文メモ書きたいなとここ数ヶ月ずっと思っていた。
背景
The Next 700 Programming Languagesは1966年にPeter Landinが発表した論文で、LISPやALGOL（そしてラムダ計算）を下敷きに、ある種理想のプログラミング言語の雛形としてISWIM（If You See What I Meanの略）を提唱している。このISWIMは実用に耐える実装はされなかったものの、後続の関数型言語のほぼすべてに多大な影響を与えた。CやJavaがALGOL系言語なら、Scheme、ML、HaskellはISWIM系言語である。
概要
前述のとおり、論文の主眼はISWIMという高級言語「群」の解説である。
Introductionから引用すると：
Most programming languages are partly a way of expressing things in terms of other things and partly a basic set of given things. The ISWIM (If you See What I Mean) system is a byproduct of an attempt to disentangle these two aspects in some current languages.
ISWIM is an attempt at a general purpose system for describing things in terms of other things, that can be problem-oriented by appropriate choice of "primitives."
とある通り、具体的なプリミティブ（整数やら浮動小数点数やら）については言及せず、何かしらのプリミティブが用意されている前提で、どのように大きなプログラムを組み立てていくか、という部分に集中している。
ちなみに論文のタイトルは
"... today... 1,700 special programming languages used to 'communicate' in over 700 application areas." -- Computer Software Issues, an American Mathematical Association Prospectus, July 1965.
という、論文の冒頭で引用されている文から来ているようだ。つまり1965年にコンピュータが利用されていた700のドメインに対して、各ドメイン固有のプリミティブをISWIMに追加することで700の言語ができるという話らしい。
章立て
論文本体は以下のセクションに分かれている：
- Introduction
- The where-Notation
- Physical ISWIM and Logical ISWIM
- Four Levels of Abstraction
- Abstract ISWIM
- Relationship to LISP
- The Characteristic Equivalences of ISWIM
- Application and Denotation
- Note on Terminology
- Eliminating Explicit Sequencing
- Conclusion
追加で最後にDiscussionがある。論文自体がCommunications of the ACMに載ったようなので、その一環としてこういう「論文についてのディスカッション」の議事録も載っていたのだろうか。
詳細
各セクションを個別に見ていく。
Introduction
ISWIMとはプリミティブの集合に対しての組み合わせ方を共通要素として持つ言語族で、ドメインから独立したプログラミング言語共通のロジックの部分を摘出した定義を持つ、とLandinは主張する。特に変数や関数の定義・利用については、対象がどんなドメインであってもすべての言語で定義されていることから、共通化できるはずだ、と書いてある。
またIntroductionの最後に
ISWIM is thus part programming language and part program for research. A possible first step in the research program is 1700 doctoral theses called "A Correspondence between x and Church's λ-notation.''
とある。ここの1700の博士論文というのも、前述の"... today... 1,700 special programming languages used to 'communicate' in over 700 application areas."という文から来ている。つまり1965年に存在していたプログラミング言語をラムダ計算に対応させる研究が必要だという一種のジョークである。（ジョークというのは1700言語すべてに対して研究が必要、というポイントに関してで、特定の言語、例えばALGOLなどは実際にLandinやReynoldsによってラムダ計算との対応が研究されている）
The where-Notation
ISWIMの新規性の一つはwhere（と機能的には同一の別構文であるlet）によるローカル変数定義である。今でこそLisp、ML、Haskellなどで普通に見るletやwhere式だが、大元はISWIMである（Lispはこの時点ですでに存在していたがlet式はISWIMからの輸入）。ただしletというキーワードによる変数定義はBASICが最初。あちらは命令型らしくLET文である。
Physical ISWIM and Logical ISWIM
ALGOL60と同じく、ISWIMも本体は文字列に対する依存性のないLogical ISWIMである、が論文などで書き表すために特定の文字列に依存したPhysical ISWIMが（複数）考えられる。この論文で表示されているのはPhysical ISWIMのうちの一つであるReference ISWIMになるらしい。
この「文字列に依存」というのは不思議な気もするが、1966年というとASCIIが初めて制定された1963年から三年後、大幅な改訂を受ける1967年の一年前なので、今想像できるよりも切実なポイントなのかもしれない。
Four Levels of Abstraction
ISWIMは以下の四つの層に概念的に分かれる：
- Physical ISWIM
- Logical ISWIM
- Abstract ISWIM
- Applicative Expressions
PhysicalとLogicalの違いは前述のとおり実際に使える文字列が限定されているかどうか。Abstract ISWIMは抽象構文のレベルの概念で、Logical ISWIMのようなカッコやインデントに関するルールは捨て去られている。Applicative ExpressionはAbstract ISWIMをさらに脱糖した「ISWIMのカーネル」となる。
Applicative ExpressionsについてはLandinの1964年の論文The Mechanical Evaluation of Expressionsでより詳しく解説されている。SECD抽象機械で直接実行できるIRだ。
Abstract ISWIM
Abstract ISWIMは前述のとおり抽象構文である。以下の概念が存在する：
amessage
プログラム全体。aexpressionかadefinitionになる。
aexpression
式。変数を含むプリミティブ、関数適用、条件分岐、リスト、let/where式の五種類が定義されている。（let/where式のことをbeetと呼んでいる。"...abbreviates beta-redex"とのこと）
adefinition
定義。変数（あるいは変数のリスト）への代入、関数の定義、継続を利用したジャンプ的なprogram point、再帰的定義、複数定義、where付き定義の六種類。
Program pointが面白く、pp f(x) = x(x+1)のような形で普通の関数のように定義されるが、この関数が呼び出されると、呼び出し元のwhere式の評価がその時点で終わり、式全体の値が関数呼び出しの結果になる。whereがネストした場合どういう挙動になるのか気になるところだが、論文には説明は載っていない。
Relationship to LISP
ISWIMは1960年に出たLISPを強く意識している。LISPの持っていたラムダ計算ベースの関数型言語っぽさをより強力の押し進め汎用化したものだと言える。
Relationship to LISPのセクション冒頭を引用すると：
ISWIM can be looked on as an attempt to deliver Lisp from its eponymous commitment to lists, its reputation for hand-to-mouth storage allocation, the hardware dependent flavor of its pedagogy, its heavy bracketing, and its compromises with tradition.
とある。
- LISPはその名のとおりシンボリックなリスト処理が主眼な言語だった（特に1960年代では）のに対して、 ISWIMはドメインを特定しない
- LISPは動的なメモリ確保の頻繁さによる効率の悪さが問題視されていたが、ISWIMは（ガベージコレクションは必要とはいえ）where/letを使うことによってメモリのプリアロケーションが可能になる
- LISPは（特に命令型な部分について）実行機械に依存している機能が多いがISWIMは抽象機械を使うことでそのような機能を特定のマシンに依存することなく実装できる
- 構文がS式じゃない。where/let式の存在、中置演算子、そしてオフサイドルールによるインデントベースの記法を採用している
5番目のLISPの欠点はCompromises with traditionだとあるが、よく読むとこの点については触れられていない。
このセクションの５項目めは逆にISWIMが継承しようとしたLISPの美点である：
The most important contribution of Lisp was not in list-processing or storage allocation or in notation, but in the logical properties lying behind the notation. There ISWIM makes little improvement because, except for a few minor details, Lisp left none to make. There are two equivalent ways of stating these properties.
(a) Lisp simplified the equivalence relations that determine the extent to which pieces of program can be interchanged without affecting the outcome.
(b) Lisp brought the class of entities that are denoted by expressions a programmer can write nearer to those that arise in models of physical systems and in mathematical and logical systems.
プログラムの一部を別のコードに変換しても結果が同一であると保証される厳密な同値関係のルールが、命令の羅列であった過去の言語に比べて非常に明瞭になり、コードに出てくる式が表す対象がより数学的・論理的なモデルに近くなったのがLispの最大の功績だとLandinは考えている。
The Characteristic Equivalences of ISWIM
前述のとおり、ISWIMがLispから継承した「プログラムの部分式に基づいた同値関係が明確」という点をLandinは非常に重要視している。
その最大の理由は：
The practicability of all kinds of program-processing (optimizing, checking satisfaction of given conditions, constructing a program satisfying given conditions) depends on there being elegant equivalence rules.
つまりプログラム自体を処理対象（それが手動であれ自動的であれ）とするため、ということだ。
同値関係のルールには四つのカテゴリがある：
- 部分式が同値な場合、式全体に置いてどのような同値関係が成り立つか
- 変数・関数に関連した同値関係
- 特殊形（条件分岐、リスト、再帰）とそれに関連するビルトインに関する同値関係
- ISWIMに追加される特定ドメインのプリミティブに関する同値関係
各グループについて実際にルールを列挙している。特にグループ２に関しては「ISWIMの純粋な部分に限って」ラムダ計算の重要な結果であるChurch-Rosser Theoremが成り立つのがポイント。
Application and Denotation
既存のプログラミング言語に対して数式などがよりシンプルである構造として
- 式がネストした部分式の組み合わせでできていること
- 一つ一つの部分式が何かを意味していること（数、真偽値、関数など）
- ある式の意味（つまり「値」）は、その式を構成する部分式の値によって決定されること。ある部分式の「値」以外の性質には影響されないこと
が挙げられる。特にcが数式のシンプルさに大きく寄与しており、プログラムが関数型であるかについての真のテストはcを満たしているかどうかだとLandinはいう。
前述のISWIMの同値関係は、ISWIMの純粋なサブセットに関してcを満たすことを保証している。
明確な言及はないがこのセクションは表示的意味論の話になっていると思う。表示的意味論の歴史の中でこの論文がどういう位置付けになるのかは今後調べてみたい。
Note on Terminology
プログラミング言語やプログラムについて使われる用語としてprocedural, nonprocedural, algorithmic, heuristic, imperative, declarative, functional, descriptiveなどがあり用語の混乱がみられるがISWIMをベースに考えるといくつかの独立した軸が見られる、という話。ついでにISWIMを最もよく表す言葉として「denotational language」という新しい用語も提唱している。やはりdenotational semanticsとの繋がりを感じる。
Eliminating Explicit Sequencing
既存の命令型言語（ALGOLなど）でGO TOなどを排除するために単一の文や式でより大きな処理を行うようプログラムを書き換える、という「ゲーム」がよく行われていたらしい。この場合「ゲーム」というのがどういう意味を持つのかよくわからないが・・・。とにかく、ALGOLでもそのようなことがある程度は可能だったが、ISWIMはより式ベースな言語であり、かなり機械的に「命令の直線的な羅列」なプログラムを、大きな式に変換することで明示的な実行シーケンスを消すことができる。
Conclusion
ISWIMの目的はプログラミング言語を「特定ドメインでの実用上必要になる機能」から抽象化し、すべてのドメインで必要となる雛形の論理構造を明らかにすることだった。
The question arises, do the idiosyncracies reflect basic logical properties of the situations that are being catered for? Or are they accidents of history and personal background that may be obscuring fruitful developments? This question is clearly important if we are trying to predict or influence language evolution.
「今後のプログラミング言語の進化を予想・影響」というのは普通は「鬼が笑う」レベルの大袈裟な話なのだが、この論文に関しては（少なくともアカデミックなプログラミング言語研究における）現代まで連なる言語の進化の源流となっているのがすごいところだ。
余談
ISWIMは現代の静的型付き関数型言語（HaskellやML）の源流であることは間違いないのだが、それ自体は動的型付き言語である。スッキリした記述と静的型を同居させるには1970年代初頭のLCF MLで型推論が開発されるのが必要だったようだ。
前述のとお李、論文の最後にDiscussionがあるのだが、NaurやFloydが「インデントベースの構文って大変じゃない？」という話をしていて、ここ十数年でよく見たPython構文談義が1960年代にもされてたのが面白い。
またStracheyが
Nearly all the linguistic features, such as
whereandwhileandandandrecursive, that Peter Landin has been talking about are incorporated as an integral part of a programming language being developed at Cambridge and London called CPL.
と言っていて非常に興味がある。CPLに関して何か文献ないかな・・・
文献で言えばこの論文のReferencesが
1 LANDIN, P. J. The mechanical evaluation of expressions. Comput. J. 6, 4 (Jan. 1964), 308-320.
2 --. A correspondence between ALGOL 60 and Church's Lambda-notation. Comm. ACM 8 (1965), 89-101; 158-165.
3 --. A formal description of ALGOL 60. In Formal Language Description Languages for Computer Programming, T. B. Steel, Jr. (Ed.), North Holland, Amsterdam, 1965.
4 --. An abstract machine for designers of computing languages. (Summary). IFIP65 Proc., Part II.
で自分の論文・記事だけなのが男らしくて笑えた。
Acknowledgementsで
The author is grateful for helpful discussions with W. H. Burge. Wider influences on the investigation of which this paper is one outcome are mentioned in [1]. Of these the main ones are the publications of Curry and of McCarthy.
と書いてあるので、より広範囲は参考文献はThe mechanical evaluation of expressionsを見てくれ、ということなのか。
PerlisとDijkstraとBauerとAPL
かなり前に、DijkstraとWirthがAPLの話をIversonから聞いて「俺たちの目が黒いうちはこんな言語は絶対流行らせない」と言ったという話をどこかで読んだ気がしていてソースを探していたのだけど、なかなか見つからずに残念に思っていた。
DijkstraがAPLのことを嫌っていたのは結構有名で
APL is a mistake, carried through to perfection. It is the language of the future for the programming techniques of the past: it creates a new generation of coding bums. - EWD498 - How do we tell truths that might hurt?
や
I thought that programmers should not be puzzle-minded, which was one of the criteria on which IBM selected programmers. We would be much better served by clean, systematic minds, with a sense of elegance. And APL, with its one-liners, went in the other direction. I have been exposed to more APL than I’d like because Alan Perlis had an APL period. I think he outgrew it before his death, but for many years APL was “it.” - CACM Interview 2001
などの発言が散見される。2番目のCACMインタビューではPerlisがAPLが好きだったという話も出てくる。Perlisが好んだ言語だったので不本意ながらAPLに接触する機会があったとDijkstraが言っているのは、この二人はどのような関係だったのだろうと想像してしまって面白い。
（ちなみに1番目のEWD498はDijkstra版Epigramsとも言えそうだが、Perlisのそれに比べてあまりにも毒が強烈）
さて前日の記事でPerlisの話をしたので、少しPerlis関連でネットを漁っていたら
というPerlis自身によるAPLの話が出てきた。APL'78 Conferenceでの講義録らしい。
PerlisにとってのAPLの良さ、言語の進化、思考を表現するツールとしてのプログラミング言語、ワンライナーの功罪、プログラミング教育におけるBASICの危険性などいろいろと楽しい話が出てくる。またEpigramsの作者らしく非常に文章が洗練されている。
DijkstraとBauer、APLを嫌う
そしてこの文章の冒頭でようやくDijkstraの「俺の目の黒いうちは・・・」発言のソースを見つけた。ただしDijkstraの相方はWirthではなくてFritz Bauerだった。
I was at a meeting in Newcastle, England, where I’d been invited to give a talk, as had Don Knuth of Stanford, Ken Iverson from IBM, and a few others as well. I was sitting in the audience sandwiched between two very esteemed people in computer science and computing — Fritz Bauer, who runs computing in Bavaria from his headquarters in Munich, and Edsger Dijkstra, who runs computing all over the world from his headquarters in Holland.
"Edsger Dijkstra, who runs computing all over the world from his headquarters in Holland."というのはなんだかBond villainっぽくていい感じではある。
Bauer, on my left, ... muttered under his breath to me, in words I will never forget, “As long as I am alive, APL will never be used in Munich.” And Dijkstra, who was sitting on my other side, leaned toward Bauer and said, “Nor in Holland.”
そしてまた発言も非常に悪役らしくていい。まあこの話はAPL好きのPerlisがAPL Conferenceで講義した時に出たものだから、まさにBauerとDijkstraは悪役として出てるわけだが。
しかし1960年にALGOLが制定されるとき、再帰を言語仕様に入れるかどうかで喧嘩して騙し討ちに近いAmsterdam plotにまでなったBauerとDijkstraが仲良くAPLの悪口を言っているのは感慨深いものがある。
PerlisとDijkstra、BASICを嫌う
Perlisの講義の終わりのほうで、少し唐突にBASIC批判が始まる：
...we’ve got to get BASIC out of the public school system. BASIC is really harmful for young people. It’s all right for old-timers. But for young people in the 11th and 12th grades of high school, in junior colleges, and in universities, the belief that by writing BASIC programs they are appreciating the beauty of programming at the exercise level that they do, and can do, in the amount of time available to them — that idea is pernicious. It is very dangerous, to boot. We are creating a set of semiliterates...
言語仕様がいけてないとかそういう話ではなく、「BASICで教育することは危険だ」とまで断言している。この発言はDijkstraのBASIC批判を彷彿とさせる：
It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration. - EWD498 - How do we tell truths that might hurt?
ただ、Dijkstraの発言は「いつものDijkstraだ」（"arrogance in computer science is measured in nano-dijkstras" - Alan Kay）と安心して聞けるが、Perlisも同じようなことを言っているというのは面白い。一体BASICのどういうところがここまで忌み嫌われるのだろうか。
Epigrams
あとはいくつか面白い部分を抜粋してみる。
APLが多彩な表現を可能にする、という話：
If Shakespeare were alive today, he’d be a programmer, and he’d be writing one-liners in APL.
ある意味Perlに似ているのかもしれない。There's more than one way to do it。そういえばIf Hemmingway Wrote JavaScriptって本があったな・・・
プログラミング言語が思考を表現できるか、という話：
Some years back, we had a visit at Carnegie from a person at MIT whose name I’ve forgotten. He started to give us a lecture in a little office about some programming issues in LISP. He went up to the blackboard and he spoke LISP. Everything he wanted to describe, he described in terms of parentheses and CONS and CARS and CDRS. He found himself quite capable of expressing his ideas in the language in which he programmed. Not once during the half hour or so that he lectured to us did I see the inevitable block diagram, the flow charts that show up on the blackboard with things written in semi-English. He didn’t need them. And at the time I said to myself, ”LISP has a very precious character, if indeed there are some people who can express programming ideas to other people in the language in which they program.” I can’t do that with ALGOL; never have I been able to do it with ALGOL.
ここでいう思考というのはプログラミングの概念なのでそこまで神秘的な話ではないが、それにしても現代からするとALGOLの表現力が弱かったのか？という気もしなくもない。まあUMLで説明したくなるっていうのは似たような話だろうか？
プログラミング言語にいくら機能を追加しても完璧にはならない、という話：
...programming, by its very nature, is a kind of bootstrapping activity. What Iverson and God give you today, you’ll find insufficient tomorrow.
ここでGodが出てくるのがいい。
APLを理解すればプログラミング言語全部理解したことになるという話：
once you’ve learned APL, you know BASIC, you know FORTRAN, you know ALGOL, indeed, I think you know all programming languages. You don’t know how you know them, but you know them.
なんだかめんどくさい言語オタクみたいなことを言い出してる・・・
しかしバランスをとって、プログラミング言語の布教の話：
And it certainly shouldn’t be a goal of people who use APL to stand forth and say, “Why do you jackasses use these inferior linguistic vehicles when we have something here that’s so precious, so elegant, which gives me so much pleasure? How can you be so blind and so foolish?” That debate you’ll never win, and I don’t think you ought to try.
これは好きな言語がAPLであれ、ML、Lisp、Haskell、Rustなどなどであれ、余計な一言を言いたくなる気持ちをうまく捉えた箴言だと思う。肝に銘じたい。
Graydon HoareのCompiler講義資料が面白かった話
Graydon Hoareが2019年にカナダのブリティッシュ・コロンビア大学でコンパイラ関連のゲスト講義した時の資料21 compilers and 3 orders of magnitude in 60 minutes - a wander through a weird landscape to the heart of compilationを読んだら大変面白かったのでメモ。
作者
Graydon HoareはMozillaでRustを開発したことで有名。その後Rustの開発もMozillaも離れて（というかRustの開発からは2013年に離れたようだ）、一時期AppleでSwift開発チームに所属していたらしい。（ソース：Reddit: I wonder, why Graydon Hoare, the author of Rust, stopped contributing into it and switched to Swift?）
概要
そういった作者のプログラミング言語開発の経験を元に、学生に実在のコンパイラについていろいろ解説した講義。
話の流れとしては：
の二点を豊富な実例（タイトルにもあるとおり21個のコンパイラ）を紹介しつつ解説している。特に最後の部分に重きを置いているので、例えばRustコンパイラ開発秘話のような内容は入っていない。
巨大コンパイラ
巨大なコンパイラの実例として挙げられているのは以下の四つ：
- clang
- swiftc
- rustc
- gcc
最初の三つはLLVMを使っており、コンパイラの大きさとしては
（ちなみにLLVMは120万行）となるようだ。ただし言語がまちまちなので行数で比較できるものでもないかもしれないが・・・。
一番気になったのはGCCに含まれているという60万行のAdaコードだ・・・。何に使われているのだろうか。
巨大さの理由
上記のコンパイラがなぜここまで巨大になったか、について４つの原因を挙げている：
これらのコンパイラに関しては巨大であることは合理的だとした上で、しかしコンパイラは必ずしも大きくなる必要はない、プロジェクトが置かれているコンテキストに拠る部分が大きいとのこと。違うコンテキストではどのような技術的選択がありえるのかについて実例とともに見ていく。
コンパイラ開発における技術的選択
資料の後半（というかスライド数では全体の2/3）ではコンパイラをそこまで大きくしない７つの手法が紹介されている：
軽く個別に見ていく。
最適化手法の限定採用
いろんな最適化を頑張ってもそこまで劇的なパフォーマンス改善は見られない（特にCのような低レベルな言語になると）、というわけで1971年（！）に出たA Catalogue of Optimizing Transformationsという論文に載っている８つほどの最適化を実装して終わるのがいいんじゃないか、という話。多くのコンパイラは最適化はこの８つだけ（あるいはそのサブセット）。それだけで、カリカリに最適化するのに比べて大体８割ぐらいのパフォーマンスが出るとのこと。
コンパイラに合った開発言語の選択
MLやLisp（特にSchemeやRacket）を使いましょう。ASTを直接表したりパターンマッチができる言語だと木構造に対する処理が直接コードに書き表せるので、コンパイラが非常に書きやすい。
メタコンパイラ
パーサだとLex/Yaccがあるが、それをコンパイラ全体に拡張したような「言語仕様を記述するDSLからコンパイラを出力する」メタコンパイラが存在するらしい。そういうツールを使ってしまえば非常に簡単に（かつ少量のコードで）コンパイラが得られる。
IR・バイトコードへのコンパイル
バイトコードインタプリタの話。OCamlの開発者Leroyの「バイトコードインタプリタはちゃんとしたコンパイラの1/4くらいのパフォーマンスだけど、実装コストは1/20くらいだ」という言葉を紹介している。OCaml（というかその前身であるCaml Light）は元々Zinc抽象機械というバイトコードインタプリタだけで開発されて、その後Nativeコンパイルもサポートされた経緯があるので、その経験からくる発言と考えると面白い。
プログラムのサブセットをコンパイル
パフォーマンスに影響が大きそうで、コンパイルがしやすい関数だけコンパイル。それ以外の部分はインタプリタに任せる。この手法はJITとの相性もいいらしい。
インタプリタの部分評価
二村射影の話。インタプリタを書いて、それを部分評価して静的に解決し得る部分を解決してしまうとコンパイラになる。Graal/Truffleで実用化しているという話も紹介されている。
IRやASTを省略
IR（コンパイラの中間表現）がなく、ASTから直接アセンブリ言語を出力するのはそれなりに事例がある（@rui314さんの8ccも紹介されている）。それをさらに進めてPascalではAST自体も必要ないように構文がデザインされていて、シングル・パスで行単位で処理・コード出力されるようになっていたとのこと。後者は本当にコンパイラを簡単にするようなメリットがあるのだろうか？
まとめ
RustとSwiftという現代的な言語の開発経験がある作者の「技術的な多様性を紹介することを主眼に置いたおもしろコンパイラ探訪」といったところで、自作言語のコンパイラに関する技術的なアイデアを得るのもよし、よもやま話的に興味本位で読むのもよしである。
個人的にはA Catalogue of Optimizing TransformationsとGraal/Truffleについての論文One VM to Rule Them Allがとても読みたくなった。
Every language is a Perlis language
時々ツイッターで俎上に上がる言説として「プログラミング言語は一つ学んだら大体全部同じ」という話と「お前HaskellやLisp見ても同じことが言えるの？」、そして「いやHaskellやLispだってそこまで違うわけじゃない」という一連の流れがある。
これで思い出すのはAlan PerlisのEpigrams of Programmingである。ACM SIGPLAN Noticesの特別記事として出されたユーモアたっぷりの箴言集で、序文からしていい感じだ：
The phenomena surrounding computers are diverse and yield a surprisingly rich base for launching metaphors at individual and group activities. Conversely, classical human endeavors provide an inexhaustible source of metaphor for those of us who are in labor within computation. Such relationships between society and device are not new, but the incredible growth of the computer's influence (both real and implied) lends this symbiotic dependency a vitality like a gangly youth growing out of his clothes within an endless puberty.
The epigrams that follow attempt to capture some of the dimensions of this traffic in imagery that sharpens, focuses, clarifies, enlarges and beclouds our view of this most remarkable of all mans' artifacts, the computer.
特定界隈で最も有名な例としては
だろう。オスカー・ワイルドをもじってLISPの計算効率の悪さをやんわりと揶揄している。
19番目の箴言が
- A language that doesn't affect the way you think about programming, is not worth knowing.
というもの。言語が思考・世界観を規定するというサピア・ウォーフ仮説を彷彿とさせる。
この箴言を受けてPerlis Languageというものが時々言及される。つまり「どういった言語が（一般的な言語を使っているプログラマの）プログラミング観に大きな影響を与えるのか？」という問いに対しての答えである。Perlis languageの候補としてよく挙がる言語はLisp系、ML系、Forth系、APL系、Prolog系などだろう。
例えばLambda the Ultimateというプログラミング言語理論のコミュニティブログのこの記事やMichael Fogusの記事などで直接この話題が取り上げられている。あるいはIo、Prolog、Haskellなどの多彩な言語を一週間ずつ試していく「７つの言語 ７つの世界」（原題「Seven Languages in Seven Weeks」）という書籍も同一のコンセプトだと言えそう。
個人的にはこういう話が大好きで、そしてこういったいわゆるPerlis languageというものに触れるのも好き。プログラマとして日々のコーディングに役に立っているか、というのは微妙な気もするが・・・。ここら辺は読書が好きだけど、それが仕事の糧になっているかどうか、という話と似ているかもしれない。「直接的に役に立っているという実感はないが、頑張れば役に立っている理屈をつけられないこともないが、正直なところ役に立つからやっているわけじゃないし、楽しいからやっているけど何らかの非自明な因果で役に立っているといいなという淡い期待はある」という感じ。
しかし（ここから本題）Perlis Languageとして特定の言語を挙げる、という行為はすなわち他の言語を「非Perlis言語」としてカテゴライズする意味も持つのではないか？つまり例えばCを知っている人間がC++を、C++を知っている人間がJavaを、RubyistがPythonを（そしてもちろんその逆も）学ぶことでプログラミング観は広がらない、ということにならないだろうか？
実際にはそんなことはまったくないと思う。I can write FORTRAN in any languageというジョークがあるが、そのような「言語の世界観（というより様々な言語機能や特性の総体から浮かび上がる流儀）」を無視したプログラミングをするのでない限り、どんな言語であってもそれを学ぶことによって新しい世界、プログラミング観などが得られるように思う。（その世界観に共感するかどうかはまた別の話だが）
PythonとRubyであっても、構文の自由度、Rubyのオブジェクト指向への忠実さに対比してPythonのdunder methodによるProtocol重視、Rubyのブロックによるメタプログラミングなどなどの見どころは色々とあって、それが言語の基本思想や歴史、使われるドメインやエコシステム、ユーザコミュニティなどとどう関連しているのか、など「プログラミングについての考えが豊かになる」点はいくらでもあると思う。
もちろん程度問題はあって、例えばC++とJavaとRubyを知っている人が次にPythonを試すよりAPLを試す方が世界が広がる（あるいはちょっと頭が柔らかくなる？）というのはあるだろう。とりあえず長期的にはAPL、Forth、Prologなどにも触れておくのは価値のあることな気もする（前述の通り「気がする」だけかもしれない）。また、これらは既知の言語との離れ具合が極端なので一週間くらい試すだけでも強烈な世界観の変化があり得る。RubyとPythonなどの違いはある程度深掘りしないと「この言語アホな仕様になってるな」程度で終わってしまうことも多く、プログラミング観を広げるような何かを得るためには逆説的により多くの時間的・精神的投資が必要かもしれない。
しかしどんな言語でも、その言語固有の特徴と歴史、ユースケースやコミュニティがあって、その世界に触れることが「not worth knowing」だとは思えない。
なのでPerlisの箴言は以下のように改変したい：
A language that doesn't affect the way you think about programming, is a language you don't know enough about.
