コード説明

Next: 割り込み/中断/失敗 Up: 例 Previous: 例

コード説明

このコードを先頭から順に説明する。

2-4行目には、コンパイルするに必要なファイルのincludeリストがならぶ。 include/klic/atom.h, include/klic/funct.hは各々、アトム番号、ファンクタ番号が記録されたファイルで、マクロの羅列になっている。つまり、アトム番号、ファンクタ番号はCのコンパイルを行うときにはすでに確定されている。
```
     2  #include <klic/klichdr.h>
     3  #include "atom.h"
     4  #include "funct.h"
```
6 行目はこのモジュールで定義されるmodule型関数のmodule_mainの宣言。
```
     6  module module_main();
```

7 - 12 行目は、このモジュール内で定義される述語、main/0, nrev/2, append/3 の述語構造体(struct predicate)の定義。このように述語構造体は定数としてコンパイル時に生成される。

     7  Const struct predicate predicate_main_xmain_0 =
     8     { module_main, 0, 0 };
     9  Const struct predicate predicate_main_xnrev_2 =
    10     { module_main, 1, 2 };
    11  Const struct predicate predicate_main_xappend_3 =
    12     { module_main, 2, 3 };

13行目は、参照している外部モジュールである、klicio:klicio/1の述語構造体の宣言。当然、klicioモジュールを実装するCファイル中に実体は定義されている筈である。
```
    13  extern Const struct predicate predicate_klicio_xklicio_1;
```

