いものやま。

雑多な知識の寄せ集め

「Lucid, the Dataflow Programming Language」を翻訳してみた。(その8)

前回の続き。

2.1 代数

プログラミング言語についての質問で最もよくされるものの1つは、「その言語にはどのようなデータ型があるのか?」というものである。
言い換えれば、どんな種類のデータがその言語では扱われるのか、ということである。
この質問に対する典型的な答えは、整数、実数、真偽値、文字列、レコード、リスト、複素数、配列、表などである。
しかし、「Iswimにはどのデータ型があるのか?」という質問に対する回答は、「何でもある」となる。

この回答は正しいものの、それの意味するところは、Iswimが想像を絶するほど大きな言語であり、考えられるすべてのデータ型を利用可能である、といったことではない。
そうではなく、この回答の意味するところは、Iswimは(単一の言語ではなく)言語ファミリであり、各メンバは基本的なデータ構造の選択によって決定されるということである。
このファミリの異なるメンバは非常によく似ていて、私たちが「外側の構文(outer syntax)」と呼んでいるものについて、同じものになっている。(※after Wilkesという表現が使われているのだけど、よく分からない・・・)
この統一性は、Iswimの基本的な機能であるwhere節がデータ型やその操作に依存しないことから生まれている。
IswimはLandin(1966)が「あるものを他のもので表現する方法(a way of expressing things in terms of other things)」と「与えられたものの基本集合(a basic set of given things)」と呼んでいるものを分離している。
ファミリの各メンバは、(Landinの言葉でいえば)「うまくマッピングされた空間の、ある一点(a point in a well-mapped space)」となっている。

Iswim空間内の任意の点の座標(=Iswimファミリの任意の言語の1つ)は、与えられた(あるいは原始的な)ものの集合にちょうどなっている。
このプリミティブなものの集合は、一連のデータの集合、その集合上での操作の集合、および、それらのデータと操作を示す記号の集合で構成されている。
言い換えれば、Iswimファミリのメンバは、代数によって決定される。
代数 Aが与えられると、それによってファミリのあるメンバが定まり、そのメンバはIswim( A)となる。

(※以下、専門的な数学用語が出てきて、雰囲気しか訳せてない)

これをもう少し正確に書くと、以下のようになる。
シグネチャ(signature)とは、個体定数(individual constant、ものを示すための記号)と操作定数(operation constant、操作を示すための記号)の集合を意味していて、操作定数はそれぞれランク(rank)(あるいはアリティ(arity))(=引数の数)が決まっている。
シグネチャ Sが与えられると、S-代数である代数 Aが、そのデータの集合( Aの宇宙(universe、個体定数と操作定数によって覆われる代数構造の入った集合))とその上での演算によって構築される。
個体定数の任意の再帰的定義を解決するために、宇宙はドメイン(cpo、完備半順序)の構造を持ち、代数によって提供されるすべての操作は連続的でなければならない。
言い換えれば、Iswimファミリのメンバの座標は連続代数(continuous algebra)である。

この考えを説明するために、算術演算の入った整数という、とてもシンプルな代数 Zを示す。
シグネチャの個体定数は0と1である。

 Zの宇宙(これは完備半順序でなければならない)は、すべての整数と特別なオブジェクト \perpの集合である。
オブジェクト \perpは( Zの宇宙の要素の順序で)すべての整数の下に置かれる(ただし、この順序で整数自体は比較できない)。
したがって半順序(partial ordering)は以下のようになり、ここから \perpは「底(bottom)」と呼ばれることもある。

f:id:yamaimo0625:20190604001656p:plain

操作定数とそのアリティは、以下の通り:

操作定数 アリティ
abs 1
eq 2
ne 2
and 2
or 2
+ 2
- 2
* 2
div 2
< 2
> 2
mod 2
if-then-else 3

 Zがこれらの記号に割り当てる演算は、以下の通り:
