ボンジュール・マドモアゼル

本サイトの情報は自己責任にてご利用下さい。

[MS-DOS] MS-DOS 多重割込み

 
INT 2Fh の多重割込み(Multiplex Interrupt)は、割込み中の割込みという本来の多重割込みとは別物であると思う。ひとつの割込みベクターで沢山のモジュールの割込みを扱えるという意味の多重だと思われる。
  1. 2007/05/23(水) 01:08:38|
  2. MS-DOS|
  3. トラックバック(-)|
  4. コメント:0

[Prolog] Prolog op/3 演算子指示子

 
述語 op/3 のxfx xfy yfx などの演算子指定子の説明で
ふたつの文字 x と y は結合性についての情報をもつ.カッコがない場合、y は引数がこの演算子の優先順位と同じかより低いクラスの演算子を含むことができることを意味する.一方、x はこの引数中の任意の演算子はこの演算子の優先順位よりかならずより低いクラスのものでなければならないことを意味する.

とあるが「優先順位が低い」という表現は誤解を与える。より適切には
式をカッコのないものとして、x に含まれる演算子の優先順位の値は演算子 f の優先順位より小さいものとされ、y に含まれる演算子の優先順位は、演算子 f の優先順位以下の値とされる。


参考英文

The meaning of x versus y is a little more subtle. x means that the precedence of the argument (i.e., the precedence of the principal functor of the argument) must be less than the precedence of   f.   y means that the precedence of the corresponding argument may be less than or equal to the precedence of  f.
The precedence number is a number between 1 and 1200 (inclusive) and determines how strong an operator binds its arguments. The lower the precedence number the stronger the operator binds.

[Prolog] SWI-Prolog

 

:/2
<Module><Term>
?- assert(world:done). % asserts done/0 into module world
?- world:assert(done). % the same
?- world:done. % calls done/0 in module world

要は、モジュールを指定するための演算子.

:-/1

Directives may be placed anywhere in a source file, invoking any predicate. They are executed when encountered. If the directive fails, a warning is printed. Directives are specified by :-/1 or ?-/1. There is no difference between the two.

要は、ディレクティブを実行するための演算子.

マニュアル上、
:/2 :-/1
で検索すると該当箇所が見つかる。

[Prolog] Prolog 差分リスト difference lists

 
以下、差分リストの疑問や考えをまとめたものです。
間違いがあるかもしれません。

差分リスト

差分リストは、差分が取れるリストの対 (List1, List2) である。差分が取れるリストの対とは List2 が List1 の接尾辞となっているようなリストの対である。たとえば、([1,2,3,4,5], [4,5])など。
append(Zs, Ys, Xs)を満たすリスト Zs が存在する場合、Xs-Ysを差分リストとして見るのは容易い。
たとえば、Xs=[1,2,3,4], Ys=[3,4], Zs=[1,2] とした場合、append([1,2],[3,4],[1,2,3,4])であり、[1,2,3,4]-[3,4]は差分リストになる。
さて、append(Zs, Ys, Xs)を満たすリスト Zs が存在しない場合、Xs-Ysは差分リストと言えるだろうか。
たとえば、[1,2,3]-[a,b,c]は差分リストだろうか。
このようなリストの対でも、以下のように append_dl を適用することができる。
?- append_dl([1,2,3]-[a,b,c], [a,b,c]-[4,5], Xs-Ys).

Xs = [1, 2, 3],
Ys = [4, 5].


差分リストを判定する Prolog プログラムは次のようになる。述語 difference_list(Xs-Ys) を満たす解となるものが差分リストである。
difference_list(Xs-Ys):-list(Xs),list(Ys),suffix(Ys,Xs).


list([]).
list([X|Xs]):-list(Xs).

suffix(Xs,Xs).
suffix(Xs,[Y|Ys]):-suffix(Xs,Ys).
ただし、このプログラムは、不完備な差分リストも受け入れてしまう。


不完備な差分リスト

『Prolog の技芸』によると、型は、項の集合である。任意の型 T (項の集合)に対して、不完備型 IT を考えることができる。不完備型 IT は、元の型 T の要素となる代入例を持つが、型 T の要素ではない代入例も持っている項の集合である。言い換えると、或る項 A が、型 T に含まれる代入例 Aθ1 と、それとは別に型 T に含まれない代入例 Aθ2 を持つとき、項 A は不完備型 IT の項となる。

項 [a,b,c|Xs]-Xs は、代入 {Xs=[d]} による代入例 [a,b,c,d]-[d] は差分リストだが、代入 {Xs=4} による代入例 [a,b,c|4]-4 は差分リストではない。よって [a,b,c|Xs]-Xs という形式の項は、不完備な差分リストである。

差分リスト Xs - Ys が完備であるには、Xs と Ys が完備なりストであることが必要だが、Xs と Ys の両方が完備なリストであっても Xs と Ys が重なる部分で、どちらか一方に、他方には存在しないか、また、他方とは異なる非基底項がある場合 Xs - Ys は不完備な差分リストとなる。[1,2,X]-[X] は完備だが [1,2,X]-[Y] は不完備である。

メタ論理述語を使うと、完備な差分リストのみ受け入れる Prolog プログラムを書くことができる。以下は、SWI-Prolog で動作を確認したもの。
difference_list(Xs-Ys):-list(Xs),list(Ys),suffix(Ys,Xs).


list(X):-var(X),!,fail.
list([]).
list([X|Xs]):-list(Xs).

suffix(Xs,Ys):-Xs==Ys,!.
suffix(Xs,[Y|Ys]):-suffix(Xs,Ys).
いくつか試してみると、、
?- difference_list([a,b,c|Xs]-Xs).

false.

?- difference_list([1,2,X,Y]-[X,Y]).
true.

