BrainFuck Part.3 <[+-.,]>

■ このスレッドは過去ログ倉庫に格納されています
2009/01/08(木) 12:09:18
BrainFuckとは
　難解プログラミング言語の一つ。
　ｵｼｼﾒｻｲﾄはhttp://www.google.co.jp/

以下俺的見解
　・スレッドタイトルに全命令が入る素敵な言語。
　・1レス内に全命令のリファレンスが入る素敵な言語。
　　> ポインタをインクリメント
　　< ポインタをデクリメント
　　+ ポインタが示すメモリ位置のデータをインクリメント
　　- ポインタが示すメモリ位置のデータをデクリメント
　　. ポインタが示すメモリ位置のデータを出力
　　, ポインタが示すメモリ位置のデータに入力
　　[ ポインタが示すメモリ位置のデータがヌルなら対応する]までジャンプ
　　] ポインタが示すメモリ位置のデータがヌルじゃないなら対応する[までジャンプ

前スレ: BrainFuck Part.2 <[+-.,]>
http://pc11.2ch.net/test/read.cgi/tech/1177988460/

過去スレ: BrainFuck <[+-.,]>
http://pc11.2ch.net/test/read.cgi/tech/1036013915/
2009/08/20(木) 06:23:46
>>120
BrainFuckはチューリング完全だから、気合でなんとかすればよろし。
2009/08/25(火) 18:52:06
>>120
相対位置でできれば良いんじゃない？
2009/08/25(火) 23:08:59
まずは再入、再配置のライブラリを書いてみようか？

2009/08/26(水) 02:46:50
>>123
そうするとメタプログラミング
みたいになるんじゃないか？
2009/08/26(水) 11:09:01
中間言語→BFにコンパイルするコンパイラを作ればいいんじゃね
逆ポーランド記法な言語からのコンパイラならなんとかできるかな
2009/08/26(水) 11:30:45
>>125
だったらBFのソースを
全部その言語で書かなきゃいけなくなるんじゃ？
2009/08/26(水) 22:42:52
どうせ有限なんだから時間さえあればいける
2009/08/26(水) 23:31:10
ついでにBrainFuckを逆アセンブル？してCソースにするコンパイラもよろしく。
2009/08/26(水) 23:43:45
それは最適化しなくていいなら簡単
2009/08/27(木) 00:02:29
もちろん可能な限り元のコードの意味を推測して、それらしいコードを復元してほしい。
2009/08/27(木) 00:22:41
今JSでそういうの書いてる
2009/08/27(木) 17:47:54
期待
2009/08/27(木) 19:07:31
がんばってくれ
2009/08/27(木) 23:43:54
前スレより
http://www.clifford.at/bfcpu/bfcomp.html
A compiler for a c-like high-level language which generates brainf*ck code
2009/08/29(土) 21:39:59
まだか？
2009/08/30(日) 08:20:26
>>128
guy shirts
2009/08/31(月) 23:10:26
>134
linuxか・・・
2009/09/01(火) 23:56:37
BrainFuckでビジービーバーゲームをやるのも面白いかもしれない。
http://ja.wikipedia.org/wiki/%E3%83%93%E3%82%B8%E3%83%BC%E3%83%93%E3%83%BC%E3%83%90%E3%83%BC

ここでやるのはスレチかな？
2009/09/02(水) 07:09:25
>>138
ビジービーバーゲームって
http://www.infonet.co.jp/ueyama/ip/history/turing.html
でおｋ？
2009/09/02(水) 07:31:28
>>139
それはチューリングマシンの説明で、ビジービーバーゲームとは違う。ビジービーバーの要点は
＞停止するまでにﾃｰﾌﾟに 1 を最も多く出力するような n-状態ﾁｭｰﾘﾝｸﾞﾏｼﾝを見つけ出そう､というｹﾞｰﾑ
だよ。


2009/09/02(水) 07:43:26
>>140
だったらチューリングマシンで
1が多く出力される遷移関数を考えるってこと？
2009/09/02(水) 07:56:56
ビジービーバーゲームの説明はそれでおk。
普通はチューリングマシンでやるところをBrainFuckでやってみようと。
2009/09/02(水) 08:03:58
まず遷移関数をどうやって
BFプログラムに変換するかが問題だな
2009/09/02(水) 17:55:03
状態数は、BFでいえばコードのバイト数と似たようなもんだよ。
だから、

同じバイト数のBFコードで、
より大きな10進数を標準出力に生成する

こんな競技になる。
2009/09/02(水) 18:01:24
+[.]

じゃあかんの
2009/09/02(水) 18:24:18
>>145
それだと無限ループになって
つまらないだろ
2009/09/02(水) 19:06:13
つまんないけど最強だろ
2009/09/02(水) 19:10:37
ビジービーバーゲームでのプログラムは停止しなきゃいけないんだ。
じゃなきゃ比較なんて出来ないからな。
2009/09/02(水) 20:00:00
じゃこれ
[>+.]
ポインタがオーバーフローすれば止まる
2009/09/02(水) 20:03:58
>>149
でも、処理系によっては
ループするぞ
2009/09/02(水) 20:52:53
>>149
ビジービーバーを考えるときは、
テープの長さに限界は考えないよ。
2009/09/02(水) 21:58:45
後出しルールうざい
2009/09/02(水) 22:41:24
後出しルールって言うか>>138のリンク先に全部書いてあるのに読んでないのが悪いんだと思うんだが
2009/09/02(水) 22:51:29
てか、一般的なBFの話をするなら無限長のテープじゃないとダメだろ
実装ではしょうがないかもしれないけどさ
2009/09/02(水) 22:56:09
テープの長さが有限だとチューリング完全にならない
2009/09/02(水) 23:28:56
そうそう、実際の処理系じゃなくて理想の処理系で動かさないと。
2009/09/02(水) 23:37:01
なあ、詳しい人教えてくれ。
ある１００状態のチューリングマシンがあって、
そのチューリングマシンがΣ(100)ステップ後に停止したとする。
このチューリングマシンがΣ(100)ステップ後に停止することを証明しようとしたら、
その証明は少なくともΣ(100)文字程度のオーダーの長さになる。
これは正しい？

2009/09/03(木) 03:57:09
>>157
一番ゆるい条件を与えるならそうなるんじゃね。
オーダーは定数倍を無視するから。
遷移を全部書き出して示せばいいだけだからね。
159デフォルトの名無しさん
垢版 |
2009/09/04(金) 22:47:53
ほ
2009/09/06(日) 18:28:26
ho
2009/09/08(火) 00:22:48
h
2009/09/10(木) 07:01:39
ho
2009/09/10(木) 15:59:52
++++++[>++++++<-]>[>+>+<<-]>--->>++++
+++++[<+++++++++>-]<--------------.++
+++++++++.---.+++++.---------------.++
++++++++++++.--.++++.----------------.
++++++++++++++++<.>
2009/09/10(木) 19:50:09
>>163
グロ注意
2009/09/15(火) 22:01:45
ほ
2009/09/18(金) 23:51:37
+[ほ+]
2009/09/21(月) 19:44:06
ho
2009/09/22(火) 07:00:44
俺的にBrainFuckの文法に最小限の拡張を加えて最大限パワーアップさせるには
どうしたらいいか考えてみた結果次のようになった。
まず、メモリはテープではなく無限の高さを持つ2分木のようなものを想定。

L ポインタを2分木メモリの左の子へ移動
R ポインタを2分木メモリの右の子へ移動
U ポインタを2分木メモリの親へ移動
+ BFと同様
- BFと同様
. BFと同様
, BFと同様
[ BFと同様
] BFと同様

まあ、大体BFでlispのconsセルが使えるようなイメージ。

2009/09/22(火) 14:13:50
そんなもん普通のBFの範囲でできるがな
2009/09/22(火) 14:17:53
BFはチューリング完全だから
変わらないぞ
2009/09/22(火) 16:31:49
この拡張でコードが劇的に短くなる例が欲しいな
172デフォルトの名無しさん
垢版 |
2009/09/22(火) 17:20:27
んで、最終的にアセンブリやCになる・・・と
拡張＝BFの死なんだよな

過去ログの通り、拡張行為すればするほどBFの簡潔さが失われていき
別にBFを使う理由がなくなる
2009/09/22(火) 18:50:58
うだうだ言ってないでインタプリタとコンパイラかけ
500バイト以内で書けたら合格にしてやる
2009/09/22(火) 20:51:37
既出じゃね？
175168
垢版 |
2009/09/22(火) 22:56:17
んが。既出なのか。ま、既出でも全然不思議ではないけど。
一応このスレの中はチェックしたつもりだったけど
前スレはチェックしてないんだよね。

>>168のプログラム言語をBTBF(BinaryTree BrainFuck)と呼ぶとして、
BTBFのコードをBFのコードに変換するトランスレータを実装しろってのは
学生向け演習問題として良問じゃね？
2009/09/22(火) 22:59:16
>175
まだ出てなかったぞ
2009/09/22(火) 23:06:44
コード短くする役に立つとすればこんなのかなぁ
まあいらないけど

x 直前のコマンドを*p回繰り返す
* p=*p
& *p=p
c 最も近い前方の[にジャンプ
b 最も近い後方の]にジャンプ
178168
垢版 |
2009/09/22(火) 23:42:17
>>172
俺は拡張=BFの死とは思ってないんだよね。
シンプルさがBFの価値なのは同意だけど、
もっともシンプルなチューリング完全言語BFと
Cやlispといった高級言語の生産性の溝がどれだけあるかってのを
把握できるのもBFの存在価値だと思う。
だから「BF+α=lisp」のαの部分がどれだけあるのか、俺は興味があるです。

#どっちもチューリング完全だから等価って乱暴な議論はなしね。


2009/09/23(水) 00:05:02
純lispはBFと同じくらいシンプルだけど考え方が全然違うから
そんな+α的な物はない
180168
垢版 |
2009/09/23(水) 00:08:29
ないわけはない。
チューリング完全的に考えて。
極端な話、理屈の上ではBFでlispインタプリタは書けることになっている。
それがどれくらい大変か？と言う問題はある。
lispでBFインタプリタを書くのは簡単だけど、
BFでlispインタプリタを書くのはきつそう。
2009/09/23(水) 00:17:40
lispからbfに変換するプログラムは作れるんじゃないか？
2009/09/23(水) 03:42:27
LISPでBFのインタプリタが簡単ねえ
真面目にシンボルをASCIIのチャーチ数表現で取り扱えば同じかそれ以上に大変だと思うけどな
2009/09/23(水) 08:18:23
pure LISPだとBFよりもプログラム書くの難易度高いだろJK
184168
垢版 |
2009/09/23(水) 08:33:05
よくみたら純lispって書いてあるな。
てっきりclispのつもりで話してた。
2009/09/23(水) 09:12:38
>>168
便利かどうか試しに実装してみようと思ったら疑問がいくつか。
・2分木メモリは値を持つの？持たないとしたらポインタがconsを指しているとき
　入出力命令は何をすべき？
・+-で指すリニアなメモリとLRUで指す2分木メモリの空間はまったく別のもの？
　ていうか+-廃止すべき？

自分的にはノーアイデアなんだけど、BFくらい最小のLispができそうですごく面白そうだとは思う。
186168
垢版 |
2009/09/23(水) 10:30:02
メモリは値を持ちます。
後は通常のBFと同じ。
187デフォルトの名無しさん
垢版 |
2009/09/23(水) 10:47:01
まずはhello worldから始めろ
プログラミング言語として使えないなら机上の空論
2009/09/23(水) 10:49:15
この板ではチューリング完全という言葉がたまに登場するが、
もちろん、このスレで使ってる人たちも、意味とか前提とか
分かって使ってるよね？
189185
垢版 |
2009/09/23(水) 12:19:47
あ、<>と+-を勘違いしてた。<>の代わりにLRUということか。
2009/09/23(水) 16:29:57
>>188
説明して
2009/09/23(水) 16:43:51
入出力が便利になれば使い道はあると思うとかは考える
でも、それじゃ駄目なんだよな
BFとは別物として考えなきゃいけなくなる
2009/09/23(水) 16:53:57
システムコールは欲しいな
2009/09/23(水) 19:48:01
BFってpure LISPほど純粋じゃないよな。
入出力命令なんてあるし。
ある意味入出力命令がシステムコールってことになるんじゃね。
2009/09/23(水) 19:51:53
>>193
それはbfが関数型言語じゃないから
純粋とか言う問題じゃないんじゃないか
2009/09/23(水) 21:26:57
BFのシンプルな体系を壊さずに拡張する方法としては
負の方向のメモリマッピングにコンソール(.,)以外の
I/Oを割り当てることかな
[-1]に数値をストアしておいて
[-2]の位置で+-すると[-1]の回数beepとか
[-3][-4]に数値をストアしておいて
[-5]の位置で+-すると[-3][-4]の座標の白黒が反転するとか
2009/09/24(木) 01:22:24
入出力命令をin,outにすればいい
>+++++++++[-<++++++++++>]<++++++, //in 60h
197185
垢版 |
2009/09/24(木) 02:13:09
>>168 の提案した奴を作ってみたけど、面白い使い方がなかなか見つからないなあ。
実際のリスト構造はともかくとして、いろいろ遊んでみると、メモリ空間がL-UとR-Uの
2次元になった、という印象。可能性はすごく感じるので、なんとかしたいのだが。
198168
垢版 |
2009/09/24(木) 05:53:17
消費メモリが定数なアルゴリズムだとBTBFの有り難味はないかもね。
実行中にバンバンnewするようなプログラムや複数の可変長配列を使うアルゴリズムが
いくらか書きやすくなるんじゃないかとは思ってる。
あと、関数コールの機構もBFで実装するのはきつくても
BTBFならもしかしたらBFよりずっと楽にいけんじゃね？
2009/09/24(木) 21:05:22
実装は既存のBF処理系に
L: p*=2;
R: p=p*2+1;
U: p/=2
を付け加えて、ptrの初期値を1に修正するだけだな
2009/09/27(日) 23:03:26
ところで、2分木を綺麗にグラフィカルに表示するライブラリって何かいいのある？
2009/09/27(日) 23:20:15
BFスレでその話題を振るココロは？
2009/09/27(日) 23:43:25
>>168をもうちょっと見やすくしたくて。


2009/09/27(日) 23:56:13
そもそもBFで書かれたライブラリなんて存在するのか？
2009/09/27(日) 23:57:21
まずbfはライブラリを作ること自体困難だろ
2009/09/28(月) 01:51:09
まずは整数の四則演算ライブラリからだな
ライブラリというかコードスニペットレベル？
2009/09/28(月) 07:02:38
前スレであったみたいに
どこのメモリに数値を入れて
どこのメモリに答えが返ってくる
って感じにすると良いんじゃない？
2009/09/29(火) 02:17:13
call
2009/09/29(火) 02:31:22
任意のシステムコールさえ呼べれば何とでもなる
敢えて関数呼び出し機構を命令に加える必要はない
2009/09/29(火) 03:23:00
文字列やポインタを渡さなくちゃならないシステムコールはどうするんだ
2009/09/29(火) 09:22:16
システムコールとシリアル通信すればいいよ
2009/09/29(火) 10:00:05
VRAMの上で走るBFを、
標準入出力から他のBFプロセスで制御すればいいんじゃね…？
212デフォルトの名無しさん
垢版 |
2009/09/29(火) 12:15:04
それをBFの機能と言えるかが問題だな
バイナリデータですらシステムコールが可能と言えてしまうぞ
2009/09/29(火) 18:41:29
BFのデータセグメントをVRAMに置けっ場解決するのか?
ダブるバッファリングは無理か
2009/09/29(火) 19:54:18
もうbf用のOS作ったら？
2009/09/29(火) 20:22:16
OSにBF向けのインターフェースがあればいいわけだな
0番地に+すると1番地の番号のシステムコールを2,3,4,...番地の値を引数にして呼び出すみたいな
2009/09/29(火) 20:26:54
そうすればハードディスクとかメモリとかにアクセスできるな
解析とかも簡単になるんじゃない？
2009/09/29(火) 22:14:03
まずはリンカとローダだろ。
2009/09/30(水) 02:09:42
コード空間とメモリ空間が分離されてるからリンカやロダは不要
2009/11/11(水) 22:18:35
何で
2009/11/19(木) 23:41:50
brainfuckって英語でどういう意味ですか？
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況