Execute Brain****/Standard ML

From Rosetta Code
Execute Brain****/Standard ML is an implementation of Brainf***. Other implementations of Brainf***.
Execute Brain****/Standard ML is part of RCBF. You may find other members of RCBF at Category:RCBF.

Quick implementation of a Brainfuck interpreter in Standard ML.

Like the Haskell version but without the lazy lists:

Pairs of lists are used to implement both the two-side infinite band of cells, and the program storage.

run interprets a Brainfuck program as a list of characters and reads integers from stdin and outputs them to stdout.

A more efficient implementation could for example only admit well-bracketed brainfuck programs, and parse bracket blocks first, to replace the matchLeft and matchRight which need linear time.

fun moveLeft  (x::l, r) = (l, x::r)
fun moveRight (l, x::r) = (x::l, r)
 
fun matchLeft (d as (#"["::_, _)) = d
| matchLeft (d as (#"]"::_, _)) = matchLeft (moveLeft (matchLeft (moveLeft d)))
| matchLeft d = matchLeft (moveLeft d)
 
fun matchRight (d as (_, #"]"::_)) = moveRight d
| matchRight (d as (_, #"["::_)) = matchRight (matchRight (moveRight d))
| matchRight d = matchRight (moveRight d)
 
fun pad ([], []) = ([0], [0])
| pad ([], r ) = ([0], r )
| pad (l , []) = (l , [0])
| pad d = d
 
fun modify (f, (l, x::r)) = (l, f x :: r)
 
fun exec ( (_, [] ), _ ) = ()
| exec (p as (_, #">"::_), d ) = exec (moveRight p, pad (moveRight d))
| exec (p as (_, #"<"::_), d ) = exec (moveRight p, pad (moveLeft d))
| exec (p as (_, #"+"::_), d ) = exec (moveRight p, modify (fn x => x + 1, d))
| exec (p as (_, #"-"::_), d ) = exec (moveRight p, modify (fn x => x - 1, d))
| exec (p as (_, #","::_), d ) = let val c = valOf (Int.fromString (valOf (TextIO.inputLine TextIO.stdIn))) in
exec (moveRight p, modify (fn _ => c , d))
end
| exec (p as (_, #"."::_), d as (_, x::_)) = (print (Int.toString x ^ "\n");
exec (moveRight p, d))
| exec (p as (_, #"["::_), d as (_, 0::_)) = exec (matchRight (moveRight p), d)
| exec (p as (_, #"["::_), d ) = exec (moveRight p, d)
| exec (p as (_, #"]"::_), d as (_, 0::_)) = exec (moveRight p, d)
| exec (p as (_, #"]"::_), d ) = exec (matchLeft (moveLeft p), d)
 
fun run s = exec (([], s), ([0], [0]))

Example output:

- run (explode ",[>+<-].>.");
5
0
5
val it = () : unit