18
$\begingroup$

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?

$\endgroup$
6
  • 2
    $\begingroup$ +1, for digging up an obscure programming language to get an interpreted language to interpret. $\endgroup$
    – rcollyer
    Feb 10, 2012 at 2:40
  • $\begingroup$ If you get it working, you could set up BF cells in mma and use WReach's method to have it automatically interpreted. $\endgroup$
    – rcollyer
    Feb 10, 2012 at 2:43
  • 1
    $\begingroup$ @rcollyer I can see my productivity sliding far downhill on this one. Endless fun :) $\endgroup$
    – Andy Ross
    Feb 10, 2012 at 2:48
  • 3
    $\begingroup$ 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.) $\endgroup$
    – David
    Feb 10, 2012 at 4:12
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 10, 2012 at 4:40

4 Answers 4

14
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ 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! $\endgroup$
    – Andy Ross
    Feb 10, 2012 at 16:30
  • $\begingroup$ @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. $\endgroup$
    – rcollyer
    Feb 10, 2012 at 16:38
  • $\begingroup$ 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]. $\endgroup$
    – Andy Ross
    Feb 10, 2012 at 16:48
  • $\begingroup$ @Andy, that was exactly my thought when I asked the question. $\endgroup$
    – rcollyer
    Feb 10, 2012 at 16:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andy Ross
    Feb 10, 2012 at 18:25
12
$\begingroup$

Wasteful, but short and no side effects:

ReplaceList[lst, {x__, y___} /; Count[{x}, "["] == Count[{x}, "]"] :> Length[{x}], 1]
$\endgroup$
1
  • $\begingroup$ this is really neat and closest to the spirit of what I was shooting for thus far. $\endgroup$
    – Andy Ross
    Feb 10, 2012 at 16:21
8
$\begingroup$

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}

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

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]]
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Andy Ross
    Feb 10, 2012 at 8:02
  • 2
    $\begingroup$ 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[]... $\endgroup$ Feb 10, 2012 at 8:05
  • $\begingroup$ It seems your dream has come true as there is now a ScanIndexed function, albeit in the GeneralUtilities package. $\endgroup$
    – RunnyKine
    Apr 18, 2016 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.