YAMAGUCHI::weblog

太めの女性の軍団が、本部をグルリと囲んでます。 現在恋人募集中! ポンコツミニチュア三等兵、中井です。

Goの正規表現エンジンを使ってファジング用ツールを書いてみる

Go

はじめに

こんにちは、Go界のコリン・ファースです。この記事はGo Advent Calendar 2014の21日目の記事です。昨日初サバゲーしたら、左手の薬指の爪のどまんなか含め、ピンポイントに左手の薬指3箇所を撃たれて、めっちゃ痛いです。

ところで今年のGo Advent Calendarではすでに2本の記事が正規表現に関する記事が上がっています。

@methane さんの記事の中では「Goの正規表現エンジンが遅い」という話が出ていました。また @ikawaha さんの記事では丁寧にVirtual Machine Approachな正規表現エンジンを実装する方法について書かれています。*1

本エントリでは実際にGoの正規表現エンジンはどういう実装になってるのかを簡単に触れて、そこで使われているVMを再利用してファジング用ツールを書いてみます。

TL;DR

Goの正規表現エンジン内で使っているバイトコードを利用して、ファジングなどで使えそうな正規表現パターンに合致するランダムな文字列を生成するツールを書いてみた。

Goでの正規表現エンジンの実装

Russ Coxによるアプローチ

Goのregexpパッケージの実装に大きくかかわっているRuss Coxは、Goのコアチームであり、RE2の実装をした本人です。そういった経緯からGoでの正規表現エンジンの実装もRE2で使われている手法と同様の、VMを使った実装になっています。すでに @ikawaha さんのエントリの中でも説明されていますが、雑に言えば有限オートマトンの状態をバイトコードの命令に落としこんでやるというものです。

詳しい話はRuss Coxの記事にボリューム満載に書いてあるのでぜひご一読されることをおすすめします。

regexp

そもそもGoのregexpパッケージを使うときはどのようにしていたか、ここでおさらいしてみます。Goの正規表現パッケージでは次の2段階となっています。使用方法のサンプルはドキュメントにあるもので確認してください。

  1. 正規表現パターンをCompileしてregexp.Regexpインスタンスを作成
  2. 作成したRegexpインスタンスでFind系のメソッドを実行する

この順番で見ていけばどうなってるのか分かりそうなので中を細かく見て行きたいところですが、本題に入る前に長くなってしまうので割愛。後日Qiitaにまとめてみます。

1.の段階、つまりCompile()を実行すると、中ではregexp/syntaxパッケージのParse()が呼ばれ、syntax.Regexpインスタンスが作成され、それがVMバイトコードに変換されています。そのバイトコード全体がsyntax.Progです。

2.の段階で、実際にマッチングをはじめると、regexp.doExecute()内で1.で作成されたバイトコードを実行し始めます。このときに、生成されるのが @ikawaha さんのエントリにあったmachine構造体のインスタンスです。

ということで、まとめると、次の二段階がそのままパッケージに反映されていることがわかります。

  1. 正規表現パターンをVMバイトコードにする: regexp/syntax
  2. VMを作成しバイトコードを実行する: regexp

今回は普段あまり触れられることがないであろう1のregexp/syntaxについて見てみます。

regexp/syntax

これは先に挙げたRuss Coxの2番目の記事の方法がそのまま反映された実装になっています。大きく分けて3つの構造体があります。

  • Regexpregexp.Regexpと同じ名前なので要注意。こちらはあくまでパターンをVMの実行形式に変換したまとまり)
  • Prog(VMバイトコード全体を保持する構造体)
  • Inst(各命令を表す構造体)

さきほど、「regexp.Compile()でバイトコードにする」と書いていましたが、その内部ではsyntax.Regexp.Parse()メソッドを呼んで、さらにsyntax.Regexp.Simplify()メソッドを呼んでから実際のCompile()を行っています。このSimplify()によってPCREの複雑なパターンを次の4つだけを使った形式に変換しています。

  • e1e2 (2つの状態が結合している)
  • e1|e2 (2つの状態に分岐している)
  • e1? (空またはe1の状態に分岐している)
  • e1* (e1?と同様の分岐だがループしている)

イメージは先に挙げたRuss Coxの記事の"Converting Regular Expressions to NFAs"の節を読んでください。ためしに次のコードを実行してみましょう。

package main

import (
    "fmt"
    "regexp/syntax"
)

func main() {
    pattern := `aa+bb*[c-z]{1,3}`
    exp, _ := syntax.Parse(pattern, syntax.Perl)
    fmt.Println(exp.Simplify())
}

結果は次の通り

aa+bb*[c-z](?:[c-z][c-z]?)?

このSimplifyしたパターンをバイトコードに変換するのがsyntax.Compile()です。実際にどのような形式になるのか、Compile()関数を呼んで、表示してみましょう。

package main

import (
    "fmt"
    "regexp/syntax"
)

func main() {
    pattern := `aa+bb*[c-z]{1,3}`
    exp, _ := syntax.Parse(pattern, syntax.Perl)
    prog, _ := syntax.Compile(exp.Simplify())
    fmt.Println(prog)
}

次のように表示されました。

  0  fail
  1*    rune1 "a" -> 2
  2 rune1 "a" -> 3
  3 alt -> 2, 4
  4 rune1 "b" -> 6
  5 rune1 "b" -> 6
  6 alt -> 5, 7
  7 rune "cz" -> 11
  8 rune "cz" -> 10
  9 rune "cz" -> 12
 10 alt -> 9, 12
 11 alt -> 8, 12
 12 match

