Talk:brainfuck

From Esolang
Jump to navigation Jump to search

About BF Joust

"I prefer putting newer comments up top..."

Anyone still interested in BF Joust? It sounds quite fun, but its current situation is bad:

  1. Tons of dead links, as None1 said.
  2. The hill and the wiki page is inactive, meanwhile bf itself is still active.
  3. The zemhill IRC bot is gone! and whenever i try the web form, it shows me:
Exception: #<Errno::ECONNREFUSED: Connection refused - connect(2) for 
/home/bfjoust/bfjoust/socket/server.sock>

Which means i can't upload any BF joust programs!

If you're interested in BF joust, please respond, whether or not you have useful information. Iddi01 (talk) 10:52, 8 October 2024 (UTC)

I made an online emulator but it's incorrect with braces because I am very bad at writing parsers! --None1 (Nope.) 10:57, 8 October 2024 (UTC)

I've seen the online emulator, but without the hill it's hard to know if your program is good or not, and there's no leaderboard, no competition, and no whatever advanced stuff zem.fi provides... Iddi01 (talk) 11:13, 8 October 2024 (UTC)

Consifer starting a GitHub repo and PR programs manually?! --None1 (Nope.) 11:20, 8 October 2024 (UTC)

Regarding the zem.fi hill, the current situation is basically this: nobody had been submitting any programs in several years, so when the bot broke down, I didn't get around to fixing it. Since I'm now running the wiki as well, I kind of wanted to rebrand it as an official esolangs.org BF Joust hill, and at the same time fix some of the more annoying implementation internals, but... didn't. It would probably not take a huge amount of effort to bring it back up in its previous form; I may try to take a look in the near future. And of course all the tools are still up at github.com/fis/chainlance, and the hill program Git repo is presumably still cloneable from https://zem.fi/bfjoust/hill.git/, so it's not impossible to run these things locally, though there may be very little documentation about it. --fizzie (talk) 11:34, 8 October 2024 (UTC)
No promises that it will fully work, but I've fixed the obvious errors with the existing zem.fi hill, and verified that at least a test submission of a < program gets the expected result (loses against everything), both through the IRC interface and the web form. It may again go away with no warning if there's no use; whether I'll ever get around to making the esolangs.org rewrite/rebranding is also doubtful.

New Windows Implementation

I'm making a full-featured Brainfuck implementation for Windows: [1]

Do you guys think it's good enough to be mentioned in the article?

Please don't judge unless you've actually seen the application running...I put EVERY possible feature into it. --98.168.145.187 11:12, 26 August 2009 (UTC)

Three questions: 1. Why this implementation is better than any other from a myriad of existing Brainfuck implementations? 2. How many do you think esolang users will download and install in their computers something from the Microsoft site just to try out a new Brainfuck implementation? 3. I could not find even obvious features like the memory watcher or memory cell size. It contradicts to what you claim, doesn't it? --Oleg 07:27, 31 July 2009 (UTC)
It's actually looks like an IDE for writing BF programs. It comes with little features like debuging, simple optimizing, end of line compatibility, and an ascii to integer converter. Pretty neat, but I've seen others like it before. Orange 15:08, 31 July 2009 (UTC)
The optimizing feature isn't done yet, neither is the app itself, still working on it. 1: Features in a simple interface (and yes, the purpose is a simple IDE (maybe eventually full?) that can also serve as a simple interpreter.) 2: it's the .NET framework, most people already have it on their computer but some people for whatever reason don't, so I linked to it in the description so people don't complain why it won't start. 3: Try debug mode... If you guys have any suggestions at all please tell me, I will be happy to do everything I can to take them into consideration. I will be putting the project code onto the Google Code page soon. --(this comment by 98.168.145.187 at 18:15, 31 July 2009 UTC; please sign your comments with ~~~~)
I uploaded Beta 2, get it from the same link. --(this comment by 98.168.145.187 at 20:18, 31 July 2009 UTC; please sign your comments with ~~~~)
I uploaded Beta 3, just addressed a small issue with thread priority to make sure everything stays responsive. --(this comment by 98.168.145.187 at 20:36, 31 July 2009 UTC; please sign your comments with ~~~~)
Try to write a moderately complex program in Brainfuck (see for example http://www.hevanet.com/cristofd/brainfuck/). You can then see what difficulties one encounters and what kind of tools and features would help to overcome these problems. I would like to add that writing a new implementation with good debug facilities will require a lot of bravery and persistence. --Oleg 04:00, 1 August 2009 (UTC)
I'm probably going to add a step into debug option, breakpoints, and a memory watcher to debug mode as soon as I think of an intuitive way to add one. Anything else? --(this comment by 98.168.145.187 at 14:45, 1 August 2009 UTC; please sign your comments with ~~~~)
I'm making the current code character that is being executed in debug mode be highlighted too. 98.168.145.187 19:37, 1 August 2009 (UTC)
I uploaded Beta 4, tell me what you think of the vastly improved debug mode so far. 98.168.145.187 20:03, 1 August 2009 (UTC)
Beta 5 has been uploaded --98.168.145.187 11:12, 26 August 2009 (UTC)

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)

