マイ・Guarded Horn Clauses の中間表現言語

マイ・GHC はマルチスレッドで動く並行論理型言語を目標として作成中の自分専用 Guarded Horn Clauses(GHC) 処理系です。

Warren't Abstract Machine を参考に、マイ・GHC の中間表現言語（My GHC Intermediate Representation Language、略して マイ・GIRL ）を設計します。

# 制限

シングルスレッド・シングルタスクである程度動く処理系ができているので今後大きく仕様が変わることはないとは思いますが、あくまでも暫定なので、この文書の記述は今後変わる可能性があります。

# 方針

以下の方針で設計します。

## なるべく元の GHC ソースコードに一対一対応できるようにする

GHC ソースコードから全くかけ離れた中間表現にすると理解が困難になります。
またコンパイラの作成もそれだけ難しくなります。

GHC ソースコードから中間表現が直截に書き下せる、あるいは中間表現を見て元の GHC ソースコードが想像できる程度のものにとどめます。

## WAM をベースにする

あまり独特な体系だと自分でもなにを基準に考えていいのかわからなくなるので、WAM をベースとしてそこから大きくかけ離れないものとします。

WAM はすこぶる良い設計なので、可能ならばそのまま使いたいのですが、今回目指している目標にはそぐわない部分、あるいは自分の理解の及ばない部分があります。このため、WAM のドキュメントを横目に見ながら自分なりに解釈しなおして新たな命令セットを作ることにしました。

## マルチスレッドで動くことを想定した設計とする

現在はシングルスレッドの処理系しか動かしていないので、マルチスレッドで思ったとおりに動かないかもしれませんが、なるべくマルチスレッドで動くように考えてみたいと思います。

# 前提とする処理系

## 仮想マシン

実行コンテキスト一つにつき、一つの仮想マシンを生成します。
仮想マシンは一連のゴール呼び出しを再帰的に実行していきます。

当該コンテキストの一連の処理が終わると、ゴールキューからゴールを取り出して新たなコンテキストとして実行する、ということを繰り返します。

シングルスレッド実装の場合には、一つの仮想マシンがゴールキューが空になるまでゴール処理を繰り返します。

マルチスレッド実装の場合には、複数の仮想マシンがゴールキューからゴールを取り出して実行することを繰り返します。

ゴールキューへのゴールの投入は、

- ソースコード上で明示的に並列実行を指示されてサブゴール呼び出しされた場合
- 変数具体化待ち状態のゴールが、当該変数の具体化によって再実行される場合

の２種類があります。

## レジスタ

仮想マシンはレジスタマシンとして動作します。

ゴール処理においては、三種類のレジスタを使用します。

- 入力レジスタ - ゴールの引数が与えられるレジスタ
- 一時変数レジスタ - ゴールの実行時に必要となるワークエリア
- 出力レジスタ - サブゴール呼び出し時に引数として与える内容を置くレジスタ

これらの実体は一つのレジスタファイル（実体はタグ付きポインタの配列）上に置きます。
ゴール呼び出し時には入力レジスタに値が設定されて呼び出されます。

一時レジスタは WAM と同様に、入力レジスタと同じインデックスでアクセスできます。

サブゴールを呼び出す場合、サブゴール実行後にも継続して必要となる一時レジスタを書き換えてしまわないように、それに続く領域を出力レジスタとします。

出力レジスタをサブゴール引数として値を設定した後、出力レジスタ位置を入力レジスタ位置に切り替えてサブゴール処理を呼び出します。

出力レジスタよりさらに後ろの領域は当該ゴール実行中も実行後も必要ないため、出力レジスタに書き込むリストや構造体を組み立てるときのスタック領域として利用できます。

逆に入力レジスタより前の領域は自身をサブゴールとして呼び出したゴールの領域なので勝手に操作してはいけません。

## ヒープ

レジスタが参照・操作する変数は全てヒープ上のタグ付きポインタとして存在します。

