Talk:Befunge

From Esolang
Revision as of 04:07, 18 January 2014 by Oerjan (talk | contribs) (SIGN BEFORE ZOD)
Jump to navigation Jump to search

I see Befunge is categorized as Cell-based. Shouldn't it be stack-based? I realize that you can use self-modification to emulate cell-based data storage, but I don't think that should count. In fact, we should probably have a category for languages capable of self-modification. --Rune 21:33, 5 Jun 2005 (GMT)

A lot of the categories on the wiki (at the time of this writing) are a bit overdone IMO. I agree that having a "self-modifying" category would be a lot more useful than "cell-based" (which is pretty subjective) or "zero-dimensional" (which is pretty rare.) --Chris Pressey 22:48, 5 Jun 2005 (GMT)
Sorry for that, I'm not really a Befunge programmer. I'm trying to put categories to some languages but seems that I've been mistaken this time. pgimeno 23:03, 5 Jun 2005 (GMT)

Other Funges

What should we do about Befunge-98 and other Funges? Should we have a separate article, or put it in a sub section here? Both options has merits in my opinion. --Rune 22:03, 14 Jun 2005 (GMT)

At this point I think it should probably be a seperate article... when I get around to it.  :) --Chris Pressey 21:32, 5 Jul 2005 (GMT)

Computational class

It's probably worth noting that a trivial extension of Befunge-93 in which it can hold arbitrary integers on the stack is likely to be TC, thanks to the swap instruction which makes it possible to implement a Minsky machine. All that would be pending to check is if 80x25 is enough for the finite-state automaton needed. My guess is that the answer is yes. --pgimeno 08:32, 21 Jun 2005 (GMT)

That's very insightful, and an interesting question, on a couple of counts:
  1. Minsky machines are quite primitive (think OISC), but Befunge instructions are more powerful, and each one can (probably) represent many Minsky machine instructions.
  2. The stack might also be used as a form of virtual memory (think of "swapping out" the playfield to the stack - you could probably roughly double the 80x25 capacity.)
  3. This seems to amount to writing a "universal Minsky machine", and I'm not sure if anyone has considered that concept (to the degree that it's been analyzed for Turing machines. I'm planning to get Minsky's book from the library tomorrow, though, and I'll see if he has anything to say about the idea.)
  4. It still has to be able to run programs of arbitrary size - and where would you store them? On the stack? If so, would you be able to access the instructions in the needed order? --Chris Pressey 00:13, 24 Jun 2005 (GMT)
