LISPの半ページ評価器と初期Smalltalkの1ページ評価器

※本稿は資料与えて ChatGPT に作成させたものです。

アラン・ケイは、LISP 1.5 のプログラマー向けマニュアルに掲載されたLISP自身で記述された評価器を「プログラミングのマクスウェル方程式」と呼んだ。彼が見たのは、単に短く美しいプログラムというだけではない。言語の意味を説明する形式が、そのまま実行可能な機械にもなるという、古典数学とコンピューター固有の数学の接点だった。本稿では、マクスウェル方程式の魅力から始め、LISPの誕生、LISP 1.5とFEXPR、そして、ケイ自身の数学観を経て、評価の仕事をオブジェクトへ分配する初期Smalltalkのインタープリタ設計「One Pager」へ至った道筋をたどる。

1. マクスウェル方程式――四つの式が、光の正体を明かす

マクスウェル方程式は、物理を学んでいないプログラマーには、ベクトル解析の記号が並んだ近寄りがたい壁に見えるかもしれない。しかし、その面白さを知るだけなら計算は要らない。四つの式を、電荷、電流、電場、磁場の関係を表す四つのルールとして読めばよい。

第一に、電荷は、電場の湧き出しや吸い込みと関係する。電場を線で表すと、その線は正の電荷から外へ広がり、負の電荷へ集まる。

第二に、磁場を線で表すと、その線には始点や終点がない。磁石を割っても北極だけ、南極だけにはならず、それぞれが北極と南極をもつ二つの小さな磁石になる。

第三に、時間とともに変化する磁場は、その周囲に渦状の電場を生じさせる。磁石をコイルへ出し入れすると電圧が生じ、回路が閉じていれば電流が流れる。これが電磁誘導である。

第四に、電流と、時間とともに変化する電場は、その周囲に磁場を生じさせる。

第三と第四の法則を組み合わせると、電場と磁場の変化が波として空間を伝わりうることが分かる。方程式から計算されるその波の速度は、当時すでに測定されていた光速と一致した。1

このことから、光は電気や磁気と無関係な別種の現象ではなく、電磁場の波として理解できることが示された。

ただし、マクスウェル方程式が、静電気、磁石、電流などを、すべて「電磁波」という一種類の現象へ置き換えたわけではない。電磁波は、四つの法則を組み合わせることで導かれる重要な帰結の一つである。

マクスウェル方程式の価値は、単に式が短いことにはない。

  • 一見ばらばらな現象を、共通の理論の中へまとめる
  • すでに知られていた現象を説明する
  • それまで知られていなかった現象の存在を予測する
  • 複数の式が組み合わさり、一つの整合的な世界像を作る

ここでいう「圧縮」とは、多くの現象を一種類の現象へ還元することではない。多様な現象の関係を、人間が見通せる少数の規則として表すことである。

マクスウェル方程式は、数式が単なる計算の道具ではなく、自然界の異なる現象を結びつけ、それまで見えていなかった関係を明らかにしうることを示した。

アラン・ケイがLISPの評価器に見いだしたのも、この種類の圧縮だった。もちろん、物理現象とプログラムが同じ仕組みで動くという意味ではない。少数の互いに結びついた規則が、多様な現象や振る舞いを見通せる形で記述するという、形式上の共通点である。

2. 「数を計算する機械」から「記号を動かす機械」へ

1950年代のコンピューターは、巨大で高価な数値計算機だった。プログラムやデータはパンチカードなどから投入され、結果は後で受け取る。メモリーは小さく、機械ごとの差も大きい。プログラミング言語そのものが、まだ発明の途上にあった。

FORTRANは、科学技術計算の数式を機械語へ変換することに成功した。しかし、初期の人工知能研究者が扱いたかったのは数値だけではない。

  • 論理式
  • 定理
  • 単語と文
  • 木構造
  • 探索手順
  • プログラムそのもの

こうした記号構造を計算の対象にするため、ジョン・マッカーシーは1950年代後半にLISPを構想した。名称は LISt Processor に由来する。プロジェクトの開始は1958年秋であり、その基本的な考え方は1960年の論文で提示された。2

LISPの中心的なデータ構造は、二つの参照を持つコンスセルである。リストは、先頭と残りに分けられる。