いかにもバイトコードらしい出力が得られました。各命令(状態)に関してはsyntax.InstOpに列挙されています。ドキュメントに各定数が何を表しているかの記載がないので、自分でざっとコード読んでみたり動かした感じだとこんなかんじです。(InstEmptyやInstEmptyMatchらへんはまだそうなるパターンを見てません)

  • InstFail: 失敗状態
  • InstMatch: 受領状態
  • InstAlt: 分岐
  • InstAltMatch: 分岐または受領
  • InstRune1: 指定された1文字で遷移
  • InstRune: 指定された範囲のなかから1文字で遷移
  • InstCapture: 括弧の開始または終了

正規表現のマッチングではこのバイトコードを使って、入力された文字列を先頭から一文字ずつマッチしていくか見ていくわけですが、これを逆に使えば、正規表現のパターンに合致する文字列を生成することができそうです。

regexp/syntaxを使って正規表現パターンに合致する文字列を生成する

というわけで、実験的に作ってみました。

やっていることは非常に簡単で、正規表現のマッチングをするときに行うCompileまでは同じで、そこでできたバイトコードで、分岐が出たらランダムに遷移するというもの。InstRuneの場合は範囲の中から任意の文字をやはりランダムに出力しています。*2

試しに動かしてみます。

package main

import (
    "fmt"
    "regexp/syntax"

    fuzz "github.com/ymotongpoo/fuzzingo"
)

func main() {
    generator, err := fuzz.NewGenerator("aa+bb*[c-z]{1,3}", syntax.Perl)
    if err != nil {
        panic(err)
    }
    for i := 0; i < 10; i++ {
        str, err := generator.Gen()
        if err != nil {
            fmt.Println(i, err)
        } else {
            fmt.Println(i, str)
        }
    }
}

するとこういう結果が出力されます。

0 aabbbje
1 aabbbs
2 aaaaabbbbbr
3 aaabbbqye
4 aaaaabjh
5 aabbeqc
6 aabr
7 aabbho
8 aaaaabbblo
9 aabesh

パターンに対して正しい結果が出力されていますね!いまは非常に乱暴な実装をしていますが、もうちょっとちゃんと実装したらそこそこ使えるツールになるんじゃないでしょうか。

次は @hogedigo さんです。

*1:僕はそこまで詳しく書けないのでぜひ続編の続編の記事を期待しています!

*2:Unicodeの対応はまだちゃんとはしていません

Go Conference 2014 autumn を終えて #gocon

はじめに

こんにちは、Go界のカール・ライナーです。2013年の春から数えて4回目のGo Conferenceですが、今回はこれまでのスケジュールと異なり、午前中のキーノート2本をはじめ、初めて1日通してプレゼンを行う本気のカンファレンススタイルとなりました。

TL;DR

何より僕自身が一番楽しめましたし、運営してくださった方々、また一緒に盛り上げてくれたコミュニティのみなさん、ありがとうございました。また次のGoConが開催されることを楽しみにしています。

f:id:ymotongpoo:20141130101121j:plain

TLとプレゼンテーションまとめ

スライドへのリンクがないものは公開され次第追って追加します。

TL

Go Conference 2014 autumn - Togetterまとめ

キーノート

プレゼンテーション

Lightning Talk

Rob Pikeをお呼びすることになった経緯とか

今回、僕は個人としての立場と所属する会社での立場を明確にするために、本カンファレンスの運営を@tenntennや@jxck_を始めとするこれまで運営をこれまで支えてくれてきたコミュニティの方々にお願いし、僕はコミュニティをサポートする立場に徹しました。 *1

これまでなんとなく半年ごとの開催をしてきましたが、今回の秋開催を期待する声を9月頃を境に次第にいただくようになりました。ただ上記のような考えがありどうしようと迷っていたのですが、 GoCart に一緒に行ったみなさんが意欲的に手を挙げてくださったので、僕はキーノートスピーカーの依頼にとどまり、一歩下がったところで支援する形にさせてもらいました。

折角ここまで盛り上がっているので、ダメ元でGoの父であるRob Pikeにメールを送ったところ、「日程的に厳しいかもしれないけれど*2出来る限り参加したい」とおっしゃってくださり、過去のGoConでキーノートをしてくれたAndrew (@enneff) やBrad (@bradfitz) からの後押しもあってキーノートをしてくださる運びになりました。Robが日本に来るのは10年ぶりということで、本当に貴重な機会となりました。これも過去のGoConがキーノートスピーカーにとっても有意義であったということの証拠だと思います。*3

また、折角日本での開催だからということで、おそらく日本でGoでの開発の知見を最も持っているであろう鵜飼さんが快くキーノートを引き受けてくださったのも大きかったです。まったく事前の打ち合わせなどなかったにもかかわらず、お二人のキーノートが「Goらしく書くことにおいて単純さがいかに大事か」という話に収束していたのは、納得の行く結果でした。

運営のみなさまお疲れ様でした

Robの来日が決まったのが10月末なので、開催まで1ヶ月の時点で会場探し始めもろもろの準備を始めることになりました。その意味では会場提供や当日運営の申し出をしてくださった @deeeet さんはじめとする楽天の方々には本当にお世話になりました。またイベントのTシャツを作ってくださった @nuki_pon さん、毎回運営を手伝ってくださっている @manji0112 さん、GoCartで話が出てから関わってくれた @ryusen33 さんと @zoncoen さん、直近1ヶ月にnodeのイベントとHTTP2のイベントを抱えていた @jxck_ さん、そしてオリジナルステッカーやTシャツのデザインの元になるGopherイラストやメインで頑張ってくれた @tenntenn さんは本当にお疲れ様でした。

とても楽しかったです

