# Is there a more elegant and efficient way to write brainf*** style loops in Mathematica?

I'm having some fun writing a brainf*** interpreter in Mathematica. See this wiki article for more info. It works nicely but I'd like to find an elegant, preferably functional, way to handle the looping structures.

This is a simple example of what I'm hoping to do with the solution I currently have in place. The variable ptr is the position of a pointer in the program. The variable paren is used to keep track of the brackets, it increments on "[" and decrements on "]" so it should be zero when I find the proper closing bracket.

ptr = 1;
paren = 1;
lst = {"[", "[", "-", "]", ">", ">", ">", ".", "<", "<", "<", "]",
">", ">", ">", ">", ">", ">", "."};

While[paren > 0, ptr++;
Switch[lst[[ptr]], "[", paren++, "]", paren--, _, Null]]


Which tells me the closing "]" is located at position 12 in lst.

In[287]:= ptr

Out[287]= 12


Is there a more elegant and/or efficient way to do this?

-
+1, for digging up an obscure programming language to get an interpreted language to interpret. – rcollyer Feb 10 '12 at 2:40
If you get it working, you could set up BF cells in mma and use WReach's method to have it automatically interpreted. – rcollyer Feb 10 '12 at 2:43
@rcollyer I can see my productivity sliding far downhill on this one. Endless fun :) – Andy Ross Feb 10 '12 at 2:48
You guys don't know Brainfuck? Well then, here's the single most amazing program I've ever seen: awib.googlecode.com/svn/builds/awib-0.3.b (Brainfuck compiler polyglot in Brainfuck, Bash, TCL and C. Oh, and the documentation is part of the source code. And it compiles to Linux executables, TCL, Ruby, Go and C code.) – David Feb 10 '12 at 4:12
Would it be cheating to just use the Brainf*** -> C conversion table in the Wiki (using Mathematica constructs such as While[...] rather than C constructs such as while (...) {...}). Then you could just call ToExpression. – Andrew Moylan Feb 10 '12 at 4:40
show 1 more comment

My solution isn't precisely what was asked for: it is the complete parser. At the moment, it is strictly a parser, but the functionality is all ready to be added.

Clear[bfinterpreter, bfeval, movf, movb, add1,  sub1, write, read, loop,
stored, loopdepth, rls]
rls = {">" -> movf, "<" -> movb, "+" -> add1,
"-" -> sub1, "." -> write, "," -> read,
"]" :> With[{mode = loopdepth--}, loop[stored[mode]]]
};

