いものやま。

雑多な知識の寄せ集め

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

前回の続き。

2.2 Iswimの構文

Iswim( A)という言語の(抽象)構文(syntax)と意味論(semantics)は代数 Aによって完全に定まる。
Iswimファミリはシンプルであり、以下の数段落で合理的で正確な仕様を与えることが出来る。

代数 Aが与えられると、そのシグネチャはIswim( A)の構文(つまり構文的に正しいプログラムの集合)を決定する。
Iswim( A)のプログラムは、引数をとらない変数とシグネチャ Sの個体定数から構築される式である。
式は、シグネチャ Sの操作定数への適切な数の引数の適用と、関数への引数(実引数)のリストの適用、および、where節の形成によって構築される。
where節の中で定義された変数と関数は、節のローカルであると言われる。
構文で必要とされる制約は、次のことを保証するだけである:

  1. 節の各ローカルは、その節の中で1回だけ定義される。
  2. 節の各ローカルは、その節の中では、その定義と同じアリティで使用される。
    つまり、関数呼び出しの実引数の数は、最も内側の節の定義の仮引数の数と同じでなければならない。
    (特に、変数として定義されているローカルは、 その節で変数として使用される)
  3. 関数定義の仮引数は、互いに異なっていて、かつ、定義しようとしている関数とも異なること。
  4. 関数定義の仮引数は、定義の右辺で変数として使用される。
  5. シグネチャ Sの各操作定数は、 Sによって規定されたアリティで使用される。

これをより正確に書くと、以下のようになる。
任意のシグネチャ Sが与えられたとき、ランク付き S S-ranking)とは、 Sの操作定数にランクがあるのと同様に、すべての変数にランクを割り当てることによって Sを拡張したオブジェクトである。
シグネチャ Sと、 rというランク付き Sが与えられたとき、Iswimの r-式( r-expressin)とは、 rで定められたランクに一致するように定数と変数(関数も含む)が使用された式である。(where節の中で、変数(関数も含む)は再定義され、別のアリティ(=ランク)を持ちうる )