各仮想マシンは一つのヒープを専有しており、このヒープの先頭から後ろに向かって変数を割り付けて払い出していきます。
ヒープを使い切った場合には、新しいヒープを確保してその先頭から割り付けていきます。

一度変数として払い出した部分は他スレッドからアクセスされる可能性があるため、所定の単一化（ユニフィケーション）操作に従った更新のみが許されます。

ガベージコレクションは、現在実行中の仮想マシン、および実行キュー上に繋がれた仮想マシンのレジスタをルート要素としてヒープ上のタグ付きポインタをマークしていき、またマークされた変数に紐づく待ちレコードに登録されたゴールレコードから参照されたヒープ上のタグ付きポインタへ、という具合にマークしていきます。
最終的には、マークされたタグ付きポインタを新しいヒープにコピーして、古いヒープを破棄する、ということでゴミ捨てを行います。

GHC の特性上、変数の払い出し順序と参照関係とは必ずしも一致しません（例えば、未完成ストリーム）。
このため、世代別 GC とは相性が悪いことが想定されます。

## 具体化待ち合わせ

ガードチェック時に参照が必要な変数の値が具体化していなかった時には、当該変数の具体化を待ち合わせて再実行する必要があります。

通常の未具体化変数はタグ REF による自己参照ループなのですが、具体化待ち合わせゴールの登録が必要な場合には、次の図のようにタグ SUS に続くアドレスがゴールレコードの循環リストとなります。

![suspend.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/412308/bb76c272-1a3b-af52-c35d-72bd4d9288f6.png "GIRでの中断構造")


Inside KLIC
https://github.com/tadashi9e/KLIC/blob/master/klic-3.011/documents/inside/master2.pdf
を読むと下の図のようにタグ REF だけで同じ構造を実現していますが、タグ REF だけだとどちらの REF にリストが続くのかがわからなくなりそうなのでタグ SUS を新たに設けています。

![suspend_klic.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/412308/4331157c-8a5d-79af-0a15-11908b12d73f.png "KLICでの中断構造")


タグ SUS で示される未実現変数に対して具体化が発生した場合、当該変数に登録されていたゴールレコード全てをゴールキューに投入します（これを効率的に実現するために、ゴールキューもタグ SUS に続くリストと同じ循環リスト構造にするべきでしょう）。

ゴールキューに投入されたゴールレコードは、手の空いた仮想マシンによって取り出され、再実行されます。

## 制御スタック

サブゴール呼び出しをゴールキューへの投入で実装すれば各ゴールの親子関係についてはあまり考えなくて済むのですが、今回の設計では性能を重視してサブルーチンコールの形でサブゴールを呼び出せるようにします。

サブルーチンとして呼び出されたサブゴールの終了を待ち合わせて処理を再開するために必要な情報をスタック上で管理することにします。

スタックで保持しなければならない（ゴール処理毎に保存しなければならない）情報は以下です：

- サブゴール呼び出し正常終了時のジャンプ先プログラムカウンタ位置
- サブゴール呼び出し異常終了時のジャンプ先プログラムカウンタ位置
- ガード処理中か否かのフラグ
- レジスタ上の入力変数オフセット
- レジスタ上の一時変数オフセット

# 命令セット

## 概略

命令は大きく分けて、以下に大別できます。

- 制御命令
- サブゴール呼び出し命令
- 変数操作命令
-- 一時レジスタ設定命令
-- 出力レジスタ設定命令
-- 単一化命令
-- 入力レジスタチェック命令


## 制御命令

### goal(Goal)

ゴール処理の先頭に置かれる命令で、トレース情報に与えるゴール名 Goal を引数とします。

また、goal 命令実行タイミングでのプログラムカウンタを保存しておき、変数具体化待ちによる再実行発生に備えます。
変数具体化待ちにより再実行されるときには、goal 命令の置かれた位置から再開されることになります。

### require(N)

