Talk:Brainfuck/Archive 1
 | This is an archive of past discussions about Brainfuck. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
| Archive 1 | Archive 2 |
Initial text
Well written article. In addition some links to other minimalist or just simple programming languages would be nice.
An an article about Knuths general assembly language which he uses in his books 'The Art of Programming'.
It's also almost a perfect copy of http://www.muppetlabs.com/~breadbox/bf/
It doesn't have any copyright info, is this acceptable???
-AlanD
You do not need to declare something copyright to make it copyright - it is by default. Thus, all web pages are by default copyright by their author.
However, my impression is that really trivial things (such as a brief summary of a language) cannot be copyrighted. So the article itself should be okay. The examples look a little more in-depth, were they lifted as well?
-Fuzzrock
Actually, I wrote the examples, short of the hello world one. As we type this, I am in the process of transmogrifying the page into something that less resembles the page it came from. Even if it's okay to lift, I don't feel comfortable just copying someone's work nearly outright.
-AlanD
IANAL, but my understanding is that one cannot copyright information, only creative expression. I do not believe that
the bare language definition and C transliteration rules would meet this test, although I suppose the "Hello World" program just might. On the other hand, I am happy to explicitly credit the source and I've now done so. -HWR
Linefeeds and EOFs
Besides adding a couple new examples, I've rewritten the previous ones. Two, like my revised versions, assumed EOF translated as 0, but they nonetheless echoed the 0 to output before quitting. A third was needlessly complex.
In redoing the third, I stated that 10 (line feed) was the ASCII for return. This is the case on Unix machines, and brainfuck is far more common on them than on Macs, which use 13 (carriage return) for return. (Looking at brainfuck and at the Mac ethos, it seems very natural that it's not a common combination.) -Daniel.
- As a minor observation, while MacOS 9 and below use 13, Mac OS X uses 10 because it is a unix based operating system. — Darco 03:27, 20 Nov 2004 (UTC)
Of course, 13 is the return Key on win/MSDOS machines, for which most BF interpreters/compilers are available. ... By the way, thanks for making the examples contain more crap than they needed to get the point across succinctly.
Hmm...
A. Windows and DOS machines represent a return with a carriage return (13) FOLLOWED BY a linefeed (10). Which is ugly. I grant it does warrant a mention on the page, and I'll add one.
(Actually, it's worse than that; in Windows, the representation is different in different programming environments, e.g. assembler vs. C, and may even be different on input than on output.)
B. I don't know about "most interpreters/compilers", not having done a survey. I do know that most brainfuck programs and most brainfuck programmers assume a return is 10. I did a fairly thorough check of existing brainfuck programs, both at the archive site and elsewhere, and none use a 13 as a return. Three do use 13 followed by 10: Ben Olmstead's "99 bottles" program, and Roland Illig's "Towers of Hanoi" and "Hello World". And one, Jim Fowler's "Pi" program, uses a 10 followed by a 13, which was probably an error. In any case, the 10s have an easy majority, which includes Urban Müller's programs, incidentally.
C. The examples I altered, I simplified and tidied if anything. I grant I could have been briefer in some of the description, and I'll try to improve that now. If what bothers you is my adding two new examples, my defense is that the previous ones contained no arithmetic and no nested loops, and I thought both should be demonstrated.
-Daniel.
Doing away with '>'
For what it's worth, I just noticed that one could do away with the > command, if one redefines + as "increment location at pointer, then increment pointer". AxelBoldt, Tuesday, May 21, 2002
- Mathematicians ;-) --FvdP
- Sheffer would've been proud :) Alex Pankratov 02:31, 25 October 2007 (UTC)
Hm, sure. Then to get > one would do -+ and to get a + one would do ><?
- You mean -+< probably. Wouldn't this result to bigger code anyway? (Aggelos I. Orfanakos | Talk | Contributions) 10:14, Mar 14, 2005 (UTC)
- Actually I meant +<. Don't know what I was thinking. And yes, it would make programs longer, besides wrecking the symmetry of the language. -Daniel.
- Bigger code would be a problem, because Brainfuck is famously concise. —Preceding unsigned comment added by 81.151.14.62 (talk) 02:13, 25 October 2007 (UTC)
You can also get rid of the - command. Just + 127 times. --Exomnium
Confusion over '[' and ']'
I just replaced the hello world on both this page and the hello world page with Müller's own version, which is more concise. Also I rewrote the textual descriptions of brainfuck semantics. There are at least six equivalent combinations of semantics for [ and ] but the one I used is the most direct, symmetrical, and time-efficient. -Daniel.
I don't understand this. If all the bytes are initialised to zero, where is the program stored? Also, the correspondence between:
- ] jump back to the statement after the corresponding [ if the byte at the pointer is nonzero.
and C } doesn't seem right. In C there isn't a test at the end of the while loop, only the beginning.
- The program is stored outside of the data area, it cannot be modified. As for the difference between the two definitions, if you think about it, it's just apparent. The two definitions behave the same (this should be noted in the article, I guess). --FvdP
- Thanks, although as it is now, it looks like it's defining an infinite loop. This language is potentially confusing :-)
- [ jump forward to the statement after the corresponding ] if the byte at the pointer is zero.
- ] jump back to the statement after the corresponding [.
- Okay. Let me try to clarify this.
- The two meanings for ] in question are those found on the pages of Brian Raiter and Frans Faase respectively, both of which can be found in the links section.
- In C, as written, the test condition is stated at the top of the loop; in brainfuck, as written, the test condition is not stated at all, since it's always the same.
- In C as compiled by an optimizing compiler, the test will be made at both the top and the bottom; it would be inefficient to use a jump instruction to jump to another jump instruction; it's faster to jump directly to the target of that second jump instruction. In any brainfuck compiler or interpreter concerned with time-efficiency, testing at top and bottom is also the right move.
- In describing brainfuck as a theoretical construct, both semantics for ] produce equivalent results (as do another four versions I can think of offhand): namely, that the the loop is exited if the cell holds a zero, and executed another time if it holds a nonzero value.
- Raiter's version uses two jumps to accomplish this effect; Faase's uses one, and is therefore more time-efficient. Raiter's, however, uses shorter code, and is therefore better suited for tiny compilers, which are an important part of brainfuck culture. However, Faase's version preserves the symmetry of the language, which is one of its most distinctive and appealing features. So I think Faase's is the better description for general expository purposes. Anyone who plans to make a tiny compiler will find the required tricks without our help; it's meant to be a challenge anyway.
- Now, as for the "infinite loop" issue: The version you quote does indeed produce an infinite loop. It is a bastard version, a combination of aspects of Raiter's and Faase's semantics, that flatly does not work; it was produced by an incautious editor of this page. The progression of semantics on this page has gone: Raiter, Faase, bastard, Raiter. Now I am going to put it back to Faase, with Raiter's mentioned in a note, and hope people will consider the above discussion enough justification to leave it that way.
- -Daniel Cristofani.
- Not having fully thought this through, nor checked the references (Muller, Faase, Raiter), I decline to edit this myself. Seeing what I perceive to be an error, I mention it here in the likely case my attention wanders. In the definition of the ']' keyword, it says the pointer will jump if "the byte at the pointer is non-zero". Byte at what pointer? I mean, the only pointer talked about at any other time is presumably still at the ']' character. Should the program "+[>]" really terminate (after 4 or so instructions)? Anyway, even if the listed semantics are correct, I disagree with "Both versions produce equivalent behavior from every Brainfuck program", since the program "+[>]" is a valid brainfuck program.--jholman 12:14, 20 Jan 2005 (UTC)
- No, the "pointer" referred to is not to do with the instructions, but the internal data - the one-dimensional array of bytes which is the "machine" represented inside brainfuck. The '[' and ']' operators control the order in which an unmodifiable sequence of instructions are executed, based on modifiable data (just like
if,while, etc, in more conventional languages); the "pointer" at any time is pointing at one byte in the data array, and is "moved" back and forth by the '<' and '>' operators. So , assuming the pointer starts at element 0, and the array is full of 0s, "+[>]" means either:- increment data byte at pointer (so, data[0]=1); jump to after matching ']' if data at pointer is 0, which it isn't; move pointer (to data[1]); jump to after matching '[' if data at pointer is non-zero - data[1] is checked, found to be 0, and we reach the end of the program.
- or, if ']' is just "jump back to matching '['", there is an extra step where we jump back to '[', test the current data byte, and find that it's 0 (the pointer being at data[1] remember); so we jump to after the ']', and have reached the end of the program. As Daniel says, this is equivalent but slightly less efficient.
- or, if we use the third interpretation, we will get: increment data byte at pointer; jump to matching ']'; jump to after matching '[' if current data byte is non-zero - the pointer's at data[0], which we just incremented, so we jump back; this brings us to the '>', which moves the pointer as before; now, reaching the ']' again, the pointer is at data[1], which is 0, so we don't jump. End of program.
- I don't know how well I've explained those, but hopefully if you think them through you'll see that the end result of all three is identical - namely, that data[0]=1, data[1]=0, and the pointer is pointing to data[1]. - IMSoP 15:45, 20 Jan 2005 (UTC)
- No, the "pointer" referred to is not to do with the instructions, but the internal data - the one-dimensional array of bytes which is the "machine" represented inside brainfuck. The '[' and ']' operators control the order in which an unmodifiable sequence of instructions are executed, based on modifiable data (just like
Tweaks, comments, and capitalisation
Just made a few tweaks. To explain:
-Decapitalized "brainfuck" in the middle of sentences, since that's Müller's original usage. Actually he put it in single quotes as well, like "the 'brainfuck' language", but I think that'd be overdoing it.
-Fixed "Hello World!" a couple places to have capital W and no comma, like the program.
-Moved the old comment about it up to the right place, and removed the part about its length--I don't think 111 characters is long at all. The comment was originally made before I put Müller's concise version in place of a less concise version.
-In the "Pointer Manipulation" example we'd better leave a 0 at the start of the sequence of letters if we want to be able to find the start again.
-Changed the comment on return; the behavior of implementations is not neatly split along platform lines, since some implementations for DOS/Windows translate return to 10 for compatibility with most brainfuck programs--or have an option to do so--and that's probably the best move anyway, in the name of consistency. I think a full explanation here would be too much, but I'll be interested to see what other people think.
-Two things I'll leave for other people to think about: one, whether all these examples (I added the last two to what was then a separate page) are now too much for the main page, and some of them should be trimmed; and two, whether brainfuck has enough in common with INTERCAL to warrant a "See also". Maybe do a "see also" linking to the wikipedia page on "esoteric programming language" instead?
-Daniel Cristofani.
Okay, now I have to decapitalize "brainfuck" again--see above. The original docs should take precedence. In fact, capitalizing it even broke the link to the original implementation on Aminet.
-Daniel Cristofani.
- Sorry about that. I take full responsibility. :-p -- Timwi 21:29 21 Jun 2003 (UTC)
- :) -Daniel.
Conversion to C
Hrmm, I converted the Hello World! program to C as per the instructions, but had to make ptr an int rather than a char to make it work (else I just got garbage characters). Also, I got a triangle instead of a space, and no exclamation mark. Am I doing something wrong? The code I got to work partially is:
#include <stdio.h>
int main (void) {
int * ptr;
*ptr = 0;
++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; while (*ptr) {++ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++ptr; ++*ptr; ++*ptr; ++*ptr; ++ptr; ++*ptr; --ptr; --ptr; --ptr; --ptr; --*ptr; } ++ptr; ++*ptr; ++*ptr; putchar(*ptr); ++ptr; ++*ptr; putchar(*ptr); ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; putchar(*ptr); putchar(*ptr); ++*ptr; ++*ptr; ++*ptr; putchar(*ptr); ++ptr; ++*ptr; ++*ptr; putchar(*ptr); --ptr; --ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; ++*ptr; putchar(*ptr); ++ptr; putchar(*ptr); ++*ptr; ++*ptr; ++*ptr; putchar(*ptr); --*ptr; --*ptr; --*ptr; --*ptr; --*ptr; --*ptr; putchar(*ptr); --*ptr; --*ptr; --*ptr; --*ptr; --*ptr; --*ptr; --*ptr; --*ptr; putchar(*ptr); ++ptr; ++*ptr; putchar(*ptr); ++ptr; putchar(*ptr);
}
Evercat 21:33 28 Jul 2003 (UTC)
- The problem is that in C you have to define the array before you can use it. The original size for the brainfuck array is 30,000 bytes. So replace the initial code with this:
- #include <stdio.h>
- char array[30000], *ptr=array;
- int main (void) {
- ++*ptr; ++*ptr; etc. etc.
- Defining the array outside main means it's initialized to be full of zeroes automatically, so you don't have to zero them all yourself.
- -Daniel Cristofani.
"No change to cell"
",[.[-],]" is a correct copy-(text)-input-to-output program for an implementation that does no-change-on-EOF; the cell always holds 0 before a comma is executed, so on EOF it will remain zero and the loop will be skipped or exited. Granted, it will also do this if a zero is input, so it's worth adding the word "text" for clarification. If we want to distinguish EOF from every byte value on a no-change implementation, we just have to set the cell to some value distinct from every byte value before each comma. Whether this is even possible depends on the implementation; for some it can be done like "-,+[-.[-]-,+]".
-Daniel Cristofani.
- The description of this as "no change to cell" is rather confusing - I couldn't work out what was meant until I put it through an interpreter. I'm not sure what a better description is though, so I'll leave it as a challenge for somebody else [what a BFed language, even commentaries are awkward!] - IMSoP 19:26, 27 Jan 2004 (UTC)
- I tried to improve it a while ago. I think it's okay now.
- -Daniel Cristofani.
- Ah, yes, so it is. Thanks, and sorry I didn't acknowledge the change earlier. - IMSoP 21:44, 22 Apr 2004 (UTC)
- No problem whatsoever. -Daniel.
Turing completeness
The brainfuck language is Turing-complete either with an unlimited number of cells with range at least 0-23, OR with at least five cells with unlimited range. In the latter case, a Turing machine can be simulated using two cells to store the left and right halves of the Turing machine tape. I'll put a detailed explanation on my web page when I get around to it.
-Daniel Cristofani.
- The language is specified such that every cell contains an 8 bit value. So speculating about cells that have an infinite range of values is talking about a change that would have to made from the standard specification of the language, just like the change to have a finite tape.
- If I'm not mistaken, the language specification allows an infinite tape.
- So, the wording of the last paragraph is confusing. You could remove the - or + operation (but not both) right now, and leave the language turing complete. Or, you could define it as having a circular tape, but change the cell specification to allow an infinite range of values with no wrapping, and also have it be turing complete.
- -Eric Hopper
- The closest thing to a language specification is the original README file, which specifies a 30,000-cell array; so an infinite array is a change too. Now that I think about it, that means that the version I reverted it to was doubly wrong--either modification alone would make the language non-Turing-complete, unless other modifications were done too, and indeed the language as originally defined is non-Turing-complete. Now I've just tried to fix it--hope it's clear now.
- -Daniel.
- Yes, it is now clear. :-) Thanks.
- -Eric Hopper
- The 0-23 restriction is a bit wide. The language is Turing complete even with an infinite array of cells that range from 0-1, for any 0-255 based Brainfuck program can be translated to the Boolfuck language, as shown here.
- Agreed--0-23 is a loose upper bound on the required range, and in fact 0-1 is sufficient. As a matter of detail, note that the proof for 0-23 doesn't assume wraparound, and Boolfuck does...but proving Turing-completeness for a 1-bit version of brainfuck that doesn't assume wraparound is trivial. Here's a mapping from normal (but non-wrapping) brainfuck to 1-bit brainfuck that should work.
Start the program with a >
+ maps to [>]+[<]>
- maps to [>]<-<[<]>
[ maps to [
] maps to ]
> maps to >>>... (*256)
< maps to <<<... (*256)
, maps to [>]<[-<]>,[>,]<[<]>
. maps to [.>]<[<].>
DanielCristofani 05:44, 20 Apr 2005 (UTC)
Dialects
Some mention of the different dialects of 'brainfuck' should probably be covered, specificly:
- Original brainfuck (8 bit)
- 16-bit, and 32-bit dialects
- Large number dialects
- EOF support (ie: reading a -1 from the input stream) (Not supported in original brainfuck)
- Symmetric data-space (ie: the ability to move the pointer behind its initial position, or negative indices)
- Okay, done.
- DanielCristofani 10:35, 30 Apr 2005 (UTC)
BF HTTP Server
It's painfully simple at the moment, but I'm working on a httpd server written in brainfuck. — Darco 04:13, 2 Feb 2005 (UTC)
- I'd love to see the source for this, if possible. It sounds crazy. -Dom
- Heh, well, it's not nearly as scary as it might seem. Serving up one page is quite simple, as long as you have a grasp for the protocol. All of the network stuff is handled by xinetd, which hands off control to my BF HTTP server after a client connects to port 85. The BF app then records all of the data it receives until it receives two line feed characters in a row. It then prints out some stuff to describe the mime type and then it outputs the page itself. After it does all of this, it goes back and prints out all the data that the browser told it (mostly just to satisfy my curiosity as to what all the browser was telling my BF program). Getting it to serve up multiple pages is a bit more difficult, but certainly doable. — Darco 01:53, 6 Feb 2005 (UTC)
Doublefuck
(I moved this from my talk page because it seemed like something that should be here instead — Darco 04:13, 2 Feb 2005 (UTC))
Are you certain the origin of the name isn't worth mentioning? I'd say calling it "nothing of value" is a bit hasty. CXI 13:59, 24 Jan 2005 (UTC)
- Origins are different than pointing out lude puns. Doublefuck is a clever name given what makes the language unique and what it was derived from, and I think most people will realize this without having to have it spelled out for them. — Darco 04:13, 2 Feb 2005 (UTC)
Notes on 3/05 revision.
I'm going back to lowercase except at the starts of sentences and in headings, to be closer to Müller's usage.
"statements" strongly connotes something with more internal structure than these have. I think "commands" is more like it; "instructions" would be fine too.
I'm trying to be a little more concise while keeping all important content and also smoothing out a few small inaccuracies. I want to maybe move the article a little closer to "featured article" level.
-Daniel.
About the C++ translations:
Using cin >> *ptr is flat-out wrong; it won't read in whitespace.
Beyond that, I think newline translation is important for portability.
Translating EOF as "no change to cell" is somewhat more controversial, but given that it can easily coexist with either of the other popular EOF behaviors in any brainfuck program (i.e. that a program that expects EOF=0 or a program that expects EOF=-1 can trivially be made to accept EOF -> "no change" as well, by setting the cell just before a ',' command) it seems like the best chance for a unified practice. Also, it's the behavior of two of Müller's three implementations.
I'm changing it back to C like it was before someone randomly changed it... - 郵便箱 03:43, Mar 31, 2005 (UTC)
That's sensible. I wondered why it got changed to C++. I still think it's important to translate newlines, naturally. DanielCristofani 10:43, 4 Apr 2005 (UTC)
I removed that "Commentary" because the important part--i.e., brainfuck would be Turing-complete if given unlimited memory--was added near the start of the article. Also, two of the "See Also"s were actually brainfuck descendents and the other was not particularly similar to brainfuck.
With as many links as this I thought they needed sub-categorizing. I labeled one implementation as "broken" and moved it to the bottom; I've emailed its author a list of bugs: -translates [ and ] like a "do while" -tries to check > and < for syntax, e.g. it thinks +>+<[>]<< will move the pointer left of its original position and calls it a syntax error; -false and insulting statements about all other compilers, in the readme -no linefeed translation.
DanielCristofani 03:23, 6 Apr 2005 (UTC)
- The author has now fixed these problems, and has correctly relabeled his compiler as "compatible".
Question.
Maybe instead of a long string of trivial examples it would be better to have "Hello World" and then one medium-sized example program, examined in detail? Some desiderata for this would be:
-input -nested loops -non-arbitrary task -use of nondestructive flow control -medium complexity/subtlety level
I think a rot13 program might be suitable and I've written one on what seems to me to be about the right level. But I'd like to know what other people think about this idea first.
>-,+[ ->++++++++[>++++++++<-]>[<<[-<+>>]>[<]>-]>++[ <+<<[<+++++++++++++>>]>[<] >++++++++++++[<<[-<+>>]>[<]>-] +<<[>++[<<------------->>-]]>[<] >++++++++++++[<<[-<+>>]>[<]>-] +<<[<+++++++++++++>>]>[<] >+++++[<<[-<+>>]>[<]>-] >- ]<<<[<+>-]<.[-]>-,+ ]
DanielCristofani 02:21, 6 Apr 2005 (UTC)
Actually, maybe one like this instead. It demonstrates a greater range of techniques.
>>>>>-,+[ -[ -<++++[<++++++++>-] >[-<+<-[<<<]>[[<+>-]<<+<]>>>>] <<[-]<[<+>-[<+>>+<-[<+>-[>-<[<+>-]]]]]>[ ->>>+++++++++++++<<[->+>-[>>>]<[[>+<-]>>+>]<<<<] >>[-]+>[<->-[<++>-]]<[<+++++++++++++>-]<[<+>-]<< ]<<[>>++++<<-]>>[>++++++++<-]>+> ]<.[-]>-,+ ]
130.94.161.238 06:07, 8 Apr 2005 (UTC)
Notes on 4/05 changes.
The new notes about the semantics were incorrect.
-It is not correct merely to replace a conditional jump with an unconditional jump; it is also necessary to change the jump's destination. I don't think adding that to the new phrasing would result in a better sentence than the one that's there now. Of course other people may disagree.
-The C translation does NOT specify that the test is performed at the top of the loop and not the bottom! C is not like assembly language in specifying which statements are to be placed where in the final executable. A standards-compliant C compiler can translate "while (*ptr){}" into an executable with the test at the top, at the bottom, both, or somewhere else entirely. Moreover, "while" is not an imperative verb, so even reading the English connotations doesn't suggest putting the test at the top, the way it would if the translation were
label1: if (!*ptr) goto label2;
goto label1;
label2:
DanielCristofani 06:46, 12 Apr 2005 (UTC)
- Who says the final executable has the test at the top? I was just saying of the 2 tests for the value only one is used in the C translation. -- Paddu 14:36, 13 Apr 2005 (UTC)
- What you said was "(Note that testing the pointer at the byte has been omitted for the
]command.)". This sounded to me like it meant the C translation of[performs a test and the C translation of]doesn't perform a test; but unlike the brainfuck commands,while(*ptr){and}cannot accurately be described as performing actions individually; the fact that the test condition is described in the former does not mean a test is performed at thewhileand not at the}. Notice further that}is not any kind of command but merely a statement-grouper, and can be omitted when the "while" governs only one statement. So it certainly does not represent any kind of jump, conditional or unconditional; whereas the "while" represents all jumps that the loop involves...
- What you said was "(Note that testing the pointer at the byte has been omitted for the
- In mentioning executables, I think I was trying to say in an indirect way that it is only when C is translated to executable form that C semantics are reduced to individual actions taken at different places in the program. At the level of C source code, it does not always make sense to talk about where in the source code things are done, and in particular it does not make sense to talk about whether the test of a loop is performed at the top or the bottom, or even to say that it is performed in only one place, or that "only one test is used" as you just phrased it.
- The final executable need not even have a loop as e.g. that could have been (fully) unrolled. So does that mean a while statement shouldn't be called a loop unless you're sure it is complex enough to have a loop in the final executable? Well, the final executable doesn't even have a "while statement"... :) -- Paddu 14:39, 13 Apr 2005 (UTC)
- I see "loop" as a source-level concept, unlike the ones I was complaining about. DanielCristofani 11:30, 14 Apr 2005 (UTC)
About "more complex and no more correct", I would like to see what other people think. Without the changes I made to the C translations, not only Urban Müller's original example programs but many other valuable programs will not run correctly on some popular platforms. On the other hand, those C translations certainly were more complex--though not nearly complex enough that the whole set wouldn't fit in the palm of your hand. Maybe we just want to explain elsewhere in the article that the C translations are not definitive?
Notes on 5/05 changes.
The paragraph beginning "A brainfuck program consists of" may seem like it's stating the obvious, but I wanted to briefly nail down that:
-This is an imperative language, not (say) a functional one
-There are no declarations or program headers or variable names or any such apparatus, just a bare sequence of commands
-There is no gathering code from several files together to make a program
Now, about the examples. I've worked on this more and am now thinking to use this rot13 program. It's originally by Bertram Felgenhauer, with a few subsequent improvements by me. He's given permission.
-,+[
-[
->+>++++[>++++++++<-]
<<[>+>+>-[>>>]<[[>+<-]>>+>]<<<<<-]
]>>>[-]+>--[-[<->+++[-]]]<[
++++++++++++<[>-[>+>>]>[+[<+>-]>+>>]<<<<<-]
>>[<+>-]>[-[-<<[-]>>]<<[<<->>-]>>]<<[<<+>>-]
]<[-]<.[-]<-,+
]
As soon as I get it fully commented, I will put it in place of all the examples except "hello world".
About my big rewrite of 5/5/05.
- changed opening paragraph to be more of a summary.
- rearranged start of "Language design".
- added a few notes to substantiate some statements.
- removed note about Müller "inspired by False"; I think that may be taking Wouter's mention on his False page as meaning more than it necessarily does, and even if fully true it looks like a digression. If someone wants to re-add it, maybe just a phrase like "Inspired by False, Urban Müller created brainfuck around 1993 etc."
- rephrased semantics of some commands, to make them maybe clearer to the general public
- made part about alternate [] semantics more concise but hopefully still accurate and readable.
- Moved and elaborated "difficult to understand, but Turing-complete". I think it's more suitable there. The danger is that it will look like part of "Commands", but I don't think it really does, and I think giving it its own subheading like "Scope" or "Limitations" or the like might perhaps be a bit too much.
- fixed a couple external links, and the Icelandic version link.
Incidentally, the article on "state" is unclear-to-wrong, and "initialization" now links to "booting", which is misleading. I'll fix both soon probably, if nobody else does.
DanielCristofani 09:30, 5 May 2005 (UTC)
Brainfuck's "formal parent" -- P′′
Brainfuck appears to be a minor variation of the formal programming language P′′, introduced by Corrado Böhm in 1964 to describe a class of Turing machines, and proved by him to be capable of computing any partial recursive function. (Thus providing a formal proof of brainfuck's Turing completeness.) Böhm's language P′′ has only four instructions -- the equivalents of '+<', '>', '[', ']', and no i/o instructions (since he was describing single-tape TMs).
--r.e.s. 11:40, 10 July 2005 (UTC)
subroutines
I always wonder, in Turing tarpits like this, is there an easy way to call/include a subroutine? This would help in writing large programs. Samohyl Jan 00:15, 19 August 2005 (UTC)
- No subroutines. Not in brainfuck. You're stuck with a bunch of "while" loops. In brainfork however, you *could* fork a thread and constantly check a cell for non-zero, then set it to 1 to run the "subroutine"... I think. :P - BodyTag 15:41, 19 August 2005 (UTC) EDIT:
- Something like
>>Y[-<+<]>[-[>subroutine code here<[-]]+]code< move to the subroutine trigger+[] call it and wait for it to end> move back to wherever you wantcode- It ended up messier than I would have thought. It *should* work. XD -BodyTag 11:41, 20 August 2005 (UTC)
- pbrain is a brainfuck extension with procedures. But if you want to write really large programs you will probably want some kind of macro language built on top of brainfuck. There have been several including a version of BASIC.
- The SNUSP programming language is also like having brainfuck with procedures. The 2-D code space makes the procedures look like boxed annotations. --IanOsgood 21:05, 11 July 2006 (UTC)
Portability and cell size.
Every reasonable brainfuck implementation uses at least byte cells. Thus, decrementing a -128 has the same effect regardless of cell size, i.e. it produces a nonzero value which, if output, will come out as a byte with bits 01111111, and which will need to be incremented 129 times to produce a zero. Similarly, incrementing a 127 will produce a nonzero value which if output will come out as a byte with bits 10000000, and which will need to be decremented 128 times to produce a zero.
Decrementing a -255, on the other hand, will produce a zero on implementations with byte cells, and a nonzero number on implementations with larger cells.
If I'm wrong it should be easy to show it: just produce a brainfuck program which does not increment a 255 or decrement a -255, and yet behaves differently depending on the cell size of the interpreter.
- The same challenge applies to a claim that decrementing a 0 will produce different effects with different cell sizes. Certainly it is possible to find interpreters that will react badly to decrementing a zero. Rarely, this is because they are built in some language where integers do not exist and need to be synthesized, and where wraparound integers are hard to synthesize. Much more commonly it is because someone is trying to enforce absolute portability, i.e. to make sure programs will run on one of the rare interpreters mentioned just above. None of this adds up to an interpreter that treats decrementing a zero differently based on cell size, though. DanielCristofani 03:04, 6 November 2005 (UTC)
- Since my careful statement has been replaced with one that is wrong for the third time now, I suppose I should expand it to make it more obvious why it is correct. I will have to think about how to rephrase it in the article. And I will leave further explanation here:
- IF YOU WRITE A BRAINFUCK PROGRAM THAT DECREMENTS A CELL DOWN TO -255, and run it on any brainfuck interpreter written straightforwardly in a commonly-used programming language, IT WILL NOT COMPLAIN, NOR WILL IT BEHAVE DIFFERENTLY BASED ON WHETHER THE CELLS ARE BYTES OR LONGWORDS, unless the writer of the interpreter deliberately and explicitly programmed it to complain in that case. The same is true of compiling brainfuck to any commonly-used programming language.
- I think what confuses people is that they are thinking something like "If you can safely and portably decrement a byte to -255 AND increment it to +255, doesn't that mean you can hold 511 different values in a byte, which is clearly impossible?" No, it doesn't mean that; in order to avoid incrementing a 255 or decrementing a -255, the program (or the programmer) must keep track of which values a cell may have, and the set of possible values of a given cell at a given time cannot include more than 256 values. HOWEVER, with fancy programming, these values can be (say) -100 to 155, or they could be even numbers from 0 up to 254 and odd numbers from -1 down to -255. And this is independent of whether the interpreter thinks of the cells as being signed or unsigned (again, unless the interpreter writer has deliberately programmed the interpreter to, say, give an error message when a 0 is decremented).
- Once again, anyone who disagrees should show me a brainfuck program that does not decrement a -255 or increment a 255, combined with a compiler or interpreter on which that program displays different behavior depending on the size of the cells. DanielCristofani 04:02, 28 November 2005 (UTC)
- The compiler I've written in PHP and other PHP compilers, and because PHP is fairly flexible, makes it possible to increment up and well over 255 and down and less than -255 and give me the exact behavior expected. 72.137.43.90 00:11, 22 June 2006 (UTC)
- That's good, but a lot of compilers can do that, and it's not what I asked about... DanielCristofani 02:18, 22 June 2006 (UTC)
At the moment it won't successfully run even fairly simple programs such as:
+++[>+++++<-]>[>+>+++>+>++>+++++>++<[++<]>---]>->-.[>++>+<<--]>--.--.+.> >>++.<<.<------.+.+++++.>>-.<++++.<--.>>>.<<---.<.-->-.>+.[+++++.---<]>> [.--->]<<.<+.++.++>+++[.<][http://www.hevanet.com/cristofd/brainfuck/]<.
Hopefully it can be fixed soon and then put back up. DanielCristofani 08:45, 22 October 2005 (UTC)
The link for "A Brainfuck Computer With a Brainfuck CPU" in Hardware section seems to be broken at the moment.
Alex / Oct 26, 2005
Clarification about speed.
For the most part, brainfuck interpreters and compilers execute one command at a time, or maybe one string of consecutive identical commands at a time. For a test case, let's compute the Fibonacci number F(32) or 2,178,309. I would do it with a program like
++++[>++++++++<-]>>+>+<<[ >>[ [-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<- [>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>> ]<<<[<<<]>- ]>>[>>>]<<<[+++++[>++++++++<-]>.<<<<]++++++++++.
which executes 15,792 commands to output the right answer. This program puts one digit of the numbers in each cell, and thus takes time proportional to the square of the logarithm of the number we are looking for. It only needs byte cells; in fact I think it would work with 6-bit cells.
Any program that computes F(32) by putting F(32) in a single cell, on the other hand, will take at least F(32) commands to pump the cell up to F(32), and another 2*F(32) commands to decrement it down to zero and check it against zero after every decrement (necessary to see what its value is in order to output it). So at least 6,534,927 command-executions, or more than 400 times as slow as the program above. In fact it will probably be at least a thousand times as slow; you might try to see how fast you can do it.
In short, a program only needs big cells if it is going to put big values in them; and producing, moving, and using big cell-values is a very slow process in brainfuck. Yes, some compilers can optimize out simple inner loops, but any mathematical operation more complicated than addition or subtraction is still probably going to take an amount of time that is at least proportional to the size of the cell values involved, and outputting values may also.
DanielCristofani 11:35, 23 November 2005 (UTC)
- You can do it the O(exp(n)) way regardless of what the cell size is, and you can do it efficiently by ignoring the extra cell size. So full range utilization is the result of choosing a poor algorithm, not the other way around. Saying that big cells make programs slower would therefore be incorrect, though that is merely how I misread it. Fredrik | tc 14:31, 23 November 2005 (UTC)
- "Full range utilization is the result of choosing a poor algorithm"--yes; and since producing and using large cell values is slow enough to cripple even an otherwise good algorithm, we can also say "full range use makes an algorithm poor (for brainfuck)" or "full range use makes a program slow". I think we're on the same page though: the actions needed to USE the high-order bits make a program slow, not their mere presence. I hope the article is clear now.
- About "FALSE"'s influence, that story seems to come from here. Although Wouter seems impressed by the size of Urban Müller's compiler, he doesn't say that it was the size of the FALSE compiler that impressed Müller, although that's a reasonable guess. Given that Befunge is also listed as inspired by FALSE, Wouter may not be claiming anything more than (say) that FALSE made some people aware that anyone can make a language at any time without regard for practical utility. Even then, he could be guessing based on the fact that his language was released before these others. Dunno. DanielCristofani 12:10, 24 November 2005 (UTC)