TLを追っていても参加した皆さんが楽しんでいたのが伝わってきましたし、なによりRob本人が非常に楽しんでくださっていたのが印象的でした。Robは日本語がほとんどわからないのですが、Google翻訳を駆使してTLを読みながら、会場内外含めた #gocon の盛り上がりを感じ、ときにおもしろいツイートを見かけては子供のような無邪気な表情で笑っていたのが何よりの証拠でしょう。(一日中椅子に座っていたので「おしりが痛い」旨のツイートがたまにあったのですが、それが "Ass hurts" のように翻訳されていて、それを見る度に爆笑していました)

また運営を手伝ってくださった方向けにTシャツを用意していったのですが、懇親会後にはお店の前でジャンケン大会での争奪戦となり、Rob Pike本人がジャンケンを盛り上げてくださっていました。

f:id:ymotongpoo:20141130204123j:plain

運営コストに関して

ちゃんと書き残すことが少ないので、一応僕の考えだけここに書いておきます。今回GoConではライブ配信も通訳もありませんでした。理由は単純で運営が大変になるのと金がないからです。僕は過去にYouTubeのライブ配信の担当をしていたので安定してライブ配信を行うことの大変さはわかっていました。*4なので、少人数運営*5では賄えないと判断しました。

また今回も前回までのGoConと変わらず、英語でのセッションがそれなりにあったものの、通訳は入れませんでした。理由は金がかかるからとめんどくさいからです。同時通訳は想像しているよりもずっと高いものです。技術系の単語を理解しつつ同時通訳ができる通訳者を雇うだけでも大変ですし、同時通訳をするとなると専用の設備を入れなければなりません。有償のカンファレンスならいざしらず、無償でボランティアベースで行っているイベントではまず無理です。また英語がわかる参加者がボランティアベースで逐次通訳すれば良いだろうと思う人がいるかもしれませんが、逐次通訳を行うと単純にプレゼンテーションの時間が半減します。また通訳者は非常に疲れます。

これらを踏まえて、上記のようなリクエストを実現するためには人的・金銭的なサポートが必要になります。遠方の方や抽選に漏れた方への救済などはなるべくしたいとは思いましたが、そもそも運営する側が継続不能なコストを被るとなっては本末転倒なので、もし上記を実現したいとなったら、ぜひ手を挙げてもらえたらと思います。

次回以降

次回がどうなるかは僕はわかりません。ただ、2年前に始めた時のGoConではGoをプロダクションで使っている人がまったくいない状態だったのが、今回はすでに実戦投入を終えてからの知見に関するプレゼンテーションが多く見られるようになり、Goのコミュニティそのものの成熟と盛り上がりを感じることができたので、これからもGoConという形にかぎらず盛り上がっていってほしいなあと感じています。もし「GoConの運営を盛り上げたい」という方がいらしたら、ぜひ手を挙げてください。一緒に楽しんでいきましょう。

*1:もちろん僕もコミュニティの人間だという思いは誰よりあると思いますが、公式に支援するという立場を取りたかったという意味で敢えて分けるような書き方をしています

*2:いまになればわかりますがGo 1.4のリリースとGitHubへの移行を含めた非常に過密なスケジュールの中講演することになる

*3:実際、Goの父であるというだけでなく、これまでのITの歴史に大きく貢献してきたRob Pikeには毎週3、4本の講演依頼が来るそうですが、ほとんどは普段の業務や生活との兼ね合いからお断りしているそうなので、GoConを有意義だと思っていてくださったようです。

*4:配信そのもののコストと発表に際しての手続きの有無の確認などは想像しているよりもかかります

*5:それでも今回は楽天の皆様始め多くの人員を割くこととなりました

C言語でプログラミングする際の覚書(Notes on Programming in C)

はじめに

こんにちは、Go界のシャールト・コプリーです。気がついたら最後のエントリから3ヶ月も経ってました。

Goを始めると「なんでこういう書き方になってるんだろう」とか、「そもそもなんでこういう仕様になってるんだろう」とか思うことがちらほらあると思います。これは大いにGoの作者の一人であるRob Pike氏の思想に依るところがあるのが見受けられます。彼のプログラムに対する考え方が25年前に公開され「Pike Style」として知られていますが、いまもその考え方は大きくは変わっていないと思われます。せっかくなので翻訳しました。本文はC言語に関する文章ですがその本質は言語に依らないものだと思います。

(追記)25年前なのでコンパイラの動作に依存する部分(includeに関する記述)などは古い部分もありますが、プログラミングスタイルに関する部分は現代にも通じるところがあると思います。

(追記2)幾つか誤訳をご指摘いただけたので修正いたしました。コメントに感謝しています。

(追記3)僕の役はひどいのでこちらを読みましょう。

誤訳箇所の一覧です。

C言語でプログラミングする際の覚書

Rob Pike 1989年2月21日

Copyright (C) 2003, Lucent Technologies Inc. and others. All Rights Reserved.

まえがき

KernighanとPlaugerの “The Elements of Programming Style” (「プログラム書法」木村泉訳)は重要で間違いなく影響力のある書籍でした。しかし、ときに私はその簡潔なルールが本来意図した哲学の簡潔な表現としてではなく、良いスタイルにするためのクックブック的な手法として捉えられていると感じます。もし、かの書籍が変数名は意味があるように選ばれるべきだと主張するのであれば、変数名はその用途を説明したエッセイになっている方が良いということにならないでしょうか。 MaximumValueUntilOverflowmaxval よりも良い変数名でしょうか。私はそうは思いません。