(My reply starts here)
About point 4, the assumption is that the stack is preloaded with a number representing the program to run, just as an UTM can emulate a TM when the tape is preloaded with the TM to emulate.
About point 2, I don't think that that could possibly help; anyway the power of Befunge will probably be enough for 80×25 to suffice. The multiply, divide and modulo operators can greatly simplify some of the operations needed. --pgimeno 19:28, 25 Jun 2005 (GMT)
Re point 4: But wouldn't that require three stack entries (program, register #1 and register #2)? Whereas Befunge only lets you randomly access (i.e. swap) the top two?
FWIW I'm pretty sure pre-loading isn't necessary; you could write a very small routine which reads the program (in say binary form) from the input, and creates the stack cell, before starting. --Chris Pressey 16:59, 26 Jun 2005 (GMT)
According to the Wikipedia "Counter" article (see Step 3 at the bottom) one of the counters is used as a temporary storage and the other one holds in one single integer the 4 counters that implement the TM tape (though actually I think that 3 counters should suffice since only one scratchpad at a time is needed). The Befunge program should take the role of the FSM that performs the coding/decoding of the counter as tape contents and interprets the tape contents as a TM.
Unfortunately the numbers of the form 2x×3y×5z grow too quickly for a practical implementation to be feasible, even using bignum libraries.
I think, however, that the availability of modulus, division and multiplication operations makes the scratchpad counter unnecessary; if so, each counter can be used as one of the stacks that are needed to simulate the tape, eliminating the need of using exponential coding (only steps 1 and 2 of the Counter article would be needed, replacing the need of two counters in step 2 by the modulus, division and multiplication operations).
About preloading, you're right - I didn't think of using the input stream as a means of feeding the program in.
--pgimeno 18:31, 26 Jun 2005 (GMT)
As a clarification: the program is actually part of the initial tape contents. That's how an UTM encodes the program.
--pgimeno 13:34, 27 Jun 2005 (GMT)
OK. In 14.2 of Computation, Minsky gives a (sketchy) proof that you only need one register if you have multiplication and conditional division (divide by some constant if the number is divisible by that constant, otherwise branch - which is easily done in Befunge with dup, modulo and test.) This seems to agree with what you're saying (insofar as I follow you. and regardless of practical concerns.)
I think the only serious issue remaining is whether the "universal driver" FSA can be coded in 80x25 Befunge instructions. I'm still undecided. They're powerful instructions, but, there's a reason Minsky's proof is sketchy - it's all like "we know A is equivalent to B, and that B is equivalent to C, which is equivalent to a TM" - he doesn't actually build a one-register universal machine. I imagine it could get quite large... only one way to find out, though. --Chris Pressey 20:51, 27 Jun 2005 (GMT)
I think I have done just that (proven that a Befunge-93 interpreter which can hold arbitrary integers in the stack is TC). I didn't implement a Minsky machine, but rather an interpreter of classic dbfi style brainfuck. First I modified mtve's befunge interpreters in perl and c to handle arbitrary bignums in the stack (new sources here and here). My brainfuck interpreter in befunge is here. It stores the code as one bignum and the brainfuck tape as another bignum. It also uses some self-modification, and stores a temporary integer in the codespace; however, it does not write bignums to the codespace. Hence, the implementations of "[" and "]" have to jump through some hoops to allow arbitrarily deep nestings. A much faster brainfuck interpreter in befunge could be written if one kept track of the nesting count by storing the number in a codespace location, but my intention was to prove TC for this dialect(?) of befunge, so I had to allow arbitrarily deep nestings. The perl code was just for debugging the befunge code (plus, it's super easy to add bignums to perl), so use the c code to try this out.
> gcc -O3 -o bigbef_me bigbef_me.c -lgmp
  • Try some brainfuck code that prints out a single "$":
> echo -n '++++++[>++++++<-]>.!' | ./bigbef_me brainfuck.bf
> echo -n '!' | cat 99bottles.b - | ./bigbef_me brainfuck.bf
> echo -n '!++++++[>++++++<-]>.!' | cat dbfi.b - | ./bigbef_me brainfuck.bf
--Nthern 19:20, 20 September 2007 (UTC)
Very nice work, dude! It's a shame the original Befunge-93 was defined to use finite values in its stack, but it seems it was common to set limits like that in esolanguages back in the day, instead of just making implementations that don't allow infinite values. Anyways, this is a great achievement in itself, even if it requires a special dialect. --Keymaker 20:12, 20 September 2007 (UTC)

No longer esoteric???

Found this via Google. Be afraid. Be very afraid. --IanO 21:17, 26 Sep 2005 (GMT)

That site looks like one of those commercial sites made by some company that wants to make money from the internet and things that it's a professional company. Yep, one of those that uses .asp for their site and has pictures of people with the camera angle from above (check the main page). The makers of the site you link at don't even know what an esoteric programming language is, they just saw the name Befunge in a list of programming languages somewhere so added it. --Aardwolf 21:23, 26 Sep 2005 (GMT)
Befunge is not the only one they're offering:
* http://www.expertrating.com/jobs/Programming-jobs/Intercal-Programmer-jobs.asp
:D --Rune 21:49, 26 Sep 2005 (GMT)
Haha, that is fun.. Only if they knew.. Someone should request more information about Befunge programming, preferably acting like one has no idea at all about it. :D

A grammar note

The following sentence:

The word "Befunge" started life as a typographical error for the word "before," typed by Curtis Coleman at 4AM on a BBS chat system.

Was changed by User:Aardwolf (by moving the comma) to:

The word "Befunge" started life as a typographical error for the word "before", typed by Curtis Coleman at 4AM on a BBS chat system.

And then reverted by Graue, who suggested that Aardwolf 'leave the pedantry to those of us who know the rules'. An ironic statement, as both The Oxford Guide To The English Language and the Chicago Manual of Style state that the comma would go inside the quotation if and only if either a comma or a period occur in the material being quoted at that point. I anticipate this causing an argument, so have added this section (and haven't moved the comma again). Clearly the phrase 'the word "before"' is not a direct quotation (as what was actually typed was 'befunge'), and in this situation the comma would never appear inside the 'quotation'. --Safalra 16:02, 6 Oct 2005 (GMT)

I am not a native english speaker, but I also thought that comma inside the quote looked very odd. But then again, we might be making way too much fuzz about just a little comma here... --Rune 16:33, 6 Oct 2005 (GMT)
Okay, I suppose I'll trust the authorities you list. (I may have made that same error, if it was indeed an error, elsewhere as well.) Still, questions should not appear in edit summaries; the Graue Manual of Style forbids it. --Graue 20:28, 6 Oct 2005 (GMT)
Allright, peace man --Aardwolf 11:44, 7 Oct 2005 (GMT)

Yet Another Befunge Interpreter

Hi there.

I have written yet another Befunge93 interpreter (named YABI93). When I began doing so, I didn't know the JavaScript one and thaught it would be somewhat useful to have a platform-independent interpreter.

This was my very first java program and now that I got a little bit more used to object-orientation, I see that the sources are pretty ugly. But it works pretty good. And that's what counts for me at the moment.

Of course it's open source.

You can take a closer look at the project homepage: http://yabi93.sourceforge.net

I didn't know up to today that there is still such a living Esolang community. You peple around here seem to be real enthusiasts, which is great and you could be the first ones that give me a real feedback. Please test my program and discuss it with me. You can even join the "project team" that currently consists only of one person if you want. Or maybe you want to contribute a translation?

Well, I feel like I finally have arrived. ;) I'm looking forward to reading from you. --Efi 20:47, 15 Dec 2005 (GMT)

Well, I guess I could say that the applet doesn't load. The geek dump is "Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8) Gecko/20051111 Firefox/1.5". --Ihope127 21:13, 15 Dec 2005 (GMT)
I'm sorry for the confusion. The applet thing was just a test for the new beta version's hybrid classing (It will be applet and aplication in one .jar-file). The current Program is avaiable at http://sourceforge.net/projects/yabi93 (The files are here.) Please notice that YABI93 only runs with the newest Java RuntimeEnvironment (1.5.) I hope this is no fundamental problem. I'm already working on a 1.4-version. --Efi (Thomas Efer) 13:19, 16 Dec 2005 (GMT)
Ah. But still... it doesn't load ;-) Anyway, that program works quite nicely, except for the fact that it seems to mostly be in German. --Ihope127 15:29, 16 Dec 2005 (GMT)
Try using the command-line parameter en this should make it a lot more English. ;) Thx. for trying it out. --Efi (Thomas Efer) 15:52, 16 Dec 2005 (GMT)
Ahh yes... it's much more English now. It doesn't seem buggy so far, but then again, I don't know Befunge very well and thus can't test it. ;-) Nice work. --Ihope127 19:49, 16 Dec 2005 (GMT)

