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

（追記 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](https://github.com/Syuparn/go-template-bf-interpreter)
- 実用性は... :smirk:

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

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

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

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

参考（公式）：[template - GoDoc](https://godoc.org/text/template)

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

（2022/02/19追記：以下紹介する方法はループ回数が有限なので**チューリング完全ではありませんでした :bow:** （理論上）無限ループができる改良版は[こちらの記事](https://qiita.com/Syuparn/items/4157d13c39b95185acfd#%E3%83%86%E3%83%B3%E3%83%97%E3%83%AC%E3%83%BC%E3%83%88%E3%81%A7%E5%86%8D%E5%B8%B0%E5%87%A6%E7%90%86) で紹介しています）

# 動作方法

`kubectl`を使用します。

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

リポジトリ：[go-template-bf-interpreter](https://github.com/Syuparn/go-template-bf-interpreter)

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

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

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

```yaml: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](https://qiita.com/TomoShiozawa/items/25dcce1540085df71053) のものを使用させていただきました。

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

## 実行の流れ

```bash:
# 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](https://github.com/Syuparn/go-template-bf-interpreter/blob/main/bf-interpreter.tpl)


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


## 空白を詰める

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

- ハイフンなし

```:withspace.tpl
{{if true}}
    {{println "got it!"}}
{{else}}
    {{println "no..."}}
{{end}}
```

```bash:無駄なスペースがそのまま出力される
 kubectl get pods -o go-template-file=withspace.tpl

    got it!

```

- ハイフンあり

```:trimspace.tpl
{{- if true -}}
    {{- println "got it!" -}}
{{- else -}}
    {{- println "no..." -}}
{{- end -}}
```

```bash:無駄なスペースは消える
$ kubectl get pods -o go-template-file=trimspace.tpl
got it!
```

## ループ

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

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

```bash:
$ 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回ループできるようにしています。

```yaml: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) -}}
```

```bash:
$ kubectl get pods -o go-template-file=inc.tpl
1
2
```

- 減算

```:dec.tpl
{{- $numStr := " " -}}
{{- println (len $numStr) -}}
{{- $numStr = slice $numStr 1 -}}
{{- println (len $numStr) -}}
```

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

## メモリの更新

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

```bash:
$ 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: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`)は使っています。実装は [こちら](https://github.com/kubernetes/kubernetes/blob/c1e5e6a5562bdd968977a36720f56362fbf4aa26/staging/src/k8s.io/cli-runtime/pkg/printers/jsonpath.go#L38)