致命的な選択

以前の記事 （ en ）で、1982年にファンファーリンギングの下で​​開始され、1992年に論理プログラミングを取り入れて撤回された、第5世代の日本のコンピューターシステムプロジェクトの歴史について話しました。 この中で、より明白なLispではなく、第5世代システムの言語としてPrologがどのように選ばれたかについてお話します。 特定の言語の支持者を形成できる人々の現象に興味があります。 この記事で説明できるといいのですが。



用語について。 論理プログラミングは、論理文を使用して手順とデータを表し、受け取ったステートメントに基づいて計算を実行する方法です。 Prologは、これら2つのアイデアに基づいたプログラミング言語です。 言語と方法の両方が、第5世代システムで主要な役割を果たしました。



1981年、プロジェクトを開いた会議で、フチは論理プログラミングを主なプログラミング方法論と呼びました。 1992年の決勝戦で、古川は1976年に東京の電気技術研究所（ETL）（後に第5世代システムプロジェクトを立ち上げた）のチームがLispで豊富な経験を持ち、プロローグは彼女にはまったくなじみがなかったことを思い出した。 1976年、これは全員に当てはまりました。マルセイユ以外では、プロローグについて知っていたのは2、3の研究所だけでした。



974は1974年に川崎^[7]の記事を読んだ後、論理プログラミング^[1]に興味を持ちました。おそらく、1976年にスタンフォード研究所を訪れたときに古川がPrologを検索するようになりました。マルセイユの外。 1974年、デビッドH.D. ウォーレンはエディンバラにコピーを取りました。 そして1976年に、ハリー・バローはエディンバラからコピーをスタンフォード研究所に持ち込みました。 ウォーレン^[1]は、 「ハリーは自分でシステムを起動できず、古川のコピーを渡しました」と語りました。 1976年に東京ETLで、古川と他の数人の研究者がPrologの実験を開始しました。 米国はプロローグウイルスの媒介として行動し、感染自体を回避しました。



ETLでの仕事の結果として、古川はいくつかのプロローグデータベースインデックス作成プログラムを実証しました。 明らかに、肯定的な結果により、ETLはDavid H.D.からDEC-10のプロローグの実装を取得することができました。 ウォーレン。 古川は次のように書いた^[2] ：

DEC-10 PrologでRubik's Cubeアセンブリプログラムを作成しましたが、効率的で、比較的短時間（約20秒）で問題を解決しました。 このタイプのエキスパートシステムでは、意思決定メカニズムは、Prologの末尾再帰を使用して効果的に実装されます。 この実験の後、プロローグは知識処理言語であると確信しました。

プロローグの歴史については、アラン・コルメロアとフィリップ・ロッセルの「プロローグの誕生」 ^{[3]に目を向けました} 。 最初のステップは1971年にエクスマルセイユ大学のColmeroer率いるグループによって行われました。 自然言語の処理専用に使用されるいくつかの予備バージョンを作成した後、1973年に「最終バージョン」が作成されました。 川崎の影響で、文の論理は言語になり、特定の形式の文が手続きを呼び出すためのメカニズムとして機能しました。 このバージョンは最初の「プロローグ」と呼ばれ、自然言語処理以外のタスクに使用されました。 1974年初頭、マルセイユへのヴァレンの訪問の後、プロローグのコピーがエディンバラに行きました。 エジンバラからヨーロッパのいくつかの機関（ブダペスト、ルーベン、リスボン）とカナダに急速に広がりました。



1974年から1977年にかけて、数多くの魅力的な実験が行われ、マルセイユで始まった作業が続けられました。 リスボンのヘルダー・コエーリョは、「プロローグのやり方」という本のプログラムを集め始めました。 1975年、ウォーレンはDEC-10 PrologでPrologコンパイラの作成を開始しました。 1977年に完成したとき、1973年のマルセイユ通訳で大きな改善が達成されたことが判明しました。 ウォーレンと彼の同僚は、それをコンパイラLispと比較することを敢えてしました。それは芸術作品として完璧であり、興味深い結果を得ました。 リストは、Lispの場合よりも30〜50％高速に反転されました。 結果は驚くべきものだった、なぜなら リストは、他の用語と同様に論理用語に変換され、統一的に処理されます。 シンボルの微分（データに依存）は、Lispよりも1.1から2.6倍速く実行されました。 1977年、Lispは18歳、プロローグは6歳で、1971年から1977年までの開発に取り組んだ人はほんの一握りでした。



次の例は、概して、役に立たない。 それらは、プロローグの魅力的な性質を示すために選ばれます。



述語「move」のプログラムは、ムーブ（X1、Y1、X2、Y2）を記述するときに、馬がセル（X1、Y1）からセル（X2、Y2）に移動できることを意味するとします。

