Zenn
🧠

令和時代のBrainf**kの基礎文法

2024/12/01に公開
初心者向け
esolang
Brainfuck
tech

はじめに

※本記事は、2020/12/23にQiitaに投稿した記事を移行したものです
これまでもBrainf**kについては色々書いてるのですが、令和ということで独断と偏見に基づきまとめてみます。

Brainf**kってどんな言語

第一印象

既にご存知の方もいらっしゃると思いますが、次のように見える言語です。

  • 記号だらけの言語
    プログラムとして意味があるのは +-<>[],. の8文字種だけなので記号だらけです
  • 何やってるのかよく分からない
    例えば次のコードは改行無しの Hello, world!出力 ( 出展:Code Golf Stack Exchangeの記事 ) です。これが特に高難易度な例というのもありますが、慣れないとコードから動きを見切るのは難しく感じると思います。
    +[+[<<<+>>>>]+<-<-<<<+<++]<<.<++.<++..+++.<<++.<---.>>.>.+++.------.>-.>>--.
  • 組めると凄い
    何か知らないけど、競技プログラミングの場面等で、このBrainf**kで正答するコードを書いてる人がいて「なぜそんなことができるんだ!?」と驚く/驚かせる場面もあることでしょう。

実際には

上述の第一印象だけだと単なるネタ言語に見えなくもないですが、実は由緒正しくまた奥の深い、取り組みがいのある言語です。なぜかというと、

  • 8種類の命令だけで機能を実現する、非常にコンパクトで美しい言語仕様
  • 計算機科学上重要な概念であるチューリングマシンを再現したかのような動作モデルの言語
  • 一般の人でもインタープリタをある程度容易に実装することができ、しかもそれがチューリング完全性の実証に繋がる学術上の重要性
  • 競技プログラミングで有名なあのAtCoderでも使用可能な、実用メジャー言語の一角

と、これだけの条件を備えているからです。
ことに、動作を頭の中で推測しながらコードを組むことで、さながら詰碁や詰将棋のような頭のトレーニングになること請け合いです!
これは取り組まない手はありませんね!!

用途

ただ、現状、この言語を業務に取り入れている例は寡聞にして知りません。まだ時代が追い付いてきていないのかも知れません。
※プロBrainf**kerとしてスカウトにはいつでも応じる準備がありますので気軽にご相談を!!

そうすると、Brainf**kの中心的な用途は次のようなものとなるでしょう。

  • 各種競技プログラミングで問題をBrainf**kで解く
    まだ使用人口も少ない、密かなこれからの有望言語と言って良いでしょう。きっと。今ならBrainf**kerの中で上位に食い込むのも夢ではありません。
  • golferとしてショートコーディングに勤しむ
    コンパクトな言語仕様であるBrainf**kは、ちょっとした工夫やヒラメキがコードの長さに反映されます。大きくコード長を縮めた時の快感は、他の言語の比ではないと言えるでしょう。
    ※ゴルフ場として有名なAnarchy Golfには非常に強い人がいるのですが、どれだけ迫れるか挑戦するという醍醐味もあります。
  • その他開発等
    言語仕様がコンパクトなBrainf**kは、例えば算術演算1つ取っても、解くべき問題に応じて創意工夫の余地が色々あります。様々な場面に応じたアルゴリズムの開発、またQuineやセルフインタプリタの実現といったマイルストーンも見逃せないところでしょう。
    また、記号だらけな面を活かしてAsciiArt風にコードを構成する楽しみもあります。

実行モデル

  • モデル概要
    前述のチューリングマシンのような仮想マシン上で、コード上の各命令に沿った動作をさせることで目的を達成する、一種アセンブリの趣を持ったインタプリタ言語です。
  • 実行管理
    インタプリタは、コードの先頭から実行を開始し後方へ進んでいき、末尾に到達すれば終了します。ただし、実行位置がジャンプする命令が一部にあり、ループや分岐を実現しています。
  • 仮想マシン
    仮想マシンは1次元の配列めいた無数の「セル」を持っており、それぞれで整数データ ( 初期値 0 ) を保持します。これらセルに対して、インクリメント ( 1増加 )、デクリメント ( 1減少 ) を行い処理を進めます。
    一度に操作できるセルは1つのみですが、対象のセルを隣へ移していくことができます ( 便宜上「左右」で表現します )。
  • 入出力
    入出力は非常に平易で、標準入力・標準出力があるだけです。操作としても1バイト
    ずつの読み込み/書き出しとなっています。
    文字はコード ( ASCII/UTF-8 ) としての数値で扱います。文字を読み込んで処理対象のセルに数値を保存、あるいは処理対象のセルにある数値に対応した文字の出力、となります。

実行環境

環境の違い

Brainf**kのコードを実行するためのインタプリタは様々ありますが、仮想マシン部分の挙動で細かい違いがあります。コード実装上影響があることも多いため、どこに違いがあるかを把握し、普段使いをどれにするか決めておくのが得策です。
ポイントとしては次のようになります。

  • セルのbit幅
    セルに格納できる整数のbit幅であり、主に8bit(0～255)か32bitの2通りです。
    8bitだと大きめの数値が1セルに収まらないため、bit幅が大きい方が分かり易い面がありますが、8bitの場合、次項のwrap-aroundと絡めて非常にトリッキーな処理を組める可能性が広がります (上級者向け)。
  • wrap-aroundの可否
    wrap-aroundとは、セルの数値を 0 からデクリメントしてセルの最大値に、あるいは最大値からインクリメントして 0 にする処理を指します。
    許可されている場合は、疑似的に負の数を扱えることになります。すなわち、セルの最大値を-1と見做して利用できるということです。
  • セルの範囲
    実装によっては、移れるセルの範囲 ( 使えるセルの数 ) に制限があります。
    また、実行開始時のセル位置を左端として、そこから更に左に移る処理が禁止されている場合もあります。
  • EOF入力時の処理
    既にEOFを迎えていた ( 入力データが空の ) 場合、セルに保存されるEOF相当の値で違いが出る場合があります。主に 0 あるいは -1 ( セルの最大値を疑似的に表現したもの ) のどちらかになります。

