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

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