Abuse filter log

Abuse Filter navigation (Home | Recent filter changes | Examine past edits | Abuse log)
Jump to navigation Jump to search
Details for log entry 7,749

14:28, 19 September 2021: Leomok2009 (talk | contribs) triggered filter 9, performing the action "edit" on Talk:Brainfuck. Actions taken: Disallow; Filter description: require new users to introduce themselves (examine)

Changes made in edit

   
 
::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. [[User:DanielCristofani|DanielCristofani]] ([[User talk:DanielCristofani|talk]]) 06:07, 17 February 2021 (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. [[User:DanielCristofani|DanielCristofani]] ([[User talk:DanielCristofani|talk]]) 06:07, 17 February 2021 (UTC)
  +
  +
== New BF Derivative (DaBooty) (Based on the “How to pronounce ( ͡° ͜ʖ ͡°)” song) ==
  +
  +
Digits for number literals
  +
Look at that booty, 1
  +
  +
show me the booty 2
  +
  +
Give me the booty, 3
  +
  +
I need the the booty 4
  +
  +
Back up the booty, 5
  +
  +
I hate the booty 6
  +
  +
I like the booty, 7
  +
  +
oh what a booty 8
  +
  +
Shaking that booty, 9
  +
  +
I saw the booty 0
  +
  +
I want the booty, decimal point
  +
  +
Math
  +
  +
  +
X, lord what a booty, Y = X+Y
  +
  +
X, Bring on the booty, Y = X-Y
  +
  +
X, give up the booty, Y = X*Y
  +
  +
X, Loving the booty, Y = X/Y
  +
  +
X, Sleeping booty, Y = X%Y
  +
  +
X, round booty, Y = X integer divided by Y
  +
  +
X, Down for the booty, Y = X to the power of Y
  +
X, I want the booty = 0-X
  +
  +
Suing the booty, X, scared of the booty = enclose X in parentheses
  +
  +
All math expressions end with “Hunting the booty”
  +
  +
Commands:
  +
  +
  +
X, Casing the booty, = print X
  +
  +
X, getting the booty, = print X as Unicode
  +
  +
X, Beautiful booty, =Set current cell to X
  +
  +
smoking booty = current cell value
  +
  +
X, Talk to the booty,= cell X value
  +
  +
X, more booty = make pointer go right X cells (left if negative)
  +
  +
Fine booty, X, All about the booty, (code), big old booty = run code until current cell = X
  +
  +
Serious booty,X, amazing booty, (code), I'll take the booty, (code2), where is the booty
  +
= run code1 if current cell=X, code2 otherwise
  +
  +
Stare at the booty = input number, store in pointed cell
  +
  +
walking the booty = input Unicode character, store in pointed cell
  +
  +
Touching the booty, = Sets the current point of execution to the location of the pointer
  +
  +
X, whos got the booty = Inserts X new cells before the current pointer, shifting all following cells to the right.
  +
X, Grabbing the booty, = Removes the cell at the current pointer and the next (X-1) cells, shifting all following cells to the left.
  +
  +
X, Harder booty, = Locks X cells and prevents it from being changed. Any attempt to change it silently fails. (This includes deleting it)
  +
  +
X, softer booty = Unlocks X previously locked cells and allows it to be edited again. Calling this on a already unlocked cell does nothing.
  +
  +
Foreign booty = swaps the program array (in Unicode) with the cell array so that their roles are reversed until another “Foreign booty” swaps it back, much like the X operator in Braintwist
  +
  +
X, home booty = Wait X seconds.
  +
  +
( ͡° ͜ʖ ͡°) = End the program.

Action parameters

VariableValue
Edit count of the user (user_editcount)
0
Name of the user account (user_name)
'Leomok2009'
Age of the user account (user_age)
1713
Page ID (page_id)
1138
Page namespace (page_namespace)
1
Page title (without namespace) (page_title)
'Brainfuck'
Full page title (page_prefixedtitle)
'Talk:Brainfuck'
Action (action)
'edit'
Edit summary/reason (summary)
'New BF Derivative (DaBooty) (Based on the “How to pronounce ( ͡° ͜ʖ ͡°)” song)'
Old content model (old_content_model)
'wikitext'
New content model (new_content_model)
'wikitext'
Old page wikitext, before the edit (old_wikitext)
'{{lowercase}} == New Windows Implementation == I'm making a full-featured Brainfuck implementation for Windows: [http://code.google.com/p/winbfinterpreter/] 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. --[[User:98.168.145.187|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? --[[User:Oleg|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. [[User:Orange|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. {{unsigned|18:15, 31 July 2009|98.168.145.187}} :::: I uploaded Beta 2, get it from the same link. {{unsigned|20:18, 31 July 2009|98.168.145.187}} ::::: I uploaded Beta 3, just addressed a small issue with thread priority to make sure everything stays responsive. {{unsigned|20:36, 31 July 2009|98.168.145.187}} ::: 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. --[[User:Oleg|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? {{unsigned|14:45, 1 August 2009|98.168.145.187}} ::::: I'm making the current code character that is being executed in debug mode be highlighted too. [[User:98.168.145.187|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. [[User:98.168.145.187|98.168.145.187]] 20:03, 1 August 2009 (UTC) : Beta 5 has been uploaded --[[User:98.168.145.187|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: :*[http://greasemonkey.shadowarts.org/bf8.zip 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? --[[User:GreaseMonkey|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. --[[User:80.174.59.115|80.174.59.115]] 17:12, 30 September 2011 (UTC) :*[http://www.mediafire.com/?o463xy29ollpa8v BF to COM compiler] can do that in ~1 second. {{unsigned|02:24, 15 January 2011|188.168.83.73}} :I agree. A common program that could be used to benchmark compilers would be nice. :[http://software.xfx.net/utilities/vbbfck/index.php 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. --[[User:Xfx|xfx]] 06:52, 18 April 2007 (UTC) ::You may want to check these two as well - [http://mozaika.com.au/oleg/brainf bff4] and [http://swapped.cc/bff bff]. Also [http://esoteric.voxelperfect.net/w/index.php?title=Brainfuck&diff=9065&oldid=9033 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. [[User:Apankrat|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. --[[User:IslandHopper973|IslandHopper973]] 20:19, 26 April 2007 (UTC) ::Are all above mentioned programs compilers? I think this info is missing. My [http://www.geocities.com/brainsub BrainSub] compiler do it in 0.05 seconds with 8bit cells and 3 min. 37 secs. with 16bit cells. [[User:Aacini|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 [http://swapped.cc/bff bff] and [http://mazonka.com/brainf 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. --[[User:Mazonka|Mazonka]] ::That program just posted runs in <s>7260ms</s> 5878ms (plus 2ms to compile it) on my compiler. But I agree, we need a standard test machine. [[User:Immibis|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. {{unsigned|01:23, 7 November 2010|216.70.157.15}} 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. {{unsigned|01:23, 7 November 2010|216.70.157.15}} *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. {{unsigned|01:23, 7 November 2010|216.70.157.15}} :(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. {{unsigned|01:23, 7 November 2010|216.70.157.15}} :(3) Failed C conversion. Didn't work. Didn't locate error. ::How did you convert things to C? {{unsigned|01:23, 7 November 2010|216.70.157.15}} :(4) unable to locate, est. is 4 sec based on comments :(5) My straightforward, unpublished, BF interpreter in C. --[[User:98.209.220.26|98.209.220.26]] 20:01, 28 August 2010 (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. --[[User:Graue|Graue]] 15:35, 9 Jun 2005 (GMT) :Theoretically, 2 cells (cf [[Minsky machine]]); Frank Faase has a proof using 5 cells. --[[User:Chris Pressey|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. --[[User:Oerjan|Ø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? --[[User:Rune|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? --[[User:Graue|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. --[[User:Rune|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 [[User:Nerowolfe|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. [[User:Immibis|Immibis]] 23:21, 5 June 2009 (UTC) Here are some link on the topic. Attention!: russian language, please use [http://translate.google.com Google.translate] if needed. * Branfuck interpreter in Lua: http://habrahabr.ru/blogs/crazydev/112919/ * Branfuck interpreter in Bash: http://habrahabr.ru/blogs/crazydev/112989/ * Branfuck interpreter in Mercury: http://habrahabr.ru/blogs/crazydev/113099/ * Branfuck JIT (AOT really) complier in Pascal: http://habrahabr.ru/blogs/development/113339/ {{unsigned|14:59, 10 February 2011|91.195.22.25}} == 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 <blockquote>1^a 0 1^b 0 1^c ... 00 1^A 0 1^B 0 1^C ... 00</blockquote> 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.)<br> --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. --[[User:Keymaker|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. --[[User:Zzo38|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... --[[User:Tromp|Tromp]] 00:23, 23 March 2009 (UTC) == Difference between "no i/o" and "no i/o <em>instructions</em>" == I've edited the reference to Smallfuck and Smallfuck/F to distinguish between "no i/o" and "no i/o <em>instructions</em>". <br> --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. --[[User:Graue|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.<br> ::--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]]. -- [[User:Smjg|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. -- [[User:Smjg|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 [http://r.s.home.mindspring.com/F/ located here]. --[[User:R.e.s.|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. --[[User:R.e.s.|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: &lambda;, R, and (''q''). It seems strange that he would give two different formulations under the same name [[P&rsquo;&rsquo;]], 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&rsquo;&rsquo; 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.) --[[User:Chris Pressey|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&rsquo;&rsquo; uses the 4-symbol alphabet &lambda;, R, (, ), where the instruction &lambda; 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&rsquo;&rsquo; 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&rsquo;&rsquo; -- 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. ::--[[User:R.e.s.|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&rsquo;&rsquo; 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&rsquo;&rsquo;-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&rsquo;&rsquo;-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&rsquo;&rsquo;-extended and he knew P&rsquo;&rsquo;-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&rsquo;&rsquo; proper - otherwise he would have based Brainfuck ''directly'' on it instead of on P&rsquo;&rsquo;-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". --[[User:Chris Pressey|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&rsquo;&rsquo; 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. --[[User:R.e.s.|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.) --[[User:Ihope127|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.) --[[User:Stux|Stux]] 13:55, 31 Oct 2005 (GMT) :::You lads haven't seen the [http://www.clifford.at/bfcpu/bfcpu.html BFCPU], have you? --[[User:ORBAT|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 <BR> 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... {{Unsigned|17:48, 11 Feb 2007|70.116.28.222}} ::How did you make the hardware match brackets? [[User:Immibis|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. --[[User:Oerjan|Ø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'' --[[User:80.221.42.204|80.221.42.204]] 22:07, 27 Oct 2005 (GMT) :That sounds like it should be in [[Esolang:The Esoteric File Archive|The Esoteric File Archive]]. Why don't you send it to graue@oceanbase.org and I'll add it for you? --[[User:Graue|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 [[Wikipedia:Text_Editor_and_Corrector|TECO]] until you mentioned it in your entry just now. It almost seems like it deserves an entry in this Wiki!--[[User:Stux|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. --[[User:Rune|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 --[[User:ORBAT|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. --[[User:Rune|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 :) --[[User:ORBAT|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? --[[User:Rune|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. --[[User:Stux|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 :) --[[User:ORBAT|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? :) --[[User:Stux|Stux]] 14:37, 31 Oct 2005 (GMT) ::::::::Not really. I personally think [[Smurf]] is a very elegant language, despite being esoteric.--[[User:Safalra|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++. --[[User:Stux|Stux]] 17:11, 31 Oct 2005 (GMT) : Maybe the interpreter should have a command line switch text/binary mode. --[[User:Zzo38|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. --[[User:Ihope127|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 --[[User:Zzo38|Zzo38]] 23:41, 13 Oct 2006 (UTC) == Implementations and External links == I just removed a large number of implementations and external links from the [http://en.wikipedia.org/Brainfuck|Brainfuck 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. -- [http://mako.cc Benjamin Mako Hill] 01:29, 18 April 2007 (UTC) :''Copyright violation removed. The information is available in the history of the Wikipedia page at [http://en.wikipedia.org/w/index.php?title=Brainfuck&oldid=123843487#External_links].'' --[[User:ais523|ais523]] 15:17, 20 April 2007 ([[User:ais523|U]][[User talk:ais523|T]][[Special:Contributions/Ais523|C]]) == 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? [[User:Aacini|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. --[[User:Lament|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 [[BrainSub|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. [[User:Aacini|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 [[Esolang:The Esoteric File Archive|The Esoteric File Archive]]? [[User:Duerig|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? --[[User:Zzo38|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. [[User:Duerig|Duerig]] 16:21, 23 July 2008 (UTC) == Who's gonna write an interpreter for bytecode (e.g. python bytecode) in brainfuck? == Is it possible? {{unsigned|02:42, 21 October 2008|91.37.37.64}} :Yes. Please sign your posts with four tildes (~). [[User:Immibis|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. {{unsigned|22:50, 29 May 2009|79.151.92.212}} == Is it possible to make an Atari 2600 interper for BF == And if you could, how much bytes would be left for the programs? {{unsigned|16:36, 18 August 2009|67.239.10.227}} :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. --[[User:Keymaker|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. [[User:Orange|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. --[[User:Keymaker|Keymaker]] 15:54, 19 August 2009 (UTC) ::Oh, make that 88x88 -- of course we'd store in bits, eight per byte... --[[User:Keymaker|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 [http://thundersf.bplaced.net/bfjit/bfjit.zip] --[[User:Thunder|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? —[[User:ehird|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). --[[User:Thunder|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 :) —[[User:ehird|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.) —[[User:Maharba|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]]. —[[User:ehird|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 &lt;>, 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. --[[User:Oerjan|Ø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. --[[User:Oerjan|Ø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? [[User:141.70.82.221|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. {{unsigned|15:38, 7 May 2012‎|65.126.124.88}} == 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. [[User:Maxdefolsch|Maxdefolsch]] ([[User talk: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 [[User:Sreekotay|Sreekotay]] ([[User talk:Sreekotay|talk]]) 04:25, 11 February 2013 (UTC)[[User:SreeKotay|SreeKotay]] ([[User talk: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 [[User:Sreekotay|Sreekotay]] ([[User talk:Sreekotay|talk]]) 04:25, 11 February 2013 (UTC)[[User:SreeKotay|SreeKotay]] ([[User talk: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 [http://www.latrobe.edu.au/phimvt/joy/j02maf.html Mathematical foundations of Joy] and designing [[Carriage]], it's abundantly clear to me that brainfuck can be explicated as a [http://concatenative.org/ concatenative] language. Also, since it doesn't use a stack, it's a counter-example (like [http://concatenative.org/wiki/view/Deque 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. * <code>&gt;</code> (resp. <code>&lt;</code>) represents a function that maps tapes to tapes where the head has been moved right (resp. left) one cell; * <code>+</code> (resp. <code>-</code>) represents a function that maps tapes to tapes where the cell under the head has been incremented (resp. decremented); * <code>.</code> 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; * <code>,</code> 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; * <code>[<var>x</var>]</code> 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.) [[User:Chris Pressey|Chris Pressey]] ([[User talk: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. --[[User:ais523|ais523]] 21:45, 25 November 2012 ([[User:ais523|U]][[User talk:ais523|T]][[Special:Contributions/Ais523|C]]) ::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.) --[[User:Zzo38|Zzo38]] ([[User talk:Zzo38|talk]]) 01:01, 26 November 2012 (UTC) :See [[Pure BF]]. --[[User:Oerjan|Ørjan]] ([[User talk:Oerjan|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: <pre> ++++ ++++ ++++ ++++[>+++++<-]>[<+++++>-]+<+[ >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<] <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<- ] </pre> 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 {{unsigned|21:40, 8 February 2013‎|70.192.195.142}} : 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. : {{unsigned|23:26, 3 April 2013‎|71.237.160.131}} :: 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. [[User:Rdebath|Rdebath]] ([[User talk: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 --[[User:Keymaker|Keymaker]] ([[User talk: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 --[[User:Keymaker|Keymaker]] ([[User talk: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) [[User:Maxdefolsch|Maxdefolsch]] ([[User talk: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. [[User:Maxdefolsch|Maxdefolsch]] ([[User talk:Maxdefolsch|talk]]) 11:13, 19 May 2014 (UTC) :There does seem to be compiled binaries there, though. (Linked from the first blog post.) --[[User:Oerjan|Ørjan]] ([[User talk:Oerjan|talk]]) 14:42, 19 May 2014 (UTC) Of course if you want a really fast interpreter you should go to [https://github.com/rdebath/Brainfuck 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. [[User:Rdebath|Rdebath]] ([[User talk:Rdebath|talk]]) 12:12, 24 May 2014 (UTC) == Syntax highlighting. == <div style="border: 1px solid #ddd;padding:1em;background-color:#f9f9f9;"> <font face="monospace,Courier"> <font color="#ff00ff">+++++</font>&nbsp;<font color="#ff00ff">+++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Set Cell #0 to 8</font><br> <font color="#a52a2a"><b>[</b></font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4 to Cell #1; this will always set Cell #1 to 4</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#a52a2a"><b>[</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">as the cell will be cleared by the loop</font><br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4*2 to Cell #2</font><br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4*3 to Cell #3</font><br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4*3 to Cell #4</font><br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4 to Cell #5</font><br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&lt;&lt;&lt;&lt;</b></font><font color="#ff00ff">-</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Decrement the loop counter in Cell #1</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#a52a2a"><b>]</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Loop till Cell #1 is zero</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #2</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #3</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Subtract 1 from Cell #4</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #6</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#a52a2a"><b>[</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#a52a2a"><b>]</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Move back to the first zero cell you find; this will</font><br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">be Cell #1 which was cleared by the previous loop</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">-</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Decrement the loop Counter in Cell #0</font><br> <font color="#a52a2a"><b>]</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Loop till Cell #0 is zero</font><br> <br> <font color="#0000ff">The result of this is:</font><br> <font color="#0000ff">Cell No :&nbsp;&nbsp; 0&nbsp;&nbsp; 1&nbsp;&nbsp; 2&nbsp;&nbsp; 3&nbsp;&nbsp; 4&nbsp;&nbsp; 5&nbsp;&nbsp; 6</font><br> <font color="#0000ff">Contents:&nbsp;&nbsp; 0&nbsp;&nbsp; 0&nbsp;&nbsp;72 104&nbsp;&nbsp;88&nbsp;&nbsp;32&nbsp;&nbsp; 8</font><br> <font color="#0000ff">Pointer :&nbsp;&nbsp; ^</font><br> <br> <font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Cell #2 has value 72 which is 'H'</font><br> <font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">---</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Subtract 3 from Cell #3 to get 101 which is 'e'</font><br> <font color="#ff00ff">+++++</font>&nbsp;<font color="#ff00ff">++</font><font color="#6a5acd">..</font><font color="#ff00ff">+++</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Likewise for 'llo' from Cell #3</font><br> <font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Cell #5 is 32 for the space</font><br> <font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">-</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Subtract 1 from Cell #4 for 87 to give a 'W'</font><br> <font color="#2e8b57"><b>&lt;</b></font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Cell #3 was set to 'o' from the end of 'Hello'</font><br> <font color="#ff00ff">+++</font><font color="#6a5acd">.</font><font color="#ff00ff">-----</font>&nbsp;<font color="#ff00ff">-</font><font color="#6a5acd">.</font><font color="#ff00ff">-----</font>&nbsp;<font color="#ff00ff">---</font><font color="#6a5acd">.</font>&nbsp;&nbsp;<font color="#0000ff">Cell #3 for 'rl' and 'd'</font><br> <font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#ff00ff">+</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #5 gives us an exclamation point</font><br> <font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">And finally a newline from Cell #6</font><br> </font></div> Well, comments ? [[User:Rdebath|Rdebath]] ([[User talk:Rdebath|talk]]) 21:04, 15 August 2014 (UTC) Looks good to me. [[User:SuperJedi224|SuperJedi224]] ([[User talk:SuperJedi224|talk]]) 19:12, 24 September 2015 (UTC) == Knuth's Arrow Notation == Has anyone ever done a Brainf*** implementation of it? [[User:SuperJedi224|SuperJedi224]] ([[User talk: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. --[[User:Keymaker|Keymaker]] ([[User talk:Keymaker|talk]]) 11:17, 19 March 2015 (UTC) :I'll try. [[User:SuperJedi224|SuperJedi224]] ([[User talk: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: [http://brain------------------------------------------------------fuck.com/programs/sts.b] Information on what kind of input it requires can be found here: [http://brain------------------------------------------------------fuck.com/sts.txt] 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. --[[User:Keymaker|Keymaker]] ([[User talk: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 <code>[]</code> 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 <code><>+-</code> 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? --[[User:Martin Büttner|Martin Büttner]] ([[User talk: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. --[[User:Keymaker|Keymaker]] ([[User talk: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 [http://mathoverflow.net/a/68358/56581 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 <code>.</code> or <code>,</code>) 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. --[[User:Martin Büttner|Martin Büttner]] ([[User talk: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. --[[User:Keymaker|Keymaker]] ([[User talk:Keymaker|talk]]) 10:13, 25 September 2015 (UTC) ::::I've asked the folks on [http://cs.stackexchange.com/q/47603/25735 Computer Science Stack Exchange] now. I'll report back here if I get any conclusive answers. --[[User:Martin Büttner|Martin Büttner]] ([[User talk: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. --[[Special:Contributions/213.162.68.156|213.162.68.156]] 12:55, 27 September 2015 (UTC) (aka [[User:Int-e|Int-e]] ([[User talk:Int-e|talk]]) 13:06, 27 September 2015 (UTC)) :Loop corrected --[[User:Int-e|Int-e]] ([[User talk:Int-e|talk]]) 15:41, 27 September 2015 (UTC) ::One more try --[[User:Int-e|Int-e]] ([[User talk:Int-e|talk]]) 16:01, 27 September 2015 (UTC) ::: So far ... If I just use the commands <code> + - &lt; &gt; </code>&nbsp;I'm getting correct results. But the command sequence <code> +++[-] </code>&nbsp;does not run properly. I expect 10 steps from it but I only get six. It seems the BF <code>[</code> 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 <code>.</code> commands output NUL bytes if possible. [[User:Rdebath|Rdebath]] ([[User talk: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. --[[User:Int-e|Int-e]] ([[User talk:Int-e|talk]]) 14:04, 28 September 2015 (UTC) ::::: [https://github.com/rdebath/Brainfuck/blob/broken-and-trivial/bf-to-for.c Here's my translator] and [https://github.com/rdebath/Brainfuck/blob/broken-and-trivial/forloop.c 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. [[User:Rdebath|Rdebath]] ([[User talk: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. --[[User:Int-e|Int-e]] ([[User talk: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 <code>.</code> to <code>&gt;.&lt;</code> is working as I said (re NUL bytes) is that by intent or just serendipity? [[User:Rdebath|Rdebath]] ([[User talk: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. --[[User:Int-e|Int-e]] ([[User talk:Int-e|talk]]) 11:09, 29 September 2015 (UTC) ::::::: Also added an initial cut of translator to my [https://github.com/rdebath/Brainfuck/tree/master/bf2any bf2any] programs. I think do better by using the control byte to the right of 'here' for an RLE loop for <code>+ and -</code> maybe for <code>&gt; and &lt;</code> too. [[User:Rdebath|Rdebath]] ([[User talk: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. [http://inversed.ru/InvMem.htm#InvMem_7 +[-[<<[+[--->&#93;-[<<<&#93;&#93;&#93;>>>-&#93;>-.---.>..>.<<<<-.<+.>>>>>.>.<<.<-.<<+.] 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, [[User:Quintopia|Quintopia]] what do you think it should be? [[User:Rdebath|Rdebath]] ([[User talk:Rdebath|talk]]) 09:59, 6 January 2016 (UTC) :As a point of clarification, the 87 byte version does not require wrapping cells, only that <code>-+</code> results in <code>0</code>, which should be true of any integer datatype. A version which does require wrapping cells is only [http://codegolf.stackexchange.com/a/68494 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 [http://brainfuck.tryitonline.net/#code=Kzw8LS0tW1s8Kz4tPisrKys-LS0tPDxdPisrXTw8PCsrLjwrKysuPC4uPC0uPDwrKy48LS4-Pj4uPC4-Pi4-LS48PDw8Ky4 71 bytes]: :<pre>+<<---[[<+>->++++>---<<]>++]<<<++.<+++.<..<-.<<++.<-.>>>.<.>>.>-.<<<<+.</pre> :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 <code>Hello World!</code>, as the example code which has stood for many years does. [[User:Primo|Primo]] ([[User talk: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 ... <dl><dd><dl><dd><pre> $ 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 $ </pre></dd></dl></dd></dl> :: 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: <dl><dd><dl><dd><pre> main() { printf("hello, world\n"); } </pre></dd></dl></dd></dl> :: 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 <code>"Hello World!\n"</code> in C string format <dl><dd><dl><dd><div style="border: 1px solid #ddd;padding:1em;background-color:#f9f9f9;font-family: monospace,Courier;"> <font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+++++++++</font><font color="#a52a2a"><b>[</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">++++++++</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#6a5acd">.</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+++++++</font><font color="#a52a2a"><b>[</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">++++</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">+</font><font color="#6a5acd">.</font><font color="#ff00ff">+++++++</font><font color="#6a5acd">..</font><font color="#ff00ff">+++</font><font color="#6a5acd">.</font><font color="#a52a2a"><b>[</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++++++++</font><font color="#a52a2a"><b>[</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">++++</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><br> <font color="#2e8b57"><b>&lt;</b></font><font color="#6a5acd">.</font><span style="background-color: #ff0000"><font color="#ffffff">#</font></span><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+++++++++++</font><font color="#a52a2a"><b>[</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">+++++</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#6a5acd">.</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++++++++</font><font color="#a52a2a"><b>[</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">+++</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#6a5acd">.</font><font color="#ff00ff">+++</font><font color="#6a5acd">.</font><font color="#ff00ff">------</font><font color="#6a5acd">.</font><font color="#ff00ff">--------</font><font color="#6a5acd">.</font><font color="#a52a2a"><b>[</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++++++++</font><font color="#a52a2a"><b>[</b></font><br> <font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">++++</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">+</font><font color="#6a5acd">.</font><font color="#a52a2a"><b>[</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#ff00ff">++++++++++</font><font color="#6a5acd">.</font> </div></dd></dl></dd></dl> :: Don't forget the newline! I'll cost you a 14 instruction penalty, which takes the '71' up to 88 total. ::[[User:Rdebath|Rdebath]] ([[User talk: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: <pre>+<--[[<++>->-->+++>+<<<]-->++++]<<.<<-.<<..+++.>.<<-.>.+++.------.>>-.<+.>>.</pre> Not rolling off the left side would cost an additional <code>>></code>. With non-wrapping cells, the best I could find is 85: <pre>->+>+>>+>---[++++++++++++[>+++++>++>+<<<-]+<+]>>+.>++.>..>.>>.<+.<.+++.<.<-.>>>>+.>+.</pre> -[[User:Primo|Primo]] ([[User talk: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''. [[User:IAM|IAM]] ([[User talk: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". --[[User:Quintopia|Quintopia]] ([[User talk:Quintopia|talk]]) 21:03, 26 April 2016 (UTC) :@[[User:IAM|IAM]] and [[User:Quintopia|Quintopia]] ([[User talk:IAM|ta]][[User talk:Quintopia|lk]]): 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! [[User:Kaa-kun|Carbuncle]] ([[User talk:Kaa-kun|talk]] • [[Special:Contributions/Kaa-kun|contribs]] • [[Special:DeletedContributions/Kaa-kun|d. contribs]]) 14:45, 21 August 2018 (UTC) == A possible proof == This [[Turing-completeness]] proof tries to compile [[brainfuck]] to the [[Z3]] computer, but [[User:A|I]] am not sure whether it is valid. Please verify it.<br> If this is verified, can it be one of the proofs used in the [[brainfuck]] page?--[[User:A|A]] ([[User talk: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.) --[[User:DanielCristofani|DanielCristofani]] ([[User talk:DanielCristofani|talk]]) 02:34, 2 July 2020 (UTC) === Addition, subtraction, etc. === It is quite certain that these are already implemented. <pre> 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] </pre> (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.<br> 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.<br> This is a possible loading algorithm(to load a value from left to right, starting from left): <pre> >[-]<[->+<]> </pre> This is a possible storing algorithm(the reverse of the above, starting from right): <pre> <[-]>[-<+>]< </pre> === 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.<br> [[brainfuck]] can easily achive this: <pre> 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 </pre> (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? --[[User:Bog&#39;riquet De FerChef|Bog&#39;riquet De FerChef]] ([[User talk:Bog&#39;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. [[User:Rdebath|Rdebath]] ([[User talk: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. [[User:DanielCristofani|DanielCristofani]] ([[User talk:DanielCristofani|talk]]) 06:07, 17 February 2021 (UTC)'
New page wikitext, after the edit (new_wikitext)
'{{lowercase}} == New Windows Implementation == I'm making a full-featured Brainfuck implementation for Windows: [http://code.google.com/p/winbfinterpreter/] 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. --[[User:98.168.145.187|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? --[[User:Oleg|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. [[User:Orange|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. {{unsigned|18:15, 31 July 2009|98.168.145.187}} :::: I uploaded Beta 2, get it from the same link. {{unsigned|20:18, 31 July 2009|98.168.145.187}} ::::: I uploaded Beta 3, just addressed a small issue with thread priority to make sure everything stays responsive. {{unsigned|20:36, 31 July 2009|98.168.145.187}} ::: 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. --[[User:Oleg|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? {{unsigned|14:45, 1 August 2009|98.168.145.187}} ::::: I'm making the current code character that is being executed in debug mode be highlighted too. [[User:98.168.145.187|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. [[User:98.168.145.187|98.168.145.187]] 20:03, 1 August 2009 (UTC) : Beta 5 has been uploaded --[[User:98.168.145.187|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: :*[http://greasemonkey.shadowarts.org/bf8.zip 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? --[[User:GreaseMonkey|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. --[[User:80.174.59.115|80.174.59.115]] 17:12, 30 September 2011 (UTC) :*[http://www.mediafire.com/?o463xy29ollpa8v BF to COM compiler] can do that in ~1 second. {{unsigned|02:24, 15 January 2011|188.168.83.73}} :I agree. A common program that could be used to benchmark compilers would be nice. :[http://software.xfx.net/utilities/vbbfck/index.php 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. --[[User:Xfx|xfx]] 06:52, 18 April 2007 (UTC) ::You may want to check these two as well - [http://mozaika.com.au/oleg/brainf bff4] and [http://swapped.cc/bff bff]. Also [http://esoteric.voxelperfect.net/w/index.php?title=Brainfuck&diff=9065&oldid=9033 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. [[User:Apankrat|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. --[[User:IslandHopper973|IslandHopper973]] 20:19, 26 April 2007 (UTC) ::Are all above mentioned programs compilers? I think this info is missing. My [http://www.geocities.com/brainsub BrainSub] compiler do it in 0.05 seconds with 8bit cells and 3 min. 37 secs. with 16bit cells. [[User:Aacini|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 [http://swapped.cc/bff bff] and [http://mazonka.com/brainf 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. --[[User:Mazonka|Mazonka]] ::That program just posted runs in <s>7260ms</s> 5878ms (plus 2ms to compile it) on my compiler. But I agree, we need a standard test machine. [[User:Immibis|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. {{unsigned|01:23, 7 November 2010|216.70.157.15}} 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. {{unsigned|01:23, 7 November 2010|216.70.157.15}} *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. {{unsigned|01:23, 7 November 2010|216.70.157.15}} :(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. {{unsigned|01:23, 7 November 2010|216.70.157.15}} :(3) Failed C conversion. Didn't work. Didn't locate error. ::How did you convert things to C? {{unsigned|01:23, 7 November 2010|216.70.157.15}} :(4) unable to locate, est. is 4 sec based on comments :(5) My straightforward, unpublished, BF interpreter in C. --[[User:98.209.220.26|98.209.220.26]] 20:01, 28 August 2010 (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. --[[User:Graue|Graue]] 15:35, 9 Jun 2005 (GMT) :Theoretically, 2 cells (cf [[Minsky machine]]); Frank Faase has a proof using 5 cells. --[[User:Chris Pressey|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. --[[User:Oerjan|Ø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? --[[User:Rune|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? --[[User:Graue|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. --[[User:Rune|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 [[User:Nerowolfe|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. [[User:Immibis|Immibis]] 23:21, 5 June 2009 (UTC) Here are some link on the topic. Attention!: russian language, please use [http://translate.google.com Google.translate] if needed. * Branfuck interpreter in Lua: http://habrahabr.ru/blogs/crazydev/112919/ * Branfuck interpreter in Bash: http://habrahabr.ru/blogs/crazydev/112989/ * Branfuck interpreter in Mercury: http://habrahabr.ru/blogs/crazydev/113099/ * Branfuck JIT (AOT really) complier in Pascal: http://habrahabr.ru/blogs/development/113339/ {{unsigned|14:59, 10 February 2011|91.195.22.25}} == 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 <blockquote>1^a 0 1^b 0 1^c ... 00 1^A 0 1^B 0 1^C ... 00</blockquote> 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.)<br> --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. --[[User:Keymaker|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. --[[User:Zzo38|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... --[[User:Tromp|Tromp]] 00:23, 23 March 2009 (UTC) == Difference between "no i/o" and "no i/o <em>instructions</em>" == I've edited the reference to Smallfuck and Smallfuck/F to distinguish between "no i/o" and "no i/o <em>instructions</em>". <br> --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. --[[User:Graue|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.<br> ::--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]]. -- [[User:Smjg|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. -- [[User:Smjg|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 [http://r.s.home.mindspring.com/F/ located here]. --[[User:R.e.s.|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. --[[User:R.e.s.|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: &lambda;, R, and (''q''). It seems strange that he would give two different formulations under the same name [[P&rsquo;&rsquo;]], 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&rsquo;&rsquo; 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.) --[[User:Chris Pressey|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&rsquo;&rsquo; uses the 4-symbol alphabet &lambda;, R, (, ), where the instruction &lambda; 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&rsquo;&rsquo; 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&rsquo;&rsquo; -- 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. ::--[[User:R.e.s.|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&rsquo;&rsquo; 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&rsquo;&rsquo;-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&rsquo;&rsquo;-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&rsquo;&rsquo;-extended and he knew P&rsquo;&rsquo;-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&rsquo;&rsquo; proper - otherwise he would have based Brainfuck ''directly'' on it instead of on P&rsquo;&rsquo;-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". --[[User:Chris Pressey|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&rsquo;&rsquo; 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. --[[User:R.e.s.|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.) --[[User:Ihope127|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.) --[[User:Stux|Stux]] 13:55, 31 Oct 2005 (GMT) :::You lads haven't seen the [http://www.clifford.at/bfcpu/bfcpu.html BFCPU], have you? --[[User:ORBAT|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 <BR> 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... {{Unsigned|17:48, 11 Feb 2007|70.116.28.222}} ::How did you make the hardware match brackets? [[User:Immibis|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. --[[User:Oerjan|Ø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'' --[[User:80.221.42.204|80.221.42.204]] 22:07, 27 Oct 2005 (GMT) :That sounds like it should be in [[Esolang:The Esoteric File Archive|The Esoteric File Archive]]. Why don't you send it to graue@oceanbase.org and I'll add it for you? --[[User:Graue|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 [[Wikipedia:Text_Editor_and_Corrector|TECO]] until you mentioned it in your entry just now. It almost seems like it deserves an entry in this Wiki!--[[User:Stux|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. --[[User:Rune|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 --[[User:ORBAT|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. --[[User:Rune|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 :) --[[User:ORBAT|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? --[[User:Rune|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. --[[User:Stux|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 :) --[[User:ORBAT|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? :) --[[User:Stux|Stux]] 14:37, 31 Oct 2005 (GMT) ::::::::Not really. I personally think [[Smurf]] is a very elegant language, despite being esoteric.--[[User:Safalra|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++. --[[User:Stux|Stux]] 17:11, 31 Oct 2005 (GMT) : Maybe the interpreter should have a command line switch text/binary mode. --[[User:Zzo38|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. --[[User:Ihope127|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 --[[User:Zzo38|Zzo38]] 23:41, 13 Oct 2006 (UTC) == Implementations and External links == I just removed a large number of implementations and external links from the [http://en.wikipedia.org/Brainfuck|Brainfuck 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. -- [http://mako.cc Benjamin Mako Hill] 01:29, 18 April 2007 (UTC) :''Copyright violation removed. The information is available in the history of the Wikipedia page at [http://en.wikipedia.org/w/index.php?title=Brainfuck&oldid=123843487#External_links].'' --[[User:ais523|ais523]] 15:17, 20 April 2007 ([[User:ais523|U]][[User talk:ais523|T]][[Special:Contributions/Ais523|C]]) == 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? [[User:Aacini|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. --[[User:Lament|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 [[BrainSub|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. [[User:Aacini|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 [[Esolang:The Esoteric File Archive|The Esoteric File Archive]]? [[User:Duerig|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? --[[User:Zzo38|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. [[User:Duerig|Duerig]] 16:21, 23 July 2008 (UTC) == Who's gonna write an interpreter for bytecode (e.g. python bytecode) in brainfuck? == Is it possible? {{unsigned|02:42, 21 October 2008|91.37.37.64}} :Yes. Please sign your posts with four tildes (~). [[User:Immibis|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. {{unsigned|22:50, 29 May 2009|79.151.92.212}} == Is it possible to make an Atari 2600 interper for BF == And if you could, how much bytes would be left for the programs? {{unsigned|16:36, 18 August 2009|67.239.10.227}} :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. --[[User:Keymaker|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. [[User:Orange|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. --[[User:Keymaker|Keymaker]] 15:54, 19 August 2009 (UTC) ::Oh, make that 88x88 -- of course we'd store in bits, eight per byte... --[[User:Keymaker|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 [http://thundersf.bplaced.net/bfjit/bfjit.zip] --[[User:Thunder|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? —[[User:ehird|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). --[[User:Thunder|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 :) —[[User:ehird|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.) —[[User:Maharba|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]]. —[[User:ehird|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 &lt;>, 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. --[[User:Oerjan|Ø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. --[[User:Oerjan|Ø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? [[User:141.70.82.221|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. {{unsigned|15:38, 7 May 2012‎|65.126.124.88}} == 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. [[User:Maxdefolsch|Maxdefolsch]] ([[User talk: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 [[User:Sreekotay|Sreekotay]] ([[User talk:Sreekotay|talk]]) 04:25, 11 February 2013 (UTC)[[User:SreeKotay|SreeKotay]] ([[User talk: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 [[User:Sreekotay|Sreekotay]] ([[User talk:Sreekotay|talk]]) 04:25, 11 February 2013 (UTC)[[User:SreeKotay|SreeKotay]] ([[User talk: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 [http://www.latrobe.edu.au/phimvt/joy/j02maf.html Mathematical foundations of Joy] and designing [[Carriage]], it's abundantly clear to me that brainfuck can be explicated as a [http://concatenative.org/ concatenative] language. Also, since it doesn't use a stack, it's a counter-example (like [http://concatenative.org/wiki/view/Deque 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. * <code>&gt;</code> (resp. <code>&lt;</code>) represents a function that maps tapes to tapes where the head has been moved right (resp. left) one cell; * <code>+</code> (resp. <code>-</code>) represents a function that maps tapes to tapes where the cell under the head has been incremented (resp. decremented); * <code>.</code> 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; * <code>,</code> 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; * <code>[<var>x</var>]</code> 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.) [[User:Chris Pressey|Chris Pressey]] ([[User talk: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. --[[User:ais523|ais523]] 21:45, 25 November 2012 ([[User:ais523|U]][[User talk:ais523|T]][[Special:Contributions/Ais523|C]]) ::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.) --[[User:Zzo38|Zzo38]] ([[User talk:Zzo38|talk]]) 01:01, 26 November 2012 (UTC) :See [[Pure BF]]. --[[User:Oerjan|Ørjan]] ([[User talk:Oerjan|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: <pre> ++++ ++++ ++++ ++++[>+++++<-]>[<+++++>-]+<+[ >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<] <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<- ] </pre> 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 {{unsigned|21:40, 8 February 2013‎|70.192.195.142}} : 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. : {{unsigned|23:26, 3 April 2013‎|71.237.160.131}} :: 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. [[User:Rdebath|Rdebath]] ([[User talk: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 --[[User:Keymaker|Keymaker]] ([[User talk: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 --[[User:Keymaker|Keymaker]] ([[User talk: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) [[User:Maxdefolsch|Maxdefolsch]] ([[User talk: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. [[User:Maxdefolsch|Maxdefolsch]] ([[User talk:Maxdefolsch|talk]]) 11:13, 19 May 2014 (UTC) :There does seem to be compiled binaries there, though. (Linked from the first blog post.) --[[User:Oerjan|Ørjan]] ([[User talk:Oerjan|talk]]) 14:42, 19 May 2014 (UTC) Of course if you want a really fast interpreter you should go to [https://github.com/rdebath/Brainfuck 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. [[User:Rdebath|Rdebath]] ([[User talk:Rdebath|talk]]) 12:12, 24 May 2014 (UTC) == Syntax highlighting. == <div style="border: 1px solid #ddd;padding:1em;background-color:#f9f9f9;"> <font face="monospace,Courier"> <font color="#ff00ff">+++++</font>&nbsp;<font color="#ff00ff">+++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Set Cell #0 to 8</font><br> <font color="#a52a2a"><b>[</b></font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4 to Cell #1; this will always set Cell #1 to 4</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#a52a2a"><b>[</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">as the cell will be cleared by the loop</font><br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4*2 to Cell #2</font><br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4*3 to Cell #3</font><br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+++</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4*3 to Cell #4</font><br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 4 to Cell #5</font><br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&lt;&lt;&lt;&lt;</b></font><font color="#ff00ff">-</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Decrement the loop counter in Cell #1</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#a52a2a"><b>]</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Loop till Cell #1 is zero</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #2</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #3</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Subtract 1 from Cell #4</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#ff00ff">+</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #6</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#a52a2a"><b>[</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#a52a2a"><b>]</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Move back to the first zero cell you find; this will</font><br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">be Cell #1 which was cleared by the previous loop</font><br> &nbsp;&nbsp;&nbsp;&nbsp;<font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">-</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Decrement the loop Counter in Cell #0</font><br> <font color="#a52a2a"><b>]</b></font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Loop till Cell #0 is zero</font><br> <br> <font color="#0000ff">The result of this is:</font><br> <font color="#0000ff">Cell No :&nbsp;&nbsp; 0&nbsp;&nbsp; 1&nbsp;&nbsp; 2&nbsp;&nbsp; 3&nbsp;&nbsp; 4&nbsp;&nbsp; 5&nbsp;&nbsp; 6</font><br> <font color="#0000ff">Contents:&nbsp;&nbsp; 0&nbsp;&nbsp; 0&nbsp;&nbsp;72 104&nbsp;&nbsp;88&nbsp;&nbsp;32&nbsp;&nbsp; 8</font><br> <font color="#0000ff">Pointer :&nbsp;&nbsp; ^</font><br> <br> <font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Cell #2 has value 72 which is 'H'</font><br> <font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">---</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Subtract 3 from Cell #3 to get 101 which is 'e'</font><br> <font color="#ff00ff">+++++</font>&nbsp;<font color="#ff00ff">++</font><font color="#6a5acd">..</font><font color="#ff00ff">+++</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Likewise for 'llo' from Cell #3</font><br> <font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Cell #5 is 32 for the space</font><br> <font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">-</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Subtract 1 from Cell #4 for 87 to give a 'W'</font><br> <font color="#2e8b57"><b>&lt;</b></font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Cell #3 was set to 'o' from the end of 'Hello'</font><br> <font color="#ff00ff">+++</font><font color="#6a5acd">.</font><font color="#ff00ff">-----</font>&nbsp;<font color="#ff00ff">-</font><font color="#6a5acd">.</font><font color="#ff00ff">-----</font>&nbsp;<font color="#ff00ff">---</font><font color="#6a5acd">.</font>&nbsp;&nbsp;<font color="#0000ff">Cell #3 for 'rl' and 'd'</font><br> <font color="#2e8b57"><b>&gt;&gt;</b></font><font color="#ff00ff">+</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">Add 1 to Cell #5 gives us an exclamation point</font><br> <font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++</font><font color="#6a5acd">.</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000ff">And finally a newline from Cell #6</font><br> </font></div> Well, comments ? [[User:Rdebath|Rdebath]] ([[User talk:Rdebath|talk]]) 21:04, 15 August 2014 (UTC) Looks good to me. [[User:SuperJedi224|SuperJedi224]] ([[User talk:SuperJedi224|talk]]) 19:12, 24 September 2015 (UTC) == Knuth's Arrow Notation == Has anyone ever done a Brainf*** implementation of it? [[User:SuperJedi224|SuperJedi224]] ([[User talk: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. --[[User:Keymaker|Keymaker]] ([[User talk:Keymaker|talk]]) 11:17, 19 March 2015 (UTC) :I'll try. [[User:SuperJedi224|SuperJedi224]] ([[User talk: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: [http://brain------------------------------------------------------fuck.com/programs/sts.b] Information on what kind of input it requires can be found here: [http://brain------------------------------------------------------fuck.com/sts.txt] 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. --[[User:Keymaker|Keymaker]] ([[User talk: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 <code>[]</code> 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 <code><>+-</code> 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? --[[User:Martin Büttner|Martin Büttner]] ([[User talk: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. --[[User:Keymaker|Keymaker]] ([[User talk: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 [http://mathoverflow.net/a/68358/56581 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 <code>.</code> or <code>,</code>) 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. --[[User:Martin Büttner|Martin Büttner]] ([[User talk: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. --[[User:Keymaker|Keymaker]] ([[User talk:Keymaker|talk]]) 10:13, 25 September 2015 (UTC) ::::I've asked the folks on [http://cs.stackexchange.com/q/47603/25735 Computer Science Stack Exchange] now. I'll report back here if I get any conclusive answers. --[[User:Martin Büttner|Martin Büttner]] ([[User talk: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. --[[Special:Contributions/213.162.68.156|213.162.68.156]] 12:55, 27 September 2015 (UTC) (aka [[User:Int-e|Int-e]] ([[User talk:Int-e|talk]]) 13:06, 27 September 2015 (UTC)) :Loop corrected --[[User:Int-e|Int-e]] ([[User talk:Int-e|talk]]) 15:41, 27 September 2015 (UTC) ::One more try --[[User:Int-e|Int-e]] ([[User talk:Int-e|talk]]) 16:01, 27 September 2015 (UTC) ::: So far ... If I just use the commands <code> + - &lt; &gt; </code>&nbsp;I'm getting correct results. But the command sequence <code> +++[-] </code>&nbsp;does not run properly. I expect 10 steps from it but I only get six. It seems the BF <code>[</code> 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 <code>.</code> commands output NUL bytes if possible. [[User:Rdebath|Rdebath]] ([[User talk: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. --[[User:Int-e|Int-e]] ([[User talk:Int-e|talk]]) 14:04, 28 September 2015 (UTC) ::::: [https://github.com/rdebath/Brainfuck/blob/broken-and-trivial/bf-to-for.c Here's my translator] and [https://github.com/rdebath/Brainfuck/blob/broken-and-trivial/forloop.c 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. [[User:Rdebath|Rdebath]] ([[User talk: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. --[[User:Int-e|Int-e]] ([[User talk: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 <code>.</code> to <code>&gt;.&lt;</code> is working as I said (re NUL bytes) is that by intent or just serendipity? [[User:Rdebath|Rdebath]] ([[User talk: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. --[[User:Int-e|Int-e]] ([[User talk:Int-e|talk]]) 11:09, 29 September 2015 (UTC) ::::::: Also added an initial cut of translator to my [https://github.com/rdebath/Brainfuck/tree/master/bf2any bf2any] programs. I think do better by using the control byte to the right of 'here' for an RLE loop for <code>+ and -</code> maybe for <code>&gt; and &lt;</code> too. [[User:Rdebath|Rdebath]] ([[User talk: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. [http://inversed.ru/InvMem.htm#InvMem_7 +[-[<<[+[--->&#93;-[<<<&#93;&#93;&#93;>>>-&#93;>-.---.>..>.<<<<-.<+.>>>>>.>.<<.<-.<<+.] 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, [[User:Quintopia|Quintopia]] what do you think it should be? [[User:Rdebath|Rdebath]] ([[User talk:Rdebath|talk]]) 09:59, 6 January 2016 (UTC) :As a point of clarification, the 87 byte version does not require wrapping cells, only that <code>-+</code> results in <code>0</code>, which should be true of any integer datatype. A version which does require wrapping cells is only [http://codegolf.stackexchange.com/a/68494 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 [http://brainfuck.tryitonline.net/#code=Kzw8LS0tW1s8Kz4tPisrKys-LS0tPDxdPisrXTw8PCsrLjwrKysuPC4uPC0uPDwrKy48LS4-Pj4uPC4-Pi4-LS48PDw8Ky4 71 bytes]: :<pre>+<<---[[<+>->++++>---<<]>++]<<<++.<+++.<..<-.<<++.<-.>>>.<.>>.>-.<<<<+.</pre> :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 <code>Hello World!</code>, as the example code which has stood for many years does. [[User:Primo|Primo]] ([[User talk: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 ... <dl><dd><dl><dd><pre> $ 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 $ </pre></dd></dl></dd></dl> :: 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: <dl><dd><dl><dd><pre> main() { printf("hello, world\n"); } </pre></dd></dl></dd></dl> :: 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 <code>"Hello World!\n"</code> in C string format <dl><dd><dl><dd><div style="border: 1px solid #ddd;padding:1em;background-color:#f9f9f9;font-family: monospace,Courier;"> <font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+++++++++</font><font color="#a52a2a"><b>[</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">++++++++</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#6a5acd">.</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+++++++</font><font color="#a52a2a"><b>[</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">++++</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">+</font><font color="#6a5acd">.</font><font color="#ff00ff">+++++++</font><font color="#6a5acd">..</font><font color="#ff00ff">+++</font><font color="#6a5acd">.</font><font color="#a52a2a"><b>[</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++++++++</font><font color="#a52a2a"><b>[</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">++++</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><br> <font color="#2e8b57"><b>&lt;</b></font><font color="#6a5acd">.</font><span style="background-color: #ff0000"><font color="#ffffff">#</font></span><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">+++++++++++</font><font color="#a52a2a"><b>[</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">+++++</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#6a5acd">.</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++++++++</font><font color="#a52a2a"><b>[</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">+++</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#6a5acd">.</font><font color="#ff00ff">+++</font><font color="#6a5acd">.</font><font color="#ff00ff">------</font><font color="#6a5acd">.</font><font color="#ff00ff">--------</font><font color="#6a5acd">.</font><font color="#a52a2a"><b>[</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">++++++++</font><font color="#a52a2a"><b>[</b></font><br> <font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">++++</font><font color="#2e8b57"><b>&gt;</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#2e8b57"><b>&lt;</b></font><font color="#ff00ff">+</font><font color="#6a5acd">.</font><font color="#a52a2a"><b>[</b></font><font color="#ff00ff">-</font><font color="#a52a2a"><b>]</b></font><font color="#ff00ff">++++++++++</font><font color="#6a5acd">.</font> </div></dd></dl></dd></dl> :: Don't forget the newline! I'll cost you a 14 instruction penalty, which takes the '71' up to 88 total. ::[[User:Rdebath|Rdebath]] ([[User talk: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: <pre>+<--[[<++>->-->+++>+<<<]-->++++]<<.<<-.<<..+++.>.<<-.>.+++.------.>>-.<+.>>.</pre> Not rolling off the left side would cost an additional <code>>></code>. With non-wrapping cells, the best I could find is 85: <pre>->+>+>>+>---[++++++++++++[>+++++>++>+<<<-]+<+]>>+.>++.>..>.>>.<+.<.+++.<.<-.>>>>+.>+.</pre> -[[User:Primo|Primo]] ([[User talk: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''. [[User:IAM|IAM]] ([[User talk: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". --[[User:Quintopia|Quintopia]] ([[User talk:Quintopia|talk]]) 21:03, 26 April 2016 (UTC) :@[[User:IAM|IAM]] and [[User:Quintopia|Quintopia]] ([[User talk:IAM|ta]][[User talk:Quintopia|lk]]): 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! [[User:Kaa-kun|Carbuncle]] ([[User talk:Kaa-kun|talk]] • [[Special:Contributions/Kaa-kun|contribs]] • [[Special:DeletedContributions/Kaa-kun|d. contribs]]) 14:45, 21 August 2018 (UTC) == A possible proof == This [[Turing-completeness]] proof tries to compile [[brainfuck]] to the [[Z3]] computer, but [[User:A|I]] am not sure whether it is valid. Please verify it.<br> If this is verified, can it be one of the proofs used in the [[brainfuck]] page?--[[User:A|A]] ([[User talk: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.) --[[User:DanielCristofani|DanielCristofani]] ([[User talk:DanielCristofani|talk]]) 02:34, 2 July 2020 (UTC) === Addition, subtraction, etc. === It is quite certain that these are already implemented. <pre> 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] </pre> (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.<br> 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.<br> This is a possible loading algorithm(to load a value from left to right, starting from left): <pre> >[-]<[->+<]> </pre> This is a possible storing algorithm(the reverse of the above, starting from right): <pre> <[-]>[-<+>]< </pre> === 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.<br> [[brainfuck]] can easily achive this: <pre> 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 </pre> (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? --[[User:Bog&#39;riquet De FerChef|Bog&#39;riquet De FerChef]] ([[User talk:Bog&#39;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. [[User:Rdebath|Rdebath]] ([[User talk: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. [[User:DanielCristofani|DanielCristofani]] ([[User talk:DanielCristofani|talk]]) 06:07, 17 February 2021 (UTC) == New BF Derivative (DaBooty) (Based on the “How to pronounce ( ͡° ͜ʖ ͡°)” song) == Digits for number literals Look at that booty, 1 show me the booty 2 Give me the booty, 3 I need the the booty 4 Back up the booty, 5 I hate the booty 6 I like the booty, 7 oh what a booty 8 Shaking that booty, 9 I saw the booty 0 I want the booty, decimal point Math X, lord what a booty, Y = X+Y X, Bring on the booty, Y = X-Y X, give up the booty, Y = X*Y X, Loving the booty, Y = X/Y X, Sleeping booty, Y = X%Y X, round booty, Y = X integer divided by Y X, Down for the booty, Y = X to the power of Y X, I want the booty = 0-X Suing the booty, X, scared of the booty = enclose X in parentheses All math expressions end with “Hunting the booty” Commands: X, Casing the booty, = print X X, getting the booty, = print X as Unicode X, Beautiful booty, =Set current cell to X smoking booty = current cell value X, Talk to the booty,= cell X value X, more booty = make pointer go right X cells (left if negative) Fine booty, X, All about the booty, (code), big old booty = run code until current cell = X Serious booty,X, amazing booty, (code), I'll take the booty, (code2), where is the booty = run code1 if current cell=X, code2 otherwise Stare at the booty = input number, store in pointed cell walking the booty = input Unicode character, store in pointed cell Touching the booty, = Sets the current point of execution to the location of the pointer X, whos got the booty = Inserts X new cells before the current pointer, shifting all following cells to the right. X, Grabbing the booty, = Removes the cell at the current pointer and the next (X-1) cells, shifting all following cells to the left. X, Harder booty, = Locks X cells and prevents it from being changed. Any attempt to change it silently fails. (This includes deleting it) X, softer booty = Unlocks X previously locked cells and allows it to be edited again. Calling this on a already unlocked cell does nothing. Foreign booty = swaps the program array (in Unicode) with the cell array so that their roles are reversed until another “Foreign booty” swaps it back, much like the X operator in Braintwist X, home booty = Wait X seconds. ( ͡° ͜ʖ ͡°) = End the program.'
Unified diff of changes made by edit (edit_diff)
'@@ -760,2 +760,88 @@ ::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. [[User:DanielCristofani|DanielCristofani]] ([[User talk:DanielCristofani|talk]]) 06:07, 17 February 2021 (UTC) + +== New BF Derivative (DaBooty) (Based on the “How to pronounce ( ͡° ͜ʖ ͡°)” song) == + +Digits for number literals +Look at that booty, 1 + +show me the booty 2 + +Give me the booty, 3 + +I need the the booty 4 + +Back up the booty, 5 + + I hate the booty 6 + +I like the booty, 7 + +oh what a booty 8 + +Shaking that booty, 9 + +I saw the booty 0 + +I want the booty, decimal point + +Math + + +X, lord what a booty, Y = X+Y + +X, Bring on the booty, Y = X-Y + + X, give up the booty, Y = X*Y + +X, Loving the booty, Y = X/Y + +X, Sleeping booty, Y = X%Y + +X, round booty, Y = X integer divided by Y + +X, Down for the booty, Y = X to the power of Y +X, I want the booty = 0-X + +Suing the booty, X, scared of the booty = enclose X in parentheses + +All math expressions end with “Hunting the booty” + +Commands: + + +X, Casing the booty, = print X + +X, getting the booty, = print X as Unicode + +X, Beautiful booty, =Set current cell to X + + smoking booty = current cell value + +X, Talk to the booty,= cell X value + +X, more booty = make pointer go right X cells (left if negative) + +Fine booty, X, All about the booty, (code), big old booty = run code until current cell = X + +Serious booty,X, amazing booty, (code), I'll take the booty, (code2), where is the booty += run code1 if current cell=X, code2 otherwise + +Stare at the booty = input number, store in pointed cell + +walking the booty = input Unicode character, store in pointed cell + +Touching the booty, = Sets the current point of execution to the location of the pointer + +X, whos got the booty = Inserts X new cells before the current pointer, shifting all following cells to the right. +X, Grabbing the booty, = Removes the cell at the current pointer and the next (X-1) cells, shifting all following cells to the left. + +X, Harder booty, = Locks X cells and prevents it from being changed. Any attempt to change it silently fails. (This includes deleting it) + +X, softer booty = Unlocks X previously locked cells and allows it to be edited again. Calling this on a already unlocked cell does nothing. + +Foreign booty = swaps the program array (in Unicode) with the cell array so that their roles are reversed until another “Foreign booty” swaps it back, much like the X operator in Braintwist + +X, home booty = Wait X seconds. + +( ͡° ͜ʖ ͡°) = End the program. '
New page size (new_size)
89701
Old page size (old_size)
87407
Lines added in edit (added_lines)
[ 0 => '', 1 => '== New BF Derivative (DaBooty) (Based on the “How to pronounce ( ͡° ͜ʖ ͡°)” song) ==', 2 => '', 3 => 'Digits for number literals', 4 => 'Look at that booty, 1', 5 => '', 6 => 'show me the booty 2', 7 => '', 8 => 'Give me the booty, 3', 9 => '', 10 => 'I need the the booty 4', 11 => '', 12 => 'Back up the booty, 5', 13 => '', 14 => ' I hate the booty 6', 15 => '', 16 => 'I like the booty, 7', 17 => '', 18 => 'oh what a booty 8', 19 => '', 20 => 'Shaking that booty, 9', 21 => '', 22 => 'I saw the booty 0', 23 => '', 24 => 'I want the booty, decimal point', 25 => '', 26 => 'Math', 27 => '', 28 => '', 29 => 'X, lord what a booty, Y = X+Y', 30 => '', 31 => 'X, Bring on the booty, Y = X-Y', 32 => '', 33 => ' X, give up the booty, Y = X*Y', 34 => '', 35 => 'X, Loving the booty, Y = X/Y', 36 => '', 37 => 'X, Sleeping booty, Y = X%Y ', 38 => '', 39 => 'X, round booty, Y = X integer divided by Y', 40 => '', 41 => 'X, Down for the booty, Y = X to the power of Y', 42 => 'X, I want the booty = 0-X', 43 => '', 44 => 'Suing the booty, X, scared of the booty = enclose X in parentheses ', 45 => '', 46 => 'All math expressions end with “Hunting the booty”', 47 => ' ', 48 => 'Commands:', 49 => '', 50 => '', 51 => 'X, Casing the booty, = print X', 52 => '', 53 => 'X, getting the booty, = print X as Unicode ', 54 => '', 55 => 'X, Beautiful booty, =Set current cell to X', 56 => '', 57 => ' smoking booty = current cell value', 58 => '', 59 => 'X, Talk to the booty,= cell X value ', 60 => '', 61 => 'X, more booty = make pointer go right X cells (left if negative)', 62 => '', 63 => 'Fine booty, X, All about the booty, (code), big old booty = run code until current cell = X', 64 => '', 65 => 'Serious booty,X, amazing booty, (code), I'll take the booty, (code2), where is the booty ', 66 => '= run code1 if current cell=X, code2 otherwise', 67 => '', 68 => 'Stare at the booty = input number, store in pointed cell', 69 => '', 70 => 'walking the booty = input Unicode character, store in pointed cell', 71 => '', 72 => 'Touching the booty, = Sets the current point of execution to the location of the pointer', 73 => '', 74 => 'X, whos got the booty = Inserts X new cells before the current pointer, shifting all following cells to the right.', 75 => 'X, Grabbing the booty, = Removes the cell at the current pointer and the next (X-1) cells, shifting all following cells to the left.', 76 => '', 77 => 'X, Harder booty, = Locks X cells and prevents it from being changed. Any attempt to change it silently fails. (This includes deleting it)', 78 => '', 79 => 'X, softer booty = Unlocks X previously locked cells and allows it to be edited again. Calling this on a already unlocked cell does nothing.', 80 => '', 81 => 'Foreign booty = swaps the program array (in Unicode) with the cell array so that their roles are reversed until another “Foreign booty” swaps it back, much like the X operator in Braintwist', 82 => '', 83 => 'X, home booty = Wait X seconds.', 84 => '', 85 => '( ͡° ͜ʖ ͡°) = End the program.' ]
Unix timestamp of change (timestamp)
1632061710