<   2015年 02月 ( 8 )   > この月の画像一覧

個体は集合か

素朴集合論では集合はものの集まりというものである。この素朴集合論のモデルは、ものという対象と、あるものが集合というものに属するという、対象と対象のあいだの帰属関係という射からなるグラフである。

このグラフの対象には、1個のりんごのように集合とは考えられない個体とりんごの集合のような集合の2種類が含まれる。対象に個体と集合という二種類のものがあっては居心地が悪いので、個体も集合の一つと考えることはできないかと考えた。個体も集合であるがそれは要素を含んでいないと考えるのだ。

しかし、一つも要素を含まない集合には空集合がある。外延性の原理を考えると、個体を要素を含まない集合であるとしたとき、これは空集合と同じものであるということになる。この議論でいけば、すべての個体は同じ空集合であるということになり、個体の個別性がなくなってしまう。個体は要素を含まないが空集合ではない。しかし、そうであれば、個体が集合である事はあり得ない。

素朴集合のグラフは自分自身を要素とする集合も表現できる。自分自身に要素として含まれるという帰属関係の射を引けはいいだけだからだ。そこで、個体とは自分自身のみを要素とする集合であると考えて見る。これは、空集合とは異なるし、外延性の原理を適用しても、個体間の差異を保つことができる。

しかし、このアイディアもうまくはいかない。自分自身だけを要素とする集合 a は a = {a} となるが、これは、a 一個だけを要素として含む集合と区別することができない。個体 a と a だけを要素とする集合 {a} は明らかに異なるものなので、個体を自分だけを要素とする集合と考える工夫には無理がある。

結局のところ、素朴集合というグラフの対象は、個体と集合という2種類のものを含んでいる。対象に2種類あるのは気に入らないが、しかし、これに帰属関係の射を加えたグラフは素朴集合の世界の過不足ないモデルになっている。

このグラフの対象には、自分自身への帰属関係の射を張るもの(すなわち、自分自身を自分自身の要素として含むもの)と、自分自身への射を持たないもの(自分自身を要素として含まないもの)に分けることができるはずだ。ところが、自分自身への射を持たない対象すべてからの射を受ける対象は、それ自身は、自分自身に射を受けない対象であるが、それ自身(自分自身を要素として含まない集合の集合)に帰属できないというラッセルのパラドックスが発生することがわかる。

これは、集合とはものの集まりというものであるという素朴集合の定義が、再帰的定義であるために、この定義を適用するたびにつねに新しい対象を作り出してしまうという性質があるからである。つまり、自分自身を要素としない集合すべてを集めて集合を作ったと思うと、そこに、全く新しい自分自身を要素としない集合が出現してしまうのだ。

この辺りの事情は、同じ再帰的定義を用いる自然数に最大値が存在しないことと似ている。自然数の無限大は数として求めることができないため、無限大が偶数か奇数かという問題は無意味になる。

おなじように、集合の定義の再帰性のためにすべての集合の集合もつくることができない。すべての集合を集めて集合を作ったと同時にそれらとは異なる(当面の全ての集合をあつめた)集合が出現してしまうからだ。これば、その集合に自分自身への帰属関係を付け加えても解決しない。その集合を一つだけ含む集合はやはり、それまでの集合とは異なる集合であるから、すべての集合を集めたはずの集合はすべてを集めていなかったということになるからだ。

素朴集合論の集合の集まりは、全体をひとくくりにできるようなものではなく、本質的に発展し続ける運動のようなものだ。これを、無理に全体としてひとくくりに考えることができると考えたためにパラドックスが発生してしまったのだ。ラッセルのパラドックスは排中律に関するパラドックスだ。排中律は集合としてまとめることのできるものの集まりには適用できる。しかし、素朴集合の全体のようにつねに膨れ続けるものの集まりには適用できないのだ。

無限大が偶数とも奇数とも言えないとしても、整数に矛盾があるとは言わないだろう。自分自身を要素としない集合の集合が作れないとしても、ものの集まりをものと考える素朴集合のモデルである単純なグラフにに矛盾があるとは言えないのではないだろうか。
[PR]
by tnomura9 | 2015-02-27 01:27 | 考えるということ | Comments(0)

System.Random (12) RandomGen クラス

System.Random 読解シリーズ

Random number generators (乱数ジェネレータ)