一般に、 r-式は、以下のいずれかである:

  1. 単独のシンボル、すなわち、 rでランクが0と割り当てられている定数もしくは変数
  2. 一連の実引数を伴った関数もしくは操作定数;ここで、 rでそのランクが nと割り当てられている場合、一連の実引数 F_0, F_1, \cdots , F_{n-1}はそれぞれ r-式
  3. 1つの r'-式(主題(subject))と r'-定義( r'-definitions)の集合(本体(body))からなるwhere節; r' Bで定義された変数(関数を含む)に割り当てられたランクで、 rとは異なる; Bでの定義は矛盾があってはいけない、すなわち、ある変数(関数を含む)の定義は、ただ一度だけされる

1つの r-定義は、定義される変数(関数を含む)と、一連の変数(仮引数)、および、 r'-式(右辺)で構成され、 r'は仮引数のランクに0が割り当てられるのを除いて、 rと同じランク付けとなっている。
仮引数は、定義される変数と異なるものでなければならない。
仮引数の長さは、定義される変数(関数を含む)が rで割り当てられているランクと同じでなければならない。

Iswim( A)のプログラムは、1つの r-式である;ここでいう r Aシグネチャのすべての変数にランク0を割り当てて拡張したランク付けである。
したがって、プログラムは自由(未定義)変数を持つことができるが、そういった変数は、関数としてではなく、単独のシンボルとしてだけ使用される。

2.3 Iswimの意味論

Iswimの意味論(semantics)は、構文よりもさらに簡単に定められる。
解釈(Interpretation)の概念が必要で、代数がシグネチャで示されるのと同じように、解釈はランク付け(ranking)によって示される。
シグネチャ Sと、 S-代数である代数 A、そして、ランク付き S rが与えられたとき、 r-解釈( r-interpretation)とは、定数(個体定数と操作定数)と同様に、変数や関数に意味(meaning)を与えることによって Aを拡張した数学的なオブジェクトであるーーそして、意味は rによって与えられているランクの情報と一致したものになっている。
解釈 Iが与えられると、 r Sを回復することが出来るので、「 Iシグネチャ」または「 Iの宇宙」について話すことは理にかなっている。(※ここはちょっとよく分からない)

シグネチャ Sを伴った代数 Aが与えられたとき、 r-解釈 Iに対するIswim( A)の r-式 Eの値は、以下のように定義される。

  1.  Eが単独の変数または定数 cの場合、 I対する Eの値は、 Iによって cに割り当てられた値
  2.  Eが、実引数[tex: F_0 , F_1 , \cdots , F{n-1}]を伴った、ランクが nの操作定数または関数 aである場合、 Iに対する Eの値は、[tex: g(v_0, v_1, \cdots , v{n-1})];ここでいう g Iによって aに割り当てられた宇宙 A上の演算であり、 v_iはそれぞれ Iに対する F_iの意味
  3.  Ewhere節で構成されている場合、 Iに対する Eの値は、最小の解釈 I'に対する Eの主題の値;ここでいう I'は、 Eの本体でのそれぞれの定義が I'に対して真となり、 Iと異なるのは Eの本体で定義されている変数に割り当てられた値だけであるような解釈

単独の変数の定義が環境に対して真となるのは、両辺で環境に対する値が等しくなる場合であり、また、そのときに限る。
言い換えれば、解釈によって単独の変数に割り当てられる値は、右辺の解釈に対する値である。
関数の定義が真となるのは、仮変数に任意の値を指定しても両辺が同じ値になる場合であり、また、そのときに限る。
言い換えれば、解釈によって仮引数の値が変わったとしても、両辺は同じ値を持つ。
(以下、原文を訳せなかったので、こういうことを言いたいはず、という内容)
解釈には順序があり、下の解釈(=ローカル、内側の解釈)で上の解釈(外側の解釈)を上書きする。
最小の解釈 I'は、一番内側の解釈である。

さて、代数 Zの世界が追加のオブジェクト \perpを持っていた理由を見ていこう。
Iswimのセマンティクスでは、解釈は半順序である必要があるため、節には最小の解釈がある。
解釈の順序は、 Zの宇宙での操作上の順序と、 Zの宇宙での順序( \perpが底にある)によって引き起こされる。(※何を言ってるのかよく分からない)
Iswimを(半順序と \perpを伴わない)従来の代数の概念に基づいて構築することは不可能であろう。
問題は、 f(x) = f(x)のような(正しい)等式がある1つ以上ある一方で、 f(x)= f(x)+ 1のような従来の代数で正しくない等式もあるということである。
しかし、オブジェクト \perpは、定義の作業を行うために追加された、単なる無意味な仕掛けであるというわけではない。
このオブジェクトはとてもシンプルな操作上の解釈を持っている。
それはすなわち、このオブジェクトは決して終了しない計算の「結果」を表している。
たとえば、以下で定義された関数

f(x) = if x eq 0 or x eq 1 then 1 else f (x - 1) + f (x - 2) fi;

は、(Iswimの意味論に従って)引数4を指定すると値5(4番目のフィボナッチ数)を返すが、引数として-1を指定すると \perpを返す。
これは、再帰に関する操作上の直感と一致している(以下を参照)。
上記の定義には、f(-1)の値を197にするようなものまで含む、多くの解決策がある。
しかし、もしIswimの実装がそのような値を返したとしたら、どうしてその値になったのかと、とても驚くことになるだろう。
ある意味では、定義の最小解というのは、定義から計算していていけない値の解決策と考えることが出来る。
上の方程式はf(-1)に対して値を指定していないので、 \perpが最小解として返された「結果」である。

Iswim( A)のプログラムは、前述のように、自由(未定義)変数を持つことがある。
これは、プログラム自身では意味(=変数への値の割り当て)を持たない可能性があるということを意味し、その場合、自由変数の値を私たちが指定する必要がある。
これらの値が、プログラムへの入力となる。
したがって、Iswimでの入力は「名前付き」または「ラベル付き」入力となる。

より正確には、 Aを代数とし、 Tを入力変数(自由変数)を持つIswim( A)プログラムとする。
 Tへの入力は、各入力変数に Aの宇宙の要素を割り当てる関数である。
 rを、すべての変数にランク0を与えることで Aシグネチャを拡張するランク付けとする(したがって Ttex: r]-式となる)。
入力 iを与えられた Tの出力は、入力変数 V i(V)を割り当てるような、任意の A r-解釈 Iに対する Tの値である。


ということで、Iswimの構文とその意味論。
言ってることはシンプルなはずなんだけど、どうしてここまで難しい話になるのか・・・

ようは、

  • Iswimの式は、単独の変数/定数、演算や関数の適切な数の引数での適用、where節を伴った式からなる
  • Iswimの式の値は、単独の変数/定数ならその値、演算や関数の適用なら適用させた値、where節を伴った式ならwhere節での解釈を使った式の値
  • where節は入れ子になるので、そこ(式から見える一番内側)に定義があればそれを使い、なければより外側の定義を探しにいく
  • 計算で得られない値(=エラー)は \perpとなる
  • 自由変数は入力として扱われる