従うべきは、厳しいルールを与えることではなく、プログラムを書く際の明確さの哲学を全体として助長するような短いエッセイです。みなさんにこれらすべてに同意してもらいたいわけではありません。なぜならこれは意見であり、意見は時間とともに変化するものだからです。しかし、私の意見は頭のなかにしばらくあったものをまとめたものであり、長らく文章として公開してきませんでした。またこれらは私の多くの経験を踏まえたものです。そのため、プログラムの細かな部分に関する計画方法の理解に役立てば幸いです。(これまでプログラム全体の計画に関しての良い文章は読んだことがありますが、それらはこの文章で触れる内容の一部となります)もしいまから紹介するものを特異だと感じたのであれば、それはそれで結構です。また同意できないとしても、それも結構です。しかし、なぜあなたがなぜ同意できないのかを考えるきっかけになったのであれば、より良いことでしょう。どのような状況においても、私がそういったからという理由で私が言ったやり方で書くべきではありません。あなたがそのプログラムで実現したいものを最も良く記述できると考える方法でプログラムしてください。そしてそれを一貫し容赦することなく行ってください。

あなたのコメントをお待ちしています。

表示の問題

プログラムは一種の出版です。プログラムはプログラマや他のプログラマ(おそらく数日後、数週間後、数年後のあなた自身)、そして最終的にはマシンに読まれることを前提としています。マシンはそのプログラムがどれほど美しいかは気にしません。コンパイルできれば、それで幸せなのです。しかし、人間は気にします。そして気にすべきです。ときに気にし過ぎます。たとえば、pretty printerは機械的にプログラムの重要でない部分も強調するような美しい出力をします。これは、英語の文章内にある前置詞 すべて太字 するの 同様 です 。しかしながら多くの人々がプログラムはAlgol-68 Reportのような見た目(システムによってはそのスタイルで編集することを強制します)であるべきと考えますが、明瞭なプログラムはそのような見た目で成されるものではなく、また悪いプログラムであれば明瞭にしても滑稽になるだけです。

もちろん表示に関する一貫した規約は見た目を明瞭にするためには重要です。インデントは最もよく知られ最も有用な例です。しかし、印字がプログラムの意図を曖昧なものにしてしまうのであれば、がやり過ぎだったということです。したがって、たとえあなたが昔ながらのタイプライターのような飾り気のない表示にこだわっているのだとしても、表示における愚かさを意識しましょう。余計な飾りをやめましょう。たとえばコメントは短く、バナーは無くしましょう。プログラム内で言うべきことを、綺麗に一貫して言いましょう。それから先に進みましょう。

変数名

そうですね、変数名です。変数名の長さは美徳ではありません。表現の簡潔さが大事なのです。滅多に使われないグローバル変数は長い名前にしてもいいでしょう。たとえば maxphysaddr といった具合です。ループ内のすべての行に出現する配列のインデックスは i 以上に凝った名前を付ける必要はないでしょう。たとえば indexelementnumber といった変数名はタイプ量(あるいはエディタ内で呼ばれる回数)が増え、計算の内容を不明瞭にします。変数名が巨大な場合、何が起きているかを把握するのが難しくなります。これは表示に関する問題の一部です。

for(i=0 to 100)
    array[i]=0

というコードと

for(elementnumber=0 to 100)
    array[elementnumber]=0;

というコードを見比べてみましょう。

現実の例では問題はもっと速く明らかになります。インデックスはただの注記なので、そのように扱いましょう。

ポインタもまた気が利いた注記が必要です。どの np が "node pointer" を意味しているかがすぐに分かる命名規則を一貫して使っていれば、 npnodepointer という名前と同じくらい読みやすいものになります。

プログラムの可読性に関していえば、命名において一貫性は重要です。ある変数に maxphysaddr と名づけたら、同様の変数に lowestaddress という名前をつけてはいけません。

最後に、私は最短の名前ではなく最も情報量がある名前を好み、ほかは文脈に任せる方法を好んでいます。たとえば、グローバル変数は典型的には使われる際にはほとんど文脈がないので、名前は比較的それだけで内容がわかるものである必要があります。したがって、グローバル変数名には maxpysaddrMaximumPhysicalAddress ではありません)という名前をつけ、ローカル変数には NodePointer ではなく np のような名前をつけます。これは好みによるところが大きいですが、その好みというのは明瞭さに関係するものです。

名前に大文字を入れるのも避けています。散文調の文章を見慣れた私には、大文字が文章の中に入ると不格好に感じられ快適に読めないのです。大文字は悪い印刷のように目障りなのです。

ポインタの使用

C言語はポインタでなんでも指せるという点で特異です。ポインタは賢い道具で、他の同様の道具のように、上手に使えば楽しく生産的になりえるものの、使い方を間違えると大きな損害を与えます。(この文章を書く数日前に木工彫刻刀で親指を怪我したばかりです。)ポインタは危険すぎる、あるいは汚すぎると考えられ、学術会では評判が良くありません。しかし私はポインタは強力な 注記 であると考えます。つまり、ポインタは明瞭な表現をする手助けをしてくれるという意味です。

次の状況を考えてみてください。あるオブジェクトに対するポインタがあるとき、それはまさにそのオブジェクトに対する名前であり、他のなにものでもありません。些細なことのように思えるかもしれませんが、次の2つの表現を見てください。

np
node[i]

最初のポインタはノードを指していて、2番目は(たとえば)同じノードを評価しています。しかし、2番目の形式は式です。単純ではありません。これを理解するためには node が何か、 i が何かを理解し、そして nodei がどのような関係にあるか(おそらく明記されていない)を周りのプログラムから理解しなければなりません。独立した式それだけでは inode の正しいインデックスかはわからないですし、ましてそれが私達がほしい要素のインデックスかはわかりません。もし ijk のすべてがノードの配列のインデックスだった場合、容易にうっかりと間違えてしまいます。特にサブルーチンに渡すときは間違いを起こしやすく、コンパイラでは避けようがありません。ポインタであれば1つのものを指しています。配列とインデックスは受け取ったサブルーチン側がお互い関係があるものとして信用しなければなりません。

オブジェクトに評価する式は、オブジェクトのアドレスよりも本質的により判断しづらく間違いを起こしやすいものです。ポインタを正しく使うことでコードを簡潔にできます。

