みどりねこ日記

よくわからないけど、頑張りますよ。

サービスに障害が発生したらどうしたらいいの?

どれだけ対策しようとサービスに障害はつきものですが、障害が発生したら損害が出るしユーザに謝ったりしないといけませんよね。 そういう非常につらい状況の中、障害からできるだけ早く復旧し、原因を究明して同じ障害が再び起きないよう対策を実施しなくてはならないわけですが、じゃあどうやったら効率的に調査できるの?という点についてまとめてみました。

障害つらいけどみんなで生きていきましょうね。

なおこの記事は所属とか関係なく個人の見解であり云々ということを最初にお伝えさせていただきます。働き始めるとこういうところが心配になっちゃうんですね…。

あともっとこうしたほうがいいんじゃない?というご指摘があれば記事の内容を変更を検討しますのでぜひご連絡下さいませ。

障害は発生します

前提

まず前提としてですが、どれだけ信頼性の高さを謳っているハードウェアを使っても壊れる時は壊れますし、ソフトウェアには不具合があります。 ハードディスクは容量いっぱいになるし、OOM Killerはいつだって包丁を研いでいるし、データベースは操作ミスで全部消えるかだってわかりません。 だから残念ながら障害が発生することは根本的に避けられません。 またユーザは原因についてはあんまり関心がありません。例えデータセンターにUFOが突き刺さったことが障害の原因だったとしても、重要なのはガチャが引けなくなったことです。 「オレのせいじゃないのに…」という気持ちは痛いほどわかりますが、何が原因であったとしてもサービス自体への影響を小さく抑えられるように頑張る必要があります。

事前の対策

ではどのような対策をしておけばいいのでしょうか。 例えばだいたいの場合において、バックアップとシステムの冗長化は非常に有効です。 定期的にデータのバックアップをしておけば、少なくともバックアップした時点までは復旧できるし、うまくシステムを冗長化しておけばシステムのコンポーネントのうち1個くらいに障害が発生しても何事もなかったかのようにサービスが継続できます。多分。 つまり原理的に障害の発生が避けられないなら、もう障害が発生することを前提としてシステムを設計しようよ、というわけです。

冗長化するということはコストが上がるってことでしょ?」という疑問は当然だと思います。 趣味で動かしているサービスとかだったら普段のランニングコストは抑えたいし、障害が発生しても「メンゴメンゴw」で済みます。 だからやりすぎればいいってもんじゃないという点については完全に同意です。 けど、エンタープライズならサービスが止まればサービスの信頼も落ちるし冗長化するために必要なコスト以上の損害が出るかもしれません。 なので、動かしているサービスの性質や、万が一障害が発生したらどれくらい損害が出るかを元に、どれくらいのダウンタイムが許されるのか、どの程度のデータの損失まで許されるのかといった見積もりをしてシステムを設計する必要があります。

復旧時間の短縮

障害が発生したときの対応を事前にチーム内で決めて共有しておくことで障害発生時の復旧を早めることができます。 復旧を優先するならその手順を、調査をする場合は何を見れば何を確認できるのかを事前に確認しておくことが重要です。 障害の影響度によって、とにかく復旧を急ぎたいのか、原因を調査するかは変わってきますので、この辺りの判断もできるだけ早く行いたいし、ベンダーのサポートに調査を依頼するときもこの辺の方針を一言入れておくだけで良い対応案を提案してくれるかもしれません。 また、ベンダーのトラブルシューティングや「よくあるご質問」のページへのリンクを共有し流し読みしておけば、障害発生時に「あ、これもしかしてあれかな…」と手がかりが得られる場合があります。

システムの構成がどうなっているかについてもチーム内で共有しておくと原因調査に役立ちます。 システムの障害は、そのシステムに詳しい人がいる時だけに発生するとは限りませんから、文章としてシステムの構成を記録して残しておきます。 例えば、サーバのハードウェア構成とか、アプリケーションの正しい状態はこうだ、そしてそれらはこのコマンドを打てば確認できる、というような文章が共有されていれば、「そもそもこれは不具合なのか?」「何が期待される動作と異なっているのか?」といった点をすぐ判別することができます。 サーバが一般的でない構成となっている場合は、その背景についても共有しておきます。 変な設定になっていたりすると「こいつが原因なんじゃね?」という偏見観点で調査をしてしまいがちですが、背景が納得できるものであればうまく切り分けができるかもしれません。 また背景がわかっていたら後々もっと良い構成を取ることができるようになるかもしれませんしね…。

テスト

