Go to Qiita Advent Calendar 2024 Top
LoginSignup
4
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@Syuparnin富士通クラウドテクノロジーズ株式会社

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

Last updated at Posted at 2020-10-18

（追記 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
  • 実用性は... :smirk:

はじめに

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

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

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

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

参考（公式）：template - GoDoc

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

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

動作方法

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)は使っています。実装は こちら ↩

4
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?