goal 命令に続いて置かれる命令で、当該ゴール処理で必須となる消費レジスタ数を引数とします。
引数レジスタ位置 IN[N] 以降は当該ゴール処理において書き換えても構わない領域、スタック領域として利用します。

### try_guard_else(Label)

ガード処理の開始部分に置かれる命令で、後続するガード処理で fail したときのジャンプ先アドレス（次の候補節の開始アドレス）を設定します。

### try_guard_else_suspend

try_guard_else 命令で設定されていたジャンプ先アドレスを取り消します。

これ以上異なる候補節がないガード処理の開始位置に置かれる命令です。後続するガード処理で fail した場合には全てのガードチェックに失敗したとみなします。

### fail

ガードチェック失敗あるいはボディ部でのアクティブユニフィケーション失敗を記録します。

- try_guard_else で失敗時の次候補が指定されていればそのアドレスにジャンプします
- try_guard_else_suspend が実行されていた場合には後述のサスペンド処理を行います
- activate が実行されていた場合にはランタイム例外を送出します（ガード処理中の親から呼び出されたゴールの場合は除く）

try_guard_else_suspend が実行されていた場合のサスペンド処理の詳細は以下です：

1. ガードチェック中の未実現変数参照が記録されていない場合には、実行時例外を送出する。
2. ガードチェック対象だったのにチェックできなかった未実現変数が記録されているか調べる。記録されていれば、当該未実現変数全てについて現在実行中ゴールを再実行対象として登録し、呼び出し元ゴールに処理を返す。

サスペンド処理を行った場合、当該ゴール処理は中断して、呼び出し元ゴールに戻ります。

呼び出し元ゴールがレジスタウィンドウ上にない（現在実行中のゴールが一番根本にある）場合には、戻る先の処理がないので仮想マシンを終了します。

いずれ待ち対象変数のいずれかが具体化したときにゴールは再実行されます。

待ち対象である変数のいずれも具体化することなく参照もされなくなったならばガベージコレクションで破棄されてしまいます。この場合、待ちレコードも同様にガベージコレクションによって破棄され、当該ゴールは永久に実行されません。

### activate

ガードチェックに成功した（コミットバーを通過した）ことを表します。

親ゴールのガード処理から呼び出された場合には、
- ガード実行中状態を継続します。
- 失敗時継続情報を suspend にします。

そうでない場合には、

- 現コンテキストのガード実行中フラグをクリアします。
- 未実現変数参照記録をクリアします。
- try_guard_else / try_guard_else_suspend で設定されていた失敗時継続情報も削除し、fail が発生した場合には例外をスローするように設定します。

### proceed

当該ゴール処理に成功し、かつ、末尾呼び出し対象となるサブゴールがないときに置かれる命令です。

呼び出し元ゴールがレジスタウィンドウ上にあれば、return 命令と同様に呼び出し元ゴールに処理を戻します。
なければ当該仮想マシンインスタンスを破棄して処理を終了します。

### return

proceed のサブセットで、ガードチェック用の組み込み述語において（seq-call で呼び出された側が）呼び出し元へ復帰するために用いる命令です。

## サブゴール呼び出し命令

サブゴールの呼び出し方として以下を用意します。

- seq-call : 逐次的呼び出し（ガードチェック）
- par-spawn : 並列呼び出し（サブゴール呼び出し）
- tail-exec : 末尾呼び出し（サブゴール呼び出し）

### seq(N)

call 命令と共にガード部のサブゴール呼び出しに用います。

述語を呼び出すに先立って、出力レジスタ位置を設定します。
IN[N] の場所を出力レジスタ OUT[0] とします。

### call(Label)

seq 命令と共にガード部のサブゴール呼び出しに用います。

seq 命令で設定された出力レジスタ位置を入力レジスタ位置に切り替えて、ラベル Label 位置にある述語を呼び出します。

seq-call はガード処理においてサブルーチンとしてのサブゴール呼び出す場合に用います。

### par(N)

spawn 命令と共にボディ部のサブゴール呼び出しに用います。