システムのテストもしておきます。 障害に対する準備ができたと思っても、実際に障害が発生した時にうまく対応できなければ効果がありません。 一部のコンポーネントを落としてもサービスが継続するか、ネットワーク通信が遮断されても他のエンドポイントへ切り替わるか、バックアップからの復旧にはどれくらいの時間がかかるのかなど確かめておくと、いざという時に慌てなくて済みます。

メトリクスとログ

うっかり忘れてしまうところでしたが、障害に対応するためには当然ながら障害が発生したことを検知しなければなりません。 サービスは動いているのか?ネットワークに問題はないか?ハードウェアに異常は発生していないか?パフォーマンスは足りているのか?といった観点でチェックを定期的に行なって、異常な状態となったことをできるだけ早く検知します。 また、検知したときに自動的に復旧したりフェイルオーバーする仕組みを取り入れておけば、人が作業する時間を短縮できるのでそのぶんダウンタイムを減らせます。

最後に、ログは非常に重要です。できる限り取りましょう。 こいつがないと一体何が起きていたのかわからず大体の場合迷宮入りすることになります。

障害が発生したときの事前の準備はとても大事です。めんどいけど頑張りましょう…。

障害が発生したら

障害が発生したら、まず何が起きているのか、影響はどれくらいなのか、復旧か原因調査のどちらを優先するかを判断していきます。

復旧であればバックアップからデータの復元を行なったり、スタンバイへ切り替えを行ったりすることになります。 ただ、原因がわからない以上復旧しても再発する可能性はあるので、復旧を優先したとしても原因究明は必要です。

じゃあどうやって調査していくの、という点ですが、まずはどのような障害が発生していたのか?を確認していきます。 障害が発生していた、ということは何かを元に障害と判断したということなので、メトリクスなりログなり、ユーザからの問い合わせなりを確認します。

障害調査に必要な情報

障害調査を行う上では、以下のような情報が重要になります。 この辺の情報は時間が経つにつれ記憶が曖昧になったり、取得ができなくなったりするので、できるだけ早い段階で記録しておきます。 ベンダーのサポートに調査を依頼するときもこの辺の情報を要求する場合が多い、というか必須なので、できるだけ少ない往復で解決したいのであれば初回の問い合わせでこの辺とどこまで調査したかを伝えるのが良いです。

  • 事象の詳細
  • 事象の発生日時。いつからいつまで発生していたのか、今でも発生しているのか
  • 何を元に障害と判断したか
  • エラーメッセージ
  • システムログ
  • アプリケーションログ
  • 各種メトリクス
  • OSやアプリケーションのバージョン
  • システムの構成
  • ネットワーク周りなら通信相手の環境など
  • 再現性。同じような環境でも発生するのか、そのマシン固有なのかなど
  • 心当たり(直前にシステム構成を変更したりパッケージのアップデートを行ったなど)

事象の詳細って何?

事象の詳細や日時については、例えば「SSH接続できない」という事象でも、「他のマシンからは接続できるけど一部の環境からは接続できない」のか、「マシンへの疎通性がそもそもないのか」で全然違うものなので、できるだけ詳しく記録します。 ssh -vvvの出力はどうなっているのか、サーバ側のsshdは正常に起動しているのか、そのマシンで動いている他のアプリケーションは動作しているのか、ファイアウォールの設定はどうなっているのか、/var/log/secureはどうなってる?そもそもネットワークに繋がっているのか…といった感じで、色々確認していきます。

判断の根拠

何を元に障害と判断したか、というのは、だいたいの場合エラーメッセージだったりログだったり、メトリクスに異常な値が記録されているから、という答えになるかと思います。 障害の発生を判断するためには、「本来あるべき形」というものがわかっている必要があります。 「メトリクスが変に見えるから障害」というのは早計な場合があって、例えばストレージへの書き込みやネットワーク通信の量に異常に大きい値が記録されていても、実はバッチ処理を裏で動かしていただけだったり、アクセスの量が増えただけかもしれません。 CPU使用率が跳ね上がっていても、実はアプリケーションは正常に動作しているだけで、サービス自体には影響がなかったかもしれません。 この辺の判断は難しいので、複数のメトリクスを見つつサーバのキャパシティを大きくしたりしてどのように変化するかなど確認していく必要があります。

調査

実際の作業としては、事象が発生していた日時のログとそれぞれのメトリクスを眺めながら、相関らしいものがあるか、謎のエラーメッセージがあるかなどを頑張って見つけていくことになります。 Linuxであれば、syslogや/var/log/messages、/var/log/secure、/var/log/ntp.log、sysstatの結果、WindowsならApplication.evtx、System.evtxなどのログを取得します。 ipmitoolが使える環境なら、ハードウェア側に問題があったかなどを確認することもできますので設定しておきましょう。 OS上のログだけではなく、例えばZabbixなどの記録があればそれらも含めて何が起きていたのかを精査していきます。

