(この記事は、2021年にQiitaに上げた記事の再投稿です。内容が古くなっている可能性がありますのでご了承ください。)

TL;DR

CUE言語でbrainf*ckの処理系を実装

https://github.com/Syuparn/cuebf

理論上は動くが、メモリを食いすぎて途中でOutOfMemoryになってしまう… 😇 ¹

はじめに

CUEは、スキーマ定義やデータバリデーション等が行える言語です。

CUE

安全にデータ構造のパッチができるので、KubeVelaのマニフェスト記述言語としても使われています。

…しかし、CUEの実力はこれに留まりません。CUEはscriptingの利用を想定しており、公式サイトでも

Automate the use of your data without writing yet another tool (別のツールを作らずともデータの活用を自動化できる)

と書かれています。ならば、scripting能力を限界まで引き出せば言語処理系も実装できるはずです。

というわけで、本記事ではCUEを使ってbrainf*ck処理系を実装した方法について紹介します。~~まじめな実用例については別の記事をご覧ください。~~

バージョン

CUE: v0.4.0

CUEの特徴：型と値を同一視

本題に入る前に、軽くCUEの型システムについて見ていきます。（詳細は公式ドキュメントをご覧ください)

CUEは型と値を区別しません。多くのプログラミング言語では「型（またはクラス）」は具体的な「値（またはインスタンス）」の集合を表していますが、CUEでは値自身も要素を1つだけ持つ集合とみなします。

これにより（OOPでいう）継承とインスタンス化をいずれも集合の共通部分を取ることで実現できます。²

Person: {
    name: string
    age: int
}

// 継承
Child: Person & {
    age: <20
}

// インスタンス
taro: Person & {
    name: "Taro"
    age: 25
}

型と値の二元論でないおかげで、「20歳未満」のようなバリデーション要素も値と同じようにデータに組み込むことができます(上記<20)。

集合の共通部分が空集合(_|_)になる場合は、型が合わないとみなされエラーが発生します。

foo: int & "abc" // foo: conflicting values int and "abc" (mismatched types int and string)

マニフェストの上書きでも、& を使えばベースの型や制約を満たさなければエラーに倒せるため安全にoverlayできます。

型システムを悪用したCUEプログラミング

次は型システムを使って、CUEをプログラミング言語として使ってみましょう。~~（業務で乱用するのはおすすめしません）~~

継承やインスタンス化は前述の通り & で表現可能です。関数もフィールドどうしの関係を利用することで実装できます。

// 関数: 引数と戻り値の関係
add: {
    x: int
    y: int
    return: x + y
}

// 関数呼び出し: 関数と引数の「共通部分」
z: (add & {
    x: 2
    y: 3
}).return // 5

手続き的な処理も、内包表記で状態のリストを作ることで表現できます。

import (
    "list"
)

fact: {
    n: int
    // 初期値
    factorials: "0": 1
    // 一つ前の状態から次の状態を計算
    // NOTE: pythonと構文が微妙に違うので注意！
    factorials: {for i in list.Range(1, n + 1, 1) {
        "\(i)": factorials["\(i-1)"] * i
    }}
    return: factorials["\(n)"]
}

"5!": (fact & {n: 5}).return // 120

brainf*ck処理系の実装

上記のテクニックを使って、brainf*ck処理系を実装しました。

モジュール化

モジュールはGo同様

$ cue mod init github.com/syuparn/cuebf

で作成可能です。配下のディレクトリごとにpackageを作ることができ、同じpackageであれば別ファイルでも変数の参照が可能です（これもGoと同じ）。

lexer

まず、文字列を1文字ずつに区切り、意味のある文字だけ抽出します。

sourceTokens: [ for t in strings.Split(source, "") if list.Contains(validTokens, t) {t}]

validTokens: [
	"+",
	"-",
	">",
	"<",
	"[",
	"]",
	".",
	",",
]

parser

「Brainf*ckにパースは不要では？」と思われるかもしれませんが、[と]のジャンプ先のtokenを知る必要があるためネストの深さを計算しています。

// tokenリストから`[` `]`だけ抜き取って、それが何番目のtokenかを記録
#Brackets: {
	tokens: [...string]
	brackets: [ for i, t in tokens if list.Contains(["[", "]"], t) {
		idx:   i
		token: t
	}]
}

