# 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. Commented Feb 10, 2012 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. Commented Feb 10, 2012 at 2:43
• @rcollyer I can see my productivity sliding far downhill on this one. Endless fun :) Commented Feb 10, 2012 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.) Commented Feb 10, 2012 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. Commented Feb 10, 2012 at 4:40

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! Commented Feb 10, 2012 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. Commented Feb 10, 2012 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]. Commented Feb 10, 2012 at 16:48
• @Andy, that was exactly my thought when I asked the question. Commented Feb 10, 2012 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. Commented Feb 10, 2012 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. Commented Feb 10, 2012 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? Commented Feb 10, 2012 at 8:50
• I especially like that last one, very sneaky :) Commented Feb 10, 2012 at 16:27
• Accumulate@lst??? Talk about misusing mma... +1
– acl
Commented Feb 11, 2012 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. Commented Feb 10, 2012 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[]... Commented Feb 10, 2012 at 8:05
• It seems your dream has come true as there is now a ScanIndexed function, albeit in the GeneralUtilities package. Commented Apr 18, 2016 at 17:19