OSやアプリケーションのバージョンに依存して発生する不具合もあります。 この辺りも記録して、似たような事象が報告されていないかを公式フォーラムなどで確認します。 それと使っているアプリケーションのバージョンはできるだけアップデートしましょう。 古いバージョンを使い続けることは楽ではあるのですが、セキュリティ上のリスクがあったり機能の制限があったりしてだんだん不便になってきます。サポートもいずれ切れます。 バージョンがものすごく古くなってから最新のものにアップグレードするコストは大きくなりがちで、そうなると「もう移行無理です」みたいな状況になるかもしれません。色々なしがらみがあって大変だろうとは思いますが、マメにアップデートできるよう頑張りましょう…。 なおバージョンを変更する前には必ずバックアップをとって不測の事態に備えておきます。

システムの構成や通信相手の環境が原因で発生する障害は少なくないです。 エラーから「こいつが原因じゃね?」ってサーバ側の設定を疑っても問題が見られない場合は、もうちょっと広い視点を持って、例えばアプリケーションが利用するAPIサーバとは正常に通信できていたのか、社内のネットワーク設定やファイアウォールに変更がなかったかといった観点で見直してみましょう。

それでもわからないとき

以上を実施したけど全然わかんねえ、という場合は各ベンダーの技術サポートにぶん投げてみましょう。 もしかしたら何かいいアドバイスをくれるかもしれません。なお技術サポートはだいたいの場合サポート範囲があるので、その範囲内での質問にしましょう。 あとサポートも人間なので、できるだけ紳士的に問い合わせましょうね!

原因究明したら

原因がわかったらなんらかの対応が必要になります。 まずユーザへ影響があったなら、早めに謝罪をします。また、可能な範囲で影響範囲と当面の事象のワークアラウンドについてアナウンスをします。 その次に、サービスへの影響度とコストから、そもそもこれは対応が必要なのか、どのような対応を行なっていけば良いかという点について考えていきます。 対応が完了し次第、事象から得た教訓と対応をドキュメントにまとめて一旦収束…という形にしたいですね(願望)。

「なんか障害起きてたけど全然わかんねえ、どうしたらいいんだ」という場合は、なぜ切り分けができなかったかということを考えて、それを元に再発した時に調査できるようログの設定やメトリクスの追加をしておきます。 また、何度も障害が発生するのであれば、障害が発生していた時の共通点を見つけるために発生日時やログ、メトリクスを収集しておきます。 いつか原因わかるといいですねって感じですが、気長に頑張っていきましょう。

頑張っていきましょう

だいたい上のような対応になりますが、何か「変じゃないこれ?」みたいな部分があったらお知らせいただけると幸いです。 人生はつらいけど頑張っていきましょう。

この漫画が好きだ!と発表したくてたまらなくなったので発表します

本日はクレジットカードの支払い金額が確定する日。 ふと「今月はいくらくらいになったのかな〜」くらいの軽い気持ちで金額を確認したらトンデモな金額になっていた。

自堕落な生活を送っているといえども、さすがに明細を見ざるを得ない金額。 なぜなら大きな買い物をした記憶がなかったからだ。

明細を見た所、やはり記憶は正し…くはなかった。普通に山道具購入してた。 しかしながらそれを差っ引いても大きすぎる請求。 なんでや、不正利用されたんか〜???って思いたかったけど、 ずらっと並ぶ「Amazon Downloads 」の文字を無視しきれない。

そう、Kindle破産である。

確認したら毎月だいたい8万円くらい漫画買っていることになっていた。 そして今月はそれをはるかに上回る金額。まあ雨の日が続いたからね、仕方ないね…。

本当であれば、本日は山梨のキャンプ場で景色を楽しみながらココアを飲んでいるはずだった。 しかし請求金額を見て、外界にお金を流出させるわけにはいかないなという気持ちになり、今日は家の中で暇を持て余した結果ブログを書いている次第である。

僕は表紙買いしてたまに面白い漫画を見つけられた時が一番嬉しいタイプである。 この記事はそうやって見つけた漫画をいくつか紹介させていただき、我が散財への供養とするものである。 誰かの本を批評することはなんだか恐れ多いし、おこがましいとも思うのだが、こんな面白い本があるんやで!と言わずにはいられなかった。

というわけで是非聞いてほしい!そして読んでほしい!


星明かりグラフィクス 1 (ハルタコミックス)

星明かりグラフィクス 1 (ハルタコミックス)