Programs without Put or Get

It seems to me that Put (p) and Get (g) are used in any program where it is necessary to access the third or lower values in the Stack. So I wrote a program which prints the first 15 Fibonacci numbers, without using Put or Get. 

00:.1:.>:"@"8**++\1+:67+`#@_v
       ^ .:\/*8"@"\%*8"@":\ <

As Put and Get have the ability to modify a Befunge program's own sourcecode, surely it's more ideal to use alternate methods to do something as simple as access the third or lower values in the Stack?

Unfortunately, if all values in the Stack must be a certain length (signed long int, as the Befunge-93 documentation says, for example), you can only access a certain way down the Stack. If the integers were of an arbitrary length, any value in the Stack would be accessable. This would also lead it to be, in extension, Turing complete. A way of doing this is to merge the two top values into eachother, such as 01100010 (98 = b) and 01100110 (102 = f) would become 01100110 01100010 (26210 = f b). The code I use to do this is: 

"@"4**+

And its reverse, to unmerge the two values, is: 

:"@"4*%\"@"4*/

These can both be used as many times as needed, to merge as many values as the integer length allows. The example given shifts the number left 8 bits ("@"4* = 256), but can be changed depending on what is required.

-Marz 20:00, 7 December 2007 (UTC)

Interpreter quality

I did some major testing of current Befunge-98 interpreters. The results are freely available for the perusal of anybody interested.

The results are, of course, somewhat biased, since I've done the whole thing by myself and can't guarantee that I've correctly interpreted everything in the spec. Still, my interpreter is the only one that gets through all the tests without dying.

Feel free to send me e-mail if you have anything to say on the subject. I'll try to monitor any discussion here, as well.

Deewiant 19:21, 9 January 2008 (UTC)

The entire Befunge-implementing world (all 12 of us!) owes you a debt of gratitude for this project. So: Thanks! --Chris Pressey 19:14, 28 November 2010 (UTC)

Hello World

The Hello World example: 

<v"Hello world"0
 <,_@#:

seems more complex than necessary. Shouldn't 

"Hello World",,,,,,,,,,@

work as well? Of course, it demonstrates nothing of Befunge's peculiarities. wr 87.139.81.19 11:34, 10 April 2008 (UTC)

Not quite. Your program prints out "dlroW olle". It should be:
"dlroW olleH",,,,,,,,,,,@
--Keymaker 13:43, 10 April 2008 (UTC)
I think that the purpose of example programs like the Hello World programs is to show off the way that a language typically behaves; the Befunge example shows a loop that's a typical way to print out strings in Befunge, and it would be a shorter way if a long string was used. Hello world programs in C aren't written as putchar('H'); putchar('e'); and so on, even though it's 'simpler' in some sense. --ais523 16:40, 11 April 2008 (UTC)

Compilation

I was running through the article and I had an idea. Wouldn't it be at least possible to remove the need for threaded code and recompilation and use self-modifying x86 code? All the code and data are stored in the same memory, if not the same segment. So couldn't a little snippet along the lines of 

PUSH CS
POP DS

Allow direct manipulation of the code? It wouldn't be small, as the code would have to be made into "tokens" of identical sizes, padded with real NOPs, 90h. It still wouldn't be truly compiled, but I think it'd be a step up from multiple simultaneous versions of the same code. --ToothPic 05:43, 1 July 2008 (UTC)

I think the relevant sentence in the article is "Note that the bf2c compiler is not correct since it does not handle p correctly, but it would not be impossible to make it do so (although the C language might not be well-suited for this.)" What you're suggesting would be an implementation of this feature, if I understand you. But there is still the problem that any given sequence of Befunge instructions could be executed forwards or backwards, so you are still on the level of threaded code: your "tokens" have to be executable in multiple orders.
Although, I guess one thing you could do is, every time you change the PC's direction, rewrite all the "directional" JMPs in the program to conform to the new direction... I can't imagine this being terribly efficient except for programs where the PC hardly ever changes direction... --Chris Pressey 19:04, 28 November 2010 (UTC)

What about editor of Befunge programs?

Who knows, are there any editors for Befunge (where it is possible both to write programs and to run it)? Of course, interpreter is a good thing, but... BurSer 20:22, 20 January 2010 (UTC)

My Yabi93-Interpreter (http://sourceforge.net/projects/yabi93/) works as a basic IDE. With command line parameter en you get it in English. --Efi (Thomas Efer) 07:28, 26 January 2010 (UTC)

Befunge-93 really 2d

Maybe not worth mentioning, but as I read Befunge-93 uses 80x25 memory cells , thus incrementing the pointer up and down instead of left and right means just adding or substracting 80 from it. In the same way one could define a 1d chess by just saying well the pawn moves eight forward. --(this comment by Mahagugu at 15:37, 16 January 2014‎ UTC; please sign your comments with ~~~~)

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