go-templateはチューリング完全？brainf*ck処理系を作ってみた

15181 ワード
kubernetes ネタ kubectl Go Brainf*ck Go テキストリンク

（追記 2022/2/19: 紹介した方法がチューリング完全ではなかったので記事を修正）

TL;DR

  • go-templateの標準関数/構文だけでbrainf*ck処理系を実装！
  • kubectlをbrainf*ckインタープリターとして利用（パワーワード）
    • podのマニフェストにbrainf*ckコード記載
    • kubectlでpod情報取得時に、brainf*ckインタープリターのgo-templateにかける
  • リポジトリ： go-template-bf-interpreter
  • 実用性は...

はじめに

C++のテンプレート、Pythonの内包表記、...有り余る自由度がもたらす黒魔術により、単体でチューリング完全になってしまった言語機能があります。

そして、ここにgo-templateが黒魔術の仲間入りを果たしたことを宣言します。

go-templateといえば、ginのHTMLやkubectlのレスポンス成形等のテンプレート用ミニ言語というイメージが強いですが（というか名前的にそういう意図で作られていますが）、以下のことが全て可能です1。

  • rangeブロックによるコレクションのループ
  • ifブロックによる条件分岐
  • 変数の宣言、更新（再代入）

参考（公式）：template - GoDoc

というわけで、チューリング完全性の登竜門、brainf*ckの処理系をgo-template（Go言語に頼らず、標準関数/構文だけ2）で実装してみました。

（2022/02/19追記：以下紹介する方法はループ回数が有限なのでチューリング完全ではありませんでした （理論上）無限ループができる改良版はこちらの記事 で紹介しています）

動作方法

kubectlを使用します。

podのマニフェストファイルにbrainf*ckのソースコードを入れ、kubectlで取得する際にgo-templateを利用し成形（＝go-templateのbrainf*ckインタープリターで評価）するという仕組みをとっています。

リポジトリ：go-template-bf-interpreter

（kubectlを使用したのは、kubectlではじめてgo-templateを知ったからです。冒頭で「ginのHTML生成でおなじみ」などと書いていましたがエアプですすみません）

マニフェストファイルにbrainf*ckソースコードを格納

metadata.annotationsには任意のキーと値（文字列）を格納できるのでここにソースコードを格納します。ついでにbrainf*ckへの標準入力も入れておきましょう。

hello.yaml
metadata:
  name: bf-source-pod
# add dummies to make annotations long enough to loop (see bf-interpreter.tpl for details)
  annotations:
# used for bf stdin
    input: ""
# bf source code
    src: >
      +++++++++[>++++++++>+++++++++++>+++>+<<<<-]>.>++.+++++++..+++.
      >+++++.<<+++++++++++++++.>.+++.------.--------.>+.>+.
    dummy1: dummy1
    dummy2: dummy2
    #...

ちなみに、ダミーのキーを大量に入れているのは、インタープリターのループ回数を稼ぐためです（後述）。

helloworldのコードは Brainfuck 超入門 - Qiita のものを使用させていただきました。

podのコンテナはどうせ使わないので何でもいいです。とりあえず起動が速いalpineイメージにしておきました。

実行の流れ

# k8sクラスターを構築 (例はkind)
$ kind create cluster

# 上記のhelloworldコードが入ったpodを作成
$ kubectl create -f hello.yaml
pod/bf-source-pod created

# pod情報(=ソースコード)を取得し、その内容をインタープリターとなるgo-templateで評価
$ kubectl get pods -o go-template-file=bf-interpreter.tpl
Hello World!

go-templateプログラミングデザインパターン（？）

brainf*ckインタープリターの実装はこんな感じです。インデント地獄。
bf-interpreter.tpl

以下、使用した小技について紹介していきます。

空白を詰める

{{}}の両端に-を付けると、かっこの外側の空白を詰めることが出来ます。これを使えば、{{}}の外側でインデント、改行を入れてもすべて無視されます。
go-templateプログラミングでは可読性のために必須です。付けないとワンライナー縛りが始まります。

  • ハイフンなし
withspace.tpl
{{if true}}
    {{println "got it!"}}
{{else}}
    {{println "no..."}}
{{end}}
無駄なスペースがそのまま出力される
 kubectl get pods -o go-template-file=withspace.tpl

    got it!
  • ハイフンあり
trimspace.tpl
{{- if true -}}
    {{- println "got it!" -}}
{{- else -}}
    {{- println "no..." -}}
{{- end -}}
無駄なスペースは消える
$ kubectl get pods -o go-template-file=trimspace.tpl
got it!

ループ

brainf*ckにはwhileループが必要です。ソースコード各文字のパースや[,]評価時のジャンプに使用します。

しかし、残念ながらstringはrangeでイテレーションできません。
さらに、go-templateで作成できるリテラルは定数のみなので、配列やマップを新たに作ることもできません。

$ kubectl get pods -o go-template --template '{{range $c := "abc"}}{{println $c}}{{end}}'
...
error: error executing template "{{range $c := \"abc\"}}{{println $c}}{{end}}": template: output:1:14: executing "output" at <"abc">: range can't iterate over abc

そこで、pod情報のmetadata.annotations (map[string]string)をrangeでのループに使用します。アノテーションにダミーを混ぜて、16回ループできるようにしています。