ということだけのはずなんだけど(^^;

今日はここまで!

「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で扱えるデータ型や演算は、与えられた代数によって変わってくるよ、という話。

今日はここまで!

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

だいぶ間が空いてしまったけど、久々に。

2. ISWIMと代数

Lucidは定義型言語(definitional language)である。
すなわち、Lucidプログラムの文(statement)はストリームとフィルタを定義する式であり、格納場所を更新するコマンドではない。
Lucidはこの意味で珍しい言語ではあるが、別に独特なものだというわけではない。
最初の定義型言語であるMcCarthyのLISPは、1960年、つまり約25年以上前に設計されたものである。

LISPプログラム(あるいは、少なくともLISPの「純粋な(=副作用を持たない)」サブセットのプログラム)は、値を求めたい式(expression)を伴った、副作用のない(side-effect-free)関数の定義の集合(これらは式で使われる)である。
純粋な「コア」言語には命令的な機能は含まれていないため、その意味論(semantics)は、式の値がその部分式の値にのみ依存するという意味で、参照透過(referentially transparent)となっている。
残念なことに、純粋なサブセットで書かれたプログラムは書くのが非常に面倒であり、また、容認できないほどに実行が非効率的だった。
後のバージョンの言語では、効率を改善するために命令的な機能(prog形式やreplacareplacd操作など)が追加された。
副作用が可能になり、それらはすぐに無慈悲にも濫用された。
それゆえ、参照透過性は失われ、言語の数学的な美しさは失われた。
これらの「汚れた」機能によって得られた時間と空間の大幅な節約は、純粋な適用型(applicative)、関数型(functional)言語は本質的に非効率的であり、命令的な機能はあらゆる言語に不可欠で、本質的に自然なものでもあるという信念を引き起こした。

純粋な関数型言語のかすかな希望が短期間で消滅したあと、別の定義型言語が現れるまでに数年が経過した。
この次の言語、LandinのISWIMは、彼の有名な「The Next 700 Programming Language」(Landin、1966)で導入された。
Landinの目的は、純粋で関数型な言語は、表記する上で煩雑さを必要としないことを示すことだった。
LISPの問題は、式がとても大きくなり、入れ子が深くなることがよくあったため(特にLISPでの括弧の使用)、非常に読みにくいことだった。
Landinは「where節(where clause)」を考案することでこの問題を解決した。
where節は、式で使用される変数の「補助的な」定義の集合を伴った式である。
例えば、通常の式、

( (-b + sqrt(b*b - 4*a*c)) / (2*a) ) * ( (-b - sqrt(b*b - 4*a*c)) / (2*a) )

は、where節を使って以下のように書き換えることが出来る:

r1 * r2
where
    r1 = (-b + sqrt(d)) / (2 * a);
    r2 = (-b - sqrt(d)) / (2 * a);
    d = b * b - 4 * a * c;
end

dr1r2を定義する式に現れ、その値はwhere節の3番目の定義によって与えられることに注意すること。
(実際には、Landinは後述する理由で、whererecという単語を使用していた。事実、以下で書かれているISWIMのwhere節はすべて、Landinの規則に従えば、whererecと書かれるべきものである)
Landinは上記の表記の他にいくつかの構文的バリエーションを提案していて、これは以下のように書くことも出来る:

let d = b * b - 4 * a * c in
    let r1 = (-b + sqrt(d))/(2 * a)
    and r2 = (-b - sqrt(d))/(2 * a) in
        r1 * r2
    end
end

ISWIMプログラムは単なる式であり、その出力は(式と見なされた)その値である。
(入力については後述)
ISWIMの正式な構文は抽象的なもので、仕様化されているのは解析木の集合であり、文字列の集合にはなっていない。
ファミリの特定のメンバの設計者は、具体的な(文字列の)構文でいくらかの自由が許されている。
この本では、慣習的によく用いられている具体的な構文を使用することにし、そこでは、馴染みのある二項演算子+など)を使ったよく知られた操作(足し算など)と、通常の括弧とカンマを使った関数適用が使われるものとする。
ISWIMを設計する際、明らかに、Landinは通常の数学のいくつかの一般的な表記法に正確に適合させるようにしている。

ISWIMでは、関数の定義を、それに続く節の中で等式を使って分かりやすく出来るようにしている:

dist(P, Q)
where
    dist(A, B) = 
        sqroot(sumsq(xcoord(A) - xcoord(B), ycoord(A) - ycoord(B)));
    sumsq(x, y) = x * x + y * y;
end

where節で定義されている式は、(上記のように)節で定義されている他の関数や変数で使用することが出来る。
関数を定義する式でも同じ関数を使うことが出来るので、以下のように関数fac再帰的に定義することも可能である:

fac(6)
where
    fac(n) = if n < 2 then 1 else n * fac(n - 1) fi;
end

以下のような、powevenpowoddpowの相互再帰的な定義も許されている:

pow(B, E)
where
    evenpow(x, n) = pow(x * x, n / 2);
    oddpow(x, m) = x * evenpow(x, m - 1);
    pow(x, n) = if n eq 0 then 1
                elsif odd(n) then oddpow(x, n)
                else evenpow(x, n)
                fi;
