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/03/24(火) 18:17:48

>>91
-<[<>+.,

**デフォルトの名無しさん** · 2009/03/24(火) 19:15:54

>>92
[<+][,.,

**デフォルトの名無しさん** · 2009/03/26(木) 21:34:05

+　→　いろはにほへと
-　→　ちりぬるを
>　→　わかよたれそ
<　→　つねならむ
[　→　うゐのおくやま
]　→　けふこえて
.　→　あさきゆめみし
,　→　ゑひもせす
濁音・半濁音・小文字は清音と一緒
「ん」はスルー

**デフォルトの名無しさん** · 2009/03/27(金) 04:37:11

ルール考えるのはいいけど、
それで自分でプログラム書いてみろってばさ。

**デフォルトの名無しさん** · 2009/03/28(土) 15:17:10

Urban Muellerさんに言ってるんだな

**デフォルトの名無しさん** · 2009/03/30(月) 23:42:15

もう痴漢ネタは秋田

**デフォルトの名無しさん** · 2009/04/10(金) 11:23:47

ほしゅ

**デフォルトの名無しさん** · 2009/04/16(木) 22:58:24

ほしゅう

**デフォルトの名無しさん** · 2009/04/25(土) 15:59:46

ごしゅう

**デフォルトの名無しさん** · 2009/05/08(金) 00:39:19

じ

**デフォルトの名無しさん** · 2009/05/15(金) 21:03:39

**デフォルトの名無しさん** · 2009/05/17(日) 20:47:00

**デフォルトの名無しさん** · 2009/05/17(日) 23:05:24

> > > > > >

**デフォルトの名無しさん** · 2009/06/04(木) 21:57:56

無ネタ

**デフォルトの名無しさん** · 2009/06/13(土) 16:24:34

+++[>+++<-]>[>+>+<<-]>->>++++++++++[<++++++++++>-]<------------.++++++<.>.<.>--.++<.>

**デフォルトの名無しさん** · 2009/06/20(土) 16:17:42

**デフォルトの名無しさん** · 2009/06/22(月) 01:30:36

、

**デフォルトの名無しさん** · 2009/08/02(日) 21:49:41

　　　　　　　　　　 _.｡ｬぁて丕刀ﾌ7ゎ｡._
　　　　　　　　 ,.ィ炙ヲ㌍≠┴⇒弍j込ｽ＞｡
.　　　　　　　 ,ｨ升ｦナ'´ 　　　　　｀ﾞ'＜弖心、
.　　　　　 ;夕ﾌア´　　　　　　　　　　＼ﾎi心.
　　　　　んfiУ　　　　　　　　　　　　　　　　▽ij∧
　　　　从j'Y　　　　　　　　　　　　　　　　　 ∨iハ
. 　　　斤W　　　　　　　　　　　　　　　　　㌣い
　　　　　|友ｶ　　　　　　　　　　　　　　　　　　　 }ｿ川
. 　　　い叭　　　　　　　　　　　　　　　　　　　仄ガ
.　　　　　Ｗi从　　　　　　　　　　　　　　　　　　从ﾉﾘ
.　　　　　 ∀t△　　　　　　　　　　　　　　　　 ∧fﾘ/
　　　　　　ﾞﾏじへ、　　　　　　　　　　　　　／リiУ
　　　　　　　＼夊i㌧､_ 　　　　　　 ,.イ!刋／
　　　　　　　　　`マ才i｢≧ｪ｡。．。｡っ夭テ少'ﾟ
　　　　　　　　　　　｀ﾟ'' ミ芝玉竺壬云=‐'´
　　　　　　　　　　　　　￣￣

**デフォルトの名無しさん** · 2009/08/03(月) 22:46:35

一応BFとして動くな

**デフォルトの名無しさん** · 2009/08/03(月) 23:31:46

[と]の個数があってればなんでも一応動くだろ

**デフォルトの名無しさん** · 2009/08/03(月) 23:52:00

個数が合っててもネスト構造がおかしかったら処理系によっては動かないだろ

**デフォルトの名無しさん** · 2009/08/04(火) 00:49:19

あー言い間違えた。そうそうそういうことが言いたかった

**デフォルトの名無しさん** · 2009/08/04(火) 16:49:05

というかム板じゃない他スレにも貼ってあったから無視したが
これはコードだったのか

**デフォルトの名無しさん** · 2009/08/04(火) 17:49:22

BFコードとして解釈できないレスの方が珍しい

**デフォルトの名無しさん** · 2009/08/04(火) 19:41:55

処理系によっては動くおかしなネスト構造ってどういうやつ？

**デフォルトの名無しさん** · 2009/08/04(火) 21:46:45

[ ] ] [ [ ]
とかじゃね

処理系によっては過剰の ] をプログラムの終了と解釈するとかもあるので
そのような処理系の場合は正常に終了する

**デフォルトの名無しさん** · 2009/08/04(火) 21:47:47

ん、ちょっと言い間違えた
終了するかはともかく、正常に実行される

**デフォルトの名無しさん** · 2009/08/18(火) 21:46:42

BrainFuckでライブラリを書けば、どんな言語、どんな環境にも極めて簡単にポーティング可能！
BrainFuckライブラリを充実させることこそ我々の急務ではないだろうか！

**デフォルトの名無しさん** · 2009/08/18(火) 23:36:08

再入可能どころか再配置可能も怪しいぞ

**デフォルトの名無しさん** · 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
一番ゆるい条件を与えるならそうなるんじゃね。
オーダーは定数倍を無視するから。
遷移を全部書き出して示せばいいだけだからね。

**デフォルトの名無しさん** · 2009/09/04(金) 22:47:53

ほ

**デフォルトの名無しさん** · 2009/09/06(日) 18:28:26

**デフォルトの名無しさん** · 2009/09/08(火) 00:22:48

**デフォルトの名無しさん** · 2009/09/10(木) 07:01:39

**デフォルトの名無しさん** · 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

**デフォルトの名無しさん** · 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

この拡張でコードが劇的に短くなる例が欲しいな

**デフォルトの名無しさん** · 2009/09/22(火) 17:20:27

んで、最終的にアセンブリやCになる・・・と
拡張＝BFの死なんだよな

過去ログの通り、拡張行為すればするほどBFの簡潔さが失われていき
別にBFを使う理由がなくなる

**デフォルトの名無しさん** · 2009/09/22(火) 18:50:58

うだうだ言ってないでインタプリタとコンパイラかけ
500バイト以内で書けたら合格にしてやる

**デフォルトの名無しさん** · 2009/09/22(火) 20:51:37

既出じゃね？

**168** · 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 最も近い後方の]にジャンプ

**168** · 2009/09/22(火) 23:42:17

>>172
俺は拡張=BFの死とは思ってないんだよね。
シンプルさがBFの価値なのは同意だけど、
もっともシンプルなチューリング完全言語BFと
Cやlispといった高級言語の生産性の溝がどれだけあるかってのを
把握できるのもBFの存在価値だと思う。
だから「BF+α=lisp」のαの部分がどれだけあるのか、俺は興味があるです。

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

**デフォルトの名無しさん** · 2009/09/23(水) 00:05:02

純lispはBFと同じくらいシンプルだけど考え方が全然違うから
そんな+α的な物はない

**168** · 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

**168** · 2009/09/23(水) 08:33:05

よくみたら純lispって書いてあるな。
てっきりclispのつもりで話してた。

**デフォルトの名無しさん** · 2009/09/23(水) 09:12:38

>>168
便利かどうか試しに実装してみようと思ったら疑問がいくつか。
・2分木メモリは値を持つの？持たないとしたらポインタがconsを指しているとき
　入出力命令は何をすべき？
・+-で指すリニアなメモリとLRUで指す2分木メモリの空間はまったく別のもの？
　ていうか+-廃止すべき？

自分的にはノーアイデアなんだけど、BFくらい最小のLispができそうですごく面白そうだとは思う。

**168** · 2009/09/23(水) 10:30:02

メモリは値を持ちます。
後は通常のBFと同じ。

**デフォルトの名無しさん** · 2009/09/23(水) 10:47:01

まずはhello worldから始めろ
プログラミング言語として使えないなら机上の空論

**デフォルトの名無しさん** · 2009/09/23(水) 10:49:15

この板ではチューリング完全という言葉がたまに登場するが、
もちろん、このスレで使ってる人たちも、意味とか前提とか
分かって使ってるよね？

**185** · 2009/09/23(水) 12:19:47

あ、<>と+-を勘違いしてた。<>の代わりにLRUということか。

**デフォルトの名無しさん** · 2009/09/23(水) 16:29:57

>>188
説明して

**デフォルトの名無しさん** · 2009/09/23(水) 16:43:51

入出力が便利になれば使い道はあると思うとかは考える
でも、それじゃ駄目なんだよな
BFとは別物として考えなきゃいけなくなる