述語を呼び出すに先立って、出力レジスタ位置を設定します。
IN[N] の場所を出力レジスタ OUT[0] とします。

### spawn(Label)

par 命令と共にボディ部のサブゴール呼び出しに用います。

par 命令で設定された出力レジスタ位置を入力レジスタ位置に切り替えて、ラベル Label 位置にある述語を呼び出します。

par-spawn は、ボディ部でのサブゴール呼び出しに相当し、状況に応じてゴールキューへの投入も許されます。

### tail(N)

exec 命令と共にボディ部の最終サブゴール呼び出しに用います。

IN[N] の位置を仮の出力レジスタ位置として設定します。

### exec(Label)

tail 命令と共にボディ部の最終サブゴール呼び出しに用います。

tail で設定された仮の出力レジスタ位置の内容で入力レジスタを書き換え、Label にジャンプします。

tail-exec は末尾呼び出しにおいて、スタック消費なしにサブゴールを呼び出すために用います。

## 変数操作命令

ガード付きホーン節

```
head(頭部の引数リスト) :- ガード部 | ボディ部.
```

それぞれの場所について

- 頭部の引数リストに与えられた条件にマッチするかを調べるのが check 系命令とそれに続く read 系命令
- ガード部に与えられる `X = Y` 形式について、`X` 部分は set 系命令とそれに続く write 系命令、`Y` 部分は check 系命令とそれに続く read 系命令
- ボディ部に与えられる `X = Y` 形式について、`X` 部分は set 系命令とそれに続く write 系命令、`Y` 部分は get 系命令とそれに続く unify 系命令
- ガード部・ボディ部共にサブゴール呼び出し引数の組み立ては out 系命令とそれに続く write 系命令

で構成します。

例えば、ボディ部における

`X = [1,2,3]`

は、以下の中間コードに変換します：

```
set_variable(reg(x, 1)).
get_list(reg(x,1)).
  unify_constant(1).
  unify_list.
  unify_constant(2).
  unify_list.
  unify_constant(3).
  unify_nil.
```

`[1,2,3] = X`

なら

```
set_list(reg(x,3)).
  write_constant(1).
  write_list.
  write_constant(2).
  write_list.
  write_constant(3).
  write_nil.
get_variable(reg(x,1),reg(x,3)).
```

にします。

実行効率を考えると前者のほうが有利なので前者の形に揃えて中間コードを出力したいところですが、現状のコンパイラは実装の簡単さ、コンパイル結果の予測しやすさの方を優先してなにも考えずに字面そのままの順序で解釈した中間コードを生成しています。

### 一時レジスタ設定命令

一時レジスタに項を構築するための命令です。

#### set_variable(Xi)

ヒープ上に新しい変数を確保し、その変数への参照を一時レジスタ Xn に書き込みます。

確保したアドレスを H と表記することにし、レジスタに書き込む、REF タグのついたタグ付きポインタを <REF>(H) と表記することにすると、処理をこのように表現できます：

```
H[0] := <REF>(H)
X[i] := <REF>(H)
H = H + 1
```

#### set_value(Vn, Xi)

レジスタ Vn の内容を一時レジスタ Xi に書き込みます。

```
X[i] := V[n]
```

#### set_nil(Xi)

一時レジスタ Xi に nil(`[]`) を書き込みます。

```
X[i] := <NIL>
```

#### set_constant(C, Xi)

一時レジスタ Xn に定数 C を書き込みます。

```
X[i] := C
```

#### set_list(Xi)

ヒープ上に CAR/CDR ２つ分の領域を確保し、そのリストへの参照を一時レジスタ Xn に書き込みます。
後続の write 命令実行に備えて、CAR/CDR 領域への参照をそれぞれスタックに push します（CAR, CDR の順に pop できるように、CDR, CAR の順に push します）。

```
X[i] := <LIST>(H)
push(<REF>(H + 1))
push(<REF>(H))
H = H + 2
```

#### set_structure(f/n, Xn)