This (Greasemonkey's) test is quite size-dependant. The BF interpreter I just wrote runs this in 0.004 seconds for 16-bit cells and 142 seconds (2:22) for 32-bit ones. --80.174.59.115 17:12, 30 September 2011 (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)
Doing comparisons like this is also stupid unless you're using the same machine with the same processor. A crappy bf interpreter can run faster on a Xeon processor than a really optimized, fast interpreter can run on a 286. We need some kind of baseline machine to establish comparisons on.
>+>+>+>+>++<[>[<+++>-
 >>>>>
 >+>+>+>+>++<[>[<+++>-
   >>>>>
   >+>+>+>+>++<[>[<+++>-
     >>>>>
     >+>+>+>+>++<[>[<+++>-
       >>>>>
       +++[->+++++<]>[-]<
       <<<<<
     ]<<]>[-]
     <<<<<
   ]<<]>[-]
   <<<<<
 ]<<]>[-]
 <<<<<
]<<]>.
And yet another good test would be to run a trivial program with a stack of brainfuck self-interpreters. --Mazonka
That program just posted runs in 7260ms 5878ms (plus 2ms to compile it) on my compiler. But I agree, we need a standard test machine. Immibis 09:05, 5 June 2009 (UTC)

I wanted to see how a handful of BF interpreters in C compared to a very simple C implementation. Most of the interpreters I wanted to test were written by Daniel Cristofani. I wanted to use bnchmark.b (above sequence) attributed to "GreaseMonkey" (aka Ben Russell) as the test application. But, most of Daniel's BF interpreters use C int's instead of unsigned char.

That was so programs that expect binary input can tell EOF apart from any byte value. --(this comment by 216.70.157.15 at 01:23, 7 November 2010 UTC; please sign your comments with ~~~~)

This causes bnchmark.b sequence to not complete. Oleg Mazonka's bff4 had this same issue.

At the risk of sounding like a crusty old guy, a benchmark that's not portable is like a submarine with a screen door. --(this comment by 216.70.157.15 at 01:23, 7 November 2010 UTC; please sign your comments with ~~~~)
  • Results: approx. (manual) timings on 2.8Ghz (on single core)
bff4(1) 2 sec Oleg Mazonka
bcci(2) 5 sec Daniel B Cristofani
pbrain(1) 5 sec Daniel B Cristofani
qdb 5 sec Daniel B Cristofani
sbi(1) 10 sec Daniel B Cristofani
dbfi.b(3) X X Daniel B Cristofani
bf8(4) X X Ben Russell
(priv.)(5) 6 sec (private)
  • Notes
(1) Converted to unsigned char's.
signed would work just as well. --(this comment by 216.70.157.15 at 01:23, 7 November 2010 UTC; please sign your comments with ~~~~)
(2) Eliminated an underflow check. Interpreter coding error?
Are you asking whether checking for underflow was an error? No. Each of these interpreters was written for a specific purpose, or I would never have written so many:
  • bcci: written to enforce the very strict portability rules of the BCC (a contest), and compute scores.
  • pbrain: written to demonstrate my interpretation of pbrain semantics, which was intended to be clean and free of gaping holes, and to integrate well with the brainfuck language.
  • qdb: written as a portable, usable, moderately fast brainfuck interpreter. The optimizations are very crude and simplistic; I felt, and still feel, that if you want to run brainfuck fast, you have no business using an interpreter. Get a compiler.
  • sbi: written to show someone how you match brackets when parsing input. Also demonstrates some other elements of good practice while being extremely simple.
  • dbfi: written to be more concise than other brainfuck interpreters in brainfuck.
  • di.html: written to be more concise than other brainfuck interpreters in JavaScript. Not fast, not good practice, not even vaguely valid HTML, but it works okay. --(this comment by 216.70.157.15 at 01:23, 7 November 2010 UTC; please sign your comments with ~~~~)
(3) Failed C conversion. Didn't work. Didn't locate error.
How did you convert things to C? --(this comment by 216.70.157.15 at 01:23, 7 November 2010 UTC; please sign your comments with ~~~~)
(4) unable to locate, est. is 4 sec based on comments
(5) My straightforward, unpublished, BF interpreter in C.

--98.209.220.26 20:01, 28 August 2010 (UTC)

I've done a brainfuck interpreter speed test using the program mandel.b.

  • QDB used 8.1402463 seconds to complete the program.
  • bffsree used 1.6732373 senconds to complete the program.
  • jitbf used 4.0699663 seconds to complete the program.

I've also tested bfi (an optimizing non-JIT brainfuck interpreter in Python) and bff4, but they didn't finish the program in 1 minute, so I killed them. --None1 (talk) 11:02, 6 August 2023 (UTC)

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)
Now we've got 3. I doubt that 2 will work because once you have passed the first ], a cell will be zero and I don't think you can get usefully back to using 2 arbitrarily large cells again, except for innermost loops. Those can do multiplication and division by a constant, but the latter will infloop unless it has remainder 0, so it does not seem enough to do the divisibility testing for the 1-register Minsky machine. --Ørjan 01:35, 10 August 2011 (UTC)

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

I've written an interpreter in c++, with the purpose of being somewhat clean and not necessarily optimized. I'm not posting it in the links section because it's just another interpreter, but feel free to add it, use it or modify it if you want... Here's the link to the source (requires libboost-program-options): http://pastebin.com/f594865b4 Nerowolfe 18:06, 7 July 2008 (UTC)

I've written one for Casio fx-9750g. It's horribly slow though and my BF program to calculate the fibonacci sequence takes about one minute to get from 8 to 13. Ask on my talk page if you want the source. Immibis 23:21, 5 June 2009 (UTC)


Here are some link on the topic. Attention!: russian language, please use Google.translate if needed.

--(this comment by 91.195.22.25 at 14:59, 10 February 2011 UTC; please sign your comments with ~~~~)

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
Another way you could design a interpreter that takes program and input in the same stream, is to separate by ] character instead. This way it doesn't break programs that contain ! as comments, and the ] character would be invalid outside of a loop anyways in a normal program, so if you use it to separate program and input then it will work. --Zzo38 18:59, 7 July 2008 (UTC)
Funny; that's exactly what I used for my 117 byte interpreter. It was very natural for my parser, since ']' has to be recognized as the end of a codeblock anyway, and realizing it is unmatched is pretty straightforward. Not having to extend the alphabet beyond the existing 8 character makes it all the more elegant... --Tromp 00:23, 23 March 2009 (UTC)

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)

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)

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 ~~~~)

