Brainfuck

date:	2013/02/15

1. 概要
2. Brainfuck とは
3. Brainfuck by Haskell
4. まとめ
5. コード

1. 概要

Haskell で Brainfuck の処理系を書く。

2. Brainfuck とは

Brainfuck はプログラミング言語の1つです。

2.1. Brainfuck の概要

Wikipedia の定義を見てみましょう。

Brainfuck - Wikipedia

まず、Brainfuck という言語は、次の8つのコマンドを持ちます。

> < + - . , [ ]

言語の処理系としては、概ね

プログラム (上記のコマンドを列挙したようなもの)
プログラム中の文字をどこを読んでいるかを表すポインタ
Int 型の配列 (要素は 0 に初期化)
配列の要素のどこかを表すポインタ
入出力ストリーム

があれば良いようです。

以下では、コマンド以外の文字はすべて無視する処理系を作ることにします。

2.2. Brainfuck の構文

Brainfuck の構文を定義します。
任意の文字列に対して、文字列が Brainfuck のプログラムとして解釈されるかどうかが決まるはずなので、
Brainfuck のプログラムになる文字列を決めようということです。
コマンド以外の文字は読み飛ばすので、適当に扱うことにします。

Comm = > | < | + | - | . | ,
(Dust = {2.1 に挙げたコマンド以外のすべての文字})
BF   = Comm (| Dust) | BF | [BF]

この BF が、 Brainfuck のプログラム全体です。

例えば、以下のような文字列は Brainfuck のプログラムです。

1. +++++++,<<<++.>+>>+++.++++<<<+++.>.++++++>>++++++++++++++++++++---<<<<<<<>>>>[->+[-]<]<<[-]
2. 9313rkok;+..+>>>.,<<,<,?<,.
3. ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

一方で、以下のような文字列は [ や ]が対応していないので、 Brainfuck のプログラムではない、こととします。

(このような文字列も適当な修正をすることに決めておけば、Brainfuck のプログラムとできます)

1. +++[>+++<---[]
2. -]]

2.3. Brainfuck の動作

Brainfuck の動作について説明します。

まず、 Brainfuck の処理系には、

プログラム, 配列, 配列の要素を指すポインタ, 入出力ストリーム

がありました。
プログラムを読む最初の段階、初期状態では、ポインタは配列の左端を指していて、
配列の全要素が 0 で初期化されています。
そして、プログラムを読むごとに、各コマンドを実行していきます。

各コマンドの意味を説明しましょう。

2.3.1. > <

> : ポインタをインクリメントする
< : ポインタをデクリメントする

2.3.2. + -

+ : ポインタの指す値をインクリメントする
- : ポインタの指す値をデクリメントする

2.3.3. . ,

. : 入力から 1バイト読み込んで、ポインタの指す先に代入する
, : ポインタの指す値を出力する

ただし、どちらも ASCII code を用いて、入出力を行う。

2.3.4. [ ]