1. RandomGen クラス

型クラスの RandomGen は乱数ジェネレータ(乱数を発生させるための情報を保持したデータ型)を取り扱うための(共通の)インターフェースを提供する。RandomGen のインスタンスとしてデータ型をインスタンス宣言すると、そのデータ型については、RandomGen 型クラスの提供する関数を使うことができるようになる。

型クラスというのは関数の多重定義(オーバーロード)を行うために工夫された仕組みだ。様々なデータ型は型クラスのインスタンスとして宣言することで、型の異なるデータ型について、型クラスの同名の関数を使うことができる。

例えば Int 型と Int 型の加算と Float 型と Float 型の加算は別の関数だが、Int 型も Float 型も Num 型クラスのインスタンスとして登録することで、 Int 型の加算も、Float 型の加算も同じ + 演算子でプログラムすることができる。

型クラスの宣言では共有する関数の抽象的な型を定義しているだけなので、実装は実際のデータ型を instance 宣言するときにコーディングする必要がある。

RandomGen 型クラスの関数としては、next :: g -> (Int, g)、split :: g -> (g, g)、genRange :: g -> (g, g) の3つがある。このうち instance 宣言では最小限 next と split は実体のコーディングが必要である。

System.Random モジュールでは RandomGen クラスのインスタンスは StdGen 型だけなので、RandomGen クラスを設定するのは冗長な気がするが、ユーザーが別の型の乱数ジェネレータを定義して使いたいときは、RandomGen クラスのインスタンスとしてそれを宣言することによって、RandomGen の関数を使うことができるから、拡張性を考えた仕組みなのだろう。

2. next 関数

next :: g -> (Int, g) 関数は、引数に1個の乱数ジェネレータをとり、整数と新しい乱数ジェネレータを戻す。

2. split 関数

split 関数は1個の乱数ジェネレータをひきすうにとり、2個の異なる乱数ジェネレータのペアを返す。この関数は関数プログラミングではたいへん便利な関数だ。たとえば、乱数ジェネレータを再帰呼び出しに渡すときに利用価値が高い。しかし、split に対しては統計学的な頑強性について研究されたものが殆ど無い。System.Random における実装は数少ないそのような例のひとつだ。

3. genRange 関数

genRange :: g -> (Int, Int) 関数は乱数ジェネレータで発生する乱数の範囲を返す。genRange g が上限と下限のペア (a, b) を帰す場合 a < b である必要がある。また、genRange 関数はいつも整数のペア (Int, Int) を返さなければならない。genRange の値の範囲は引数として与えられる乱数ジェネレータに依存している。next で返された新しい乱数ジェネレータの範囲の値がもとの乱数ジェネレータの範囲と異なっていても genRange でチェックすることはできない。

デフォールトの genRange の範囲は Int 型の下限と上限の値である。

4. RandomGen のインスタンス

RandomGen のインスタンスは、System.Random モジュールで定義されているのは StdGen ひとつだけである。

5. RandomGen のソースコード

RandomGen のコメントを除いたソースコードは次のようになる。

class RandomGen g where

    next :: g -> (Int, g)

    split :: g -> (g, g)

    genRange :: g -> (Int,Int)

    -- default method
    genRange _ = (minBound, maxBound)

6. StdGen 型

StdGen 型は System.Random では data StdGen = StdGen Int32 Int32 と定義されている。System.Random で定義されている唯一の乱数ジェネレータであるが、コンストラクタが StdGen で、32ビット符号付き二進数のフイールドを2つ持っている。

ソースコードでの記述は次のようになっている。

data StdGen
  = StdGen Int32 Int32

instance RandomGen StdGen where
  next = stdNext
  split = stdSplit
  genRange _ = stdRange

stdNex、stdSplit、stdRange などの関数は System.Random のソースコードの後ろの方にまとめて記述されている。

stdRange は次のように (0, 2147483562) を返すだけの関数だ。

stdRange :: (Int,Int)
stdRange = (0, 2147483562)

stdNext は StdGen 型の値をとり、整数型の乱数と新しい乱数ジェネレータのペアを返す。乱数発生のアルゴリズムをしらないので詳しいことは分からないが、値の計算法は簡単な整数の演算だ。