bfeval[a : (">" | "<" | "+" | "-" | "." | "," | "]")] :=
With[{val = a /. rls},
If[loopdepth == 0,
val[ptr],
AppendTo[stored[loopdepth], val]; ## &[]]
]

bfeval["["] := (stored[++loopdepth] = {}; ## &[])
bfeval[_] := (## &[])

bfinterpreter[code_String] :=
Block[{loopdepth = 0, stored, ptr,
bfeval /@ StringSplit[code, ""]
];


A user would access this by passing bfinterpreter as String of BF commands. The string is split into individual characters via StringSplit[code, ""], and then bfeval is mapped over the resulting list. Scan would be better for the full implementation, but I used Map here to show that the parser works. In particular, using this on the OPs supplied BF code we get

(* spaces added for demo purposes *)
bfinterpreter["[[-]>> > . <<<]>>>  >>>."]
(*
=> {loop[{          (* [ *)
loop[{sub1}], (* [-] *)
movf, (* > *)
movf, (* > *)
movf, (* > *)
write, (* . *)
movb, (* < *)
movb, (* < *)
movb  (* < *)
}
][ptr],    (* ] *)
movf[ptr], (* > *)
movf[ptr], (* > *)
movf[ptr], (* > *)
movf[ptr], (* > *)
movf[ptr], (* > *)
movf[ptr], (* > *)
write[ptr] (* . *)
}
*)


As you've probably figured out, all the magic happens in bfeval. The first form accepts all BF characters {">", "<", "+", "-", ".", ",", "]"}, but the open loop, "[". It works by applying a list of replacement rules to the supplied character and either storing it, if we're within a loop, or evaluating it immediately. The close loop rule, though, has added functionality in that it needs to both reduce loop counter, loopdepth, and return the stored commands for the loop, hence the use of RuleDelayed (:>).

The second form of bfeval simply increments the loop counter, and returns ##&[] to ensure the final list doesn't contain Nulls. And, the final form is the catch all for every other type of character.

-
wow, now I really understand your question about single versus multiple passes. This setup will allow the code to be optimized on the fly in a way I can't in a single pass. Very nice! – Andy Ross Feb 10 '12 at 16:30
@Andy It still is a single pass interpreter because if you define movf, etc, they will be executed immediately. (This was also the comment about using Scan.) The loops had to be constructed outside of the normal execution order, so that they could be used effectively. But, you are correct, if you do not define the operations before executing bfinterpreter you can then optimize it in subsequent passes. – rcollyer Feb 10 '12 at 16:38
right, but one wouldn't have to define movf. I commented since the results you show make it obvious what a second pass might do for example, say I have ... add1, add1, add1,... If these are just inert and don't actually do anything, I could go back in a second pass and create add[3,ptr]. – Andy Ross Feb 10 '12 at 16:48
@Andy, that was exactly my thought when I asked the question. – rcollyer Feb 10 '12 at 16:51
I've accepted this answer because of the effort involved and because it caused me to rethink the way I'm approaching the problem in the first place. – Andy Ross Feb 10 '12 at 18:25

Wasteful, but short and no side effects:

ReplaceList[lst, {x__, y___} /; Count[{x}, "["] == Count[{x}, "]"] :> Length[{x}], 1]

-
 this is really neat and closest to the spirit of what I was shooting for thus far. – Andy Ross Feb 10 '12 at 16:21

This may be way off base as I really don't understand what you are doing, but perhaps something like:

Replace[lst, {"[" -> 1, "]" -> -1, _ -> 0}, 1];

Position[Accumulate@%, 0, 1, 1]


{{12}}

Or perhaps:

paren = 0;
x@"[" := ++paren;
x@"]" := --paren;
1 + LengthWhile[x /@ lst, # =!= 0 &]


12

Perhaps more cryptically:

Position[
Accumulate@lst,
_?(Equal @@ # ~Coefficient~ {"[", "]"} &),
{1}, 2
][[2]]


{12}

-
@Andy I just added another one. Is this closer to or farther from what you want? – Mr.Wizard Feb 10 '12 at 8:50
I especially like that last one, very sneaky :) – Andy Ross Feb 10 '12 at 16:27
Accumulate@lst??? Talk about misusing mma... +1 – acl Feb 11 '12 at 13:12

I'd have done something like

ptr = paren = 0;
lst = {"[", "[", "-", "]", ">", ">", ">", ".", "<", "<", "<", "]",
">", ">", ">", ">", ">", ">", "."};

res = 0;
Scan[(++ptr; Switch[#, "[", ++paren, "]", --paren; res = ptr, _, Null]) &, lst];
{paren, res}


myself.

A more compact version might go something like

Catch[Scan[(++ptr; Switch[#,
"[", ++paren,
"]", If[(--paren) == 0, Throw[ptr]],
_, Null]) &, lst]]


What follows is a MapIndexed[] version. I prefer the Scan[] versions myself, but at least ptr is no longer needed:

Catch[MapIndexed[
Switch[#1, "[", ++paren,
"]", If[(--paren) == 0, Throw[First[#2]]],
_, Null] &, lst]]

-
I like this solution, hence the +1, but I'm hoping for something a bit more functional and cryptic in the spirit of both BF and the clever functional capabilities of M. – Andy Ross Feb 10 '12 at 8:02
Ah, so you want to avoid the use of the ptr and paren auxiliary variables, I presume? Too bad there does not seem to be an analog of MapIndexed[] for Scan[]... – J. M. Feb 10 '12 at 8:05