Talk:Brainfuck

From Esolang

Jump to: navigation, search

Contents

[edit] Interpreter/compiler speed test

I prefer putting newer comments up top...

Seeins as there are so many interpreters/compilers, I reckon that each of them should go through certain brainfuck speed tests. Because sometimes speed is an issue. Here's some code: 

++++++++[->-[->-[->-[-]<]<]<]
>++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>
  • Interpreters:
  • My interpreter can do that in 10.5 seconds.
  • QDB can do that in 11.5 seconds.
  • The "Optimizing BF interpreter", claiming to be "a very fast C interpreter", takes longer than 2 minutes. I stopped timing then.
  • BFDB was rigged with errors so I couldn't test it.
  • YABFI.C turns out to be merely a code checker.

I believe that QDB takes the cake as mine uses a function array but is only a second faster.

What else should I check? --GreaseMonkey 08:04, 26 Jan 2007 (UTC)

I agree. A common program that could be used to benchmark compilers would be nice.
Mine can do it in about 4 seconds with an 8bit cell size and about 39 seconds with a 16bit cell size.
If I have the time I will run your code against as many compilers as I can and I'll return with the results. --xfx 06:52, 18 April 2007 (UTC)
You may want to check these two as well - bff4 and bff. Also this change is mine, it said that bff (which is mine) was fastest in its class, which was correct at some point, but it is no more. Oleg's version takes the optimization further and it is now fastest from those I personally played with. Apankrat 18:30, 18 April 2007 (UTC)
Not very long for mine, which I got from http://4mhz.de. Precise time it doesn't say - I guess somewhere in the region of two seconds. --IslandHopper973 20:19, 26 April 2007 (UTC)
Are all above mentioned programs compilers? I think this info is missing. My BrainSub compiler do it in 0.05 seconds with 8bit cells and 3 min. 37 secs. with 16bit cells. Aacini 03:50, 18 July 2007 (UTC)
Hehe. Dont you see guys that this test is very stupid, because it assumes wrapping integers (this is not portable dialect of brainfuck). So the quickest interpreter would be the one which implementation uses the smallest number of bits for a memory cell. I can propose something like the following (some comparison for this program done for bff and bff4) 
>+>+>+>+>++<[>[<+++>-
 >>>>>
 >+>+>+>+>++<[>[<+++>-
   >>>>>
   >+>+>+>+>++<[>[<+++>-
     >>>>>
     >+>+>+>+>++<[>[<+++>-
       >>>>>
       +++[->+++++<]>[-]<
       <<<<<
     ]<<]>[-]
     <<<<<
   ]<<]>[-]
   <<<<<
 ]<<]>[-]
 <<<<<
]<<]>.
And yet another good test would be to run a trivial program with a stack of brainfuck self-interpreters. --Mazonka

[edit] Arbitrarily large numbers

"In fact, Brainfuck can be Turing-complete in two different ways. Turing-completeness is achieved when the number of cells in memory is infinite, or when individual cells can contain arbitrarily large numbers."

What's the minimum number of arbitrarily large cells needed for this to be true? It obviously isn't the case with one. --Graue 15:35, 9 Jun 2005 (GMT)

Theoretically, 2 cells (cf Minsky machine); Frank Faase has a proof using 5 cells. --Chris Pressey 18:33, 9 Jun 2005 (GMT)

[edit] Implementation links

There are a huge amount of Brainfuck implementations out there, and listing them all in the main article might be a bit much. But it would be nice to have them listed too. Maybe we should make a separate Brainfuck implementations article where they could be listed? --Rune 01:24, 12 Jun 2005 (GMT)

Why don't we mirror all the brainfuck implementations in the files archive with links to their original URLs? --Graue 13:31, 12 Jun 2005 (GMT)
We could do that, but I think it would be better to have the list of links in the wiki, as it makes editing them so much easier. Mirroring them, however, is a very good idea. There might be some licensing issues, though. --Rune 14:27, 12 Jun 2005 (GMT)
I've added the link to BlueFern an IDE a friend and I made back in 2002/3. Feel free to mirror it, if I can find the source code I'll post it. - Peregrine