stdNext :: StdGen -> (Int, StdGen)
-- Returns values in the range stdRange
stdNext (StdGen s1 s2) = (fromIntegral z', StdGen s1'' s2'')
        where        z'   = if z < 1 then z + 2147483562 else z
                z    = s1'' - s2''

                k    = s1 `quot` 53668
                s1'  = 40014 * (s1 - k * 53668) - k * 12211
                s1'' = if s1' < 0 then s1' + 2147483563 else s1'
    
                k'   = s2 `quot` 52774
                s2'  = 40692 * (s2 - k' * 52774) - k' * 3791
                s2'' = if s2' < 0 then s2' + 2147483399 else s2'

stdSplit 関数は引数の乱数ジェネレータから新しい乱数ジェネレータのペアを生成する。

stdSplit            :: StdGen -> (StdGen, StdGen)
stdSplit std@(StdGen s1 s2)
                     = (left, right)
                       where
                        -- no statistical foundation for this!
                        left    = StdGen new_s1 t2
                        right   = StdGen t1 new_s2

                        new_s1 | s1 == 2147483562 = 1
                               | otherwise        = s1 + 1

                        new_s2 | s2 == 1          = 2147483398
                               | otherwise        = s2 - 1

                        StdGen t1 t2 = snd (next std)

これを見ると乱数ジェネレータといっても、乱数を作成するための単なる整数のペアであることが分かる。
[PR]
by tnomura9 | 2015-02-22 12:14 | Haskell | Comments(0)

TED.com

すごく良い英語の教材を見つけた。TED (Technology Enterment Design) というグループがインターネットで配布している講演 TED Conference のビデオだ。画面下の吹き出しマークをクリックすると、字幕を日本語にしたり、英語にしたり、消したりできる。今の所字幕なしでは内容が理解できないので、ひたすらシャドウイング(聞いた言葉を声を出さずに真似すること)をしているが、2700時間をかけると理解できるようになるそうだ。

TED.com : TED の公式ホームページ
[PR]
by tnomura9 | 2015-02-19 23:59 | 考えるということ | Comments(0)

System.Random(11) インポートリスト

System.Random 解読シリーズ

モジュールのエクスポートリストの後は、外部モジュールのインポートリストが続く。System.Random のソースファイルの場合は次のようになっている。インポートされたモジュールは System.Random の内部処理で使われるので、Haddock には表示されない。

import Prelude

import Data.Int

#ifdef __NHC__
import CPUTime( getCPUTime )
import Foreign.Ptr ( Ptr, nullPtr )
import Foreign.C( CTime, CUInt )
#else
import System.CPUTime( getCPUTime )
import System.Time( getClockTime, ClockTime(..) )
#endif
import Data.Char( isSpace, chr, ord )
import System.IO.Unsafe ( unsafePerformIO )
import Data.IORef
import Numeric( readDec )

#ifdef や #else はコンパイラのプリプロセッサへの指示を行うプラグマである。意味は gcc の場合と同じようだ。__NHC__ フラグ立っている場合はコンパイラが nhc98 の場合だ。nhc98 コンパイラは Unix プラットフォームのコンパイラで、メモリ使用量の少ない小さいオブジェクトコードを生成する。

Prelude モジュールは Haskell の標準的なモジュールで全てのモジュールにデフォールトでインポートされる。上の例のように明示的にインポートしてもいいし、明示的なインポートがなくても暗黙のうちにインポートされる。

Data.Int モジュールは整数型を定めている。Data.Int 型で data 宣言されている整数型は Int, Int8, Int32, Int64 でいずれも符号付きの2進数の整数だ。これらのデータ型は、Bounded, Enum, Eq, Integral, ... などの数多くの型クラスのインスタンスになっている。

System.CPUTime モジュールでは getCPUTime 関数のみをインポートしている。getCPUTime 関数は picosecond 単位で CPU タイムを取得する。

System.Time モジュールからは getClockTime 関数と ClockTime 型をインポートする。ClockTime(..) の (..) は ClockTime 型のフィールドもインポートすることを示している。getClockTime 関数は現在のシステムの時刻を取得し IO ClockTime 型で返す。ClockTime 型のコンストラクタは Tod で Tod Integer Integer のように Integer 型のフィールドを2つ持っている。