parent->link[i].type

lp->type

を見比べてください。

もし次の要素の型が必要な場合は

parent->link[++i].type

よりも

(++lp)->type

のほうが見やすいでしょう。

i は値が進みますが、それ以外はなにも変化がありません。ポインタであれば進めるのは1つのものだけです。

ここでも表示の問題が出てきます。ポインタを使って構造を読み込むのは式を読むよりも理解が楽です。必要なインクの量は少なく、コンパイラやコンピュータが展開する労力も減ります。関連した問題として、ポインタの型が正しく使われているかに影響を与えているかというものがあります。これでコンパイル時に配列のインデックスが適切で無い旨のエラー検出が可能になります。また、そのオブジェクトが構造体の場合はタグとフィールドは型を思い出させてくれます。つまり

np->left

はそれぞれが何を挿すかを思い出させるのに十分です。これがもしインデックスが指定された配列であれば、配列名はきちんと選ばれた名前で、表現は長くなります。

node[i].left

再度になりますが、余計な文字は表現が大きくなるにつれて苛立たしくなります。

ルールとして、もし同様の表現を含むコード、たとえばデータ構造の要素を評価するような複雑なデータ構造があった場合、思慮深くポインタを使えばすっきりとできます。

if(goleft)
     p->left=p->right->left;
else
     p->right=p->left->right;

p の複合的な使い方をしているこのコードが何をしているかを考えてみましょう。時には一時変数(この場合は p )を使用したり、計算の本質を抜き出すマクロを使用する価値があります。

プロシージャ名

プロシージャ名はそれが何をするかを反映すべきです。つまり関数名はそれが何を 返すか を反映すべきです。関数は式の中で使われ、しばしば if の中で使われます。したがって適切に読む必要があります。

if(checksize(x))

という記述は役に立ちません。なぜならchecksize関数がエラーの時にtrueを返すのか、エラーでない時にtrueを返すのかが推測できないからです。代わりに

if(validsize(x))

とすれば要点が明らかになり、将来同じ関数を使うときの間違いが起こりにくくなるでしょう。

コメント

慎重に、経験と判断をもって書く必要があります。私は、いくつかの理由から、コメントを極力書かないようにしています。まず、コードがきれいで、良い型名や変数名を使っている場合、コードそれ自身が内容を説明しているはずです。次に、コメントはコンパイラにはチェックされないので、コメントが正しいという保証はありません。特にコードが変更されたあとはそうです。誤解を招くコメントは非常に紛らわしいものです。最後に、表示の問題です。コメントはコードを散乱させてしまいます。

しかし私も時々コメントを書きます。ほとんどもっぱらその後に何が続くかを説明するために書きます。例えば、グローバル変数の使い方とその型の紹介(大きなプログラムではいつもコメントするものの一つ)、通常の使い方をしていないプロシージャや非常に重要なプロシージャの紹介、あるいは大きな計算をする際の区切りなどです。

悪いコメントの例としては次のようなものがあります。

i=i+1; /* Add one to i */

さらに悪いコメントの例は

/**********************************
*                                 *
*           Add one to i          *
*                                 *
**********************************/

i=i+1;

いまこの例を笑ってはいけません。実際にこのようなコードに出くわしたらはじめてそこで笑いましょう。

複雑さ

たいていのプログラムは複雑過ぎます。つまり、問題を効率的に解決するために必要な複雑さよりも複雑なのです。なぜでしょう。多くの場合、それは設計の悪さに起因しますが、ここではその話は大きすぎるテーマなので触れません。しかし、プログラムはしばしば細かなレベルでも複雑で、ここではその点についてお話します。

ルール1 プログラムのどこに時間がかかる場所があるかはわからない。ボトルネックは思わぬ場所で起きる。したがって、どこがボトルネックかわかるまでは、合理的な判断なしに余計な勘ぐりをしたり高速化のためのハックをするのはやめよう。

ルール2 計測しよう。計測するまでは高速化のためのチューニングはやめよう。さらに、高速化のためだとしても、プログラムの残りの部分を圧倒するような場合でない限り、チューニングはやめよう。

ルール3 n が小さい時にはしゃれたアルゴリズムは遅く、そして通常 n は小さい。しゃれたアルゴリズムではその影響が現れるコンスタントな値は大きい。 n が頻繁に大きくなるとわかるまでは、手が込んだアルゴリズムは使わないようにしよう。(たとえ n が大きくなるとしても、まずはルール2を考えよう)たとえば、日常的な問題では二分木は常にスプレー木よりも速い。

ルール4 しゃれたアルゴリズムは単純なアルゴリズムよりもバグを起こしやすい。そして実装がずっと難しい。単純なアルゴリズムと単純なデータ構造を使おう。

次に挙げるものはほぼすべての実用的な問題を解決するデータ構造の一覧です。

  • 配列
  • 連結リスト
  • ハッシュテーブル
  • 二分木

もちろん、これらのデータ構造を組み合わせたデータ構造にすることも配慮しなければいけません。たとえば、シンボルテーブルは文字型の配列の連結リストを含んだハッシュテーブルとして実装されているでしょう。

ルール5 データが支配する。正しいデータ構造を選び、物事をうまくまとめれば、それを使うアルゴリズムは自明である。アルゴリズムではなく、データ構造がプログラムの中心である。(詳しくは「人月の神話」を参照のこと)

ルール6 ルール6はない。

データでプログラミングする