適切なプログラムを持っている、あなたは尋ねることができます

?- move (U,U,V,V).



これは、「1回の移動で馬がセルの1つに斜めに行ける」ことを意味し、「いいえ」という答えを得ることができます。



尋ねられたとき

?- move(U,U,X,Y),move(X,Y,V,V).



「騎士は2回の動きで斜めに動くことができます」という意味で、必要に応じてすべての動きで「はい」と答えます。 次はプログラムです

move(X1,Y1,X2,Y2) :- diff1(X1,X2),diff2(Y1,Y2).

move(X1,Y1,X2,Y2) :- diff2(X1,X2),diff1(Y1,Y2).



% diff1(X,Y): X Y 1.

diff1(X,Y) :- succ(X,Y).

diff1(X,Y) :- succ(Y,X).



% diff2(X,Z): X Z 2.

diff2(X,Z) :- succ(X,Y),succ(Y,Z).

diff2(X,Z) :- succ(Z,Y),succ(Y,X).



% succ(X,Y): Y X.

succ(1,2). succ(2,3). succ(3,4). succ(4,5). succ(5,6). succ(6,7). succ(7,8).



別の例。 次のリストに含まれる27桁のセットがあるとします

[1,9,1,6,1,8,2,5,7,2,6,9,2,5,8,4,7,6,3,5,4,9,3,8,7,4,3]

[1,9,1,2,1,8,2,4,6,2,7,9,4,5,8,6,3,4,7,5,3,9,6,8,3,5,7]

[1,8,1,9,1,5,2,6,7,2,8,5,2,9,6,4,7,5,3,8,4,6,3,9,7,4,3]

[3,4,7,9,3,6,4,8,3,5,7,4,6,9,2,5,8,2,7,6,2,5,1,9,1,8,1]

[7,5,3,8,6,9,3,5,7,4,3,6,8,5,4,9,7,2,6,4,2,8,1,2,1,9,1]

[3,4,7,8,3,9,4,5,3,6,7,4,8,5,2,9,6,2,7,5,2,8,1,6,1,9,1]



各桁d = 1、..、9の条件では、3つのdの出現があり、dはdの位置で互いに分離されています。 これを解決するには、かなり複雑なクエリが必要です

?-equals(List,

[_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_]),

sublist([9,_,_,_,_,_,_,_,_,_,9,_,_,_,_,_,_,_,_,_,9],List),

sublist([8,_,_,_,_,_,_,_,_,8,_,_,_,_,_,_,_,_,8],List),

sublist([7,_,_,_,_,_,_,_,7,_,_,_,_,_,_,_,7],List),

sublist([6,_,_,_,_,_,_,6,_,_,_,_,_,_,6],List),

sublist([5,_,_,_,_,_,5,_,_,_,_,_,5],List),

sublist([4,_,_,_,_,4,_,_,_,_,4],List),

sublist([3,_,_,_,3,_,_,_,3],List),

sublist([2,_,_,2,_,_,2],List),

sublist([1,_,1,_,1],List).



ただし、プログラム自体は非常に小さく、一般的な述語のみが含まれています。

% sublist(X,Y) X Y



sublist([],List).

sublist([X|Xs],[X|Ys]) :- append(Xs,_,Ys).

sublist(List,[Y|Ys]) :- sublist(List,Ys).



append([],Y,Y).

append([U|X],Y,[U|Z]) :- append(X,Y,Z).



equals(X,X).



プロローグの初期の歴史は、私にとって非常に興味深いようです。ゼロから6年のほんの数人がそれをエレガントで強力で効果的な言語に発展させました。 Lispの初期の歴史はそれほど面白くありません。 1950年代、マッカーシーは顧問プロジェクトに言語を選択しました。 候補者は、IBMのBacusチームによって開発されたIPL-V NewwellとSimonおよびFortranコンパイラーでした。 IPLには、リストで表される柔軟なデータ構造という利点がありました。 一方、McCarthyは、その反復メカニズムのためにFortranが好きでした。 そこで彼は、リストの操作をサポートするFortranコンパイラーのバージョンであるFLPL（Fortranリスト処理言語-Fortranリスト処理言語）を作成するための実験を開始しました。 Fortranでのユーザー定義関数のサポートは、文書化されていない実装時間の長いプロパティであり、関数本体は1行に制限されていたことを思い出してください。 当然のことながら、マッカーシーは自分のリスト処理言語で作業を始めました。 1958年11月、通訳はすでにMITで働いていました。 すぐに、現在Lispとして知られている言語に進化しました。これは、プロジェクトの説明の作業の副作用でした。



