Brainfuck interpreter in F#

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 }

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)

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

StackExchange Code Review Q#84695, answer score: 3