Data.Char モジュールからは isSpace 関数と chr 関数、ord 関数をインポートする。isSpace はキャラクターが空白文字であるかを判断し、chr 関数は整数をASCIIコードに変換し、ord 関数はASCIIコードを整数に変換する。

System.IO.Unsafe モジュールからは unsafePerformIO 関数をインポートする。unsafePerformIO 関数の型は unsafePerformIO :: IO a -> a で IO モナドにバックドアをつける働きがあるらしいが詳しくは調べなかった。

Data.IORef モジュールはIOモナドの中に代入可能な変数を導入するモジュールだ。

Numeric モジュールからは readDec 関数がインポートされる。readDec 関数は文字列を10進数として読み取って整数型の値を得る。

乱数発生というような単純明快な動作のモジュールも unsafePerformIO などがインポートされていると怪しさを感じてしまう。
[PR]
by tnomura9 | 2015-02-16 18:13 | Haskell | Comments(0)

System.Random (10) System.Random モジュール

System.Random 読解シリーズ

System.Random モジュールのソースコードの先頭部分から順番に読解していくことにする。短いモジュールで、アルゴリズム的にも擬似乱数の発生法以外にはそう難しいものはないような感じなので、GHCの標準モジュールを解読する際のモデルになるのではないだろうか。

System.Random モジュールのエクスポートは次のようになる。

module System.Random
        (

        -- $intro

        -- * Random number generators

         RandomGen(next, split, genRange)

        -- ** Standard random number generators
        , StdGen
        , mkStdGen

        -- ** The global random number generator

        -- $globalrng

        , getStdRandom
        , getStdGen
        , setStdGen
        , newStdGen

        -- * Random values of various types
        , Random ( random, randomR,
                 randoms, randomRs,
                 randomIO, randomRIO )

        -- * References
        -- $references

        ) where

System.Random のエクスポートの中にはたくさんのコメントが並んでいるが、これらは Haddock の System.Random のページの見出しに対応している。 -- * や --** は見出しの階層のレベルに対応している。 -- $intro や -- $globalrng の部分はソースの他の部分で定義された文字列置換される。たとえば $globalrng は次の文章に置換される。

{- $globalrng #globalrng#

There is a single, implicit, global random number generator of type
'StdGen', held in some global variable maintained by the 'IO' monad. It is
initialised automatically in some system-dependent fashion, for example, by
using the time of day, or Linux's kernel random number generator. To get
deterministic behaviour, use 'setStdGen'.
-}

$intro に対応する定義はないが、冒頭の部分に置換されるようだ。

また、クラスや関数などの entity の Hadock での表記は、ソースコードから抽出して表示されるようだ。そのさいに、entity の上部に書かれているコメントは、Haddock の注釈として表示される。

たとえは class RadomGen g の場合は、そのクラスについての概要に続いて、Method という見出しのもとにそのクラスのメソッドである next, split, genRange がその注釈とともにまとめられている。また、このクラスの Instance の見出しの後には、このソースコードで定義されている RandomGen クラスの唯一のインスタンスである StdGen 型の定義へのリンクが表示されている。

ソースコードの各 entity の概要は、このように Haddock に忠実に反映されるので、Haddock を参照しながら各 entity のアルゴリズムの本体を読解していけばいい。
[PR]
by tnomura9 | 2015-02-14 13:30 | Haskell | Comments(0)

System.Random (9) Haddock

System.Random 解読シリーズ

前回までの記事で、System.Random モジュールの大半を占めるコメントがそのまま Haddock に反映されていることが分かった。したがって、GHCの標準モジュールのソースを解読するには、Haddock を入り口にすれば良いことが分かる。ソースのコード部分も Haddock のリンクをクリックすれば自由に読むことができる。

System.Random の Haddock の一番上にはタイトルとリンクが載ったツールバーがある。このツールバーの右端のリンクの中で Source というリンクをクリックすると System.Random のソースコードにアクセスできるが、それは、一本のソースコードにまとまっている。そう長いプログラムではない。

System.Random.hs ファイルには、大量のコメントと比較的コンパクトなコードとが書き込まれているが、コメントは Haddock に反映されているので、コメントを直接読むよりは Haddock の文書を読んだ方が読みやすい。コード部分を読みたいときは Haddock の各所に見られる Souce というリンクをクリックすればよい。

