2011-09-09

Haskellの評価戦略とfoldl/foldr (1)

関数型言語などで再帰を使ってプログラムを書く場合、

末尾再帰はループに最適化されるのでメモリ消費量が少なくなる

と、一般には言われます。
が、これは評価戦略によっては成り立たなくなります。

foldlとfoldr

リストの内容をある演算子によって畳み込む処理は、一般に fold というプログラミングパターンとして知られています。
例えば、

    [a0,a1,a2,a3,a4,a5,a6]

というリストを、初項をzとして、<+>という演算子で畳み込みたいとします。
この場合、演算を右結合で行うか左結合で行うかで二通りの解釈が存在します。
左結合の場合、

    (((((((z<+>a0)<+>a1)<+>a2)<+>a3)<+>a4)<+>a5)<+>a6)   ... (*1)

となりますし、右結合の場合は

    (a0<+>(a1<+>(a2<+>(a3<+>(a4<+>(a5<+>(a6<+>z)))))))   ... (*2)

となります。
これを一般のリストについて再帰関数で記述すると、左結合の場合は

  foldl :: (b -> a -> b) -> [a] -> b
  foldl (<+>) r []     = r
  foldl (<+>) r (x:xs) = foldl (<+>) (r<+>x) xs

右結合の場合は

  foldr :: (a -> b -> b) -> [a] -> b
  foldr (<+>) z []     = z
  foldr (<+>) z (x:xs) = x <+> (foldr (<+>) z xs)

となります。
この、foldl, foldr を使って先の例を記述すると、(*1)は

  result = foldl (<+>) z [a0,a1,a2,a3,a4,a5,a6]

(*2)は

  result = foldr (<+>) z [a0,a1,a2,a3,a4,a5,a6]

と書けることがわかると思います。

foldlは末尾再帰

上のfoldlの定義を見ても分かるとおり、foldlは式の一番外側が自分自身の呼び出しになっているので、末尾再帰になります。
一方、foldrは自分自身を呼び出した後で演算をするので、末尾再帰にはなっていません。
ではここで、「遅延評価でない」通常の言語でfoldl(末尾再帰)を評価することを考えます。
定義通りに式を評価していくと……

  result =
    foldl (<+>)  z        (a0:[a1,a2,a3,a4,a5,a6]) = 
    foldl (<+>) (z <+>a0) (a1:[a2,a3,a4,a5,a6]) =
    foldl (<+>)  b0       (a1:[a2,a3,a4,a5,a6]) =
    foldl (<+>) (b0<+>a1) (a2:[a3,a4,a5,a6]) =
    foldl (<+>)  b1       (a2:[a3,a4,a5,a6]) =
    foldl (<+>) (b1<+>a2) (a3:[a4,a5,a6]) =
    foldl (<+>)  b2       (a3:[a4,a5,a6]) =
    foldl (<+>) (b2<+>a3) (a4:[a5,a6]) =
    foldl (<+>)  b3       (a4:[a5,a6]) =
    foldl (<+>) (b3<+>a4) (a5:[a6]) =
    foldl (<+>)  b4       (a5:[a6]) =
    foldl (<+>) (b4<+>a5) (a6:[]) =
    foldl (<+>)  b5       (a6:[]) =
    foldl (<+>) (b5<+>a6)  [] =
    foldl (<+>)  b6        [] = b6

というように、リストの頭から要素を取り出しつつ次々と左側に畳み込んでいきます。
このとき、

再帰の一段前のコンテキストは捨ててよい
foldlの第2引数には常に演算の「結果」が入っている

