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/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って英語でどういう意味ですか？
2009/11/20(金) 00:06:17
のーみそこねこね
2009/12/03(木) 18:18:34
　　　　　　 ＿＿＿
　　　　　／　　 　 　＼
　　　 ／　　　⌒ 　 ⌒＼
　　／ 　 　 ,（⌒）　（⌒）､＼　　ひとりＳＭセット買ったお
　　| 　 　 /// （__人__）/// | 　　 　今夜は楽しむおｗｗ
　　＼　 　　　 ｀ ヽ_ノ　　 ／　　　
　　　　ヽ　　 　, ＿_ , イ
　 　 ／　　　　　　　|＿"＿＿__
　 　| 　　ｌ..　　　／l ＳＭグッズ l
　 　ヽ 　丶-.,／ 　|___＿＿＿___|
　　　/`ー､＿ﾉ　／　　　　　　／
　　　　　　　::　　　　　　　　　　 　 　 　.|ﾐ|
　　　　　　　　::　　　　　　　　　　 　 　 .|ﾐ|　　　　　　　　　　 ::::::::
　　　　　　　　　:::::　　　　　＿＿＿＿　|ﾐ|　　　　　　　　　 ::::
　　　　　　　　　　 ::　,. -'"´　　　　　　｀¨ー ､　　　　　　　::
　　 ::　　　　　 　 ／　　　,,.-'"　　　　　　ヽ　 ヽ、　　　 ::
　　　:: 　　　 ,,.-'"_　 r‐'"　　　　　,,.-'"｀　　　　　ヽ、　::
　　　:: 　　/　　　 ヾ (　　　 _,,.-='==-､ヽ　　 　 　 　 ヽ、
　　　:: 　　i へ＿__ ヽゝ=-'"／　　　 _,,>　　　　　　　　 ヽ　
　　 ::　　 ./ /　　＞ ＝'''"　￣￣￣　　　　 　 　 　 　 　 ヽ　
　　:: 　　/ .<_　ノ''"　　　　　　　ヽ　　　　　　　　　　　　 　 i
　 ::　　 /　　　 i　　　人＿　　　ノ　　　　　　　　　　　　　　.l
　　:: 　,'　　　　 ' ,_,,ノｴｴｴｪｪ了　　　　　　　　　　　　　　　/
　　　　i　　　　　　　じｴ='='='" ',　　　　　　　　　　　　　　/　::
　　　　',　　　　　　 (___,,..----U　　　　　　　　　　　　 ／　::
　　　　 ヽ、　　　　　　　　 __,,..　--------------i-'"　　::
　　　　　　ヽ､_　　　__ -_'"--''"ニニニニニニニﾆヽ　　 ::
　　　　　　　　 ｀¨i三彡--''"´　　　　　　　　　 　 　 ヽ　　:: 　
　　　　　　　　　 /　　　　　　　　　　　　　　　 　 　 　 ヽ　:: 　 　 　 　　　　　　　┼ヽ　 -|r‐､.　ﾚ　|
　　　　　　　　　/　　　　　　　　　　　　　　　　　　　　　ヽ::　　　　　　　　　　　　ｄ⌒)　./|　_ﾉ　 __ﾉ
2009/12/03(木) 20:02:48
あるある
2009/12/04(金) 05:07:08
perlでBrainfuckの処理系書いてみたんだが、
Brainfuckのプログラム書くより簡単でなんだか複雑な気分だ…
2009/12/04(金) 22:07:52
次はBrainfuckでperlの…
2009/12/04(金) 23:22:03
Brainfuckで日本語が扱えるようにはならないものか
2009/12/04(金) 23:35:38
そーすに記述したいってんでもあるまいし、扱えないことはないだろう？
2009/12/05(土) 00:08:59
ShiftJISなりUTF-8なりのバイト列を吐けばいいだけだよな
2009/12/05(土) 09:33:31
例えば、
：　で、ポインタの指している値とその次のポインタの値を2バイト文字として出力する。
；　で、2バイト文字を入力して、ポインタの指している値とその次のポインタの値に代入する。

ってのはどうよ?
2009/12/05(土) 11:01:11
.>.<と,>,<で十分じゃないか
231229
垢版 |
2009/12/05(土) 16:21:32
とりあえず実行してみた。

>++++++++++[<+++++++++++++>-]
+++[>+++++<-]>[<++++++++++++>-]<--->
>++++++++++[<+++++++++++++>-]
>++++[>++++<-]>[<+++[<+++++>-]>-]<<+>
>++++++++++[<+++++++++++++>-]
>++++++++++++++[<++++++++++++++>-]<+++++>
>++++++++++[<+++++++++++++>-]
>++++++++++++++[<++++++++++++++>-]<----->
>++++++++++[<+++++++++++++>-]
>++++++++++++++[<++++++++++++++>-]<+++++++++>
>++++++++++++[<++++++++++++>-]
>+++++++++++++[<+++++++++++++>-]<------->
>++++++++++++[<+++++++++++>-]<++++++>
>++++++++[<++++++++>-]<+++++>
>++++++++++[<+++++++++++++>-]<->
>++++++++[<+++++++++>-]<+
<<<<<<<<<<<<<<<
:>>:>>:>>:>>:>>:>>:>>:>>:


メモリに"こんにちは世界！"を表わす
82,B1,82,F1,81,C9,81,BF,82,CD,90,A2,8A,45,81,49
がメモリに積まれて、最後の方の"："命令で、Shift-JIS形式の文字が表示される。

作ってから思ったけど、これって既出？
2009/12/05(土) 17:03:48
うん。
2009/12/05(土) 17:46:50
>>229
Shift-JISを使うために新命令は必要ないってことわかってる？
入出力は1byteずつでも、解釈はまとめてやればいい。
実際そうしてShift-JISを扱えるBF処理系も存在する。
234デフォルトの名無しさん
垢版 |
2009/12/05(土) 22:50:53
馬鹿だなぁ
:>
が顔に見えるってギャグだろどうせ
2009/12/06(日) 10:05:30
海外風な顔文字か。
[:<]<
2009/12/06(日) 23:24:24
BFで : を .>.< に置き換えるBFプロプロセッサ書けばいいよ
2009/12/08(火) 12:47:34
まだBFなんてやってんのかよだっせー
時代は純粋関数型言語Unlambdaだぜ
2009/12/09(水) 03:11:58
>>237
そんなこと言うならBrainfuckユーザが容易にUnlambdaへ移行できるように
Brainfuck-to-UnlambdaトランスレータをUnlambdaで書いてくれｗ
2009/12/09(水) 18:02:48
bfユーザが理解できるようにトランスレータはbfで書こうぜ
2009/12/22(火) 13:47:48
#defineしまくればCでも書けるかな
2010/01/02(土) 17:42:21
esotope-bfcって凄いな
自分で作る気が失せる出来
2010/01/02(土) 17:58:44
>>241
見てきた
なんじゃあのオプティマイズ
2010/01/03(日) 00:13:20
まだまだだな
例示のプログラムのmやpはいらん
2010/01/03(日) 08:07:28
そのへんは削除するようにする（した）って書いてるよ
2010/01/09(土) 00:17:46
#include <stdio.h>

int main(int argc, char *argv[])
{
int c;

while ((c=getchar()) != EOF) {

while (c) {
putchar('+');
c--;
}
puts(".>");
}
}
2010/01/09(土) 02:25:08
俺にもHello Worldが作れた！
247245
垢版 |
2010/01/09(土) 19:43:17
修正
#include <stdio.h>

int main(int argc, char *argv[]){
int c,d;
int l = 0;

while ((c=getchar()) != EOF) {
d = c-l;
if (d>0) {
while (d--) {
putchar('+');
}
} else {
while (d++) {
putchar('-');
}
}
puts(".");
l = c;
}
}
2010/01/10(日) 04:01:44
最適化されたBFのソースを吐くなら、まだ修正する意味もあるかもしれないな。
2010/01/15(金) 16:34:45
最小ブレインファック問題の計算複雑性ってどの程度？
250デフォルトの名無しさん
垢版 |
2010/01/16(土) 09:18:43
http://d.hatena.ne.jp/KeisukeNakano/20070626/1182879045

凄いんだが、何を行ってるのか分からない( ´∀`)ﾊﾊﾊ
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況