処理系の違いについては、「各種サービスにおけるbrainfuck処理系について」が詳しいです。

開発環境

実際にBrainf**kのコードを書いた時、自分のPCにインストールしたインタプリタや、ideone.comのようなオンラインIDEで実行させても良いのですが、途中のコードの動きを追えるものの方が断然やり易いと言えるでしょう。

私が好んで利用しているのはAzicore氏のオンラインエディタで、環境の違いの調整や途中のセル状況のダンプ機能があります。
他にも探したところ、実行状況をトレースしてくれるオンラインBrainf*ckデバッガというページがあるようです。

また、自作の brainfuck の開発環境の紹介で紹介されているように、unidentifiedexe氏は高性能な専用エディタを自作して利用されています。

何かしら自分にあった開発環境を探してみるのが良いと思います。

基本文法

ここでようやくですが、Brainf**kの文法について説明します。しかしとても簡単なので、すぐ把握することができると思います。

命令

命令は +-<>,.[] の8種類だけです。しかも、機能的に分類するとたったの4分類となります。

  • インクリメント(+),デクリメント(-)
    対象のセルをそれぞれ1増加/減少させます。
  • セル移動 ( 左:<, 右:> )
    対象のセルを1つ移動します。
  • 入出力 ( 入力:,, 出力:. )
    入力の場合は、1バイトを標準入力から読み込み、対象のセルにコードの数値を保存します。EOFの場合は対応する数値 ( 0 or -1 ) を保存します。
    出力の場合は、対象のセルに保存されている数値をコードと見做し、1バイトを出力します。セルのbit幅が8bitより大きい場合は、下位8bitのみを使います。
  • 条件判定とジャンプ ( [,] )
    この命令のみ特殊で、必ずペア ( [→]の順 ) で記述する必要があります。入れ子も可能です。
    対象のセルが 0 の場合は ] の直後の命令へ、逆に非 0 の場合は [ の直後の命令へ移ります。
    つまり [,]で囲まれた部分がブロックのような扱いとなり、以下のような挙動となります。
    • ブロック到着時 ( [ )
      • 対象のセルが 0
        ブロックをスキップする
      • 対象のセルが非 0
        ブロック内の実行に進む
    • ブロック脱出時 ( ] )
      • 対象のセルが 0
        ブロックを脱出する
      • 対象のセルが非 0
        ブロックの先頭に戻って再実行する

最後の [,] だけ少し複雑ですが、これが実際にBrainf**kでコードを組む時の柔軟性に繋がっています。

コメント・変数

前項で8種類の命令を紹介しましたが、それ以外の文字は全てコメントとして扱われます。改行や空白文字もです。
なので、コード中に色々解説を自由に書くことができます。コメントの充実は大事ですね!

ただ逆に、全てのデータはセルで管理しているので、他の言語にあるような変数というのはBrainf**kにはありません。
とは言え、何がどのようなデータを表しているか分かるようにしておきたいという需要があると思います。そういった場合には、セルの位置に自分で名前をつけて、コード上のコメントとして ( この命令を実行する時の対象のセルは○○という名前にする、等 ) 分かるようにしておくのが良いと思います。

インデント

Brainf**kは、当然ながらインデントに関して全くの自由です。
ただ、[,]の組がコードブロックを構成するような機能を持つため、[が現れるたびにインデントを深く、]でブロックが終了するたびにインデントを浅くしていく書き方をすると見やすいと思います。

取り組み方

初めての人は

この記事で基本文法を紹介していますが、それだけで実際にどのようにコードを組むか、初めてでは想像し辛いと思います。
そこで、過去に連載した講座記事が、Brainf**kの記事一覧にありますので、まずこれでちょっとしたコードを書いてみるのが良いと思います。

また、Brainfuck Text Editorというサイトでは、指定の文字列を出力するBrainf**kコードを自動生成してくれます。
コードを見てその動きを考えてみたり、暗号めいた気分でコードをSNSに貼り付けてみたり、楽しみ方は色々です。

慣れてきたら

AtCoderのコンテストの中で、ABCであればA問題やB問題がBrainf**k用として手頃な問題として用意されていることが多いです。
こういった問題にチャレンジして腕を磨くのが良いでしょう。時にはD問題,E問題レベルでも解ける場合があり、解けた時の嬉しさはとても大きなものがあります。

また、以下のサイトにあるコード例を見てできることを増やしていくのも良いでしょう。

  • Brainfuck algorithms
    典型的な各アルゴリズムを実装するコード例を紹介しています
  • Brainfuck constants
    狙った数値を効率良く作る方法が一覧で紹介されています

その後は

AtCoderでのAC数を稼ぐも良し、anarchy golfでコードゴルフに挑戦するも良しです。

例えばBrainf**kセルフインタプリタを実装した話のように、セルフインタプリタを実装してみるのも面白いかもしれません。楽しみ方は人それぞれかと思います。

終わりに

ということで、Brainf**kについて色々書いてみました。
これによってBrainf**kを楽しむ方が増えてくれると嬉しいなと思います。

Discussion