という性質があります。
一方、foldrを評価すると、

 result =
   foldr (<+>) z (a0:[a1,a2,a3,a4,a5,a6]) =
   a0<+>(foldr (<+>) z (a1:[a2,a3,a4,a5,a6])) =
   a0<+>(a1<+>(foldr (<+>) z (a2:[a3,a4,a5,a6]))) =
   a0<+>(a1<+>(a2<+>(foldr (<+>) z (a3:[a4,a5,a6])))) =
   a0<+>(a1<+>(a2<+>(a3<+>(foldr (<+>) z (a4:[a5,a6]))))) =
   a0<+>(a1<+>(a2<+>(a3<+>(a4<+>(foldr (<+>) z (a5:[a6])))))) =
   a0<+>(a1<+>(a2<+>(a3<+>(a4<+>(a5<+>(foldr (<+>) z (a6:[]))))))) =
   a0<+>(a1<+>(a2<+>(a3<+>(a4<+>(a5<+>(a6<+>(foldr (<+>) z []))))))) =
   a0<+>(a1<+>(a2<+>(a3<+>(a4<+>(a5<+>(a6<+>z)))))) =
   a0<+>(a1<+>(a2<+>(a3<+>(a4<+>(a5<+>c6))))) =
   a0<+>(a1<+>(a2<+>(a3<+>(a4<+>c5)))) =
   a0<+>(a1<+>(a2<+>(a3<+>c4))) =
   a0<+>(a1<+>(a2<+>c3)) =
   a0<+>(a1<+>c2) =
   a0<+>c1 = c0

というように、再帰を一段辿る度に式が組み上げられていき、リストを最後まで辿ったところで今度は順番に演算を消化していっていることがわかります。
この、「式を組み上げていく」ということがいわゆる「スタックを消費している」ことに相当します。

内部簡約と最外最左簡約

さて、前節でfoldlを評価する際に、

    foldl (<+>) (z <+>a0) (a1:[a2,a3,a4,a5,a6]) =   ... (*3)
    foldl (<+>)  b0       (a1:[a2,a3,a4,a5,a6])

という計算(式変形)を行いました。しかし、上の式に対して適用できる式変形はこの一通りではありません。
foldlの定義から

    foldl (<+>) (z <+>a0) (a1:[a2,a3,a4,a5,a6]) =
    foldl (<+>) ((z <+>a0)<+>a1) (a2:[a3,a4,a5,a6])

という展開も行えることがわかります。つまり、(*3)のような式を見たときに、内側の部分

    foldl (<+>) (z <+>a0) (a1:[a2,a3,a4,a5,a6])
 {-             ~~~~~~~~~                       -}

を先に簡約(計算)するという選択肢と、一番外側の部分

    foldl (<+>) (z <+>a0) (a1:[a2,a3,a4,a5,a6])
 {- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -}

を先に簡約(展開)するという選択肢の2通りの計算順序が存在することになります。
一般に、簡約できる箇所が複数存在するとき、前者のように内側を先に簡約する評価戦略を内部簡約、後者のように一番外側(の一番左)を先に簡約する評価戦略を最外最左簡約と呼んでいます。
OCamlや一般の手続き型言語では基本的に内部簡約、Haskellでは基本的に最外最左簡約で計算が行われます。
実は、この最外最左簡約というのが遅延評価の性質を持っているのです。

2011-07-13

ログに色をつけるスクリプト試し書き

プログラミング

syslog に色をつけてみるテスト。

tail -f /var/log/syslog | ruby log_color.rb

とかやると適当に色つきで表示される。

#!/usr/bin/ruby1.8 -Ku

ESC_DEFAULT = "\x1b[39m"
ESC_RED     = "\x1b[31m"
ESC_YELLOW  = "\x1b[33m"
ESC_BLUE    = "\x1b[34m"
ESC_CYAN    = "\x1b[36m"

ARGF.each do |line|
   line.chomp!

   date, hostname, msg =
       line.scan(/^([A-Z][a-z][a-z] \d+\ \d+:\d+:\d+) (\S+) (.*)$/)[0]

   esc_code = nil
   case msg
   when /-- MARK --/
      # no output
      next
   when /\/usr\/sbin\/cron/i
      esc_code = ESC_YELLOW
   when /^kernel/
      esc_code = ESC_CYAN
   end

   printf "%s %s %s%s%s\n", date, hostname, esc_code, msg, ESC_DEFAULT
end

2011-07-05

無限の大きさ

数学

無限大にもいろいろな大きさの違いがある！？！
という記事を見て、自然数全体の集合と、偶数全体の集合の大きさについて考えてみた。
上記記事には、

無限大と無限大の個数を比べるのは無意味のようでもあるが、しかし、私たちは、直感的に自然数の個数の方が、偶数の個数の2倍あることが分かる。
http://ameblo.jp/kohno-masao/entry-10943462422.html

