Befungeのすゝめ

この記事について

以前の記事でBefungeを唐突に導入したが、補足記事としてBefungeを取り巻く環境、インタプリタ実装の所見、単なる難解プログラミング言語に留まらないポテンシャル等について語りたい。

Befungeについて

Befungeの言語仕様と簡単な歴史は難解プログラミング言語wiki esolangs に詳しい。Wikipediaの記述は粗いので、実装の参考にする際はesolangsに掲載されているBefunge98の仕様を読むのがいいだろう。暗黙になっている例外の扱いは、いくつかの実装を読まなければならない。

Befungeは一部でカルト的な人気を持つ言語で拡張のバリエーションが豊富であり、それらの総称をFungeと呼ぶことがある。ここでは一番単純で有名なBefunge-93をBefungeと呼称する。多くのBefunge拡張はこのBefunge-93で予約されてない領域に各々好き勝手な命令や空間を割り当てる。Befunge-93の93は93年の意、それなりに歴史のある言語である。

Hello Worldを読む

基本知識

上下左右の方向指示があって、^,v,<,>に対応し、デフォルトでは左上から右向きに突入する形で評価される。
つまり無限ループはこう。

>   v

^   <

わかりやすいね

ここで^のx座標がずれたりすると、>に戻らずIPがどっか飛んでしまう。つまり幅という要素が実装で絡んでくる。これにより、プリミティブな命令が実質的に一文字に制約され、多くの操作がスタックベースを介することになる。ここをレジスタで実装してもよいし、そういった拡張命令を時折実装されるが、やはり基本的な部分において、スタックが存在したほうが後述のクロスワード(上下左右の交差)で表現力が豊かであろう。

この命令が一文字という不自由さは、実装の簡易さという部分で拡張実装に非常に都合がよい。開発者から見れば、入力された段階でtokenizeがすでに殆ど終わっている状態になっていて先読み評価順序等の面倒な問題を一切気にせずに実装できるのだ。

せいぜい"の文字列モードとgridへのp,gでのIOの考察がいるくらいで、あとはダダダーと書いても実装できてしまう。

こういった事情からインタプリタ開発者にとって存外楽な言語である一方、やはりユーザーにとってはとっつきにくい言語ではある。そもそも難解プログラミング言語として考案されているし、その悪名が当然であるのは否定出来ないのだが、難解さの要素では

スタック経由の命令の呼び出し
まともな命名と、モジュール分割機能が無いため初見では意味不明

といった部分が多くを占める。逆に言えば、これらを障壁と思わないPwn大好き人間とかにとっては一考の価値のがある言語ではないか。

著者が主張したいのは、『Befunge自身は難解でもないし、むしろ潜在的になんかすごいんじゃないかと夢を見せてくれる、難解プログラミング言語界の金字塔なのである 』ということだ。

わかりやすく興味深い例を上げると、縦と横それぞれの方位について多義性を持つクロスワードコーディングが可能だ。ちなみにクロスワードコーディングというのは今考えた著者の造語である。誰か先に言ってそうだけど、コンセプトが伝わりやすい。正式な呼び方があるのかもしれないが、資料が散逸してるしあまり調べてないため知らない。

さて、実際にWikipediaのBefungeのページで出されているHello Worldを見てみよう。

v @_       v
>0"!dlroW"v 
v  :#     < 
>" ,olleH" v
   ^       <

ここで全てを解説しないが、最低限の命令の解説を導入する。

" はもう一度"が読まれるまでstring-modeに入り、文字を順にstackに積む
0-9 それぞれ数値をstackに積む命令になる。連続して並んでいても一桁の連続なので注意
, stackからpopし文字を出力する
: stackのtopをpushする
! stackからpopした値が0なら1,それ以外なら0をpushする
_ stackからpopした値が0なら左、それ以外では右へ実行の向きを変化させる分岐命令
| stackからpopした値が0なら下、それ以外では上へ実行の向きを変化させる分岐命令
# 現在の向きに従って次の命令をskipする
@ 終了