How did you make the hardware match brackets? Immibis 00:17, 6 June 2009 (UTC)
It would probably just be a simple stack. So some reserved RAM, and register with pointer. It pushes code address at '[', pops top address when exiting, and checks the top when it hits the ']'. -Kyle 1 Feb, 2012
That doesn't work very well for loops that are skipped on first entry. --Ørjan 15:37, 1 February 2012 (UTC)
Add a register "ignoring" which includes the boolean for whether it's fully executing or just counting brackets, and the location on the bracket stack for the loop it's skipping over. There are probably other ways too, maybe even more elegant. -Kyle 7 Feb, 2012
I have made a design that does this by cheating and encoding the jump addresses as an extended instruction, so that '[' and ']' instructions are actually three bytes long so that the cpu does not need to waste time searching for matching brackets. It turns out that is a variant of brainfuck that is actually a ton easier to work with, since it essentially gives jump-if-zero and jump-if-nonzero instructions, which have semantics much easier to use than requiring matching braces. -Craig 7 May 12

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)

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)

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)

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)

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 [2]. --ais523 15:17, 20 April 2007 (UTC)

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)

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)

I have done the same thing before. I have also made a Brainfuck interpreter in ZZT, but with no I/O and a very limited program size, and only binary data stored on tape. What I made was really more like Smallfuck than Brainfuck. How is yours done? --Zzo38 18:45, 7 July 2008 (UTC)
Since I did this last November, I have uploaded it to the vast ZZT archive. In addition to my own effort (http://zzt.belsambar.net/zgames/b/brain.zip), I learned that it had been done before by someone with the pseudonym of WiL (http://zzt.belsambar.net/zgames/b/BFI.zip). My system actually has 8-bit memory for data and 3-bit memory for code. Each column is a different word, and you change the current cell by simply moving the controller left or right. I use the ammo/torches/gems/score as temporary registers for moving information around. I even managed to make it a visual editor so you can see your code (barely within the 20k-per-board limit). WiL's implementation used a single square for each memory/code word. But WiL used a really nifty trick to eek out 3 bits per square rather than my measly 1 bit per square. It would be interesting to combine them. You could treble the amount of memory/codespace available. My system has something like 120 code cells and 60 memory cells, but that could increase by a lot. I/O is pretty lame, though. Output means putting a number in the ammo count and pausing and saying 'read what it says there'. Input means going through eight menus and asking the user to set each bit. Duerig 16:21, 23 July 2008 (UTC)

Who's gonna write an interpreter for bytecode (e.g. python bytecode) in brainfuck?

Is it possible? --(this comment by 91.37.37.64 at 02:42, 21 October 2008 UTC; please sign your comments with ~~~~)

Yes. Please sign your posts with four tildes (~). Immibis 00:40, 6 June 2009 (UTC)

Simple Python implementation

Maybe this is not the place but I just made a simple Brainfuck interpreter in Python and want to share it: http://pastebin.com/f6b934a1 PS: It does not wrap. --(this comment by 79.151.92.212 at 22:50, 29 May 2009 UTC; please sign your comments with ~~~~)

Is it possible to make an Atari 2600 interper for BF

And if you could, how much bytes would be left for the programs? --(this comment by 67.239.10.227 at 16:36, 18 August 2009 UTC; please sign your comments with ~~~~)

Sure, but it won't be able to run large programs or use much memory. My reply may not be correct since I don't know anything at all about this system, but if I (quickly) read correctly, one'd have 128 bytes of memory to use on run-time. The brainfuck interpreter could be short, take less than 1k easily, and the brainfuck program that would be ran with it would be stored on the ROM with the interpreter. It could take about 3k, maximum. I don't how much memory printing on screen (if having output) would take, but the actual interpreter might be able to have a memory array of about 100 bytes, and it wouldn't require many other variables; program pointer, memory pointer, loop counter. Too bad I don't have the skills to program it, knowing nothing about Atari. --Keymaker 18:44, 18 August 2009 (UTC)
That would be kind of cool. I think something like Paintfuck would work better for the atari though. Orange 00:04, 19 August 2009 (UTC)
Depends on can you store data on the screen so that you can read and modify it (I don't know) -- otherwise the area would be like 11x11 pixels, if the only place to store it is that 128 bytes. --Keymaker 15:54, 19 August 2009 (UTC)
Oh, make that 88x88 -- of course we'd store in bits, eight per byte... --Keymaker 15:56, 19 August 2009 (UTC)

portable, fast compiler implementation

I built a new implementation of a brainfuck compiler that is meant to be portable, fast and suitable. It translates the brainfuck code directly to 80386 opcodes, writes them onto the heap and executes the machine code. So, it's currently resricted to 80386 processors, but not to a specific OS (the OS only has to provide a libc and an executable heap). Some optimization is also done, so that the speed of execution is nice. It supports 8, 16 and 32 bit cells; "no-change on eof", "0 on eof", "255 on eof". I hope somebody takes time for testing the program and giving some feedback [3] --Thunder 15:10, 2 April 2011 (UTC)

Does this work on OS X where C symbols are prefixed with an underscore? What about OSes that use the NX bit? —ehird 18:38, 2 April 2011 (UTC)
I haven't got OS X, so I can't tell you. I tested it successfully on Windows XP and ArchLinux. If the NX bit is set for the heap segment, it won't work (Windows, Linux and Mac OS X support the NX bit, but afaik they don't use it standardly - but I will check this with some other PCs/processors). --Thunder 20:59, 2 April 2011 (UTC)
I was more asking in the general sense if it would handle the linking if the symbols were named in that manner :) —ehird 00:25, 3 April 2011 (UTC)

Nesting required for TC?