アルゴリズム、つまりアルゴリズムの細かな部分は、しばしばデータという簡潔で、効率的で、表現豊かな形に記号化されます。それは、たとえば、多くのif文という形ではありません。その理由は、もし手元にある 複雑さ が独立した細かな部分の組み合わせによるものなのであれば、それは 記号化できるから です。古典的な例で言えば、表のパースです。これはプログラミング言語の文法を、定形のかなり単純なコード片によって説明可能な形式に記号化することです。特にこのような問題に取り組むときには有限状態機械が採用されていますが、ある抽象的な入力を「パース」して一連の独立した「振る舞い」に変換するようなあらゆるプログラムは、ほとんどが生産的な形としてデータ駆動のアルゴリズムになります。

おそらくこのような設計の最も魅力的な側面は、ときどき表が、古典的な例ではパーサジェネレータといった、他のプログラムに生成されることです。もっと現実的な例では、オペレーションシステムが、I/Oのリクエストとそれに対する適切なデバイスドライバの組み合わせを持ったひとまとまりの表によって動いているとした場合、システムはマシンに接続されたある特定のデバイスの説明を読み込み、対応する表を表示するようなプログラムによって「構成される」でしょう。

データ駆動プログラムが一般的でない理由の一つは、少なくとも初心者においては、Pascalによる圧政でしょう。Pascalは、その創始者のように、コードとデータの確固たる分離を信条としています。したがって(少なくとも本来の形では)初期化されたデータを作ることはできません。このことはチューリングフォン・ノイマンの理論の前にはたち消えてしまいます。この理論はストアドプログラム方式のコンピュータの基本原理を定義しています。コードとデータは同じものです。あるいは少なくとも同じになりえます。それ以外にどうやってコンパイラが動作するかを説明できるでしょうか。(関数型プログラミング言語でもI/Oにおいて同様の問題を抱えています。)

関数ポインタ

Pascalの圧政は、初心者が関数ポインタを使わない、という状況ももたらしています。(Pascalでは関数を値にもった変数を持つことができません。)複雑さを記号化するために関数ポインタを使うことにはいくつか面白い特性があります。

複雑さのいくつかは参照先のルーチンに渡されます。そのルーチンはいくつかの標準的な規約に従わなければいけません。そのルーチンは同じ呼び出し方をされたひとまとまりのルーチンの一つです。しかしそれ以上にそのルーチンは自分がすべきことしかしません。複雑さが 分散された のです。

この規約という考え方があり、そこでは似たような使われ方をする関数はすべて似たような振る舞いをしなければいけなません。これによって、ドキュメントが書きやすくなり、テストがしやすくなり、コードを成長しやすくし、さらにはプログラムをネットワーク越しに分散させて稼働させやすくなります。この規約はリモートプロシージャコールとして記号化されます。

私は、関数ポインタを明確な形でつかうことがオブジェクト指向プログラミングの心であると、主張します。あるデータに対してひとまとまりの操作を行いたい、かつ、それらの操作に対してひとまとまりのデータ型を返したい場合、そうプログラムする簡単な方法は各型に対して関数ポインタをまとめることです。これは、一言で言えば、クラスとメソッドを定義することです。もちろん、オブジェクト指向言語は優れた構文、派生型などといった、より多くのものを提供してくれます。しかし、概念的にはオブジェクト指向言語は先のものにほんの少しのおまけを提供してくれるだけです。

データ駆動プログラムと関数ポインタを組み合わせが、プログラムの驚くほど表現豊かな書き方へと導いてくれます。私の経験から、その書き方はしばしば嬉しい喜びももたらしてくれます。たとえ特別なオブジェクト指向言語がなくても、余計な手間をかけずに、オブジェクト指向の90%の恩恵を授かることができ、結果をより管理することができるようになります。より高度な次元の実装方法を推奨することはできません。私がこのようなやり方で書いてきたすべてのプログラムは、その後の多くの開発のあとも快適に動作しています。規律が少ない手法で開発されたものよりもずっと良く動作しています。以上です。この手法が強制する規律は、長い目で見て大きな利益をもたらします。

インクルードファイル

単純なルールです。インクルードファイルは決してインクルードファイルをインクルードすべきではありません。代わりに(コメントや暗黙的に)まずどのファイルがインクルードされるべきか宣言した場合、どのファイルをインクルードするかという問題はユーザ(プログラマ)側に押し付けられますが、ある意味では管理がしやすくなり、ビルド時に複数のインクルードを避けることができます。複数のインクルードはシステムプログラミングでの悩みの種です。一つのCのソースファイルをコンパイルするのに5回以上もインクルードされたファイルがあることは珍しくありません。Unix/usr/include/sys はこの点でひどいものです。

1つのファイルが2度呼ばれないように #ifdef を駆使する方法がありますが、普通は間違った結果となります。 #ifdef はインクルードされるファイルの中にあり、インクルードする側にはありません。その結果、しばしば何千行もの不要なコードが字句解析器に渡されることとなり、これは(良いコンパイラでは)最もコストが高いフェーズとなってしまいます。

単純なルールに従いましょう。

本文に出てきた書籍

プログラム書法 第2版

プログラム書法 第2版

人月の神話【新装版】

人月の神話【新装版】

「すごいErlangゆかいに学ぼう! 」という本が出版されました #すごいE本

はじめに

こんにちは、Erlang界のCBR400Rです。このたび、私の2冊めの翻訳書籍、印刷されたものとしては初となる書籍が「すごいErlangゆかいに学ぼう!」というタイトルでオーム社より出版されました。本日より書店ならびにAmazonはじめとするオンラインストアでご購入頂けます。

すごいErlangゆかいに学ぼう!

すごいErlangゆかいに学ぼう!

いま手元にある本の厚さや重さを実際に感じて、電子書籍では味わえなかった充実感、達成感を得ています。これの実現に至るまでに多くの方々にお世話になり、その方々のご協力なしには出版なんて到底ありえませんでした。本当に感謝しています。ありがとうございました。