ヒープ上に構造体 f/n が入る 1 + n 個分の領域を確保し、その先頭にアトム f/n を書き込みます。確保した構造体領域への参照を一時レジスタ Xn に書き込みます。
後続の write 命令実行に備えて、CAR/CDR 領域への参照をそれぞれスタックに push します（CAR, CDR の順に pop できるように、CDR, CAR の順に push します）。

```
X[i] := <STR>(H)
H[0] := f/n
push(<REF>(H + n))
push(<REF>(H + (n-1)))
push(<REF>(H + (n-2)))
 :
push(<REF>(H + 1))
H = H + n + 1
```

### 出力レジスタ設定命令

対象となるのが出力レジスタであることを除くと、set 系命令とほぼ同じ内容です。

#### out_variable(Vn, Oi)

set_variable 命令と同じ。

但し、操作対象が出力レジスタで、出力レジスタに書き込んだのと同じ変数をレジスタ Vn にも書き込みます。

#### out_value(Vn, Oi)

set_value 命令と同じ。但し、操作対象が出力レジスタです。

#### out_nil(Oi)

set_nil 命令と同じ。但し、操作対象が出力レジスタです。

#### out_constant(C, Oi)

set_constant 命令と同じ。但し、操作対象が出力レジスタです。

#### out_list(Oi)

set_list 命令と同じ。但し、操作対象が出力レジスタです。

#### out_structure(f/n, Oi)

set_structure 命令と同じ。但し、操作対象が出力レジスタです。

### 要素設定命令

set 系命令 / out 系命令でスタックに push された位置に対して操作を行う命令です。

#### write_variable(Vn)

ヒープ上に新しい変数を確保し、スタックから pop した位置にそれを書き込みます。
同時にレジスタ Vn にその変数への参照を書き込みます。

```
H[0] := <REF>(H)
*pop() := <REF>(H)
H = H + 1
```

#### write_value(Vn)

スタックから pop した位置にレジスタ Vn の内容を書き込みます。

```
*pop() := Vn
```

#### write_nil

スタックから pop した位置に nil(`[]`) を書き込みます。

```
*pop() := <NIL>
```

#### write_constant(C)

スタックから pop した位置に定数 C を書き込みます。

```
*pop() := C
```

#### write_list

ヒープ上に CAR/CDR ２つ分の領域を確保し、そのリストへの参照をスタックから pop した位置に書き込みます。
後続の write 命令実行に備えて、CAR/CDR 領域への参照をそれぞれスタックに push します（CAR, CDR の順に pop できるように、CDR, CAR の順に push します）。

```
*pop() := <LIST>(H)
push(<REF>(H + 1))
push(<REF>(H))
H = H + 2
```

#### write_structure(f/n)

ヒープ上に構造体 f/n が入る 1 + n 個分の領域を確保し、その先頭にアトム f/n を書き込みます。確保した構造体領域への参照をスタックから pop した位置に書き込みます。
後続の write 命令実行に備えて、CAR/CDR 領域への参照をそれぞれスタックに push します（CAR, CDR の順に pop できるように、CDR, CAR の順に push します）。

```
*pop() := <STR>(H)
H[0] := f/n
push(<REF>(H + n))
push(<REF>(H + (n-1)))
push(<REF>(H + (n-2)))
 :
push(<REF>(H + 1))
H = H + n + 1
```

### 単一化命令

マルチスレッドで単一化を行う場合、

1. 変数をデリファレンスしてその結果のタグを見て未実現変数だと判断
2. 未実現変数に対してなにか操作

ということをしようとしたら 1 から 2 までの間に別スレッドが当該変数を書き換えている可能性がある、ということに注意が必要です。

この場合には、デリファレンスから処理をやり直す必要があります。

一方で、変数が未実現でない、なんらかの値にバインドされている、という場合にはもうそれ以上変化することはありません。

#### get_variable(Vn, Ai)

レジスタ Ai をデリファレンスし、その結果をレジスタ Vn に書き込みます。