System.Radom モジュールの Haddock の冒頭部分には、このモジュールの概要が書かれている。その内容は大体次のようなものだ。

このモジュールは擬似乱数を発生させるためのものだ。このモジュールを利用すると、再現可能な乱数列を作成できる。(再現可能とは、同じ一連の乱数の数列を何度でも再現できるということだ。これは、乱数を使ってプログラムをテストするとき、同じ入力が使えるのでプログラムの動作の変化の検証がしやすいということだ)。再現可能な乱数列を作るには、最初の乱数発生のためのジェネレータを同じにすればいいし、異なる乱数列はこの乱数ジェネレータを変更すればいい。

このモジュールは2つの層に分けられている。ひとつは、コアの random number generator の部分で、乱数発生のジェネレータとなるビット列を作る。ジェネレータの操作については RandomGen クラスによって操作の抽象化が図られている。System.Random では RandomGen のインスタンスとなるデータ型は一つだけ StdGen が定義されている。インスタンスが StdGen 一つだけなのに RandomGen という型クラスが用意されたのは、乱数ジェネレータをユーザが用意する場合を想定しているからだ。

RandomGen 以外にも、もう一つの型クラス Random がある。これもいろいろな型の乱数を統一的に扱うための工夫だ。たとえば、Float 型は Random クラスのインスタンスなので、Random クラスの関数を使って Float 型の乱数を自由に作り出すことができる。同じように Int 型の乱数も Float 型の乱数と同じ関数で作り出せる。

乱数発生のアルゴリズムは、L'Ecuyer の 32-bit コンピュータ用に書かれた Portable Combined Generator が使われている。これは、Lennart Augustsson によって GHC 用に書き直されている。このアルゴリズムによる乱数発生の周期性はおおよそ 2.30584e18 である。
[PR]
by tnomura9 | 2015-02-08 23:08 | Haskell | Comments(0)

System.Random (8) Haddock

System.Random 解読シリーズ

Stystem.Random 解読関連で Haddock について調べた記事は、今回で最後だ。Haddock の仕様について調べていく過程でわかったのは、モジュールのソースコードのコメントのほぼ全てが Haddock 文書に反映されるということだ。したがって、GHC の標準モジュールの解読は、GHC の Haddock 文書からたどっていけばいいことが分かる。

Haddock User Guid の Chapter 3. Documentation and Markup (文書の仕様とマークアップ)

3.8 Markup

Haddock にはコメントの文書をレイアウトするための簡単なマークアップが使われている。

3.8.1 Paragraphs

コメントのパラグラフとパラグラフの間は空行で区切ることで分けられる。空行は1行以上なら複数でもよい。

3.8.2. Special characters

アスキー文字のうち \,/,',",@,< はマークアップの記号として使われるので、この記号を表示したいときはエスケープが必要だ。これらの記号をエスケープ表示にするためには先頭に \ 記号をつける。

また、>>> は特別な意味があるので、先頭に \ をつけてエスケープする必要がある。

3.8.3. Character references

ソースファイルのコメントは ASCII 文字に制限されている。非アスキー文字はエスケープ表示にする必要がある。

3.8.4. Code Blocks

プログラム例などのコードブロックは上下を @ 記号で挟むことでコード表示にレンダリングできる。次の例のような表記になる。

-- | This documentation includes two blocks of code:
--
-- @
-- f x = x + x
-- @
--
-- > g x = x * 42

bird(鳥の嘴)表記の場合はそのままコードブロック表記されるが先頭の > の部分は表示されない。

3.8.5. Examples

コードを ghci で実行した時の実例をレンダリングできるが、次の例のように先頭に >>> をつける。

-- | Two examples are given below:
--
-- >>> fib 10
-- 55
--
-- >>> putStrLn "foo\nbar"
-- foo
-- bar

3.8.6. Properties

次の例のように property を設定することができる。(property というのがわからなかったが、QuickCheck でソフトウェアーの検証をするときに利用されるのだろうか?)

-- | Addition is commutative:
--
-- prop> a + b = b + a

3.8.7. Hyperlinked Identifiers

次の例のように、コメントの中に現れた Haskell の identifier はシングルクオート ' で囲むとハイパーリンクにすることができる。

-- | This module defines the type 'T'.

上の方法では、そのモジュール内での定義にハイパーリンクをつくるが、次のように qualified name で表記すると他のモジュールの文書にハイパーリンクを作ることができる。