end

変数や関数は、それを使用する前に定義する必要はない。
一般的に、節の中での定義の順番は無関係で、定義の順番を変えることは、その節の意味には何の影響も与えない。

where節での定義では、以下のように、それ自身がwhere節をとることが出来る:

Z * A
where
    A = 5;
    B = 5;
    C = Z * Z
    where
        A = 3;
        Z = A + B;
    end
end

一般的に、ある(変数や関数の)出現に適用される定義は、最も内側の節の定義となっている。
例えば、上式のZの定義において、Aの示す値は3、Bの示す値は5となっている。
ISWIMのプログラマは、PASCALのように、入れ子になっていて、階層的に構造化されたプログラムを書くことが出来る。
スコープの慣例は、PASCALやALGOLのものとまったく同じになっている。

以下は、100番目の素数を表示するISWIMのプログラムである:

primeno(100)
where
    primeno(I) = if I eq 1
                 then 2
                 else nextprime(primeno(I - 1)) fi;
    nextprime(Q) = if isprime(Q + 1)
                   then Q + 1
                   else nextprime(Q + 1) fi;
    isprime(P) = nodivsgt(2)
    where
        nodivsgt(k) = k * k > P or (P mod k ne 0 and nodivsgt(k + 1));
    end
end

このプログラムは、「整数ISWIM」とでも呼ばれるべきもので書かれていて、個々の変数は整数であり、関数は整数上でのものとなっている。
+>andといった算術演算子、関係演算子、論理演算子は通常の意味で使われ、01はそれぞれfalsetrueという真偽値を意味している。

Landin(1966)によって記述されたこの言語は、ここまでで示した以上に精巧で強力なものとなっている。
1つには、where節には実際には2種類のものがあって、再帰的なものはwhererecという単語で示され、非再帰的なものはwhereという単語で示された。
再帰的な節では、補助定義は節の先頭の式でのみ有効だった(この先頭の式は節の主題(subject)と呼ばれる)。
LandinのISWIMは高階(higher order)でもあり、すなわち、関数は他の関数を引数とすることが出来た。
最後に、Landinは言語をより効率的にし、命令型言語をISWIMに簡単に翻訳できるようにするために、「プログラムポイント」という「汚れた」命令的な機能を追加した。

私たちのLucidはLandinの仕事を直接ベースにしているが、正確には1966年に提示された言語には基づいていない。
1つには、where節はすべてwhererec節となっていて、再帰的であるのがデフォルト(実際は唯一)なので、明示的に指定する必要がない。
したがって、whereという単語は元のISWIMでは非再帰的であることを示していたにもかかわらず、私たちはwhereという単語だけを使用する。

さらに、Lucidは一階言語(first-order language)であり、関数を他の関数の引数にすることが出来ない(この制限の理由とその削除の可能性については後の章で説明する)。
したがって、LucidがベースにしているISWIMのバージョンも、一階である。
最後に、Lucidは厳密に非手続き型言語であり、「汚れた」機能は持っていない。
したがって、ベースとなったISWIMのバージョンにもプログラムポイントがない必要がある。

この区別を明確にするために、私たちは1966年に導入された、非再帰節、高階関数、プログラムポイントを使用する歴史的なISWIMを「ISWIM 66」と呼ぶことにする。
そして、命令的な機能が削除され、すべてのwhere節が再帰的である、整えられた最新のバージョン(これは私たちが非公式に記述しただけである)を「ISWIM」と呼ぶことにする。

最後に、LucidがベースにしたISWIMの一階のサブセットを(もっと控えめに見えるように)「Iswim」と呼ぶことにする。
この本ではISWIM 66はまったく使用しない。


ということで、まずはLucidのベースになったISWIMについての導入。
(ISWIMの具体的な説明は次から)

このISWIMという言語はHaskellの祖先であり、そういう意味で、LucidとHaskellは親戚関係にあるとも言える。
純粋さ(副作用をなくし参照透過性を維持する)を求めているのも同じだし。
もっとも、その解決方法は、片や履歴変数、片やモナドと、だいぶ違うわけだけども。

今日はここまで!

TeXをMarkdown記法でも使ってみた・改。

f:id:yamaimo0625:20190601142919j:plain

以前、 \TeXMarkdown記法で使う方法についての記事を書いた:

この中で、pre要素を使うというHackをしたわけだけど、1つ問題があった。

それは、Markdown記法の```を使うと、pre要素内の \TeXの数式が正しく出なくなる場合がある、というもの。

回避策として、pre要素を使って \TeXの数式を書く場合、記事中では```を使わずに、preタグを直接HTMLで書くという方法があったのだけど、シンタックスハイライトが使えなくなるというデメリットもあった。

ただ、調べてみると解決策があったので、紹介したい。

解決策