I've written an implementation of brainfuck for the HP48gII calculator. It may work on other HP calculators too, but I can't test it on any other, as I only own a 48gII. Anyway, here's the link: http://sp3tt.i.ext.as/bf.txt

[edit] Extensions -- '!' is convenient, but not needed

It seems to me that the remark about an extension like '!' being *required* for a Brainfuck interpreter written in Brainfuck, is not correct. Although it would be ridiculously inconvenient, such an interpreter could be written to expect coded input, such as
1^a 0 1^b 0 1^c ... 00 1^A 0 1^B 0 1^C ... 00

where the first 00 terminates the program-string to be interpreted, and the second 00 terminates the input-string for that program. (0 and 1 are here bytes, and a byte-value of n is encoded as 1^(n+1) 0 -- a string of n+1 1's followed by a 0.)
--r.e.s. (r dot s at mindspring dot com)

Something 'symbol'/way is always required to separate the program from the input, just like this example of yours or '!'. Naturally there are several ways to do this, and the '!' "extension" isn't a must. It's just useful, common, and easy way to do it and fits well in brainfuck instruction set by its look. That's probably why it's in the article. Well, maybe the thing could be expresesd some other way in the Brainfuck entry. Perhaps I'll tweak it some day if nobody does that before me. --Keymaker

[edit] Difference between "no i/o" and "no i/o instructions"

I've edited the reference to Smallfuck and Smallfuck/F to distinguish between "no i/o" and "no i/o instructions".
--r.e.s. (r dot s at mindspring dot com)

Watch out, we have a Category:No IO, which means the same thing. I think I/O is generally taken to mean "something like stdin and stdout" around here, but maybe we could rename the category. --Graue 21:56, 29 Jun 2005 (GMT)
OK, but I'm interested in abstract machine-models that are so minimalistic that input and output may have nothing to do with anything like "stdin and stdout". E.g., i/o may be what's on the "tape" (before & after a computation) in a single-tape TM-like model, such as for the Brainfuck F language.
--r.e.s. (r dot s at mindspring dot com)

"No I/O instructions" could also be interpreted to the effect that I/O is performed by some means other than instructions, while it still may be the stdin/stdout kind of I/O. For example, the memory-mapped I/O of Fromage, or the function-mapping-input-to-output principle of Lazy K or LOLA. -- Smjg 13:01, 1 May 2007 (UTC)

OK, so that's not exactly how LOLA works, and you could debate what counts as an instruction in LOLA, but you get the idea. -- Smjg 13:05, 1 May 2007 (UTC)

[edit] Brainfuck's formal parent -- and formal proof of Turing completeness

Brainfuck appears to be a very minor informal variation of a formal programming language called P", introduced by C. Bohm in 1964 to describe a class of Turing machines that includes a UTM. (Thus providing a formal proof of Brainfuck's Turing completeness.) It has only four instructions -- the equivalents of '+<', '>', '[', ']', with bracket-matching, and no i/o instructions (since it is describing single-tape TMs). My reformulation of P" (for TMs with left-bounded tapes) is located here.

--R.e.s. 11:56, 10 Jul 2005 (GMT)

I've tried to clarify how *very* close part of brainfuck is to P%27%27. As I mention, Bohm's 1964 paper actually lists the basic programs for partial recursive functions using six symols precisely equivalent to brainfuck's +, -, <, >, [, ], which is surely worthy of note. (The issue is not whether brainfuck's creator knew of this. That part of brainfuck could well have been an independent re-creation.) But the fact of the formal relationship of brainfuck to P%27%27 immediately settles the Turing completeness question, for example.

--R.e.s. 19:58, 16 Jul 2005 (GMT)

