(私が想像する)純論理型言語はいわゆるパターンマッチの所で組み合わせ爆発が起こり得るのだと思います。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言語(高級アセンブラ)みたいな言われ方をすることがあるのは、ここに起因していると思います。