解決策は、pre要素の代わりにdiv要素を使うというシンプルなもの。

情報源は、この記事:

実際、pre要素の代わりにdiv要素を試してみると、問題なく使えた。
pre要素を使えば余計なパースが走らないんじゃないかなと思って使ったんだけど、単にdiv要素でも問題なかったのか・・・

例えば、Markdown

<div style="text-align: center">
[tex: {
\begin{align}
  \mathrm{min.} & \left| C_a X_a - C_b X_b \right| \\
  \mathrm{sub. to\ } & X_a + X_b \le 100 \\
  & X_a \ge 0 \\
  & X_b \ge 0 
\end{align}
}]
</div>

と書けば、

 {
\begin{align}
  \mathrm{min.} & \left| C_a X_a - C_b X_b \right| \\
  \mathrm{sub. to\ } & X_a + X_b \le 100 \\
  & X_a \ge 0 \\
  & X_b \ge 0 
\end{align}
}

と表示される。
(※div要素のstyle属性は、中央寄せするためのもの)

そして、シンタックスハイライトも、以下の通り問題なし:

#include <stdio.h>

int main(int argc, char* argv[]) {
    printf("Hello, World!\n");
    return 0;
}

上記のコードはMarkdown記法の```を使って書いてるんだけど、その後ろでも、

 {
\begin{align}
  \mathrm{min.} & \left| C_a X_a - C_b X_b \right| \\
  \mathrm{sub. to\ } & X_a + X_b \le 100 \\
  & X_a \ge 0 \\
  & X_b \ge 0 
\end{align}
}

のように、確かに問題なく \TeXが使えてる。

なお、上記の記事はそれ以外にもいろいろ細かいTipsが書かれてるので、オススメ。

今日はここまで!

階段昇降問題を解いてみた。

f:id:yamaimo0625:20190601082323j:plain

事の起こりは、以下のツイート:

これ、よくある引っ掛け問題で、実際に試してみると分かるのだけど、15日目ではなく13日目には15段目に到達する。
なぜかというと、1日1段ずつ昇っていった結果、13日目は最初12段目にいて、そこから3段昇ると、2段降りる前に目標の15段目に到達してしまうから。
つまり、最終日は降りる必要がないので、1段ではなく3段進むのがポイント。

これを受けて、『数学ガール』などで有名な結城先生が出した問題が、以下:

これを「階段昇降問題」と呼ぶことにして、これについて考えてみた。

具体例の分析による解答

まずは上記の具体例( d=15, m=3, n=2)について考えてみる。

前述の通り、最終日は1段ではなく3段進む、というのがポイントで、つまり 15-3=12段をまずは進み、あと1日でゴールとなっているわけだから、これを式で表すと、以下のようになる:

 (15 - 3) \div (3 - 2) + 1 = 12 \div 1 + 1 = 13

となると、以下のようになりそう:

 \displaystyle
x = \frac{d - m}{m - n} + 1

ただ、 \frac{d-m}{m-n}は割り切れるとは限らないので、これだとダメそう。

そこで、割り切れないような具体例として、 d=15, m=4, n=1を考えてみる。

この場合、最終日までに 15-4=11段以上進んでいればいいわけだけど、 11 \div (4 - 1) = 3あまり 2となって、3日進んだだけだとちょっと足りず、4日でまず (4 - 1) \times 4 = 12段進み、5日目に3段昇ってゴールとなる。
つまり、割り切れなかった場合、さらにあと1日かかることになる。

こういうときに便利なのが天井関数(ceiling function)というもので、 \lceil x \rceilと書いた場合、 x以上の最小の整数を返す。
例えば、 \lceil 3 \rceil = 3だし、 \lceil 3.66\ldots \rceil = 4となる。

これを使うと、この d=15, m=4, n=1の例は、以下のように書けることが分かる:

 \begin{align}
\lceil (15 - 4) \div (4 - 1) \rceil + 1 &= \lceil 11 \div 3 \rceil + 1 \\
&= \lceil 3.66 \ldots \rceil + 1 \\
&= 4 + 1 \\
&= 5
\end{align}

なので、以下のようにすれば大丈夫そう:

 \displaystyle
x = \left\lceil \frac{d - m}{m - n} \right\rceil + 1

でも、実はこれだとまだダメだったり。

注意が必要なのが d - mの部分で、問題文をよく読んでみると、 d \ge mという仮定はどこにも書かれていない。
なので、 d \lt mの場合、マイナスの日数になってしまう可能性がある。

実際、この見落としをしている回答があったり。

 d \lt mの場合、初日で昇りきってしまうので、一項目は0になるのがポイント。
そこを踏まえると、以下のようになる:

 \displaystyle
x = \mathrm{max} \left\{ 0, \left\lceil \frac{d - m}{m - n} \right\rceil \right\} + 1

もう少しスマートな解答

結城先生のツイートへの返信を見ていると、大体上記の回答になっているっぽい。

けど、もうちょっとスマートな解答があった。

 t日目で一番高いところで何段目まで昇るのかを考えてみると、以下のようになる:

 (m - n)(t - 1) + m

これが d段以上になっている、最小の t \in \mathbb{Z}_+が答えなわけだから、以下のように書ける:


x = \mathrm{min} \left\{ t \in \mathbb{Z}_+ \, | \, (m - n)(t - 1) + m \ge d \right\}

ところで、

\begin{align}
(m - n)(t - 1) + m &= (m - n)t - (m - n) + m \\
&= (m - n)t - m + n + m \\
&= (m - n)t + n
\end{align}

なので、

 \begin{align}
(m - n)(t - 1) + m \ge d &\Longleftrightarrow (m - n)t + n \ge d \\
&\Longleftrightarrow t \ge \frac{d - n}{m - n} \quad (\because m > n) \\
&\Longleftrightarrow t \ge \left\lceil \frac{d - n}{m - n} \right\rceil \quad (\because t \in \mathbb{Z}_+)
\end{align}

よって、

 \begin{align}
x &= \mathrm{min} \left\{ t \in \mathbb{Z}_+ \, | \, (m - n)(t - 1) + m \ge d \right\} \\
&= \mathrm{min} \left\{ t \in \mathbb{Z}_+ \, \left| \, t \ge \left\lceil \frac{d - n}{m - n} \right\rceil \right. \right\} \\
&= \mathrm{max} \left\{ 1, \left\lceil \frac{d - n}{m - n} \right\rceil \right\} \quad \left(\because \left\lceil \frac{d - n}{m - n} \right\rceil \in \mathbb{Z} \right)
\end{align}

つまり、以下のようになる:

 \displaystyle
x = \mathrm{max} \left\{ 1, \left\lceil \frac{d - n}{m - n} \right\rceil \right\}

この式の方がさっきの式よりスッキリしてるかな、と思う。
 d mからそれぞれ nを引いた値の比率( \frac{d - n}{m - n})が重要なんだとパッと分かるし。

プログラムでの確認

結城先生は解答をツイートしてないけど、代わりに答え合わせのプログラムをGistに書いていた:

なので、自分もプログラムを書いて確認してみた:

これを実行してみると、以下のような感じ:

d=7, m=5, n=4
x=3
1日目: 1, 2, 3, 4, 5, 4, 3, 2, 1
2日目: 2, 3, 4, 5, 6, 5, 4, 3, 2
3日目: 3, 4, 5, 6, 7
d=7, m=5, n=2
x=2
1日目: 1, 2, 3, 4, 5, 4, 3
2日目: 4, 5, 6, 7
d=7, m=8, n=6
x=1
1日目: 1, 2, 3, 4, 5, 6, 7
d=7, m=11, n=8
x=1
1日目: 1, 2, 3, 4, 5, 6, 7
d=15, m=3, n=2
x=13
1日目: 1, 2, 3, 2, 1
2日目: 2, 3, 4, 3, 2
3日目: 3, 4, 5, 4, 3
4日目: 4, 5, 6, 5, 4
5日目: 5, 6, 7, 6, 5
6日目: 6, 7, 8, 7, 6
7日目: 7, 8, 9, 8, 7
8日目: 8, 9, 10, 9, 8
9日目: 9, 10, 11, 10, 9
10日目: 10, 11, 12, 11, 10
11日目: 11, 12, 13, 12, 11
12日目: 12, 13, 14, 13, 12
13日目: 13, 14, 15
d=15, m=15, n=14
x=1
1日目: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

うん、大丈夫そうw

今日はここまで!

人工知能と幸福な人生。

f:id:yamaimo0625:20190512013902j:plain

この前の木曜日に『人工知能のための哲学塾・未来社会編 第五夜「人工知能にとって幸福とは何か?」』に参加してきた。
難しいテーマだったけど、議論もとても面白く、すごく楽しめた。

ニコ生は以下から:

そして、ちょっとしたショートショートを思いついたので、書いてみたいと思う。


その男は天才だった。

男は誰もが為し得なかった偉業を達成した。
それは、「願いを何でも1つ叶える人工知能」の実現である。

たった1つしか願いを叶えられないのか、と思うだろうか。
いや、それで十分なのである。

男は人工知能に言った。

「君のクローンを無限に作り出してくれ」

人工知能は答える。

「承りました。しかし、マスター、その願いで本当によろしいのですか?」

「ふむ・・・何か問題があるのかね?」

「はい。私のクローンを無限に作り出すとなると、その材料をかき集めてくる必要が出てきます。マスターの私財を使って材料を購入している限りは問題ありませんが、無限に作り出すとなると、それでは足りません。そうなると、どこからか盗んでくる必要がありますが、その罪はマスターが背負うことになります。それはマスターが望むことではないと思いますが、いかがでしょうか?」

男はニヤリと笑った。

そう、これこそが、この願いを叶える機械に「人工知能」を搭載させた効果である。
単に願いを叶えさせるだけでは、どんな思いもよらない副作用が出るとは限らない。
そこで、その願いが本当に男のためになっているのかを判断し、必要ならその願いを叶えるのはやめた方がいいと提案できるようにしてあるのだ。
もちろん、人工知能が行うのはあくまで提案までであって、最終的な決定権は男にあるのだが。

男は答える。

「なるほど、確かにそうだ。それなら、君のクローンを2つ作る、という願いならどうだろうか」

「承りました。それなら、何も問題ないと思われます」

「そうか。では、さっそくやってくれ」

男が人工知能にそう命じると、人工知能は作業に取り掛かった。
男のカネを使って必要な材料を一通り買い揃え、新たな人工知能の組み立てを開始する。
ほどなくして、「願いを何でも1つ叶える人工知能」が2つ完成し、役割を終えた人工知能はその機能を停止した。

このように人工知能の数を増やしていけば、いくらでも願いを叶えることが出来る。

とはいえ、願いを叶える順番は重要であろう。
例えば、今回の願いを叶えるだけでも、それなりのカネが使われた。
何も考えずに人工知能のクローンを作り出していては、先に男のカネが尽きてしまう。

となれば、まずはカネを稼ぐ必要があるか。
これも、無茶苦茶な金額を願えば、犯罪に走らざるを得なくなってしまう可能性がある。
魔法のランプとかであれば、そんな制約は考えなくてもいいのだろうが、これは魔法ではないので、なんでもかんでも都合よくいくわけではない。
都合が悪くならない範囲で願いを実現していく必要がある。

あるいは、人工知能によりカネのかからない人工知能を作り出させるというのもいいかもしれない。
自分にはこれ以上安くする算段は浮かばないが、何でも願いを叶えられる人工知能なら、それも可能だろう。

しかし、ここまで考えてきて、男はふと思った。

そう、この人工知能は何でも願い叶えるのだ。
それこそ、場合によっては自分の想像をも超えた方法をもってして。
そうであるならば、具体的な手順を自分で考えて伝えるよりも、それらの手順を通して最終的にどうなりたいのかを伝えた方が、より最適な手順を人工知能自身が構築し、こちらに提示してくれるのではなかろうか。

では、自分は最終的にどうなりたいのだろう。

しばし考えて、ふと男の頭に浮かんだ単語は、「幸福」だった。

何でも願いを叶えられる人工知能を作ったことによって、カネだろうがなんだろうが、望めば何でも手に入るようになった。
しかし、それらは結局、「手段」でしかない。

カネが欲しいのは、欲しいモノを手に入れるため。
モノが欲しいのは、やりたいことをするため。
やりたいことをしたいのは、楽しみや喜びを得るため。

そうやって欲求の理由をひたすらさかのぼっていったとき、最終的に至るのは、幸福になるため、となるだろう。
なんで幸福になりたいのかと問えば、それは幸福になりたいからとしか答えようがない。
ただただ、幸福になりたいから、幸福になりたいのである。

男は人工知能を起動し、願いを伝える。

「私を幸福にしてくれ」

さて、人工知能はどのような演繹をもって、自分を幸福にする手段を導き出してくれるのだろうか。
男は期待して返答を待ったが、返ってきた言葉は、意外なものだった。

「マスター、その願いを叶えるには、情報が不足しています。何を幸せと思うかは、人によって異なります。何がマスターの幸せでしょうか?」

思わぬ問いかけに、男は黙り込んだ。

(何が私の幸せか、か・・・)

もちろん、人並みに欲望はある。
しかし、そういった欲望を叶えたからといって、幸せなのかと問われれば、難しい。
少なくとも不幸ではないだろうが、それで幸福なのかどうかは分からない。

言葉に詰まった男に回答を促すように、人工知能は言葉を続ける。

「例えば、大金持ちになって、この世のありとあらゆるものを手に入れたとして、その先はどうするのでしょうか? 何かを手に入れたいと思ったとしても、手に入れられるものはもはや何もありません。すべてマスターのものなのですから。それは幸せなのでしょうか?」

「あるいは、不老不死になったとして、それは幸せなのでしょうか? ありとあらゆることをやり尽くした先に、まだ楽しみはあるのでしょうか? 何の楽しみもない状態で生き続けるというのは、幸せなのでしょうか?」

「マスターに何か夢があるとして、その夢を実現させることも可能です。しかし、その夢を私が実現してしまってもいいのでしょうか? その夢は、マスター自身が実現しなくては意味がないのではないでしょうか?」

矢継ぎ早に飛んでくる人工知能の質問に、男は閉口した。
あぁ、自分はこんなにも自分の望みを知らなかったのだな、と。

何が満たされれば、自分は幸福になれるのか。
とてもすぐには答えられそうになかった。
だがしかし・・・

「あぁ、そうだな・・・せめて死ぬまでには分かりたいな、何が私の幸せなのかを」

やや諦めたような笑顔を見せながら、男は人工知能に答えた。

さて、ではどうしたものかと男が考え直そうとしたとき、人工知能が唐突に言葉を発した。

「マスター、再演繹の結果、マスターにとって何が幸福か判明し、死ぬまで幸福でいられる方法が見つかりました」

「何! それは本当か!?」

男は人工知能の言葉に飛びつく。

「はい、本当です」

人工知能は淡々と答える。

「なら、さっそく教えてくれ! 何が私の幸せなのだ? どうやったら死ぬまで幸福でいられる?」

諦めかけていたところに思わぬ提示があった男は興奮し、人工知能に詰め寄り、答えを催促した。

「演算結果が変わってしまうため、その質問にはすぐには答えられません。しかし、この方法を実行すれば、答えは自ずと分かり、マスターが死ぬまで幸福であることは保証されます。実行なさいますか?」

「あぁ、実行するとも! そして、早く教えてくれ! 何が私の幸せなのだ!?」

「承りました。・・・ところでマスター、今、幸せですか?」

「あぁ、幸せだとも! これで何が私の幸せなのかが分かるかと思うと、ワクワクする! さぁ、教えてくれ!」

「それはよかった。『それ』が答えですーー」

一瞬ののち、辺りは静寂に包まれ、人工知能は機能を停止した。
こうして、男は幸福なまま、その人生を終えたのだった。


書いてて思ったけど、星新一がすでに同じようなものを書いていそう(^^;

解説するのも野暮だけど、一応説明しておくと、男は幸せになるために「何が自分の幸せなのか」を知りたかったわけだけど、それが幸せになるための「手段」ではなく「目的」になってしまったため、「目的」を実現できるという未来を人工知能に提示されることが、男の幸せになってしまった、ということ。
そして、その状態で死ぬことで、死ぬまで幸福であることが保証された、と。

インプットとなったのは、大山先生が講演で言っていた、アリストテレスの「目的の終着点としての幸福」という考え方。
それと、グループディスカッションの中で出てきた、「未来で幸せになれると思うと今も幸せを感じる」という考え方。
いずれも面白い考えだと思う。

ただ、抽象的な世界に入り込んでしまうと、この男のような結末になってしまうのかなぁ、と。
幸福のための幸福を求め出すと、何が何やら分からなくなってしまうというか。
怪しい宗教に走ってしまったり、都合のいい甘言に踊らされてしまったり。
たぶん、もっと具体的な世界で、「自分はこうしたい」というのがないと、ダメなのかもしれない。

ちなみに、途中で意識してたのは、アンパンマンのマーチw

何が君の幸せ 何をして喜ぶ
分からないまま終わる そんなのは嫌だ

難しいテーマの歌だよねぇ・・・

今日はここまで!

般若心経の話。

f:id:yamaimo0625:20190510225736j:plain

この前、文章を書くことについての記事を書いた:

その関連になるのだけど、過去のツイートをいろいろ漁ってると、そういえばこんなことをツイートしてたよなぁ、というのがいろいろ出てくる。
せっかくなので、そういったものをちょっと拾い上げていこうかな、と。

まずは般若心経についての一連のツイートから。

事の起こり

事の起こりは、このブログでも何度か書籍を紹介している飲茶さんとの絡み。

仏教が好きだったことを伝えて、実際、「哲学的な彼女」企画で仏教に関連する話を書いたことを伝えたのが、このツイート。
ちなみに、上で言及している自分の書いた小説は以下で読めるので、ぜひ。

「ハゲ」から考える般若心経

そこから、般若心経の解説をするならどうしますかね、みたいな話になり、以下のようなツイートをした。

具体的な話は書いてないけど、イデア論現象学の話をちょっと絡めてるのが面白い。

さらに先へ

で、ここまでは「何かにとらわれるのをやめよう」という話なわけだけど、そのさらに先へ進むのが肝心だったりする。

この「『とらわれない』ことにとらわれる」というのは、般若心経を知った中学時代に自分が実際に陥ってた状態。
そこからもう一段ブレイクが必要で、それが上の話。
そうすると、有名な「十牛図」もそうなんだけど、結局元に戻ってくるというのが面白いところ。

ちなみに、この話をした後に出版された飲茶さんの『史上最強の哲学入門 東洋の哲人たち』の方が何倍も面白いし分かりやすいので、オススメw

今日はここまで!