I can't say anything about Bohm's 1964 until I read that paper, but when he cites it in 1966 he definately describes it as having only three components: λ, R, and (q). It seems strange that he would give two different formulations under the same name P’’, or that he would mis-cite himself. Are you certain that the six-symbol version doesn't have a different name?
Whether Urban knew about it or not influences whether it should be under "History" or "Related languages", and since it's not known whether he knew about it, and doubtful (since he didn't mention it,) I moved it out of "History". (I have reservations about the usage of the word "variation" for the same reason.)
Also, it's nice that P’’ provides another proof for Brainfuck's TC, and nice that it is both early and formal, but given that Brainfuck was pretty much defined to be TC ("if we ignore the size limits", as the readme says,) and that there are three proofs already available, I don't see there being much of a "question" to "settle" in that regard. (I'm also not certain what a "formal relationship" is or if it's meaningful for a language as informally defined as Brainfuck to have one.) --Chris Pressey 21:43, 16 Jul 2005 (GMT)
I'll try to address each of the points you raise.
First, Bohm's programming language P’’ uses the 4-symbol alphabet λ, R, (, ), where the instruction λ is equivalent to '+<', R is equivalent to '>', and ( ) is equivalent to [ ]. (I used square brackets in stating the definition previously, and there is also the inessential need of converting to a right- rather than left-infinite tape.) Bohm then defines three symbols "useful for the proof" that P’’ can compute any partial recursive function. These three he calls L, r and r' -- and they are the equivalents of <, +, and -, each defined in terms of his 4-instruction alphabet. He then procedes with the proof, constructing every program along the way in terms of the six symbols r r' L R ( ) -- in other words, precisely in symbols equivalent to the six brainfuck instructions + - < > [ ].
Second, our opinions seem to differ on what is included in the history of a programming language. In my opinion, a published article that actually exhibits extremely non-trivial "brainfuck" programs (differing from brainfuck essentially only in the choice of symbols) is part of the history of brainfuck -- irrespective of whether brainfuck's creator was aware of that part of its history. (The history of a thing, in this view, includes all of its occurrences in history -- by whatever name.) So I do think "formal parent" and "minor informal variation" are appropriate expressions.
Finally, it's because the essential part of brainfuck is a such minor informal variation of P’’ -- whose Turing completeness was *proved* about 30 years prior -- that the "parent" does more than merely offer "another proof" of the "child's" heritage. Also, I think it's incorrect to say that "Brainfuck was pretty much defined to be TC" with unboundedness as required, unless the author established its TC-ness at the time -- did he? Actually, the author's simple declaration that brainfuck is TC, with no proof given or cited (correct me if that's wrong), suggests that he indeed had some unstated reason to be confident that it was -- perhaps he was a beneficiary of Bohm's results, whether he knew them as such, or not.
--R.e.s. 23:40, 16 Jul 2005 (GMT)
OK, I'll try to respond to each of these points, in turn:
First: I believe you that it is the case, but I'd prefer to explicitly describe that as an extension/variation of P’’ to avoid confusion. (It's somewhat unfortunate that Bohm didn't give that intermediate language a name.)
Second: I don't see Brainfuck and "P’’-extended" sharing a history simply because they're isomorphic. For example, imagine that a Middle Egyptian papyrus is unearthed tomorrow, and it turns out to be a musical score for a folk tune which happens to have the same melody as the Beatles' "Yesterday", but in a different key. Does that piece of music become part of the history of the Beatles? That strikes me as absurd. Correspondingly, to me, the history of Brainfuck started when Urban conceived of it. If it is known that P’’-extended was one of his influences, that could be noted in the history - but that would be for causal reasons, not Platonic ones. And if it's not known, we shouldn't try to pass off conjectures as history.
Third: Whether Urban asserted the TCness of Brainfuck in the readme because he based it on P’’-extended and he knew P’’-extended to be TC, or simply because he felt it was obvious because it was quite similar to a Turing machine, I don't know. Both are possibilities; I certainly can't rule out the latter, having now seen any number of esolang descriptions where the author baldly asserts that it is TC on intuitive grounds, not bothering to give a proof.
(Further on that: under the assumption that Urban was telling the truth when he claimed to be writing as small a compiler as possible, it seems more likely that he was actually unaware of P’’ proper - otherwise he would have based Brainfuck directly on it instead of on P’’-extended, and would have shaved even more bytes off his compiler.)
Lastly, for clarity: when I said "pretty much defined", I meant that the author was clear that that was one of the intents of the language. Presumably, if there was some other aspect of the language that was not defined well enough to make it TC, the interpretation of it would naturally be "towards TC". (For example, that the array's finiteness should be interpreted as an artefact of implementation, rather than an inherent limitation.) In that light, proofs of Brainfuck's TCness are hardly "settling a question". --Chris Pressey 03:08, 17 Jul 2005 (GMT)
If an inscription in strange symbols, eventually decoded & determined indisputably to be a proof of Pythagoras' theorem, were found on an ancient rock on a planet in another star system, would that not be part of the history of Pythagoras' theorem? Surely the theorem doesn't depend on who formulates it, or when?
In the brainfuck/P’’ comparison, the fact is that there are extensive programs, written about 30 years before brainfuck, that are *literally* brainfuck programs -- except for a different choice of symbols, the programs have essentially the same syntax and semantics as brainfuck. --R.e.s. 08:56, 17 Jul 2005 (GMT)

[edit] Brainfuck Computer?

Has anybody ever tried to make a full PC-hardware-compatible computer design out of Brainfuck? I imagine it'd be... tricky. (And by PC-hardware-compatible I mean the external stuff: mouse, keyboard, monitor etc. as well as drives.) --Ihope127 17:55, 9 Sep 2005 (GMT)

Nope, that kind of thing hasn't been made yet. I can imagine it being quite difficult.. :) Would be nice. --User:Keymaker
So basically make a CPU that interprets BF directly? IMO (related to my discussion Talk:Brainfuck#EOLbelow), the question shouldn't be if you can make the HW BF compatible, but if you can build an entire OS from BF alone. (Which in theory you can... sort of. It would use up a lot of space!... I think.) --Stux 13:55, 31 Oct 2005 (GMT)
You lads haven't seen the BFCPU, have you? --ORBAT 14:18, 31 Oct 2005 (GMT)

I designed and built a brainfuck processor completely using standard 7400 series ICs and memory ICs (EEPROM for the ROM (instruction space)) and a high speed RAM. I built the circuit using 6 breadboards (the long type that radioshack sells, except it wasn't from radiosahck and all the breadboards were on the same panel. I didn't use the input and output instructions... instead I reserved an area in the RAM for use as I/O, so any device could be plugged into it and a driver could be written for it, although I never worked on that part. I simply had LEDs and at one point a 7 segment numeric display. If anyone wants to talk to me about this, email me at: jesrandall@austin.rr.com
I'm working on a new computer design, in an attempt to be able to build a from scratch computer capable of enough processing power to run some simple games (perhaps even NES type games), but atleast tetris...! It would be fun (for me) to build one out of relays, but I doubt there is any way I could get the speed high enough for this to work for a game. I was thinking about using pneumatic switches (custom built) to reach speeds possibly into the 1khz to 10khz range, but even still, that would not be fast enough for graphics (using conventional methods). So I will most likely be using discrete transistors and go for making a 250MHz. If any of you have ever tried to make a game in brainfuck you may notice that the game speed is very unstable due to the length of time required to move the pointer inside of loops and stuff like that. My friend made a graphical pong in brainfuck with a memory mapped graphics and as the ball reached the other side of the screen it slowed down more and more. If the brainfuck computer was fast enough you could calculate delta time to correct for this effect. Would a 250Mhz (250million instructions (+,-,>,<,[,],.,,)) / second brainfuck computer be fast enough to do anything "useful"? The brainfuck computer I originally made was 20Mhz, but required 5 cycles to do one instructions (yes it could have been optimized).. so only 4 million instructions / second... --(this comment by 70.116.28.222 at 17:48, 11 Feb 2007 UTC; please sign your comments with ~~~~)

[edit] Yet Another Brainfuck Implementation

Having - apparently - gone stark raving mad, I made YABI. Using TECO, no less.

It's still slightly buggy and doesn't do much checking, but programs like 99 Bottles, Hello World (duh), Fibonacci and such run quite happily.


Oh, and did I mention it's absolutely hideous when you remove all formatting? No wonder they say that TECO command strings look like line noise.

If someone wants to take a look, I can e-mail the monstrosity to them.


Tom Eklöf

--80.221.42.204 22:07, 27 Oct 2005 (GMT)

That sounds like it should be in The Esoteric File Archive. Why don't you send it to graue@oceanbase.org and I'll add it for you? --Graue 00:48, 28 Oct 2005 (GMT)

[edit] Who's familiar with TECO?

I started wondering how many people here have even heard of TECO, let alone used it? It'd be a shame to let my fine implementation (shameless plug, I know) go to complete waste :)

It's a great editor, in any case. Perfect for esolang fans, anyhow. Anything that actually parses and executes something like 

 @^U9/[]-+<>.,/
 <@:-FD/^N^EG9/;>

Can't be all that bad. That snippet translates to: save characters [] - + < > . , in register 9, search for all characters that don't match those and delete them.)


Tom Eklöf --11:50, 29 Oct 2005 (GMT)

Tom, I really hadn't heard of TECO until you mentioned it in your entry just now. It almost seems like it deserves an entry in this Wiki!--Stux 16:34, 29 Oct 2005 (GMT)

[edit] EOL

I don't get the following sentence: It is generally accepted that a proper Brainfuck implementation should return 10 for newline.

A brainfuck implementation never returns a newline, it just outputs whatever bytes the program tells it to. --Rune 00:32, 31 Oct 2005 (GMT)

The way I understand it, it means that when a CR LF (13 10) pair is encountered in input, it should return a LF (ie. 10). Probably so that BF programs written on UN*X (and other OSs that use a 10 for newline) and Windows (and other that use 13 10) would be compatible. Which is why it was also suggested that a 10 should always stand for a newline when outputting data, too.
Just my take on the matter --ORBAT 09:18, 31 Oct 2005 (GMT)
OK, but I must say I disagree that an implementation should alter the input in any way. The read instruction is used for both textual and binary data, so discarding a 13 because it precedes a 10 is not a good idea IMHO. People should write programs that handle the EOL issue instead of relying on the interpreter to do it. --Rune 11:52, 31 Oct 2005 (GMT)
That's very true. But how can a BF program check what system it's running on? It is quite clear that altering the input is a Bad Thing when dealing with binary data, just think about the DeCSS (oops. Is it even legal to say it out loud?) program. ASCII data is a different thing, however. Hmm... maybe switching to Unicode would help, it accepts a plethora of line terminators :) --ORBAT 13:24, 31 Oct 2005 (GMT)
A BF program can't check what system it is running on, but it is fully capable of discarding a 13 preceding a 10 if it wants to. I see no need for the interpreter to force that. Does anybody have an example where this is required? --Rune 13:42, 31 Oct 2005 (GMT)
BF may not know what system it's on, but it is conceivably not that hard to create some convention and make and external program that would tell BF what system it's running on or what type of file it is looking at before reading. Much like external library functions in C, C++. It just needs a convention, a rather complicated one at best, but a convention nonetheless. At the very least, IMO one could have an external app convert DOS text to UNIX text whenever it's appropriate (much in the fashion Cygwin Does) and have BF treat everything like UNIX input (in other words, text=binary). There is also no reason that that conversion program be written in BF, but eventually we'll come back to the issue of needing an external program to talk to and identify the OS and file type being issued. Ok that was long winded enough. --Stux 13:52, 31 Oct 2005 (GMT)
How about the interpreter checking what convention the OS uses, and then setting cell 42 to 255 if it's CR +LF, and to 252 if it's plain LF. Why 42, 255 and 252? Why the bugger not? It's BF, damnit. Don't take this too seriously :) --ORBAT 14:10, 31 Oct 2005 (GMT)
Almost every brainfuck program considers dec 10 as a new-line and doesn't output a 13 byte before it. Thus, almost none brainfuck programmer cares about any other new-line than the 10 byte. Making every input code check if the next two bytes are 13 and 10 would be annoying and pointless, and in almost every case would result to much less elegant code/solutions. Personally I will use only dec 10. And, as for making the interpreter check the convention; that'd be no language feature, just interpreter feature, which is never very good thing.. And if that kind of thing would be added to the language itself, I'd jump out of window, the elegance would be ruined! --User:Keymaker
Um result to much less elegant code/solutions? Elegance... ruined? *ponders -- rather inquisitively* Isn't the word elegance taboo when talking about esoteric languages? :) --Stux 14:37, 31 Oct 2005 (GMT)
Not really. I personally think Smurf is a very elegant language, despite being esoteric.--Safalra 15:57, 31 Oct 2005 (GMT)
Yeah, there are many elegant esoteric programming languages. Brainfuck has perfect symmetry and instruction set, yet it's a minimalistic turing-tarpit. --User:Keymaker
Brainfuck is already useless for binary data because EOF leaves it with only 255 possible symbols to use. To solve that problem would require a new instruction to push the last read input character back into the queue.
You can always escape the EOF character much like it's done in networking protocols and string quote inclusion ("\"") in C/C++. --Stux 17:11, 31 Oct 2005 (GMT)
Maybe the interpreter should have a command line switch text/binary mode. --Zzo38 23:02, 4 May 2007 (UTC)

