はじめに
こちらは株式会社Voicyのアドベントカレンダーの23日めの記事です！
自己紹介
私は11月からVoicyに11月にバックエンドエンジニアとして入社しました。入社してから日が浅いためにあまり業務とは関係ない記事を書くことになります。その点ご了承ください。
VoicyではGo言語をバックエンドの開発言語として使用しているため、Go言語の記事をかきます。
Brainf**kって？
いまとなってはBrainf**kの記事は世にありふれていますが、あらためて説明します。
Brainf**kはたった8つの命令文字からなるプログラミング言語で、非常に可読性が低いです。
以下は命令の一覧です。
> ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。
< ポインタをデクリメントする。C言語の「ptr--;」に相当。
+ ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。
- ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。
. ポインタが指す値を出力に書き出す。C言語の「putchar(*ptr);」に相当。
, 入力から1バイト読み込んで、ポインタが指す先に代入する。C言語の「*ptr=getchar();」に相当。
[ ポインタが指す値が0なら、対応する ] の直後にジャンプする。C言語の「while(*ptr){」に相当。
] ポインタが指す値が0でないなら、対応する [ （の直後[注釈 1]）にジャンプする。C言語の「}」に相当[注釈 2]。
Wikipediaから引用(https://ja.wikipedia.org/wiki/Brainfuck)
プログラム例
hello world
+++++++++[->++++++++>+++++++++++>+++++<<<]>.>++.
+++++++..+++.>-.------------.<++++++++.--------.
+++.------.--------.>+.
なんとよみにくいことでしょうか。
参考までにGo言語でhello worldはこんなかんじですね。
package main
import "fmt"
func main() {
fmt.Println("Hello, world!")
}
なぜこんな言語のインタプリタをつくるのか
GoやPHPのようなよく使われるプログラミング言語に比べて、Brainf**kは本当に見にくい言語です。しかしそれは裏を返せば少ない言語仕様を読めばインタプリタを実装したりしやすい非常に教育的な言語であることです。個人的に言語処理系に多少の興味があり、勉強に丁度いいかなと思い実装しました。
実際のコード
package main
import (
"fmt"
"os"
)
// brainf**kのトークン
const (
INCREMENT = "+"
DECREMENT = "-"
NEXT = ">"
PREVIOUS = "<"
LOOP_START = "["
LOOP_END = "]"
READ = ","
WRITE = "."
)
// 必要なポインター、バイト列などを格納する構造体
type bf struct {
point, codePoint int
mem, buf, code []byte
}
func main() {
// 引数チェック
if len(os.Args) < 2 {
fmt.Println("please input filename")
return
}
// 引数で受け取ったファイル名を開く
f, err := os.ReadFile(os.Args[1])
if err != nil {
fmt.Println(err)
return
}
program := NewProgram(f)
// const とそれを処理する関数のmap
dict := map[string]func(){
INCREMENT: program.Increment,
DECREMENT: program.Decrement,
NEXT: program.Next,
PREVIOUS: program.Previous,
LOOP_START: program.LoopStart,
LOOP_END: program.LoopEnd,
READ: program.Read,
WRITE: program.Write,
}
for {
key := string(program.code[program.codePoint : program.codePoint+1])
if _, ok := dict[key]; ok {
dict[key]()
}
program.codePoint++
if program.codePoint >= len(program.code) {
break
}
}
}
func NewProgram(f []byte) *bf {
bf := new(bf)
bf.mem = make([]byte, 3000, 3000)
bf.buf = make([]byte, 1)
bf.code = f
return bf
}
// Next ポインターのインクリメント
func (b *bf) Next() {
b.point++
}
// Previous ポインターのデクリメント
func (b *bf) Previous() {
b.point--
}
// Increment ポインターの示す値のインクリメント
func (b *bf) Increment() {
b.mem[b.point]++
}
// Decrement ポインターの示す値のデクリメント
func (b *bf) Decrement() {
b.mem[b.point]--
}
func (b *bf) LoopStart() {
if b.mem[b.point] == 0 {
n := 0
for {
b.codePoint++
if string(b.code[b.codePoint:b.codePoint+len(LOOP_START)]) == LOOP_START {
n++
} else if string(b.code[b.codePoint:b.codePoint+len(LOOP_END)]) == LOOP_END {
n--
if n < 0 {
break
}
}
}
}
}
func (b *bf) LoopEnd() {
if b.mem[b.point] != 0 {
n := 0
for {
b.codePoint--
if string(b.code[b.codePoint:b.codePoint+len(LOOP_END)]) == LOOP_END {
n++
} else if string(b.code[b.codePoint:b.codePoint+len(LOOP_START)]) == LOOP_START {
n--
if n < 0 {
break
}
}
}
}
}
func (b *bf) Write() {
b.buf[0] = b.mem[b.point]
_, err := os.Stdout.Write(b.buf)
if err != nil {
return
}
}
func (b *bf) Read() {
_, err := os.Stdin.Read(b.buf)
if err != nil {
return
}
b.mem[b.point] = b.buf[0]
}
。
コードに関しても説明すべき説明は世に溢れているので深くはする必要性を感じないですが、少しだけ工夫した点があります。
- switch文ではなく、mapでトークンと関数の紐付けを行った。これは、世にあるサンプルコードのほとんどがswitchで実装されているため、同じことをしても芸がないなと考えたため。
- inputしたbfコードに現れるトークンとconstの比較を文字コードではなく文字列で行い、slice操作をしている点。これは後々トークンを文字ではなく、意味のある文字列にする実装がしやすいと考えたため。
- 言語処理に必要なポインターやバイト列をstructに入れて、そこに関数を作成した。これはなんとなく、実際の業務でのGoの使い方に近いかなと考えたため。
ループ処理については自分でも正確な説明をできるか不安なのでこの記事では行いませんが、試行錯誤しているうちになんとーなくわかったような気になってきます。
さて、このプログラムを動かしてみます。
% go run main.go hello_world
Hello, world!
おてもとで動かしてみてください！なんとか動くのではないでしょうか
おまけ Voicy言語
使用している文字列さえ変えてしまえば、Brainf**kとおなじ形式のオリジナル言語を作ることができます。
voicy.jpの8文字を使ってみましょう
const (
INCREMENT = "v"
DECREMENT = "o"
NEXT = "i"
PREVIOUS = "c"
LOOP_START = "y"
LOOP_END = "."
READ = "j"
WRITE = "p"
)
hello world
vvvvvvvvvyoivvvvvvvvivvvvvvvvvvvivvvvvccc.ipivvp
vvvvvvvppvvvpiopoooooooooooopcvvvvvvvvpoooooooop
vvvpoooooopoooooooopivp
こちらを実行しても先ほどと同様の結果が得られます！
% go run main.go hello_world
Hello, world!
最後に
あまりまとまりのない記事になってしまったかなーと思いますが以上となります。一見簡単そうにみえるこのプログラムですが、自分で作ってみると結構時間がかかるものですね。あと、やはりトークンを長い文章にできたらなーと思います。これはまた今度やろう。
参考
https://rightcode.co.jp/blog/information-technology/brainfuck-implementation-learn-cpp-practice-last-part
https://yryr.me/programming/csharp/beginner/object-model/sample-program/how-to-create-brainfuck-interpreter.html
https://ja.wikipedia.org/wiki/Brainfuck
http://tsoft-web.com/sub/brainfuck/convert.html