Is nesting of loops required for brainfuck to be Turing-complete? (I'm asking because I'm trying to show reduction with another esolang where nested loops would be difficult.) —Maharba 22:24, 31 July 2011 (UTC)

Yes, though I don't know the proof, and this talk page is probably far too small to contain it anyway. You may want to try BCT. —ehird 23:11, 31 July 2011 (UTC)
I believe you can show that for a loop with no further loops inside you can decide its halting problem on a given tape, which then allows you to solve it for a whole program without nested loops, disproving TC-ness.
First, if a loop has unbalanced <>, then each iteration must move it on the tape, and if it doesn't halt, it will after a predictable time reach unitialized regions of the tape and behave in a periodic manner forever.
Otherwise, if a loop is balanced, then at each iteration it will add a fixed constant to each touched cell, and deciding whether the loop halts is a matter of deciding whether the constant added to the cell tested at the end of the loop will eventually make it 0. Whether cells are unbounded or wrapping, this is easy to do with some division and modulo arithmetic.
For a whole program, run it step by step, while using the above to check if each loop entered will halt or not. This will either end with a loop confirmed non-halting, or by reaching the end of the program. --Ørjan 23:31, 31 July 2011 (UTC)
I just thought about what if the tape is circular, in which case unbalanced loops will eventually return to the same spot. However then you can adapt the method for balanced loops to check whether any of the finite number of tested cells will ever reach 0. --Ørjan 23:38, 31 July 2011 (UTC)

Is there any program to create simple GUI applications with BF?

I have heard of plenty interpreters/compilers for Brainfuck so far. What I am looking for now is sth to make very simple graphical applications, but using Brainfuck as the code behind the events of the controls present on the window form. Just like VB6, only much more simpler. Is there any program that you know of capable of doing that? I have some starting ideas, but no time to start this project so I thought maybe someone else did it. Is this at least possible? 141.70.82.221 08:25, 27 November 2011 (UTC)Ionut

I would love to see a project like EsoAPI made for this purpose. It could intercept output that matches certain sequences, and pass through calls to win32 apis or gtk, or maybe just some simplified gui system. Not sure what it would be useful for, and when you get to that level of complexity I can only really see something like c code compiled to brainfuck being really usable, but maybe not. --(this comment by 65.126.124.88 at 15:38, 7 May 2012‎ UTC; please sign your comments with ~~~~)

New optimizing implementation / speed tests ?

Hi everybody !

(please don't pay attention to my bad english ...)

Last month I discovered this wiki and more particularly the Brainfuck world, and writing an interpreter in C seemed a interesting challenge. So I did it, it was slow at the beginning but I continued to optimize it while keeping the code simple enough (I'm not very skilled in C, for example I don't understand half of the code in some of the optimizing interpreters I saw here).

The thing is, on the computer where I tested many implementations, I found out that mine was about as fast as bff4.c, supposed to be the faster. And I can't really believe that my simple program could be this powerful, so I wanted to know if the BF programs mandelbrot.b and hanoi.bf were sufficient to test the speed of interpreters written in C. (speeds with those tests : ~11 seconds (mandelbrot.b) and ~3 (hanoi.bf) for bff4.c, ~12 and ~1.5 for mine)

If you think it is good enough, I'll be glad to post the source code here as soon I commented it in english (currently the comments are in french) and documented it ! And if you don't think the aforementioned programs are good benchmarks, please provide a better one !

Thank you for reading,

Maxime Rinoldo.

Maxdefolsch (talk) 21:29, 20 October 2012 (UTC)

The best tests I've seen so far for speed are: - mandelbrot.b - hanoi.b - long.b - si si hi123.b (self interpreter running self interpreter running hi123.b)

for completeness - LostKng.b (large file test) - squares.b - bottles.b

Sreekotay (talk) 04:25, 11 February 2013 (UTC)SreeKotay (talk) 22:36, 9 February 2013

Updated: executables and package with speed tests available for Windows and Linux @ http://sree.kotay.com/2013/02/implementing-brainfuck.html Sreekotay (talk) 04:25, 11 February 2013 (UTC)SreeKotay (talk) 22:05, 10 February 2013

brainfuck as a concatenative language

I guess this is no great insight, but after designing Burro and finally actually reading Mathematical foundations of Joy and designing Carriage, it's abundantly clear to me that brainfuck can be explicated as a concatenative language. Also, since it doesn't use a stack, it's a counter-example (like Deque) to the idea that concatenative languages are somehow tied to stacks and/or RPN.

Consider the program state to consist of a single-headed tape, an input queue, and an output queue. The I/O queues are "lazy", to permit interactive I/O. A brainfuck program is a concatenation of symbols, with an interpretation (which is a monoid homomorphism) which maps each symbol to a function and concatenation to function composition.

  • > (resp. <) represents a function that maps tapes to tapes where the head has been moved right (resp. left) one cell;
  • + (resp. -) represents a function that maps tapes to tapes where the cell under the head has been incremented (resp. decremented);
  • . represents a function that maps states to states where the value of the cell under the tape head has been enqueued on the output queue;
  • , represents a function that maps states to states where the cell under the tape head now has a value that was dequeued from the input queue;
  • [x] is the quoting operator. It's meaning is much the same as it is in Joy -- the string x is interpreted concatenatively as a function. However, instead of pushing this function on the stack, it is immediately applied, if the value of the cell under the tape head in the state is non-zero, and repeatedly reapplied under the same conditions (sorry, this still sounds a little too operational, but you get the idea.) Chris Pressey (talk) 12:54, 25 November 2012 (UTC)
I agree; I also noticed that BF was concatenative (while trying to work out whether it contained monads, in an attempt to troll Reddit). I think I concluded that it has monad transformers, but not monads. --ais523 21:45, 25 November 2012 (UTC)
How can they have monad transformers, but not monads? First you have a category (such as the category where morphisms are the program, with only one object, so you have a monoid). All categories can use identity monad, so at least it has one. (This applies whether it is "pure" or not, I think.) --Zzo38 (talk) 01:01, 26 November 2012 (UTC)
See Pure BF. --Ørjan (talk) 22:35, 25 November 2012 (UTC)

Conformance suite?

Is there a set of "canonical" examples that validate correct function of a BF interpreter or runtime? The following program, for example, fails to produce correct results with Oleg Mazonka's BFF4 interpreter for example: 

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

That is to say, the output is different than other implementations I could find (including my own).

Similarly, it'd be nice if there were a canonical performance test suite. Suggestions? - Sree --(this comment by 70.192.195.142 at 21:40, 8 February 2013‎ UTC; please sign your comments with ~~~~)

I wrote some tests that catch common problems. They're at http://www.hevanet.com/cristofd/brainfuck/tests.b .
But the problem with your modified version of squares.b is that it tries to store 401 in a cell as the number of squares to compute. Any attempt to set cells to values above 255 fails if the cells are bytes, which is a common and legitimate implementation decision.
--(this comment by 71.237.160.131 at 23:26, 3 April 2013‎ UTC; please sign your comments with ~~~~)
Just to confirm, my interpreter can run in both 8 and 32 bit modes (and any between) this BF script needs at least 10 bits per cell to work correctly. The interpreter bff4 uses 32bit cells. Rdebath (talk) 16:36, 27 August 2013 (UTC)

Turing-complete programs in 148 and 135 instructions

I've made a minimal implementation of Finiteless Cyclic Tag, and after about twelve versions of the program I've managed to get it down to 148 instructions. I doubt I can get this particular program shorter (someone else might) but I think a shorter Turing-complete brainfuck program can be made, of course, and I will keep working on it every now and then... Here's the program: http://www.brain------------------------------------------------------fuck.com/programs/mfcti.b And here's a description of its input and a program to generate it: http://www.brain------------------------------------------------------fuck.com/mfcti.txt --Keymaker (talk) 17:27, 2 April 2014 (EDT)

I made a Rule 124 cellular automaton simulator and got it to 135 instructions. Here: http://www.brain------------------------------------------------------fuck.com/programs/r124.b
And here's the description of input: http://www.brain------------------------------------------------------fuck.com/r124.txt --Keymaker (talk) 16:36, 18 May 2014 (UTC)

My optimizing interpreter again

Hi,

I posted two years ago on this page to talk about my fast interpreter in C, but never posted the source code and ultimately forgot about it, having more important things to do (like... procrastinating). I saw last week that my post got an answer in February 2013 from someone who claimed to have made a fast interpreter too, so I ran a few tests and indeed, for example mandelbrot.b took about 8 seconds with his interpreter and 10 seconds with mine on my computer.

Of course, I couldn't stand that, so I came back to the world of BF =D I made a few more optimizations and yay, mandelbrot.b now runs in only 6-6.5 seconds with my interpreter o/ (These optimizations weren't even hard, I really could have made them two years ago .-.)