```
V[n] := deref(A[i])
```

#### get_value(Vn, Ai)

レジスタ Ai とレジスタ Vn を単一化します。

単一化に失敗した場合には fail します。

```
unify(V[n], A[i])  →  当該変数で待っているゴールがあれば起こす
if (unification_error) {
  fail();
}
```

#### get_nil(Ai)

レジスタ Ai と nil(`[]`) を単一化します。

単一化に失敗した場合には fail します。

```
unify(<NIL>, A[i])  →  当該変数で待っているゴールがあれば起こす
if (unification_error) {
  fail();
}
```

#### get_constant(C, Ai)

レジスタ Ai と定数 C を単一化します。

単一化に失敗した場合には fail します。

```
unify(C, A[i])  →  当該変数で待っているゴールがあれば起こす
if (unification_error) {
  fail();
}
```

#### get_list(Ai)

（概念としては）レジスタ Ai とリスト `[_|_]` を単一化したうえで、その CAR/CDR をスタックに push します。

単一化に失敗した場合には fail します。

実際の処理は、いきなりヒープ上に `[_|_]` を作るわけでなく、デリファレンス結果のタグを見て作る・作らないを決めて動作します。

```
do {
  q := deref(A[i])
  tag := tag_of(q)
  if (tag == REF || tag == SUS) {
    H[0] := <REF>(H[0])
    H[1] := <REF>(H[1])
    push(<REF>(H[1]))
    push(<REF>(H[0]))
    compare_exchange_strong(アトミックに A[i] を q から <LIST>(H[0]) に書き換える)
        書き換え成功 → 当該変数で待っているゴールがあれば起こす
        書き換え失敗 → continue  // リトライ
    H = H + 2
  } else if (tag == LIST) {
    push(*(addr_of(q) + 1))
    push(*(addr_of(q)))
  } else {
    fail()
  }
} while (0)
```

後続の命令が内容を書いていくのでなく get_list でいきなり空の内容を書き込んでしまうのは、書き込み途中の壊れた状態を他のスレッドに見せないためです。

#### get_structure(f/n, Ai)

（概念としては）レジスタ Ai と、引数が全て未実現変数の構造体 f/n とを単一化したうえで、その引数全てをスタックに push します。

単一化に失敗した場合には fail します。

実際の処理は、いきなりヒープ上に構造体 `f(_, _, ...)` を作るわけでなく、デリファレンス結果のタグを見て作る・作らないを決めて動作します。

```
do {
  q := deref(A[i])
  tag := tag_of(q)
  if (tag == REF || tag == SUS) {
    H[0] := f/n
    for (int j = n; j > 0; --j) {
      H[j] := <REF>(H[j])
      push(<REF>(H[j]))
    }
    compare_exchange_strong(アトミックに A[i] を q から <STR>(H[0]) に書き換える)
        書き換え成功 → 当該変数で待っているゴールがあれば起こす
        書き換え失敗 → continue  // リトライ
    H = H + n + 1
  } else if (tag == STR) {
    if (*(addr_of(q)) != f/n) {
      fail()
    }
    for (int j = n; j > 0; --j) {
      push(*(addr_of(q) + j))
    }
  } else {
    fail()
  }
} while (0)
```

後続の命令が内容を書いていくのでなく get_structure でいきなり空の内容を書き込んでしまうのは、書き込み途中の壊れた状態を他のスレッドに見せないためです。

### 単一化命令

get 系命令でスタックに push された位置にある変数との単一化を実行する命令が unify 命令です。

#### unify_variable(Vn)

スタックから参照を pop し、その位置の内容をレジスタ Vn に書き込みます。

```
V[n] := *pop()
```

#### unify_value(Vn)

スタックから参照を pop し、その位置の内容とレジスタ Vn とを単一化します。

単一化に失敗した場合には fail します。

```
unify(*pop(), A[i])  →  当該変数で待っているゴールがあれば起こす
if (unification_error) {
  fail();
}
```

#### unify_nil