(car '(A B C))  ; A
(cdr '(A B C))  ; (B C)

二つの要素を組み合わせれば、新しいリストを作れる。

(cons 'A '(B C)) ; (A B C)

決定的なのは、プログラムも同じリスト構造で表されることだ。

(+ 3 4)

これは加算を指示する式であると同時に、記号 + と数値 3、4 からなるデータでもある。したがってプログラムは、別のプログラムから分解、変形、生成できる。

「コードとデータが同じ材料でできている」という性質は、後のマクロやメタプログラミングだけでなく、言語が自分自身について語るための土台になった。

3. 紙上の定義が、インタープリタになった

マッカーシーは、LISPの意味を説明するために eval を定義した。もともとは、S式がどのように値へ変換されるかを示す数学的・記述的な関数だった。

ところがスティーブ・ラッセルは、この定義を機械語で実装すればLISPインタープリタになると見抜いた。マッカーシーは当初その考えに懐疑的だったが、ラッセルはIBM 704上で実際に動かした。3

ケイは、LISPの偉大さの中心はマッカーシーの「アイデア」にあるとしながらも、ラッセルのようにアイデアを現実の機械へ橋渡しした人々を明確に評価している。同じ関係はSmalltalkでも、ケイの設計と、ダン・インガルスによる実装の間に見られる。4

ここで、LISP史を貫く循環が生まれる。

  1. LISPプログラムはリストとして表せる
  2. リストはLISPプログラムで操作できる
  3. LISPプログラムの意味は eval で定義できる
  4. eval 自身をLISPで記述できる
  5. その評価器へLISPプログラムを渡せば、LISPが動く

言語の定義が、言語を実行する機械にもなる。

一般的な仕様書は、実装者が別の仕組みに翻訳しなければ動かない。LISPの評価器では、その距離が極端に短くなった。意味論、プログラム、実装の設計図が、ほぼ同じ形を取ったのである。

4. LISP 1.5――研究アイデアが生きたシステムになる

1962年に刊行された LISP 1.5 Programmer’s Manual は、John McCarthy、Paul W. Abrahams、Daniel J. Edwards、Timothy P. Hart、Michael I. Levinの共著である。5

「1.5」という番号は、現代的な小規模アップデートの印象とは異なる。構想されたLISP 2へ向かう途中にありながら、実際に利用できるシステムとして育った版だった。

LISP 1.5には、（1962年の初版マニュアルの時点では）マクロこそまだ無かったが、後のLisp文化を形作る要素がすでにそろっている。 [追記：id:g000001 さんにコメント欄でご指摘いただいた通り、マクロについての記述が正確ではありませんでした。LISP 1.5も1963年にはコンパイラでマクロをサポートしていたそうです。なお、マクロは（後述する） FEXPR を置き換えるために導入され、両者は長らく併存したのち、ついにCommon Lispで FEXPR は淘汰されたのだとのこと。]

  • S式によるプログラム表現
  • 再帰的なリスト処理
  • 条件式 COND
  • 動的な名前の束縛
  • ガベージコレクション
  • インタープリタとコンパイラ
  • 属性リスト
  • EXPR、FEXPR、SUBR、FSUBR
  • Lisp自身で記述された eval と apply

マニュアル13ページ下部には、evalquote、apply、eval、そして補助関数 evcon、evlis の定義が掲載されている。6

役割を現代的な言葉で単純化すれば、次のようになる。

eval  : 式を環境の中で評価する
apply : 関数を引数と環境に適用する

eval は式の形を調べる。

  • 記号なら環境から値を探す
  • 引用なら式をそのまま返す
  • 条件式なら条件を順に調べる
  • 関数適用なら引数を処理して apply へ渡す

apply は関数の形を調べる。

  • 基本関数なら対応する処理を行う
  • LAMBDA なら仮引数と実引数を結び、新しい環境で本体を eval する
  • 再帰的な定義なら、関数名を環境へ加えて適用する

eval が apply を呼び、apply が再び eval を呼ぶ。この小さな循環へ、変数参照、関数適用、条件分岐、再帰、環境が収まる。

もちろん、実際のLISP 1.5処理系全体が半ページだったわけではない。入出力、メモリー管理、機械語ルーチン、コンパイラなど、多くの実装が必要だった。それでも、言語の意味の中心を、人間が一度に見渡せる大きさへ収めたことは画期的だった。

5. 「ソフトウェア（もしくはプログラミング）におけるマクスウェル方程式」

アラン・ケイは大学院時代、LISP 1.5マニュアル13ページ下部のコードが「Lispで書かれたLisp」であることを理解し、大きな衝撃を受けた。

2004年のACM Queue のインタビューで、彼はその半ページを “Maxwell’s Equations of Software!” と表現している。7 一方、後年のQuora回答では「たしか “Maxwell’s Equations of programming” と言ったと思う」と記憶を留保しつつ、この比喩がLispの登場した1950年代末から1960年代初頭にはよく当てはまると説明した。そこで強調されているのは、当時行われていた種類のプログラミングを包含する強力なモデルを “one eyeful”――一目で見渡せる大きさ――で示したことだった。8

別のQuora回答でケイは、これをさらに “unlimited programming in an eyeful”（「ひと目で見渡せる、万能のプログラミング」）と言い換えている。彼が「Lispは史上最高の単一のプログラミング言語設計だ」と称賛した理由は、括弧を使う外見や特定の実用性能ではない。マッカーシーが、ほぼあらゆるプログラミング言語を表現できる一般性を備えながら、その本質を小さなメタ記述として表現したことにあった。4[^kay-greatest]

したがって、後のケイの意図を汲むなら “programming” だが、“Software” でも意味は通りそうだ。無理にどちらか一方を唯一の定型句として固定する必要はないだろう。比喩の中心は、当時のプログラミングを広く包含するモデルを、人間が一度に把握でき、しかも実行へ移せる形に圧縮した点にある。

この比喩は、次の三点でよく働く。

①多数の機能が、一つの原理として見える

関数呼び出し、変数探索、条件分岐、再帰は、利用者から見ると別々の機能である。eval と apply の相互作用として見ると、すべて「式を環境の中で意味へ変える」という一つの過程になる。

②記述が予測と生成の力を持つ

評価規則を少し変えれば、異なる言語が生まれる。環境の扱い、引数評価の時期、関数の表現を変更すると、新しい計算モデルを実験できる。評価器は既存のLISPを説明するだけでなく、LISPに似た別の世界を作るための母型にもなる。

③全体を思考の対象にできる

ケイは、人間の思考を制約する認知負荷に繰り返し言及している。いちどに注意を向けられる対象が少ないなら、その少数の記号へ、より大きな意味を担わせなければならない。彼の標語 “Point of view is worth 80 IQ points” は、新しい表現形式が、以前は難しすぎた思考を可能にするという意味である。4[^kay-greatest]

LISPの半ページの評価器は、処理系の核心を一度に視野へ収める。そのうえで手で追跡し、変更し、別の言語を考えられる。ケイが称賛したのはLISPの完成度だけではなく、LISPを理解した者が、ただちにLISPよりよい言語や、よりよいメタ記述を構想できるようになる視点だった。

6. ケイの数学観――形式は、動いてこそ試される

ケイは数学的厳密さを拒んでいたのではない。むしろ、プログラミングシステムの問題は新しい種類の数学的問題だと考えていた。

1998年のメーリングリスト投稿で、彼は古典的な数学を CM（Classical Mathematics）、コンピューター固有の数学を CptrM（Computer Mathematics） と呼び分けている。そこでマッカーシーの自己記述的LISP評価器を、両者の世界にまたがる美しい数学的対象として挙げた。9

この区別は、「数式かコードか」という表面上の違いではない。

古典数学では、公理と定義を置き、命題を導く。形式は主として静的な対象であり、その妥当性は証明や人間の読解によって検討される。

コンピューター上の形式には、それに加えて次の性質がある。

  • 入力を与えて実行できる
  • 状態が時間とともに変化する
  • 他の仕組みと相互作用する
  • 途中経過を観察できる
  • 想定外の例を試し、欠陥を発見できる
  • 形式自身を部品として別の形式を構築できる

プログラムは記述であると同時に、実験装置でもある。

ケイは、古典数学の形式をコンピューターへ外から被せるだけでは、この媒体の特徴を十分に捉えられないと考えた。彼が問題視したのは数学そのものではなく、形式が巨大で理解しにくく、しかも実行不能なまま正しさを保証したことになる状況だった。

アルゴリズムを完全に記述する形式が、元のプログラムより簡潔で明晰なら、なぜその形式を直接実行しないのか。速度が足りなければ、最適化を機械に任せればよい。ケイの批判は、この問いに集約できる。

推論機械であり、考えるための物体でもある

ケイがニクラウス・ヴィルトによるEulerの形式化を高く評価した理由も同じである。ヴィルトの仕事では、小さな状態空間言語、そのコンパイラ、バイトコードインタープリタが、数ページの記号へまとめられていた。10

それは言語を説明する仕様であるだけでなく、実行の仕組みであり、人間が全体を眺めて考えられる人工物でもあった。ケイは、形式と機械がこのように近接した仕事を好んだ。

最低層から最高層までの「急勾配」

ケイはLISPについて、単純な機械構造から高水準の表現までの「傾斜」が、かつてないほど急だったとも述べている。4[^kay-greatest] これは、抽象度の高い表現がハードウェアから隔絶しているという意味ではない。少数の基礎機構から、自己記述や言語構築へ一気に上れるという意味である。

この急勾配が、LISPを単なる一言語ではなく、言語について考えるための足場にした。小さな機械的核と大きな表現力が同じ系の中で接続されているため、抽象的なアイデアを実装へ降ろし、実装上の現象を再びモデルとして考えられる。

LISP評価器に残った一つの不足

ケイは同じ1998年の投稿で、マッカーシーの評価器の「唯一の本当の欠点」は、純粋関数的な性格がコンピューターの強力な状態空間を反映していないことだと述べた。9[^kay-formalizing]

なお、この批判は評価器という形式の性格についてのものであり、マッカーシー個人が状態を軽視したという意味ではない。ケイは別の場所で、状態と時間の扱いにおけるマッカーシーの先駆性——変化の履歴を保持し、「擬似時間」で索引づけて関数的・論理的な推論と両立させるsituation calculus——をむしろ高く評価し、PARCでも可能な範囲で取り込もうとしたと述べている。11

ここでいう状態は、単なる代入文の有無ではない。

  • ユーザーの操作を待つ
  • オブジェクトが過去を記憶する
  • 画面上の対象が継続的に変化する
  • 一つの操作が後の振る舞いを変える
  • 複数の主体がメッセージを交換する

ケイが構想したパーソナルコンピューターは、一度入力して答えを得る関数計算機ではなく、人間と長時間対話する動的な媒体だった。そのため、状態と時間は排除すべき不純物ではなく、正面から扱うべき計算の構成要素だった。

課題は、関数的な明晰さを捨てずに、状態を含む実行モデルを小さく記述することだった。実際ケイは同じ投稿で、Smalltalk-72の黎明期に自分が試みたのは、マッカーシーの評価器に劣らず小さく明晰でありながら、状態空間を備え、読みやすい構文を許すインタープリタ定義だったと振り返っている。9[^kay-formalizing] この状態の軸に答える部品が、後述するメッセンジャーである。

ただし、ケイのLISP批判にはもう一つ、これとは独立した軸があった。次章で見るFEXPRが関わるのは、そちらの軸である。

7. FEXPR――受け手が引数の読み方を決める

LISP 1.5には、通常の関数とは異なる評価規則を持つ FEXPR があった。これは古いLISPにおけるマクロの前身のような機能で、特殊形式を定義することができた。

通常の関数（ FEXPR に対して EXPR ）では、引数が先に評価され、得られた値が関数へ渡される。

(f (+ 1 2))

この場合、f が通常の関数なら、まず (+ 1 2) が評価され、値 3 が渡る。

FEXPRには、引数を構成する式が未評価のまま渡される。FEXPR側は、その式をどう扱うか自分で選べる。

  • 評価しない
  • 一度だけ評価する
  • 一部だけ評価する
  • 条件を見て必要な式だけ評価する
  • 別の環境で評価する

これは利用者定義の特殊形式、ことに制御構造を作るうえで強力だった。たとえば条件分岐では、真の場合と偽の場合の両方を先に評価してはならない。未評価の式を受け取れれば、条件を調べた後で必要な側だけを実行できる。

LISP 1.5では、LISPで定義された通常関数を EXPR、未評価引数を受け取る関数を FEXPR と分類した。機械語で実装された対応物は SUBR と FSUBR である。12

FEXPRが示したのは、呼び出し側や中央評価器だけでなく、受け手も評価の時期へ関与できるという可能性だった。

ただし、自由の範囲は中央の eval が決めている。評価器が関数の種類を調べ、「FEXPRなら未評価で渡す」と分岐する。受け手の自由は、評価器が用意した特別な入口から与えられていた。

ケイの不満は、まさにこの構図に関わる。The Early History of Smalltalk での回想によれば、純粋なLISPは関数に基づくとされながら、lambda式、quote、condといった最重要の構成要素は関数ではない「特殊形式」という例外だった。他の研究者の工夫で一部を関数に還元できても、宝石に残った傷は消えない。一方、実用言語の側には、引数を評価するEXPRと評価しないFEXPRが最初からある。それならなぜ関数型言語と名乗るのか。いっそすべてをFEXPRに基づかせ、必要な評価は受け手側で強制すればよいのではないか。 この問いに良い答えは得られなかったが、Smalltalkを発明する際に大いに役立った、とケイは述べている。13

副作用や状態の扱い（前章）とは別の、この統一性の軸が、FEXPRの入口を評価機構全体へ広げるという発想の出所である。

8. 中央の eval を、オブジェクト社会へ分配する

オブジェクト指向言語を考えるケイにとって、LISPの評価器は美しい一方、意味の判断が中央へ集まりすぎていた。

eval は、式を見て次のような判断を行う。

  • 変数か、リテラルか
  • 引用か、条件式か
  • 引数を先に評価するか
  • どの環境で評価するか
  • 関数をどう適用するか

新しい評価方法を追加するには、この中央機構との関係を決めなければならない。

ケイは逆の構造を考えた。

  • 数は、+ の意味を自分で決める
  • 真偽値は、続く式を評価するか自分で決める
  • 変数は、値の参照や代入をメッセージとして処理する
  • 引数受信用のオブジェクトは、次の式を評価するか否かを決める
  • 制御構造は、実行コンテキストへ保護された方法で働きかける
  • クラスのコードは、受け取れるメッセージの形を記述する

添付資料の元となった The Early History of Smalltalk の付録で、ケイはこの考えを、eval を個々のオブジェクトと、言語が拡張される動的過程へ distribute することだと説明している。14

One Pagerの短さは、処理を消した結果ではない。中央評価器が担っていた役割を、オブジェクト、クラスコード、実行コンテキストへ移した結果である。

9. 1972年の賭け――最強の言語を1ページで

1972年、Xerox PARCでケイ、ダン・インガルス、テッド・ケーラーが、プログラミング言語の力について議論していた。ケイは、世界で最も強力な言語を1ページのコードで定義できると主張した。反応は当然、「ならばやってみろ」だった。15

ケイにはLISPの先例があった。関数的な言語世界を半ページほどで示せるなら、状態を持つオブジェクト指向の世界も、同程度の明晰さで定義できるはずだ。

彼が目指した条件は、少なくとも三つあった。

  1. マッカーシーの評価器のように小さく、全体を考えられる
  2. 状態空間を持つ
  3. LISPより自然に読める構文を許す

ケイは続く2週間ほど、始業前の早朝に設計を進め、出勤してきたインガルスらが案を批評する、という作業を繰り返した。最初の案には欠陥があったが、そのうち手作業で追跡可能なインタープリタ設計へ到達した。これがOne Pagerである。

ケイはこの話はここで終わりと思っていたが、その後数日で、インガルスが必要なスキャナやリスト処理などを補い、BASICでNOVA上に実装してしまい、ケイを驚かせたという。3+4 の評価は非常に遅かったが、結果は 7 になった。15[^earlyst-bet]

One Pagerはケイによるインタープリタ設計であり、それを最初に実機上の処理系として動かしたのはインガルスだった。マッカーシーの eval がラッセルにより実装されたエピソードを彷彿とさせるこの処理系誕生と続く改良が、後にSmalltalk-72と呼ばれるシステムへ育っていく。

10. One Pagerの発想――手紙ではなく、手紙の場所を知らせる

現代的なオブジェクト指向言語では、メッセージ送信を次のように考えることが多い。

  1. 引数を評価する
  2. セレクタに対応するメソッドを探す
  3. メソッドを実行する
  4. 戻り値を返す

One Pagerのモデルは異なる。

ケイは、送信を「郵便屋が手紙を届けること」ではなく、手紙がどこにあるかを受け手へ通知することになぞらえた。14[^earlyst-appendix]

受け手は、送り手が保持しているメッセージ列の位置へアクセスし、必要な分だけ読み進める。

  • 次のトークンが特定の記号か調べる
  • 次の部分式を送り手の環境で評価する
  • 次の部分式を未評価のまま受け取る
  • 不要な部分を飛ばす
  • 独自の文法として解釈する
  • 結果を送り手へ返す

送信時点でメッセージの構造と評価順序が完全に確定するのではない。受信側が読み進める過程で意味が形になる。

11. 3+4 ＝「3へ +4 を送る」は単なる比喩ではない

One Pagerでは、式の最初の要素を評価して受け手とし、残りをメッセージとして扱う。

receiver | message
    3    | + 4

+ は、インタープリタが生まれつき知っている固定演算子である必要はない。整数クラスが受け取れば整数加算として、行列が受け取れば行列加算として、文字列が受け取れば連結として解釈できる。

さらに受け手は、4 をいつ、どの範囲まで、どの環境で評価するかに関与する。

この設計では、構文解析、引数評価、メソッド選択が完全に分離した工程ではない。それらは「受け手がメッセージを読み取る」という一つのプロトコルへ組み込まれている。

12. 「メッセンジャー」――状態と制御を対象化するオブジェクト

One Pagerの中心にあるのは、メッセンジャー（MESSENGER）と呼ばれる実行コンテキストである。概略として、次の情報を持つ。

SNDR/SENDER  送り手のメッセンジャー
GLOBAL       大域環境
SELF         現在の受け手
PC           メッセージ中の現在位置
MSG/MESSAGE  現在解釈しているメッセージ列
RTN/RETURN   評価終了後の復帰先

この表記はOne Pagerの擬似コード自体でも用いられている。RTNには、このメッセンジャーの評価が終わった後に実行される継続のラベルが入る。図の APPLY はその一つで、擬似コードにはほかに条件実行からの復帰用 FROMTRUE などがある。14[^earlyst-appendix]

現代的に言えば、環境、スタックフレーム、継続、プログラムカウンタ、メッセージカーソルを組み合わせたような存在である。

重要なのは、実行状態が処理系内部の見えない機構だけに閉じ込められず、オブジェクトとしてモデル化されていることだ。制御構造や引数受信オブジェクトは、保護された方法でメッセンジャーへ働きかけられる。また、メッセンジャーとの協働により、Smalltalk-72 環境には、すでにインタラクティブな「検査機能」として強力なデバッグ機能が備わっていた。16

これにより、LISPの eval 内部に置かれていた環境操作や制御の一部を、オブジェクト世界の側へ移せる。

評価の二場面

添付された二つの図は、3+4 の評価で実行コンテキストがどのように切り替わるかを示している。両図にある e（Beforeでは左上に、Duringでは下段のメッセンジャーの左脇に置かれている）は、One Pagerの冒頭で「現在のメッセンジャーオブジェクトに束縛される環境（the environment）」と定義されているレジスタである。14[^earlyst-appendix] Beforeでは送り手のメッセンジャーを、Duringでは新しく作られた受け手側のメッセンジャーを指しており、活性コンテキストの移動を表す。なお原図では図中のこのラベルは判別しがたいため、e の文字は読み解きの補助として補ってある。

Before――送り手が式の途中にいる

<sodipodi:namedview id="namedview43" pagecolor="#ffffff" bordercolor="#000000" borderopacity="0.25" inkscape:showpageshadow="2" inkscape:pageopacity="0.0" inkscape:pagecheckerboard="0" inkscape:deskcolor="#d1d1d1" inkscape:zoom="1.0630952" inkscape:cx="169.78723" inkscape:cy="261.03024" inkscape:window-width="1920" inkscape:window-height="1137" inkscape:window-x="-8" inkscape:window-y="-8" inkscape:window-maximized="1" inkscape:current-layer="svg43" showgrid="false" /> e CLASS MESSENGER SENDER GLOBAL SELF PC MSG RTN APPLY CLASS INT MAG 3 CLASS SYM VAL + CLASS INT MAG 4
3+4 評価開始時のメッセンジャー

送り手側メッセンジャーの MSG は、3、+、4 を含むコード列を指す。列の先頭側にある黒点は、すでに消化されたトークンを表す。評価はメソッドの途中から始まっているのである。PCが 3 を指しているとき、eval はそれを整数オブジェクトとして評価する。得られた整数 3 が、残りのメッセージを受け取る SELF になる。

During――整数クラスのコードがメッセージを読む

<sodipodi:namedview id="namedview104" pagecolor="#ffffff" bordercolor="#000000" borderopacity="0.25" inkscape:showpageshadow="2" inkscape:pageopacity="0.0" inkscape:pagecheckerboard="0" inkscape:deskcolor="#d1d1d1" showgrid="false" inkscape:zoom="1.0383721" inkscape:cx="222.94513" inkscape:cy="466.59574" inkscape:window-width="1920" inkscape:window-height="1137" inkscape:window-x="-8" inkscape:window-y="-8" inkscape:window-maximized="1" inkscape:current-layer="svg104" /> CLASS MESSENGER SENDER GLOBAL SELF PC MSG RTN APPLY CLASS INT MAG 3 CLASS SYM VAL + CLASS INT MAG 4 e CLASS MESSENGER SENDER GLOBAL SELF PC MSG RTN APPLY CLASS CLS NAME INT CODE CLASS SYM VAL ¤ CLASS SYM VAL + CLASS SYM VAL »
整数クラスのコードへ制御が移った状態

新しいメッセンジャーでは SELF が整数 3 となり、MSG は整数クラスのコードを指す。一方、読み取る対象である + 4 は送り手側のメッセージ列に残っている。図の点線が示すとおり、この時点で送り手側のPCは、消費済みの 3 の次のトークンである + を指す。Beforeで 3 を指していたPCは、その消費とともに一つ進んでいるのである。

受け手側コードの ¤ のような補助オブジェクトは、送り手側のPCを手がかりにメッセージ列を調べ、受信の進行に応じて送り手のPCを動かす。ケイ自身、こうした補助オブジェクトは送り手のプログラムカウンタを「責任を持って（responsibly）」動かさねばならないと注記している。14[^earlyst-appendix] 実行主体は受け手へ移っているが、受信対象は送り手の文脈に保持される。この二つのコンテキストの協調が、遅延されたメッセージ受信を可能にする。

13. 小さな受信プロトコル

初期設計では、メッセージ列を読むための少数のオブジェクトまたはメタ操作が使われた。14[^earlyst-appendix]

記号
(Kay) 		記号
(ST-72) 		記号
ASCII 		名称 役割
¤ ∢ % eyeball 次のトークンが指定されたリテラルか調べる
: : : evl-bind 次の部分を評価し、結果を束縛する
⦂ ⦂ ; unval-bind 次の部分を未評価のまま束縛する
^ ⇑ ! send-back 値を送り手へ返す
' ☞ " quote メタ解釈を抑止する

Duringの図で整数クラスのコード列が ¤ + » で始まっていたことを思い出そう。»（Smalltalk-72 では ⇒ ）は、ケイの付録で「最初の『実際の』実装時に定義された」記号群（to、ISNEW、=、»、.）の一つで、then と名づけられた条件実行の記号である。受け手が真なら、メッセージの次の部分を評価してそこで抜け、偽なら次の部分を読み飛ばして評価を続ける。14[^earlyst-appendix] 整数クラスのコードは「次のトークンが + なら、加算の処理へ進む」という受信パターンを、¤ と » の連なりで表現している。同じ形は、Smalltalk-72で書かれたclass integerによるfactorialの定義など、初期のコード例にも一貫して現れる。17

: と ⦂ の対比に注目すると、FEXPRとの関係が見える。

LISP 1.5では、関数全体を EXPR または FEXPR と分類し、引数を評価して渡すか、未評価で渡すかを決める。

One Pagerでは、受信コードの中で、メッセージの各部分について選べる。

  • 次のトークンはリテラルとして照合する
  • 次トークン以降を式として送信側の文脈で評価して束縛する
  • 次のトークンは未評価のまま束縛する

評価方法の選択が、関数単位からメッセージ文法の部品単位へ細分化された。

なお、現存するOne Pagerは1972年の原稿そのものではなく、ケイが後年、失われた設計を記憶から再構成したものである。ケイ自身も、手作業でいくつかの例を評価して動くように見えるが、バグがあるかもしれないと記している。14[^earlyst-appendix]

14. ペアオブジェクトが、自分の構文を読む

c がLISPのコンスセルに似たペアオブジェクトだとする。

c hd ← 3 + 4

受信側のコードは、概念的に次の順序でメッセージを読む。

  1. 次のトークンは hd か
  2. 続くトークンは代入記号 ← か
  3. 残りの式 3+4 を送り手の環境で評価する
  4. 結果を内部変数 h へ格納する
  5. その値を送り手へ返す

LISP風に書けば、おおよそ次に相当する。18

(rplaca c (plus 3 4))

ただし意味の置き場所が異なる。

LISPでは、評価器が式の構造を読み、RPLACA を適用する。One Pagerでは、c のクラスコードが hd ← ... という受信パターンを認識し、必要な部分の評価を依頼する。

構文は独立したパーサーだけが所有するのではなく、受け手の振る舞いの一部になる。

15. FEXPRからOne Pagerへ――自由の粒度を細かくする

三つのモデルを並べると、発想の移動が分かりやすい。

通常のLISP関数

評価器が引数を評価する
        ↓
関数が値を受け取る

FEXPR

評価器が関数の種類を判定する
        ↓
未評価の引数列を渡す
        ↓
FEXPRが必要に応じて評価する

One Pager

受け手へメッセージの所在を知らせる
        ↓
受け手側コードが列を読み進める
        ↓
部分ごとに照合・評価・未評価束縛・スキップを選ぶ

ケイがFEXPRから得たのは、単に「引数を遅延評価できる」という機能ではない。受け手が、自分へ届くプログラム断片の意味形成へ参加できるという考えだった。

不足していたのは、その能力が中央評価器の特別分岐として与えられていたことだ。One Pagerは、FEXPR的な自由を通常のメッセージ受信へ一般化しようとした。

こうして、ケイの二つのLISP批判は、One Pagerの別々の部品で回収される。特殊形式という例外への不満（統一性の軸）には受信プロトコルが、純粋関数性が状態空間を映さないという不満（状態の軸）にはメッセンジャーが、それぞれ答えているのである。

16. オブジェクトは、状態を理解可能な大きさへ区切る

ケイの古典数学批判とオブジェクト指向は、ここで接続する。

巨大なプログラムの全状態を一つの形式へ展開すると、記述は急速に大きくなる。形式的であっても、人間が全ケースを理解できなければ、その価値は限定される。

オブジェクトは、状態と、その状態を扱うコードを局所化する。

  • 内部状態へ直接触れさせない
  • 外部との関係をメッセージへ限定する
  • 誤りや変更の影響範囲を狭める
  • 各部分を、人間が考えられる大きさに保つ

これは単なるコード整理術ではない。複雑な動的システムについて推論するための構造でもある。

One Pagerでは、この原則が言語処理系自身へ適用された。評価器を巨大な中央機構として完成させる代わりに、評価、構文、制御、状態の役割を、相互作用する対象へ分ける。

ケイのいうCptrMは、古典数学を捨てた無形式なプログラミングではない。実行でき、人間が追跡でき、修正の影響を局所的に考えられる形式を作ることだった。

17. 後のSmalltalkとは異なる、受信言語としてのSmalltalk-72

One Pagerから始まるSmalltalk-72は、Smalltalk-76やSmalltalk-80と同じ実行モデルではない。

後のSmalltalkでは一般に、構文が解析され、引数が評価され、セレクタに対応するメソッドがクラス階層から検索される。

Smalltalk-72では、クラスコードがメッセージ列をパターンマッチし、必要な部分を能動的に読み取る。クラスはメソッド辞書というより、小さな受信言語を持つインタープリタに近い。

この方式は柔軟だが、実行効率、理解しやすさ、ツール支援、最適化の面で重い。Smalltalkの設計はその後ダン・インガルス主導で大胆に整理され、Smalltalk-76では、今日知られるメソッド辞書とバイトコードインタープリタに近い構造へ移っていった。19

One Pagerの価値は、現在のオブジェクト指向言語を最小化したことではない。「受け手はメッセージの意味をどこまで決められるか」という問いを、動く処理系の形で試したことにある。

18. 半ページと1ページ――継承と反転

LISP 1.5の評価器とOne Pagerには、明確な継承関係がある。

ケイがLISPから受け継いだのは、次の考えだった。

  • 言語の意味を小さな評価器へ圧縮できる
  • コードを通常のデータとして扱える
  • 評価規則自体をプログラムから操作できる
  • 実行環境を明示的な構造として考えられる
  • 定義は実装から切り離された説明にとどまらず、実行可能になり得る

そのうえで、二つの点を反転させた。

第一に、純粋関数的な世界へ状態を導入した。

第二に、意味を決める場所を中央の eval からメッセージの受け手へ移した。

LISP:
    evalが式を読み、評価方法を決める

初期Smalltalk:
    受け手がメッセージを読み、受信方法を決める

One PagerはLISP評価器の否定ではない。その美点を、別の計算世界へ移植する試みだった。

19. 結び――コンピューター自身を数学の媒体にする

マクスウェル方程式は、多様な物理現象を少数の法則へ統一した。LISPの自己評価器は、多様な言語機能を eval と apply の相互作用へまとめた。

ケイが特に高く評価したのは、その形式が実行可能だったことである。LISP評価器は、言語について説明する記号列であると同時に、実装すればその言語を動かす機械になる。人間は全体を読み、機械は同じ構造を実行する。

この性質は、ケイがコンピューターに見た新しい数学の条件を満たしていた。

One Pagerは、そこへ状態と相互作用を加える試みだった。実行コンテキストをメッセンジャーとして対象化し、FEXPRが示した受け手側の評価能力をメッセージ受信へ拡張し、中央評価器の仕事をオブジェクトへ分配した。

その設計は完成されたSmalltalkの最終形ではない。再構成された記述には未確定な部分があり、後のSmalltalkは異なる実行モデルへ進んだ。それでも、One Pagerは思想を紙上にとどめなかった。インガルスの実装によって動き、Smalltalk-72という実験環境の出発点になった。

ここに、ケイが評価した仕事の基準が表れている。

形式的に美しいこと。人間が全体を考えられること。そして、機械の上で本当に動くこと。

LISP 1.5の半ページからSmalltalkの1ページへ続く道は、プログラミング言語の影響関係だけを示すものではない。それは、コンピューターを古典数学の適用対象として見るだけでなく、状態、時間、相互作用を含む新しい数学を行うための媒体として捉える試みの歴史でもある。

  1. James Clerk Maxwell, “A Dynamical Theory of the Electromagnetic Field,” Philosophical Transactions of the Royal Society of London, Vol. 155, 1865, pp. 459–512. Royal Society Publishing ／ IEEE History Center, “Maxwell’s Equations, 1860–1871,” Engineering and Technology History Wiki. ETHW。マクスウェルによる電磁気学の統一と電磁波の導出については両者を参照。↩
  2. John McCarthy, “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I,” Communications of the ACM, Vol. 3, No. 4, 1960, pp. 184–195. Stanford PDF。LISPの初期構想と記号式、再帰関数については本論文を参照。↩
  3. John McCarthy, “History of LISP,” in Richard L. Wexelblat (ed.), History of Programming Languages, Academic Press, 1981, pp. 173–185. Stanford version ／ Paul Graham, Hackers and Painters: Big Ideas from the Computer Age, O’Reilly Media, 2004, p. 185。eval の実装をスティーブ・ラッセルが提案・実現した経緯は、前者に収められたマッカーシーの回想に記されている。マッカーシーが当初「君は理論と実践を混同している。この eval は読むためのものであって、計算するためのものではない」と懐疑的だった逸話は、後者に収録されたマッカーシー自身の発言による。↩
  4. Alan Kay, “What did Alan Kay mean by, ‘Lisp is the greatest single programming language ever designed’?”, Quora, edited October 30, 2017, together with Kay’s comments on the answer. Quora answer。認知負荷、“Point of view is worth 80 IQ points”、“unlimited programming in an eyeful”、Lispの「急勾配」、マッカーシーとラッセルの役割については、同回答とそのコメント欄での補足を参照。↩
  5. John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, and Michael I. Levin, LISP 1.5 Programmer’s Manual, MIT Press, 1962. Computer History Museum / Software Preservation Group PDF。初版の標題紙には5名が著者として記載されている。↩
  6. 前掲 McCarthy et al., LISP 1.5 Programmer’s Manual。evalquote、apply、eval の定義は印刷ページ13–14付近を参照。↩
  7. Stuart Feldman and Charles Simonyi, “A Conversation with Alan Kay,” ACM Queue, Vol. 2, No. 9, 2004. ACM Queue。ケイによる “Maxwell’s Equations of Software!” という表現と、マニュアル13ページへの言及はこのインタビューにある。↩
  8. Alan Kay, answer to “According to Alan Kay, LISP's metacircular interpreter serves as the ‘Maxwell's equations of software’. What are then the Einstein's field equations of software?”, Quora, edited October 31, 2021. Quora answer。本文中の引用内容はユーザー提供の転記に基づく。↩
  9. Alan C. Kay, “HELP! formalizing OO,” Squeak mailing-list post, April 26, 1998. Mailing-list archive。CM、CptrM、Lisp評価器の純粋関数性、状態空間、形式手法への批判については、この投稿を参照。↩
  10. Niklaus Wirth and Helmut Weber, “EULER: A Generalization of ALGOL, and Its Formal Definition,” Communications of the ACM, Vol. 9, No. 1, 1966, pp. 13–25; No. 2, pp. 89–99. ACM DOI。ケイが言及したEulerの形式化はこの論文（CACM 9巻1号・2号に分載）である。↩
  11. Alan Kay, answer to “Why is functional programming seen as the opposite of OOP rather than an addition to it?”, Quora, 2018年（回答中のCurryOnアムステルダム講演〔2018年7月開催〕および「マッカーシーが60年前に示した」という言及からの推定）. Quora answer 本稿ではユーザー提供の転記も参照。マッカーシーのsituation calculus（situations／fluents）への評価と、PARCでそれを可能な範囲で実装しようとしたという回想はこの回答にある。ケイが同回答内で参照するマッカーシー自身の定式化は McCarthy, “Situations, Actions, and Causal Laws,” Stanford, 1963。時間を計算へ組み込むこの系譜（world-lines、Worlds等）は本稿の射程外とする。↩
  12. 前掲 McCarthy et al., LISP 1.5 Programmer’s Manual。EXPR、FEXPR、SUBR、FSUBR の説明は、特に関数定義と評価器を扱う章を参照。↩
  13. Alan C. Kay, “The Early History of Smalltalk,” ACM SIGPLAN Notices, Vol. 28, No. 3, 1993, pp. 69–95; reprinted from History of Programming Languages II. HTML transcription ／ PDF(Appendix付き) ／ ACM DOI。特殊形式への批判（「宝石に残った傷」）と、「なぜ関数型言語と呼ぶのか。すべてをFEXPRに基づかせ、必要な評価を受け手側で強制してはどうか」という問いについては、同論文本文、1960年代の大学院時代にLISP 1.5と出会う場面の回想を参照。↩
  14. 前掲 Kay, “The Early History of Smalltalk”。eval の分配、受信プロトコル、メッセンジャー、One Pagerの疑似コードは、同論文のAppendix II “Smalltalk Interpreter Design” を参照。本稿では、ユーザー提供の同付録の転記資料も照合に使用した。↩
  15. 前掲 Kay, “The Early History of Smalltalk”。PARCでの賭け、ケイの設計作業、インガルスによるBASIC実装については、本文の “The Birth of Smalltalk” 周辺を参照。↩
  16. Adele Goldberg and Alan Kay (eds.), SMALLTALK-72 Instruction Manual, SSL 76-6, Learning Research Group, Xerox Palo Alto Research Center, March 1976. Bitsavers PDF。本文の「検査機能」は、エラー発生時に評価の文脈を対話的に調べられる Diagnosis Window を指す（のちのSmalltalk環境のインスペクターにあたるものは、Smalltalk-72にはまだない）。同ウィンドウについては同マニュアルを参照。↩
  17. 前掲 Kay, “The Early History of Smalltalk”。»（then）は、Appendix II “Smalltalk Interpreter Design” のFIGURE 11A.2に、to、ISNEW、=、. とともに掲げられている。用例は同論文本文中のSmalltalk-72コード例（class integerとして「内包的に」書かれたfactorialの定義や、“Proposed Smalltalk-72 Syntax” のPairクラスの例）にも見られる。↩
  18. 前掲 Kay, “The Early History of Smalltalk” の付録では (REPLACA C (PLUS 3 4)) と綴られているが、LISP 1.5での関数名は RPLACA である。↩
  19. Daniel H. H. Ingalls, “The Smalltalk-76 Programming System: Design and Implementation,” Proceedings of the 5th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, 1978, pp. 9–16. ACM DOI。Smalltalk-76の構造とバイトコード処理系については同論文を参照。Smalltalkの初期版からの変化については、前掲 Kay, “The Early History of Smalltalk” も参照。↩

Smalltalk の風変わりな FizzBuzz にモノイドを見つけた話 〜Haskell と F# の流儀の違い〜

※本稿は資料与えて ChatGPT に作成させたものです。

FizzBuzz をちょっと変わった「オブジェクト指向」で書く

FizzBuzz は、たいてい条件分岐の練習問題として紹介されます。

「3 で割り切れるなら Fizz、5 で割り切れるなら Buzz、両方なら FizzBuzz、それ以外なら数字を出す」

という、あの問題です。

よくある実装は、次のような形でしょう。

もし n が 15 で割り切れるなら:
    "FizzBuzz" を出力
そうでなく n が 3 で割り切れるなら:
    "Fizz" を出力
そうでなく n が 5 で割り切れるなら:
    "Buzz" を出力
そうでなければ:
    n を出力

これはこれで素直ですが、条件が増えるにつれて分岐が膨らみ、組み合わせ爆発を起こします。

ところで、Smalltalk ではその特性を活かし、この FizzBuzz を次のようにも書くことが可能です。

Integer >> fizz
   ^(self isDivisibleBy: 3) ifTrue: ['Fizz'] ifFalse: ['']

Integer >> buzz
   ^(self isDivisibleBy: 5) ifTrue: ['Buzz'] ifFalse: ['']

(1 to: 100) collect: [:n | n fizz, n buzz ifEmpty: [n]].

このアプローチはメインループから IF 文を排除するだけでなく、FizzBuzz を少し違う角度から見せてくれます。つまり、よくある実装のように「3 の場合」「5 の場合」「15 の場合」を個別に分岐するのではなく、

3 のルールが返す文字列
5 のルールが返す文字列

をそれぞれ作り、それらを連結するだけでこの問題を容易に解決できるという気づきを与えてくれることです。これは、FizzBuzz を「条件分岐の問題」としてではなく、小さな結果を結合する問題として解いていることを意味します。

この記事では、その結合の正体がモノイドであることを確かめ、同じ発想を Haskell と F# に移したときに何が起きるかを見ていきます。

Smalltalk のコードを読む

まず、Integer >> fizz （ Integer クラスに追加された fizz メソッド）のコードから詳しく見てみましょう。

Integer >> fizz
   ^(self isDivisibleBy: 3) ifTrue: ['Fizz'] ifFalse: ['']

これは、整数自身が 3 で割り切れるなら 'Fizz'、そうでなければ空文字列 '' を返します。同様に buzz は、5 で割り切れるなら 'Buzz'、そうでなければ '' を返します。

Integer >> buzz
   ^(self isDivisibleBy: 5) ifTrue: ['Buzz'] ifFalse: ['']

n = 3 なら、n fizz は 'Fizz'、n buzz は '' なので、連結すると 'Fizz' です。n = 5 なら、'' と 'Buzz' で 'Buzz'。n = 15 なら、'Fizz' と 'Buzz' で 'FizzBuzz'。そして 3 でも 5 でも割り切れない n = 7 では、'' と '' の連結なので空文字列です。

その「空文字列になった場合」だけ、最後に ifEmpty: [n] で数字そのものを返します。Smalltalk では引数を持たないメソッド呼び出し（単項メッセージ）は、二項演算を模した二項メッセージに、二項メッセージは一つ以上のキーワード（コロンで終わる ifEmpty: のようなトークン）と、それと対になる引数からなるキーワードメッセージに優先して処理されるルールがあるので、それを明示的にすると、

((n fizz), (n buzz)) ifEmpty: [n]

という順で評価されます（Smalltalk では「,」もメソッドで、この場合、文字列同士を連結して返します）。

つまり、このコードの中心にある発想は次のように言えます。

各ルールは「該当すれば文字列、該当しなければ空文字列」を返す。
それらを全部連結する。
連結結果が空なら、数字を出す。

この「該当しなければ空文字列を返す」というところがミソです。なぜなら、空文字列は文字列連結における「何もしない値」だからです。

参考まで、同じコードを Ruby で書くとこうなります。

class Integer
  def fizz
    self % 3 == 0 ? "Fizz" : ""
  end
  
  def buzz
    self % 5 == 0 ? "Buzz" : ""
  end
end

class String
  def if_empty
    self == "" ? yield : self
  end
end

puts 1.step(100).collect{|n| (n.fizz + n.buzz).if_empty{n}}

文字列連結はモノイドである

ここでモノイドが登場します。モノイドとは、大まかに言えば、次の三つを持つ構造です。

1. 値の集合、または型
2. 値どうしを結合する二項演算（結果が同じ型に戻る＝閉じている）
3. 結合しても相手を一切変えない単位元

さらに、その演算は結合律を満たしている必要があります。

(a • b) • c = a • (b • c)

文字列で考えると、これはとても自然です。文字列には連結があり、空文字列 "" があります（以下、演算記号は Haskell に合わせて <> と書きます）。

"Fizz" <> "Buzz" = "FizzBuzz"
"Fizz" <> ""     = "Fizz"
""     <> "Buzz" = "Buzz"

空文字列は、連結しても相手を変えません。また連結は結合的です。したがって、文字列は次のようなモノイドです。

型      : String
演算    : 文字列連結
単位元  : 空文字列

補足：モノイドは可換性（左右を入れ替えてよいこと）を要求しません。文字列連結はまさに非可換で、"ab" と "ba" は別物です。ここで問題にならないのは、FizzBuzz が fizz → buzz の順を固定しているからで、私たちが頼っているのは「並びは意味を持つが、括弧の付け方は意味を持たない」という結合律のほうだけです。

先の Smalltalk の FizzBuzz では、このモノイド構造がそのまま使われています。

fizz(n) <> buzz(n)

該当しないルールは、連結において「何もしない」。ここがこの実装の美しいところです。条件に該当しない場合を null や None や特別なフラグで表すのではなく、モノイドの単位元で表しているのです。

オブジェクト指向の特に Smalltalk らしいメソッド分割から出てきたコードの中に、結果を単位元と結合で扱うモノイド的な構造が隠れている、というのは興味深いところです。

Haskell に落としてみる

同じ考え方を Haskell で書くと、たとえば次のようになります。空文字列を、文字列モノイドの単位元 mempty として明示しておきます。

fizz, buzz :: Int -> String
fizz n = if n `mod` 3 == 0 then "Fizz" else mempty
buzz n = if n `mod` 5 == 0 then "Buzz" else mempty

fizzBuzz :: Int -> String
fizzBuzz n
  | null s    = show n
  | otherwise = s
  where s = fizz n <> buzz n

main :: IO ()
main = mapM_ (putStrLn . fizzBuzz) [1..100]

<> は Semigroup の演算（モノイドの結合に相当）で、String は [Char] なのでこれはリスト連結です。mempty :: String は空文字列です 1。「該当しない場合は空文字列を返す」が、「該当しない場合はこのモノイドの単位元を返す」と読めるようになりました。

補足：Smalltalk / Ruby 版では、非該当時に ifEmpty: [n] / if_empty{n} が整数 n を返すため、collect: / collect の結果は文字列と整数が混在したコレクションになっていました。動的型付けではこれがそのまま通りますが、Haskell 版では show n で常に文字列へ写しており、戻り値の型を String に統一しています（F# 版の string n も同じです）。

ここまでは Smalltalk のコードの比較的素直な翻訳と言えそうです。しかし Haskell には、もう一段きれいな書き方があります。

point-free にする ―― 関数それ自体がモノイド

fizz n <> buzz n をよく見ると、n を二度書いています。実はこれは省けます。

Haskell には「返り値がモノイドなら、そこへ至る関数もモノイドになる」という仕組みがあります（instance Monoid b => Monoid (a -> b)）。その結合は「点ごとに <> する」と定義されているので、fizz と buzz を、引数を書かずに関数のまま足し合わせられます。

rules :: Int -> String
rules = fizz <> buzz          -- (fizz <> buzz) n == fizz n <> buzz n

fizzBuzz :: Int -> String
fizzBuzz n
  | null s    = show n
  | otherwise = s
  where s = rules n

fizz <> buzz には n が現れません。n をどう配るかは、<> が「中の String の流儀で配る」と知っているからです。これがいわゆる point-free スタイルで、Smalltalk の n fizz, n buzz が n を二度手で書いていたのに対し、Haskell ではルールどうしの結合そのものを名前にできます。

念のため、ひとつ誤読を防いでおきます。ここでの関数のモノイドは、関数合成ではありません。fizz <> buzz は fizz . buzz（一方の出力をもう一方の入力に渡す合成）とは別物です。意味するのは「同じ n を fizz と buzz の両方に渡し、返ってきた文字列を <> で結合する」こと、すなわち次の等式です。

(fizz <> buzz) n = fizz n <> buzz n     -- これは fizz . buzz ではない

そもそも fizz . buzz は型が通りません（buzz の返り値は String、fizz の引数は Int）。<> が結合しているのは関数の入出力ではなく、あくまで返り値どうしです。

ルールを増やす ―― foldMap

この見方は、ルールが増えたときに効きます。各ルールに 割る数 単語 を部分適用した関数にして、foldMap で畳み込みましょう。foldMap は「各要素をモノイド値に写してから、まとめて結合する」関数です 2。

rule :: Int -> String -> Int -> String
rule divisor word n = if n `mod` divisor == 0 then word else mempty

rules :: [Int -> String]
rules = [ rule 3 "Fizz", rule 5 "Buzz" ]

fizzBuzz :: Int -> String
fizzBuzz n
  | null s    = show n
  | otherwise = s
  where s = foldMap ($ n) rules

($ n) は「ルールに n を適用する」関数で、foldMap ($ n) rules は各ルールを n に適用した文字列を <> でつないだものに等しくなります。Smalltalk の n fizz, n buzz を、一般化して書いたものだと言えます。

7 で割り切れるとき "Woof" も出したくなったら、ルールを一つ足すだけです。

rules :: [Int -> String]
rules = [ rule 3 "Fizz", rule 5 "Buzz", rule 7 "Woof" ]

該当しないルールは mempty（空文字列）を返すので結果に影響せず、21 なら "Fizz" <> "" <> "Woof" = "FizzWoof" のように、条件の組み合わせを列挙しなくても自然に結合されます。

F# に落としてみる

同じ考え方を F# で書くと、こうなります。F# では文字列連結に + を使えます 3。単位元はやはり空文字列です。

let fizz n = if n % 3 = 0 then "Fizz" else ""
let buzz n = if n % 5 = 0 then "Buzz" else ""

let fizzBuzz n =
    let s = fizz n + buzz n
    if s = "" then string n else s

[1..100] |> List.iter (fizzBuzz >> printfn "%s")

設計の骨格は Smalltalk・Haskell と同じです。「該当すれば文字列、該当しなければ空文字列、最後に連結」。ところが、Haskell でいちばん気持ちよかった fizz <> buzz（関数のまま結合する point-free）を、F# はそのままでは書かせてくれません。

まず前提として、Haskell がモノイド結合に使った記号 <> は、F# では「等しくない（≠）」を意味する演算子として先約済みなので同じ記号は使えません。

だからといって別記号を使えばよいかというとそれも違って、そもそも F# には Haskell と違い、「返り値がモノイドなら関数もモノイド」という一般則が存在しません。従って、もし fizz と buzz をそのまま足したければ、「文字列を返すルール専用の結合器」を、自分で書く必要があります。

ただし、そうして定義された結合器は、Haskell の <> とは違い、汎用のモノイド演算子ではないという点に注意してください。あくまで「同じ入力を 2 つの文字列生成関数に渡し、その結果を +（文字列連結）でつなぐ」だけの、出力を文字列に固定した道具として書きます（入力の型は多相にできます）。

// 文字列を返すルール専用の結合器。出力は string 固定、汎用のモノイド演算子ではない
let combineRules (f: 'a -> string) (g: 'a -> string) : 'a -> string =
    fun x -> f x + g x

let rules = combineRules fizz buzz     // n を書かずに 2 つのルールを結合（point-free）

let fizzBuzz n =
    let s = rules n
    if s = "" then string n else s

combineRules fizz buzz は n を書いていないので、point-free の眼目（結合そのものを名前にする）は保たれています。しかも出力 string を固定して入力 'a だけ多相にした形は、Haskell の Monoid (a -> b)（任意のモノイド b、任意の入力 a）で b = String を固定した特別な場合に対応していて、対比が見やすくなります。違いは、Haskell の <> があらゆるモノイド b に効く一つの演算だったのに対し、こちらは b = string 専用に手で書いた結合器だという点です。

要するに、この + は string の連結を名指ししているだけで、Haskell の <> のような「抽象的なモノイド演算」ではありません。F# 側には「+ が指す抽象的なモノイド」という足場がそもそも無いのです。

ここが Haskell との違いの核心です。Haskell は「関数のモノイドは一般法則から自動的に従う」ので、何も書かずに fizz <> buzz が出てくる。F# は「欲しい結合器をひとつ、用途を限定して、その場で明示的に定義する」。自動ではないぶん、何が起きているかは目の前のコードに全部書いてあります。

これは F# の力不足というより、選好でもあります。F# は「簡潔・堅牢・高速」を掲げ、問題領域に集中できる自己記述的なコードを重んじる言語で 4、型は強く推論する一方、mempty のような単位元を型から暗黙に導くよりは、挙動をコードに明示する側に寄っています。どちらが上ということではなく、抽象を宣言して自動で導く Haskell と、挙動を明示する F#、という設計の好みの違いだと言えます。

ルールを増やすときも、<> が使えないぶん結合は String.concat（または List.fold (+) ""）で書きます。

let rule divisor word n =
    if n % divisor = 0 then word else ""

let rules =
    [ rule 3 "Fizz"
      rule 5 "Buzz"
      rule 7 "Woof" ]

let fizzBuzz n =
    let s =
        rules
        |> List.map (fun r -> r n)
        |> String.concat ""
    if s = "" then string n else s

[1..100] |> List.iter (fizzBuzz >> printfn "%s")

これは Haskell の foldMap ($ n) rules に対応する発想を、map してから concat する と明示的に書いたものです。

補足：String.concat "" の "" は区切り文字で、モノイドの単位元としての意味では使われていません。出力は同じですが、List.fold (+) "" の "" とは役割が違っている点に注意してください。

コラム：F# のモノイド標準抽象の欠落と、Haskell の型クラスの癖

F# 版が Haskell 版と「設計は同じなのに書き味が違う」のは、F# に Haskell の型クラスに相当する標準の Monoid 抽象が無いからです。差がいちばん出るのは、畳み込みの行です。

-- Haskell: 任意のモノイドで動く一つの関数
foldMap ($ n) rules

// F#: 文字列に固定された専用関数
rules |> List.map (fun r -> r n) |> String.concat ""

foldMap は Monoid に対して定義されているので、結合対象を [LogLine] や Sum Int に差し替えても行は変わりません。一方 String.concat "" は文字列専用です。

もっとも、F# でも SRTP（inline ＋静的に解決される型パラメータ） を使えば、foldMap 相当を「+ を持つ任意の型」に対して一つの関数で書けます。

let inline foldRules zero n rules =
    rules |> List.map (fun r -> r n) |> List.fold (+) zero

推論される署名には 'a ではなく ^a（キャレット）が付き、+ メンバを要求する静的制約が明示されます。

val inline foldRules :
  zero: ^a -> n: 'b -> rules: ('b -> ^a) list -> ^a
    when ^a : (static member (+) : ^a * ^a -> ^a)

ただし SRTP が拾えるのは「+ というメンバを持つか」までで、単位元は自動では出てきません。string には Zero メンバが無いため、単位元 zero は呼び出し側で手渡しています。Haskell が Monoid インスタンスから <> と mempty をセットで供給する（だから foldMap は単位元を書かずに済む）のとは、そこが違います。「宣言された抽象で解決するか、メンバの有無で解決するか」――これが二つの言語の流儀の差です 5。

では Haskell の型クラスが万全かというと、そうでもありません。

Haskell の Monoid は、単なる演算子オーバーロードのためだけではなく、「ある型を、モノイドとして扱うために必要な部品（結合演算と単位元）を載せる」仕組みとして機能します 6。

class Semigroup a where
  (<>) :: a -> a -> a

class Semigroup a => Monoid a where
  mempty :: a

String が Monoid のインスタンスだ、というのは、String に「連結」と「空文字列」を載せた、ということ。だから foldMap は文字列専用にならずに済みます。

ただし、Haskell の型クラスには瑕疵ともとれる「癖」があります。ある型とある型クラスの組に対して、インスタンスは基本的に一つです。そのため、同じ型に複数の自然なモノイド構造があると、そのままでは区別できません。たとえば整数には加法（+, 0）と乗法（*, 1）の両方がありますが、Int に Monoid インスタンスを二つ与えることはできず、Sum / Product のような newtype で包み分ける必要があります 7。

Sum 3 <> Sum 4          -- Sum 7
Product 3 <> Product 4  -- Product 12

つまり型クラスの便利さは、「型そのものに標準の構造を一つ結びつける」という設計に支えられています。今回の FizzBuzz では String のモノイドがほぼ一意（連結と空文字列）なので、その自動化が気持ちよく働きました。裏を返せば、ここで見ているのは型クラスがうまくはまる素直な例であって、いつでも万能というわけではない、ということです。

おまけ：ifEmpty:もモノイドにできる。ただしfizzやbuzzほどのうまみは出ない

各版の末尾はこうでした。

ifEmpty: [n]
| null s = show n

if s = "" then string n else s

ここでしていることは、文字列を連結することではありません。連結はすでに終わっています。ここでしているのは、結合結果が空だった場合に、数字の表示へフォールバックするという処理です。

つまり、冒頭の Smalltalk のちょっと変わった FizzBuzz 実装は、全体で二段階になっていたのです。

1. ルールの結果を文字列モノイドで結合する   ← String のモノイド
2. 結合結果が空なら、数字を表示する         ← フォールバック

ここで「2 段階目は条件分岐であって、モノイドの話はもう終わり」と言ってしまいたくなります。しかし、ここも実はモノイドにできます。「左から見て、最初に存在する候補が勝つ」という演算です。これには結合律があり、単位元（どこにも値がない状態）もあります。Haskell ではこれが Data.Monoid の First として用意されています。

まず、空文字列を「値がない」とみなし、空でない文字列だけを「値がある」とみなす関数を用意します。

presence :: String -> Maybe String
presence "" = Nothing
presence s  = Just s

そのうえで、show n を「必ず存在する最後の候補」として末尾に並べ、First で畳みます。

import Data.Monoid (First(..))
import Data.Maybe  (fromJust)

fizzBuzz :: Int -> String
fizzBuzz n =
  let label = fizz n <> buzz n             -- ① String のモノイドで結合
  in fromJust . getFirst                   -- ③ Maybe を剥がす（← この一手が残る）
       $ First (presence label)            -- 候補：結合結果（空なら Nothing）
      <> First (Just (show n))             -- ② First のモノイドで番号へフォールバック

確かに、フォールバックまでモノイドで畳めています。これで FizzBuzz は端から端まで、二つのモノイドの重ね合わせ ―― 各数を組み立てる連結のモノイドと、候補から一つを選ぶ First のモノイド ―― として書けたことになります。

ところが、これにはあまり嬉しさがありません。fizz/buzz の連結では、結合する部品も最終結果も同じ String で、型が閉じていました。だから <> と mempty だけで端まで書けたのです。一方フォールバックは、候補が Maybe String、欲しい答えが String と型が閉じておらず、First で畳んだ後に getFirst／fromJust で Maybe を剥がす一手がどうしても残ります。First は選択をモノイド化してくれますが、この型の段差までは消してくれません。

だから実用上は、わざわざ First を持ち出さず、素朴にこう書けば十分です。

import Data.Maybe (fromMaybe)

fizzBuzz :: Int -> String
fizzBuzz n = fromMaybe (show n) (presence (fizz n <> buzz n))

裏を返すと、fizz/buzz があれほど綺麗にはまったのは、部品と結果が同じモノイドに閉じていた、稀な幸運だったということです。モノイドとして統一的に美しく表せることと、それが設計上のコストに見合うかどうかは、別の話と考えた方がよいでしょう。fizz/buzz は前者と後者が一致した好例で、ifEmpty: のフォールバックは、前者は成り立つのに後者が伴わない例 ―― そう並べてみると、この FizzBuzz が「うまくはまった」理由のほうが、より鮮明に見えてきそうです。

補足：Data.Monoid.First（Maybe を包み、単位元を持つ）と Data.Semigroup.First（Maybe なし・単位元なし・常に左を返す）は別物です。ここで欲しいのは前者なので、import Data.Monoid (First(..)) を明示してください。くしくも、この「同名で別物」もまた、抽象が現実では綺麗に閉じてくれない一例になっています。

既存のモノイド的 FizzBuzz 解法との違い

念のため、FizzBuzz をモノイドや Semigroup と結びつけて読む発想そのものは、関数型プログラミング、とくに Haskell 周辺ではすでに知られています。

たとえば、Mark Seemann は FizzBuzz を catamorphism、Semigroup、Monoid の例として扱い、条件分岐ではなく代数的な結合として FizzBuzz を構成しています 8。また Matt Parsons は、FizzBuzz の monoidal solution が rules engine と関係していることを指摘しています 9。ほかにも、Maybe String のモノイドや関数のモノイドを用いた有名な2行 FizzBuzz が知られています（元コード 10 と、その読み解き 11,12,13）。

言うまでもなく、本稿の狙いは「FizzBuzz はモノイドで書ける」という事実を新しい視点として提示することではありません。この構造が言語ごとにどのように見えるか、見せるか、あるいは、Smalltalk のコードのように隠れているか、というところに置いたつもりです。

まとめ

Smalltalk の風変わりな FizzBuzz は、条件分岐を組み合わせているのではなく、各ルールの出力を文字列として作り、それらを連結しています。その連結の背後にあるのが、実は文字列のモノイド構造（演算＝連結、単位元＝空文字列）でした。

Haskell では、これを <> と mempty で明示でき、さらに「関数自体がモノイド」という性質のおかげで fizz <> buzz と point-free に書けます。ルールが増えても foldMap で畳むだけで、foldMap は任意のモノイドに対して一つで通用します。

F# でも空文字列＝単位元という骨格はそのまま通用できますが、仕上げの一手が違います。<> は ≠ に先約され、関数のモノイドの一般則も標準では効かないので、combineRules のような文字列ルール専用の結合器も、String.concat "" という文字列専用の畳み込みも、手で明示することになります。この「手間なしで導かれるか、明示するか」の差こそ、Haskell 型の型クラスを持つ言語と、そうでない言語の書き味の違いそのものでした。

この FizzBuzz から学べるのは、非該当の結果を null や例外で特別扱いせず、モノイドの単位元として表す、という拡張に向いた設計です。

該当すれば意味のある値を返す
該当しなければ単位元を返す
最後に全部まとめる

この形にできると、条件の組み合わせを列挙せずに、独立したルールをあとから結合できます。最後のフォールバックさえ「もう一つのモノイド」として畳めること、そしてそれが必ずしもペイしないことまで含めて、素朴に、FizzBuzz の主要ロジックをモノイド的に書いているという気付きの面白さを楽しんでいただけたなら幸いです。

参考文献

  1. Hackage, Data.Monoid, Monoid, Sum, Product などの標準ライブラリ文書。https://hackage.haskell.org/package/base/docs/Data-Monoid.html↩
  2. Hackage, Data.Foldable, foldMap の標準ライブラリ文書。https://hackage.haskell.org/package/base/docs/Data-Foldable.html#v:foldMap↩
  3. Microsoft Learn, Strings - F#, 文字列演算子としての +。https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/strings↩
  4. Microsoft, What is F# (.NET ドキュメント)。F# を「簡潔・堅牢・高速なコードを書くための言語」であり「問題領域に集中できる、すっきりした自己記述的なコードを書ける」と説明している。https://learn.microsoft.com/en-us/dotnet/fsharp/what-is-fsharp↩
  5. Microsoft Learn, Statically Resolved Type Parameters - F#, SRTP の説明。https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/generics/statically-resolved-type-parameters↩
  6. 檜山正幸, 「入門的ではない型クラスの話：Haskellの型クラスがぁ (´^｀;)」, 檜山正幸のキマイラ飼育記, 2016。型クラスを、単なる演算子オーバーロードではなく「型に構造（演算と法則）を載せる」仕組みとして捉える解説。https://m-hiyama.hatenablog.com/entry/20160928/1475022255↩
  7. Hackage, Data.Monoid, Sum / Product newtype の標準ライブラリ文書。https://hackage.haskell.org/package/base/docs/Data-Monoid.html↩
  8. Mark Seemann, “Semigroup resonance FizzBuzz”, ploeh blog, 2019。条件分岐を使わず、異なる周期の無限ストリームを <>（Maybe String のモノイド）で重ね合わせ、fromMaybe で数字とマージする「共鳴」方式。https://blog.ploeh.dk/2019/12/30/semigroup-resonance-fizzbuzz/↩
  9. Matt Parsons, “An Elegant Fizzbuzz”, 2016。各ルールを Integer -> Maybe String とし、関数・Maybe・String の三層のモノイドを fold で畳む rules engine 的な構成。https://www.parsonsmatt.org/2016/02/27/an_elegant_fizzbuzz.html↩
  10. r/haskell, 「I Did A Haskell: fizzbuzz」, Reddit（2014年頃）。次項以降で読み解かれる有名な2行 FizzBuzz の初出とされるスレッド（投稿者は現在アカウント削除済み）。https://www.reddit.com/r/haskell/comments/2cum9p↩
  11. Joseph Weston, “Fizzbuzz in Haskell”, 2018。上記の2行コードを解読し、a -> b と Maybe a のモノイドは意味が異なると注意しつつ、最も外側の型から内側へ合わせて読む方法を説く。https://weston.cloud/posts/coding/haskell-fizzbuzz/↩
  12. itchyny, 「Haskellで読めないコードに遭遇した時に解読する方法を徹底解説する」, 2015。同じ2行コードを日本語で徹底解読。関数のモノイド・Maybe のモノイド・Applicative ((->) a) の「三段構え」を解きほぐす。https://itchyny.hatenablog.com/entry/2015/12/27/150000↩
  13. kerupani129, 「『Haskellで書かれたおもしろいFizzBuzz』を再考する」, Qiita, 2023。同じ2行コードを再考し、Maybe String のモノイドで素直な形に落としてから point-free 形へ再構成する。https://qiita.com/kerupani129/items/949749926400ebbcfa9a↩

構造化定理と構造化プログラミングは、似ているけれど同じ話ではない

※本稿は私の理解の整理および備忘用に ChatGPT に書かせた記事です。

TL;DR　ベーム＝ヤコピーニの構造化定理は「表現できるか」の話。ダイクストラの構造化プログラミングは「人間が理解できるか」の話。両者は同じ三つの制御構造にたどり着くが、問題意識はかなり違う。

プログラミング史の入門では、よくこんな説明を見かけます。

「どんなプログラムも、順次・選択・繰り返しの三つで書ける。だから goto は不要で、構造化プログラミングが生まれた」

これは完全な間違いではありません。けれども、少し平らにしすぎた説明でもあります。ベームとヤコピーニの「構造化定理」と、ダイクストラの「構造化プログラミング」は、あとから見るときれいにつながる。しかし出発点は別です。前者はフローチャートや計算能力についての数理的な話で、後者は大きく複雑なプログラムを人間がどう理解し、どう正しさに近づけるかという設計論でした。

この記事では、その違いをざっくばらんに整理します。goto 論争だけでなく、段階的詳細化、階層化、抽象データ型、そしてオブジェクト指向への流れまで、少し寄り道しながらつなげてみます。

まず、構造化定理とは何か

ベーム＝ヤコピーニの論文は、1966年に Communications of the ACM に掲載された Corrado Böhm と Giuseppe Jacopini の “Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules” です。題名からもわかるように、もともとは「プログラマの作法」を説いたエッセイではなく、フローダイアグラム、チューリング機械、言語の形成規則に関する理論的な論文です。

俗にいう構造化定理は、ざっくり言えば、任意の計算可能な処理を、次のような構造で表せるという主張として広まりました。

  1. 順次：これをして、次にあれをする。
  2. 選択：条件によって、こちらかあちらを選ぶ。
  3. 繰り返し：条件が成り立つ間、同じ処理を繰り返す。

現代のプログラミング言語で言えば、順次実行、if / else、while / for のようなものです。これらの組み合わせだけで、goto を使った任意のフローチャートと同等の計算を表現できる、という理解が一般に「ベーム＝ヤコピーニの定理」として流通しています。

[2026-06-05 追記： 念のため、この「順次・選択・繰り返し」という説明は、後世に広く流通した要約であり、Böhm–Jacopini 論文そのものの定理文をそのまま言い換えたものではありません。Harel は 1980年の "On Folk Theorems" で、Böhm–Jacopini の結果を、補助的な Boolean 変数を許せば任意のフローチャートが、逐次合成・条件分岐・while-do からなる while-program と等価になる、という結果として整理しています。一方、Harel は同論文で、Mills はこの結果を未公刊の講義ノートで “The Structure Theorem” と呼び、多くの聴衆を集めた講義やセミナーで再証明・議論する事を通じ、それが大きく取り上げられることになった最大の功労者の一人と位置付けてもいます。総じて、構造化定理を Böhm–Jacopini に由来するものとして語ること自体には、少なくとも歴史的には一定の妥当性があるとの立場をここではとらせていただきます。Mills に帰さないことにご不満の向きもあるかと思いますが、どうぞあしからずご容赦ください。]

ただし、ここで大事な注意があります。

この定理は「そう変換すれば、プログラムが読みやすくなる」と言っているわけではありません。変換のために、元のプログラムの位置情報を保持する追加変数、いわばプログラムカウンタのようなものを導入すれば、たしかに一つの大きなループと分岐で振る舞いを再現できます。しかし、それはしばしば「構造化されたスパゲティ」になります。goto は消えたが、制御の意味は巨大な状態変数に押し込められただけ、ということが起こるわけです。

だから構造化定理を、実務上の教訓として読むなら、正確にはこう言うのがよいでしょう。

goto なしでも、計算能力の面では困らない。だが、goto を機械的に取り除けば良いプログラムになる、という意味ではない。

この一文が、構造化定理と構造化プログラミングを混同しないための出発点です。

ダイクストラの関心は「表現能力」ではなかった

ダイクストラの有名な書簡 “Go To Statement Considered Harmful” は1968年に Communications of the ACM に掲載されました。もとの投稿タイトルは “A Case Against the Goto Statement” だったと言われていますが、掲載時に現在の有名なタイトルになりました。

この短い文章でダイクストラが問題にしたのは、goto が「計算能力として必要かどうか」ではありません。彼の関心は、静的なプログラム本文と、時間の中で進行する実行過程との対応を、人間がどれだけ単純に追えるかでした。

プログラムは紙や画面の上では静的なテキストです。しかし実行時には、命令が時間順に進み、変数の値が変わり、条件によって道筋が分かれます。人間は静的な関係を把握するのは比較的得意ですが、複雑に時間発展する過程を頭の中で追うのは苦手です。だからこそ、プログラムの形と実行過程の対応をなるべく単純にする必要がある。ダイクストラの goto 批判は、この認知上の問題から出ています。

goto は、実行の現在地をどこへでも飛ばせます。自由である一方、その自由は「この行に来たとき、どういう経路で来たのか」「この変数はどんな条件を満たしているはずなのか」を追いにくくします。条件分岐やループなら、入り口と出口、成立している条件、ループ不変条件などを比較的局所的に考えられます。無制限なジャンプは、その局所性を壊しやすい。

ここが、ベーム＝ヤコピーニの定理との違いです。

  • 構造化定理：任意の制御フローは、理論上、構造化された構成に変換できる。
  • ダイクストラ：最初から、人間が理解し、正しさを論じられる構造としてプログラムを組み立てるべきだ。

片方は「後からでも表現できるか」の話。もう片方は「最初からどう考えるべきか」の話です。

では、ダイクストラはベーム＝ヤコピーニをどう見ていたのか

ここは少し慎重に書いたほうがよいところです。

「ダイクストラはベーム＝ヤコピーニの構造化定理を根拠に goto を追放した」と説明されることがあります。しかし、ダイクストラ自身の主張を読むと、それは言い過ぎです。彼の 1969年の “Notes on Structured Programming” は、構造化定理を土台にして議論を組み立てた文書ではありません。目次を見ても、「人間には多くのことはできない」「プログラムを理解する」「正しさの証明」「段階的なプログラム構成」といった、人間の知的限界と設計方法への関心が前面に出ています。

とはいえ、「ダイクストラは構造化定理と無関係だった」とまで言うのも単純化しすぎです。両者が同じ三つの制御構造、すなわち順次・選択・繰り返しに収束しているのは事実です。後世の教育や実務では、構造化定理が「goto なしでも十分に書ける」という安心材料になり、ダイクストラ流の構造化プログラミングとセットで語られるようになりました。

したがって、いちばん自然な整理はこうです。

ベーム＝ヤコピーニとダイクストラは、同じような制御構造に着目した。しかし、ベーム＝ヤコピーニは表現能力の側から、ダイクストラは人間の理解と正当性の側から、別々の道を歩いてそこへ到達した。

この整理なら、両者を無理に対立させる必要も、無理に一体化する必要もありません。

「goto を使わない」だけが構造化プログラミングではない

構造化プログラミングという言葉は、しばしば「goto を使わず、順次・選択・繰り返しで書くこと」と説明されます。入門的にはそれで十分です。しかし、ダイクストラの関心をそこだけに閉じ込めると、本丸を見落とします。

ダイクストラにとって重要だったのは、巨大なプログラムを人間の頭で扱える大きさに分解することでした。三つの制御構造は、そのための末端の道具です。より大きな話としては、次の三つが重要です。

1. 段階的詳細化、または段階的なプログラム構成

大きな問題をいきなりコードにしない。まず抽象的な処理として書く。次に、その抽象的な一行を、もう少し具体的な数行へ分解する。さらに必要なら分解する。そうして、最終的に実行可能なコードへ降りていく。

これが、いわゆる段階的詳細化です。厳密に言えば “stepwise refinement” という言葉を広く有名にしたのはニクラウス・ヴィルトの 1971年の論文ですが、ダイクストラの “Notes on Structured Programming” にも “step-wise program composition” という形で同じ問題意識がはっきり現れています。

ポイントは、抽象度を一気に混ぜないことです。

たとえば、請求書を処理するプログラムを書くとします。いきなり「CSVの3列目を int に変換し、丸め誤差に注意して……」から始めると、業務上の意味と実装上の都合が混ざります。まずは、

入力を読む
請求項目を検証する
税額を計算する
請求書を出力する

という抽象的な構造を置く。次に「税額を計算する」をさらに分ける。最後に、丸め処理やフォーマットの詳細へ降りる。こうすれば、人間は常に一つの抽象度で考えられます。

2. 正しさを後から探すのではなく、作りながら保つ

ダイクストラは、テストを軽視したわけではありません。しかし、テストだけで正しさを保証できるとは考えていませんでした。テストはバグの存在を示せても、一般にはバグの不在を示せないからです。

そこで重要になるのが、プログラムを書きながら「ここでは何が成り立っているはずか」を意識する態度です。ループならループ不変条件、関数なら事前条件と事後条件、モジュールなら外部に約束する仕様。構造化された制御フローは、こうした論理的な足場を置きやすくします。

goto が嫌われた核心もここにあります。どこからでも飛び込める場所では、「ここに来た時点で何が必ず成り立つか」を言いにくい。逆に、入口と出口が明確なブロックなら、そのブロック単位で正しさを考えやすい。

3. 階層化と抽象化

ダイクストラの業績として、1968年の THE multiprogramming system も重要です。このシステムは、活動を複数の逐次プロセスに分け、それらを階層的なレベルに配置しました。論文の要旨でも、各階層で一つ以上の独立した抽象が実装され、その階層構造が設計の論理的健全性と実装の正しさの検証に重要だった、と述べられています。

ここでのポイントは、単に「整理整頓されたOS」という話ではありません。下位の詳細を上位から隠し、上位は下位が提供する抽象だけを使う。つまり、システムを一度に全部理解しなくてもよいようにする仕組みです。

これは、構造化プログラミングのもう一つの顔です。制御フローを構造化するだけでなく、システムそのものを抽象度の違う層に分ける。人間が一度に扱う必要のある情報量を減らす。その意味で、構造化プログラミングの核心は「抽象化」だと言ってよいと思います。

コラム：break や return は悪なのか？

構造化定理を素朴に受け取ると、「ループは単一入口・単一出口でなければならない」「途中の break や return も避けるべきだ」という厳格な流儀に行きがちです。実際、教育用の言語や古典的なプログラミング作法では、そのような純粋主義が強かった時期もあります。

しかし現代の実務では、早期 return や break がむしろ可読性を高める場面も多いです。

def find_user(users, user_id):
    for user in users:
        if user.id == user_id:
            return user
    return None

これを「出口が二つあるから悪い」と機械的に非難しても、あまり得るものはありません。大事なのは、制御の意味が局所的に理解できるか、条件が明確か、読み手が実行過程を追えるかです。

つまり、構造化プログラミングを「三つの構文だけを使う宗教」として読むより、「人間が理解できる単位に制御と状態を閉じ込める技法」と読むほうが、現代のコードにもよく効きます。

ミルズらが、理論と実務をつないだ

構造化プログラミングが広まる過程では、Harlan D. Mills らの役割も大きいです。ダイクストラの議論は、かなり哲学的で、数学的で、実務家にとってはそのまま導入しにくい面がありました。ミルズらは、構造化プログラミングを企業や教育の現場で使える方法論として整理し、数学的基礎、設計法、テスト、文書化といった文脈へ広げました。

ここでベーム＝ヤコピーニの構造化定理は、実務上の説得材料として強く働きました。「goto をやめても計算能力は落ちない」という定理は、構造化プログラミングを普及させるうえで便利な旗印だったからです。

ただし、ここでも注意が必要です。理論があるから実務が自動的に成功するわけではありません。定理が保証するのは表現能力であって、よい設計ではありません。よい設計は、問題の分解、命名、抽象化、データの隠蔽、検証しやすさといった別の努力によって生まれます。

リスコフと抽象データ型へのバトン

ここから少し横道にそれますが、構造化プログラミングを「抽象化の歴史」として見るなら、バーバラ・リスコフの抽象データ型（ADT）にも触れたくなります。

リスコフは、1970年代前半にデータ抽象の概念を発展させ、CLU という言語の設計につなげました。彼女自身の “A History of CLU” では、1972年ごろにモジュール性やカプセル化の議論から、データ型とモジュールを結びつける考えへ進んだことが説明されています。抽象データ型とは、オブジェクトの表現を隠し、外部からは定められた操作だけを通じて扱えるようにする考え方です。

ここで、ダイクストラからリスコフへ一本の直線を引きすぎると危険です。リスコフの仕事には、モジュール性、Simula、Parnas、Strachey らを含む複数の流れが合流しています。しかし、構造化プログラミングが重視した「抽象度を分ける」「実装の詳細を隠す」「小さな単位で正しさを考える」という問題意識は、抽象データ型や後のオブジェクト指向とよく響き合います。

ざっくり言えば、流れはこう見えます。

  • 構造化定理：制御フローは、順次・選択・繰り返しで表現できる。
  • 構造化プログラミング：人間が理解できるように、制御と処理を構造化する。
  • 階層化・モジュール化：システムを抽象度の違う単位に分ける。
  • 抽象データ型：データ表現と操作をひとまとまりにし、表現を隠す。
  • オブジェクト指向：データと振る舞い、インターフェース、カプセル化、多相性などを言語機構として発展させる。

もちろん、オブジェクト指向の源流は Simula やケイなどにもあり、ADT だけから生まれたわけではありません。それでも、リスコフのデータ抽象が現代のプログラミング言語に与えた影響は大きく、構造化プログラミングの「抽象化の作法」をデータ側へ深めた重要な流れとして見ることができます。

まとめ：三つの構造は出発点であって、ゴールではない

構造化定理と構造化プログラミングの関係は、次のようにまとめると見通しがよくなります。

ベーム＝ヤコピーニの構造化定理は、goto を含む任意の制御フローを、理論上、構造化された形で表現できることを示しました。これは「goto がなければ計算できない」という不安を取り除くうえで重要でした。

一方、ダイクストラの構造化プログラミングは、もっと実践的で、もっと認知的な問題を扱っていました。人間の頭は小さい。複雑な時間的過程をそのまま追うのは難しい。だからプログラムは、理解できる単位、証明できる単位、抽象化できる単位へ分けて構成しなければならない。

両者は同じ「順次・選択・繰り返し」という美しい三点に触れます。しかし、そこに至る道は違います。

  • ベーム＝ヤコピーニは、数学の側から「表現できる」と言った。
  • ダイクストラは、設計の側から「理解できるように作れ」と言った。
  • ミルズらは、その二つを実務の方法論として広めた。
  • リスコフらは、抽象化をデータとモジュールの側へ発展させた。

そう考えると、構造化プログラミングは単なる「goto 禁止運動」ではありません。むしろ、現代のソフトウェア開発に今も残る、かなり根深い問いを投げかけています。

私たちは、プログラムを機械に実行させるためだけでなく、人間が理解し続けるために、どのように構造化すべきなのか。

この問いは、関数型プログラミングでも、オブジェクト指向でも、マイクロサービスでも、巨大なフロントエンドでも、いまだに形を変えて現れます。だから構造化プログラミングの話は、古典ではあっても、古びてはいないのだと思います。

事実確認メモ

  • Böhm と Jacopini の論文は 1966年、Communications of the ACM 9巻5号、366–371ページに掲載された “Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules”。構造化定理はこの論文に由来するものとして広く知られている。
  • ダイクストラの “Go To Statement Considered Harmful” は 1968年、Communications of the ACM 11巻3号、147–148ページに掲載された書簡。主眼は、goto の有無そのものより、プログラム本文と実行過程の対応を人間が理解できるかにある。
  • “Notes on Structured Programming” は 1969年に書かれ、1970年に Eindhoven のレポートとして出た後、Dahl、Dijkstra、Hoare の Structured Programming（1972年）にも収録された。構造化定理を中心にした文書ではなく、プログラム理解、正当性、段階的な構成が主題である。
  • THE multiprogramming system は 1968年の論文で発表され、階層構造と抽象化が設計・実装の検証に重要だったと説明されている。
  • Liskov の “A History of CLU” は、データ抽象が1970年代前半のモジュール性・構造化プログラミングの議論と結びつき、CLU の設計へつながった経緯を説明している。ただし、抽象データ型やオブジェクト指向をダイクストラだけからの「直系」と言い切るのは強すぎる。

参考文献・資料

「データは“悪いアイデア”」——アラン・ケイが投じた一石と、リッチ・ヒッキーとの根源的なすれ違い

※この記事は Hi Alan! I've got some assumptions regarding the upcoming big paradigm shift (an... | Hacker News といくつかの参考資料を NotebookLM に解説させたものです。

2016年、コンピュータ界の伝説的人物であり、「オブジェクト指向」やパーソナルコンピュータの概念を創出したアラン・ケイが、人気フォーラムHacker Newsに降臨しました。ある若手起業家が未来のプログラミングについて熱意ある予測を投稿したのに対し、ケイはたった一行の、しかし恐ろしく挑発的な問いを投げかけます。

もし「データ」という発想自体が、とても悪いアイデアだとしたら？ (What if "data" is a really bad idea?)

この一文は、瞬く間にClojure言語の作者であるリッチ・ヒッキーを巻き込み、プログラミングの思想的根幹を揺るがす大論争へと発展しました。それは単なる言葉尻の応酬ではありませんでした。この議論は、コンピュータ科学の歴史を通じて対立してきた二つの世界観——宇宙を「記録」しようとする科学者の視点と、新たな宇宙を「構築」しようとするシステム設計者の視点——の衝突を白日の下に晒したのです。

本記事では、この歴史的な議論を紐解き、そこから浮かび上がってきた驚くべき5つの発見を解説していきます。

⒈ すれ違いの核心：2人の天才は、同じ「データ」という言葉を別の意味で使っていた

この論争がここまで複雑化した根本的な原因は、ケイとヒッキーが「データ」という言葉を全く異なる定義で用いていたことにあります。彼らの議論は、一見噛み合っているようで、実は全く異なる土俵で繰り広げられていました。

  • リッチ・ヒッキーの「データ」: 観測された「事実の記録」であり、変化することのない静的な値（value）であるべきもの。彼にとってデータは、科学者が宇宙の真理を探究するために用いる、信頼性の高い基盤そのものです。
  • アラン・ケイの「データ」: それ単体では意味を持たず、解釈器（インタープリタ）から切り離された「記号の列」。彼にとって、意味を伴わない記号の列を送受信することには、本質的な危うさが潜んでいます。

この定義のズレこそが、互いの主張がすれ違う「不幸な不一致」を生み出した元凶でした。ヒッキーは「事実の記録という素晴らしいアイデアをなぜ否定するのか」と問い、ケイは「解釈の方法なしに記号の列を送って、どうやって意味が伝わるというのか」と問うていたのです。この定義のすれ違いこそが、単純なデータフォーマットの話ではなく、「意味はいかにして伝わるのか」という、より根源的な問いを我々に突きつけることになるのです。

⒉ 真意を伝える鍵：「電報」ではなく「大使」を送れ

アラン・ケイの思想を最も象徴するのが、「大使（ambassador）」という比喩です。彼は、意味の伝達における根本的な問題を次のように指摘しました。

重要な交渉では、私たちは電報を送りません。大使（ambassador）を送ります。

ここで「電報」とは、ケイの言う「データ」、つまり単なる記号の列を指します。それは一方的に送られ、受け手がどう解釈するかに全てが委ねられています。一方、「大使」は単なるメッセージの運び手ではありません。大使は文脈を理解し、相手と交渉し、予期せぬ事態にも自律的に対応する能力を持つ、動的なプロセスそのものです。

彼が本来目指したOOPとは、データという概念そのものを消し去り、すべてをメッセージのやり取りとして記述する世界のことであり、この「大使」という発想はその思想を凝縮したものです。オブジェクトとは、静的なデータをカプセル化したものではなく、自身の振る舞い方を知っている、自律した存在であるべきだという思想がここに凝縮されています。

⒊ 無限後退問題：「通訳の通訳の通訳…」をどう止めるか？

では、単なる「データ」ではなく、解釈の仕方を同梱すれば問題は解決するのでしょうか？フォーラム参加者の一人（panic）が、この点について鋭い指摘をしました。

「データに解釈器を同梱して送ったとしても、その解釈器のコード自体もまた、それを動かす別の何か（機械）がなければ意味をなさないデータではないか？ これでは解釈器のための解釈器を送る、という無限後退に陥ってしまうのではないか？」

この問題は、特に通信相手と何の共通基盤も持たない「銀河間ネットワーク」のような極限状況を考えると、より深刻になります。相手が我々のコンピュータアーキテクチャや文字コードすら知らない場合、どうやって最初の「解釈器」を理解させればよいのでしょうか。

この問いに対し、アラン・ケイは「いい質問でしょう？」と応じ、この壮大な問題を考えるヒントとして、ある驚くべき存在を示唆しました。それが「Lincos」です。

⒋ 宇宙人との対話法：人工言語「Lincos」という驚くべき解決策

アラン・ケイがヒントとして提示した「Lincos（リンコス）」とは、1960年に数学者ハンス・フロイデンタールが考案した、地球外知的生命体との通信を想定した人工言語です。その目的は、いかなる共通言語も持たない相手に対して、意味をゼロから立ち上げることでした。

Lincosの核心的なアイデアは、「いきなり情報を送るのではなく、まず相手に“解釈器を自力で構築させる”ための教材（辞書/primer）を送る」という点にあります。それは、意味を一方的に伝えるのではなく、意味を理解する能力そのものを相手に育ませようという、壮大な試みです。

Lincosは、以下のステップで意味を“ブートストラップ”します。

  • ステップ1: 数の提示 まず、電波パルスの繰り返し（「.」「..」「...」）によって、文化や言語を超えて普遍的である可能性が高い「数」という概念を例示します。
  • ステップ2: 記号の導入 次に、「1+2=3」のような計算の例題を大量に送り続けます。これにより、受け手はパルスの列の間に挟まれた特定のパターンが、「=」や「+」といった演算記号の意味を持つことを推測できるようになります。
  • ステップ3: 論理と会話へ さらに、二人の登場人物による質問と応答のやり取りを“劇”のように見せます。これにより、「質問とは何か」「回答とは何か」「その回答が正しいか（肯定/否定）」といった、対話のプロトコルそのものを教え込みます。

Lincosは、まさに究極の「大使」と言えるでしょう。それは完成した意味のパッケージを送るのではなく、「意味を理解するための手続きそのもの」を、丁寧なカリキュラムとして送る試みなのです。そしてこれは、前章で提起された無限後退問題に対する、壮大で理論的な解答でもあります。Lincosは「亀が下に亀」問題を、数学と論理という共有可能な現実の基盤を仮定し、受け手にそれを再構築させることで停止させるのです。

⒌ 最大のリスク：「大使」が“トロイの木馬”である可能性

しかし、「大使」というアイデア、つまり実行可能なプロセスや解釈器を受け手に送り、動かしてもらうというアプローチには、本質的なセキュリティリスクが伴います。フォーラム参加者（brutuscat）が指摘したように、この懸念は極めて現実的です。

「もし送られてきたオブジェクト（大使）が、トロイの木馬を隠したメッセージだったらどうする？」

この問いに対して、Lincosのアプローチは再び示唆に富んでいます。Lincosが送るのは、「これを実行せよ」という命令的なコードではありません。それは「これを理解し、検証せよ」という、宣言的で教材的な内容です。これにより、受け手は無防備にコードを実行する受動的な状態から、内容を吟味する能動的で批判的な状態へと移行します。未知のコードをいきなり実行してしまうリスクは、相対的に下がると考えられるのです。

結論：では、「データ」は本当に悪いアイデアなのか？

この記事で追ってきた議論を振り返ると、「データは悪いアイデアか？」というアラン・ケイの問いに対する答えは、単純なYes/Noではないことがわかります。

この論争から得られる最も重要な教訓は、「意味はデータ自体に宿るのではなく、送り手と受け手の間で共有される“解釈のプロセス”の中に生まれる」という事実です。リッチ・ヒッキーが重んじる「事実の記録」としてのデータも、アラン・ケイが追求する「自律したプロセス」としての大使も、この共有された解釈のプロセスがなければ成り立ちません。

最後に、この壮大な議論を私たちの日々の仕事に引き寄せてみましょう。

私たちが日々設計するAPIやデータフォーマットは、意味を削ぎ落とした無味乾燥な“電報”になってはいないでしょうか？ どうすれば、それを少しでも豊かな文脈を持つ“大使”に近づけることができるでしょうか？

この問いこそが、二人の天才が残してくれた、最も価値ある宿題なのかもしれません。

Smalltalk-72で遊ぶOOPの原点：「ask」「start」の実装

アラン・ケイの“メッセージングによるプログラミング”という着想に基づき（非同期処理などいろいろ足りていないながらも──）比較的忠実に実装された1970年代の非常に古いSmalltalk-72に実際に触れてみるシリーズ 第2弾です（なお最新のSmalltalkについては Pharo などでお楽しみください！）。

今回は謎言語「Smalltalk-71」で書かれたスペースウォー・ゲームを Smalltalk-72に移植して動かすことを目指しました。なんとか完走できてよかったです。前回(2019年)を含む他の記事はこちらから→Smalltalk-72で遊ぶOOPの原点 | Advent Calendar 2023 - Qiita

ユーザー入力を受け付ける ask とゲームをスタートさせる start

いよいよ仕上げの start です。

まず、Smalltalk-71 では組み込みのプロシージャを想定しているであろう ask を Smalltalk-72 で用意します。

to ask (disp _ :. !read eval)

すみません。かなり手を抜きました ^^;

この ask はメッセージとして送られてきた続く文字列を表示して、ユーザー入力の結果 read を Smalltalk-72 の式として eval してから返します。

これを使って start を実装しましょう。

to start ss pilot sy sx sbut (
    "SSIZE _ 6. 
    "MOVELAG _ "FRAMELAG _ 0. 
    "SPSCALE _ 1.0. "DIRSCALE _ 1.0. "LSCALE _ 1.0. 
    "CLOSE _ SSIZE * 3. 
    "TORPLIFE _ 2000.
    spacewar delete all.
    spacewar schedule keysens.
    stick delete all.
    do ask 'how many will be playing~ ' (
        "pilot _ ask 'pilot''s name str~ '.
        "sy _ stick ask 'two chars (keys) str for stick y-axis~ '.
        "sx _ stick ask 'tow chars (keys) str for stick x-axis~ '.
        "sbut _ stick ask 'one char (key) str for stick button~ '.
        "ss _ spaceship pilot sy sx sbut.
        spacewar schedule ss)
    disp _ 'type ''esc'' to exit...'.
    spacewar run)

"disp _ dispframe 16 480 514 184 string 2000. disp clear
@ erase. disp display.
start

作業用に広げていたターミナルウインドウのサイズを元に戻して（ disp ← ... ）から、画面を綺麗にして（ ☺ erase. disp display. ） start を実行します。

すると、プレイヤー数、プレイヤー名、推進力操作のキーのペア、操舵のキーのペア、魚雷発射キーをどうするかについて1プレイヤーずつ訊ねられるので、プレイヤー数については整数、それ以外は文字列リテラル（ '...' ）でタイプして do-it \（グリフは ！ ）することで入力できます。

全ての入力が終えると escキーで中止できる旨のメッセージを表示してゲームが始まります。

おわりに

当初の甘い計画では 18回くらいでサクッと終わらせて、残りは Smalltalk-72 らしい実装に試みにあてたかったのですが、ままならないものですね…^^;

ともあれ、なんとか start でゲームを開始するところまでこぎ着けられてよかったです。

おそらくオブジェクトのアクティベートのタイミングへの理解が足りていないのが主な理由でしょうが、“原因不明”のエラーとの格闘で無駄に時間を溶かしてしまいました。しかし、おかげでメッセージング のみ によるプログラミングを今まで以上に踏み込んで体験し身につけられたように思います。

一方で、クラスやオブジェクトがクロージャーで実現されていて、メッセージを受け取るために「アクティベート」と称する実行が必要になる Smalltalk-72 がその非効率さ以外にも抱えている構造的な問題点もなんとなくいろいろと見えてきたような気がします。

今後は、前述のとおり今回果たせなかった Smalltalk-72 ならでは版の他に、Squeak や Pharo といった現在の Smalltalk で実装したらどんなふうになるかも試してみたいと思っています。

また、オリジナルのスペースウォー・ゲームの仕様を探して、Smalltalk-71版のコードは何が違うのか、といったあたりも調べてみたいです。

Smalltalk-71 についてはますます謎が深まっただけで終わってしまったような残念な感じではありますが、それでも、なるほど「A Persona Computer for Children of All Ages（あらゆる年齢の『子供たち』のための パーソナルコンピュータ）」 でジミーとベスが遊んでいたのはまさにこのSmalltalk-71で書かれたスペースウォー・ゲームそのものであり、この論文（エッセイ？）にアラン・ケイ氏が掲載しようとしていたのもまさにこの Smalltalk-71版のコードだったのでは!?…という今更ながらの気付きを得ることができました。この予想が当たっているとしたら、読み解くのにかなり労力を費やした身としては、ダニエル・G ・ボブロー氏の助言はしごくまっとうなものだったと強く同意します^^;

あと非常に気になった点として、これはオリジナルの当ゲームの仕様がどうだったか次第で意見が分かれるところではありますが、このゲームでは向きの操舵が慣性に従っていないところがずっと引っかかりました。速度と同様に宇宙船の向きを制御するそれ用のスラスターを用意し、加速・減速を意識した姿勢制御がしたいところです。

グラフィック出力やキー入力などの IO を手軽に扱えることが前提ですが、新しく学ぶ言語や処理系を試すときにこのスペースウォー・ゲームはほどよい規模の題材として使えそうです。今後も大いに活用してゆこうと思います。

付録１：Smalltalk-71 のコードを極力修正したバージョン

Smalltalk-72 への移植を通じて、意味が通りにくい部分について恐らくこうなのではないかと修正を試みた Smalltalk-71版のコードです。

to ship :size
  penup, left 180, forward 2 * :size, right 90
  forward 1 * :size, right 90
  pendown, forward 4 * :size, right 30, forward 2 * :size
  right 120, forward 2 * :size
  right 30, forward 4 * :size
  right 30, forward 2 * :size
  right 120, forward 2 * :size
  left 150, forward :size * 2 * sqrt 3.
  left 150, forward :size * 2
  right 120, forward :size * 2
  left 150, forward :size * 2 * sqrt 3
  penup, left 90, forward :size, right 90, forward 2 * :size
end to

to flame :size
  penup, left 180, forward 2 + sqrt 3, pendown
  triangle :size, forward .5 * :size
  triangle 1.5 * :size, forward 5 * :size
  triangle 2 * :size, forward .5 * :size
  triangle 1 * :size, forward .5 * :size
  etc.
end to

to flash
  etc.
end to

to retro
  etc.
end to

to torp
  etc.
end to

to spaceship :pilot :thrust :steer :trigger
use :numtorps :location:(:x :y) :speed :direction
  repeat
    moveship
    if :trigger and :numtorps < 3
    then create torpedo :speed :direction :location .
    ?crash :self
    display ship
    pause until clock = :time + :movelag
end to

to moveship
  make :speed be :speed + (:spscale * :thrust)
  make :direction be :direction + (:dirscale * :steer) rem 360
  make :location:x be :location:x + (:lscale * :speed * cos :direction) rem 1024
  make :location:y be :location:y + (:lscale * :speed * sin :direction) rem 1024
end to

to display ":obj
  penup, moveto :location, turn :direction
  create :obj :size
  if :thrust > 0 then create flame :size
  if :thrust < 0 then create retro flame :size
  pause until clock = :time + :framelag
end to

to ?crash :object
  find all (create spaceship :s)
    if :object ≠ :s
      and |:object:location:x - :s:location:x| < :close
      and |:object:location:y - :s:location:y| < :close
    then explode :s, explode :obj
end to

to explode :object
  penup, moveto :object:location
  flash
  finish :object
end to

to torpedo :speed :direction :location
  use :thrust 0
  bump :numtorps
  moveship
  if not (0 < :location:x < 1024 and 0 < :location:y < 1024)
  then ?bump :numtorps, finish :self
end to

to start
  repeat ask "how many will be playing?" times
    create spaceship ask "pilot's name?"
      stick.(make :sn be ask “stick number?”).y
      stick.:sn.x
      stick.:sn.but
  end repeat
  if (make :char be ask) = “s” then done
  find all (create spaceship :x)
    start :x
end to

*start
how many will be playing?
*2
pilot's name?
*Jimmy
stick number?
*2
pilot's name?
*Bill
stick number?
*3

付録２： Smalltalk-72版 全コード（Smalltalk-72エミュレータのSnippetsウインドウへのコピペと二回クリックによるターミナルへの転送用）

"disp _ dispframe 16 480 8 670 string 2000. disp clear

to ship size (
    @ penup turn 180 go 2 * :size turn 90
        go 1 * size turn 90
        pendn go 4 * size turn 30 go 2 * size
        turn 120 go 2 * size
        turn 30 go 4 * size
        turn 30 go 2 * size
        turn 120 go 2 * size
        turn `150 go (sqrt 3) * 2 * size
        turn `150 go 2 * size
        turn 120 go 2 * size
        turn `150 go (sqrt 3) * 2 * size
        penup turn `90 go 1 * size turn 90 go 2 * size)

to triangle size (
    @ pendn turn 90 go 0.5 * :size
        turn `120 go size
        turn `120 go size
        turn `120 go 0.5 * size turn `90
        penup)

to flame size (
    @ penup turn 180 go ((sqrt 3) + 2) * :size pendn.
    triangle size. @ go 0.5 * size.
    triangle 1.5 * size. @ go 0.5 * size.
    triangle 2 * size. @ go 0.5 * size.
    triangle size. @ go size.
    @ penup turn 180 go ((sqrt 3) + 2.5 + 2) * size)

to abs x y (0 > :x ? (!-x) !x)

to sqrt x y z (
    0.0 > :x ? (error)
    0.0 = x ? (!0)
    "y _ 1.0 * x.
    "z _ 1.0e`8 * x.
    repeat (z > y - "y _ y - ((y * y) - x) / y * 2 ? (done)).
    x is float ? (!y)
    z > abs y - "x _ 1 * y + z ? (!x) !y)

"PI _  3.14159265

to nfact acc n m (
    7 < :m ? (error "(16 bit signed int overflow))
    "acc _ 1. for n to m do ("acc _ acc * n) !acc)

to sin acc x n m (
    "x _ (:) mod 360.
    (180 < x ? ("x _ x - 360))
    (90 < x ? ("x _ 180 - x)
    `90 > x ? ("x _ `180 - x))
    "x _ (PI / 180) * x.
    "acc _ 0.0.
       for n _ 0 to 3 do (
        "m _ 1 + 2 * n.
        "acc _ acc + ((`1.0 ipow n) * (x ipow m) / nfact m))
    !acc)

to cos (!sin 90 + :)

to retro (@ turn 180)

to rand low high : : n (
   (%seed ? (:n))
   (null n ? ("n _ 12345))
   "n _ n &- n &/ 7.
   "n _ n &- n &/ `9.
   "n _ n &- n &/ 8.
   %between ? (:low. :high. !low + n mod high + 1 - low)
   !(32768.0 + n) / 65535.0)

to clock (!mem 280)

PUT vector "each nil
addto vector "(%do ? (:#y. for x to SELF length ("each _ SELF[x]. y eval)))

to t each (ev)
t
to each (!vec[i])
PUT obset "each #each
done

addto obset "(%do ? (:#input. for i to end (input eval))

to moveship (
    "speed _ speed + SPSCALE * thrust.
    "direction _ (direction + DIRSCALE * steer) mod 360.
    "locx _ (locx + (cos direction) * LSCALE * speed) mod 512.
    "locy _ (locy + (sin direction) * LSCALE * speed) mod 512)

to stick x y i kcode : keys val : kmap (
    %delete ? (%all ? ("kmap _ nil)
        :#x.
        for i to 256 do ("y _ kmap[i]. eq #x #y ? (kmap[i] _ nil)). )
    (null kmap ? ("kmap _ vector 256))
    %process ? ("x _ kmap[1+:kcode].
        null #x ? (!false)
        x handle kcode. )
    isnew ? (
        (1 = :keys length ? ("val _ false) "val _ 0).
        for i to keys length do (kmap[1+keys[i]] _ #SELF))
    %print ? (disp _ '(stick '. disp _ 39. disp _ keys. disp _ 39. disp _ ') ')
    %handle ? (
        :kcode.
        1 = keys length ? ("val _ true)
        1 = keys[1 to 2] find first kcode ? ("val _ val - 1) "val _ val + 1)
    eq val true ? ("val _ false. !true)
    !val
)

to keysens (
    %step ? (repeat (kbck ? (stick process kbd) done))
    #keysens)

to spacewar x y : : objects (
    (null objects ? ("objects _ obset))
    %schedule ? (objects _ :#)
    %delete ? (%all ? ("objects _ nil) objects delete :#)
    %run ? (
        repeat (
            objects do (null each ? () each step).
            1 = objects vec length ? (done)))
    %find ? (%all. :"x. "y _ obset.
        objects do (each is~ = x ? (y _ each)).
        !y))

to crash object other (
    %~. "object _ :#.
    spacewar find all spaceship do (
        "other _ each.
        eq #object #other ? ()
        CLOSE < abs (object locx - other locx) ? ()
        CLOSE < abs (object locy - other locy)? ()
        explore object. explore other))

to explore object (
    :#object.
   @ penup goto object locx object locy.
   flash.
   finish object
)

to flash (
    do 10 (
        @ penup turn 36 go SSIZE * 2. 
        @ pendn triangle SSIZE * rand between 2 5.
        @ penup turn 180 go SSIZE * 2 turn 180))

to finish obj stk (
    :#obj.
    obj release.
    spacewar delete obj)

to torp size (
    @ penup turn 180 go :size turn 90
        go 0.5 * size turn 90
        pendn go 2 * size turn 30 go size
        turn 120 go size
        turn 30 go 2 * size
        turn 30 go size
        turn 120 go size
        penup turn 120 go 0.5 * size turn `90 go size)

to torpedo : thrust steer locx locy speed direction time
        ftime llocx llocy ldir lthr launcher endlife (
    isnew ? (:launcher. :speed. :locx. :locy. "ldir _ :direction.
        "locx _ "llocx _ locx + (cos direction) * SSIZE * 10.
        "locy _ "llocy _ locy + (sin direction) * SSIZE * 10.
        launcher bumptorps.
        "thrust _ "lthr _ "steer _ 0. 
        "time _ "ftime _ clock.
        "endlife _ clock + TORPLIFE)
    %release ? (
        stick delete thrust.
        stick delete steer.
        stick delete trigger)
    %locx ? (!locx)
    %locy ? (!locy)
    %step ? (
        0 < clock - time + MOVELAG ? (
            "time _ clock.
            0 < clock - endlife ? (
                launcher debumptorps.
                display torp erase.
                finish SELF)
            moveship.
            crash~ SELF.
            display torp))
    %is ? (ISIT eval)
)

to display obj (
    :#obj.
    0 < clock - ftime + FRAMELAG ? (
        "ftime _ clock.
        @ penup goto llocx llocy up turn ldir + 90 pendn white.
        obj SSIZE.
        (0 < lthr ? (flame SSIZE)
        0 > lthr ? (retro flame SSIZE)).
        @ penup goto locx locy up turn direction + 90 pendn black.
        %erase ? ()
        obj SSIZE.
        (0 < thrust ? (flame SSIZE)
        0 > thrust ? (retro flame SSIZE))
        "llocx _ locx. "llocy _ locy. "ldir _ direction ."lthr _ thrust))

to spaceship newtorp : pilot thrust steer trigger numtorps locx locy speed direction time
        ftime llocx llocy ldir lthr (
    isnew ? (:pilot. "lthr _ :#thrust. :#steer :#trigger. 
        "numtorps _ "speed _ 0.
        "direction _ "ldir _ 0 + rand * 360.
        "locx _ "llocx _ rand between 50 462.
        "locy _ "llocy _ rand between 50 462.
        "time _ "ftime _ clock)
    %release ? (
        stick delete thrust.
        stick delete steer.
        stick delete trigger)
    %locx ? (!locx)
    %locy ? (!locy)
    %step ? (
        0 < clock - time + MOVELAG ? (
            "time _ clock.
            (trigger ? (3 > numtorps ? (
                "newtorp _ torpedo SELF speed locx locy direction.
                spacewar schedule newtorp))
            moveship.
            crash~ SELF.
            display ship)))
    %is ? (ISIT eval)
    %bumptorps ? ("numtorps _ numtorps + 1)
    %debumptorps ? ("numtorps _ numtorps - 1)
)

to ask (disp _ :. !read eval)

to start ss pilot sy sx sbut (
    "SSIZE _ 6. 
    "MOVELAG _ "FRAMELAG _ 0. 
    "SPSCALE _ 1.0. "DIRSCALE _ 1.0. "LSCALE _ 1.0. 
    "CLOSE _ SSIZE * 3. 
    "TORPLIFE _ 2000.
    spacewar delete all.
    spacewar schedule keysens.
    stick delete all.
    do ask 'how many will be playing~ ' (
        "pilot _ ask 'pilot''s name str~ '.
        "sy _ stick ask 'two chars (keys) str for stick y-axis~ '.
        "sx _ stick ask 'tow chars (keys) str for stick x-axis~ '.
        "sbut _ stick ask 'one char (key) str for stick button~ '.
        "ss _ spaceship pilot sy sx sbut.
        spacewar schedule ss)
    disp _ 'type ''esc'' to exit...'.
    spacewar run)

"disp _ dispframe 16 480 514 184 string 2000. disp clear
@ erase. disp display.
start

Smalltalk-72で遊ぶOOPの原点：魚雷を実装する

アラン・ケイの“メッセージングによるプログラミング”という着想に基づき（非同期処理などいろいろ足りていないながらも──）比較的忠実に実装された1970年代の非常に古いSmalltalk-72に実際に触れてみるシリーズ 第2弾です（なお最新のSmalltalkについては Pharo などでお楽しみください！）。

今回は謎言語「Smalltalk-71」で書かれたスペースウォー・ゲームを Smalltalk-72に移植して動かすことを目指します。前回(2019年)を含む他の記事はこちらから→Smalltalk-72で遊ぶOOPの原点 | Advent Calendar 2023 - Qiita

torpedo と torp

魚雷 torpedo とその描画用プロシージャの torp は、宇宙船 spaceship に対する ship のペアと同じ関係にあります。

継承があれば torpedo はきっと spaceship との共通部分を抽象クラス化してそれを継承して作ると少し楽ができそう（Smalltalk-72版ではコードが膨れ上がったので…）ですが、Smalltalk-72 同様に Smalltalk-71 にも継承機構は想定されていなかったようで、一部重複するコードで実装する必要があります。

まず描画用の torp ですが、これは例によって省略されているので、ship から尾翼を省いて少し小さめにした処理で済ませました。

to torp size (
    @ penup turn 180 go :size turn 90
        go 0.5 * size turn 90
        pendn go 2 * size turn 30 go size
        turn 120 go size
        turn 30 go 2 * size
        turn 30 go size
        turn 120 go size
        penup turn 120 go 0.5 * size turn `90 go size)

魚雷 torpedo は、前述のとおり spaceship と基本的なところは同じなのですが、

  1. パイロット名 pilot は無い
  2. 速度 speed と位置 locx locy（Smalltalk-71版では location ）、そして方向 direction は射出された時点の spaceship のそれに従う
  3. 推進力 thrust は常に 0（つまり、速度 speed はそのまま）

という点で異なることが Smalltlak-71版の元コードから読み取れます。

書かれてはいませんが、向き direction も変わらず一定であるべきなので、舵 steer も当然 0 であるべきでしょう。

位置の更新に moveship を、描画用の torp を呼ぶ際に display torp を使っているので、魚雷としては不要なはずの thrust や steer に加え、Smalltalk-72版で追加した直近描画の位置等情報の llocx llocy lldir lthr も宣言と初期化が必要になります。

射出時の初期位置 locx locy は元コードのままだと spaceship と重なっており、これでは crash? が反応してしまうので、direction の方向に SSIZE * 3 ほど移動して現れるように変えています。後述の時限のしくみに倣って、生成直後から一定時間 crash? の実行を行わないというやり方でも良いかもしれませんね。

Smalltalk-71の元のコードでは、画面をまたぐと消滅するようですが、moveship で位置は画面をまたぐように正規化されてしまっており、またいだことを知る方法もないため、Smalltalk-72版では時限を設けて一定時間（グローバル変数 TORPLIFE ）で無効化して消滅することにしました。

時限を迎えたり他のオブジェクトと接触した時の消滅 finish SELF の際には、発射した spaceship の numtorps のデクリメントを行う必要があるのですが、発射した spaceship の numtorps にアクセスできるコンテキストから外れてしまうため spaceship に numtorps をデクリメントする debumptorps（と、必要ないですがインクリメントする bumptorps も）用意しこれをコールしています。なお torpedo インスンタス生成時に、それを射出した spaceship（自身）を launcher として渡すような変更も加えています。

魚雷が時限を迎えて消滅するときのために、display アクションに消去だけする erase オプションも用意しました。

to torpedo : thrust steer locx locy speed direction time
        ftime llocx llocy ldir lthr launcher endlife (
    isnew ? (:launcher. :speed. :locx. :locy. "ldir _ :direction.
        "locx _ "llocx _ locx + (cos direction) * SSIZE * 10.
        "locy _ "llocy _ locy + (sin direction) * SSIZE * 10.
        launcher bumptorps.
        "thrust _ "lthru _ "steer _ 0. 
        "time _ "ftime _ clock.
        "endlife _ clock + TORPLIFE)
    %release ? (
        stick delete thrust.
        stick delete steer.
        stick delete trigger)
    %locx ? (!locx)
    %locy ? (!locy)
    %step ? (
        0 < clock - time + MOVELAG ? (
            "time _ clock.
            0 < clock - endlife ? (
                launcher debumptorps.
                display torp erase.
                finish SELF)
            moveship.
            crash~ SELF.
            display torp))
    %is ? (ISIT eval)
)

to display obj (
    :#obj.
    0 < clock - ftime + FRAMELAG ? (
        "ftime _ clock.
        @ penup goto llocx llocy up turn ldir + 90 pendn white.
        obj SSIZE.
        (0 < lthr ? (flame SSIZE)
        0 > lthr ? (retro flame SSIZE)).
        @ penup goto locx locy up turn direction + 90 pendn black.
        %erase ? ()
        obj SSIZE.
        (0 < thrust ? (flame SSIZE)
        0 > thrust ? (retro flame SSIZE))
        "llocx _ locx. "llocy _ locy. "ldir _ direction ."lthr _ thrust))

to spaceship newtorp : pilot thrust steer trigger numtorps locx locy speed direction time
        ftime llocx llocy ldir lthr (
    isnew ? (:pilot. "lthr _ :#thrust. :#steer :#trigger. 
        "numtorps _ "speed _ 0.
        "direction _ "ldir _ 0 + rand * 360.
        "locx _ "llocx _ rand between 50 462.
        "locy _ "llocy _ rand between 50 462.
        "time _ "ftime _ clock)
    %release ? (
        stick delete thrust.
        stick delete steer.
        stick delete trigger)
    %locx ? (!locx)
    %locy ? (!locy)
    %step ? (
        0 < clock - time + MOVELAG ? (
            "time _ clock.
            (trigger ? (3 > numtorps ? (
                "newtorp _ torpedo SELF speed locx locy direction.
                spacewar schedule newtorp))
            moveship.
            crash~ SELF.
            display ship)))
    %is ? (ISIT eval)
    %bumptorps ? ("numtorps _ numtorps + 1)
    %debumptorps ? ("numtorps _ numtorps - 1)
)

こちらが、停止している宇宙船（敵）対して魚雷を発射、一発外して二発目で当てたときの様子です。しつこいようですが^^; 航跡が残るように display の残像を消す処理はコメントアウトしてあります。

（ 「ask」「start」の実装 へ続く ）

Smalltalk-72で遊ぶOOPの原点：衝突時（爆撃時）処理の実装

アラン・ケイの“メッセージングによるプログラミング”という着想に基づき（非同期処理などいろいろ足りていないながらも──）比較的忠実に実装された1970年代の非常に古いSmalltalk-72に実際に触れてみるシリーズ 第2弾です（なお最新のSmalltalkについては Pharo などでお楽しみください！）。

今回は謎言語「Smalltalk-71」で書かれたスペースウォー・ゲームを Smalltalk-72に移植して動かすことを目指します。前回(2019年)を含む他の記事はこちらから→Smalltalk-72で遊ぶOOPの原点 | Advent Calendar 2023 - Qiita

crash? explore flash final の追加と spaceship の修正（spacewar も）

衝突判定と衝突時処理のプロシージャは Smalltalk-71 版ではクエスチョンマークが頭に付く ?crash として定義されています。Smalltalk-72 でもそう組むこともできそうです（ ?アクションを作り、そこに crash メソッドセクションを作る…）が、Smalltalk-72 では is? のようにクエスチョンマークが後の方が自然なので crash? で書きます。ただ、Smalltalk-72 はアルファベット列と記号をひとめとめにしたメッセージシンボル等は使えないので、crash アクションを定義して、? はメッセージトークンとして消費（ ᗉ? ）するというパターンで対処します。（結果、? はあってもなくてもよいことになってしまいますが、そこは気にしない方向で…^^; ）

併せて explore flash finish も定義します。

to crash object other (
    %~. "object _ :#.
    spacewar find all spaceship do (
        "other _ each.
        eq #object #other ? ()
        CLOSE < abs (object locx - other locx) ? ()
        CLOSE < abs (object locy - other locy)? ()
        explore object. explore other))

to explore object (
    :#object.
   @ penup goto object locx object locy.
   flash.
   finish object
)

to flash (
    do 10 (
        @ penup turn 36 go SSIZE * 2. 
        @ pendn triangle SSIZE * rand between 2 5.
        @ penup turn 180 go SSIZE * 2 turn 180))

to finish obj stk (
    :#obj.
    obj release.
    spacewar delete obj)

Smalltlak-71版にコードがある crash? と explore は Smalltalk-72 の評価順を意識した式の順の変更等あるものの、おおむね元コードと同じ内容です。

to ?crash :object
  find all (create spaceship :s)
    if :object ≠ :s
      and |:object:location:x - :s:location:x| < :close
      and |:object:location:y - :s:location:y| < :close
    then explode :s, explode :obj
end to

to explode :object
  penup, moveto :object:location
  flash
  finish :object
end to

例によってコードが省略されている flash については、残像を消すことは考えずに単純にランダムな大きさの三角形を triangle で円形に描く処理だけで済ませています。

finish は create 同様に Smalltalk-71 では組み込みを想定しているのかもしれませんが、ここでは stick のリリースと spacewar からの削除の処理をするアクションにしました。

あとは spaceship に crash? をコールしたり、locx や locy のアクセッサーを追加する修正を加えれば完了です。

to spaceship : pilot thrust steer trigger numtorps locx locy speed direction time ftime llocx llocy ldir lthr (
    isnew ? (:pilot. "lthr _ :#thrust. :#steer :#trigger. 
        "numtorps _ "speed _ 0.
        "direction _ "ldir _ 0 + rand * 360.
        "locx _ "llocx _ rand between 50 462.
        "locy _ "llocy _ rand between 50 462.
        "time _ "ftime _ clock)
    %release ? (
        stick delete thrust.
        stick delete steer.
        stick delete trigger)
    %locx ? (!locx)
    %locy ? (!locy)
    %step ? (
        0 < clock - time + MOVELAG ? (
        "time _ clock.
        moveship.
        crash~ SELF.
        display ship))
    %is ? (ISIT eval)
)

本質ではない＆なんか重くなるだけ…のような気もしますが、spaceship がすべて finish した場合にループを抜けるように spacewar にも少し手を入れました。

to spacewar x y : : objects (
    (null objects ? ("objects _ obset))
    %schedule ? (objects _ :#)
    %delete ? (%all ? ("objects _ nil) objects delete :#)
    %run ? (
        repeat (
            objects do (null each ? () each step).
            1 = objects vec length ? (done)))
    %find ? (%all. :"x. "y _ obset.
        objects do (each is~ = x ? (y _ each)).
        !y))

うまく衝突するか試してみましょう。航跡が残るように display の残像を消す処理はコメントアウトしてあります。（同前^^;）

"SSIZE _ 6. "MOVELAG _ "FRAMELAG _ 0. "SPSCALE _ 1.0. "DIRSCALE _ 1.0. "LSCALE _ 1.0. "CLOSE _ SSIZE * 3.
@ erase. disp display. disp clear
"s1x _ stick 'jl'. "s1y _ stick 'ki'. "s1but _ stick ','.
"s1 _ spaceship 'Jimmy' s1y s1x s1but.
"s2x _ stick 'ad'. "s2y _ stick 'sw'. "s2but _ stick 'x'.
"s2 _ spaceship 'Beth' s2y s2x s2but.
spacewar delete all.
spacewar schedule keysens
spacewar schedule s1. spacewar schedule s2.
spacewar run

バシィッ！

（ 魚雷を実装する へ続く ）