全ては紹介しない、と書いたが、殆どこれだけ覚えれば、あとは時々マニュアルを読むだけで大抵のプログラミングは出来るだろう。

さて、Hello Wolrdの解説だ。注目してほしい部分を[]で囲うことにする。

v @_       v
>0"!dlroW"v 
v  :#     < 
>" ,olleH"[v]
  [^]     [<]

この実装の面白い点は、"!dlroW" も、" ,olleH"も"でstring-modeに入った際には単に文字列として読まれるが、[^]からの出力ループが開始され、ここで縦向きに読まれた結果,は出力命令として働き、!は座標(1, 1)で積まれた0を基準に終端を判定する命令として働くという点だ。

この、同じ座標のsymbolの意味が読み取る向きで変化する構造はまさにクロスワードであり、魔法陣のようなプログラムを組めてしまうのである。 さらに 自己書き換え命令がサポートされており、 これを活用することでより奥深いコーディングが可能なのである。

ところで現実のクロスワードは原則として左から右、上から下だが、Befungeはどちらもあり得るのもポイントだ。

こういったテクニカルな奥深さは現実的にはややこしいだけ、という印象を抱くかもしれないが、縦や横に偏りがちなコードの情報密度を制御可能であるというのは、巨大ディスプレイでの開発で新たな意義を得るかもしれないし、上手く拡張命令を定義すれば何らかの実用性を見いだせそうではないか。ちょっと考えるだけでもQRコードの各点を構成するFungeコードとか、圧縮アルゴリズムを自分自身に適応するとか色々出来そうだ。

まあ、仕事に用いる道具として、という観点での意義は30年近くコミュニティが探し続けても……おそらく広く知られている内容はないが…… とにかくこの言語の面白さには関係がないことだ。

ちなみに使われているプロダクトが無いかというとそうでもなくて、難解プログラミング言語コミュニティで人気を誇る(らしい)Befunge-98拡張で書かれたIRCボットのfungot といったOSSも存在していて、なんとそのソースコードはTシャツに印刷しても収まるのだという。本当にそういうTシャツがあるのか探してみたが、適当にググった限りで写真が手に入らなかった。SUZURIで作ったらいいと思う。

Rust実装での設計の気持ちとか

ここからは前回の記事への実装面での補足となる

traitの命名規則

traitの命名規則(naming conventions)はここを参照した。

In Rust we have some categories:

**Imperatives** like io::Write, fmt::Debug, clone::Clone
**Agent nouns** like iter::Iterator, hash::Hasher  
**Nouns like** fmt::Binary, ops::Fn  
**Adjectives** like marker::Sized, panic::UnwindSafe  
**Preposition** like convert::Into, borrow::ToOwned

今回初めて知ったが、要するにDeriveの中に突っ込んで違和感が無い名前はこのいずれかになっている。例えばtraitの気持ちとしてはIOHandlerよりIOHandleになると自分は解釈した。

結果としてimplとforの関係の見通しがよくなったので、traitへ他言語でのInterfaceで用いる命名規則を利用している諸氏へはぜひオススメしたい。

細かいコード設計のあれこれ

commandの実装にはボイラーテンプレートが登場するものの、あえて現段階では型パズルでの一般化をしていない。
とにかくlifetimeについて一旦整理し、スレッド関連の見通しをよくしたかった。型での表現はいけそうなら段階的にやっていく。
現状適当にmutexを使っている悪影響が見え隠れしていて、整理を必要としている。
層の名前は適当。ドメインとかアーキテクチャについてもっと真面目に考えるともっといい名前があると思うが、現状スクラップビルドなのでそこまで拘っていない。

命令を手軽に増やせる拡張性を最も重視した設計を志向した。結果としてChatGPTやOllamaなどのLLMの活用もやりやすくなった。ただ、自分がコメントで書いたヒントまで後からみるとLLMがやったように見え、イキりOSSとしてちょっと嫌な気持ちになり、あとからいくつか消している。