とある。「直感的に」「2倍あることが分かる。」といきなり書かれているのだが、本当にそうなんだろうか。

いきなり要素数が無限個の集合を考えると難しいので、有限個の集合で考えてみる。
まず、「1から10までの自然数を全て含む集合」 $\small N_{10}$ を考えてみよう。

$N_{10} = \{\,\,1,\,\,2,\,\,3,\,\,4,\,\,5,\,\,6,\,\,7,\,\,8,\,\,9,\,\,10\}$

ここで、「 $\small N_{10}$ の全ての要素に2をかけた新しい集合を作る」という演算 $\small\phi(N_{10})$ を考えてみる。この結果はすぐに

$\phi(N_{10}) = \{\,\,2,\,\,4,\,\,6,\,\,8,\,\,10,\,\,12,\,\,14,\,\,16,\,\,18,\,\,20\}$

となることがわかるだろう。そして、この集合 $\small\phi(N_{10})$ は「2から20までの偶数を全て含む集合」になっていることがわかる。また、 $\small N_{10}$ の各要素に2をかけたものを $\small \phi(N_{10})$ としたのだから、要素数は元の $\small N_{10}$ と同じ10個である。

同様に、「1から20までの自然数を全て含む集合」 $\small N_{20}$ を考えて

$N_{20} = \{\,\,1,\,\,2,\,\,3,\,\,\dots,\,\,18,\,\,19,\,\,20\}$

これに演算 $\phi$ を適用すると、「2から40までの偶数を全て含む集合」

$\phi(N_{20}) = \{\,\,2,\,\,4,\,\,6,\,\,\dots,\,\,36,\,\,38,\,\,40\}$

ができる。両者の要素数はやはり同じで、20個である。

では、この $\phi$ を適用する集合をどんどん大きくしていって、「自然数全体の集合」 $\mathbb{N}$ としたらどうなるだろう？この場合、

$\mathbb{N} = \{\,\,1,\,\,2,\,\,3,\,\,4,\,\,5,\,\,\dots \}$

なので、 $\phi$ を適用した結果は、「偶数全体の集合」

$\phi(\mathbb{N}) = \{\,\,2,\,\,4,\,\,6,\,\,8,\,\,10,\,\,\dots \}$

になるはずだ。そして、 $\phi(\mathbb{N})$ の各要素は、 $\mathbb{N}$ の各要素に2をかけて作られたものだから、全体の要素数は同じである。

……あれ？

だがちょっと待って欲しい。

任意の偶数は必ず自然数でもあるから、偶数全体の集合 $\phi(\mathbb{N})$ のどの要素も、自然数全体の集合 $\mathbb{N}$ に含まれる。また、3を含む全ての奇数は自然数だが偶数ではないので、 $\phi(\mathbb{N})$ は $\mathbb{N}$ の真部分集合になるはずである。

$\phi(\mathbb{N})\subset\mathbb{N}$ なのに $\phi(\mathbb{N})$ と $\mathbb{N}$ の要素数が同じ？

まったく、わけがわからないよ。

なんでこんなことになった？

自然数全体の集合ってそもそもどんなものなの？ってのを考えてみる。
なんとなくイメージできるのは、左端が固定されていて、右方向に果てしなく伸びていて、等間隔に珠が連なっている数珠のようなものだ。

  ◆--( 1)--( 2)--( 3)--( 4)-- ……

この数珠の右側は果てがなく、どこまでも続いている。さて、これを2本並べてみる。

  ◆--( 1)--( 2)--( 3)--( 4)-- ……
  ◆--( 1)--( 2)--( 3)--( 4)-- ……

ここで、下側の数珠を引き伸ばして、珠同士の間隔を倍にしてみる。

  ◆--( 1)--( 2)--( 3)--( 4)--( 5)--( 6)--( 7)--( 8)-- ……
  ◆--------( 1)--------( 2)--------( 3)--------( 4)-------- ……

珠の数には全く手を加えていないことに注意。で、番号を振り直してみる。

  ◆--( 1)--( 2)--( 3)--( 4)--( 5)--( 6)--( 7)--( 8)-- ……
  ◆--------( 2)--------( 4)--------( 6)--------( 8)-------- ……