hello.yaml
metadata:
  name: bf-source-pod
  annotations:
# used for bf stdin
    input: ""
# bf source code
    src: >
      +++++++++[>++++++++>+++++++++++>+++>+<<<<-]>.>++.+++++++..+++.
      >+++++.<<+++++++++++++++.>.+++.------.--------.>+.>+.
    dummy1: dummy1
    dummy2: dummy2
    #...
    dummy14: dummy14

このループを多段に使うことで、メモリの初期化やソースコードのパースを行っています。

bf-interpreter.tpl
{{- /* mapを代入し、rangeブロックに使用 */ -}}
{{- $Looper := (index .items 0).metadata.annotations -}}

{{- /* メモリの初期化 (len $Looper)^2バイトを0埋め) */ -}}
{{- $memory := "" -}}
{{- range $Looper -}}
    {{- range $Looper -}}
        {{- $memory = print $memory "\x00" -}}
    {{- end -}}
{{- end -}}

{{- /* ソースコードの読み込み (len $Looper)^3文字を頭からパース) */ -}}
{{- range $Looper -}}
    {{- range $Looper -}}
        {{- range $Looper -}}
            {{- /* NOTE: exists is implemented only in k8s parser */ -}}
            {{- if exists $Source (len $parsingBytePos) -}}
                {{- $tokenByte := index $Source (len $parsingBytePos) -}}
                {{- $token := printf "%c" $tokenByte -}}

                {{- /* トークンを評価（省略） */ -}}

                {{- /* increment pos */ -}}
                {{- $parsingBytePos = print $parsingBytePos " " -}}
            {{- end -}}
        {{- end -}}
    {{- end -}}
{{- end -}}

ちなみに、16回ループしているのはインタープリターのスペックのキリを良くするためです。

  • メモリサイズ: 256byte ($Looper 2段ループ)
  • パース可能ソースコード長上限: 4096文字 ($Looper 3段ループ)

加算、減算

残念ながら（2度目）、go-templateには整数の加算、減算の関数、演算子がありません。
しかし、brainf*ckにはメモリの値やポインタの更新の際加算、減算が必要です。

そこで、文字列の長さを整数の代わりに使用します。
文字列は結合、スライシングにより長さを変えることができ、len関数で長さを整数で取得できます。

  • 加算
inc.tpl
{{- /* go-templateのprintはGoのSprintに相当(副作用はない) */ -}}
{{- $numStr := " " -}}
{{- println (len $numStr) -}}
{{- $numStr = print $numStr " " -}}
{{- println (len $numStr) -}}

$ kubectl get pods -o go-template-file=inc.tpl
1
2
  • 減算
dec.tpl
{{- $numStr := " " -}}
{{- println (len $numStr) -}}
{{- $numStr = slice $numStr 1 -}}
{{- println (len $numStr) -}}

$ kubectl get pods -o go-template-file=dec.tpl
1
0

メモリの更新

前述の通りgo-templateでは配列を作成できません。また、既存オブジェクトの要素のみ更新することもできません。代入式の左辺値になれるのは変数のみです。

$ kubectl get pods -o go-template --template '{{(index .items 0) := "hoge"}}'
error: error parsing template {{(index .items 0) := "hoge"}}, template: output:1: unexpected ":=" in operand

そこで、文字列をメモリとして利用します。
Goでは文字列のインデックスを取る際文字列を[]byteとして扱うので、文字列自体をバイト列とみなすことが出来ます。

go言語のindex
s := "abc"
fmt.Println([]byte(s)) // [97 98 99]
fmt.Println(s[0]) // 97
fmt.Println([]byte(s)[0]) // 97

そして、+や-等で文字列中のあるバイトのみ更新する場合は、「当該バイトのみ置き換えた新しいメモリ文字列」を作成しています。

bf-interpreter.tpl
{{- else if eq $token "+" -}}
    {{- /* ...参照アドレスの値を取り出しインクリメント(省略) */ -}}

    {{- /* メモリの更新 */ -}}
    {{- /* 参照アドレスのみ置き換えた新しいメモリで置き換える */ -}}

    {{- /* 参照アドレスより前のメモリ */ -}}
    {{- $former := slice $memory 0 (len $memoryPtr) -}}

    {{- /* 参照アドレスより後のメモリ */ -}}
    {{- /* NOTE: (len (print $memoryPtr " ") は参照アドレス+1 */ -}}
    {{- $latter := slice $memory (len (print $memoryPtr " ")) -}}

    {{- /* 置換（バイトの値をそのままprintすると整数が文字列化されてしまうので、printfで対応するアスキーコードの文字に変換） */ -}}
    {{- $memory = print $former (printf "%c" $incrementedValue) $latter -}}
{{- end -}}

おわりに

以上、go-templateのbrainf*ck処理系の紹介でした。

Let's go-templateプログラミング！

  1. これだけ見ると「そんなんerbでもできるわ！」という感じですが、erbはRubyの式を何でも書ける一方、go-templateは独立した文法(スカラーしか作れず、goの標準関数もそのままでは呼び出せない)という縛りがあります... ↩

  2. 一部、k8s独自のgo-template関数(index)は使っています。実装は こちら ↩