pub trait CommandResolve {
    fn get_command(&self, cmd: char) -> Option<Arc<dyn Command + Send + Sync>>;
}

pub struct CommandRegistry {
    commands: HashMap<char, Arc<dyn Command + Send + Sync>>,
}

impl CommandResolve for CommandRegistry {
    fn get_command(&self, cmd: char) -> Option<Arc<dyn Command + Send + Sync>> {
        self.commands.get(&cmd).cloned()
    }
}

impl CommandRegistry {
    pub fn new() -> Self {
        let mut commands: HashMap<char, Arc<dyn Command + Send + Sync>> = HashMap::new();
        commands.insert('+', Arc::new(AddCommand));
        commands.insert('-', Arc::new(SubtractCommand));
        commands.insert('*', Arc::new(MultiplyCommand));
        commands.insert('/', Arc::new(DivideCommand));
        commands.insert('%', Arc::new(ModuloCommand));
        commands.insert(':', Arc::new(DuplicateTopCommand));
        commands.insert('\\', Arc::new(SwapCommand));
        commands.insert('$', Arc::new(DropCommand));
        commands.insert('.', Arc::new(PrintNumberCommand));
        commands.insert(',', Arc::new(PrintCharCommand));
        commands.insert('@', Arc::new(TerminateCommand));
        commands.insert('t', Arc::new(ThreadCommand));
        commands.insert('!', Arc::new(LogicalNotCommand));
        commands.insert('_', Arc::new(HorizontalIfCommand));
        commands.insert('|', Arc::new(VerticalIfCommand));
        commands.insert('>', Arc::new(RightCommand));
        commands.insert('<', Arc::new(LeftCommand));
        commands.insert('^', Arc::new(UpCommand));
        commands.insert('v', Arc::new(DownCommand));
        commands.insert('p', Arc::new(PutCommand));
        commands.insert('g', Arc::new(GetCommand));
        commands.insert('"', Arc::new(StringModeCommand));
        commands.insert('&', Arc::new(ReadNumberCommand));
        commands.insert('~', Arc::new(ReadCharacterCommand));
        commands.insert('`', Arc::new(GraterThanCommand));
        // 数字コマンド
        for digit in 0..=9 {
            commands.insert(
                char::from_digit(digit, 10).unwrap(),
                Arc::new(DigitCommand::new(digit as usize)),
            );
        }
        Self { commands }
    }
}

commandのオブジェクト管理部分。Arcによって共有された参照を管理している

命名に関して余談

上記のCommandRegistryで行っているような、大量のオブジェクトをFactoryで必要になる度に生成するのではなく事前にKey-Value Mapなどに集約させ参照させる実装パターンをSingletonに対してMultitonと呼べるが、直接名前に突っ込むことが出来ないのでそこまで知られておらずちょっと悲しい。

こういった集約を担う構造体(クラス)宣言にManagerを使わないという原則を守るだけで全権委任大使の誕生を防ぐことが出来て、コードの見通しが良くなるといった経験則が知られており、オススメである。

BeFungibleにおけるBefunge実装の現状、拡張の予定

セルオートマトン的なコーディングのしやすさ、という観点で徐々にBefungeから離れて最適化していくと思うが、出来るだけBefungeで利用可能な資産も両立したい。

main直pushというカス運用しているが、ある程度固まったらbranchを分ける
とりあえず(dx, dy)を引数にした t は動く。
step時のstdinの扱いはケアする必要がある。
マルチIP(←→↑↓)は多分まだ不安定。他の部分終わったら手を付ける
sでsyscallを呼べるようにしたい
includeのような命令を三次元セルとして扱うのは直感的に正しい気がするので、模索したい

といった感じ。そもそも最近コーディングスキルを問われる機会が多かったので、適当な題材として作ったのだが、思ったよりも二次元コーディングの奥深さに魅了されたという経緯があり、さっさと転職とかにケリ付けて続きをやりたい。

douro log