プログラミングの7つの原型言語(2022)
(madhadron.com)- 個別の文法よりも 基礎パターンのまとまり の違いのほうが重要であり、プログラミング言語は反復・再帰・構成方式によって 7つの原型言語 に分かれる
- ALGOL, Lisp, ML, Self, Forth, APL, Prolog が中核的な分類であり、各系統は代表言語を基準サンプルとして他言語の系譜を判断する
- 慣れた原型言語を共有する新しい言語は学びやすいが、見慣れない原型へ移ると 新しい思考経路 とかなりの学習時間が必要
- ALGOLは代入・条件文・反復文中心の関数構成、Lispは マクロとリストコード、MLは第一級関数と再帰、Selfはメッセージ送信オブジェクト、Forthはスタックベース文法、APLはn次元配列、Prologは事実と探索構造が特徴
- すべてのプログラマにとって ALGOL系言語 の習熟が優先であり、その次にSQLを学び、その後は見慣れない原型言語を継続的に学ぶやり方が長期的に有利
プログラミングの7つの原型言語
- プログラミング言語を選ぶときは個別の文法差より 基礎パターン の習得が重要であり、似た系統の言語同士では配列走査や組合せ走査のような基本構造がほぼ同じ形
- 異なる言語群では反復、再帰、プログラム構成方式が大きく異なり、こうした 基礎パターンのまとまり が互いに異なる原型言語を成す
- 慣れた原型言語を共有する新しい言語の学習は比較的容易な移行だが、見慣れない原型言語へ移るとかなりの時間と新しい思考経路が必要
- ソフトウェア分野で認識されている原型言語は ALGOL, Lisp, ML, Self, Forth, APL, Prolog の7つ
- 各原型言語は特定の代表言語を基準サンプルのようにして分類され、他の言語はそのサンプルとの比較で系統を判断する
-
ALGOL
- プログラムは 代入、条件文、反復文 の列で構成され、関数単位で組織される形
- 多くの言語はここにモジュールシステム、新しいデータ型定義方式、多相性、例外やコルーチンのような代替制御フロー構造を追加している
- 現在広く使われているプログラミング言語の大半がこの原型言語の系統に属する
- ALGOLそのものには ALGOL 58, ALGOL 60, ALGOL W, ALGOL 68 が含まれる
- Assembly language, Fortran, C, C++, Python, Java, C#, Ruby, Pascal, JavaScript, Ada がこの系統につながる
- 最も古い原型言語であり、Ada Lovelace によるバベッジ解析機関向けプログラムの定式化にまでさかのぼる系譜
- EDVACと初期Univacへ続く Eckert-Mauchly 型コンピュータの機械語とアセンブリ言語、Grace Hopper の A-0 から Fortran と COBOL に至る初期高級言語の試みはすべてこの形
- 1960年代に学界で構造化プログラミングが発展し、こうした言語をより管理しやすくした結果が ALGOL 60 であり、その後の系統メンバーの大半はここから派生した
- 時間がたつにつれ他の原型言語の機能を吸収する傾向がある
- 1980年代には Self系の概念 がクラスの形で取り込まれ、データ型定義と多相性の実装手段として使われた
- 2010年以降には ML系の概念 も登場した
-
Lisp
- 括弧で囲まれた前置式 とリスト表現が結びついた文法
(+ 2 3)(defun square (x) (* x x))(* (square 3) 3)
- 空白で区切られた項目を括弧で囲む リスト表現 が言語に組み込まれているため、コード自体がリストの形をしている
- マクロはリストを受け取って変更し、その変更後のコードをコンパイラへ渡せるため、プログラマが言語の意味を再定義できる構造
- ほとんどのコード記述では他の原型言語、通常は ALGOL や ML のように動作する傾向があるが、マクロシステム が相違点
- Common Lisp の
loop構文も言語組み込み機能ではなくマクロとして定義された形 - 初期には多くの Lisp 方言があったが、コミュニティは Common Lisp に合意した
- Sussman と Steele は関数でどこまでできるかを探究して Scheme を生み出した
- 数値計算用の Lush、AutoCAD のスクリプト言語 AutoLISP、Emacs の編集動作実装言語 Emacs Lisp のような特定目的の Lisp も使われている
- 最近では Clojure が Lisp 系の3つ目の主要分岐として台頭している
- Fortran より約1年後に登場した、今日まで使われている2番目に古い言語系統
- 出発点は、自分自身の式を評価できる数学的構造をどう表記するかという 数学的な問い だった
- John McCarthy が1958年に答えを示し、その後コンピュータ上に実装された
- 初期 Lisp は数学的背景のため当時の機械と相性がよくなく、メモリや CPU サイクルの問題は数学にはなかったテーマであり、ガベージコレクション のような技法が必要になった
- 1970年代後半から1980年代初頭には Lisp 実行だけのために一から設計された機械が存在した
- 今日の統合開発環境の多くの要素はそれらの機械で発明された
- 同時期には人工知能研究の主な手段が Lisp であり、1980年代の人工知能ブームが成果を出せなかったことで、分野とともに Lisp も AI Winter に沈んだ
- それでも生き残り、コンピュータ性能の向上と他言語による機能受容によって実装上の難しさは小さくなった
- 括弧で囲まれた前置式 とリスト表現が結びついた文法
-
ML
- 関数が 第一級の値 であり、多様な関数とタグ付きユニオンを表現できる Hindley-Milner 系型システム を持つ
- すべての反復は再帰で行われる
sum [] = 0sum (x:xs) = x + sum xs
- 反復パターンをカプセル化した関数を定義し、他の関数を受け取って動作を実装するやり方も用いられる
map _ [] = []map f (x:xs) = (f x) : (map f xs)
- 一部の言語、Miranda と Haskell は基本的に遅延評価を用いる
- 他の言語は型システムをさまざまな方向に拡張している
- OCaml は Self 原型言語の概念との結合を試みた
- Agda と Idris は値と型を混在させる依存型システムを採用した
- 1ML はモジュールと型を結合した
- ML から CaML, Standard ML, OCaml が派生した
- Miranda, Haskell, Agda, Idris のような関連系統も続いている
- ML はイギリスの Cambridge で開発された定理証明プログラムの メタ言語 であり、名前もそこに由来する
- その後その文脈を離れて独立した言語として広まり、特にイギリスとフランスを中心にヨーロッパで人気を得た
-
Self
- プログラムは互いにメッセージを送り合う オブジェクトの集合 で構成され、すべての動作がこの方式で実装される
- 新しいオブジェクトは既存のオブジェクトにメッセージを送って生成する構造
- 条件文も true オブジェクトと false オブジェクトのどちらかを参照する変数によって実行される
- 2つのオブジェクトは、真のときに実行する関数と偽のときに実行する関数を引数に取るメッセージを受け取る
- true オブジェクトは最初の関数を、false オブジェクトは2番目の関数を実行する
- 呼び出し側コードはどちらのオブジェクトかを知らず、単にメッセージを送るだけ
- 反復文も同じ方式であり、適切なオブジェクトを作って適切な場所に入れれば 言語意味全体の再定義 も可能
- この種の言語では通常、ソースはテキストファイルではなく ライブ環境 に保存される
- プログラマはライブシステムを修正し、ファイルをコンパイルしてシステムを作る代わりにその状態を保存する
- 重要な例は Smalltalk と Self
- 多くの言語はこの言語群のメッセージ送信方式の一部だけを取り入れており、この部分導入を通常オブジェクト指向プログラミングと呼ぶ
- その大半は Smalltalk ベースで、JavaScript だけは例外的に Self のクラスなしオブジェクトシステムに由来する
- Common Lisp のオブジェクトシステムは、メッセージを受ける1つのオブジェクトだけでなく すべての引数 を基準にランタイムが実行コードを選ぶよう一般化している
- Erlang は実行の流れがオブジェクト間を移る代わりに、並列実行スレッド が明示的にメッセージを受信し送信する方向へ切り替えた
- 元祖の言語は Smalltalk であり、1970年代後半から1980年代に Xerox Parc で開発された
- 1980年代には複数の商用 Smalltalk システムがあり、IBM は他言語向けプログラミングツールである VisualAge コレクションの開発に Smalltalk を使った
- 今日の Smalltalk は主にオープンソースの Pharo Smalltalk の形で存続している
- Smalltalk を高速かつ効率的に実行する研究が数多く行われ、その頂点が Strongtalk プロジェクト だった
- Strongtalk の発見は Java の HotSpot JIT コンパイラ の基盤となったという歴史的重要性を持つ
- Smalltalk はそれ以前の言語にあった値と型の概念を引き継いでクラスを実装し、すべてのオブジェクトは型を与えるクラスを持ち、そのクラスがその型のオブジェクトを生成した
- Self はクラスの概念を取り除き、オブジェクトだけで構成される
- より純粋な形であるという理由から、この原型言語のサンプルには Self が選ばれている
-
Forth
- スタック言語は Lisp の鏡像 のような形であり、Hewlett Packard の逆ポーランド記法電卓と文法を共有する
- データスタックを持ち、
42のようなリテラルを書くとスタックにプッシュされ、関数名は明示的な引数なしでスタックを対象に動作する - 単純な算術も
2 3 + 5 *のような反転した形になる - 関数定義も非常に簡潔
- 多くの Forth 方言では
:が新しい単語の定義になる squareはdupと*を呼ぶのと同じ意味dupはスタック最上段を複製し、*は最上段の2項目を乗算する
- 多くの Forth 方言では
- パーサを横取りして自分のコードに置き換えられるため、文法全体の置き換え が可能
- Fortran の部分集合やパケットレイアウト、状態機械遷移を表す ASCII ダイアグラムを直接パースする方式のような小さな言語を定義した Forth プログラムがよくある
- Forth の各種方言、PostScript, Factor, Joy が含まれる
- Joy はスタックの代わりに合成の数学的定式化を使う純粋関数型言語
- Forth は1970年に 電波望遠鏡制御 用として最初に書かれた
- その後、組み込みシステム全般へ広く普及した
- Forth システムはブートストラップが十分容易で、多くのプログラマがそれぞれの目的に合わせて作った方言が数十種存在する
- PostScript は1980年代にプリンタで文書を記述する柔軟な手段として登場した
- PostScript は多くの面で Forth より制限されているが、グラフィックレイアウト関連の基本演算を言語に定義している
-
APL
- 言語のすべてが n次元配列
- 演算子は1〜2個の記号から成り、配列全体に対する高水準演算を行う
- 表現は非常に圧縮されており、記号列そのものが別名を付けなくても演算の標識になる
- 例として変数
xの平均計算は(+⌿÷≢) xの形 - APL, J, K が代表例
- 配列に対する高階演算は MATLAB, NumPy, R など多くの環境に部分的に輸出されている
- APL は1960年代に Kenneth Iverson が作った数学表記法から始まり、その後コンピュータに実装された
- 重い計算を行う人々の間で、その後もニッチな支持層を保ってきた
- 子孫言語 K は金融分野で非常に人気があった
-
Prolog
- プログラムは事実の集合で構成される
father(bob, ed).father(bob, jane).
- 変数によって他の事実から事実を導く 非接地の事実 も用いる
grandfather(X, Y) :- father(X, Z), father(Z, Y).
- Prolog ランタイムはこれらの事実と問い合わせを受け取り、結果を見つけるために探索を行う
- 事実定義の構造を適切に選べば チューリング完全性 が成り立つ
- Prolog では事実を構成する項がそれ自体で固有のデータ型であり、生成してからランタイムへ渡せる
- この点は Lisp のマクロや Forth のパーサ置換と似た位置づけ
- Prolog プログラムは本質的に探索であるため、データベース問い合わせのように 探索順序の調整 と成果のない経路の早期打ち切りを中心にチューニングする
- Prolog, Mercury, Kanren を含む
- この原型言語系統で実際のプログラミングの大半は Prolog 自体で行われており、コミュニティの統一性は非常に高い
- 1970年代にフランスの論理学者たちがプログラムを 一階述語論理 で表現できると気づき、実装の試みを始めた
- 1980年代の日本の第5世代コンピュータプロジェクトは Prolog に大きく賭けたが、プロジェクトの失敗とともに Prolog の評判も下がった
- それとは別に、数十年にわたり Prolog ランタイムを多くの場合で効率化する研究と新機能追加の研究が続けられてきた
- 数値制約 のような機能が加わり、制約論理プログラミングへつながった
- Prolog はニッチな領域で引き続き現れている
- Java の型検査は何年ものあいだ Prolog で実装されていた
- Facebook の初期ソースコード検索ツールも Prolog ベースだった
- プログラムは事実の集合で構成される
どう活用するか
- ほとんどのプログラマにとって、この言語群の一部または全部は非常に異質に見えるかもしれないが、それぞれが生み出す 思考経路 と新しい可能性のために時間を投資する価値がある
- ALGOL の観点では完全に違って見える2つの対象が、別の観点では些細な比較になることは非常によくある
-
優先順位
- すべてのプログラマは ALGOL系言語 を1つよく知っておくべき
- その次に Prolog 系言語である SQL の学習を勧める
- キャリアにおいて ALGOL の次に最も大きな効用をもたらす位置づけ
-
その後の拡張
- 上の2系統を身につけた後は、毎年、見慣れない原型言語系統の新しい言語を1つ学ぶやり方が長期的に有益
- 各系統で提案されている言語と順序は次のとおり
- Lisp: PLT Racket
- ML: Haskell
- Self: Self
- Prolog: Prolog
- Forth: gForth
- APL: K,
okを通じて使用
-
順序の調整
- 数値計算を多く行うなら K をより早く学ぶのが適している
- 組み込みプログラミングが多いなら gForth をより早く学ぶのが適している
- ただし順序そのものや、どの言語を正確に選ぶかは重要ではない
- Haskell の代わりに Standard ML や OCaml、PLT Racket の代わりに Common Lisp、gForth の代わりに Factor を学んでも問題ない
-
脚注に含まれる補足
- SQL を学んだ後でも Prolog 自体 はなお学ぶ必要がある
- 実際の使い方が SQL とかなり異なるため
- Forth を深く理解するには Forth 実装系を自分で作ってみるアプローチが一般的だという読者コメントがある
- Forth は1人で比較的短時間に一から実装できるほど小さいという言及
- gForth は ANS Forth を学ぶのに適した実装系
- 学習資料として McCabe の FORTH Fundamentals, Volume 1 に言及
- あわせて見るべき Forth として PygmyForth, eForth, colorForth に言及
- SQL を学んだ後でも Prolog 自体 はなお学ぶ必要がある
5件のコメント
面白いですね
大学のとき、ALGOL系とLisp、Prologで専攻科目を学んだり課題をこなしたりしていたので、記憶がよみがえりますね。
あの言語群は現代の主流プログラミング言語に多くのものを残しましたが、
その中では Forth だけが影響が少ないように見えます。
前置記法はともかく、後置記法でコーディングするのはかなり不便なんですよね
Hacker News のコメント
Tufts の PL の授業で、命令型、Lisp、ML、Smalltalk という最初の4系統の言語をそれぞれミニ版として実際に作ったことがあり、その内容が今では教科書にもなっていてうれしい。以前は Prolog のパートもあったのに外されてしまったのは残念
この記事の分類で1つだけ直すなら、Ruby は Algol 系というより明確にオブジェクト指向言語だと思う。Smalltalk の影響が大きく、標準ライブラリの名前も
mapよりcollectのようにその痕跡が残っている。Ruby は最初から最後まで何もかもがオブジェクトで、メソッド呼び出しもオブジェクトにメッセージを送る概念として理解するほうが自然だ。Python とよく比較されるが、進化の経路はかなり違っていて、今は似たようなエコシステム上の地点に収束した感じがする。私には Ruby のほうが Python よりずっと ぬくもりのあるアルパカ のように感じられるHello Worldレベルでは目立たなくても、基本型まですべてオブジェクトになった。OOP を嫌う人にtype(42)とdir(42)を見せると、整数ですらオブジェクトだという点を強調しやすい言語の系譜に 証明表現用言語 というカテゴリをもう1つ加えたい。Curry-Howard 対応によってプログラムがそのまま証明になる系統で、Lean が代表例だ。関数型の下位分類と見なすこともできるが、主目的が実行より検証にあるという点で別軸として扱う価値があると思う
最近、言語比較プロジェクトをもう一度見直したが、10文字に対する 3,715,891,200 個の signed permutation を並列に cycle decomposition するベンチマークだった。「原型言語」よりも、各パラダイムの 現代的な実装 の中で研究用プログラミングに実際に選べる言語を探したかった。性能だけでなく、AI の支援を受けやすいか、自分がコードを読んで考えやすいかも一緒に見ていて、AI のおかげで各言語をかなり深く最適化してみる一種の観光もできた。結果はここにまとめてあり、とくに F# が最上位に来たのはかなり意外だった
私も似たような記事をここに書いたことがある。Algol、Lisp、Forth、APL、Prolog には同意するが、革新的な関数型言語としては ML より少し早い SASL を入れ、オブジェクト指向の代表としては Self より先に出た Smalltalk を選んだ。さらに Fortran、COBOL、SNOBOL、Prograph まで、それぞれ別のやり方で流れを変えた言語だと思って一緒に含めた
この議論には 意味論的な系統 も加えたい。Verilog、Petri nets、Kahn process networks、dataflow machines、process calculi、reactive、term rewriting、constraint solver/theorem prover 系、probabilistic programming などだ。さらに既存の7分類にぴったり当てはまらないが、実際には本番運用段階に近い Unison、Darklang、temporal dataflow、DBSP のような言語も思い浮かぶ。やや反則にも見えるが、どれも von Neumann 的な機械モデルと並行する計算モデルだからだ。私は以前から 「私たちが知るあらゆる計算方法、von Neumann の先へ」 みたいな記事を書いてみたいと思っていた
1+1をADD(1,1)のような形に 書き換え れば自分の知っているやり方でパースできると気づいた。しかも regex を覚えるのを妙に拒んでいたせいでコードはかなり奇妙になり、同僚が「Andy ができるって言うんだから触らないでおこう」と言っていたのをまだ覚えている。別チームの人は regex で私のコードの20分の1くらいの長さで終わらせていたTU Delft で受けた「Concepts of programming languages」は、コンピュータサイエンスでいちばん好きだった科目だった。C、関数型寄りとして Scala、プロトタイプ概念として JavaScript を学び、そのおかげで数年後に Elixir を覚えるときずっと楽だった。また Unreal Tournament のエージェントを GOAL という Prolog ベースの言語で書く授業もあった。私は長いこと Prolog をどこで使えばいいのかピンと来なかったが、結局 LLM が生成したひどいパピアメント語の文を反復的に修正させる spellcheck を作るのに使うことになった
私は「異なる種類の言語を学ぶべきだ」という主張に賛成だ。OCaml を学んで初めて、関数が本当に数学的な関数のように感じられたし、Mathematica は式そのものを入力として見る習慣を身につけさせてくれた。PostScript の逆ポーランド記法は、単純な算術を超えて考え方そのものを配線し直したような感覚だった。ただし Java、C#、C++、Python、Ruby のどれを選んでも同じだという主張には賛成しない。クイックソート実装くらいが目的なら似たようなものかもしれないが、実際に何かを作ろうとする人にとっては、言語選択は 昼と夜ほど大きな差 を生む。3D ゲームを作りたい人に Ruby を、探索的データサイエンスやディープラーニングをやりたい人に Java を最初に渡したら、やる気をそがれるかもしれない
この記事を見て Bruce Tate の 7 languages in 7 weeks を思い出した。私もあの本で Erlang に初めて触れた。ただ、歴史的に COBOL と Fortran を Algol 系に入れるのは少し無理があると感じるし、それでも歴史とは本来ある程度還元的に整理されるものだと思い出させてくれる
関連して、以前の HN 議論もあった。以前の議論も一緒に見ると文脈の把握に役立つ