brainfuck interpreter using tail calls

main.roc

app "brainroc"
    packages {
        pf: "https://github.com/roc-lang/basic-cli/releases/download/0.3.2/tE4xS_zLdmmxmHwHih9kHWQ7fsXtJr7W7h3425-eZFk.tar.br",
    }
    imports [
        pf.File,
        pf.Path,
        pf.Stdout,
        pf.Task,
    ]
    provides [main] to pf

dataSize = 30_000

Instruction : { 
    operator: Operator,
    operand: Nat
}

Operator : [
    IncrementPointer,
    DecrementPointer,
    IncrementByte,
    DecrementByte,
    Output,
    JumpForward,
    JumpBack,
]

lookup : Operator -> (Nat, List Instruction, Nat, List U8, Nat, List U8 -> List U8)
lookup = \operator ->
    when operator is
        IncrementPointer -> incrementPointer
        DecrementPointer -> decrementPointer
        IncrementByte -> incrementByte
        DecrementByte -> decrementByte
        Output -> stdout
        JumpForward -> jumpForward
        JumpBack -> jumpBack

Jump : Nat

tokenize : List U8 -> (Nat, List Instruction, List Jump)
tokenize = \bytes ->
    List.walk bytes (0, [], []) \(pc, instructions, jumpStack), c ->
        when c is
            '>' ->
                instruction = { operator: IncrementPointer, operand: 0 }
                (pc + 1, List.append instructions instruction, jumpStack)

            '<' ->
                instruction = { operator: DecrementPointer, operand: 0 }
                (pc + 1, List.append instructions instruction, jumpStack)

            '+' ->
                instruction = { operator: IncrementByte, operand: 0 }
                (pc + 1, List.append instructions instruction, jumpStack)

            '-' ->
                instruction = { operator: DecrementByte, operand: 0 }
                (pc + 1, List.append instructions instruction, jumpStack)

            '.' ->
                instruction = { operator: Output, operand: 0 }
                (pc + 1, List.append instructions instruction, jumpStack)

            '[' ->
                instruction = { operator: JumpForward, operand: 0 }
                (
                    pc + 1,
                    List.append instructions instruction, 
                    List.append jumpStack pc,
                )

            ']' ->
                when List.last jumpStack is
                    Err _ -> crash "malformed program"
                    Ok jumpPc ->
                        instruction = { operator: JumpBack, operand: jumpPc }
                        (
                            pc + 1,
                            List.append instructions instruction |> List.update jumpPc \{ operator } -> { operator, operand: pc },
                            List.dropLast jumpStack,
                        )

            ' ' | '\n' | '\t' -> (pc, instructions, jumpStack)
                            
            other -> 
                when Str.fromUtf8 [ other ] is
                    Ok str -> 
                        crash "unexpected character: '\(str)'" 

                    Err _ -> 
                        crash "unexpected non-utf8 character" 


execute : List Instruction -> Str
execute = \instructions ->
    output = next 0 instructions 0 (List.repeat 0 dataSize) [] 

    when Str.fromUtf8 output is
        Err _ -> crash "invalid utf8 in the output"
        Ok str -> str

next : Nat, List Instruction, Nat, List U8, List U8 -> List U8
next = \pc, instructions, dataPtr, data, output ->
    if pc < List.len instructions then
        nextInstruction = List.getUnsafe instructions pc
        
        f = lookup nextInstruction.operator

        f pc instructions dataPtr data nextInstruction.operand output
    else
        output
    

incrementPointer : Nat, List Instruction, Nat, List U8, Nat, List U8 -> List U8
incrementPointer = \pc, instructions, dataPtr, data, _, output ->
    next (Num.addWrap pc 1) instructions (Num.addWrap dataPtr 1) data output

decrementPointer : Nat, List Instruction, Nat, List U8, Nat, List U8 -> List U8
decrementPointer = \pc, instructions, dataPtr, data, _, output ->
    next (Num.addWrap pc 1) instructions (Num.subWrap dataPtr 1) data output

incrementByte : Nat, List Instruction, Nat, List U8, Nat, List U8 -> List U8
incrementByte = \pc, instructions, dataPtr, data, _, output ->
    b = List.getUnsafe data dataPtr
    newData = List.replaceUnsafe data dataPtr (Num.addWrap b 1) |> .list
    next (Num.addWrap pc 1) instructions dataPtr newData output

decrementByte : Nat, List Instruction, Nat, List U8, Nat, List U8 -> List U8
decrementByte = \pc, instructions, dataPtr, data, _, output ->
    b = List.getUnsafe data dataPtr
    newData = List.replaceUnsafe data dataPtr (Num.subWrap b 1) |> .list
    next (Num.addWrap pc 1) instructions dataPtr newData output

stdout : Nat, List Instruction, Nat, List U8, Nat, List U8 -> List U8
stdout = \pc, instructions, dataPtr, data, _, output ->
    c = List.getUnsafe data dataPtr
    newOutput = List.append output c
    next (Num.addWrap pc 1) instructions dataPtr data newOutput

jumpForward : Nat, List Instruction, Nat, List U8, Nat, List U8 -> List U8
jumpForward = \pc, instructions, dataPtr, data, operand, output ->
    n = List.getUnsafe data dataPtr 

    if n == 0 then
        next (Num.addWrap operand 1) instructions dataPtr data output
    else
        next (Num.addWrap pc 1) instructions dataPtr data output

jumpBack : Nat, List Instruction, Nat, List U8, Nat, List U8 -> List U8
jumpBack = \pc, instructions, dataPtr, data, operand, output ->
    n = List.getUnsafe data dataPtr

    if n > 0 then
        next (Num.addWrap operand 1) instructions dataPtr data output
    else
        next (Num.addWrap pc 1) instructions dataPtr data output

main =
    inputFilePath = "/home/folkertdev/roc/brainroc/examples/bench/bench-1.bf"
    inputResult <- inputFilePath |> Path.fromStr |> File.readBytes |> Task.attempt

    when inputResult is
        # Run the interpreter
        Ok bytes -> 
            (_pc, tokens, _jumpStack) = tokenize bytes

            Stdout.line (execute tokens) 
        Err (FileReadErr _ _) -> "Failed to read the input file `\(inputFilePath)`." |> Stdout.line