オートマトンと正規表現のお勉強
計算理論の基礎 1 オートマトンと言語を買っていただいたので、少しずつ読んでいる。
オートマトンも正規表現も、齧ったことは何度もあるけれど、きちんと学んだことはなかった。
真っ当な情報系の学部を出ていれば普通はこのくらいの知識は持っているはずだろうけれど、真っ当とはいえない情報系の学部にいたし、卒業もしなかった。
最初は雑に読んでいたんだけれど、丁寧に読んだ方がいいなと思って読み直している。ついでに折角なので記録を取ろうと思う。
以下、メモ。
ちょっと理解に戸惑った箇所についてまとめ。二つの言語に対する連結演算の結果として、空列を受理する明らかに無駄と思われる状態が導入される。例えば p79 の正規表現 ab の例における空列を受理する状態等。これは演算の対象となる言語 A1, A2 それぞれの受理状態と開始状態を仮に q1, q2 とすると、q1 と q2 を等しいとするような操作はないので、新しく状態を導入することで連結を実現している。p71 の遷移関数の上から三番目がこの導入（された状態の遷移）に相当する。
p79 の NFA と等価な最小の NFA について "読者は、それを見つけられるだろうか？"とあるが、
オートマトンの気持ちになってる。 pic.twitter.com/bpweGka6to
— りりかるろじかる (@lyrical_logical) December 10, 2016
で多分あってるはず… a* から考えて (ab⋃a)* について考えれば割と自明。
追記：
メモを公開すると厳しい突っ込みが入る。
@lyrical_logical あと「言語」は列の集合のことであってそれを定義するオートマトンのことではないので、言語について受理状態と言っても意味が通らないと思います。読んで分からない文章ではありませんが、厳密な議論を展開する上でまずは用語を正しく理解することが重要でしょう🙆
— 坂口和彦@C91 1日目 西み-28a (@pi8027) December 10, 2016
ということで
二つの言語に対する連結演算の結果として、
は
同じΣを持つ任意の NFA N1, N2 を受理する正規言語 A1, A2 について、A1, A2 の連結演算の結果として～
とかで、以降も同じ。
病人の一日
今日は 10 時前に起きた。
起きたといっても、ボクが言う起きたには色んな意味がある。睡眠から覚醒した。布団から出た。布団から出て薬を飲んで薬が効き始めて動けるようになった。最後の意味で使うことが一番多い。最後の状態になる前に「起きた」をいう相手はいないし、ツイッターにツイートするくらいだけれど、ツイートしても大して意味はないし疲れるだけだ。今日は珍しく、覚醒してすぐ体調が良かったので、起きた旨をツイートした。服用している薬のうちの一つが四時間ほどしか効果がないので、効果が切れて痛みで目覚めればよく眠れず、眠りすぎれば起きる頃にはあちこち痛い状態になる。寝ながら薬が飲めればいいのに。
薬が効くまでは大したことはできない。ツイッターを見ていた。
今日も人々は自分の想像力のなさを認められずに騒いでいた。うんざりして、いい加減認めろとツイートした。誰が誤りのない人生をおくれるというのか。そんな聖人が現実にいるわけがない、馬鹿馬鹿しい。誰だって間違えたり、他人を傷つけたりすることはある。それを認め反省するところから始めないといけないのに、お前のあれはポリティカルコレクトでない、それはポリティカルコレクトでない、そんなことばかりいっている。一見正しそうに見える物事も、見方を変えれば間違いになったりする。主観の相違、見解の相違。命題論理程現実は単純じゃない。それなのに、一々あげつらって、最後にはポリティカルコレクトとは、なんて話をして、お前のポリティカルコレクトは正しい正しくないなんてことを言いあって、それで何がどうなるっていうんだ。
皆さんが自分の健康を主張するようなツイートをする度に、ちくりちくりと痛むボクの心は、体は、一体誰がケアしてくれるんだ。勿論そんなこと本気で望んでいない。自明に無理だとわかっているから。ボクだって、誰かの心をきっと痛め続けているんだろう。少なくとも母がボクの体調の事をずっと気に病んでいることは分かっている。
今日も人々は自分が愚かだということを認められない。
母に心配をかけたくはない。良くなりたいけれど、現実にはどうにもならない。土曜だかに浅草にいってひいたおみくじは吉、病は治るでしょうとのことだった。ボクは、母が自分のために、夫婦で旅行へ行く先々で、お守りだとか、何をすれば願いがかなうだとか、そういうものに縋っていることを知っている。母は別にオカルト信仰者ではない。多分母の気持ちの問題だ。その気持ちの強さに、ボクの 100 円のおみくじがかなうはずはなく、きっと今年も、来年も、再来年も、ボクは病人なのだろう。
マザコンだと思われるかもしれないけれど、どちからというと父親が何考えているのか分からないので、家族について話すとき母親の事しか書けないだけだ。お互い変わり者のようだから、お互いにこいつ何考えてるか分からんと思ってるんだろう。
自分の家庭は世間一般に比べれば恵まれていたと思う。その家族の父子ですらこうなのに、分かり合えるわけない。なんで皆分かり合えるなんて思っているんだろうか。もしくは思っていない、はじめから与えられた武器で相手をやっつけたいだけなんだろう。うんざりする。
閑話休題。母の話以降はこれを書いている今考えたことだ。時系列的には飛ばしていい。
人間に心底うんざりしたあと、記憶がブツンと消えてなくなっている。朧気に覚えているのは、良かったはずの体調が急に悪くなって、あちこちが痛み始めて、動けなくなる前に、何か食べてお薬増やしたほうがいいかな、とか考えていたような…体中のあちこちから発せられる痛みに耐えられなくなって、どうしようもなく、気が付いたら眠っていた。
起きたら、あわれキーボード（HHKB Pro 日本語版）は miniUSB ケーブルをはずされ、床に落ちていた。位置的に自分がふっ飛ばしたらしい。こんなだから miniUSB ケーブルばかり三度も買いなおす羽目になる。兎にも角にも、まず薬を飲んだ。充電スタンドにない携帯を、痛みを我慢しながら苦心して探した。矢張り床に落ちていた。視界の中に入っていたはずなのに認識するのにずいぶん時間がかかった。痛みがボクのすべてを緩慢にしていた。
アプリケーションで今日明日の気圧の推移をみる。見た時点で、数時間前から下がり続けていた。しかもアプリケーションの予想（この数値はどこからきているのだろう）が正しければ、明日の昼まで下がり続けるということだ。地獄だ。地獄がきてた、という旨のツイートした。いつもは気圧が下がっているときは、アプリケーションのスクリーンショットとともにツイートするのだけれど、それをする気もないほど疲れ切っていた。寝てたのに何で疲れるのかというと、寝ている間も体は痛みと、そこからくる緊張に襲われ続けているからだ。ひどい時は一日寝てるだけなのに、緊張し続けた筋肉が筋肉痛になったりする。痛みと同居している。
今日のボクは使い物にならないなと思いながら、TODO リストにどうしても今日やらないといけないものがないかを確認する。ない。横になる。ピンポンと、来訪者を知らせる音が鳴る。難儀して玄関までいくと、テレビアンテナの調子の確認で云々の日程が決まりましたといわれた。そういえばそんなことをすると前にも人がきて、言われたような…日程は大変都合の悪いものだったので、どうしたものかと思ったけれど、変更はできないのだろうなあと思っているうちに、話は終わって帰られてしまった。同じ階には今は誰も住んでいない。目下の問題は、この部屋が散らかっていて、掃除も最近できていないことだ。ここに業者の人を入れるのは忍びない。どこかのタイミングで最低限の掃除をしようと思い、TODO リストに追加した。
そのあとも、矢張り何をしていたのか思い出せない。痛みに打ち勝つぞという強い意志があるときでもないと、気圧の低下でボロボロになった体が発する痛みに、ボクの思考や理性は全く敵わない。ゲームをしようとしていた気もする。そうだ、そしたらアップデートを要求されてうんざりしてやめたのだ。今みたらアップデートは終わっていた。
それで今これを書いている。もう日付が変わる。これが病人の一日だ。勿論今日は特別に悪かった、ここまで悪い日はそう多くない、と思う。良い日もある。
疲れている時は悪いことばかり考えてしまう。痛みに耐えて、無理にでも眠ってしまうのが一番いい。んだけれど、寝ていたものだから眠気が一切ない。どうしたものか。もしかしたら病人の一日はこれから始まるのかもしれない。大層長い一日だなあ…
普段は兎も角、こういう日は、冗談抜きで要介護状態だと思う。結局ご飯も食べられていないし。これが毎日続くのなら違うのだろうけれど、そうではないので、ボクは生活保護以外に受けられる社会的なサポートはないらしい。ご飯も食べられない、まともに動けない、何もできない病人が、信じられる、想像できるだろうか。
これを読む前に想像できた人間だけがポリコレとやらで人間を叩けばいいんだろう。右わき腹の辺りが痛い。何か食べたい。指も疲れたし終わる。
JVM におけるメモリ効率の良い末尾再帰最適化の実装の紹介
やあやあ病人です。今日は特に予定もないので、最近読んだ論文の中から、適当にいくつかピックアップして紹介したいと思います。
Memory-efficient Tail Calls in the JVM with Imperative Functional Objects
JVM における TCE(Tail Call Elimination) については、長い間研究されてきています。六年前に JVM での TCE についての Odersky 先生の論文を紹介する記事を書いたりもしました。もう六年前…こちらの論文は TCE の実現における常套手段が JVM では通用しないよという話や、historical な話が面白くて、実際の提案手法は、まあダメでしょ…みたいなものだったのですが、今回の論文の手法はかなり良いと思います。
JVM で TCE というと、矢張り Trampoline です。Trampoline というと、Free モナドが数年前だかに流行った頃に、皆さん少しは齧っていると思うので説明は省略します。Trampoline で大体良いのですが、Trampoline はメソッド呼び出しの都度 memory allocation が生じるので、結局最後は OOM で死ぬという問題がありました。実際少なくともひと昔前の Scalaz の IO を真面目に使うと OOM で死にます。まあ Scalaz が footprint いくらなんでも気にしなさすぎというのもあると思いますが、そんな感じです。今は IO の実装とか諸々変わってるかもしれません。
話を戻して…今回の論文の提案手法では、general な TCE をメモリ使用量定数で実現することができます。実現方法は、言われてみればという感じで、特に難しくはなく、論文の主題としてはそれを利用することで FCore という System F の拡張を作れるよ（作ったよ）という部分だと思います。が、まあ System F なんて誰も興味ないと思うのでそこは飛ばします。
JVM での関数の representation は、Function as Object つまり Java8 の Functional Interfaces(aka SAM) が一般的です。というか他に知らないです。Scala も Kotlin も Clojure も Frege も Java との Interoperability を考えると、どうしてもそうなってしまいます。Functional Interfaces が加わった Java8 以降は特にそうです。論文では、Function as Object の頭文字をとってこれらを FAO と呼んでいます。
それに対して、FAO に代わるものとして、新しい関数の representation、Imperative Function Object 略して IFO と呼ばれるものが提案されています。これはどういうものかというと…見てもらうのが一番早いと思うので見てください。
public abstract class Function { Object arg, res; abstract void apply(); }
これだけです。引数や返り値を、フィールドとして持つようにしただけですね。本当にこれだけですが、色々と変わってきます。
Trampoline の問題点は、FAO の allocation がどうしても必要なので、メモリ使用量が定数にならないというところでした。一方で、IFO は関数を「使いまわす」ことで、これを回避します。FAO では使いまわせないのかというと、少し考えればわかると思うのですが、関数呼び出しには当然引数が必要になります。Trampoline を利用すると、引数が決定されるタイミングより、実際に関数を適用を行うタイミングの方が遅くなるので、bind 相当の処理が必要になり、結果として bind された FAO の allocation が発生します。
IFO では、引数をフィールドとして持っているので、bind の必要はありません。単純明快ですね。処理全体の流れとしては殆どトランポリンと同じで、IFO を保持する比較的スコープの大きい変数を用意しておき、関数適用したい場合は、代わりにその変数に IFO を渡して return。次に処理すべき IFO があるかどうかチェックして、あれば呼び、なければ最後の返り値をフィールドから返り値を取り出す。相互再帰の場合も問題なくいけます。
というわけで IFO いい感じなんですが、課題も色々あります。currying は必須、Object で持つと boxing/unboxing が生じる、mutable な外部スコープの変数を持つクロージャだと困る、thread-safety に実装するの大変、Java との Interoperability が下がる（IFO 版呼ぶ FAO 定義することで回避可能）、FAO と違い都度生成するのではなく、最初に生成しちゃうので部分適用とか使われるとだるい、と色々あります。
前述のとおり既に実装はあるので、試したい人はどうぞ。
もう一つ紹介したかったんですが、結構前に読んだ論文だったので間違いがないか読み直してたら大分疲れてしまったのでおしまい。
歩き方
生活保護受給者に戻ることにしました。
しましたというか、現実的に考えてそうせざるをえないというか。今年二月に請けた仕事でお金貰った時点で、生活保護は廃止になったものだと思っていたんですが、廃止ではなく停止扱いになっていたみたいです。まあ病気が治ったわけではないというのは役所の人も把握していたので、妥当な判断だなあと思いました。それをボクが聞かされてなかった or 忘れてたのは問題だけれど…
あまり言い訳はしたくないのですが、体調悪くて正直あまり営業もできてないし、そも病人というだけで仕事取ってくる難易度は高くなるので、まあ今のところ営業進捗全くダメです。楽観的にみて、根気よくやれば今年中には見つかるのではないかみたいな大変渋い状態なんですが、一方でそこまで貯蓄はもうないので、生活保護受給再開です。受給額どんどん減ってるんで本当に辛い。
ここ最近は本当に体調がずっと悪くて、なんでだろう…と思っていたんですが、なんとか仕事を取らないと、という焦りからくるストレスで、諸々悪化していたんだと思います。実際焦っていたし、焦らざるを得ない状況だった。しかしそれが原因で体調悪くしてたんじゃ、取れるものも取れない…本当に自分の現状が悔しくて悔しくて、ただその一心で頑張ろうとしていたんですが、それが負担になってしまっていたわけですね。一定諦めた途端に体調良くなって気が付きました。ダメですね。病人が頑張ろうとしちゃいけません。というか、そのぐらい色んな面で追い込まれていたということと、追い込まれることで体調悪くなるんだなということが結構ショックです。
生活保護の受給を再開するからといって、仕事を探すことをやめるということではないです。これからはもう少しゆっくりと、病人なりのペースで探そうと思います。生活保護は本当に受給額が厳しくなっていて、以前にも増してまともな生活送るのも大変なので、できれば早めにお仕事を見つけてまた脱したいという気持ちは当然あるんですが、焦ってまた体調悪くすることだけは避けるように、しないといけない…
病人には病人なりの歩き方生き方があるのだということは、わかっていたつもりだったんですが、まだまだだったようです。病人歴六年目なんだけれど、人間学びませんね。それともボクが特別ダメなんだろうか。
そんなわけで報告でした。
前述のとおり、お仕事は今後も探しますし募集します。こんな病人ですけれど、一応人並み以上にはプログラミング他、諸々できるつもりではいるので、何かあったら lyrica.logical あっと gmail.com までメールお願いします。何卒。
追い詰められてるときほど、追い詰められてる自分を見失いがちですね。特に病気で体調悪いと、そんなこと考える余裕もないし。参っちゃうなあ…何か無駄に長くなった。おしまい。
時間の使い方
病人というのは、多かれ少なかれ健常者よりも活動可能な時間が短い。何をするかにもよるけれど、自分の場合はざっくりいって半分とかになるんじゃないかなあと思う。時間を大切に使わないといけない、と思っていても、実践するのはなかなか難しい。
請けている仕事がないなら、いくらでも時間があるじゃないと思われそうだし、ボクもそう思いたいのだけれど、痛みが酷くてダウンしている時間とか、体力の問題でお昼寝してるとか、その他諸々含めると、そんなにない。その中で、営業行ったりアポとったりして残った時間は、いうほど多くない。
今日は生活保護中の年金が支払われていないと家に人がやってきた。生活保護を受けていれば支払い義務はないと思っていたのだけれど、支払い義務がないことを示すための手続きが必要らしい。そうだった気もする。どの道、今月仕事を見つけられなかったら、貯蓄的な問題で、次の仕事が見つかるまでまた生活保護に戻らざるを得ないので、その下準備に（見つかるといいんだけれどなあ…）役所へは行くつもりだったので、そこで解決しようと思う。書類関係はいつも何かしら間違えるので、詳しい人間に教えて貰いながらやるのが一番だ。世の中の仕組みを自分より知っている人間のサポートを受けるのは、多分正しいことだ。というか世の中の仕組みを知らないので、今の状態があるわけで…
話がそれてしまった。そういえば働き始めた二月からの今までの年金についても同じ問題があるし絶対今の状態だと払えないな…まあ役所いこう。本当は、貰えるあてもない年金なんて働きたくはないのだけれど、別にアナーキーでもないし、払わないことで生じる問題を考えると何事もとりあえず払っておくのが楽でいい。お金で解決できることはお金で解決しとくのが大体妥当だ。今お金ないんだけど。
プログラミングや計算機科学だけに絞っても、やりたいことはたくさんある。取捨選択しないといけない。あれはあとで、これはあとでなんでやっていると、無限に溜まってしまって何から手を付ければいいか分からなくなるし、そもそもなぜやりたいと思ったのかもそのうち忘れてしまう。最近体調が悪かったり関西にいったりで時間が取れなかったので、今まさにそうなっている。改善したい。どうすればいいのか。
病気を言い訳にはしたくないけれど、事実としてできないことがたくさんあって、やりたいことも十分にできなかったりするわけで、ちゃんと考えて何事もやっていかなければとは思う…んだけれど、まだ健康だった頃のボクは、人間なんて好きなことやってればよくて、好きなことがお金を稼ぐことな人間は絶対に一定いるから、なんとなくそんな感じで勝手に世の中が回っていくべきなのだと思っていた気がする。理想世界の実現の前に、自分がダメになってしまった。
それはそうと、三連休だということを完全に失念していたので、お薬がなくなる。ピンチだ。デパスくらいコンビニで売っててほしい。他に飲んでいるお薬はまだ少し余裕がある。
とりとめもなく散漫としているけれど、終わり。
