Blog Dice

AWKGo, an AWK-to-Go compiler

Ben Hoyt

AWKGo、AWKからGoへのコンパイラ

原文は Ben Hoyt により に公開されました。 このブログを購読する

私はかなりのオタクで、自分で自分をnerd-snipedしてしまった。

Goで書かれたAWKインタプリタGoAWKの作者である私は、ある日ふと、AWKプログラムをGoのコードに変換するのはどれくらい難しいのだろうかと考えた。そんなに難しくないだろう？ 試してみることにした。

少なくとも自分のコンパイラがサポートするAWKのサブセットに関しては、特に難しいこともなく、GoAWKのパーサーや多くのテストを再利用できた。私のクリエイティブなネーミングセンスを披露すると、このコンパイラをAWKGoと名付けた。

この記事の残りでは、AWKGoが何をするものなのか、どのように動くのか、作成やテストの過程で学んだ興味深いことのいくつかについて説明し、出力例をいくつか紹介する。さらに、生成されたコードのパフォーマンスについても簡単に見ていく。

GitHubでAWKGoのソースを見ることができる。

対応するサブセット

AWKGoはAWKの有用なサブセットをサポートしているが、いくつかの点でAWKのセマンティクスから逸脱している。たいていの小さなAWKスクリプトは問題なく動くが、一部は軽微な修正が必要になるだろう。

サポートしているものは以下のとおりだ：

  • BEGIN、END、そして範囲パターンを含むパターン・アクションブロック。
  • 制御構造：if、else、for、while、breakなど。
  • 入力の自動フィールド分割（$1、$2など）。
  • printやprintfによる出力 — Goのbufioパッケージを使って高速にバッファリングされる。
  • スカラー変数と配列変数（参照と代入の両方）、x+=10のような複合代入やx++のようなインクリメント／デクリメント演算。
  • FS、NF、OFSといった、よく使われる特殊変数。
  • AWKと同様の自動型変換：数値が文字列コンテキストで使われれば自動的に文字列に変換され、その逆も同様。
  • ~（正規表現マッチ）を含む通常の単項・二項演算子。さらに三項条件演算子、例えばn!=1?"s":""など — ただし両方の分岐が同じ型を返す場合に限る。
  • 組み込み関数の大半：数学関数、split、sprintf、sub、substrなど。

一方、サポートしていないものは以下のとおりだ：

  • 動的型付け：AWKは独自の動的型付けを持つが、Goは静的型付けだ。そのためAWKGoでは、変数に一度文字列を代入したらその変数は文字列のままでなければならず、数値を代入したら数値のままでなければならない。
  • 数値文字列：上に関連して、AWKではユーザー入力から読み込まれた値が数値のように見える場合、「数値文字列」とみなされ、文字列としても数値としても扱うことができる。AWKGoは適切に処理しようとするが、一度ある値を文字列（あるいは数値）と判断したら、その型のままでなければならない。
  • null値：AWKでは未設定の変数は「null」であり、出力時には空文字列として現れる。一方AWKGoでは、未設定の数値変数は0として出力される。
  • ユーザー定義関数：AWKの基準で言えば大きなスクリプトでしか使われないことが多く、動的型付けなしでの実装が少し難しかった。
  • リテラルでないprintfフォーマット文字列：printf("%s %d", k, v)のような書き方はできるが、printf(fmt, k, v)はできない。後者はシンプルなスクリプトでは稀だ。
  • 出力のリダイレクト：AWKGoはprint "foo" >"out.txt"のような形式や、getlineをサポートしていない。
  • 存在しない配列要素：POSIXでは、存在しない配列要素への参照はその要素を生成することになっている。これはひどい仕様だと思うし、いずれにせよGoのmapのセマンティクスに合わせたかった。
  • x = y+=2のような一部の複合代入の形式。サポートできない理由があるわけではなく、単にあまり一般的でない構文にまで手が回らなかっただけだ。
  • ARGCやFILENAMEなどの一部の特殊変数。また、NFなどの一部の特殊変数はAWKGoでは読み取り専用だ。

出力例

AWKGoの出力はどのようなものだろうか？多くの「トランスパイラ」と同様、出力は美しくもなければイディオマティックでもない。うまく変換できる構文もあれば、そうでないものもある。シンプルなものから少し複雑なものまで、3つの例を見てみよう。