星明かりグラフィクス

潔癖症で人格に難ありの天才と、人の間に入るのがうまい普通の美大生のふたりの話。 僕が説明すると作品の面白さを損ねるような気になるので、とにかく読んでほしい。

ふたりモノローグ

幼馴染の再会から物語が始まる。 おとなしい主人公と、彼女に偏執的な愛を抱くクールなギャルの話である。 ふたりの距離感が少しずつ近づいていくのが微笑ましい。 著者のツナミノユウさんは「つまさきおとしと私」という作品で知った。 ふたりモノローグはドラマ化もするそうな。

麻衣の虫ぐらし

無職の主人公がフラフラ農業手伝ったりする。 何が好きなのかよくわからないが好き。説明がクソでごめん、けど面白いよ。

働かないふたり 1巻 (バンチコミックス)

働かないふたり 1巻 (バンチコミックス)

働かないふたり

この作品、以前はブログにて連載されていた。 ニートの兄妹がほのぼの毎日を過ごすだけの話だが癒される。

木曜日のフルット

石黒正数さんの作品。 それ町と似た雰囲気で、のどかな日常。 最近少しフルットがたくましくなった気がする。一方飼い主はあまり…。

ゴーゴーダイナマイツ

父とヒゲゴリラと私

この二つの作品は同じ著者が書いたもの。ゴーゴーダイナマイツはすでに完結。 疲れた時に読むとなんだか安心する作品。

惰性67パーセント

大学生の生活を抽出して濃縮させたみたいな作品。

スペクトラルウィザード

スペクトラルウィザード

スペクトラルウィザード

騎士団に追われる魔術師が寂しい生活を送るという話なのだが、重い話ではない。救いはあるし笑いもある。 「金魚王国の崩壊」の模造クリスタルによる作品。

はねバド!

高校バドミントンが舞台。1巻と5巻の表紙の差が気になりすぎて購入。 登場人物一人一人に魅力があって、全員がかっこいい。 僕は重盛さんが一番好き。

ゆるキャン

高校生がキャンプをする話。 僕も高校生の時キャンプが好きだったので、「あ〜、高校生ってお金ないよね…」とか、「お金ないと荷物重くなってしんどいんだよな〜、車かあいいなあ」などと無駄に感情移入してしまう。 アニメ化もするらしいので楽しみです。

あそびあそばせ

著者は、あの「ゆえに人は豚である」で有名?な「りとる・けいおす」の著者である涼川りんさん。 ハイペースで笑わせにくる。

ちおちゃんの通学路

主人公のちおちゃん及び友人がいい感じに情けなく、そしてゲスい。


以上が誰かに「好きだー!!!」と言わずにはいられない作品であった。ああスッキリ。

ただまあ、こんな記事を書きつつ今日も数冊Kindle買ってしまったあたりで人の性というものを感じてしみじみしている。

あ、面白い漫画あったら教えてください。

未踏事業に出した提案が不採択となったので資料を公開します

大学院時代の友人である森下くんと一緒に未踏事業に出した提案が不採択となりました。 私は今年25歳になり、来年以降は未踏事業の年齢制限に引っかかってしまうため、今回が未踏クリエータになる最後の機会でした。 そして残念ながらそれを活かすことができませんでした。

申請書、二次審査の発表資料及びPMからいただいた不採択理由を公開します。 不採択とはなりましたが、以下に公開する資料が今後未踏事業への提案を考えている方の参考になれば幸いです。 ちなみに形式は年によって結構異なるようです。あくまで参考にどうぞ。

一次審査

https://drive.google.com/file/d/0B9q5iVCNpwDlT2V2dHhJdGJHdEE/view?usp=sharing

二次審査

https://drive.google.com/open?id=0B9q5iVCNpwDla2pVUU9yZjk4MnM

不採択理由(PMのコメント)

技術的に特に新しいところや難しいところはなく、むしろ広くユーザを獲得して大きなトレンドにすることに一番の課題があるように思われました。つまり、この種のプロジェクトの最大の課題はユーザのインセンティブの確保の戦略です。これが現時点では、ブラウザプラグインという(ひょっとして気がつかないうちに実装されている)仕掛けのみだと思われました。それでも、ネットワーク帯域幅とディスク容量を食われるので、P2Pの好きな人でも、アーカイブというテーマでは導入を逡巡すると思われます。 むしろ、The Internet Archiveのようなものを非集中・分散で構築できるソフトウェアを開発して、有志なり大学なりがサーバ上で運営する、というシナリオならよかったかもしれません。 それよりもすべてのPMが感じた不安が、就職したばかりで必要な時間が本当に取れるのだろうかということでした。提案のときには、就職先と事前のネゴはしっかりしておいてほしかったですね。

