第五世代コンピュータの前半で話題となった論理型計算機言語の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から入門した私には何が何やらで、実働する処理系も身近に無く、最初はさっぱり分からなかった記憶があります。