?- difference_list([1,2,X,Z]-[X,Y]).
false.


差分リストと同値類

すべての完備な差分リストの集合は、リスト対の差分が同じリストになるという同値関係によって、同値類に分割することができる。完備なリスト L に対して、差分リスト L - [] を対応付けられることから、リストと同値類は、一対一に対応していることがわかる。リストの連結などの演算は、この同値類の間の演算としてみることができる。

例えると、差分リストのリストの関係は、整数と剰余類との関係に相当する。
整数環 Z について、法 n に関する合同関係を考えたとき、整数が差分リストにあたり、合同関係によって分割された同値類(剰余類)がリストにあたる。


差分リストと分数

差分リストを分数と比較してみると、差分リストが見えてくる。
下のように、ひとつのリストに同値な差分リストは無限にある。

リストと差分リスト
[a,b,c] = [a,b,c]-[], [a,b,c,d]-[d], ...


[1,2,3] = [1,2,3,4]-[4], [1,2,3,4,5]-[4,5], ...

同様に、あるひとつの整数と同値な分数は無限にある。

整数と分数
1 = 1/1, 2/2, 3/3, ..., n / n


2 = 2/1, 4/2, 6/3, ..., 2n / n

3 = 3/1, 6/2, 9/3, ..., 3n / n
これらの分数の分母と分子は、任意の整数の組み合わせではない。
分子を分母で割ったとき、余りがなく除算ができる組み合わせである。

リスト L を 差分リスト L - [] で表すことができ、空リスト [] を Xs - Xs と表すことができるのと同様、整数 x は、x / 1 という分数で表すことができ、空リストにあたる整数 1 については、n / n という分数で表すことができる。

次は、Prolog による典型的な差分リストの連結プログラムである。
    append_dl(Xs-Ys, Ys-Zs, Xs-Zs).

しかし、この連結プログラムは、任意の差分リストに適用できるわけではない。
たとえば、
   ([a,b,c,d,e]-[d,e]) + ([1,2,3,4]-[4]) ≡ ([a,b,c,1,2,3]-[])

という連結ついて、Prolog は、

?- append_dl([a,b,c,d,e]-[d,e], [1,2,3,4]-[4], Xs-Zs).
false.

と false を返す。

これに関して、Prolog の技芸には、次のように書かれている。
プログラム15.1(append_dl)を用いて、2つの差分リスト As\Bs とXs\Ys を連結することができるための必要かつ十分な条件は、BsとXsが単一化可能なことである。このとき、この2つの差分リストは適合する(compatible)という。

Prolog の技芸 - 15.1 差分リスト 311ページ

したがって、さきほどの例は、ふたつの差分リストが適合しないため失敗したのである。
今度は、さきほどの差分リストと同等であるが、ふたつの差分リストが適合するよう表現を変えて問い合わせると、次のように成功する。

?- append_dl([a,b,c,1,2,3,4]-[1,2,3,4], [1,2,3,4]-[4], Xs-Zs).
Xs = [a, b, c, 1, 2, 3, 4],
Zs = [4].



差分リストのプログラムは、[a,b,c|Xs]-Xs といった不完備な差分リストを用いて実行効率をあげることを目的としているため、任意の差分リストに動作するわけではない。

差分リストの連結プログラムについて、分数の乗算を例にして考えてみよう。
分数の乗算は、整数の乗算をもとに
    A / B * C / D := A * C / B * D
と計算できる。しかし、B = C の場合は、整数の乗算を使わずとも、
    A / B * C / D := A / D  (B = C の場合)
と計算できる。差分リストの連結を単位時間で実行するのと同様、 B = C の場合は、分数の乗算を単位時間で実行することができる。ただし、この2番目の乗算を適用するには、B = C が必要かつ十分な条件となっている。

append_dl は、正当ではない

プログラム P の意味 M(P) は、Pから演繹可能な基底項の集合である。
プログラム P の意味 M(P) がある意図された意味 M の部分集合であるとき、P は M に関して正当(correct)であるという。すなわち、正当なプログラムは、意図されていないことを表すことはない。M が M(P) の部分集合であるとき、P は M に関して完全(complete)であるという。

Prologの技芸 − 1.9 プログラムの意味 22ページ
この定義によると、append_dl は完全であるが、正当ではない、ということになる。
なぜなら、
?- append_dl([a|b]-b,b-c,[a|b]-c).

true.
となるから。
ガーベージイン・ガーベージアウトなプログラムは正当ではない。


不完備な差分リストは SCSI 機器 に例えられる。(今更、SCSIも古いか)
SCSI 機器は、いくつかの機器を下図のように数珠繋ぎにすることができる。

[ パソコン ]<---[ デバイス 1 ]<---[ デバイス 2 ]<---[ デバイス 3 ]<---[ ターミネータ ]

ひとつの機器(デバイス)を取り出すと、

[ デバイス ]<--....

後にいくつかの機器が連結される可能性を残すものとなる。

不完備な差分リストも同じようなもの。
ひとつの差分リストがひとつの SCSI 機器に対応する。

[ a, b, c | X ]

SCSI には連結の終わりを示すターミネータがある。
同じように、差分リストには、ターミネータとして空リストがある。

差分リストの連結
差分リストの "連結" は、単一化(ユニフィケーション)を利用する。
節には、後続の差分リストが単一化されるための差込口を設けてやらねばならない。

app( [ a, b, c |X]/X ,...)

↑差込口

[用語] コリファレンス(Coreference)

 
Coreference
Coreference is the reference in one expression to the same referent in another expression.
About LinguaLinks/ Library contents/Book contents/Page context/
What is coreference?



コリファレンスとは、ある式と別の式における同じ指示物(referent)への参照である。

例: 次の文ではyou が同じ対象を参照している。(coreferしている)

You said you would come.
次のページ