すると、上の数珠の偶数に対応する位置には必ず下の数珠の珠が見つかって、なおかつ珠全体の数は同じであることがわかる。上の数珠を「自然数全体の集合」、下の数珠を「偶数全体の集合」と捉えれば、「一方が他方の真部分集合で、かつ全体の要素数が同じ」という状態が再現できたことになる。

元の記事では「偶数君」が

偶数君：「うっっ、確かに、僕が持っている数字は、自然数君は全部持っている。そして、君は、僕が持っていない数字も無限に持っている。でも、俺の数字の個数も無限なんだ。なんで僕が君に負けているような気がするんだろう・・・・・？」
http://ameblo.jp/kohno-masao/entry-10943462422.html

と悩んでいるが、何のことはない、実は「自分が持っていた"2"という数字は元は自然数君の持っている"1"という数字で、"6"という数字は自然数君が持っていた"3"という数字で、……」という具合に、単に番号を振り直しただけで同じものだったのである。

なーんだ、結局二人とも「同じものを違う見方で見ていた」だけだったのね、ということだ。

……。

胡散臭いって？
胡散臭いよねぇ。

そう思ったアナタは数学に向いています。

2010-07-09

「白票」は果たして誰(or 何)に対する抗議なのか

選挙の投票について興味深い意見があったので。
白票の意味 - 真もわ爛漫
当選者に対する不支持の積極的な表明として、白票を投じよう。という趣旨と理解。

仮に投票結果中9割が白票であれば、投票結果がどうであれ、また、法律がそのときにどうであれ、候補者に対する国民感情は明らかに表明されており、仮にそこで当選者がマニフェストを表明したところで、その当選者の為政能力を当選当初に国民が支持していないことは国家内外から既に明らかになっている。
白票の意味 - 真もわ爛漫

ここで思うのは、果たしてそのような事態が起きうるのか、ということ。
まず、今現在の日本の政治の一側面として、(明文化されてないにせよ)世代間の対立という要素が存在する。ネットではインタゲだリフレだーという意見が一定の支持を集める一方、現在政治に対して比較的大きな影響力を持っている世代には、インフレや国債のデフォルトに強い恐怖感が存在する、という意見がある。

第二次世界大戦が終結して65年弱を経過はしていますが、戦後第一世代≒第一次ベビーブーマーは、先立つ世代から、インフレと国債デフォルトの話を色濃く受け継いでいることでしょう。リフレ政策支持者の希望に沿わず、与謝野議員に代表される財政再建を目指す主張に少なからぬ支持が集まるのは、今にしてなお思い知らされざるを得ない重い戦争の遺産なのかもしれません。
http://d.hatena.ne.jp/bewaad/20100430/p1#p1

また、このような歴史的経緯によらずとも、今現金として資産を大量に持っている高齢世代にとっては、インフレは自己資産の実質的な減少を意味するので、彼らが現在の自己の利益を優先するならば当然インフレには反対となる。

インフレとデフレについて、ある高齢者（81歳）に聞いたところ、「あんたらはインフレで得するかもしれんが、うちら（老人）が困る、デフレがいい」
と言っていたので、こういう層が結構いるのかな、と思ったりします。
finalventの日記コメント欄

次に、上で述べたような「財政再建,インフレ反対」世代は国政に対して比較的大きな影響力を持っているという要素。

上記サイトから引っ張ってきた年代別投票率(平成21年8月30日)、人口分布(推計。平成22年1月1日)から年代ごとの投票に占める割合を計算すると、

20〜29歳 : 9.31%
30〜39歳 : 15.49%
40〜49歳 : 15.96%
50〜59歳 : 17.84%
60〜69歳 : 21.51%
70歳以上 : 19.89%

となる。ざっぱに言っても、50歳未満が約4割に対し、50歳以上が約6割である。ていうか、20歳代の影響力は群を抜いて低い。

国政選挙への参加意欲が強く、「財政再建,インフレ反対」な高齢世代。日本の経済状態に無力感を感じつつ、選挙への参加意欲がそもそも低い若年世代。果たして、このような状況で「むかつく国政選挙へ白票を！」と叫んだとして、強い勢力になり得るだろうか。白票を以て政治に対するサボタージュを試みる若者を尻目に「お前さんらは信任せんかもしれんが、わしらにとっては大事なんでな」と、年寄りが余計に幅を利かせることになるのではないだろうか。