(一般に、 \mathtt{k}_Aは代数 Aが演算 \mathtt{k}にそのシグネチャで割り当てた演算である)

  •  \mathtt{abs}_Zは、引数が整数の場合はその絶対値を返し、そうでなければ \perpを返す。
  •  \mathtt{not}_Zは、引数が1の場合は0を、引数が0の場合は1を返し、それ以外の場合は \perpを返す。
  •  \mathtt{eq}_Zは、両方の引数が整数で、値が等しければ1を、等しくなければ0を返し、そうでない場合は \perpを返す。
  •  \mathtt{ne}_Zは、両方の引数が整数で、値が等しいければ0を、等しくなければ1を返し、そうでない場合は \perpを返す。
  •  \mathtt{and}_Zは、引数が両方とも1の場合は1を、最初の引数が0、あるいは1つ目の引数が1で2つ目の引数が0の場合は0を返し、それ以外の場合は \perpを返す。
  •  \mathtt{or}_Zは、引数が両方とも0の場合は0を、最初の引数が1、あるいは1つ目の引数が0で2つ目の引数が1の場合は1を返し、それ以外の場合は \perpを返す。
  •  \mathtt{+}_Zは、引数がどちらも整数であればその合計を返し、そうでなければ \perpを返す。
  •  \mathtt{-}_Zは、引数がどちらも整数であればその差を返し、そうでなければ \perpを返す。
  •  \mathtt{*}_Zは、引数がどちらも整数であればその積を返し、そうでなければ \perpを返す。
  •  \mathtt{div}_Zは、引数がどちらも整数で、2つ目の引数が正の場合、引数の商(あまりは捨てられる)を返し、そうでなければ \perpを返す。
  •  \mathtt{\gt}_Zは、引数がどちらも整数で1つ目の引数が2つ目の整数より大きい場合は1を、1つ目の引数が2つ目の引数以下の場合は0を返し、そうでなければ \perpを返す。
  •  \mathtt{\lt}_Zは、引数がどちらも整数で1つ目の引数が2つ目の整数より小さい場合は1を、1つ目の引数が2つ目の引数以上の場合は0を返し、そうでなければ \perpを返す。
  •  \mathtt{mod}_Zは、引数がどちらも整数で、2つ目の引数が正の場合、1つ目の引数を2つ目の引数で割ったあまりを返し、そうでなければ \perpを返す。
  •  \mathtt{if}-\mathtt{then}-\mathtt{else}_Zは、最初の引数が1ならば2つ目の引数を、0ならば3つ目の引数を返し、そうでなければ \perpを返す。

この代数では、整数1、0をそれぞれ真、偽と解釈し、andorをそれぞれ論理積論理和と解釈する。
 \perpは、不適切な引数(0で割るなど)を演算に適用した結果に使用されるが、それ以外の明確な用途はない。
その本当の意味は後で説明される。

したがって、Iswim( Z)という言語は「整数Iswim」となっている(この言語については以前に言及したことを思い出して欲しい)。

より興味深い例として、"POP"代数 Pがある。
これは、この本で使用される最も重要なインデックス代数となっている。
 Pは、POP-2言語(Burstall, Collins, and Popplestone、1971)で提供されるデータ型および演算(の一部)に基づいている。
 Pの宇宙は、数値(有理数を含む)、文字列、単語(LISPでのアトムのようなもの)、リスト、および、エラーとデータの終わり(end-of-data)を指し示す2つの特別なオブジェクトで構成されている。
付録のpLucidマニュアルでは、これらのオブジェクトと操作について詳しく説明している。
また、POP-2に限りなく近い具体的な構文も説明している。

以下は、"POP-2"代数 Pによって定まるIswimファミリのメンバであるIswim( P)で書かれたプログラムである:

perms([a b c d])
where
    perms(L) = if L eq []
               then [[]]
               else allinserts(hd(L), perms(tl(L)))
               fi;
    allinserts(x, J) = if J eq []
                       then []
                       else inserts(x, hd(J)) <> allinserts(x, tl(J))
                       fi;
    inserts(x, M) = if M eq []
                    then [%[% x %]%]
                    else (X :: M) :: h(hd(M), inserts(x, tl(M)))
                        where
                            h(m, K) = if K eq []
                                      then []
                                      else (m :: hd(K)) :: h(m, tl(K))
                                      fi;
                        end
                    fi;
end

このプログラムは、リスト[a b c d]のすべての順列の一覧を出力する。
具体的な構文規則はpLucidのものとなっていて、たとえば、::はリストのコンストラクタ操作を示している。


ということで、Iswimと代数の関係について。

何やら難しい話だけど、ようはIswimは単一の言語ではなく、複数の言語からなるファミリであり、Iswimとして定められているのは共通する文法の部分だけで、それぞれのIswimで扱えるデータ型や演算は、与えられた代数によって変わってくるよ、という話。

今日はここまで!