#NestLevels: {
	bracketIndices: [...{idx: int, token: ("[" | "]")}]

	nestLevelsStruct: "-1": {idx: -1, level: 0, token: "["} // dummy initial element
	// structを使って、前のtokenのネストの深さから次の要素のネストを計算している
	// (listだと計算順序の問題からか上手く評価されなかった)
	nestLevelsStruct: {for i, b in bracketIndices {
		"\(i)": {
			idx:   b.idx
			token: b.token
			if b.token == "[" && nestLevelsStruct["\(i-1)"].token == "[" {
				level: nestLevelsStruct["\(i-1)"].level + 1
			}
			if b.token == "]" && nestLevelsStruct["\(i-1)"].token == "]" {
				level: nestLevelsStruct["\(i-1)"].level - 1
			}
			if b.token != nestLevelsStruct["\(i-1)"].token {
				level: nestLevelsStruct["\(i-1)"].level
			}
		}
	}}
	// 扱いやすいようにstructをlistに詰め替える
	nestLevels: [ for i in list.Range(0, len(nestLevelsStruct)-1, 1) {
		let nl = nestLevelsStruct["\(i)"]
		idx:   nl.idx
		level: nl.level
	}]
}

evaluator

トークンを評価するたびにメモリ、次に評価するトークン、出力等が変化します。これを宣言的に記述するために、evaluatorには初期状態からnステップ後までの状態のリストを持たせています。

#Evaluator: {
	initial: initialState
	states: "0": initial
	states: {for i in list.Range(1, maxStates, 1) {
		// 未評価のtokenが残っているなら
		if states["\(i-1)"].cursor < len(states["\(i-1)"].tokens) {
			// ステップiの状態は、ステップi-1の状態に対して「現在読んでいるtoken」のコマンドを実行した結果
			"\(i)": (#Commands[states["\(i-1)"].tokens[states["\(i-1)"].cursor]] & {
				input: states["\(i-1)"]
			}).output
		}
	}}
	result: states["\(len(states)-1)"]
}

状態には、brainf*ckを実行するための全ての要素を持たせています。

#State: {
	memories: #Memories // メモリ
	pointer:  int // メモリポインタ
	tokens: [...string] // ソースコード（のトークンリスト）
	nestLevels: [...{idx: int, level: int}] // ネストの深さ(`[`, `]`の評価に使用)
	cursor: int // 今読んでいるtokenが何番目か
	inputValues: [...#MemoryUnit] // 入力 (`,` のたびに先頭から取り出す)
	outputValues: [...#MemoryUnit] // 出力 (`.` のたびに末尾に追加)
}

各コマンドは、コマンド実行前の入力状態と実行後の出力を持っています。

#_Command: {
	input:  #State
	output: #State
}

// `+`: ポインタの値を1増やす
#PlusCommand: #_Command & {
	input: #State
	output: {
		memories: list.Concat([
				input.memories[:input.pointer],
				[mod(input.memories[input.pointer]+1, memoryUnitSize)],
				input.memories[input.pointer+1:],
		])
		pointer:      input.pointer
		tokens:       input.tokens
		nestLevels:   input.nestLevels
		cursor:       input.cursor + 1 // tokenを読み進めるのを忘れずに
		inputValues:  input.inputValues
		outputValues: input.outputValues
	}
}

[, ] のコマンドでは、parserで計算したネストの深さを利用します。注意点として、可変長リストの要素参照が定義に含まれる場合は、ダミー要素を入れておかないとエラーが発生してしまいます(#JumpToEnd の部分。[...T] やそれをもとに作ったリストは長さ0で推論されるため)。

#StartCommand: #_Command & {
	input: #State
	output: {
		memories:   input.memories
		pointer:    input.pointer
		tokens:     input.tokens
		nestLevels: input.nestLevels
		// ポインタの値が0であれば、ネストの深さが同じtokenまで読み進める
		if memories[pointer] == 0 {
			cursor: (#JumpToEnd & {state: input}).jumpedCursor + 1
		}

		// elseの構文はないので別のif文使用
		if memories[pointer] != 0 {
			cursor: input.cursor + 1
		}
		inputValues:  input.inputValues
		outputValues: input.outputValues
	}
}

#JumpToEnd: {
	state: #State
	// NOTE: 最後のダミー要素 0 が無いと、`&` をとって具体化する前の #JumpToEnd が out-of-indexエラーを吐いてしまう (currentNestLevelで0番目要素を参照するため)
	currentNestLevel: [ for nl in state.nestLevels if nl.idx == state.cursor {nl.level}, 0][0]
	jumpedCursor:     [ for nl in state.nestLevels if (nl.idx > state.cursor) && (nl.level == currentNestLevel) {
		nl.idx
	}, len(state.tokens)][0]
}