先頭のimport宣言や末尾に含まれるランタイムのヘルパー関数は毎回同じなので、ここでは省略する。

また、特に面白くない共通のセットアップコードも省略する。完全なコードへのリンクを貼ってあるのでそちらで確認できるが、ここではコンパイラが出力する核心部分だけを抜粋する。

最初の例は、ウェブサーバーのログから「about」ページへのリクエストを探し、4番目のフィールドを出力するようなシンプルなプログラムだ：

/about/ { print $4 }

これは次のようにコンパイルされる：

func main() {
    _output = bufio.NewWriter(os.Stdout)
    defer _output.Flush()

    _scanner = bufio.NewScanner(os.Stdin)

    // A few lines of setup code elided...

    for _scanner.Scan() {
        _lineNum++
        _line = _scanner.Text()
        _fields = _splitHelper(_line, FS)

        // The is the heart of the translated code
        if _re1.MatchString(_line) {
            fmt.Fprintln(_output, _getField(4))
        }
    }

    if _scanner.Err() != nil {
        fmt.Fprintln(os.Stderr, _scanner.Err())
        os.Exit(1)
    }
}

var (
    _re1 = regexp.MustCompile("about")
)

_splitHelperや_getFieldといったヘルパー関数がどのように定義されているかはGitHub上の完全な出力で確認できるが、ここではそれぞれ基本的にstrings.Fields(_line)や_fields[3]に相当する。

正規表現リテラル（_re1）をトップレベルでGoのregexp.MustCompile関数を使って事前にコンパイルしている点に注目してほしい。

見てのとおり、この例はかなり読みやすく、手書きのGoとそれほど変わらない。AWKでは入出力の扱い（やほとんどの変数）がグローバルな状態であるため、シンプルさを優先してGoでもグローバルとして定義している。

2つ目の例はもう少し複雑だが、それでも十分に現実的な例だ。テキストファイル内の単語の出現回数を数え、単語とその回数を出力する：

{
    for (i = 1; i <= NF; i++)
        counts[tolower($i)]++
}

END {
    for (k in counts)
        print k, counts[k]
}

これは次のようにコンパイルされる（GitHub上の完全な出力）：

func main() {
    // Common setup code elided...

    counts = make(map[string]float64)

    for _scanner.Scan() {
        _lineNum++
        _line = _scanner.Text()
        _fields = _splitHelper(_line, FS)

        // The action (first for loop)
        for i = 1.0; i <= float64(len(_fields)); i++ {
            counts[strings.ToLower(_getField(int(i)))]++
        }
    }

    // Error handling elided...

    // The END for loop
    for k = range counts {
        fmt.Fprintln(_output, k, _formatNum(counts[k]))
    }
}

AWKGoが認識するのは文字列と数値の2種類だけなので、最初のforループで整数だけで済むことを検出できない — すべての数値はfloat64として定義される。これはAWKのセマンティクスをシンプルな形で反映したものだが、もちろんGoで直接書くならintを使うだろう。

AWKの連想配列の操作が、かなりイディオマティックなGoのmapの使い方に変換されている点に注目してほしい。AWKGoは文字列から数値へのmapを構築していることを検出している。また、tolowerはそのままstrings.ToLowerに変換される。

3つ目の例では、もう少しトリッキーなものをコンパイルしてみよう：

$1+0 == $2 { x += ++n }
END { print x }

これは次のようにコンパイルされる（GitHub上の完全な出力）：

func main() {
    // Common setup code elided...

    for _scanner.Scan() {
        _lineNum++
        _line = _scanner.Text()
        _fields = _splitHelper(_line, FS)

        if _numToStr(_strToNum(_getField(1))+0.0) == _getField(2) {
            x += func() float64 { n++; return n }()
        }
    }

    // Error handling elided...

    fmt.Fprintln(_output, _formatNum(x))
}

おそらく特に有用なプログラムではないが、AWKGoに関する興味深い点をいくつか示している。これについては後で詳しく説明するが、+0のような構文で式を数値（あるいは文字列）に強制し、AWKGoの型検出を後押しする必要がある場合がある。また、AWKでは式だがGoでは文であるインクリメントのようなものをどう変換しているかも、この出力からわかる。詳しくは後述する。