[ : ポインタが指す値が 0 なら、対応する ] の直後へジャンプする
] : ポインタが指す値が 0 でないなら、対応する [ にジャンプする

Note

] について、[ に戻った時に [ ] のブロックを抜けるかどうか見れば動作は同じなので、

以下では ] を読んだときは、必ず一度 [ に戻ることにする。

2.4. Brainfuck プログラムの例

以上で、大体 Brainfuck の動作についてわかったことにして、例を出してみます。

1. +++++++++++++++++++++++++++++++++++++++++++++++++. ('+'が49個続いたあと、'.'がある)
2. +++++++[->+++++++<]>.

Brainfuck では初期状態では、ポインタは配列の左端を指し、配列の要素は 0 だったことを思い出しましょう。

例1. について

‘+’ が49個あるので、 ‘.’ を実行するときポインタの指す要素は 0+49=49 となっています。

ASCII コードで 49 は数字の 1 のことなので、1 が出力されます。

例2. について

‘[‘ の手前までで ‘+’ が 7個あるので配列の要素は [_7, 0, 0, 0...] となって、ポインタは左端を指しています。
(_ はポインタの指す場所を表すことにします。)
‘[‘ を読む時、ポインタの指す値は 7 (つまり 0 でない)なので、[]の中身を実行します。
‘[ ]’の中身は何をするかというと、

ポインタの指す値を -1

[_6, 0, 0, ...]

ポインタを右へずらす

[6, _0, 0, ...]

“ポインタの指す値を +1” を 7回

[6, _7, 0, ...]

ポインタを左へずらす

[_6, 7, 0, ...]

という処理をします。つまり、ポインタの指す値を -1 して、右の値を +7 する処理です。
この処理が、 ポインタの指す値が 0 になるまで続くので、’[ ]’ を抜けるときには、[0, _49, 0, ...] となります。
よって、 例1 と同様に、数字の 1 が出力されます。

長々と Brainfuck の説明をしたので、次は Haskell で Brainfuck を実装することを考えましょう。

3. Brainfuck by Haskell

ここからは、 Haskell で上に述べたような Brainfuck (と”同じ”もの)を実装しましょう。

3.1. 構文

まず、 2.2. でやったように Brainfuck のプログラムと呼べる列を定義しましょう。

data Br = Next | Prev | Succ | Pred | Out | In | Loop [Br]

このとき、 Br のリスト [Br] がここで実装する Brainfuck のプログラムの全体となります。

3.2. Brainfuck との対応

Brainfuck のプログラムと、上で定義した [Br] を対応させましょう。

各コマンドの対応は次のようにします。

Brainfuck	[Br]
>	Next
<	Prev
+	Succ
-	Pred
.	Out
,	In
[ br ]	Loop [ br ]

プログラムの対応を与える関数 translate の型は、

transelate :: String -> [Br]

となるはずです。(めんどくさいので、与えられる文字列は [ ]がちゃんと対応しているものとする。)
プログラムを前から読んでいって、表の通りに対応させようとすると、
まだ読んでいない残りの文字列を表した方が便利なので、次の型を持つ関数 pretranslate を考えます。

pretranslate :: String -> ([Br], String)

というわけで、 translate, pretranslate を実装します。

translate :: String -> [Br]
translate = fst . pretranslate

(+++) :: a -> ([a], b) -> ([a], b)
(+++) s (t, str) = (s:t, str)

pretranslate :: String -> ([Br], String)
pretranslate ('>':str) = Next +++ pretranslate str
pretranslate ('<':str) = Prev +++ pretranslate str
pretranslate ('+':str) = Succ +++ pretranslate str
pretranslate ('-':str) = Pred +++ pretranslate str
pretranslate ('.':str) = Out +++ pretranslate str
pretranslate (',':str) = In +++ pretranslate str
pretranslate ('[':str) = let (bf, xs) = pretranslate str in Loop bf +++ pretranslate xs
pretranslate (']':str) = ([], str)
pretranslate (_:str) = pretranslate str
pretranslate [] = ([], [])

ここで、

pretranslate ('[':str) = let (bf, xs) = pretranslate str in Loop bf +++ pretranslate xs
pretranslate (']':str) = ([], str)

の行を説明します。
配列は、a:b:c:...:[] という形なので、 pretranslate str の評価で、 str の中に ‘]’ という文字があれば、
br1 +++ br2 +++ ... +++ ([], xs) = (bf,xs) という評価ができます。
xs は ‘]’ の後の文字列になっているので、あとは、 xs を pretranslate しておけば、対応を定めることができます。

3.3. 実行

Brainfuck では、ポインタが配列のどの場所を指すか、という状態があるので、

ポインタが指す場所と、その前後の配列を合わせて、1つの状態だと思えば良いでしょう。

type State = ([Int], Int, [Int])

あとは、各コマンドの意味にしたがって、[Br]→IO() を定めれば良いでしょう。

4. まとめ

Haskell で Brainfuck と似たようなものができた。
括弧のような、単独では意味が決まらないコマンドを含む文字列のパースができた。
もっとうまく書かれてるブログを見つけた...つらい。 Haskellで書くBrainfuckインタープリタ - プログラムモグモグ
- 特に、モナドの扱いと、 Brainfuck の実行部分のコードが全く異なっている。

5. コード

以下は、コードの全体像です。

import Data.Char (chr, ord)
--
-- Define Brainfuck syntax
--
data Br = Next | Prev | Succ | Pred | Out | In | Loop [Br] deriving (Show, Eq)

--
-- Parser
--
translate :: String -> [Br]
translate = fst . pretranslate
--
-- Translater for translate
--
(+++) :: a -> ([a], b) -> ([a], b)
(+++) s (t, str) = (s:t, str)
pretranslate :: String -> ([Br], String)
pretranslate ('>':str) = Next +++ pretranslate str
pretranslate ('<':str) = Prev +++ pretranslate str
pretranslate ('+':str) = Succ +++ pretranslate str
pretranslate ('-':str) = Pred +++ pretranslate str
pretranslate ('.':str) = Out +++ pretranslate str
pretranslate (',':str) = In +++ pretranslate str
pretranslate ('[':str) = let (bf, xs) = pretranslate str in Loop bf +++ pretranslate xs
pretranslate (']':str) = ([], str)
-- Ignoring invarid chars
pretranslate (_:str) = pretranslate str
pretranslate [] = ([], [])

--
-- State of Brainfuck : consist of array and pos.
--
type State = ([Int], Int, [Int])
-- Execution Brainfuck syntax
exec :: [Br] -> IO([Br], State)
exec bf = do
  (bf, state) <- step bf ([], 0, [])
  -- putStrLn $ show (bf, state)
  exec' bf state

exec' bf state
  | bf == []  = return ([], state)
  | otherwise = do
      (bf', state') <- step bf state
      -- putStrLn $ show (bf', state')
      -- putStrLn $ show state'
      exec' bf' state'

step :: [Br] -> State -> IO ([Br], State)
step (Next:bf) (xs, x, [])            = return (bf, (x:xs, 0, []))
step (Next:bf) (xs, x, s:ys)          = return (bf, (x:xs, s, ys))
step (Prev:bf) state@([], x, ys)      = return (bf, state)
step (Prev:bf) (s:xs, x, ys)          = return (bf, (xs, s, x:ys))
step (Succ:bf) (xs, x, ys)            = return (bf, (xs, x + 1, ys))
step (Pred:bf) (xs, x, ys)            = return (bf, (xs, x - 1, ys))
step (Loop []:bf) state@(xs, 0, ys)   = return (bf, state)
step br@(Loop s:bf) state@(xs, x, ys) = do
  (_, st@(xs', x', ys')) <- (exec' s state)
  if ( x' == 0 )
     then return (bf, st)
     else return (br, st)
step (Out:bf) state@(xs, x, ys)       = do
  putChar (chr x)
  return (bf, state)
step (In:bf) (xs, x, ys)              = do
  s <- getChar
  return (bf, (xs,ord  s, ys))
step [] state                         = return ([], state)

--
-- Interpret & Execution
--
interpreter :: String -> IO()
interpreter str = (exec $ translate str) >> (return ())

main :: IO()
main = do
   contents <- readFile "BrainFuck.txt"
   interpreter contents

Study Haskell

Brainfuck

1. 概要

2. Brainfuck とは

2.1. Brainfuck の概要

2.2. Brainfuck の構文

2.3. Brainfuck の動作

2.3.1. > <

2.3.2. + -

2.3.3. . ,

2.3.4. [ ]

2.4. Brainfuck プログラムの例

例1. について

例2. について

3. Brainfuck by Haskell

3.1. 構文

3.2. Brainfuck との対応

3.3. 実行

4. まとめ

5. コード

Recentpages

Links