あとは、tokenに応じて実行するコマンドをstructで取り出せるようにすれば完成です。

// #Commands[token] でコマンドを取り出せる
#Commands: {
	"+": #PlusCommand
	"-": #MinusCommand
	">": #IncCommand
	"<": #DecCommand
	"[": #StartCommand
	"]": #EndCommand
	",": #ReadCommand
	".": #WriteCommand
}

ちなみに上記はdisjunction(2つの型の和集合)を使うともっとかっこよく書けるのですが、計算時間がstate数の指数関数で増えていったので諦めました 😢 (おそらくevaluatorのdisjunctionが 8^state数 個になるのが原因)

#_Command: {
	token:  string
	input:  #State
	output: #State
}

#PlusCommand: #_Command & {
	token: "+"
	// ...
}

// #Command & {token: token} でコマンドを取り出せる
// (tokenが具体的な値になることで、#Commandのどれか1つに推論可能なため)
#Command: #PlusCommand | #MinusCommand | #IncCommand | #DecCommand | #StartCommand | #EndCommand | #ReadCommand | #WriteCommand

CLI

最後に、実行するためのCLIを作ります。標準の tool/* モジュールに、CLI作成のための操作が一通りそろっています。

cli: 対話型コマンドライン作成
exec: コマンドライン実行
file: ファイル読み書き
http: httpクライアント
os: 環境変数の読み書き

cue/pkg/tool at master · cue-lang/cue · GitHub

*_tool.cue という名前のファイルがコマンド実行に使えます。command の配下に定義した要素は、 cue のサブコマンドとして呼び出せます。

package main

import (
	"tool/cli"
	"tool/file"

	interpreter "github.com/syuparn/cuebf/bf"
	"github.com/syuparn/cuebf/view"
)

// `$ cue bf` で実行するコマンドの定義
command: bf: {
	// 実行する各タスクをtaskに定義（全て実行される）
	// brainf*ckソースコード読み込み
	task: read: file.Read & {
		filename: "hello.bf"
		contents: string
	}

	// ソースコードを評価し、出力結果を表示
	task: eval: cli.Print & {
		outputValues: (interpreter & {
			memorySize: 8
			source:     task.read.contents
			inputValues: [97, 98, 99]
			maxStates: 512
		}).#Evaluator.result.outputValues
		text: (view.bytesToStr & {byteInts: outputValues}).str
	}
}

file.Read や cli.Print 等は cue eval で評価した際には実行されないので、必ず上記のようにスクリプト化する必要があります。また、サブコマンドの引数指定は未対応なので、hello worldのファイルを決め打ちで読み込んでいます。

いざ実行！

$ cue bf
fatal error: out of memory allocating heap arena metadata

runtime stack:
runtime.throw(0x1564d3e, 0x2c)
...

😇

~~きっといつかムーアの法則が解決してくれるはず…~~

おわりに

残念ながらスペック不足によりhello worldを実行することが出来ませんでした。もう少し効率化が必要なようです。

最後までネタ記事にお付き合いいただきありがとうございました。CUEの機能を一通り触れたので、今度は真面目な用途でも使ってみたいと思います。

もちろんCUEが想定するまともな使い方をしていたらメモリを食いつぶすことはありません。 ↩︎
CUEの用語としては、継承した型(subtype)のことも「インスタンス」と呼ぶようです。 ↩︎

揮発性メモ帳

スキーマ定義だけじゃない、CUE言語プログラミングの限界に挑む