スタックから参照を pop し、その位置の内容と nil(`[]`) を単一化します。

単一化に失敗した場合には fail します。

```
unify(<NIL>, *pop())  →  当該変数で待っているゴールがあれば起こす
if (unification_error) {
  fail();
}
```

#### unify_constant(C)

スタックから参照を pop し、その位置の内容と定数 C を単一化します。

単一化に失敗した場合には fail します。

```
unify(C, *pop())  →  当該変数で待っているゴールがあれば起こす
if (unification_error) {
  fail();
}
```

#### unify_list

（概念としては）スタックから参照を pop し、その位置の内容とリスト `[_|_]` を単一化したうえで、その CAR/CDR をスタックに push します。

単一化に失敗した場合には fail します。

実際の処理は、いきなりヒープ上に `[_|_]` を作るわけでなく、デリファレンス結果のタグを見て作る・作らないを決めて動作します。

```
do {
  q := deref(pop())
  tag := tag_of(q)
  if (tag == REF || tag == SUS) {
    H[0] := <REF>(H[0])
    H[1] := <REF>(H[1])
    push(<REF>(H[1]))
    push(<REF>(H[0]))
    compare_exchange_strong(アトミックに q を <LIST>(H[0]) に書き換える)
        書き換え成功 → 当該変数で待っているゴールがあれば起こす
        書き換え失敗 → continue;  // リトライ
    H = H + 2
  } else if (tag == LIST) {
    push(*(addr_of(q) + 1))
    push(*(addr_of(q)))
  } else {
    fail()
  }
} while (0)
```

後続の命令が内容を書いていくのでなく get_list でいきなり空の内容を書き込んでしまうのは、書き込み途中の壊れた状態を他のスレッドに見せないためです。

#### unify_structure(f/n)

（概念としては）スタックから参照を pop し、その位置の内容と、引数が全て未実現変数の構造体 f/n とを単一化したうえで、その引数全てをスタックに push します。

単一化に失敗した場合には fail します。

実際の処理は、いきなりヒープ上に構造体 `f(_, _, ...)` を作るわけでなく、デリファレンス結果のタグを見て作る・作らないを決めて動作します。

```
do {
  q := deref(pop())
  tag := tag_of(q)
  if (tag == REF || tag == SUS) {
    H[0] := f/n
    for (int j = n; j > 0; --j) {
      H[j] := <REF>(H[j])
      push(<REF>(H[j]))
    }
    compare_exchange_strong(アトミックに q を <STR>(H[0]) に書き換える)
        書き換え成功 → 当該変数で待っているゴールがあれば起こす
        書き換え失敗 → continue;  // リトライ
    H = H + n + 1
  } else if (tag == STR) {
    if (*(addr_of(q)) != f/n) {
      fail()
    }
    for (int j = n; j > 0; --j) {
      push(*(addr_of(q) + j))
    }
  } else {
    fail()
  }
} while (0)
```

後続の命令が内容を書いていくのでなく get_structure でいきなり空の内容を書き込んでしまうのは、書き込み途中の壊れた状態を他のスレッドに見せないためです。

### 入力レジスタチェック命令

パッシブユニフィケーションを行う命令です。

#### check_variable(Vn, Ai)

入力レジスタ Ai をデリファレンスし、その結果を一時レジスタ Vn に格納します。

#### check_value(Vn, Ai)

入力レジスタ Ai をデリファレンスし、その結果とレジスタ Vn の内容を比較します（このとき、必要なら再帰的に比較を繰り返します）。

内容が一致しない場合には fail します。

また、デリファレンス結果が未実現変数だった場合には当該変数を（try_guard_else_suspend 実行時のサスペンション処理で用いられる）待ち対象リストに追加して fail します。

#### check_nil(Ai)

入力レジスタ Ai をデリファレンスし、その結果が nil(`[]`) であるか調べます。

nil でなければ fail します。

