polyglot: the almighty befunge

reminder: this article is part of a serie.

till now, we support 5 languages. plain, boring, production languages. it's time to add fun languages - and which is funnier than befunge? this topological, stack-based language on a 2D lahey space really is interesting to study. for this polyglot effort, we're going to use the -98 version of befunge, and use the interpreter supplied by Language::Befunge (shameless plug). so, let's create our test script, and let's roll!

in befunge, every character is an instruction. and the instruction pointer can move in whatever direction one wants: from left to right (as other languages), but also right to left, top to bottom or bottom to top. add to this that code and data share the same space, and you will understand that befunge introduces a whole new dimension to coding (and obfuscation). :-)

before trying to mix befunge with our polyglot program, let's first try to write the program itself. here's my version:

^ ,+*68-*+55/+55::,+*+338/+55:<

note that spaces are important: if chars are not lined up, then your program changes semantics!

so, how can we include that in our polyglot beast? befunge starts at the top-left corner, with a left-to-right velocity. therefore, we need to insert it at the top of the file... which is not really doable, given the other languages. some things worth knowing wrt befunge:
  • when the instruction pointer hits a border, it goes back to the opposite (i simplify a bit, but for this program you can ignore the details).
  • when hitting an unknown instruction, befunge reverses the direction. this is also the case on error cases.

unlucky us, the opening paren is a valid befunge 98 instruction: it loads a library (yes, befunge supports libraries). but we cannot insert any library name before the (, therefore it will try to load a non-existant library. which is an error - bingo! we reverse. we just need to insert a caret ^ (protected by a hash for perl, and without impact on other languages) that will change befunge velocity to bottom-to-top. and since we're at the top of file, it will wrap to the end of file! it misses the space between bar and the star at the end of the file, but * being a stack multiplication in befunge, the star of the end of pascal comment is not a problem. so, let's just use a > to put it back on a left-to-right velocity (protected by a * comment for fortran). note how the ^ and > are lined up:

(*foo /*bar#^
* >
#define bar *)

we can now paste our befunge code, protected by * fortran comments. but since we want befunge to execute as if it were at the top-left corner of the file, we need to clear the stack first, in case some instructions filled it. this is done by inserting a n instruction (n clears the stack in befunge) just after the comment:

*n 1:86*+,a,86*+,a,11884pv >
* +,>a,94g\84g1-:84p!#@_>:94p+:a`#v_:'0
* ^ ,+*68-*+55/+55::,+*+338/+55:< */
#define bar *)

but when we run our test suite, we don't get the expected output for befunge! when thinking about it, it's obvious: the second line of our befunge program wraps from the right (after the 0) to the beginning of the line. and when our plain befunge program was hitting a + instruction (addition), it now hits a * instruction, which, as you remember, performs a multiplication. which totally ruins our stack! so we need to somehow ignore this instruction - but we cannot remove it. so let's just add 2 numbers on the stack (with eg : which duplicates the top of stack), let befunge hit the * and then remove the top of stack (instruction $ which pops the stack). we can then continue with our regular befunge program:

*n 1:86*+,a,86*+,a,11884pv >
*$ +,>a,94g\84g1-:84p!#@_>:94p+:a`#v_:'0 ::
* ^ ,+*68-*+55/+55::,+*+338/+55:<

you can see the whole program:

(*foo /*bar#^
*1337#) 2>/dev/null;i=0; a=1; b=1;echo $a;while test $i -lt 9;do c=$((a+b));a=$b;b=$c;echo $a;i=$((i+1));done;exit
*0) if 0; sub C () {} # */ );

#include <stdio.h>
#include <stdlib.h>
#define C
#define $ /*
C ; "*/
C ; main () { /*"; { # */
C ; int $ i;
C ; int $ n1;
C ; int $ n2;
C ; int $ n3;
C ; $ i = 0;
C ; $ n1 = 1;
C ; $ n2 = 1;
C ; printf( "%d\n", $ n1 );
C ; while ( $ i < 9 ) {
C ; $ n3 = $ n1 + $ n2;
C ; $ n1 = $ n2;
C ; $ n2 = $ n3;
C ; printf( "%d\n", $ n1 );
C ; $ i++;
C ; }
C ; }

#define foo /*
C ; __END__
*) program foo; (*
*) var i, n1, n2, n3 : integer; (*
*) begin i := 0; n1 := 1; n2 := 1; writeln(n1); while i < 9 do begin (*
*) n3 := n1 + n2; n1 := n2; n2 := n3; writeln(n1); i := i + 1; end; end.(*

integer i, n1, n2, n3
n1 = 1
n2 = 1
print '(I0)', n1
do 10 i = 1, 9
n3 = n1 + n2
n1 = n2
n2 = n3
print '(I0)', n1
10 continue
*n 1:86*+,a,86*+,a,11884pv >
*$ +,>a,94g\84g1-:84p!#@_>:94p+:a`#v_:'0 ::
* ^ ,+*68-*+55/+55::,+*+338/+55:<
#define bar *)

which now passes all our tests:

$ prove -l t
t/c..........fibonacci.c:1: warning: data definition has no type or storage class
All tests successful.
Files=6, Tests=6, 0 wallclock secs ( 0.02 usr 0.01 sys + 0.38 cusr 0.09 csys = 0.50 CPU)
Result: PASS

6 languages supported, that's not bad. but we won't stop here! to be continued...

No comments:

Post a Comment