スケジュール

申請書の締め切り(一次審査)は3/3でした。

一次審査の通過及び二次審査に関する連絡が来たのは4/3です。

二次審査は4/16に行われ、不採択通知が来たのは5/28でした。

ちなみに一次審査の倍率は3.3倍だったそうです。

所感

未踏事業には憧れがあったので、不採択となったことは本当に残念です。

提案したプロジェクトに関してPMから貴重な意見をいただきましたが、前半部分に関してはおっしゃる通りで、もっと良い方法もあっただろうと考えています。 しかし後半の「サーバで運用」という話に関しては、あまり同意できません。 もちろんサーバを補助的に使っていくというのは考えておりましたが、大学機関などのサーバに頼ることを前提にしたアーキテクチャでは我々の解決したい問題の根本的な部分は解決しません。 そういった面で我々のしたいこととは方向性が異なると感じています。

私はインターネットの利用者がPure Peer-to-Peerでアーカイブ及びCDNを行い、 互いのために少しずつ負担を負うことに意味があると思っているし、 面白いと思っているので、また別の機会にいつか実装するかもしれません。

私も森下くんも今年から社会人であり、 またどちらも4/16の二次審査の段階で所属する会社と兼業について交渉中であったことは大きな敗因だと考えています。 しかしやれることはやっていたので、これ以上どうしようもなかったと思っています。

森下くんは本当によく頑張ってくれました。ありがとう。

ただやはり悔しいですね。

謝辞

ご協力いただいた方々にお礼を申し上げます。

特にXcoo, Inc.の西村さん、青木さん、 及びUhuru Technical Rockstarsの部谷さんに感謝します。 過去に採択された際の申請書を送っていただいたり、貴重なアドバイスをいただきました。

応援していただいた、所属する会社の上司及び同僚に感謝します。

全然関係ないけど

Xcoo, Inc.は人材募集中です。

追記

未踏アドバンスド事業があるので「今回が未踏クリエータになる最後の機会でした」という書き方は不正確ではないかという旨のコメントをいくつか頂いたのでご回答させていただきます。

未踏アドバンスドは技術より事業化を目的とされているように見受けられました。 事業化は大事なステップであることは理解しているつもりですが、収益は見込めなくても人々の生活を変えられるようなプロジェクトもサポートしてくれる未踏事業に対して憧れがあったためにこのように書いています。

Pythonを呼べるLispを作った話

この記事はLisp Advent Calendar 2016 5日目の記事です。

Futhonとは

Futhonとは、Pythonが呼べるLispである。 先日作ってみた。 読み方は「ふとん」である。

本記事は、Futhonの内部実装がどうなっているかを簡単に説明する。 すごく小さな実装(ソースコードすべて含んで500行くらい)なので、この記事とコードを合わせて読めば誰でもちょっとしたおもちゃ言語が作れるようになるんじゃないかと思う。

作った動機

最近周りで機械学習がアツい。

Pythonディープラーニング機械学習ライブラリが充実していて、モデルを簡単に作ったり試したりすることができる素晴らしい環境になっている。

一方で、Lispニューラルネットを組もうと思ってもライブラリがなかったり、あってもドキュメントが少なかったりしたのでどうしたものかと悩んでいた。

そこで、ClojureJavaのリソースを利用できるように、Pythonのライブラリを自在に呼び出せるLispを実装して解決しようという考えに至った。 その結果完成した言語がこちらのFuthon言語。 Clojureにはcore.matrixとかあるから自分でそういうライブラリ実装すればいいじゃないかという意見は聞こえない。たぶん言語実装したほうがコスト小さい…。

実装の方針

Pythonのライブラリを自作言語から呼ぶ方法はいくつかある。 そのうちで検討したのは以下の3つである。

まず一つ目は実装がしんどそうな割にあまりメリットもなく思われたので候補から外した。そもそもC++について詳しくないので難航するのは目に見えていた。 二つ目が最有力候補だったけれどREPLの実装の仕方がわからなかったために断念。 というのは、REPLを実装するには順に入力された式を評価しながら何らかの方法でPython側の環境を管理する必要があるが、その仕方が思いつかなかった。 実はPythonにはcode.InteractiveConsoleというクラスが用意されていて、これの継承クラスを書いてやれば簡単にできることをあとあと知った。 結局、最後のメタプログラミングをする方法が実装に手間も時間もかからなさそうだったのでこれを採用した。

実装の大まかな流れ

大きく分けると、インタプリタはだいたい以下の要素で構成されている。

  • トークナイザ
  • パーザ
  • 評価器
  • プリンタ