-- | The identifier 'M.T' is not in scope

シングルクオートは次の例のように文章中で使うときはエスケープする必要はない。

-- | I don't have to escape my apostrophes; great, isn't it?

3.8.9. Linking to modules

コメントの中から他のモジュールにリンクを張る場合は、ダブルクオートで囲む。

-- | This is a reference to the "Foo" module.

3.8.10. Itemized and Enumerated lists

項目を箇条書きにするときは * や - , (1), 2. などの表記をするが、詳しくは上のリンクから本文をたどって確認して欲しい。

3.8.11. Definition lists

用語の定義のリストも下の例のようにして作ることができる。

-- | This is a definition list:
--
-- [@foo@] The description of @foo@.
--
-- [@bar@] The description of @bar@.

3.8.12. URLs

URL は次の例のようにブラケットで囲むとハイパーリンクにできる。

<http://example.com label>

3.8.13. Images

画像へのリンクは次のように2重のブラケットで囲む。

<<pathtoimage.png title>>

3.8.14. Anchors

文書中にアンカーをうめこんで #label# のようにリンクを張ることができるが、詳しくは本文を参照して欲しい。

3.8.15. Headings

= 記号でヘッダーを指定することができる。ヘッダーの階層は == のように = 記号の数でコントロールする。

-- |
-- = Heading level 1 with some __bold__
-- Something underneath the heading.
--
-- == /Subheading/
-- More content.
--
-- === Subsubheading
-- >>> examples are only allowed at the start of paragraphs
[PR]
by tnomura9 | 2015-02-03 12:00 | Haskell | Comments(0)

System.Random (7) Haddock

System.Random 解読シリーズ

Haddock User Guid の Chapter 3. Documentation and Markup (文書の仕様とマークアップ)

3.6. Hyperlinking and re-exported entities

この節は直訳ではなく、概要について説明する。Haddock 文書中に現れたデータ型 type や型クラス class については、その定義へのハイパーリンクが作成される。しかし、このパイパーリンクをどのモジュールの Haddock 文書に張るのかについては注意が必要だ。

それは、当該のモジュールが、他のモジュールをインポートしていたり、そのモジュールが更に他のモジュールをインポートしていた場合に、どのモジュールで定義された文書にリンクを貼ればよいのかというのが問題になるからだ。

この判断は Haddock の文書作成プログラムの中で大本のモジュール home が自動的に判断されるのでこの概要では詳しくは延べないが、次のようなルールがあるようだ。

  • 当該のモジュールが A と B の二つのモジュールから同じ entity をインポートしており、さらにモジュール A がモジュール B をインポートしている場合、その entity のハイパーインクはモジュール B の定義に張られる
  • 隠蔽属性が設定されているモジュールは引用されない。
  • home モジュールの entity がエクスポートされていない場合、non-home モジュールの定義が引用される。

3.7. Module Attributes

各モジュールについては、モジュールの属性を定義することができる。このモジュールの属性は、Haddock 文書を作成するときに参照され、それによって、モジュールの文書からの隠蔽などが行われる。

各属性はモジュールのソースの先頭に置かれた {-# OPTIONS_HADDOCK ... #-} プラグマの中に記述される。属性が複数ある場合コンマ区切りのリストとして記述される。プラグマの位置はモジュールの宣言文 module discription の前でも後でも良い。モジュール属性のプラグマの例を次に示す。

{-# OPTIONS_HADDOCK hide, prune, ignore-exports #-}

-- |Module description
module A where
...

属性の出現順序は順不同である。現在のところ Haddock では次のような属性が設定可能である。

hide
この属性を持ったモジュールは無視されて Haddock 文書には引用されない。たとえこのモジュールが他のモジュールに引用されて、その内容がさらにその他のモジュールにエクスポートされる場合でも無視される。
prune
注釈のない定義は無視される。
ignore-exports
エクスポートリストに関係なく全ての entity についての文書が作成される。
not-home
このモジュールの entity の定義には、他のモジュールの文書からのハイパーリンクを作れない。
show-extensions
このモジュールで定義された拡張についての文書が作成されない。(意味がよくわからなかった。)

[PR]
by tnomura9 | 2015-02-01 12:06 | Haskell | Comments(0)