読者です 読者をやめる 読者になる 読者になる

Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

プログラムにおいて自然数を構成する話について

はじめに

たぶん、多くの人々が「自然数とは?」と言われると、「そりゃ、1, 2, 3とかそのあたりの整数のことでしょ」という、具体例を挙げられるかと思われるのですが、実際に「じゃあその自然数とやらを作る方法ってあるんですか」というと、目の前のリンゴを指して「いや、あれが1つとか2つでしょ」ということになると思う。

今回は、その辺りの「どうやって自然数を生成するか」という、誰にとって興味があるのかわからないネタを久しぶりに技術的な話としてやろうと思う。自分も一週間程度は追いかけたけれど、聞きかじりのネタしかないので、間違いなく、おかしい部分が山ほどあると思うけれど、それらについては、数学徒の手厳しい意見を頂ければと思っている。

そもそも自然数とは

実際の実装に入る前位に、二つのトピックを取り上げておく。まず一つには、ノイマン及びシェルメロによる、集合論からの自然数生成のアプローチだ。これの元になっているのはペアノの公理というものだ。ペアノの公理は、下のようなものとなっている:

ペアノの公理

  1. {0 \in \mathbb{N} }
  2. {n \in \mathbb{N} \to n' \in \mathbb{N} }
  3. {n' \neq 0 }
  4. {m' = n' \to m = n }
  5. {\forall X [0 \in X \land \forall x (x \in X \to x' \in X) \to \mathbb{N} \subset X }

馬鹿正直に書き写してみたものの、正直自分の力では全くわからない。むしろ、コンピューター創生者とも呼ばれるフォン・ノイマンの構成法がわかりやすいだろう。ノイマンの構成法は以下の通りになる:

ノイマンの構成法

  1. { 0 = \emptyset }
  2. { 1 = \{ \emptyset \} }
  3. { 2 = \{ \emptyset , \{ \emptyset \} \} }

といったように。しかし、このように書き出していく方法は、余りにもエレガントではないし、単純に面倒臭い。無限の自然数に対して無限のこのような書き下しははっきりいえば現実的ではない。

従って、この自然数の構成方法を、循環論法を使わずになんとか定義しておきたい。そこで、以下のような定義を使うことができる。

集合{x}に対して, {x' =  x \cup \{x\} }とおく. そして, 以下の条件をみたす集合{A}を帰納的と呼ぶ: (1)  { \emptyset \in A }, (2) すべての{x \in A}に対して {x' \in A}

さて、このとき「次の数」を表すような関数があると便利だろう。これを後続者関数とどうも呼ぶらしい。この後続者関数を、この記事では{s}と定義しよう。

例えば、上記でいうならば次のような対応としてみることができる。

ノイマンの構成法 + 後続者関数

  1. { 0 = \emptyset }
  2. { 1 = s(0) = \{ \emptyset \} }
  3. { 2 = s(1) = \{ \emptyset , \{ \emptyset \} \} }

さて、この後続者関数があることによって、以下のように書くことが可能になる。

 {2 = s(s(0)) }

Haskellで表現してみよう

さて、数学の話ばっかりでコードが出てこないので、ここでHaskellに登場してもらおう。そもそも、このような後続者関数、つまり先ほど表現した{ 2 = s(s(0)) }を、あえてss0といった、括弧を省略した形に直してみると、この0とsは数を表すための記号である、という見方ができる。乱暴に言ってしまえば、これはデータ構造を現しているという見方は可能である。

そこで、Haskellで表現するならば、下のようなデータ構造になるだろう:

data Nat = Zero | Succ Nat
         deriving (Show)

ついでなので、私たちが良く知っている10進法からこの後続者関数を用いた構造に置換する関数も定義しておこう:

unfoldN :: Integer -> Nat
unfoldN 0 = Zero
unfoldN x = Succ . unfoldN $ x - 1

さて、なぜこのような回り道をしているかというと、これらを定義するさいに、ラムダの考え方があると非常に便利であり、チャーチ数(Church numerals)がそれによって定義されている。ラムダについてはこのエントリを参考にしてもらうとして、チャーチ数の説明を以下に書き記しておく:

チャーチ数について

チャーチ数については、以下のように表現することができる:

  •  {\lambda(f)\lambda(x)f(f(...f(x)...))}

例えば、0, 1, 2, 3だと下のように書くことができる:

  1. {0 = \lambda(f)\lambda(x)x}
  2. {1 = \lambda(f)\lambda(x)f(x)}
  3. {2 = \lambda(f)\lambda(x)f(f(x))}
  4. {3 = \lambda(f)\lambda(x)f(f(f(x)))}

あくまでも素人の雑感ではあるけれど、ポイントとしては、いわゆる0としていたものをxとして抽象化し、後続者関数を単なる関数として抽象化しているのがポイントであるというように感じる。もちろん、後続者関数も「次の数である」という表現なので、必ずしも {s(x) = x + 1}とは限らない、とは言えるかと思うけれど、この場合においても同様のことが考えられる。

さて、そこで気になることが一つだけある。先ほどHaskellでデータ化したものをIntegerに直したいという欲求が出てくる筈。そこでまず最初に、このデータ形式を関数に変換するような畳み込み関数を定義する:

foldN :: (a -> a) -> a -> Nat -> a
foldN h c Zero = c
foldN h c (Succ n) = h (foldN h c n)

ただ、これをこのままIntegerの変換に使うのは非常に面倒臭いのは事実なので、先にエイリアス的な関数を作ってしまったほうがよい気がするので、そうする:

nat_to_int :: Nat -> Integer
nat_to_int = foldN (\x -> x + 1) 0

Haskellは、言語仕様か処理系の癖かはわからないけれど、引数が足りないときは、足りない部分は放っておいて、部分適用した関数となる。上記の場合ですと、後続者関数に当たる部分が、Haskellの無名関数であるx + 1であり、そして実質のZeroは、ご存知の通り0。先の関数と合わせると、無事10が返ってくる。ヤッタネ!

nat_to_int $ unfoldN 10 -- => 10

Haskellの場合はわかった、他の言語の場合はどうなる

元ネタは『アンダースタンディング・コンピュテーション』。本文はRubyで書かれており、ただそのままRubyだと面白くないので、ちょっとここはPythonで書いてみよう:

# Primitive
ZERO = lambda f: lambda x: x
ONE = lambda f: lambda x: f(x)
TWO = lambda f: lambda x: f(f(x))
THREE = lambda f: lambda x: f(f(f(x))) 

チャーチ数っぽい感じになった。当然、これも同じように:

THREE(lambda x: x + 1)(0) # => 3

というような利用ができる。ちなみに、こちらの写経については、ソースコードがあるので参考にして頂ければと思う。

ちなみに、こういう風に抽象化すると面白いことが発生して、ZEROの定義を少しだけ変更して:

THREE(lambda x: x[1::])(u"いろはにほへと")[0] # => "に"

といった、対応付け遊びもできて楽しい!!

まとめ

というわけで、最近興味を持って色々と調べたことを文章にしてみた。基本的には下の本のパクリなので、もしこれを読んで、たぶん仕事には直結しないけれど「なんか面白そうだ」と思った奇特な人がいれば、下の本をお勧めしておきます:

アンダースタンディング コンピュテーション―単純な機械から不可能なプログラムまで

アンダースタンディング コンピュテーション―単純な機械から不可能なプログラムまで

関数プログラミング入門 ―Haskellで学ぶ原理と技法―

関数プログラミング入門 ―Haskellで学ぶ原理と技法―

論理と計算のしくみ

論理と計算のしくみ

また、参考PDFとして、以下が挙げられます:

"平成26年度教員免許状更新講習テキスト「数の体系」牧野哲(山口大学工学部教授)"

蛇足

すいません、仕事します