トークナイザとパーザは、ライブラリによっては一緒に行われる場合もある。 これらを順に実装していくことになる。ここでもその順番に説明していく。

データ型と文法

最初にプログラミング言語のデータ型と構文を決める。 Futhonには以下のデータ型をプリミティブとして持たせることにした。

  • Vector
  • Set
  • HashMap
  • Symbol
  • Keyword
  • Lambda

以下がBNFで表記した文法。

program ::= sexpr

sexpr ::= atom | sequence | quoted

atom ::= string | regex_string | symbol
sequence ::= vector | list | hashmap | set

quoted ::= '\'' sexpr

symbol ::= '[_@\w.\-><\+\-\*\/\?!:=]+'
string ::= '".*?(?<!\\)(\\\\)*?"'
regex_string ::= '\#' string

vector ::= '\[' sexpr* '\]'
list ::= '\(' sexpr* '\)'
hashmap ::= '{' (sexpr sexpr)* '}'
set: '\#{' sexpr* '}'

Futhonプリミティブであるデータ型はFuthonObjectを継承するクラスとして実装する。 そうすると独自の型なのかPython側のオブジェクトなのかがisinstance(x, FuthonObject)するだけで判別できる。 ついでに__repr__のように、あったら便利かもみたいなメソッドをデータ型ごとに追加していく。 これらの詳しい定義はdatatypes.pyを参照のこと。

class Symbol(FuthonObject):
    def __init__(self, name):
        self.name = name
        
    def __repr__(self):
        return self.name

    def __hash__(self):
        return hash(self.name)

    def __eq__(self, other):
        return isinstance(other, Symbol) and self.name == other.name

    def __ne__(self, other):
        return not self.__eq__(self, other)

文法

トークナイザ・パーザ

ソースコードからいきなり実行しようとすると、実装が難しい。 なので、ソースコードからトークンを切り出したり、木構造を生成して後に続く処理を楽にする。 これをするのがトークナイザとパーザ。 パーザの生成にはPlyPlusというパーザジェネレータを使う。 ドキュメントはあまりないがサンプルはあり、BNF表記でLRパーザが生成される点が素敵。 このライブラリを使えばトークナイザを作る必要もないので「とりあえずパーズしたい」という場合には便利だと思う。

start: sexpr;

@sexpr: atom | sequence | quoted;

@atom: string | regex_string | symbol;
@sequence: vector | list | hashmap | set;

quoted: '\'' sexpr;

symbol: '[_@\w.\-><\+\-\*\/\?!:=]+';
string: '".*?(?<!\\)(\\\\)*?"';
regex_string: '\#' string;

vector: '\[' sexpr* '\]';
list: '\(' sexpr* '\)';
hashmap: '{' (sexpr sexpr)* '}';
set: '\#{' sexpr* '}';

WS: '[ \t\n,]+' (%ignore) (%newline);

あとは生成されたLRパーザを呼び出してやって、それぞれ対応するデータ型に変換してやればパージングは終わり。 この辺の実装はfuthon_parser.pyに書かれている。

評価器

式の評価

大抵のプログラミング言語のパーズ結果は抽象構文木である。これはもちろんFuthonでも同様。 そういうわけで、得られた木構造をゴリゴリ評価していく。 Futhonは変数を持つ言語なので、評価する際には変数と値の対応を管理する環境という機構が必要になる。 さらにFuthonからPythonのメソッドなどを呼び出せるようにしたいのでPythonメタプログラミングが必要になる。

環境

環境は変数と値を対応づけるための構造。 Futhonの環境は階層的な構造を持っており、そうすることで変数の局所的な定義などができるようになる。 例えばFuthonでは定義された関数は新しい環境を持つことになるが、同時に生成された時点の環境を上位に持つことで、その時点での環境を関数内から参照できるようになる。

コード上の実装としては上の環境へのリンクを持つ、変数からFuthonObjectへのdict型という感じ。 environment.pyを読めばだいたいわかるはず。

Pythonメタプログラミング

FuthonではPythonのメソッド呼び出しやクラス生成を実行時に行いたいので、これらを実現する方法がホスト言語側に求められる。 幸いPythonにはいくつかそういったものが用意されていて、例えばgetattrを使えばPythonでクラスやメソッドをロードしたり呼び出したりできる。 getattrPythonの組み込み関数で、引数としてPythonのオブジェクトと属性名をあらわす文字列の二つを取り、そのオブジェクトの属性を返す。

class Hello():
    def __init__(self):
        self.hello = "nice to meet you!"

    def greeting(self):
        return self.hello