15行目からmodule_mainの定義がはじまる。引数はすでに説明をした通り。

    15  module module_main(glbl, qp, allocp, toppred)
    16    struct global_variables *glbl;
    17    struct goalrec *qp;
    18    register q *allocp;
    19    Const struct predicate *toppred;
    20  {

21 - 36 行目には[1,2,3]を実現するリスト構造が定義されている。このように、コンパイル時に確定している構造は、コンパイル時に静的に生成される(

ページ、第3.4.2章参照)。

    21    static Const q cons_const_0[] = {
    22      NILATOM,
    23      makeint(3),
    24    };
    25    static Const q cons_const_1[] = {
    26      makecons(cons_const_0),
    27      makeint(2),
    28    };
    29    static Const q cons_const_2[] = {
    30      makecons(cons_const_1),
    31      makeint(1),
    32    };
    33    static Const q cons_const_3[] = {
    34      NILATOM,
    35      makesym(atom_nl),
    36    };

37行目に、述語間引数用変数(引数レジスタの気分)の宣言。これは必要な数だけコンパイラが生成する。
```
    37    q a0, a1, a2;
```
39行目にあるのは、中断スタック(詳細後述)の先頭ポインタの宣言。
```
    39    q *reasonp;
```
40行目に、module_topなるラベルが定義されている。一般的に``モジュール名'' + ``_top''なる名称のラベルが実行行の先頭に定義される。
41-45行目以降にあるのは、switch文となるマクロ。KLICの制御構造は、 include/klic/control.h内でマクロ化されている。このswitchは、 toppred->predを参照し、それが、0, 1, 2 のいずであるかにより各々、ラベルmain_0_top, nrev_2_top, append_3_top に飛ぶ。 predicate型のpred fieldはこのようにswitchするため、モジュール内でuniqueな番号になるようにコンパイラが定めている。
```
    40   module_top:
    41    switch_on_pred() {
    42      case_pred(0, main_0_top);
    43      case_pred(1, nrev_2_top);
    44      last_case_pred(2, append_3_top);
    45    }
```
47行目にはラベル main_0_top の定義がなされている。各述語の先頭には、''述語名_" + 引数個数 + ``_top''なる名称のラベルが生成され、swicth_on_predからジャンプされる。
```
    47   main_0_top: {
```
48 行目にあるのは述語内で使われる一時変数(一時レジスタの気分)。
```
    48    q x0, x1, x2, x3, x4, x5;
```
qp の先頭を49行目でずらす。
```
    49    qp = qp->next;
```
50行目のラベルは51行目のサスペンションスタックを初期化する操作に対してのラベルである。述語mainの実行にあたり、 reasonp の設定が済んでいることがわかっている場合にはこではなく、52行目に入る。
```
    50   main_0_clear_reason:
    51    reasonp = reasons;
```
52行目から述語メインの実際の動作が開始される。53-56で, nrev([1,2,3],Y)に対応するゴールレコードが生成される。allocpとあるのはヒープ割り付けである。このように KLICではゴールレコードもヒープ中に生成される。ゴールレコードのnextに相当する先頭にはqpが格納されている。
また、基本的にKLICプログラム中で記述した順とは逆にゴールが生成され、エンキューされていく。 56行目で純粋未定義変数を生成しているのに注意。
```
    52   main_0_0:
    53    allocp[0] = (q)qp;
    54    allocp[1] = (q)(&predicate_main_xnrev_2);
    55    allocp[2] = makecons(cons_const_2);
    56    allocp[3] = x0 = makeref(&allocp[3]);
```

57 - 71では、[stdout(normal([putt(X),nl]))]に対応した構造を組みたてている。構造の末端からくみたてていることに注意。

    57    allocp[4] = makesym(functor_putt_1);
    58    allocp[5] = x0;
    59    x1 = makefunctor(&allocp[4]);
    60    allocp[6] = makecons(cons_const_3);
    61    allocp[7] = x1;
    62    x2 = makecons(&allocp[6]);
    63    allocp[8] = makesym(functor_normal_1);
    64    allocp[9] = x2;
    65    x3 = makefunctor(&allocp[8]);
    66    allocp[10] = makesym(functor_stdout_1);
    67    allocp[11] = x3;
    68    x4 = makefunctor(&allocp[10]);
    69    allocp[12] = NILATOM;
    70    allocp[13] = x4;
    71    x5 = makecons(&allocp[12]);

72 - 74 ではklic:klicio(...)に対応したゴールレコードが生成される。next fieldには先に作成したnrev(...)のゴールレコードを格納することに注意。
```
    72    allocp[14] = (q)(struct goalrec*)&allocp[0];
    73    allocp[15] = (q)(&predicate_klicio_xklicio_1);
    74    allocp[16] = x5;
```
75行目では、今組み立てたklic:klicio(...)のゴールをqpに格納している。つまり、通常呼び出しのためのゴールスタックへのエンキューを行っている。
```
    75    qp = (struct goalrec*)&allocp[14];
```
76行目でヒープ割付点を更新している。
```
    76    allocp += 17;
```
77行目のproceed()はinclude/klic/control.h内で定義されているmacroで、 module型関数内で必ず定義されているproceed_labelなるラベルに飛ぶ。
```
    77    proceed();
```
ここでは、さらに実行するゴールがないため、ゴールスタックのデキュー操作を行うためproceed()が出力されている (ページ、第3.3.2章参照)。
78-80行目は中断、失敗するためのコードである。引数がない (= 中断も失敗もしない)main/0では意味がない。
```
    78   main_0_ext_interrupt:
    79    reasonp = 0l;
    80   main_0_interrupt:
```
84行目はnrev/2の入口である。外部モジュールからmain:nrev/2が呼び出された時や、モジュール内でもゴールスタックよりnrev/2を呼ぶコードが取り出された時にはここに飛ぶ。
```
    84   nrev_2_top: {
```
85行目は一時変数の宣言。
```
    85    q x0, x1, x2;
```
86 - 87行目で引数を引数レジスタにコピーしている。
```
    86    a0 = qp->args[0];
    87    a1 = qp->args[1];
```
88行目で実行可能キューをデキュー。
```
    88    qp = qp->next;
```

89 - 92行目に述語の先頭の処理が記述される。

    89   nrev_2_clear_reason:
    90    reasonp = reasons;
    91   nrev_2_0:
    92   nrev_2_1:

93行目から始まるswitch文で、a0のタグにより分岐する。
```
    93    switch (ptagof(a0)) {
```
94 - 109行目はCONSタグの場合。
```
    94   case CONS:
    95    allocp[0] = NILATOM;
    96    x1 = car_of(a0);
    97    allocp[1] = x1;
    98    x0 = makecons(&allocp[0]);
    99    allocp[2] = (q)qp;
   100    allocp[3] = (q)(&predicate_main_xappend_3);
   101    allocp[4] = x2 = makeref(&allocp[4]);
   102    allocp[5] = x0;
   103    allocp[6] = a1;
   104    a0 = cdr_of(a0);
   105    a1 = x2;
   106    qp = (struct goalrec*)&allocp[2];
   107    allocp += 7;
   108    execute(nrev_2_0);
   109    goto nrev_2_ext_interrupt;
```
- 95 - 98 で[A] を組みたて、x0にセットする。
- 99 - 103で、append/3 のゴールを作成し、エンキューしている。
- 104 - 108 で、nrev/2 の呼び出しを行っている。
  ここでは、nrev/2が「直接呼び出し」されている。
  この時には、引数レジスタ群(a0, a1, ...)は、呼び出された先でもそのまま (ゴールからひきあげることなく)利用されるため、executeまでの間に引数レジスタ群に適当な引数を用意しておく必要がある。
  - まず、104行目でXを第0引数ににセット。
  - 105行目では、純粋未定義変数であるX1(x2に載っている)を第一引数にセット。
  - 106行目で、append/3 をqpにセット(つまり、append/3のエンキュー)
  - 107行目でヒープ割付点の更新。
  - 108行目でexecuteで直接呼びだしする。これは、include/klic/control.hで以下のように定義されたマクロである。
```
#define execute(label)\
{\
  if (allocp < heaplimit) goto label;\
}
```
    ここで、allop とheaplimitを比較している。これは第3.2章 (ページ) で述べた、「例外的処理の有無」の検出である。ここで「例外的処理処理」要求が検出できなかった場合には指定されたラベル(ここでは、 nrev_2_0 に飛ぶ)。検出された場合には109行以降の処理を行う。
    nrev_2_0 とはすでに経過した部分であり、91行目にある。これは、「ゴールから引数が引き上げ」られたのと「引数の検査」の切れ目に存在するラベルである。これは、execute実行の場合には前述のように引数(a_xレジスタ)はすでに正しい内容を持っているため「ゴールからの引数の引き上げ」は不要であり、省略するためにこのようなラベルに飛ぶようになっている。つまり、述語が開始されるには、一般的には以下の2通りがある(ページ、第3.3.2章参照)。
    
    通常呼び出しによる実行:
    ``述語_引数個数'' + ``_top''。直後にゴール引数の引き上げがある。
    
    直接呼び出しによる実行:
    ``述語_引数個数'' + ``_0''。ゴール引数の引き上げは省略。
直前のexecuteで、「他の処理」に対する要求があった場合には、 109行目を実行し、その後121に飛ぶ。その結果、中断スタックポインタを0にしてからinterrupt_2に飛ぶ。中断スタックには、通常はゴール実行の原因となった未定義変数をプッシュする。しかしながら、中断スタックポインタが0である場合には、ヒープ溢れの検出による中断であることを示す (ページ、第4.2.2章参照)。 interrupt_2 とは、「2引数用の割出し処理ラベル」であり、引数レジスタ上の2つの引数をゴール引数部に格納してから、「他の処理」の実行のため、関数interrupt_goalに制御を移す。
110行目からは、a0がアトミックな場合の処理である。
```
   111    if (a0 != NILATOM) goto nrev_2_interrupt;
   112    x0 = NILATOM;
   113    unify_value(a1, x0);
   114    proceed();
```
- 111行目はa0がNILATOMかどうかを検査し、NILATOMでなければnrev_2_interrputに飛ぶ。nrev_2_interruptでは、中断スタックポインタを0にすることなく、中断スタックの底を指す(つまりスタックを空にする)状態にする。これは、リダクション実行の失敗を示す(ページ、第4.2.2章参照)。その後引数を退避し、関数interrupt_goal に制御を移す。
- 112では、x0 にNILATOMを代入し、a1とunify_value()により Y=[] が実行される。unify_value は、第2引数が具体値であることが判明しているときに呼びだされるmacroで、一般的にはdo_unify()が呼びだされる。これら2つはマクロであり、include/klic/unify.h に定義されている。 unify_value の場合には第0引数が純粋未定義変数である場合には、実行時ルーチンを呼ばずに、その場で具体化を行う。この「単純な場合」以外は、 runtime/unify.cで定義されているC関数、do_unify, do_unify_valueが呼びだされる。
- 114行目ではproceedする。
115-118行目ではa0がREFタグの場合処理が記されている。
```
   115   case VARREF:
   116    deref_and_jump(a0,nrev_2_1);
   117    *reasonp++ =  a0;
   118    goto nrev_2_interrupt;
```
116行目のderef_and_jumpはinclude/klic/index.hに定義されるマクロで、 deref_and_jump(レジスタ、ラベル)という引数をとる。具体的には以下のようなマクロである。
```
#define deref_and_jump(x, loop) \
{ \
  q temp0 = derefone(x); \
  if(!isref(temp0)) { \
    (x) = temp0; \
    goto loop; \
  } \
}
```
これを以下で解説する。
- レジスタを1段手繰り(マクロderefone())、
  - 具体値であれば書き戻し、ラベルに飛ぶ。その結果第0引数(a0)の検査を最初から行うことを示す。
  - 具体値でなければ、次の行に進む。
  117行目では、(少なくとも2段以上)REFであったa0を中断スタックに詰み、 nrev_2_interrptに飛ぶ。その結果、最終的には引数を退避し、関数interrupt_goal()が呼びだされる。

127行目からはappend/3のコードである。 128 - l34行目までで引数の引き上げ、中断スタックポインタの初期化が行われる。

   127   append_3_top: {
   128    q x0, x1, x2;
   129    a0 = qp->args[0];
   130    a1 = qp->args[1];
   131    a2 = qp->args[2];
   132    qp = qp->next;
   133   append_3_clear_reason:
   134    reasonp = reasons;

137行目で、a0の型検査が行われる。 CONSであれば、139 - 144行目で単一化がなされ、147行目でappend/3が直接呼び出しされる。

   137    switch (ptagof(a0)) {
   138   case CONS:
   139    allocp[0] = x1 = makeref(&allocp[0]);
   140    x2 = car_of(a0);
   141    allocp[1] = x2;
   142    x0 = makecons(&allocp[0]);
   143    allocp += 2;
   144    unify_value(a2, x0);
   145    a0 = cdr_of(a0);
   146    a2 = x1;
   147    execute(append_3_0);
   148    goto append_3_ext_interrupt;

ATOMICであれば、150行目でNILATOMかどうか検査され、NILATOMであれば、 2つの引数を単一化し、proceed()する。NILATOMでなければ、append_3_interruptに飛び、引数が書き戻され、interrupt_goalsが呼びだされる。
```
   149   case ATOMIC:
   150    if (a0 != NILATOM) goto append_3_interrupt;
   151    unify(a1, a2);
   152    proceed();
```
153 - 156行目はREFの時のコードであり、nrevと同様に手繰りの後に検査され、再度137より検査されるか、interrupt_goalが呼びだされるかする。
```
   153   case VARREF:
   154    deref_and_jump(a0,append_3_1);
   155    *reasonp++ =  a0;
   156    goto append_3_interrupt;
```

164 - 169行目は引数をゴールレコードに書きもどす処理である。

   164   interrupt_3:
   165    allocp[4] = a2;
   166   interrupt_2:
   167    allocp[3] = a1;
   168   interrupt_1:
   169    allocp[2] = a0;

171行目でinterrupt_goal を呼び出している。この関数呼びだしが起きる時は、以下いずれかであり、おのおの中断スタックの状態により interrupt_goal関数内で適切な処理が行われる。 interupt_goal関数内の処理の概要は第3.4章 (ページ)を参照のこと。
```
   170   interrupt_0:
   171    allocp = interrupt_goal(allocp, toppred, reasonp);
```
なお、interupt_goals(allocp, toppred, reasonp)の関数specは以下の通り。
allocp:
ヒープ割付点。

toppred:
失敗/中断を起した述語の述語構造体。この例ではなかったが、各述語よりinterrupt_Xに飛ぶコードが出る直前で、 toppredに当該述語の構造体がセットされる。この例では出現しなかった理由は、以下である。
- モジュール内でのexecuteによるジャンプを考えなければ、このtoppredはmodule型関数を呼びだすときに設定されているので、内部であらたに設定する必要はない。つまり、executeされる場合に考慮する必要がある。
- ここの例で、executeされるものは、nrev, appendが共に自分自身を呼び出すものしかなかった。よって、この例では、executeによりtoppredと実際に実行している述語とがずれる可能性はないため、このような処理は必要がない。
reasonp:
中断スタックポインタ。
また、戻り値としては更新されたヒープ割付点を返す。
どちらにしても、このinterrupt_goalが呼び出された後には、レジスタなどは「中途半端な状態」にはなく、すべてgoal recordに収められている。
最終的に、include/klic/control.hで定義されている、 loop_within_module なるマクロに制御が移される。
```
   172   proceed_label:
   173    loop_within_module(module_main);
```
具体的には以下のような定義である。
```
#define loop_within_module(f)                           \
{ \
  module (*func)(); \
  if (allocp >= heaplimit) { \
    allocp = klic_interrupt(allocp, qp); \
    qp = current_queue; \
  } \
  if ((func = (toppred = qp->pred)->func) == (f)) \
    goto module_top; \
  heapp = allocp; \
  current_queue = qp; \
  return (module) func; \
}
```
ここでは、

1.
allocp と heaplimitを比較する。つまり、「例外的な処理(GC要求を含む)」があるかどうか検査する。「例外的処理が」ある場合には、 runtime/intrrpt.cで定義されている関数 klic_interruptが呼びだされ、「例外的処理」が処理される。

2.
必要ならば「例外的な処理」を終了したあとに、「次に実行される述語の属するモジュール関数」が、現在のモジュール関数であるかどうか調べられる。現在のモジュール関数であれば、returnはせずに、関数の実行部分の先頭である module_topに飛ぶ。現在のモジュールでなければ、allocpをheappに、 qp をcurrent_queueに退避し、次に実行すべきmodule型関数を返し、トップレベルループに戻る。

先に「例外的な処理」の検査、措置を行う理由は、以下の通りである。
- 「例外的な処理」を行った結果、ゴールがエンキューされる場合がある。
- そのゴールは、最高の優先である可能性があり、その場合には、そのゴールの実行を例外的処理の措置の前のキュー先頭のゴールよりも先に行う必要がある。

Next: 割り込み/中断/失敗 Up: 例 Previous: 例

Sekita Daigo
1998-05-18