型付け

AWKは「stringly typed」と呼ばれることがある。しかしこれはやや侮蔑的な言い方で、実際にはほとんど静的型付けに近い。「数値文字列」のような一部のエッジケースを除けば、明示的な型宣言なしでも、ほとんどの式の型をコンパイル時に検出できる。

個人的には、言語に少し手を加えればAWKの型はコンパイル時に完全に決定できるようになり、その方が言語自体も良くなるのではないかと思っている。「数値文字列」はAWKを学ぶ際に理解に苦しむトリッキーな要素の一つだ。

いずれにせよ、AWKGoの仕事は動的型付けのAWKを静的型付けのGoに変換することだ。そのために、AWKコード内の各式や変数の型を決定するパスを実行する「typer」がある。

数値リテラルや数学演算が行われていれば、それは数値だとわかる。文字列リテラルや文字列操作が行われていれば、それは文字列だ。typerは代入の右辺の型がわかると、左辺の変数も同じ型として指定する。

実際にどのように動作するかを、typerのコード断片で見てみよう（式の型を決定する関数からの抜粋だ）：

func (t *typer) expr(expr Expr) (typ valueType) {
    switch e := expr.(type) {
    case *FieldExpr:
        t.expr(e.Index)
        return typeStr

    case *UnaryExpr:
        t.expr(e.Value)
        return typeNum // all unary operators yield num

    case *BinaryExpr:
        t.expr(e.Left)
        t.expr(e.Right)
        if e.Op == CONCAT {
            return typeStr
        }
        return typeNum // all binary operators except CONCAT yield str

    case *InExpr:
        for _, index := range e.Index {
            t.expr(index)
        }
        t.expr(e.Array)
        return typeNum

    case *NumExpr:
        return typeNum // number literal

    case *StrExpr:
        return typeStr // string literal

    ...
}

typerは構文木を2回走査し、最初に使われた後に代入される変数の型も確実に検出する。例えばwhile (i<5) i++では、i++が代入であり、i<5が使用箇所だ。

前述のとおり、AWKGoでは時折n+0（ゼロを加算する）といった何もしない式で式を数値に強制したり、s ""（空文字列を連結する）で文字列に強制したりする必要がある。これは上記の$1 == $2のような「数値文字列」を比較する場合に必要で、AWKGoはそれらを文字列として比較すべきか数値として比較すべきかわからないからだ。そのため、数値として比較したいなら$1+0 == $2、文字列として比較したいなら$1 "" == $2と、明示的に教えてやる必要がある。多くのAWKスクリプトでは、既知の型の式と比較するので、このトリックは必要ない。

明示的な変換がもう一つ必要になるのは、フィールドを演算なしで直接変数に代入する場合だ。この場合、AWKGoは$1のようなフィールドを文字列として扱うため、n = $1; n++と書こうとするとvariable "n" already set to str, can't set to numというエラーになる。n = $1+0; n++と書いて、明示的に型を教えてやる必要がある。

コンパイラ

AWKGoのコンパイラは、構文木を再び走査してGoのコードを出力するシンプルな「ツリーウォーカー」だ。退屈な作業ではあるが、特に凝ったことは何もない。その一端として、式をコンパイルする関数の一部を紹介しよう：

func (c *compiler) expr(expr Expr) string {
    switch e := expr.(type) {
    case *NumExpr:
        if e.Value == float64(int(e.Value)) {
            return fmt.Sprintf("%d.0", int(e.Value))
        }
        if math.IsInf(e.Value, 0) {
            panic(errorf("number literal out of range"))
        }
        return fmt.Sprintf("%g", e.Value)

    case *StrExpr:
        return strconv.Quote(e.Value)

    case *FieldExpr:
        return "_getField(" + c.intExpr(e.Index) + ")"

    case *VarExpr:
        switch e.Scope {
        case ScopeSpecial:
            return c.special(e.Name, e.Index)
        case ScopeGlobal:
            return e.Name
        default:
            panic(errorf("unexpected scope %v", e.Scope))
        }

    case *RegExpr:
        return fmt.Sprintf("_boolToNum(%s.MatchString(_line))", c.regexLiteral(e.Regex))

    case *BinaryExpr:
        return c.binaryExpr(e.Op, e.Left, e.Right)

    case *IncrExpr:
        exprStr := c.expr(e.Expr) // will be an lvalue (VarExpr, IndexExpr, FieldExpr)
        if e.Pre {
            // Change ++x expression to:
            // func() float64 { x++; return x }()
            return fmt.Sprintf("func() float64 { %s%s; return %s }()",
                exprStr, e.Op, exprStr)
        } else {
            // Change x++ expression to:
            // func() float64 { _t := x; x++; return _t }()
            return fmt.Sprintf("func() float64 { _t := %s; %s%s; return _t }()",
                exprStr, exprStr, e.Op)
        }

    ...
}

この他にも、パターン・アクション、制御構造、代入、tolower()のような組み込み関数などの処理を含む、かなりの量のコードがある。

一つ面白かった問題は、x++（上記参照）のような、AWKでは値として使える式だがGoではトップレベルの文である構文をどう扱うかということだった。これを解決するために、上で示したようにx++を無名関数への即時呼び出しに変換するテクニックを使っている — 関数なら値を返せるし、関数本体ではGoの文を使えるからだ。

例として、y = x++をコンパイルしたもの（複数行に分割して表示）は次のようになる：

y = func() float64 {
    _t := x // temp variable to store current x
    x++
    return _t
}()

ただし、インクリメントや代入の式が文として使われている場合、コンパイラは「最適化」を行う。この場合、式の値は使われず副作用だけが問題になるため、通常のGoの代入文やインクリメント文に短縮できる。

例えば、{ x++; print x }は素直なGoにコンパイルされる：

x++
fmt.Fprintln(_output, _formatNum(x))

コンパイラで手抜きした点の一つは、空白や余分な括弧を気にしないようにしたことだ。Goコンパイラは空白の有無や余分な括弧を気にしないし、上記の例では出力をgofmt -r '(x) -> x'にかけている。これはコードをフォーマットし、書き換えルールで不要な括弧を取り除くものだ。

そのため、AWKの演算子の優先順位をGoのそれに変換しようとする必要がまったくない。単にすべての二項・単項演算の周りに括弧を出力し、あとはgofmtに任せればいい。例えば、AWKプログラムのBEGIN { print 1+2*3 }は次のようにコンパイルされる：

func main() {
// Common setup code elided...
fmt.Fprintln(_output, _formatNum((1.0 + (2.0 * 3.0))))
}

しかし上記のgofmtコマンドにかけると、次のようになる：

func main() {
    // Common setup code elided...
    fmt.Fprintln(_output, _formatNum(1.0+2.0*3.0))
}

ヘルパー関数

フィールドの取得や設定（例えば$1）、文字列と数値の相互変換、match、substr、subといった組み込み関数の実装などの操作のために、小さなAWK「ランタイム」が必要になる。

これらは毎回同じなので、helpers.goの中にGoのソースコードを含む複数行文字列として含めている。それぞれの名前には、名前の衝突を避けるためにアンダースコアのプレフィックスを付けている（完璧ではないことはわかっているが、十分だ）。

例として、フィールドを取得・設定するヘルパー（それぞれ$iや$i = s）を以下に示す。手書きのGoプログラムなら_lineや_fieldsのようなものをグローバルにするのは避けるだろうが、AWKではその状態自体がグローバルなので、そのように変換するのが理にかなっている。

func _getField(i int) string {
    if i < 0 || i > len(_fields) {
        return ""
    }
    if i == 0 {
        return _line
    }
    return _fields[i-1]
}

func _setField(i int, s string) {
    if i == 0 {
        _line = s
        _fields = _splitHelper(_line, FS)
        return
    }
    for j := len(_fields); j < i; j++ {
        _fields = append(_fields, "")
    }
    _fields[i-1] = s
    _line = strings.Join(_fields, OFS)
}

func _splitHelper(s, fs string) []string {
    var parts []string
    if fs == " " {
        parts = strings.Fields(s)
    } else if s == "" {
        // NF should be 0 on empty line
    } else if utf8.RuneCountInString(fs) <= 1 {
        parts = strings.Split(s, fs)
    } else {
        parts = _reCompile(fs).Split(s, -1)
    }
    return parts
}

テスト

GoAWKには、インタプリタのさまざまな側面が正しく動作することを保証する大量のテストがすでにあった。それらをawkgoディレクトリにコピーし、AWKGoを経由して実行されるように手を加えた。

元のテストと同様に、AWKGoのテストも単一のTestAWKGo関数で駆動されるテーブル駆動テストとして書かれている。AWKのソースをパースしてコンパイルし、Goのコードを一時ファイルに出力する。それをgo runで実行し、出力を期待される結果と比較する。

また、テストを実行し、実行ごとに変わる実行時間などの情報を出力から取り除き、結果をawkgo/tests.txtに書き出す小さなスクリプトawkgo/run_tests.shも書いた。

始めた当初は、パスするテストはわずかだった。しかし機能を実装したりバグを修正したりするたびに、ゆっくりと確実にPASSの数がFAILの数を上回るようになっていった。多くのテストに影響する問題を修正して、tests.txtの差分から大量の失敗が消えるのを見るのは本当に気持ちがいい。

実装したい機能を終えたところで一区切りとし、残りのテストをコメントアウトして、go testが失敗なく実行できるようにした。

パフォーマンス

AWKGoプログラムのパフォーマンスは、同じプログラムをAWKインタプリタで実行した場合や、手書きのGoで書いた場合と比べてどうだろうか？

まあ、プログラムによる。タイトなループで数学演算を行うプログラムは大幅に高速化する。0から1億までの整数を合計する次のAWKワンライナーを使ってみよう：

BEGIN { for (i=0; i<100000000; i++) s += i; print s }

AWKGo版の実行時間を、GoAWK、Gawk、mawk、そしてオリジナルのKernighan版awkと比較してみよう。それぞれ3回実行したうちの最速の結果を、遅い順に並べている：

バージョン時間（秒）
goawk6.59
awk6.27
gawk5.73
mawk2.88
awkgo0.33

最初の3つのインタプリタはどれも似たような結果で、Gawkが少しリードしている。mawkはインタプリタとしては非常に高速だ！とはいえ、コンパイルされたGoのコードは当然それより約9倍速い。

比較のために、グローバルではなくローカル変数を使い、float64ではなくintを使ったこのプログラムの手書きGo版は0.098秒で実行され、さらに3倍以上速い。

I/Oを行うプログラム（公平を期して言えば、AWKは通常そういう用途に使うものだが）は、わずかに速くなる程度だ。上で紹介した「単語の出現回数を数える」プログラムを、欽定訳聖書を10回連結したファイルに対して実行し（出力は/dev/nullにパイプ）、計測した結果は次のとおりだ：

バージョン時間（秒）
awk4.56
gawk3.55
goawk3.16
mawk1.23
awkgo0.98

mawkはここでもインタプリタの中では群を抜いて速く、コンパイルされたAWKGo版とほぼ互角だ。mawkがバイトコードコンパイラを使っていることは知っているが、Gawkだってそうなのだ……「Mawkはなぜ速いのか？」という記事は面白そうだ。もし書いたら、リンクを送ってほしい！

おわりに

やる価値はあったか？私にとっては、ほぼ間違いなくあった。言語やコンパイラが好きだし、シンプルな3パスのコンパイラを作るのは良い経験になった。シンプルなコンパイラを書いたことは以前にもあるが、静的型付け言語へコンパイルする「型付け」パスを持つものは初めてだった。

役に立つか？正直、あまりそうでもない。パフォーマンスが欲しければ、Mawkを使えばいい！そして、AWKよりも保守しやすい言語でテキスト処理スクリプトを書きたいなら、最初からGoのような言語で書くだろう。その方がよりイディオマティックなGoになるのはほぼ確実だし、おそらくより効率的でもある。

それでも、手元にあるAWKスクリプトを「本物のプログラム」に変換したいのであれば、AWKGoは悪くない出発点になるかもしれない。スクリプトをGoにコンパイルして構造を得てから、それを整理して、整理したバージョンを保守していけばいい。

いずれにせよ、AWKGoを面白い、あるいは有用だと思ったら、ぜひ教えてほしい。フィードバックを歓迎する！

この記事は「muse-spark-1.2-contributor」を使用して翻訳されました。

コメント