Blogこの広告は、90日以上更新していないブログに表示しています。Combinatoricsがめちゃくちゃ面白い。場合の数という離散的なものを数えるのに、連続的世界から生まれた解析学の知見を用いる分野だ。階乗をガンマ関数で表示するだとかいうレベルではなく、マクローリン展開の係数を調べることで場合の数を知るようなことをしている。)というサーベイ論文。文字となる出力の場合の数が直ちにわかるという内容を紹介していた。文字の場合の数になっているという。場合の数を数えるのになんとマクローリン展開!一体どういうことなのか。[1]中では「正しく対応する括弧の文字列」の集合で構成されるDyck言語を取り上げていた。生成規則中の括弧は文字を表すことに注意)。上記を見ると、Dyck言語では2文字の場合は1通り、4文字の場合は2通り、6文字の場合は5通り存在する。一般の文字数では何通りあるのか?普通、この問に答えるには、漸化式や場合分けなどが沢山必要だろうというイメージがあった。通りであることがわかるのである。これを初めて見た時の感想は「あ・・・ありのまま今起こったことを話すぜ・・・!!」だった。あの場合の数の細かい操作が、全て解析的操作に押し込められていた。離散的なものを解析するのに、解析学の知見を使う系の物が好きな上に、複雑な対象が代数的に、かつ機械的に処理できるようなものが昔からかなり好きなのだけど、これはもう驚きの連続で見ているだけで幸せになれた。Starが母関数の無限等比級数を取る操作に等しいことだ。文字のものは常に1通りだ。母関数はとなることがわかる。これだけでは終わらない。いう正規表現があったとき(ここではDyck言語における括弧とは意味が異なり、括弧は文字としてカウントしていないことに注意)、なんとのようになるのだ。このマクローリン展開の一般項は、なんとフィボナッチ数列になることが、[1]の中で触れられている。番目のフィボナッチ数通りあるのだ。母関数が代数関数となることから、言語の母関数の極が無限にあればそれは文脈自由言語や正規言語ではないことがわかるなどの結果が紹介されていた。これは、正規表現でマッチしうる場合の数の性質と、文脈自由言語の性質が、解析学的には有理関数と代数関数の差として表現できるという、もうこれ哲学じゃん!!という内容だった。他にも、まだ読めていないがいわゆる無限の猿定理のフォーマルな証明などを紹介している。一般化し、異なる確率で得られるクーポンを集めるまでの回数の期待値を、マルコフ連鎖を用いて計算している。そこには正規言語の話など見慣れた話題が載っていた。この論文の定理4.1が、問題の期待値を求める式を与えている。いう論文が出典らしい。この論文では、所望の期待値を求めるために、なんと道具がガンマ関数の定義式であるオイラー積分にまで発展しているのだ!!これが、階乗を連続的に扱うためにガンマ関数で表示する、とかいう生半可な使い方ではないのだ。倍してオイラー積分を行うのだ。「え、ここでそれするの!?」と、久々に感動した。最初多項式の話をしていたと思ったら、みるみるうちに話が解析的になっていき、最後にはガンマ関数が出てきて度肝を抜かれた。この感動は是非元論文を読んで体験していただきたい。4ページで、アイデアもわかりやすいので、非常に読みやすい。Combinatoricsという名前がついているらしい。いう発表スライドを見つけた。著者だった!!一気に親しみを覚えると同時に少し寂しくなってしまった。どんな方だったのだろうか。ノードある二分木の数え上げなどが行われていた。等価、を更に推し進めたような規則が沢山書いてあるのだ。これは、正に「オートマトン理論再考」[1]を読んだ時の感動の源泉そのものだった。神秘を兼ね備えた感動をそのまま言い表していて、スライドの著者にとても同意した。Combinatoricsによる数え上げによってアルゴリズムの計算クラスを証明したりするらしい。このような美しい理論に実用的な使い道があるとますます嬉しくなる。Combinatoricsを発見した。こちらは、826ページにも亘るにもかかわらずオンラインで無料で全ページ公開されている。マクローリン展開の係数になっていることを発見したことから始まったという。この本のp.35では、凸多角形の三角形分割の場合の数がカタラン数で与えられることの直感的説明を紹介している。Dyck言語もカタラン数で与えられるため、三角形分割もDyck言語と同じような規則が存在するはずであると思ってこの本を読む前までしばらく悩んでいたのだが、このような複雑な構造をここまで直感的に説明できるものなのかと思った。読み進めていくと、そもそもこの分野を調べるきっかけとなったオートマトンの話などが載っており、目が幸せになりつつ、現在この本を読み進めている途中である。Combinatoricsの幕開けである1881年は彼の没後となる。Engineは、実はBabbageの生前は実装することができず、2002年に初めて実装されたとある。Combinatoricsという大変美しい理論によってアルゴリズムの計算量が測られる現代までの、風が吹くような勢いの変遷を見て、計算機科学に待ち受けるまだ見ぬ面白さにますます大きな期待を僕は寄せている。*1に関する記事です。ラストには長い滝が登場します。この滝は4つの部分に分けられますが、これらの滝は全て1つ目の滝に対して下記のような鏡像変換を適用したような配置になっていることに気付きました。2つ目の滝では、←と→が互いに入れ替わり、他のポジションは固定(ただし、最後の一音だけ例外で、→が入れ替わらず→のままになっています。)3つ目の滝では、↓と↑が互いに入れ替わり、他のポジションは固定4つ目の滝では、上記の変換が両方適用されるこの事実は目視では確認しづらいので、これを検証する下記のようなコードを書きました。言語はPythonです。実際、2つ目の滝の最後の音だけが入れ替わっていないことは、このコードを動かすことで初めて気付きました。stream_1.startswith(stream_4)print(stream_1)print(stream_2)print(stream_3)print(stream_4)なぜ二つ目の滝では最後の一音だけ→が入れ替わらず→のままになっているかという理由について、ここが←になっていた場合を考えると、3つ目の滝の冒頭の↑を右足で踏もうとした時に、すでに右足で←を踏んでしまっているため足が絡まってしまうことから、どうやらそのような事を防止するために最後の音だけ入れ替わらずにしてあるようです。4つ目の滝は途中で曲が減速する部分に入り、滝が途中で終わってしまいます。この理由について、これは鏡像変換を二つ適用していることから、実は省略されている部分は難しい配置になっているため途中で切っているのではないかと予想したのですが、特にそうではありませんでした。下記のコードによって、1つ目の滝に4つ目の滝の変換を適用することで省略された残りの滝の譜面を生成し、矢印表記で表示してみたのですが、特に変わった様子はありませんでした。(下記のコードは、上記のコードの末尾にappendして使います。Combinatoricsがめちゃくちゃ面白い。場合の数という離散的なものを数えるのに、連続的世界から生まれた解析学の知見を用いる分野だ。階乗をガンマ関数で表示するだとかいうレベルではなく、マクローリン展開の係数を調べることで場合の数を知るようなことをしている。)というサーベイ論文。文字となる出力の場合の数が直ちにわかるという内容を紹介していた。文字の場合の数になっているという。場合の数を数えるのになんとマクローリン展開!一体どういうことなのか。[1]中では「正しく対応する括弧の文字列」の集合で構成されるDyck言語を取り上げていた。生成規則中の括弧は文字を表すことに注意)。上記を見ると、Dyck言語では2文字の場合は1通り、4文字の場合は2通り、6文字の場合は5通り存在する。一般の文字数では何通りあるのか?普通、この問に答えるには、漸化式や場合分けなどが沢山必要だろうというイメージがあった。通りであることがわかるのである。これを初めて見た時の感想は「あ・・・ありのまま今起こったことを話すぜ・・・!!」だった。あの場合の数の細かい操作が、全て解析的操作に押し込められていた。離散的なものを解析するのに、解析学の知見を使う系の物が好きな上に、複雑な対象が代数的に、かつ機械的に処理できるようなものが昔からかなり好きなのだけど、これはもう驚きの連続で見ているだけで幸せになれた。Starが母関数の無限等比級数を取る操作に等しいことだ。文字のものは常に1通りだ。母関数はとなることがわかる。これだけでは終わらない。いう正規表現があったとき(ここではDyck言語における括弧とは意味が異なり、括弧は文字としてカウントしていないことに注意)、なんとのようになるのだ。このマクローリン展開の一般項は、なんとフィボナッチ数列になることが、[1]の中で触れられている。番目のフィボナッチ数通りあるのだ。母関数が代数関数となることから、言語の母関数の極が無限にあればそれは文脈自由言語や正規言語ではないことがわかるなどの結果が紹介されていた。これは、正規表現でマッチしうる場合の数の性質と、文脈自由言語の性質が、解析学的には有理関数と代数関数の差として表現できるという、もうこれ哲学じゃん!!という内容だった。他にも、まだ読めていないがいわゆる無限の猿定理のフォーマルな証明などを紹介している。一般化し、異なる確率で得られるクーポンを集めるまでの回数の期待値を、マルコフ連鎖を用いて計算している。そこには正規言語の話など見慣れた話題が載っていた。この論文の定理4.1が、問題の期待値を求める式を与えている。いう論文が出典らしい。この論文では、所望の期待値を求めるために、なんと道具がガンマ関数の定義式であるオイラー積分にまで発展しているのだ!!これが、階乗を連続的に扱うためにガンマ関数で表示する、とかいう生半可な使い方ではないのだ。倍してオイラー積分を行うのだ。「え、ここでそれするの!?」と、久々に感動した。最初多項式の話をしていたと思ったら、みるみるうちに話が解析的になっていき、最後にはガンマ関数が出てきて度肝を抜かれた。この感動は是非元論文を読んで体験していただきたい。4ページで、アイデアもわかりやすいので、非常に読みやすい。Combinatoricsという名前がついているらしい。いう発表スライドを見つけた。著者だった!!一気に親しみを覚えると同時に少し寂しくなってしまった。どんな方だったのだろうか。ノードある二分木の数え上げなどが行われていた。等価、を更に推し進めたような規則が沢山書いてあるのだ。これは、正に「オートマトン理論再考」[1]を読んだ時の感動の源泉そのものだった。神秘を兼ね備えた感動をそのまま言い表していて、スライドの著者にとても同意した。Combinatoricsによる数え上げによってアルゴリズムの計算クラスを証明したりするらしい。このような美しい理論に実用的な使い道があるとますます嬉しくなる。Combinatoricsを発見した。こちらは、826ページにも亘るにもかかわらずオンラインで無料で全ページ公開されている。マクローリン展開の係数になっていることを発見したことから始まったという。この本のp.35では、凸多角形の三角形分割の場合の数がカタラン数で与えられることの直感的説明を紹介している。Dyck言語もカタラン数で与えられるため、三角形分割もDyck言語と同じような規則が存在するはずであると思ってこの本を読む前までしばらく悩んでいたのだが、このような複雑な構造をここまで直感的に説明できるものなのかと思った。読み進めていくと、そもそもこの分野を調べるきっかけとなったオートマトンの話などが載っており、目が幸せになりつつ、現在この本を読み進めている途中である。Combinatoricsの幕開けである1881年は彼の没後となる。Engineは、実はBabbageの生前は実装することができず、2002年に初めて実装されたとある。Combinatoricsという大変美しい理論によってアルゴリズムの計算量が測られる現代までの、風が吹くような勢いの変遷を見て、計算機科学に待ち受けるまだ見ぬ面白さにますます大きな期待を僕は寄せている。world!プログラムの書き方を解説します。K入門の過程をまとめた記事でもあります。K入門の副読記事として活用して頂ければ幸いです。World!プログラムについて解説します。Kの相互翻訳法については、記事末尾の付録にて解説しています。自然数の表現まずはプログラミング上最も重要なデータの一つ、数を表現してみます。On参照)によって表現します。これは端的に言うと、自然数Nを、「任意の構造物fとXを捧げられた時、XにfをN回捧げた物を返す構造物」で表すという事です。(fがN回登場)に変換されるような構造物Nで、自然数Nを表します。Xとなり、確かにfにXを0回捧げた結果が返ってきます。ここでは長くなるので割愛しますが、「2に捧げるfに捧げるX」という構造物を評価すると、実際に「fに捧げる「fに捧げるX」」となることが確認できます。SUCCに捧げる2...のように計算できます。このような数の表現方法(チャーチエンコーディング)におけるポイントは、どの数の表現の最上層部にも禁断の者が存在しているため、これ以上の変形ができないという事です。「さけるチーズを避ける「裂けてるチーズ」」では禁断の者さけるチーズがいます。SUCCがさけるチーズとチーズという2人の禁断の者を含んでいることから、0を捧げても禁断の者さけるチーズが残り、これ以上の変形ができません。変形ができないことから、「最終的に計算結果の答えとして残す」ような使い方ができるのです。加算と累乗このような数の表し方の下で、数同士の演算も行うことができます。X+Yという計算は、「XにSUCCをY回適用する」ことによって表すことができます。(SUCCがY回登場)となります。(SUCCがY回登場)となり、捧げ物をすることで足し算が行える構造物を得ることができました。「fに捧げる「fに捧げる「fに捧げる「fに捧げるA」」」」となることがわかる。「fに捧げる「fに捧げる「fに捧げる「fに捧げる「fに捧げる「fに捧げる「fに捧げる「fに捧げるX」」」」」」」」これは、Xにfを8回捧げたものになっています。よって、「3に捧げる2」は、さけるチーズ言語でいう8に等しいことになります。ここでいう8は2の3乗を表しています。「与えられた物を3回捧げる」機能を持つものに「与えられた物を2回捧げる」機能を持つものを与えた結果、2×2×2回捧げることになった、というわけです。リストの表現さて、これまでで一つの数を表すことができました。文字列や数の列を扱うには、列の概念、つまりリストの概念が必要です。fに捧げるXに捧げるYとなるような構造物PAIRを考えます。「「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「さけるチーズを避けるチーズ」」と「「さけるチーズを避ける「チーズとさけるチーズと地図のある地、伊豆」」と「「さけるチーズを避ける「「裂けてるチーズ」とさけるチーズと地図のある地、伊豆」」と「さけるチーズを避けるチーズ」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と地図のある地、伊豆」と「さけるチーズを避ける「さけるチーズを避けるチーズ」」と地図のある地、伊豆」と表すことができます。(証明はとても長いのでここでは省略します。)ここで、PAIRにXとYのみを捧げ、fを捧げずPAIRに捧げるXに捧げるYで捧げ物を止めてみましょう。この構造物にはfを捧げる余地の為の禁断の者が1人含まれるため、これ以上変形できません。END))))という、入れ子になったペアを表しています。ここで、ENDはリストの終わりを表す特別な構造物です。Kをベースにしているため、ENDには256を用います。World!プログラムを書くことができます。さけるチーズでは、実行結果として残った構造物をASCII文字コードの入ったリストとして解釈し、文字列として表示します。「PAIRに捧げる72に捧げる「PAIRに捧げる101に捧げる「...に捧げる256」」」」...」」」」という構造物を作れば良いのです。K)では「プログラムに標準入力の値が捧げられる」ため、実行時には「PAIRに捧げる72に捧げる「PAIRに捧げる101に捧げる「...に捧げる256」」」」...」」」」に捧げる標準入力という構造物が評価されてしまいます。「さけるチーズを避けるHELLO_WORLD」というプログラムを書きます。World!を表示することができます。World!プログラムについて解説しました。累乗以外にも加減乗除など様々な演算を行うことができます。さけるチーズはチューリング完全であるため、数にまつわる演算ならばいかなるものでも行うことができます。Kの計算能力や方法には度々驚かされました。Onなどが非常に参考になります。Kではチャーチ数そのものを出力に用いることができず、単一の数字でも、必ずリストに入れて出力しなければいけないという事です。65という数字(ASCIIのAに対応)を出力したい時、チャーチ数の65を使うと出力されず、PAIRに捧げる65に捧げるENDという65を唯一の要素に持つリストを出力しなければなりません。これは仕様にしっかりと書いてあることなのですが、そもそもSKIコンビネータ計算におけるリストとは何なのか、という点から調べる必要があり、苦労しました。「「式」に捧げるAに捧げるBに捧げるC」4つ目の式が一番特徴的で、関数適用を「に捧げる」の文法で表しています。(SXY)Zのように、禁断の者(チーズ、さけるチーズ、地図)を空のコンビネータで置き換えることで翻訳が可能になります。)にZを適用したものであるためこうなっています。Kでは関数適用はコンビネータの直後に引数を置くだけで行えるということが、この翻訳の原理になっています。Programming最近、「裂けてるさけるチーズを裂けて避けるチーズが載ってる裂けてる地図を裂けて避けるチーズ」が話題になりました。togetter.com「さけるチーズを避けるチーズ」において、チーズがさけるチーズを避けた結果、残るのはチーズ。「さけるチーズを避けるチーズを避ける地図」において、さけるチーズとチーズが避けられた結果、残るのは地図。「裂けてるさけるチーズを裂けて避けるチーズが載ってる裂けてる地図を裂けて避けるチーズ」の「事の果て」には、何が残るのか?この記事では、そのような疑問を追うこと、つまりさけるチーズや地図が従う法則を追う行為によって、チューリング完全な純粋関数型言語「さけるチーズ」を構成します。Kと呼ばれる言語に束縛変数を導入することでラムダ計算風にし、自然言語的に意味が通るように中置記法に改めたものです。)例えば以下は、さけるチーズで記述した素数を無限に出力し続けるプログラムです。Codeをさけるチーズに変換しました。)このチーズ達の「せめぎ合い」の果てに何が残るのか、それを探す過程が素数を求める事に対応するのです。さけるチーズはチューリング完全であるため、これほど単純な文法を持ちながら、素数計算に限らず、計算機上で実行できるいかなる計算も実行することができます。自然数すら現れないこのコードで、なぜ素数が計算できるのか...?本当にそうなのか?という疑問に答えるため、この記事では上記のコードを実際に実行するために必要なツールを用意しました。さけるチーズ翻訳器を構成しました。(インタプリタ作成は今回は割愛しました。Kの相互翻訳器に載せています。さけるチーズとはどのような言語なのでしょうか。世の中には数多の言語が存在し、それぞれ複雑な構文や規則を持っています。さけるチーズに存在するのはたった4つの構文です。「チーズとさけるチーズと地図のある地、伊豆」の4つです。この言語の唯一の原則は、以上の語句が現れたタイミングで、自然の摂理に従った置き換えを行うという事です。2016まずは「さけるチーズを避けるチーズ」。「Yを避けるX」という語句が現れたら、「X」に置き換えます。YはXに避けられ、結果としてXが残るからです。これが第一の法則です。Cのように変形できるため、「「Yを避けるX」を避けるZ」を避ける「Aを避ける「Bを避けるC」」の実行結果(評価結果)はCという事になります。2016続いて、「裂けてるチーズ」です。「裂けてるX」という語句が現れたら、「X」に置き換えます。裂けたXはやがて自らの力で修復され、元に戻るからです。これが第二の法則です。Cとなり、「「Yを避けるX」を避けるZ」を避ける「裂けてる「Aを避ける「「裂けてるB」を避ける「裂けてるC」」」」の実行結果はCとなります。第三法則:Xに捧げるYさて、ここで事態は少し複雑になります。この構文を説明する前に、この世界(言語)に関する重要な定めについて話す必要があります。それは、この世界には触れてはならぬ禁断の者が3人存在するということです。彼らはすなわち、「さけるチーズ」「チーズ」「地図」です。実は、先ほどの第一、第二の法則、そして続く第四の法則では、これら禁断の者本人が存在する場合、置き換えを行ってはなりません。(※禁断の者を含む構造物を変形してはいけない!)と変形されます。一行目から二行目の変形は許されています。「Bを避けるチーズ」は禁断の者本人ではないため、「Aを避ける「Bを避けるチーズ」」は変形が可能なのです。第二行目において「チーズ」は禁断の者であることから、これ以上変形ができません。(※禁断の者を含む構造物を変形してはいけない!)のようになります。最後の一つ手前の行では、構造物が禁断の者チーズを含んでいるためこれ以上変形できません。ここで「Xを捧げるY」という構文が登場します。「Xを捧げるY」は、「Xに含まれる最強の禁断の者を、Yで置き換える」という規則です。禁断の者たちの強さの順番は、禁断の者の強さの順は「チーズ>さけるチーズ>地図」となっています。Xとなり、この構造物の値はXとなります。1行目から2行目の変形では、第一項(「Aを避ける「Bを避けるチーズ」」)の最上層部には禁断の者は存在しないため、「に捧げるX」は発動しません。第二項内部の第二項「チーズ」は、1行目の最上層には存在しないため、禁断の者としてカウントされません。2行目にたどり着くと、第一項(「Bを避けるチーズ」)が変形できない形になっています。ここで、「に捧げるX」という構文によって、2行目から3行目にかけて禁断の者チーズがXに置き換えられました。第一の法則によって、最終的にこの値はXとなっています。捧げ物同士で捧げあってはいけません。(※結果が正しい変形の場合と異なってしまっている)ということです。(つまり、「〜に捧げる」は左結合な演算子です。)(補足)禁断の者を、以下のように空欄で置き換えると、この法則が明快になります。「__2を避けるY」と変形されます。禁断の者に関するルールは、最上層に空欄が存在する構造物は変形してはいけないという事になります。第四法則:「チーズとさけるチーズと地図のある地、伊豆」さて、この法則がさけるチーズにおいて最も複雑な法則になります。神聖なる地、伊豆では、古来から物を捧げる文化が発達してきました(要出典)。Xに捧げるZに捧げる「Yに捧げるZ」です。裂けてるチーズとなり、答えは「裂けてるチーズ」となります。さけるチーズによるプログラミングさけるチーズの全ての文法が出揃った所で、さけるチーズによる実際のプログラミング方法を解説しながら、さけるチーズで実際にプログラミングが可能であることを示したいと思います。World!プログラムを扱います。Updateが始まってssh接続が切れてしまった...つらい...」こんな場面はしばしばあります。普通にssh接続をしている場合、接続を切るとタスクが止まってしまいます。すると上記のような場合、sshで接続している自機を一晩中つけておいたり、学校から家までsshの接続をずっと保っておくわけには行きません。Updateなどで強制的にsshが切られたらもっと嫌です。そんな時にはtmuxを使います。3個コマンドを覚えるだけで十分です。完熟トマトの「tmux利用のイメージ図」がわかりやすいです。簡単に言うと、tmuxはサーバー側に仮想端末を包み込んだ(アタッチした)プロセスを走らせておきます。この仮想端末はsshを切っても裏で動き続けてくれるので、一晩寝ていても裏でタスクを走らせ続けることができるのです。tmuxの使い方については主に下記のサイトを参考にしました。サーバー側でtmuxをインストールまずはターミナルからtmuxをインストールします。GitHubが参考になるかもしれません。作業開始:tmuxを起動いよいよtmuxを使います。sshで処理を行いたいサーバーへ接続します。tmuxを実行します。すると、仮想端末(セッション)が開始します。仮想端末は閉じたり開いたりするので、名前をつけておきます。b」「$」と続けて押します。(Controlで操作するのはemacsに似ていますね。)その後、セッション名を入力してEnterで名前がつきます。<session-name>とします。名前のついたセッションを起動しました。セッションは普通の端末と同じように使えるので、一晩投げたいタスクをここで実行します。作業中断:セッションのデタッチタスクも実行開始した所で、いよいよ一晩寝る時がやってきました。b」「d」と続けて押します。すると、仮想端末から抜けて普通の端末に戻ります。裏ではtmuxの仮想端末がちゃんと動いています。lsを実行してみましょう。すると、先ほど名前をつけた端末が裏で走っています。<session-name>とします。これで、先ほどの処理の実行途中でも、その端末の様子を見ることが出来ます。lsを実行しても、やはり裏で仮想端末が走り続けてくれています。これで、安心して一晩寝ることが出来ます。作業復帰:セッションのアタッチ新しい朝がやって来ました。<session-name>を実行します。lsで確認すれば大丈夫です。これで一晩寝られる!これで、あなたもサーバーにタスクを投げて一晩寝られるようになりました。tmuxにはここで紹介した他にも色々な便利な機能があります。NOTESが大変参考になります。