Brainfuck interpreter in F#

Question

I have some concerns, like the updateValue function. I was trying to follow the functional paradigm, but I wonder if I could use another approach or something.

My parsing function seems overly complicated, particularly the '[' case seems complicated. Any other comments are appreciated too!

namespace Brainfuck
module Interpreter = 
 type public ProgramState = 
 { Pointer : int
 Memory : Map<int, int> }
 let private currentValue state = Map.find state.Pointer state.Memory
 let private updateValue state op = 
 let updateMemory = 
 match Map.tryFind state.Pointer state.Memory with
 | Some(x) -> 
 let m = Map.remove state.Pointer state.Memory
 Map.add state.Pointer (op x) m
 | None -> Map.add state.Pointer (op 0) state.Memory
 { state with Memory = updateMemory }
 type private Command = 
 | SimpleCommand of char
 | Loop of Command list
 let private parse code = 
 let literals = [ '+'; '-'; '>'; '<'; '.'; ',' ] |> Set.ofList
 let rec parsing = 
 function 
 | x :: xs when x = '[' -> 
 let innerLoop, innerRemaining = parsing xs
 let commands, remaining = parsing innerRemaining
 let remainingCommands, after = parsing remaining
 Loop(innerLoop) :: commands @ remainingCommands, after
 | x :: xs when x = ']' -> [], xs
 | x :: xs when Set.contains x literals -> 
 let commands, remaining = parsing xs
 SimpleCommand(x) :: commands, remaining
 | x :: xs -> parsing xs
 | [] -> [], []
 code
 |> Seq.toList
 |> parsing
 |> fst
 let private interpretSimpleCommand state command = 
 match command with
 | '>' -> { state with Pointer = (state.Pointer + 1) }
 | '<' -> { state with Pointer = (state.Pointer - 1) }
 | '+' -> updateValue state (fun x -> x + 1)
 | '-' -> updateValue state (fun x -> x - 1)
 | '.' -> 
 printf "%c" <| (char) (currentValue state)
 state
 | ',' -> updateValue state (fun x -> System.Console.Read())
 | _ -> failwith "invalid command"
 let private compute bytecode = 
 let rec cmp state cmd = 
 match cmd with
 | SimpleCommand(x) -> interpretSimpleCommand state x
 | Loop(xs) -> 
 let nextState = computeProgram state xs
 if currentValue (nextState) = 0 then nextState
 else cmp nextState cmd
 and computeProgram = List.fold cmp
 computeProgram { Pointer = 0
 Memory = Map.empty<int, int> } bytecode
 let public eval code = 
 code
 |> parse
 |> compute

• luksan: You could replace x::xs when x = '[' with '['::xs I believe.
• luksan: I also think the explicit type parameters on Map.empty<int, int> are not needed.
• Bruno: Wow, the type inference amaze me everyday, thanks!

Answer 1

let private currentValue state = Map.find state.Pointer state.Memory

This won't work correctly if you try to access memory that hasn't been set yet. Doing that should return 0, but will instead throw an exception. You can fix that by using Map.tryFind together with defaultArg:

let private currentValue state = defaultArg (Map.tryFind state.Pointer state.Memory) 0

---

let m = Map.remove state.Pointer state.Memory
Map.add state.Pointer (op x) m

You don't need to remove before adding the key back in, because add will overwrite the old value. (The documentation isn't clear on that.)

This also means you can make your code more DRY by using currentValue:

let updateMemory = 
 Map.add state.Pointer (op (currentValue state)) state.Memory

---

let rec parsing = 

I think that parsing is a weird name for a function, function names should be verbs. Since you're already using parse, if you can't figure out any better name, you could use something like parseInternal or parse'.

---

| x :: xs when x = '[' -> 
 let innerLoop, innerRemaining = parsing xs
 let commands, remaining = parsing innerRemaining
 let remainingCommands, after = parsing remaining
 Loop(innerLoop) :: commands @ remainingCommands, after

This code doesn't make any sense to me. And testing it on Wikipedia's Hello World program gives me incorrect results. Instead, I think it should look like this:

| x :: xs when x = '[' -> 
 let innerLoop, innerRemaining = parsing xs
 let commands, remaining = parsing innerRemaining
 Loop(innerLoop) :: commands, remaining

---

code
|> Seq.toList
|> parsing
|> fst

This means that if you encounter unmatched ], you're going to treat it as the end of the file. Is that the correct behavior?

And thinking about unmatched brackets some more, unmatched [ are automatically closed at the end of the input. Is that correct?

---

(fun x -> x + 1)

You can shorten this to: ((+) 1).

---

let private compute bytecode = 

I think that bytecode is a misleading name here, since it's not a code composed of bytes, it's an AST.

---

| Loop(xs) -> 
 let nextState = computeProgram state xs
 if currentValue (nextState) = 0 then nextState
 else cmp nextState cmd

This is not correct. Brainfuck loops are equivalent to while loops, not do while loops. The correct code would be something like:

| Loop(xs) -> 
 if currentValue state = 0
 then state
 else 
 let nextState = computeProgram state xs
 cmp nextState cmd