hi = Hello()
getattr(hi, "hello")
# => "nice to meet you!"
getattr(hi, "greeting")
# => <bound method Hello.greetings of <__main__.Hello object at 0x7febcaf46470>>

getattrで得られたオブジェクトがメソッドなのかはinspect.ismethod()で判別できる。 ただしこれだけではBuilt-in functionなのかどうかまでは分からないので、isinstance(o, types.BuiltinFunctionType)などでチェックする必要がある。 Futhonではメソッド呼び出しと一部のBuilt-in functionのみをサポートしている。

モジュールをインポートする場合はimportlib.import_moduleにモジュール名を渡してやればモジュールオブジェクトが返ってくる。

importlib.import_module("numpy")
# => <module 'numpy' from '/home/delihiros/.pyenv/versions/3.5-dev/lib/python3.5/site-packages/numpy/__init__.py'>

このへんのコードはdynamic.pyにまとめた。

こういうちょっとメタ的な仕様は他にも色々あって、例えばBuilt-in functionであるtypeに3つ引数を与えるとPythonのクラスを新しく生成できたりする。 興味ある人は公式ドキュメントを読んでほしい。 今回は後述する事情により途中で飽きた必要そうでもなかったので取り入れなかった。

以上で評価をするための部品はできた。

評価を行う

あとは実際に抽象構文木の評価を行う。 基本的には抽象構文木の根から葉に向かって深さ優先探索で評価をしていく。 このとき、与えられたノードの型によって評価の仕方を分ける。 例えばFuthonObjectではなくPython側のオブジェクトだったら、そのまま返す。Symbolだったら環境から対応する値を見つけてきて返す、など。 ただし、リストの場合はFuthonの式の可能性があるので特別な評価を行う。 これらの処理はevaluator.pyにある。

def eval(self, expr, env):
    if not datatypes.isFuthonObj(expr):
        if isinstance(expr, list):
            return self.eval_list(expr, env)
        return expr
    elif datatypes.isSymbol(expr):
        return env.get(expr)
    elif datatypes.isKeyword(expr):
        return expr
    elif datatypes.isVector(expr):
        return datatypes.Vector([self.eval(e, env) for e in expr])
    elif datatypes.isSet(expr):
        return datatypes.Set([self.eval(e, env) for e in expr])

リストの場合は、その先頭にあるオブジェクトの型と名前を見て、合致する条件に対応した処理を行う。 例えば、先頭がdefifのように特別な意味を持つSymbolの場合、環境に対して操作を行ったり条件分岐を行ったりする。 先頭が関数やメソッドの場合はそれらを適用する。

def eval_list(self, expr, env):
    if len(expr) == 0:
        return expr
    head = expr[0]
    if datatypes.isSymbol(head):
        if head.name == 'def':
            env.set(expr[1], self.eval(expr[2], env))
            return None
...
    elif datatypes.isLambda(head):
        args = [self.eval(v, env) for v in expr[1:]]
        return self.apply_function(head, args, env)
...

REPL

評価もできるようになったので、あとは外部からプログラムを読み込めるようにすれば終わり。 入力をパースして評価、という処理を繰り返すだけのREPLを実装した。 コードはrepl.pyにある。

(def np (import numpy))
(def chainer (import chainer))

(def l1 (chainer.links.Linear 4 3))
(def l2 (chainer.links.Linear 3 2))

(def my-forward
  (fn [x] (l2 (l1 x))))

(def x (.astype (np.array [[1 2 3 4]]) np.float32))

(.data (my-forward x))
; [[-1.02830815  0.6110245 ]]

これでひとまず大体の機能は備わったので、ChainerやTensorFlowのようなライブラリを使ってニューラルネットLispで書けるようになった。 やったね!!!!!!

オチ

Hyっていう言語があるんでそいつを使いましょう。 実装する前に知りたかった。事前のリサーチは大事。

どうでもいいこと

最初はPalisというオシャレな名前を付けて開発していたが、研究室のメンバーが「FudabaのPythonなんだからFuthonにしなよ」と言ったのでそのようになった。

参考

言語実装資料まとめ

YANSに参加してきました

大体上に書いてあるとおりなんですが、そういうわけにもいかないので絞り出しました。

YANSとはNLP若手の会の別名らしく、その名のとおり若い自然言語処理erが集まってワイワイ発表とかをする会です(たぶん)。

まずなんですけれど、これが初参加です。

実は昨年も参加登録して楽しみにしてたんですけど、そのときにインターンしていた研究所でのシンチョクが出ておらず、泣く泣くキャンセルしたという過去があります。

今回は他の学会と日程がかぶってしまったので、2日目から参加しました。

