Languagesという本があります。この本の6章が少し難しいという話があったので読んでみたところ、確かにある程度数学に慣れていないと難しそうな記述があったので、その気持を簡単に理解することに努めます。手を動かさないと理解が進まないだろうと思ったので、実際に計算もします。名無し表現のモチベーション5章以前で、(型無しの)ラムダ計算を導入しているのですが、ラムダ計算を用いて実際に新しい式を作ろうとすると、変数名の衝突が問題になる場合があります。x$をどう扱うべきかという問題が生じます。これは最後の束縛が有効というような定義の仕方をすれば一意に解釈ができますが、しかし人間にとって易しくありません。これを避けるための書き換えのルールなどはいくつかありますが、そのうちの「名無し表現」によって項を表現することで変数束縛を明快な形に書き換える、という方法があります。以下、この3行を少し丁寧に解説します。最小性の説明は数学的に詳しく気になる人だけでよいと思います。本質的なのは、この定義によって帰納的にどのような集合(族)が定まるのか?ということです。set.と書いてありますが、これがある意味で曲者で、まず集合族とは何か?という話になります。集合族とは、この場面においては早い話が単純に集合の集合であって、集合たちを添え字付けたものになります。今回の定義においては、$\mathcal{T_0,T_1,T_2,\cdots}$というのはそれぞれ集合だということですね。最小性(1):一般には複数存在し得ることこの$\mathcal{T_0,T_1,T_2,\cdots}$たちが満たす関係式というのが1,2,3になっていて、かつ、これらを満たす最小の集合であるということを要請しています。\mathcal{T_0,T_1,T_2,\cdots}$とするとき、適当な自然数$m$を取ってきて、以下のようにして新しい集合族$\mathcal{S}$を構成します。\mathcal{T_n}$そうすると、実はこの$\mathcal{S}$も最小性以外の$\mathcal{T}$の条件を満たすことが(適当な計算によって)わかります。従って、最小性以外の条件だけでは、そのような集合族は複数存在し得るのですね。最小性(2):そもそも最小の集合族の存在が自明でないことここで、一層難しいことを言うと、そもそも"最小"という条件を満たすものが一意に定まるか否かは、実は自明なことではありません。B$でも)ない場合があって、そのような場合には比較ができず、この2つの集合の間に"最小"という概念を定めることは通常はできないからです。従って、"最小の集合族"という言い回しも、実は全く自明ではなくて、そもそもそのようなものが存在するのか?というところから考える必要があります。\rbrace$が同じ条件を満たすことを言えばよいです。U_n}$というのは、取り得る$\mathcal{U_n}$たちすべてについての共通部分を意味します。\mathcal{U_{n,i}}$などと書きます。)というのも、今回の場合は1.の条件により条件を満たす集合が空でないことが保証されているため、最小性以外のすべての条件を満たす集合についての共通部分をとれば、そのすべての集合についての共通部分が条件を満たすならば自然にそれが(空でない)最小の集合となるからです。\mathcal{U_{n-1}}$といえます。\mathcal{U}$も同様の条件を満たすことがわかったので、最小性以外の条件を満たすものたちについての共通部分を取ると、ある空でない最小の集合(族)が定まることがわかりました。\mathcal{U_n}$が条件を満たすと言うことはできないので、結局、無限を用いた記法に改めました。$を含む開集合(開区間:境界が等号ではなく不等号になっているやつ)の族などをとると、個々の開集合の共通部分は開集合になりますが、その開集合族の共通部分は[0,1]で閉です。実際の項の形さて、上記の項の定義は「含まれない項」についての定義は特にないため、3つの条件が矛盾するようなことはなく、従って定義によって空でない集合族が定まることはわかりました。一方で、具体的な形は何も分かっていません。この定義は帰納的な定義となっているので、具体的に書き下すことにしましょう。その前に、$\mathcal{T_0}$は無限集合である(要素が無限に存在する集合である)ということに注意をしておきます。)))}$という形の要素をいくらでも作れるので、要素は無限に存在します。λ.4これは、とてもよくない例です。$\mathcal{T_n}$たちは無限に存在するので、途中までの書き下し例としてはこれで良いようにも見えますが、例えば$\lambda.\lambda.0$というようなものは出てきません。このやり方で出てくるのは、$\lambda$がたかだか一つの項だけです。$と列挙しているようなものですね。たしかに分数を列挙してはいますが、いつまでたっても$2/3$などは出てこないでしょうし、仮分数のように1より大きな分数の存在を知ることもできません。書いて属性を理解しようとしたつもりなのに、何も理解できない酷い例ですね。どのように改善すればよいのでしょうか。ましな書き下し例さきほどの分数についてのポエムたとえに少しヒントがあります。(正の)分数の場合、以下のようにすると、すべての分数がどこかには出てくるような書き下し方になります:$1/1,1/2,2/1,1/3,2/2,3/1,1/4,2/3,3/2,4/1,\cdots$これは一つの方向に対して伸ばしてしまわずに、分子分母の合計が2になる、3になる、4になる、...という条件で書いているのですね。これと同じようなことを考えてみると...、例えば、文字数によって区切るという方法があります。2のルールも、3のルールも、必ず項を構成する文字数は増加するので、文字数が一定以下の項はある程度制限ができるはずです。\mathcal{T_n}$なので、単純な文字数だけではなく、$n$の深さも考慮するようにしてみます。すると、少しマシな書き下し方ができます。terms[:1]]))printのところで、$\mathcal{T_0}$に限定しています。出力結果に適当に改行を入れると以下のようになります。λ.λ.λ.2$\mathcal{T_0}$の中にも2が出てきます。これは、$\mathcal{T_3}$に含まれる2に対して2つ目のルールを3回適用した結果の項です。帰納的な定義だけだとなかなか把握することが難しい場合もありますが、このように書き下してみると、実は$\mathcal{T_0}$の中には自由変数が居ないということがわかります。0)となっていて、実はそれ以外の変数はすべて束縛されています。all.と書いてあるのですが、確かにそうなっていそうですね。いうのは、実際、2の条件(操作)では自由変数が一つ減り、3の条件(操作)では自由変数の数は変わらないので、1で定まる自由変数が各$\mathcal{T_n}$の自由変数の上限を定めているのでした。このようなことは、ある程度数学に慣れていれば自然に発想されると思いますが、実際には手を動かさないとわかりにくいと思います。手を動かすといっても、この帰納的な定義はそもそも無限集合を扱っているので、下手な触り方をすると間違った方向に理解が進んでしまいます。そこで、今回は分数を列挙する時のうまいやり方との対比を用いて、重み付けをすることによって少しマシな列挙方法を用いて、実際の項に触れるという事をしました。そもそも6章を読むには、以下の知識が前提だったので、この記事単独でもある程度読めるように内容を示しておきます。定義((名前付きの・名無しでない)項)可算集合$\mathcal{V}$が与えられたとき、$\mathcal{V}$を変数集合とする名前付きの項$\mathcal{T'}$とは、以下で(帰納的に)定まる最小の集合とする。\mathcal{T'}}$:この形の項を変数と呼ぶ。\mathcal{T'}$:この形の項を(ラムダ)抽象と呼ぶ。\mathcal{T'}}$:この形の項を(関数)適用と呼ぶ。※注:本書では単に$\mathcal{T}$となっていましたが、いまは名無し表現の定義との混同を避けるためにあえて$\mathcal{T'}$としています。例によって最小性の確認などが必要ですが、名無しの項の場合と同様に考えれば自明なので省略します。この、変数集合を用いて定まる項と、名無しの項の間の対応ルールの考え方として、コンテキストと呼ばれるものがあります。定義(命名コンテキスト)$\mathcal{V}$を変数集合とする。x_0}$が与えられたときは、各Brujin添字$i$に対して$\sf{x_i}$を割り当てる。ラムダ抽象の結合が右側から行われることと合わせて、右側の変数から順に$0,1,2,\cdots$と割り当てることに注意しよう。$\Gamma$に登場する変数の集合を$\mathrm{dom}\Gamma$で表す。要するに0から順番に適当な変数を割り当てるという、かなり普通のことを言っています。定義(シフト)$c,d$を$0$を含む自然数とする。項$\sf{t}$の$c$を断面とする$d-$シフトとは、以下のように定まる項のことで、これを$\uparrow^d_c$と書く。k})$と書くことがある。これは定義の通りですが、帰納的な定義のそれぞれに対しての定義が与えられている、ということに注意することぐらいでしょうか。こちらの操作の場合は、書き下しとは違って、具体的な項が与えられた時の計算について順序などを深く考えずに簡単に行うことができます。そのような点においては、帰納的な定義というのは非常に扱いやすい性質もあるものなんですね。$$この定義は、先ほどと同じパターンではあるものの、「代入」という言葉を使っているという点において、少し特殊です。いうのも、代入という言葉を目にすると、多くの人は既に代入というものをなんとなく知っているはずなので、それからの類推や対比で理解をしようとするのが自然です。これは定義ではあるものの、一方でそれを代入と呼ぶという主張でもあるのですね。数学的な意味では差は無いですが、人間が読んで理解をする上では、じつは主張になっている定義が存在するということは重要なポイントと思います。説明が長くなりましたが、では、確かにそれが代入と呼び表せるような内容なのかを確認してみましょう。1つ目、3つ目はさもありなんという定義かと思います。j+1}$への代入という事になっています。t_1}$の自由変数はシフトしないので、代入対象の変数が0であっても、元の式の0以外の自由変数が変化する場合があります(というかλが存在する場合で実際に置換が発生する場合は確実にそう)。代入対象の変数は、あくまでも何番目の自由変数に代入するかという事を意味していて、単純な置き換えではないことに注意しておきます。こちらも例によって簡単に計算をすることができます。it.まさに、上で述べた通り、この定義の主張としての性質を踏まえた上で、自然な定義であるという事を確認するような練習問題になっているのでした。定義(β簡約)この章は、β簡約まで述べるとおしまいですね。余談この本はこうした難しさがあるので、訳本の監訳者いわく、サポートサイトができたらジュンク堂トークのPDFも載ると思いますが、これだけは先に:型システム入門(TAPL)はとりあえず1,3,8,5,9,11章(&2章の必要な部分)と、あとは好きな章を読めば「読んだ」ことにしても良いと思います!(60%本気)ということだったので、そのような読み方もあるのかもしれません。https://twitter.com/esumii/status/315135694462939137ただ、型システムに関して言えば、基本的には本書は入門という位置づけのようです。Qrunch.netサーバー提供フィードバックを送信する。