また、デリファレンス結果が未実現変数だった場合には当該変数を（try_guard_else_suspend 実行時のサスペンション処理で用いられる）待ち対象リストに追加して fail します。

#### check_constant(C, Ai)

入力レジスタ Ai をデリファレンスし、その結果が定数 C と一致するか調べます。

一致しなければ fail します。

また、デリファレンス結果が未実現変数だった場合には当該変数を（try_guard_else_suspend 実行時のサスペンション処理で用いられる）待ち対象リストに追加して fail します。

#### check_list(Ai)

入力レジスタ Ai をデリファレンスし、その結果がリストか調べます。

リストでなければ fail します。

また、デリファレンス結果が未実現変数だった場合には当該変数を（try_guard_else_suspend 実行時のサスペンション処理で用いられる）待ち対象リストに追加して fail します。

リストだった場合、後の read 系命令実行に備えて CAR/CDR をスタックに push します（このとき、後の処理で CAR, CDR の順で処理できるように CDR, CAR の順に push します）。

#### check_structure(f/n, Ai)

入力レジスタ Ai をデリファレンスし、その結果が構造体 f/n か調べます。

構造体 f/n でなければ fail します。

また、デリファレンス結果が未実現変数だった場合には当該変数を（try_guard_else_suspend 実行時のサスペンション処理で用いられる）待ち対象リストに追加して fail します。

構造体 f/n だった場合、後の read 系命令実行に備えて n 個の引数全てをスタックに push します（このとき、後の処理で先頭の引数から順に処理できるように最後の引数から先頭に向かって逆順に push します）。

#### read_variable(Vn)

スタックから pop したアドレスの内容をレジスタ Vn に格納します。

#### read_value(Vn)

スタックから pop したアドレスの内容をデリファレンスし、レジスタ Vn の内容と比較します。

内容が一致しない場合には fail します。

また、デリファレンス結果が未実現変数だった場合には当該変数を（try_guard_else_suspend 実行時のサスペンション処理で用いられる）待ち対象リストに追加して fail します。

#### read_nil

スタックから pop したアドレスの内容をデリファレンスし、その結果が nil(`[]`) であるか調べます。

nil でなければ fail します。

また、デリファレンス結果が未実現変数だった場合には当該変数を（try_guard_else_suspend 実行時のサスペンション処理で用いられる）待ち対象リストに追加して fail します。

#### read_constant(C)

スタックから pop したアドレスの内容をデリファレンスし、その結果が定数 C と一致するか調べます。

一致しなければ fail します。

また、デリファレンス結果が未実現変数だった場合には当該変数を（try_guard_else_suspend 実行時のサスペンション処理で用いられる）待ち対象リストに追加して fail します。

#### read_list

スタックから pop したアドレスの内容をデリファレンスし、その結果がリストか調べます。

リストでなければ fail します。

また、デリファレンス結果が未実現変数だった場合には当該変数を（try_guard_else_suspend 実行時のサスペンション処理で用いられる）待ち対象リストに追加して fail します。

リストだった場合、後の read 系命令実行に備えて CAR/CDR をスタックに push します（このとき、後の処理で CAR, CDR の順で処理できるように CDR, CAR の順に push します）。

#### read_structure(f/n)

スタックから pop したアドレスの内容をデリファレンスし、その結果が構造体 f/n か調べます。

構造体 f/n でなければ fail します。

また、デリファレンス結果が未実現変数だった場合には当該変数を（try_guard_else_suspend 実行時のサスペンション処理で用いられる）待ち対象リストに追加して fail します。

構造体 f/n だった場合、後の read 系命令実行に備えて n 個の引数全てをスタックに push します（このとき、後の処理で先頭の引数から順に処理できるように最後の引数から先頭に向かって逆順に push します）。

# 追記

まだまだ試行錯誤中で人様にお見せできるようなものでもないのですが、一応それなりに動いていることと、いきなり開発中のファイルが消えてなくなったりすると悲しいので GitHub に登録しておきました。

https://github.com/tadashi9e/my_little_ghc_compiler