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

Question

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?

Answer 1

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, 
         movf, movb, add1,  sub1, write, read}, 
   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.

Answer 2

Wasteful, but short and no side effects:

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

Answer 3

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}

Answer 4

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]]