I'll try to see if I can make some more difficult optimizations, and afterwards I'll be glad to post my code ! (and I promise I won't forget this time =P)

Maxdefolsch (talk) 13:51, 15 May 2014 (UTC)

... I just read more carefully this person's website and it seems I was misled : the code source I used to compare it with mine wasn't the optimized interpreter but only a reference interpreter, he didn't actually post the source on this page. It's probable that his interpreter is in fact way faster than mine. =( I'll continue to work on it anyway.

Maxdefolsch (talk) 11:13, 19 May 2014 (UTC)

There does seem to be compiled binaries there, though. (Linked from the first blog post.) --Ørjan (talk) 14:42, 19 May 2014 (UTC)

Of course if you want a really fast interpreter you should go to Github, seems to beat all the competition, but truthfully it's difficult to be sure as I've run out of good tests. The original prime.b from the original archive actually makes quite a good one if your cell size is 16bits or more; I get primes to 2000 in about 10 seconds on a 3Ghz I7. Rdebath (talk) 12:12, 24 May 2014 (UTC)

Syntax highlighting.

+++++ +++               Set Cell #0 to 8
[
    >++++               Add 4 to Cell #1; this will always set Cell #1 to 4
    [                   as the cell will be cleared by the loop
        >++             Add 4*2 to Cell #2
        >+++            Add 4*3 to Cell #3
        >+++            Add 4*3 to Cell #4
        >+              Add 4 to Cell #5
        <<<<-           Decrement the loop counter in Cell #1
    ]                   Loop till Cell #1 is zero
    >+                  Add 1 to Cell #2
    >+                  Add 1 to Cell #3
    >-                  Subtract 1 from Cell #4
    >>+                 Add 1 to Cell #6
    [<]                 Move back to the first zero cell you find; this will
                        be Cell #1 which was cleared by the previous loop
    <-                  Decrement the loop Counter in Cell #0
]                       Loop till Cell #0 is zero

The result of this is:
Cell No :   0   1   2   3   4   5   6
Contents:   0   0  72 104  88  32   8
Pointer :   ^

>>.                     Cell #2 has value 72 which is 'H'
>---.                   Subtract 3 from Cell #3 to get 101 which is 'e'
+++++ ++..+++.          Likewise for 'llo' from Cell #3
>>.                     Cell #5 is 32 for the space
<-.                     Subtract 1 from Cell #4 for 87 to give a 'W'
<.                      Cell #3 was set to 'o' from the end of 'Hello'
+++.----- -.----- ---.  Cell #3 for 'rl' and 'd'
>>+.                    Add 1 to Cell #5 gives us an exclamation point
>++.                    And finally a newline from Cell #6

Well, comments ? Rdebath (talk) 21:04, 15 August 2014 (UTC)

Looks good to me. SuperJedi224 (talk) 19:12, 24 September 2015 (UTC)

Knuth's Arrow Notation

Has anyone ever done a Brainf*** implementation of it? SuperJedi224 (talk) 19:04, 18 March 2015 (UTC)

To my knowledge, no. Are you planning to? If not, I could make one because it seems like a good idea. --Keymaker (talk) 11:17, 19 March 2015 (UTC)
I'll try. SuperJedi224 (talk) 18:04, 19 March 2015 (UTC)

Shortest Turing-complete brainfuck programs?

I've made an implementation of Sequential tag system in brainfuck, and to my surprise, through various versions I managed to get it down to 40 instructions. (39 instructions, if one allows a kind of variation of STS.) The program can be found here: [4] Information on what kind of input it requires can be found here: [5] I have a feeling that even shorter programs will be found and I for one will be intrigued. If you find any, let it be known here. --Keymaker (talk) 15:14, 6 May 2015 (UTC)

Would BF still be TC with do-while loops?

I've been wondering whether Brainfuck would still be Turing-complete if the semantics of [] would be changed to do-while loops, i.e. the loop body would always be executed at least once. It's clear that not every BF program can be translated to this new dialect (e.g., it's impossible to write a program which may or may not print something - you'd have to always print at least one character if you potentially want to print anything), but can a Turing-complete subset of BF be translated? For simple loops, it's trivial to do the conversion, because all of <>+- can easily be inverted to cancel the first repetition. But for nested loops it's not that simple... Does anyone know if this has been discussed before somewhere? --Martin Büttner (talk) 10:47, 24 September 2015 (UTC)

I haven't thought about this much but at the moment I don't think it is. I can't see a way one would make code that is never executed if memory is this or that, which is essential for making Turing-complete programs, such as esointerpreters, in brainfuck. I haven't seen this problem considered for other languages either. --Keymaker (talk) 05:49, 25 September 2015 (UTC)
Yes, it's definitely impossible to skip code entirely, but I can't see whether that's an necessary requirement for Turing-completeness, or whether there would be a way to work with it anyway, e.g. be cancelling the first iteration of each loop somehow. I just found this post though, which shows that not every computable function has a computable inverse. This means cancellation of a loop iteration (even if it doesn't contain . or ,) is not always possible. So if translation of BF into this new dialect is possible at all, it would mean that the loops themselves have to be rewritten. --Martin Büttner (talk) 08:44, 25 September 2015 (UTC)
For the same reason it's impossible to skip loops it's likewise impossible to implement anything that could detect the first iteration of a loop. I think some form of branching is essential and this variation doesn't allow it -- as far as I can see. An interesting problem. --Keymaker (talk) 10:13, 25 September 2015 (UTC)
I've asked the folks on Computer Science Stack Exchange now. I'll report back here if I get any conclusive answers. --Martin Büttner (talk) 09:16, 27 September 2015 (UTC)


Here's a reduction from Brainfuck to Do-While-Brainfuck (somewhat tested):

Memory layout: Each original cell is replaced by two cells. The first one is a control byte (0 or 1), while the second one carries the original value. The control bytes of all cells to the left of the pointer are 1, while the control bytes of all cells to the right are 0. The control byte of the current cell indicates whether we're executing (1) or skipping (0) code ("current control byte").

At the beginning of the tape there is a control block that is used for saving (restoring) the current control byte at the start (end) of a loop. With the following abbreviations, 

  m = maximal nesting depth of [ ] blocks
  d = depth of the current [ or ] token
  {...}n = n-fold repetition

The tape looks as follows, where * indicates the current pointer (there's a dummy cell at the start of the tape to make the implementation of > easier): 

  cm ... c1 0 0 1 0 {1 ?} *[0|1] ? {0 ?}

The Brainfuck operations are implemented as follows: 

  start ==>  {>}m>>+>>+
  >     ==>  >>>>+<<<<<<[>>]>>>>+[-]<<+[<<+>>-]<<-
  <     ==>  +[>>+<<-]>>->>+[<<]>>>>+[-]<<-<<<<
  +     ==>  +[>>+<<-]>>[<+<+>>-]<-<-
  -     ==>  +[>>+<<-]>+>[<-<+>>-]<<-
  [     ==>  +[>>+<<-]>>[>>+<<<<<<[<<]{<}d+{>}d>>[>>]>>-]>>-<<<                  (save control byte)
             +[>+[<<+>>-]>>+[<<+>>-]>>+<<<<-<<->-]>+[-]>>>>[<<<<<+>>>>>-]<<<<<-< (compute new control byte)
             [                                                                   (start actual loop)
  ]     ==>  +[>>>>+<<<<-]>>>>-<<<
             +[>+[<<+>>-]>>+[<<+>>-]>>+<<<<-<<->-]>+[-]>>>>[<<<<<+>>>>>-]<<<<<-< (compute new control byte)
             ]                                                                   (end loop)
             +[<<]{<}d[{>}d>>[>>]<<+[<<]{<}d-]{>}d>>[>>]<<--                     (restore control byte)
  .     ==>  >.<                                                                 (outputs NUL while skipping code)

You can easily add a loop that reads (non-empty) input at the start of the program and outputs (non-empty) tape contents at the end; arbitrary interaction is, of course, impossible.

--213.162.68.156 12:55, 27 September 2015 (UTC) (aka Int-e (talk) 13:06, 27 September 2015 (UTC))

Loop corrected --Int-e (talk) 15:41, 27 September 2015 (UTC)
One more try --Int-e (talk) 16:01, 27 September 2015 (UTC)
So far ... If I just use the commands + - < >  I'm getting correct results. But the command sequence +++[-]  does not run properly. I expect 10 steps from it but I only get six. It seems the BF [ command runs the pointer off the beginning of the tape, the interpreter I'm using doesn't mind, but the results are still wrong. BTW: As output isn't something that's required for TC I would suggest that it be faked (slightly) by having skipped . commands output NUL bytes if possible. Rdebath (talk) 07:44, 28 September 2015 (UTC)
Okay, I fixed two problems with the [ and ] commands, but I still haven't run it in an actual do-while brainfuck interpreter (the translation is designed to work with both do-while- and while-loops). When testing, note that the depth of the outermost loop is 1, not 0. --Int-e (talk) 14:04, 28 September 2015 (UTC)
Here's my translator and here's a do-while interpreter (it's "Broken No.5" with a primitive debug). They're very minimal for the moment, but that can be fixed later. Rdebath (talk) 18:11, 28 September 2015 (UTC)
I believe my translation is now correct, but your interpreter is broken: The stack pointer is not decreased in the ] operation when a loop is done. --Int-e (talk) 22:52, 28 September 2015 (UTC)
Now that was predictable! I use a known broken interpreter and what do you know it really is broken! Okay, when I switch to "No.9" it is passing some rather nasty tests; even "Erik's mandelbrot" seems to be working properly. It also looks like translation of . to >.< is working as I said (re NUL bytes) is that by intent or just serendipity? Rdebath (talk) 08:01, 29 September 2015 (UTC)
It's serendipity: The only way that the control byte becomes zero is when we enter a loop and the current cell contains 0, and while skipping code, the pointer doesn't move. I've added the translation to the list. --Int-e (talk) 11:09, 29 September 2015 (UTC)
Also added an initial cut of translator to my bf2any programs. I think do better by using the control byte to the right of 'here' for an RLE loop for + and - maybe for > and < too. Rdebath (talk) 08:11, 29 September 2015 (UTC)

8bit Assembly BF interpreter

After some work i finally finished this 8bit Assembly interpreter. It's biggest limitation is program space, as the simulator the interpreter runs in is limited to 255 bytes of ram, which are used by the program, stack, output buffer, etc... So your program + input is limited to (about) 32 bytes...

https://github.com/tatjam/Brain-Assembly-Interpreter (It runs using this simulator: https://schweigi.github.io/assembler-simulator)

Read the instructions inside, to run it simply copy it to the assembler simulator, click assemble (below), and then run at the top!

It's mostly made as a learning project, the first thing I ever make with Assembly.

Example program i debugged the program with: (Copies all input to output) >[>,][<][>.]

Tell me what you think.

Program size (assembled) is about 170 bytes.

Cheers! :)

Shortest known "hello world" program.

I think it's a bad idea to add the "shortest known" version of a program to the page. This version which is also the "shortest known" illustrates the problems. 

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

It prints "hello world!", but that's a different string to the '106', '103', '87' and '89' strings.

It needs an 8-bit wrapping interpreter where the '106' and '103' run on 7-bit hard boundary (error on overflow) interpreter and the '87' needs an 8-bit wrapping or greater than 8-bit interpreter.

Lastly, the program used to search for the '66' is (probably) a bit different, it uses better automation and smaller code fragments (ie: single instructions) than the more manually guided search programs for the others.

So, I could replace the code in the main page with the above, delete that example completely or leave the page as is. But if it's the latter what should the rules be? Well, Quintopia what do you think it should be? Rdebath (talk) 09:59, 6 January 2016 (UTC)

As a point of clarification, the 87 byte version does not require wrapping cells, only that -+ results in 0, which should be true of any integer datatype. A version which does require wrapping cells is only 78 bytes. Both of these produce a comma not present in the 103 byte version. Producing the same output with wrapping can be accomplished in 71 bytes:
+<<---[[<+>->++++>---<<]>++]<<<++.<+++.<..<-.<<++.<-.>>>.<.>>.>-.<<<<+.
8 bytes shorter than the inversed.ru version, and I suspect the lowercase version may be improvable as well. However, if anything should be listed as a 'shortest version', it should probably produce exactly Hello World!, as the example code which has stood for many years does. Primo (talk) 06:32, 19 February 2016 (UTC)
Hmm, okay, I was a little unclear about that 87, for some reason the byte cells are often assumed to be 0..255, it requires negative values.
As for the 71 ...
$ profilebf <<< '+<<---[[<+>->++++>---<<]>++]<<<++.<+++.<..<-.<<++.<-.>>>.<.>>.>-.<<<<+.'
Hello World!
\ no newline at end of output.
Program size 71
Final tape contents:
 ! 253 246 228 : 176  22  74 232 196  90  30 108  87  33 114 111 108 ...
                                                       ^
WARNING: Tape pointer minimum -3, segfault.
Tape pointer maximum 18
Range error: value check, overflows: 5, underflows: 6
Program logic effects '['->0, ']'->11
Counts:     +: 12642        -: 10082        >: 7582         <: 7573
Counts:     [: 20           ]: 2538         .: 12           ,: 0
Total:         40449
$
Using cells to the left of home is normally considered a failure, so it should probably be considered to be a '74'.
I've just dug up my copy of K&R, first published in 1978 and the first confirmed sighting of a HW program, it uses:
main()
{
     printf("hello, world\n");
}
It appears to contain the comma, no uppercase and the "\n" is a newline. The earlier, 1972 but not completely confirmed, BCPL sighting seems to use the same 13 characters. I don't personally like that one though.
I think you probably mean Urban Müller's HW program which produces "Hello World!\n" in C string format

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

Don't forget the newline! I'll cost you a 14 instruction penalty, which takes the '71' up to 88 total.
Rdebath (talk) 09:37, 3 March 2016 (UTC)
Different rules, different game. If the newline is necessary, it would be much better to generate it as part of the byte sequence, rather than tacking it on to the end. For example, the following at 76 bytes: 
+<--[[<++>->-->+++>+<<<]-->++++]<<.<<-.<<..+++.>.<<-.>.+++.------.>>-.<+.>>.
Not rolling off the left side would cost an additional >>. With non-wrapping cells, the best I could find is 85: 
->+>+>>+>---[++++++++++++[>+++++>++>+<<<-]+<+]>>+.>++.>..>.>>.<+.<.+++.<.<-.>>>>+.>+.
-Primo (talk) 12:44, 11 April 2016 (UTC)

Last Half—Or Is It?

I’m being silly here, but “fuck” isn’t the last half of “brainfuck”—it’s the last four ninths. IAM (talk) 20:56, 26 April 2016 (UTC)

It's the last half in the same way "coaster" is the last half of "rollercoaster" and "driver" is the last half of "screwdriver". Either subword of a compound word is a "half". --Quintopia (talk) 21:03, 26 April 2016 (UTC)
@IAM and Quintopia (talk): IAM’s right, in terms of letters, but Quintopia’s right in terms of syllables. Also, tell Sinebot@Wikipedia that Oshwah@Wikipedia said hi. SineBot is the bot who signs my posts! Carbuncle (talk • contribs • d. contribs) 14:45, 21 August 2018 (UTC)

A possible proof

This Turing-completeness proof tries to compile brainfuck to the Z3 computer, but I am not sure whether it is valid. Please verify it.
If this is verified, can it be one of the proofs used in the brainfuck page?--A (talk) 11:05, 29 April 2019 (UTC)

Implementing an interpreter for any Turing-complete language in brainfuck, or providing a compiler that translates any Turing-complete language to brainfuck, would count as an additional proof that brainfuck is Turing-complete, but I don't know how many more of these proofs we need; it's no longer an open question. The Z3 is also a marginal choice for Turing-completeness proofs because it's more explicitly and intrinsically storage-limited than most languages, and yet would only be Turing-complete if it had no storage limitations. But if you do implement the Z3 in brainfuck that would be an interesting project. (Note that it used essentially floating-point numbers and not integers.) --DanielCristofani (talk) 02:34, 2 July 2020 (UTC)

Addition, subtraction, etc.

It is quite certain that these are already implemented. 

Addition: 
    y[-x+y]x
Subtraction: 
    temp0[-]
    y[x-temp0+y-]
    temp0[y+temp0-]
Multiplication:
    temp0[-]
    temp1[-]
    x[temp1+x-]
    temp1[
     y[x+temp0+y-]temp0[y+temp0-]
    temp1-]
Division:
    temp0[-]
    temp1[-]
    temp2[-]
    temp3[-]
    x[temp0+x-]
    temp0[
     y[temp1+temp2+y-]
     temp2[y+temp2-]
     temp1[
      temp2+
      temp0-[temp2[-]temp3+temp0-]
      temp3[temp0+temp3-]
      temp2[
       temp1-
       [x-temp1[-]]+
      temp2-]
     temp1-]
     x+
    temp0]

(Note: these are copied from brainfuck algorithms, which is in public domain.)

Loading and Storing from the accumulator

The Z3 has an accumulator to operate over an infinite tape. brainfuck also has an implicit accumulator, which is a chosen cell on the tape.
Loading can be expresses as copying a cell to this chosen cell, and storing can be expressed as copying a value from this chosen cell.
This is a possible loading algorithm(to load a value from left to right, starting from left): 

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

This is a possible storing algorithm(the reverse of the above, starting from right): 

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

Implementing an infinite loop

The Z3 implements an infinite loop via glueing the two ends of a command tape together, and it halts via zero division.
brainfuck can easily achive this: 

An example infinite loop:+[]
Note: If we want to make sure that the loop runs forever
We have to specify a cell to always be nonzero
Breaking from that loop is equivalent to setting that cell to 0

(Note: It must be certain that the outer-most loop indexes the chosen cell to be nonzero.)

Input\Output format

Input\Output uses ASCII codes, right? --Bog'riquet De FerChef (talk) 10:23, 8 December 2020 (UTC)

Most BF programs use ASCII. However, it's not completely certain; some will use an extended character set, usually UTF-8 and a few will use I/O with decimal numbers. Though I suspect the latter is just because printing big numbers using BF is very slow. Rdebath (talk) 02:07, 9 December 2020 (UTC)
Printing big numbers is fast if you store them in a way that makes it fast. One digit per cell is a good choice for many uses. DanielCristofani (talk) 06:07, 17 February 2021 (UTC)

How did you add the color to the Hello World Program

--None1 (talk) 09:14, 3 August 2023 (UTC)

You can use some HTML and CSS tags like <font> in wikis, for instance 

++ Increment the cell twice
. Output some random ASCII control character
--Fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff (talk) 06:44, 1 December 2024 (UTC)

Bffsree's source code?!

I recently went to the homepage of bffsree and found that there is part 2, and that part includes the source code and the header. --None1 (talk) 04:58, 30 August 2023 (UTC)

Is there any compilers/interpreters for useful luaguages made by brainfuck?

Like interpreter for C in brainfuck or something? I'm wondering.

Probably no, but there are compilers from a high level language to brainfuck, like BFBASIC. --None1 (talk) 13:34, 11 October 2023 (UTC)

Might Bf will destroy other programing languages?

Each programing language requires at least 1 byte for an command. But Bf only 3 bits! This makes some BF programs so small they can fit on a QR code. The smallest Hello World Assembly is 20 bytes, and on bf is 300 bits, divided by 8, 37.5... So not quite, but some programs might be small enough to surpass Assembly. Maybe with compression it will!

brainfuck will beat a language in golfing.
Unless if it's printing text
User:Gaham (Discord:belarusianflag)

Retrieved from "https://esolangs.org/w/index.php?title=Talk:Brainfuck&oldid=147208"