「すごいErlangゆかいに学ぼう!」はどんな本なのか

これはFred Hebertの書いた"Learn You Some Erlang for great good!"の日本語訳書籍です。著者のFredはこの本の出版を評されて、2012年のErlang User of the Yearに選ばれています。Erlang公式コミュニティからも、推薦の一冊として紹介されている、という書籍です。

Learn You Some Erlang for Great Good!: A Beginner's Guide

Learn You Some Erlang for Great Good!: A Beginner's Guide

タイトルに「Erlang」と入っているので、当然プログラミング言語Erlangに関する本です。ただその内容の量、質が尋常じゃないんです、ほんとに。内容をいくつかの章ごとに大きく分けると、おおよそ次のような構成になっています。

  • 1-9章: Erlangの基礎と関数プログラミングの初歩について
  • 10-13章: 並行プログラミングについて
  • 14-17章: OTPの基礎
  • 18-25章: OTPアプリケーションについて
  • 26-29章: 分散アプリケーションについて
  • 30章と残り: 型と新仕様について

Erlangの本なので1-9章でErlangの文法の習得をするのは当たり前なのですが、それ以降の章はErlangを習得しようとする方のみならず、並行プログラミングや分散アプリケーションを実現する上で一体どのような機構を用意しなければいけないのかを理解したい他言語の方にも十分有用な内容となっています。OTPという「フレームワーク」がいかに先に述べたようなアプリケーションを容易にかつ堅牢に実現しているかを理解する上で、本書の構成が非常に優れていると私個人は思っています。その理由はこの本がOTPありきで進まないからです。まずかならず手持ちの機能だけで頑張ってアプリケーションを実装してみて、いよいよ実装が複雑になりお手上げとなったところでOTPを紹介し、その有用性を実感できる形になっています。一つ一つ確実にその有用性を理解することで、Erlangに限らず他の言語でも同様のアプリケーションを実装する際には似たような機構が必要になることを直感的に理解できるのではないでしょうか。このような内容を自分で手を動かしながら理解できる日本語書籍は、自分で言うのもなんですが、他に知りません。

また理解が進めば進むほど、OTPの強力さを思い知らされることになります。普通の言語では標準ライブラリ等はあくまで言語に付随するもので、とりだてて別称することはありません。しかしErlangではわざわざErlang/OTPと標準ライブラリであるOTPを併記します。個人的にはこの辺りにOTPの重要性が垣間見えると思っています。つまりOTPというフレームワークがあるからこそ、Erlangが存在しうる、という意志の表れではないでしょうか。

「新しい言語を学ぶ」というだけではなく「新しい仕組みを知る」という点でもおすすめです。ぜひご一読下さい。また本書は原著版にもない、最新のR17.0から導入されたマップについてのまるまる1章追加されています。R17.0対応している日本語のErlang書籍は本書だけです!

翻訳の思い出

この翻訳書籍を出版するきっかけは3年半前までさかのぼります。*1 訳者序文にもありますが、まだ僕が転職する前に、レビュアーの @voluntas から原著のウェブ版(当時はまだウェブ版しかなかった)を紹介されたのがきっかけでした。そして、Erlangという、よくわからないけどなにやら並行・分散プログラミングが非常に得意でネットワークサーバの作成にすこぶる向いている面白い言語がある、と前々から聞いていたので、勉強がてら翻訳を開始しました。

始めのほうは順調に翻訳を行っていたものの、後半になるにつれどんどん1章ごとの分量が増え、さらに内容も複雑化して、非常に苦労していたことを覚えています。その後、途中で別のことをしていたり、仕事が忙しくなったりして翻訳が滞り、ウェブ版の原著が30章まで完成しいよいよ印刷版が出るという噂が出始めた頃には、まだ22章までしか翻訳が終わっていませんでした。その後しばらくして転職をし、そろそろ翻訳を再開しようかと思っていた頃に、オーム社の鹿野さんと高尾さんに今回の翻訳書籍の出版のお話を頂きました。

とりあえずウェブ版原著の翻訳を終えることが肝心ということで、なんとかウェブ版原著の翻訳を終えました。その後、原著の書籍版が出版され、オーム社さんにウェブ版と書籍版の突き合わせ原稿を作成してらっているうちに、またバタバタしだしてしまい、翻訳が滞ってしまい、結局今年の頭から書籍版の翻訳を再開。とまあ、書籍版自体の翻訳を開始するまでがすでにウェブ版の翻訳から3年経っているという状況だったのですが、書籍版の翻訳が始まってからは、多くのレビュアーの方に的確なレビューをいただき、短い期間で非常に多くの改善を行うことが出来ました。現在公開されているウェブ版の日本語訳と比較すると、恥ずかしくてウェブ版を取り下げたいレベルです。

自分の中で4年間弱常に頭の片隅にあったモヤモヤが、こうやって無事に出版にこぎつけた今日ようやく消えた気がします。あー、長かった。

オーム社での翻訳体制の話

ウェブ版の翻訳は個人のBitbucketのhgレポジトリ、後半になってGitHubのprivateレポジトリ、そして書籍版の翻訳は最初はsvn+tracを使い、2013年11月からはオーム社GitHubのプライベートレポジトリに移行しました。このように何度かレポジトリの引越しをして出版まで来たわけですが、最後のGitHubでの運用が一番個人的に楽でした。運用方法は特に明文化されていたわけでなく、レビュアーに自由にチケットを切っていただきながら、ラベルやマイルストーンを適宜追加していったわけですが、いま振り返ると次のような方法で翻訳するのが楽だったなと思いました。

編集原稿

鹿野さんが用意して下さったのですが、拡張HTMLのようなマークアップ原稿でした。基本HTMLなのですが、原稿には日本語と英語原文の両方があり、日本語の部分のみ編集。たとえばつぎのような感じです。