A simple compromise: the BF interpreter has a binary mode and a text mode. Binary mode will leave everything intact, and text mode will convert whatever the OS uses for line breaks to LF and back. --Ihope127 20:52, 11 Jun 2006 (UTC)

[edit] Turing Machine

  • < all leave value the same and move tape pointer to left, goto next command
  • > all leave value the same and move tape pointer to right, goto next command
  • - all decrement value (5 to 4, 1 to 0, etc.), leave tape pointer to same position (or move left and add > command immediately afterward), goto next command
  • + all increment value (5 to 6, 1 to 2, etc.), leave tape pointer to same position (or move left and add > command immediately afterward), goto next command
  • [ if zero, goto corresponding ] command else goto next command, do not adjust value or pointer
  • ] if non-zero, goto corresponding [ command else goto next command, do not adjust value or pointer
  • , no I/O on a Turing Machine
  • . no I/O on a Turing Machine

--Zzo38 23:41, 13 Oct 2006 (UTC)

[edit] Implementations and External links

I just removed a large number of implementations and external links from the Wikipedia article. I'm going to link from that article to here. Please incorporate any that you like into this wiki since it seems on topic here and not quite ontopic for Wikipedia. -- Benjamin Mako Hill 01:29, 18 April 2007 (UTC)

Copyright violation removed. The information is available in the history of the Wikipedia page at [1]. --ais523 15:17, 20 April 2007 (UTC)

[edit] Advice of a change in this article

In Related languages section, after the phrase "Many people at various times have tried to extend brainfuck to make it easier to program in", I would like to delete "but such efforts have been compared to trying to make a luxury car by gluing parts onto a skateboard" and put in this place "BrainSub is the first one to achieve this goal in 2007"; unless someone have reasons to not to do this change. What do you think? Aacini 03:50, 18 July 2007 (UTC)

There're tons of brainfuck extensions making it easier to program in. Nobody just cares much about them because being hard is one of the things that make brainfuck interesting. BrainSub is far from being the first. --lament 16:07, 18 July 2007 (UTC)
Excuse me, but I disagree. Yes, there are tons of brainfuck extensions, but the vast majority do not provides ways to write brainfuck programs in an easier way. When an extension provides means to do new things this requires the user have knowledge of the new things besides brainfuck, so is really more difficult to use it. BrainSub is ENTIRELY DIFFERENT to any other brainfuck compiler because it provides the same techniques proven by years in high-level structured programming languages for an easier programming but used to write the same brainfuck programs, not new things; in this sense is not an extension but an evolution of brainfuck language. You can take a look on BrainSub capabilities in this article. Of course, this can be a very subjective matter, so I think we could compare BrainSub features for easier programming vs other brainfuck compilers/interpreters that makes easier to program in, so please give me a list of several of them. Aacini 03:48, 19 July 2007 (UTC)

[edit] Brainfuck in ZZT

As a programming challenge, I programmed a brainfuck interpreter a while back in ZZT-OOP. If you don't know, ZZT-OOP is a very primitive language for an old text game-creation framework called ZZT. Mostly, it was for nostalgia since some of my earliest programming experiences were in it. Given that ZZT has so many limitations, this is much like an esoteric-in-esoteric implementation. Is there any interest in uploading it to the The Esoteric File Archive? Duerig 04:46, 12 November 2007 (UTC)

Retrieved from "http://esolangs.org/wiki/Talk:Brainfuck"
Personal tools