この言語の特徴の1つは、その普遍性でした。つまり、原則として計算されるすべてを計算することは可能でしょうか。 ユニバーサルチューリングマシンのプログラムがデモンストレーションとして使用されました。 多くの人々は、マッカーシーが再帰関数の理論から普遍的な関数を好んだという事実が好きです。 それまでは、この理論は自然数のセット内でのみ使用されていました。 McCarthyは、セットの自然さは制限ではなく、列挙されたセットで機能することを指摘しました。 これらすべてが、シンボリック式（S式）上の関数の汎用関数につながりました。



汎用関数は、引数として関数の説明とその引数の説明を取りました。 その結果、彼女は引数で関数を実行した結果を返しました。 このような関数を作成するには、関数定義の構文を変更する必要がありました。 データを使用して説明する必要がありましたが、現在はS式です。

... EVALについて説明し、それについて公開した後、Steve Russellは、なぜEVALをプログラムして通訳を作成しないのかと尋ねました。 理論と実践を混同しないでください。EVALは計算ではなく読み取りのためです。 しかし、彼は続けて通訳をしました。 彼は私の記事のEVALを704行のマシンコードにコンパイルし、バグを修正し、Lispインタープリターについて実際にそれを伝えました。 一般的に、その瞬間から、Lispは私たちが今日知っている形式、S式の形式（1974年のMcCarthyとの会話である「The Lisp Story」の転写のStoyan ^[5]によって強調された形式）を獲得した。

McCarthyは彼の記事で、S-expressionの小さな操作セット、ATOM、EQ、CONS、CAR、CDRについて説明しました。 それらに、彼は論理関数としてQUOTEとCONDを追加しました。 LABELとLAMBDAのステータスは非常に興味深いものです。EVALはリストを書き換えてリストにアトムとして表示するため、LABELとLAMBDAがプロセスで使用されます。



普遍的なマッカーシー関数は、計算手法のエレガントな公理化と考えることができます^[8] 。 しかし、理論的な研究はLispになりました。 汎用関数により言語が変更され、データだけでなく関数もリストになりました。 ラッセルのインスピレーションとプログラマとしての彼の能力のおかげで、普遍的な機能は通訳になりました。



なぜ人々がPrologに恋をするのかという質問に答えるために、私はいくつかの例よりも良いものを思いつきませんでした。 Lispにはもっと良い方法があります。ユニバーサルEVAL関数とその分離不可能なAPPLY関数を調べてください。 それらは、Lispの説明の最初にあります。 これがポンツasinorum ^[9]です。研究を放棄した人々は、まさにこの場所でそれを放棄したように思えます。 橋を渡った後、初心者は最後まで旅を続け、Lispの支持者になります。



LispとPrologの美徳の類似点は、常に議論の対象となっています。 LispでFortranプログラムを書いている人や、テンプレートをサポートしたPascalなどのプロローグを使用している人の作成を無視します。 要するに、マッカーシーが「ポルノ番組」と呼んだものすべて^[4]は無視されるべきです。 この議論では、Zen言語の知識で書かれたコードのみを検討する価値があります。 Zen Prologの説明は別の機会に残します。 Lispの場合、次のようになります。



現代の観点から、マッカーシーが行った主なことは、仮想マシンの定義です。 一般に、彼は思考実験中に単に説明目的でそれを定義しました。 したがって、彼は論理的な観点から可能な限り単純化する余裕がありました。リストで動作する7つのプリミティブのうち（リストとS式の違いは無視）、頭と尾だけで構成されています。 驚くべきことに、これらはすべて、当時実装できる言語に成長しました。 さらに興味深いのは、非常に単純な仮想マシンが何十年にもわたってメモリとプロセッサの速度を向上させてきたことです。 この仮想マシンに基づいて、すべてのEVAL / APPLYインタープリターが構築されます。これは、Lisp入門コースで見つけることができます。



初心者がZen of Lispを学ぶとすぐに、基本的なインタープリターの限られた機能の拡張としてプログラムを書くことは自然になります。 そして、これらの7つのプリミティブは埋もれておらず、通訳が終了するとすぐに見えなくなります。 それどころか、それらはユーザーコードでは非常に一般的です。 ギルバートは集合論の反対者に言った：「誰も私たちにカントールによって作られた楽園を去ることを強制しないだろう。」 LispersはMcCarthyによって作成された楽園に関して同じことを経験します。



第5世代のプロジェクトは、Lispを知っており、Prologを興味をそそる斬新さであると認識する人々によって開始されました。 新世代のコンピューターのビジョン（またはmi気楼）は、論理計算と並列性に基づいていたため、意見のバランスがPrologに移行しました。 もしそれが違っていたら、第5世代システムの運命はLispに何の影響も及ぼさなかっただろう：それはすでに広まっていた。 しかし歴史的に、Prologの脆弱で初期の希望は、目標を達成しなかった第5世代システムの崩壊とともに崩壊しました。