<p lang="en">Learn You Some Erlang for great good!</p>
<p lang="ja">すごいErlangゆかいに学ぼう!</p>

このlang="ja"の部分だけど編集する形。GitHubへpushするとCIが回され、そこでLaTeX化の後にPDFになり、毎日夜中に最終版のPDFが共有のWebDAVサーバに置かれる形でした。

この原稿がよかったのは、CSSがきちんと用意されていたので、ローカルでもブラウザで簡単に読めたこと、そしてHTML、PDFという異なる形式でレビューできたので間違いを拾いやすかったことです。逆になれないと大変だったのは、HTMLを直接さわる感じなので、最初はタグがチラチラ目障りに感じたこと、そして < などの特殊記号のエスケープがたまに必要だったことぐらいです。自分の好きなエディタで気軽に編集できたのは助かりました。

ブランチ戦略

基本masterブランチ1本で、Pull Requestがある場合にのみブランチを切ってもらいます。ソースコードほど厳密にfeatureがあるわけでもないので、ブランチ名はレビュアー名とか、適当に分かる名前をつけてもらいました。mergeに関しては翻訳者である自分と編集者の鹿野さんが行うのみ。自然言語のmergeは時折うまくいかないことがあり、mergeツールに騙されたことが何度かありましたが、ほぼ問題なく運用できていました。

レビューのissueの切り方

それぞれにまちまちで、それぞれにわかりやすい点はあったのですが、個人的に一番対応しやすかったのは次のようなissue。

  • タイトル: <章番号> <該当箇所 or issue概要>
  • 本文: <GitHub上の該当箇所への行リンク> <issue内容>

GitHubでは行へのリンクが可能なので、ブラウザ上で読むときにリンクが該当箇所のリンクがあるのは非常に便利。さらに、行リンク内に行番号があるので、実際に手元で編集を行う上でも行リンクは便利でした。編集後に行番号がずれることはありましたが、基本的に10行もずれないのでこの方法でうまく行きました。

編集コメントの扱い

最初は僕と編集の方だけでやりとしていたので特にissueとか上げず タグでやりとしをしていました。が、レビューの段になって、編集コメントで質問されている内容が後々まで放置されてしまい、最後で慌てて回収するという事がありました。組版や作業報告以外は編集コメントではなく、issueに上げたほうが皆の目が入るし幸せかなと思いました。(もしくは両方に記載する)

おわりに

訳者序文でも書いていますが、本書の出版はレビュアーの方々のご協力なしには到底ありえませんでした。私がErlangを業務で書いているわけではない中で、実際にErlangで、しかも先端で仕事をされている方々からの実務経験に基づいた細かなアドバイスや、他の関数型言語のエキスパートとしての側面からの指摘、さらには他言語の経験がありつつErlang初学者としての視点からのフィードバッグなど、果ては私の拙い日本語の修正など、多くのレビューを頂きました。この場を借りてレビュアーの皆様に改めて感謝いたします。

書籍版レビュアーのみなさま(五十音順)

  • @ajiyoshi さん
  • 幾田雅仁さん (@cooldaemon)
  • 上西康太さん (@kuenishi)
  • 篠原俊一さん (@itawasa)
  • 渋川よしきさん (@shibu)
  • 島崎清山さん (@seizans)
  • 中居良介さん (@voluntas)
  • 廣江 深さん (@hiroe_orz17)
  • 山本和彦さん (@kazu_yamamoto)
  • 力武健次さん (@jj1bdx)
  • 若山史郎さん (@r_rudi)

Special Thanks

  • 古瀬 淳さん (@camloeba) :型について

オーム社

  • 鹿野桂一郎さん (@golden_lucky)
  • 高尾智絵さん

皆様からのレビュー(随時追加)

*1:原著者のFredに翻訳の許可をもらうメールを送ったのが2010年12月22日でした。

Go Conference 2014 springを開催しました #gocon

はじめに

こんにちは、Go界のユアン・マクレガーです。5月最終日にリクルートライフスタイルさんの会場をお借りしてGo Conference 2014 springを開催してきました。

前回は「新幹線を使って参加してくれた人もいました」と書いていましたが、今回は僕が呼んだBrad Fitzpatrik以外に、国内でも飛行機を使って福岡から来て発表してくれた @monochromegane や、なんとシドニーからDave Cheneyが参加してくれたりと、本当に規模の大きいイベントになってきたなと実感しています。

発表者スライド(発表順)

「あとで」となっているものは公開され次第追加します。

togetter

参加できなかった方もこちらにまとめがありますので、眺めつつ資料を見ていただければと思います。

まとめてくださった岩田さん(@qt_luigi)ありがとうございました!

運営・スタッフの皆様ありがとうございました!

今回のGoConは開催を決めてから当日までがほとんど日にちがなく、かつ自分がかなり立て込んでいたこともあって、正直自分の中では開催が危ぶまれていたのですが、蓋を開けてみれば、会場提供をしてくださったリクルートライフスタイルの荒川さんを始めとする皆様のご協力や、スタッフ参加で申し込んでくださった皆様のお陰で、非常にスムーズな運営が出来ました。

懇親会に関しても、@Jxckさんが色々と手配してくれたこともあり、会場と同じ建物の素晴らしい眺めのカフェで行うことが出来ました。

チュートリアルに関しても当日に無茶ぶりをしてくれたにも関わらず、快く引き受けてくれて、多くの参加者が楽しかったと言ってくれるようなチュートリアルをしてくれた@tenntennさん、本当に助かりました。

次回以降

何も決まっていませんが、もうちょっとコミュニティベースの開催にできたらいいなと思っています。また国内外の他のGoコミュニティとももっと交流を深められるような会にできればいいなとも思っています。