2日目のポスター発表でおもしろいなと思ったのは、機械翻訳向け前編集に有効な書き換えルールに関する調査でした。

機械翻訳の精度向上の手段の一つとして、原文が機械翻訳されやすい文を入力するというものがあります。 ただこの機械翻訳されやすい文というのが何なのか、またどうしたらそういった文を得られるかなどというのが分かっていなかったのですが、この研究はそれを調査しています。

手法自体はすごく地道で、英語、日本語どちらにも精通した被験者に文とそれに対応する機械翻訳結果を見せて、うまく機械翻訳されるまで意味が保たれる範囲で文を書き換えてもらう、というのを繰り返し行うものでした。

これによって得られた改変履歴から、どのような性質を持った文が機械翻訳されやすいかまで分析していてかっこいいなあと思いました。

この改変履歴を使って文の書き換えを自動で行えたりするとさらにおもしろそうだなあ…などと思って見てました。

夜になると旅館の一室が飲み会会場になり、お酒をグビグビ飲みました。結果、誰と飲んだのかすら、うっすらとしか覚えていません。

朝起きたらちゃんと自分の部屋で布団にくるまって寝ていたので本当によかったです。 なにか粗相をしてしまったのではないかとビクビクして一日過ごしましたので、お酒はほどほどにがいいですね…。

3日目にポスター発表を行いました。 僕の発表は自然言語からプログラミング言語ソースコードを生成する手法についての検討で、奨励賞をいただきました。 僕の発表と同じ時間に発表されていたいくつかのおもしろそうな発表が見れなかったのは残念です。

金沢駅でラーメンを食べて帰りました。

「迷子になったら動くな」を検証してみた

今日友達とホームセンターに行ったら迷子になってしまった。

いや、はぐれちゃっただけなんだけど、僕は携帯を持ってなかったし、この年で迷子センターに行くのもなーってことでしばらくウロウロして探した。

そこでふと幼い頃「迷子になったらそこから動くな、探される方がウロウロしてしまうと見つけにくくなるから」とママンに言われたのを思い出したんだけど、これって本当だろうかと思って検証してみた。

コードはgistにある。

動作させるとこんな感じ

迷子になったホームセンターを模したマップを作って、それに対して人を2人だけ用意してランダムに配置し、見つけられるまでに行動した回数をカウントする。

「双方動いた場合」っていうのと「ママンだけが動いた場合」っていう2つの状況を100,000回ずつ試して、その行動回数の分布を見てみる。

このシミュレーションでは、ひとはステップごとに移動と向きを変えることができて、向いている方向に対象の人がいたら見つけたことになる。

結果はこんな感じ。 横軸が試行回数、縦軸がその試行回数で発見できた回数。 試行回数の最高値は16,811なんだけど、双方動いた場合の最高値は1,995なのでこのグラフは全体の一部だけの表示。

f:id:paprikas:20150206034033p:plain

双方動いたときの平均試行回数が131.15286であるのに対し、動かなかったときの平均回数が536.75194。 ちなみに分散はそれぞれ27,592.7712938と692,246.087266。

双方動いたほうが圧倒的に早い!!!!!!!!!!

真面目に考察するなら、「ここにはいなかったからきっとあっちだ」っていう予想をAIがするようになれば、移動しないほうが探索回数の上限が決まるので早いと思う。

無限の大きさを持つホームセンターならどうなるんだろう。

簡単に人の顔に泥を塗る方法

僕は人の顔に泥を塗るのを得意とするのですが、泥を塗るのにも労力がかかるんですよ。 なので常日頃からこの作業を自動化できないかと思っていたので、論文の息抜きにやってみました。

import sys, cv2, random

imagefilename = sys.argv[1]

image = cv2.imread(imagefilename)
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
gray = cv2.equalizeHist(gray)

faceCascade = cv2.CascadeClassifier("./lbpcascade_animeface.xml")
faces = faceCascade.detectMultiScale(gray)

for (x, y, w, h) in faces:
    points = []
    for i in range(1, 8):
        points.append((x+x/4+random.randint(-w/20,w/20), y+i*h/8+random.randint(-h/20,h/20)))
        points.append((x+w-x/4+random.randint(-w/20,w/20), y+i*h/8+random.randint(-h/20,h/20)))
    for i in range(1, len(points)):
        cv2.line(image, points[i-1], points[i], (64, 122, 170), 40)

cv2.imwrite("mud_"+imagefilename, image)

f:id:paprikas:20150204223231j:plain

これであなたも人の顔に泥をぬれる!!!!!!!!

lbpcascade_animeface.xmlはこちらからいただきました。