（追記 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のレスポンス成形等のテンプレート用ミニ言語というイメージが強いですが（~~というか名前的にそういう意図で作られていますが~~）、以下のことが全て可能です¹。

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

参考（公式）：template - GoDoc

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

（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プログラミング！

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