4389. 金曜日

　ややくどい文章になってしまいました。が、読み直しても今の私の知識ではこれ以上簡易に説明することは難しいです。後もう少しの予定です。

　昨日と今日はやや寒くて、来週からは気温が上昇するとのことです。春らしい感じは少し前からあります。
　学生が春休みのためか通勤電車が空いています。座席は埋まっています。帰宅途中の駅で、多分有名電子系の製造業の社員が乗ってきて、社内事情は言いませんが何だか楽しそうでした。儲かっている感じです。
　株価は年初以来急激に上昇していて、さすがに一旦落ち着くのかと思ったらまた日経平均が4万円台に上昇しました。どこまで行くのかな。

　半導体業界のごく一般向けの解説書を見てみました。さすがに昔のことはそれほど詳しくは出ていません。日本の半導体の復活の感じはいろいろとあるらしく、米国も自国生産を強化してきたみたいなので、ここしばらくは安定感が続くと思います。

　注文していた「LISP 1.5 Programmer's Manual (1962年)」が届きました。オンデマンド版で国内印刷のようです。B5版程度の大きさで100ページほどです。後半は付録扱いですが、主な関数はこちらに定義が書いてあります。
　いや懐かしいというか。手元にある1974年のbit臨時増刊「プログラミング言語」(共立出版)の中の一章がLISPで、このLISP 1.5がメインの解説になっています。ん、邦訳があって、書名は思い当たりますからあとで書庫を探してみます。最近、事情があってやや奥にしまってあるので。
　それにしても米国に比べて10年以上も遅れています。産業にあまり関係ないと当時は思われていたのでしょう。昨今の2度目の人工知能ブームなど知るよしも無く。

4388. 論理型言語、続き^2

　(私が想像する)純論理型言語はいわゆるパターンマッチの所で組み合わせ爆発が起こり得るのだと思います。PROLOGではホーン節に分解しカット述語と合わせることにより、組み合わせ爆発を防ぎます。しかし、ここで一階述語論理の構造が保たれているかどうかは大問題だと思えますが、すっきりした解説は見たことが無い、と思っています。

　ホーン節への分解とカット述語は、PROLOG解説が必要となった時に改めて説明すると思うので、一旦棚上げします。要は、この両者でLISPのcond形式、つまりマッカーシーの条件式の形になるのがミソです。
　まあ、これだけまとめてやっと今頃になって、LISPがなぜ逐次言語的なのかが分かった気がします。つまりマッカーシーの条件式が逐次実行だからです。PROLOGも同様。

　とすると、PROLOGとLISPの違いは束縛変数の扱いのわずかな違いだけになります。
　PROLOGでは未束縛、つまり値が決まっていない変数を引き継ぐことが出来て、どこかで値が決まると別の場所の同じ変数も値が決まります。面白いのは逆が効くことで、束縛が無かったことにすることが出来て(バックトラック)、その場合は別の場所の同じ(単一化された)変数の束縛も解かれます。この機構を実現するために、PROLOGでは他の言語に無いトレイルスタックと呼ばれる記憶域が用意されます。

　トレイルスタックの動作に関しては、PROLOGの標準的なインタプリタの解説、Warren Abstract Machine (WAM)の論文(1983年)が公開されていて、詳細が分かります。私はこの論文は持っていますが、まだ実際のインタプリタを作っていないので、実感はつかめていないことをお断りしなければなりません。

　このトレイルスタックの効果が外部に唯一現れるのが、差分リストの技法、だと私は思っています。普通のLISP流のリストでは頭にアトムまたはリストをくっつけ(cons)、あるいは頭からアトムまたはリストを取り出す(carとcdr)だけの動作になります。単純リストと呼ばれています。LIFO (後入れ先出し)、つまりプログラミング解説で言う一般的なスタックの動作です。
　PROLOGでは差分リストが完全に組めて、LIFOだけでなく、FIFO (先入れ先出し)の待ち行列とかキューと呼ばれる動作が可能となります。つまりリストの最後尾にアトムまたはリストをくっつけることが(LIFOに追加で)出来ます。FIFOは一般的なOSのファイルシステムでは順次ファイルに相当し、入出力ストリームやパイプ(プロセス間通信)と同等です。

　LISPでリストをくっつけるにはappend関数を用います。しかしくっつける方のリストはコピーされます。コピーせずにポインタを付け替えるだけのnconc関数が別に用意されていますが、これは純LISPの範囲には無く、くっつけられた方のリストの変化を防ぐには、くっつけた方のリストの操作ができなくなる、という重大な「副作用」があり、LISPでは効率が良いものの要注意の関数となっています。ちなみに、私の感触では今はnconc関数ではなくsetfマクロを使うのがかっこいいみたいです。

　間の悪いことに、nconc関数(相当)を使いこなすのが一流のLisperへの登竜門になっている、と思います。人工知能のアセンブラ、だったか、FORTRANに対するC言語(高級アセンブラ)みたいな言われ方をすることがあるのは、ここに起因していると思います。