参照セルと純粋未定義変数セル

論理型言語で特徴的な実装レベルのデータとして、 「参照セル」(以下REFセル)がある。これは、言語仕様上は 全く現われない、「不可視の」データである。例えば、図2.3に 示されるデータ構造は全て共にATOM: fooとして扱われる。 このデータにはREFなるタグが付加される。図にも現われる連続するREFのつながり (言語仕様上は全く意味のないデータ群)をREF鎖と呼ぶ。

  

Figure 2.3: 参照セルの例

このようなデータが必要な理由は、論理型言語特有な操作である 「単一化」、および「論理変数」と「具体化」を実装するためである。     まず、論理変数を実装するためには、まだいかなる項にも具体化していない 項、「未定義変数」を実装する必要がある。この未定義変数の実装のために 独立したタグを用いたりする流儀もあるが、タグ節約も兼ね、 KLICではREFタグで、「自分自身」を参照した構造を用いる(図2.4(1)参照)。 この構造を「純粋未定義変数」と以下で呼ぶ。

今、X = [a|_] で、Yは純粋未定義変数であることが保証されている時に、 X=Y なる操作を行ったとする。すると、純粋未定義変数Yは[a|_]に具体化 されるが、実装レベルでは、これは純粋未定義変数Yの ポインタ部分がXを実現するデータ を指すように書きかえられる、ということが行われる(図2.4(2)参照)。 ここで挙げたような具体化操作がなんども行われると、先に示したREFの連鎖が できることもある。

  

Figure 2.4: 純粋未定義変数の実装と単一化