4387. 論理型言語、続き

　本日は春分の日で国民の祝日です。ペンディングになっているマイコンボードの半田付けを予定していましたが、純LISPが気になってしまって、そちらの調べごとをしています。
　wikipediaの日本語版に純LISPの項目があって、外部リンクにLISPの創設者のマッカーシーによる有名な論文があり、とても綺麗なpdfが得られます。それと、ごく初期の処理系、LISP Iのマニュアルと。どちらも1960年のものです。

　IBM 704という当時最先端のコンピュータが用いられていて、演算素子は真空管、36bitのワードマシンで、浮動小数点演算機構が付いているそうです。記憶素子は信頼性の高いコアメモリで、そのLISP Iのマニュアルには32Kワードと書いてありますから、現在で言うと144Kバイトです。
　私の経験で申し訳ありませんが、LISPは64KB程度のメモリではほんのお試ししかできず、128KB程度から気の利いた応用が出来ますから、非常にラッキーな開発状況だったと思います。さすがMITです。

　LISP IではできたばかりのLISPを手慣れたプログラマが素晴らしいシステムに仕上げていて、こちらもラッキーでした。科学技術用の計算機言語のFORTRANは莫大な費用で開発されたと聞きますから、LISPも本来ならば同程度の予算が必要だったはずですが、おそらく大学で開発されています。

　ただし、その2文献は、FORTRANやC言語しか知らない方だとかなりの難物に見えるはずです。Common LISPである程度のプログラムが書ける方には、慣れるまでちょっとかかるでしょうけど、何とか解読できると思います。

　数値計算が得意なようには見えないので、何に役立つのか、というと、記号処理でリスト処理ですから、コンパイラの構文解析のような感じの処理に役立ちます。論文ではエキスパートシステムの開発用に設計された、とあります。純LISPで書かれた純LISPインタプリタ、apply関数が万能チューリングマシンに相当する、と書いてありますから、計数型電子計算機の理論上の能力を知る近道になります。

　今のプログラマは構造化プログラミングに慣れているでしょうから、if文もwhile文も無い純LISPでどうやってプログラムを組むか、が最初の問題になります。論文の最後の方にフローチャートをLISPで動作させるには、の項目があります。
　cond形式が純LISPでは唯一の制御構造です。多重分岐の構文ですから、if文はすぐに分かるでしょう。繰り返しは再帰で行います。現在の処理系はまず間違いなく末尾再帰の最適化を実施しますから、(うまく書けば)機械語では単純なループになります。逐次実行は、condの条件節が逐次実行されるのを利用します。今のLISPではcondの実行節に複数の関数を並べることが出来て、もちろん逐次実行されますから、逐次実行用のprogn形式が必要な場面は少ないはずです。

　あと、数値計算はあるにはあるものの、配列がありません。代用にリストを使うことは出来ますが、何となく効率が良くない感じがします。近代LISPでは配列が用意されていると思います。まあ、普通はそんな場合にはFORTRANやC言語を使うでしょう。

4386. 論理型言語

　第五世代コンピュータの前半で話題となった論理型計算機言語のPROLOGは、私の考えでは第二世代の論理型計算機言語と思っています。

　ここでいう第一世代と第二世代は、LISPで言うと純LISPと、計算に適したLISP 1.5だったか、の違いに相当するものです。

　純LISPでは、単純データ型はアトム(記号)だけ。ただし、リストで任意の複合データ構造が組めて、その組み方はLISPの本には必ず出てくると思います。これらはS形式と呼ばれる形で表され、LISPの計算対象です。
　純LISPのプログラム遂行、つまりアルゴリズムの記述のためにM形式があります。

　チューリング機械で気の利いたプログラミングはかなり困難なので、純LISPがその代用となると思います。私はまだ詳細を詰めていないので、完全に同等だとの確信はありません。しかし、上述の純LISPの範囲である程度のプログラムを組むことは、例えば簡単なゲームを私は書いてみせることが出来ると思っています。

　ここで、そのM形式を説明しようと一瞬思ったのですが、LISPの教科書の前半になってしまってかなりの分量が予想されるのと、さっきLISP 1.5のマニュアルをネット販売で注文してしまって、それを見てからまとめて書いた方が良いような気がするので、延期します。あまり面白い話にならないようなら、話の流れからは少し外れるので本ブログでは取り上げないかもしれません。

　この純LISPに相当する、PROLOG開発のきっかけとなった純粋(?)な論理型計算機言語があるはずなのですが、なぜか詳しい資料が見つかりません。なので私の想像が混じってしまいますが、多分、一階述語論理の束縛変数を残したまま命題論理に変換したものを、いわゆる横型探索で解を求める、ものだと思っています。

　なお、LISPの勉強を開始したいと思った方は、今は普通にCommon LISPの処理系を導入して、それに沿った解説書や教科書を選んだ方が良いと思います。初期のLISPは概念と特有の記述と計算機の都合がかなり錯綜していて、FORTRANから入門した私には何が何やらで、実働する処理系も身近に無く、最初はさっぱり分からなかった記憶があります。