2010-05-05

英語のアルファベット読みが発生する条件

英語音声

英語の母音は通常、単音節で読む。

"a" → [æ] (ぇぁ)
"i" → [i] (い)
"u" → [ʌ] (綺麗な「あ」)
"e" → [e] (え)
"o" → [o] (お)

これが時々、アルファベット読みに変化することがある。
例えば、

mind → [máind] (まいんど)
fine → [fáin] (ふぁいん)

の `i' という文字は通常の「い」という発音でなく、[ai]「あい」という `I' のアルファベット読みになっている。
他にも

fate → [féit] (ふぇいとぅ)
gene → [ʤíːn] (じーん)
fold → [fóuld] (ふぉぅるどぅ)
tutor → [tjúːtər] (ちゅーたぁ)

の各2文字目の `a', `e', `o', `u' はいずれも `A'(えぃ), `E'(いー), `O'(おぅ), `U'(ゆー) のアルファベット読みになっている。
これも例外が色々あって読むのに勘がいるのだが、単語を覚えてくるとある程度ルールがあることがわかってくる。一番わかりやすいのは、「母音+子音+`e'」という組み合わせ。この時、`e'の2文字前の母音はアルファベット読みになる。
例:

mate [méit] (cf. mat)
bite [báit] (cf. bit)
theme [θíːm] (cf. them)
code [kóud] (cf. cod)
cute [kjúːt] (cf. cut)

2010-05-04

英語の読み方は変態的に不規則だと思う

音声文字英語

ソフトウェア開発でひっじょーによく出てくる "warning" (警告) という単語がある。これを日本人はかなりの率で「わーにんぐ」と読むのだが、実際の英語での発音は「うぉーにんぐ」に近い。
ところが、なぜ「うぉーにんぐ」と読むのが本来かと聞かれると、答えに窮する。例えば、"farm" (農場) は「ふぁrむ」と読む。"arm", "large" も同様に "ar" の発音は「あr」である。(rの巻き舌音は日本語にないのでrのまま書いてます)
しかし、例外的に、'w', 'a', 'r' と続いた場合にのみ、"ar" は「おー」という発音になる。一番単純な例は "war" (戦争)「うぉー」。地球温暖化 "global warming" は「ぐろぅばるうぉーみんぐ」。ちなみに「○○アワード(賞)」の原語 "award" の読みは「あうぉーど」である。
ふと、『あれ、でも "warp" (歪める) は「わーぷ」じゃないか？』と思って調べてみると、やはり原語での発音は "wɔːp" 「うぉーぷ」であった。

でもって、逆に "wor" は「わぁr」と読む。("worm"「わーむ」, "worth"「わース」, "world"「わーるど」)わかんねーって。

機構部品の一つに「ウォームギア」という歯車があって(参考松下製作所:ウォームギア・ウォームホイール)、長い円筒形のボディにネジが切ってあり、これが円筒の軸を中心に回転することで非常に大きな減速比を得ることが出来るのだが、これも原語では "worm gear"。芋虫("worm" 「わーむ」)のような形状をしているからであって、ギアが暖かい("warm" 「うぉーむ」)わけではありません。

2010-05-04

日本語の「ん」と「む」

音声文字日本語

現代日本語の音素 /n/ (ん) は、実際の音声が n になるもの、m になるもの、ng になるものがある。例えば、「しんじゅく」はヘボン式ローマ字表記すると "shi'n'juku" になるが、「しんばし」は "shi'm'bashi" になる。標識における駅名/地名の英語表示は実際にそうなっているので確認してみて欲しい。
ところが、古語では /n/ を表す「ん」の他に /m/ を表す「む」が別に存在した。日本におけるネカマのはしりとして有名な土佐日記の冒頭、「男もすなる日記といふものを、女もしてみむとてするなり」の「してみ"む"とて」は、現代仮名遣い表記すれば「してみ"ん"とて」になる。
第二言語として日本語を学ぶ人のために、音声を区別する用途として旧仮名遣いの一部を復活させてみてはどうだろう。「しんばし」は「しむばし」と書くとか。

我らが柿崎大先輩もこう言っておられます。(雁屋哲、由起賢二(1977)「野望の王国」日本文芸社)