RustでParser combinatorを書いた
chasaというRustのparser combinatorを作った。おそらくparser combinatorは実際に車輪より再発明されていると思うが、今回の再発明にも理由がある。
Rustはplatformを選ばずunicodeが使える言語だ。str
はunicode文字列のことだし、unicode character categoryが手に入るlibraryとかも一通りそろっている。それになんと言っても高階関数が(trait
を通して)使える。
高階関数が自由に使える言語のうち、いくつかは型がないし(JS, Ruby)、いくつかはunicodeにきれいに対応してない(OCaml, Haskell)。残ったのがRustだが、これも一筋縄ではいかない。
例えば、有名なparser combinator libraryのNomやCombineでparserはParser
trait(型class)を実装する個別の型として実装される。なぜこんな回りくどいことになっているかは、closureの実装が環境と関数の組であることを思い出す必要があるが、とりあえずparserが個別の型を持っていることだけ知っておいて欲しい。これを崩すにはRustの軽快さを捨てる必要が出るくらいには本質的な問題だ。
この問題の一つとして、異なるparserをif文の分岐先に書けない。よくRustでは「関数の型を条件分岐の先に書けない」と言われるが、同じことである。違う型の物は同じ場所に書けない。すなわち次の(疑似)codeは型検査を通らない:
fn pure_or<I,O>(value: Option<O>, parser: Parser<I,O>) -> Parser<I,O> { if let Some(value) = value { pure(value) } else { parser } }
これを回避するにはEither
という型を用いてLeft(pure(value))
、Right(parser)
(これらは同じ型Either<A,B>
を持つ)と書かねばならず、分岐が多くなればその分だけLeft(Left(parser1))
、Left(Right(Right(parser4)))
などのように意味のない左右を連呼せねばならない。最初の文字で次のparserを決定する程度ならor
で十分だが、parserの結果を計算して次に実行すべきparserを決定するような、複雑なparserがどうしても書きづらくなってしまうのだ:
fn pure_or<O, I: Input, P: EasyParser<I,Output=O>>(value: Option<O>, parser: P) -> Either<Pure<O>, P> { if let Some(value) = value { Either::Left(pure(value)) } else { Either::Right(parser) } }
私はRubyの様な演算子の中値や前置が空白で変わる(f -x
= f(-x)
、f-x
= f - x
)言語のparserを書こうとしてEither
が4重くらいになった当たりで叫んで、新しいparser combinatorを書き始めた。こういうparserはPratt parserとして書くのが簡単なのだけど、Pratt parserは「parseした後に演算子の優先順位を比較して受理するか決め、演算子の種類から次に何が来るか決定する」という性質の物なので、演算子の数だけLeft(Left(Left(...
。
Either
も回避するには、新しくparserを書き直すしかない。つまり:
fn pure_or<O,I:Input,P>(value: Option<O>, parser: P, input: I) -> Result<(O,I),Error> { if let Some(value) = value { Ok((value, input)) } else { parser.parse(input) } }
のようにする。これではcombinatorの旨味が完全に失われてしまう。しかし我々の武器はcombinatorだけではない。method chainもRustでは強力な武器になる。すなわち、これをinputのmethod chainで処理して、
fn pure_or<O,I:Input,P>(value: Option<O>, parser: P, input: I) -> Result<(O,I),Error> { if let Some(value) = value { input.pure(value) } else { input.then(parser) } }
の様にしてしまえばよい。inputでは長いのでk
とでも置いてしまえば、簡単に書けるようになる。他のものもchainにしてしまうことで、次のような処理が簡単に書けてしまう:
use chasa::*; fn parser<I:Input<Item=char>>() -> impl ParserOnce<I,(),(),Nil,Output=usize> { one_of("abc".chars()).case(|char, k| match char { 'a' => k.pure(10), 'b' => k.then(parser).and(parser).map(|(a,b)| a + b), 'c' => k.then(parser), _ => unreachable!() }) } assert_eq!(parser.parse_easy("abc".chars()).ok(), Some(10)); assert_eq!(parser.parse_easy("bcaa".chars()).ok(), Some(20)); assert_eq!(parser.parse_easy("bcabacca".chars()).ok(), Some(30)); assert_eq!(parser.parse_easy("ba".chars()).ok(), None);
本来ならone_of("abc".chars()).bind(|char| ...
と書くところがone_of("abc".chars()).case(|char, k| ...
となっているのがミソで、再帰的なparserもお手の物である。このような単純な方法が他のcombinatorで採られなかった(と私が認識している)のは、「単純に条件分岐をするくらいなら関数を分けるべき」などの理屈があるのかも知れないが、便利ならばよいのだ。
他にも工夫した点はある。例えば、Rustで配列に確保してmap
map
するのはあんまり頭のいい方法ではない。そういうのはIterator
traitで処理するのが常識である。これをparserでも使える様にmany_with
というiteratorを操作する関数で内容を操作できるようにした。これはHaskellで渡されたList
を操作するのと殆ど変わらない処理と言っていいだろう:
use chasa::*; assert_eq!( any.many_with(|iter| iter.enumerate().collect::<Vec<_>>()) .parse_easy("abcde".chars()).ok(), Some(vec![(0,'a'),(1,'b'),(2,'c'),(3,'d'),(4,'e')]) ); assert_eq!( any.many_with(|iter| iter.take(2).collect::<String>()).and(char('c')) .parse_easy("abcde".chars()).ok(), Some(("ab".to_string(), 'c')) ); assert_eq!( any.and(char('a')).many_with(|iter| iter.collect::<Vec<_>>()) .parse_easy("baca".chars()).ok(), Some(vec![('b','a'),('c','a')]) ); assert_eq!( any.and(char('a')).many_with(|iter| iter.collect::<Vec<_>>()) .parse_easy("bacahh".chars()).ok(), None );
実はReader
monadとState
monadに相当するものも実装してある。単に引数に加えてあるだけなので、あんまり綺麗ではないが、parse全体で状態を持ちたかったり、parserに与える引数を引き回したりするのに便利だ。特にPythonのようなindent levelを引数として式の細かい部分まで引き回していたら疲れてしまう。
あとParsecなどでは次の方式が採られている: 入力を消費してさらにparserが続いたならそれは『構文が決定した』ということなので以降のor
を読まない。
これはJSONのparserを想像してもらえるとわかりやすくて、{
を受理した後に失敗した場合、[
から始まるlist literalを読みに行くのは完全に無駄であることから明らかだ。もちろん文法が確定するのが1文字だけとは限らないから、Parsecではtry
というcombinatorを用いて複数文字を囲うことで表現している。
or
を読みに行かなくてよいのであれば、実際に戻り読みのためのinputを捨ててよいので、こうした消費に併せて実際にcloneしたinputを破棄するような実装にしている。具体的にはdrop
という引数に&mut FnMut()
を渡していて、この関数の中でOption<Input>
をNone
にして取り去っている。これでfileを実際に読みながら戻り読みに応じてbufferを捨てることもできる。buffered streamを実装していないので今のところ宝の持ち腐れだが……
というわけでcase
によるinput chain、many_with
のiterator、引数と変数の引き回し、inputの適切なdropを実装したchasaをよろしく。私はこれでPratt parserの変種を実装していますがかなり快適です。
∑^n k^m を積分と漸化式で出す
だれしも、って積分して漸化式でいけない? って思ったことありませんかね。だからやります。
まず、和として としておきます。
すると、
ところで、なので、
となり、
なので、
を得ます。
これで、みんなが直感的に思っている「積分して最後の係数調整すれば出てくるんじゃねえの」という理屈が正当化されました。
なので、積分を繰り返せばは次式でしょう。最高次の係数は当然。
よって、と定めると、
より、
において、
を得ます。
の時を求めたいので、
を用いて、
この時、はベルヌーイ数と漸化式の定義が等しくなります。ソースはWikipedia。
あとは
と、そのようになっている事が確認できます。
できました。高2くらいの頃に泥臭く出してベルヌーイ数だったことに落胆した思い出があるのでリベンジです。
うざいし贅沢なつらみ
TL; TD
数学がちょっとできるから天才風キャラを演じて不当な学歴を得たけど最高にダサいしそのうち来るであろうしっぺ返しに怯えてるよ
ボクは生まれてこの方勉強をしていない。小学校では宿題しかしなかったし、夏休みの宿題は最後の数日で終わらせた。中学校でも宿題しかしなかったし、夏休みの宿題は夏休みのあとの1週間で終わらせた。毎日大学ノート何ページか勉強をしろと言われたから、ポエムを3年間書いて提出した。先生から皮肉たっぷりに「それでお前が勉強になると思ってるんならそれでいいから注意はしない」って言われたけど「じゃあ、なる」って本当に3年間ポエムだけ先生に提出した。高校では宿題もしなかった。
そんなだから、大体の教科が苦手。どのくらい苦手だったかと言うと、センター平均が学校の平均だと褒められる学校の化学のテストで半分ちょっとしか取れないくらい。社会はもうちょっと取れない。全然勉強しないから知識系は当然できない。英語も壊滅的で、いまも苦労してる。できたのは数学と物理だけど、90点はまあとれるかなーくらい。そんなにできる方じゃないと思う。
それなのに、ボクは勉強ができるように見えるらしい。でももうめんどくさくなって低い点数のテスト答案とか普通に晒していたと記憶してるんだけど、それでも社会や英語の答えをボクに訊いてきたから、ぼんやりと勉強のできるやつとしかみんな記憶してない。周りと話はするんだけど、ボクは人の顔が憶えられない(病気じゃない。他人に興味をもてないだけ。でもそれって最高にダサいよね。スカしてるって感じ)から、弱いつながりで生きてきた。
原因はわかる。数学だけそこそこできたから。毎日自分で数学の問題を作って解き、周りに見せびらかす。今思えば最低の行為だ。能ある鷹は爪を隠すから、ボクには能がないんだなというのがよくわかる。脳もないんじゃないのか。県の数学大会で優秀賞を取ったり数学好きの集まるキャンプに行ったりもしたけど、あれのレベルが高かったのかはいまいち釈然としない。学校の先生曰くすごいらしいんだけど、あれは楽しいだけで全然難しくない。北関東クソ田舎の自称進学校だって時点で察してほしい。
そうじゃなくても周りに偉そうにする性格だったから(友人曰く喋り方が孫正義だってさ。大学でも先生っぽいとか言われる)、勘違いするのも無理はなかったかもしれない。天才風キャラに見えていたかどうかはともかく、一旦見えてしまえば誰も疑いはしない。勉強をしないのは天才風キャラの邪魔にはならないし、テストの点数だってあんまり気にしないといえばそれまで。
高校受験では面接と作文しか見られなかったし、大学受験でも数学しか使ってない。それで学年で上位の大学に受かったので、ますます過大評価された。問題は面白くて興奮したけど7割解けてるかどうかも怪しかったから、個人的には「数学大好きです」スタンスを貫いたおかげで受かったんだとすら思ってる。受かったあと校長が「こいつは努力してきた」とか的はずれなこと言うし、高校の受験知見共有会でイラッと来たので、「テキトーにやってたら受かったので知見はないです」みたいなこと言ったら先生が慌ててた。最低。
AOで旧帝大レベルの数学科にはいった。頭悪そうだね。そこには、1年生にして大量のセミナー(先生がいないので、読書会みたいなニュアンスかな)を開いて群とか位相とかをバリバリやっている人だとか、ちょっとバカっぽく見えるのに英語が恐ろしくできる人だとか色々いた。それでもボクの数学能力だけは褒めてくるんだ。やめろ。もうこれはお世辞だと思うことにした。無視。あとみんな性格が良すぎる。ボクのことを立てながら話してくれる。ボクはそういう能力がないのでよく人を傷つける。入る大学間違えた。
そのうち痛い目見るよ。だって努力してないもん。そのうちしわ寄せやら報いやら来る。意地悪な家の爺さんは大きなつづらを選んで、鬼の集会でダンスを踊れなくて、妖怪に出くわしたりコブが増えたりしている。世の中のすべてが報われると警告している。大学生になってまで苦労してないと、そのうち人生が台無しになるレベルのしっぺ返しが来る。でもまだ来てない。失敗があとになればなるほど、その大きさはすごいだろうから、日々怯えてる。
この話、他の人にはできない(現実で雰囲気に酔ってこの話をしちゃったことはあるけど、大体「大丈夫だよ」って返ってくる。お世辞め)。だって、それをするには「ボクは努力してないけど周りから評価されてる」って最低の話をしなきゃいけないから。ここまで読んでくれた人には敬意を表する。ほんとうにありがとう。
そんなボクにも親友だと思える人はできた。田舎でそういう人がいないと死ぬからね。誰が誰だかわかっちゃうと困るけど、とりあえず話をするよ。
1人は、オタク。なんでか知らないけど先生にはめっちゃ嫌われる性格で、提出物を握りつぶされて未提出扱いされたりしたらしい。ボクが勉強をしない主義だったのと同じように、こいつも何もしなかったと記憶している。大学は知らないけど、「俺が高いところに受かってたら〜」論調で話をされたから本当につらい気分になった。こいつのお陰で技術的に充実した高校生活を送れたけど、ボクからは何もしてない。数学の知見を一方的にまくし立てたくらいか。
1人は、真面目くん。音楽と特撮が好きらしい。おとなしいし、よく勉強する。ボクとはまったく違う性格で、とても楽しい。幼稚園のころからの仲だ。3年生になるといつも勉強していて、こちらを不安にさせた。ボクがどんな気分のときも、変な顔をするくらいで毎日応対してくれた。風立ちぬを見て、堀越二郎にボクを重ねてきたときは過大評価にも程があると思った。そんないいやつが留年するとは思わないじゃないか。本来なら彼のほうが評価されるべきだ。家庭状況も複雑だし彼には幸せになってほしい。ボクが入試の直後暗くなって(落ちたと思っていたから)八つ当たりしたのが本当に心残りだ。
1人は、根暗? ちょっとインターネットの虚無虚無した感じの人。幼い頃からの付き合い。ボクが勉強をしてこなかった煽りをモロに食らって全然勉強せずに当然の結果を迎えたんだけど、そのせいで今自分に押しつぶされてるっぽい。本当に申し訳ない気持ちでいっぱいだ。
地元の医学部に受かったやつとも友人だった。こいつには数学の問題を「面白いよ」ってふっかけたら「面白そうだけど受験に間に合わないからあとで」って言われた。息をするように勉強する、怖いやつだった。サイコパスってこんな感じかな。痛みとか感じないんじゃないか。性格はとても良くて、やさしい。ボクが勉強のできないやつだって気づいたのもこいつのお陰。そうじゃなかったら今でも天狗だったんじゃないかな。怖い。
もしボクが天才風キャラを演じていないでちゃんと一人の高校生として友達をたくさん作っていたらもっと幸せだったかもしれないな、と思う。勉強しない人を少しでも減らせたかもしれない。もしかしたらボクの姿勢が親友を留年させたのかも。遠くの大学で寂しい思いすることもなかったかも。身の丈に会った大学でちゃんと同じレベルの友達ができていたかも。
そんなこんなで怖い。そもそも大学に受かったのが信じられない。朝目覚めたら実は受かってなくて、遮光カーテンを閉めたくらい部屋の隅でニートしてるんじゃないかとすら思う。そうじゃなくてもそのうち周りに数学で追い抜かれて死んでしまうんだろうな、と思ってる。
今はもう数学も特定の問題に突発的な興味が出て夜中3時まで解く、みたいな変な状況じゃなければ情熱はない。俺は雰囲気で数学をやっている。もうダメかもしれない。
再起もメモも行列も使わないで再起より確実に速いフィボナッチ数列の計算方法
今回はフィボナッチ数列です。本当何やってるんでしょうね
まず、の解の大きい方をとします
この数はと考えることができます
また、フィボナッチ数列の第項をとします
の時とすると、
であるため、であることが数学的帰納法で証明されます
ここから、
となり、
とが導けます
また、
から、
とという式も導けますが、今回はあんまり使いません
今回使うのは、先ほどの式のにを代入したとです
ここからはRubyでフィボナッチ数列を求める関数を書いていきます
通常のフィボナッチ数列の求め方は他に色々再起でやる例が紹介されているし、とても遅いので割愛します
まず、ビネの公式から近似値を求めて切り捨てるやつです
def fib1 n (((1+Math.sqrt(5))/2)**n / Math.sqrt(5) + 0.5).floor end
公式に当てはめてるだけなのでさほど複雑ではありませんね
ボクのマシンでは第71項目で誤差が生じ始め、第2000項程度でオーバーフローを起こしました
一方、こちらは先程の式を使ったものです
def fib3 n f = [1, 0] #F(-1) と F(0) n.to_s(2).each_char do |c| f = [f[0]**2 + f[1]**2, 2*f[0]*f[1] + f[1]**2] #F(2a)を求め、fに入れる f = [f[1], f[0] + f[1]] if c == '1' #その位の数が1ならF(a+1)を求め、fに入れる end f[1] end
2進数に直し、その後に10進数に直す時の要領で計算しています(2進数の筆算で検索)
もちろん再起は使っていませんし、メモ(一度した計算を保存)もしていません
ただ、ボクのマシンでは誤差が見たところ生じず、第1000000項目が数秒で求まりました
ベンチマークを取りました
fib2には行列で求める式をいれ、第0項目、第10項目……第1000000項目を各10回求めました(http://qiita.com/mathhun/items/4c117d33028a888f6fcf参照)
ビネの公式は早々に10000でへたった(オーバーフローした)ので、測ってません
user system total real fib2: 0 fib 0.000000 0.000000 0.000000 ( 0.000000) fib3: 0 fib 0.000000 0.000000 0.000000 ( 0.000000) user system total real fib2: 10 fib 0.000000 0.000000 0.000000 ( 0.000000) fib3: 10 fib 0.000000 0.000000 0.000000 ( 0.000000) user system total real fib2: 100 fib 0.000000 0.000000 0.000000 ( 0.000000) fib3: 100 fib 0.000000 0.000000 0.000000 ( 0.001001) user system total real fib2: 1000 fib 0.000000 0.000000 0.000000 ( 0.001001) fib3: 1000 fib 0.000000 0.000000 0.000000 ( 0.000000) user system total real fib2: 10000 fib 0.015000 0.000000 0.015000 ( 0.010007) fib3: 10000 fib 0.000000 0.000000 0.000000 ( 0.001000) user system total real fib2: 100000 fib 0.219000 0.000000 0.219000 ( 0.229153) fib3: 100000 fib 0.016000 0.016000 0.032000 ( 0.041026) user system total real fib2: 1000000 fib 5.484000 0.031000 5.515000 ( 5.892934) fib3: 1000000 fib 1.078000 0.000000 1.078000 ( 1.409943)
となりました
fib3がボクの式です
行列のほうが綺麗に解けるけどボクはこっちの式のが速いし好きだなあ
メソッドを呼び出したあとにNoMethodErrorを返してあたかも自分が定義されていないかのように振る舞えるメソッドを作りました
class Object def raise_n_m_error er ee = caller[0][/`([^']*)'/, 1] ex = NoMethodError.new begin self.__send__(?#) rescue $!.message.sub(?#, ee) end ex.set_backtrace(er) raise ex end end def test raise_n_m_error caller end test #=> test.rb:18:in `<main>': undefined method `test' for main:Object (NoMethodError)
これをメソッド内で呼び出すと、絶対に呼ばれないであろうメソッド#
が呼ばれます。
で、その後そのメソッド名の置換をし、caller
でバックトレースして返します。
これでエラー内容を偽装し、エラー発生位置を偽装することができます
もちろん、define_method
で#
が定義されると呼ばれてしまってなんか変なことになるのでそこら辺はまあ
以上っ!
わびさび方式から、インデント付きでみやすく、スペースを表示しないHTML(ジェームズ・クラーク式記法)に変換する
つまりこういうことです
def format_xml arr return "<!doctype html\n>#{_format_xml [arr]}" end def _format_xml(arr, args = {}) args = { :pre => false }.merge(args) return_text = '' arr.each_with_index do |item, index| if item.instance_of? Array inner = item[1..-1] return_text << "<#{item[0]}" if item[1].instance_of? Hash inner = item[2..-1] item[1].each do |key, val| return_text << " #{key}=\"#{val.gsub(/"/, '"')}\"" end end if item[0] =~ /(?:are|met)a|base(?:font)?|[bh]r|col|frame|i(?:mg|nput|sindex)|link|param/ return_text << "\n/>" else if item[0] =~ /s(?:tyle|cript)/ return_text << ">\n#{inner[0].gsub(/^/, ' ')}" else if item[0] == :pre inner_text = _format_xml(inner, args.merge(:pre => true)) else inner_text = _format_xml(inner, args) end if inner.length == 1 and (inner[0].instance_of? Array or ! inner_text.index("\n")) and return_text.length - (return_text.rindex("\n") || 0) + (inner_text.index("\n") || 0) < 80 return_text << ">#{inner_text}" else return_text << "\n >" return_text << inner_text.gsub(/(?<=\n)/, ' ') end end if index == arr.length - 1 return_text << "</#{item[0]}>" else return_text << "</#{item[0]}\n>" end end else if args[:pre] return_text << item.gsub(/\n/, "<br\n/>") else return_text << item end end end return return_text end
format_xmlにわびさび方式を引数として渡すと、HTML5の文書にして返してくれます。以上。
内容はインデント付きでそれなりに見やすくしたジェームズ・クラーク式記法です。
気に入ったので作った
追記
XML の James Clark 記法の件なんですけど生前に直接聞いてみた.結論から言うと James Clark 記法という表記は存在しない.渕さんがページを書く際に,そういえば James Clark がこういう記法使ってたなのを書いただけだった.
— Koichiro Eto (@eto) 2007, 11月 6
都のことなので、これはジェームズ・クラーク式記法ではないということになる。
などと紛らわしいので、カッコ付きにしておきました