commit acf3448fc0a4e4066a858ae02bc6340ec0ae53d7
parent 64d851fab8598d35c4a98bf549d376d8cafabe91
Author: david cochran <about.trout@gmail.com>
Date: Sat, 18 Nov 2023 13:38:14 -0800
fixes #3 - support "streaming" command evaluation
Diffstat:
| M | README.md | | | 29 | ++++++++++++++++++++++++++++- |
| A | bf.go | | | 124 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | bf_test.go | | | 122 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | cmd/gbfy/main.go | | | 73 | +++++++++++++++++++++++++++++++++++++++++++++++-------------------------- |
| D | gbfy.go | | | 141 | ------------------------------------------------------------------------------- |
| D | gbfy_test.go | | | 144 | ------------------------------------------------------------------------------- |
6 files changed, 321 insertions(+), 312 deletions(-)
diff --git a/README.md b/README.md
@@ -1,3 +1,30 @@
# `gbfy`
-A [Brainfuck](https://en.wikipedia.org/wiki/Brainfuck) interpreter in Golang.
+A [Brainfuck](https://en.wikipedia.org/wiki/Brainfuck) interpreter that I wrote myself in Go.
+
+
+```
+$ cat test.bf
+,>,<[>+<-]>.
+$ hexdump -C input.bytes
+00000000 01 02 |..|
+00000002
+$ ./gbfy -f test.bf -i input.bytes -repl
+2023/12/02 18:41:06 Output from execution: [3]
+2023/12/02 18:41:06 Starting interactive REPL
+Welcome!
+ :q[uit] to exit REPL loop
+ :d[ump] to dump interpreter state
+ :f[uck] to reset interpreter state
+gbfy> :d
+cmds: ",>,<[>+<-]>."
+i: 12, current cmd: '.'
+cells: [0 3 0 0 0 0 0 0 0 0]
+d: 1, current cell: 3
+gbfy> +++++
+gbfy> :d
+cmds: ",>,<[>+<-]>.+++++"
+i: 17, current cmd: '+'
+cells: [0 8 0 0 0 0 0 0 0 0]
+d: 1, current cell: 8
+```
diff --git a/bf.go b/bf.go
@@ -0,0 +1,124 @@
+package gbfy
+
+import (
+ "bytes"
+ "errors"
+ "fmt"
+)
+
+type Brainfuck struct {
+ cells [3e4]byte // cells
+ d int // data pointer for cells access
+ cmds []byte // commands evaluated by the interpreter
+ i int // instruction pointer for cmds access
+
+ in, out *bytes.Buffer // input and output buffers
+
+ loops map[int]int // stores index for matching [ or ]
+ parLoops []int // indices for not-yet-complete loops
+}
+
+// New returns a new Brainfuck interpreter.
+func New(in, out *bytes.Buffer) *Brainfuck {
+ return &Brainfuck{in: in, out: out, loops: map[int]int{}}
+}
+
+// Run runs a Brainfuck program and returns output bytes or error.
+func Run(program string, in *bytes.Buffer) ([]byte, error) {
+ var out bytes.Buffer
+ bf := New(in, &out)
+ for _, cmd := range []byte(program) {
+ if err := bf.Eval(cmd); err != nil {
+ return nil, err
+ }
+ }
+ return out.Bytes(), nil
+}
+
+// Eval evaluates a single command with the given interpreter.
+func (bf *Brainfuck) Eval(cmd byte) error {
+ switch cmd {
+ case '>', '<', '+', '-', '.', ',', '[', ']':
+ bf.cmds = append(bf.cmds, cmd)
+
+ // TODO: Move this special loop handling to internal .eval?
+ j := len(bf.cmds) - 1
+ // Special handling for loops.
+ if cmd == '[' {
+ bf.parLoops = append(bf.parLoops, j)
+ }
+ if cmd == ']' {
+ if len(bf.parLoops) == 0 {
+ return errors.New("invalid loop close")
+ }
+ k := bf.parLoops[len(bf.parLoops)-1]
+ bf.loops[j] = k
+ bf.loops[k] = j
+ bf.parLoops = bf.parLoops[:len(bf.parLoops)-1]
+ }
+ return bf.eval()
+ default:
+ return nil
+ }
+}
+
+func (bf *Brainfuck) eval() error {
+ if len(bf.parLoops) > 0 {
+ // Delay evaluation if there are unclosed loops.
+ return nil
+ }
+
+ for bf.i < len(bf.cmds) {
+ switch bf.cmds[bf.i] {
+ case '>':
+ bf.d++
+ if bf.d >= len(bf.cells) {
+ bf.d -= len(bf.cells)
+ }
+ case '<':
+ bf.d--
+ if bf.d < 0 {
+ bf.d += len(bf.cells)
+ }
+ case '+':
+ bf.cells[bf.d]++
+ case '-':
+ bf.cells[bf.d]--
+ case '.':
+ bf.out.WriteByte(bf.cells[bf.d])
+ case ',':
+ if b, err := bf.in.ReadByte(); err != nil {
+ return fmt.Errorf("failed to readDataVal: %v", err)
+ } else {
+ bf.cells[bf.d] = b
+ }
+ case '[':
+ if bf.cells[bf.d] == 0 {
+ bf.i = bf.loops[bf.i]
+ }
+ case ']':
+ if bf.cells[bf.d] != 0 {
+ bf.i = bf.loops[bf.i]
+ }
+ }
+ bf.i++
+ }
+ return nil
+}
+
+// Dump interpreter state to caller.
+func (bf *Brainfuck) Dump() (int, []byte, int, []byte, []byte) {
+ return bf.d, bf.cells[:], bf.i, bf.cmds, bf.out.Bytes()
+}
+
+// Reset interpreter state.
+func (bf *Brainfuck) Reset() {
+ bf.d = 0
+ bf.cells = [len(bf.cells)]byte{}
+
+ bf.i = 0
+ bf.cmds = nil
+
+ bf.loops = map[int]int{}
+ bf.parLoops = nil
+}
diff --git a/bf_test.go b/bf_test.go
@@ -0,0 +1,122 @@
+package gbfy
+
+import (
+ "bytes"
+ "fmt"
+ "testing"
+
+ "github.com/google/go-cmp/cmp"
+)
+
+func TestEval(t *testing.T) {
+ tests := []struct {
+ // Command to evaluate.
+ cmd byte
+ // Expected value of instruction and Data pointer.
+ i, d int
+ // Expected values of *specific* cells; mapping between cell
+ // index and value expected there. Since the cell region is
+ // large (3e4) and sparse (0 by default) only specific cells
+ // are checked.
+ cells map[int]byte
+ // Expected output data bytes.
+ out []byte
+ }{
+ // Check < and > move data pointer around circular cell region.
+ {'<', 1, 29999, nil, nil},
+ {'>', 2, 0, nil, nil},
+ // Check that + and - modify cell values.
+ {'+', 3, 0, map[int]byte{0: 1}, nil},
+ {'-', 4, 0, map[int]byte{0: 0}, nil},
+ // Check that , and . read input and write output bytes.
+ {',', 5, 0, map[int]byte{0: 4}, nil},
+ {'>', 6, 1, map[int]byte{0: 4}, nil},
+ {',', 7, 1, map[int]byte{0: 4, 1: 8}, nil},
+ {',', 8, 1, map[int]byte{0: 4, 1: 15}, nil},
+ {'>', 9, 2, map[int]byte{0: 4, 1: 15}, nil},
+ {',', 10, 2, map[int]byte{0: 4, 1: 15, 2: 16}, nil},
+ {'.', 11, 2, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16}},
+ {'<', 12, 1, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16}},
+ {'.', 13, 1, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15}},
+ {'<', 14, 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15}},
+ {'.', 15, 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15, 4}},
+ // Check that [ and ] are handled correctly by adding two adjacent cells.
+ // Evaluation is delayed in the presence of partial loops, so all internal
+ // state remain the same until the final ] is Eval'd.
+ {'[', 15, 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15, 4}},
+ {'-', 15, 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15, 4}},
+ {'>', 15, 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15, 4}},
+ {'+', 15, 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15, 4}},
+ {'<', 15, 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15, 4}},
+ {']', 21, 0, map[int]byte{0: 0, 1: 19, 2: 16}, []byte{16, 15, 4}},
+ {'>', 22, 1, map[int]byte{0: 0, 1: 19, 2: 16}, []byte{16, 15, 4}},
+ {'.', 23, 1, map[int]byte{0: 0, 1: 19, 2: 16}, []byte{16, 15, 4, 19}},
+ }
+
+ var out bytes.Buffer
+ bf := New(bytes.NewBuffer([]byte{4, 8, 15, 16, 23, 41}), &out)
+ if err := checkInterpreter(bf, 0, 0, nil, nil); err != nil {
+ t.Fatalf("[0] Unexpected interpreter state: %v", err)
+ }
+
+ for i, test := range tests {
+ if err := bf.Eval(test.cmd); err != nil {
+ t.Fatalf("[%d] Eval(%q) failed with error: %v", i+1, test.cmd, err)
+ }
+ if err := checkInterpreter(bf, test.i, test.d, test.cells, test.out); err != nil {
+ t.Errorf("[%d] Unexpected interpreter state: %v", i+1, err)
+ }
+ }
+}
+
+func checkInterpreter(bf *Brainfuck, i, d int, cells map[int]byte, out []byte) error {
+ if bf.i != i {
+ return fmt.Errorf("instruction pointer; got %d, want %d", bf.i, i)
+ }
+ if bf.d != d {
+ return fmt.Errorf("data pointer; got %d, want %d", bf.d, d)
+ }
+ for idx, got := range bf.cells {
+ if want := cells[idx]; got != want {
+ return fmt.Errorf("cell value at index %d; got %d, want %d", idx, got, want)
+ }
+ }
+ if diff := cmp.Diff(out, bf.out.Bytes()); diff != "" {
+ return fmt.Errorf("output diff (-want +got): %s", diff)
+ }
+ return nil
+}
+
+func TestInvalidLoopHandling(t *testing.T) {
+ invalidLoops := []string{"]", "[]]", "[][]]"}
+ for _, test := range invalidLoops {
+ _, err := Run(test, nil)
+ if err == nil {
+ t.Errorf("Parsed invalid program %q; expected error", test)
+ }
+ }
+}
+
+func TestHelloWorld(t *testing.T) {
+ program := `
+ >++++++++[<+++++++++>-]<.
+ >++++[<+++++++>-]<+.
+ +++++++..
+ +++.
+ >>++++++[<+++++++>-]<++.
+ ------------.
+ >++++++[<+++++++++>-]<+.
+ <.
+ +++.
+ ------.
+ --------.
+ >>>++++[<++++++++>-]<+.`
+
+ out, err := Run(program, nil)
+ if err != nil {
+ t.Fatalf("Run failed: %v", err)
+ }
+ if diff := cmp.Diff("Hello, World!", string(out)); diff != "" {
+ t.Errorf("Mismatched output data (-want +got):\n%s", diff)
+ }
+}
diff --git a/cmd/gbfy/main.go b/cmd/gbfy/main.go
@@ -2,8 +2,10 @@ package main
import (
"bufio"
+ "bytes"
"flag"
"fmt"
+ "io"
"log"
"os"
@@ -19,8 +21,6 @@ var (
func main() {
flag.Parse()
- // Read contents of codeFile and inputFile to get commands
- // to execute and any input data the program may expect.
var (
err error
cmds []byte
@@ -39,51 +39,72 @@ func main() {
}
}
- bf, err := gbfy.New(string(cmds), input)
+ var output bytes.Buffer
+ bf := gbfy.New(bytes.NewBuffer(input), &output)
if err != nil {
log.Fatalf("Failed to initialize interpreter: %v", err)
}
- output, err := bf.Run()
- if err != nil {
- log.Printf("Run failed with error: %v", err)
+ if len(cmds) > 0 {
+ for _, cmd := range cmds {
+ if err := bf.Eval(cmd); err != nil {
+ log.Fatalf("Failed to Eval command %q: %v", cmd, err)
+ }
+ }
+ log.Printf("Output from execution: %v\n", output.Bytes())
}
- log.Printf("Output from execution: %q\n", output)
-
- // Drop user into interactive "REPL" if requested. Execution
- // may continue in the REPL with whatever interpreter state
- // state the above program left it in.
if *launchREPL {
- log.Println("... starting interactive REPL")
- beInteractive(bf)
+ log.Println("Starting interactive REPL")
+ repl(bf)
}
}
-const welcomeMsg = `Welcome!
+const (
+ welcomeMsg = `Welcome!
:q[uit] to exit REPL loop
:d[ump] to dump interpreter state
:f[uck] to reset interpreter state`
-func beInteractive(bf *gbfy.Brainfuck) {
+ prompt = "gbfy> "
+)
+
+func repl(bf *gbfy.Brainfuck) {
fmt.Println(welcomeMsg)
in := bufio.NewReader(os.Stdin)
for {
- fmt.Print("gbfy> ")
- line, _ := in.ReadString('\n')
- if line[0] == ':' {
- // Handle REPL commands.
+ fmt.Print(prompt)
+ line, err := in.ReadString('\n')
+ if err == io.EOF {
+ fmt.Println("")
+ return
+ } else if err != nil {
+ log.Fatalf("Error! %v", err)
+ }
+
+ if len(line) > 0 && line[0] == ':' {
switch line[1] {
- case 'q': // exit REPL loop.
- return
- case 'd': // dump state to stdout.
- fmt.Println(bf.String())
- case 'f': // reset interpreter.
+ case 'd':
+ replDump(bf)
+ case 'f':
bf.Reset()
- fmt.Println("Restarted interpreter...")
+ fmt.Println("Reset interpreter!")
+ case 'q':
+ return
}
} else {
- // Handle a Brainfuck command(s).
+ for _, cmd := range []byte(line) {
+ if err := bf.Eval(cmd); err != nil {
+ log.Fatalf("Failed to Eval command %q: %v", cmd, err)
+ }
+ }
}
}
}
+
+func replDump(bf *gbfy.Brainfuck) {
+ d, cells, i, cmds, out := bf.Dump()
+ fmt.Printf("Cells; d: %d, current cell value: %x\n", d, cells[d])
+ fmt.Printf("Cmds: i: %d, current command: %q\n", i, cmds[i-1])
+ fmt.Printf("Out: %v\n", out)
+}
diff --git a/gbfy.go b/gbfy.go
@@ -1,141 +0,0 @@
-package gbfy
-
-import (
- "bytes"
- "errors"
- "fmt"
- "strings"
-)
-
-// Brainfuck is the interpreter state.
-type Brainfuck struct {
- cells [3e4]byte // cells
- d int // data pointer for cells access
- cmds []byte // program being executed
- i int // instruction pointer for cmds access
- loops map[int]int // stores index for matching [ or ]
- in, out *bytes.Buffer // input and output buffers
-}
-
-// New constructs a new Brainfuck interpreter with the given program
-// and input buffer.
-func New(program string, input []byte) (*Brainfuck, error) {
- cmds, loops, err := parseProgram(program)
- if err != nil {
- return nil, err
- }
- return &Brainfuck{
- cmds: cmds,
- loops: loops,
- in: bytes.NewBuffer(input),
- out: new(bytes.Buffer),
- }, nil
-}
-
-// Run the program loaded into the interpreter.
-func (bf *Brainfuck) Run() ([]byte, error) {
- for bf.i < len(bf.cmds) {
- if err := bf.eval(bf.cmds[bf.i]); err != nil {
- return nil, fmt.Errorf("Run failed with error: %v", err)
- }
- bf.i++
- }
- return bf.out.Bytes(), nil
-}
-
-// String dumps the Brainfuck interpreter state for debugging.
-func (bf *Brainfuck) String() string {
- var s strings.Builder
- s.WriteString(fmt.Sprintf("pointers: [d=%d i=%d]\n", bf.d, bf.i))
- s.WriteString("non-zero cells: {\n")
- // TODO: Better cell printing.
- for i, c := range bf.cells {
- if c != 0 {
- s.WriteString(fmt.Sprintf(" %d: %d\n", i, c))
- }
- }
- s.WriteString("}")
- return s.String()
-}
-
-// Reset the interpreter state to defaults.
-func (bf *Brainfuck) Reset() {
- bf.cells = [3e4]byte{}
- bf.i = 0
- bf.d = 0
- bf.cmds = nil
-}
-
-// eval evaluates a single Brainfuck command.
-func (bf *Brainfuck) eval(cmd byte) error {
- switch cmd {
- case '>':
- // Increment data pointer.
- bf.d++
- if bf.d >= len(bf.cells) {
- bf.d -= len(bf.cells)
- }
- case '<':
- // Decrement data pointer.
- bf.d--
- if bf.d < 0 {
- bf.d += len(bf.cells)
- }
- case '+':
- // Increment value at current cell.
- bf.cells[bf.d]++
- case '-':
- // Decrement value at current cell.
- bf.cells[bf.d]--
- case '.':
- // Write current cell's value to output buffer.
- bf.out.WriteByte(bf.cells[bf.d])
- case ',':
- // Read value from input and store in current cell.
- if b, err := bf.in.ReadByte(); err != nil {
- return errors.New("program expects more input")
- } else {
- bf.cells[bf.d] = b
- }
- case '[':
- // Loop start; jump to matching ] if current cell is zero.
- if bf.cells[bf.d] == 0 {
- bf.i = bf.loops[bf.i]
- }
- case ']':
- // Loop end; jump to matching [ if current cell is non-zero.
- if bf.cells[bf.d] != 0 {
- bf.i = bf.loops[bf.i]
- }
- }
- return nil
-}
-
-func parseProgram(program string) ([]byte, map[int]int, error) {
- cmds, opens, loops := []byte{}, []int{}, map[int]int{}
- for _, cmd := range program {
- switch cmd {
- case '[', ']', '<', '>', '+', '-', ',', '.':
- cmds = append(cmds, byte(cmd))
- }
- }
- for i, cmd := range cmds {
- if cmd == '[' {
- opens = append(opens, i)
- } else if cmd == ']' {
- if len(opens) == 0 {
- return nil, nil, fmt.Errorf("mismatched [ at index %d", i)
- }
- // Remove matching [.
- j := opens[len(opens)-1]
- opens = opens[:len(opens)-1]
- // Store mapping.
- loops[i] = j
- loops[j] = i
- }
- }
- if len(opens) > 0 {
- return nil, nil, errors.New("unclosed [ at end of program")
- }
- return cmds, loops, nil
-}
diff --git a/gbfy_test.go b/gbfy_test.go
@@ -1,144 +0,0 @@
-package gbfy
-
-import (
- "fmt"
- "testing"
-
- "github.com/google/go-cmp/cmp"
-)
-
-func TestEval(t *testing.T) {
- tests := []struct {
- // Command to evaluate.
- cmd byte
- // Expected value of Data pointer.
- d int
- // Expected values of *specific* cells; mapping between cell
- // index and value expected there. Since the cell region is
- // large (3e4) and sparse (0 by default) only specific cells
- // are checked.
- cells map[int]byte
- // Expected output data.
- out []byte
- }{
- // Check < and > move data pointer around circular cell region.
- {'<', 29999, nil, nil},
- {'>', 0, nil, nil},
- // Check that + and - modify cell values.
- {'+', 0, map[int]byte{0: 1}, nil},
- {'-', 0, map[int]byte{0: 0}, nil},
- // Check that , and . read input and write output bytes.
- // NB: output is inspected at the very end since the interpreter
- // uses bytes.Buffer.
- {',', 0, map[int]byte{0: 4}, nil},
- {'>', 1, map[int]byte{0: 4}, nil},
- {',', 1, map[int]byte{0: 4, 1: 8}, nil},
- {',', 1, map[int]byte{0: 4, 1: 15}, nil},
- {'>', 2, map[int]byte{0: 4, 1: 15}, nil},
- {',', 2, map[int]byte{0: 4, 1: 15, 2: 16}, nil},
- {'.', 2, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16}},
- {'<', 1, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16}},
- {'.', 1, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15}},
- {'<', 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15}},
- {'.', 0, map[int]byte{0: 4, 1: 15, 2: 16}, []byte{16, 15, 4}},
- // Hmm, we can't really test [ and ] with eval ...
- }
-
- bf, _ := New("", []byte{4, 8, 15, 16, 23, 41})
- if err := checkInterpreter(bf, 0, 0, nil, nil); err != nil {
- t.Fatalf("[0] Unexpected interpreter state: %v", err)
- }
-
- for i, test := range tests {
- if err := bf.eval(test.cmd); err != nil {
- t.Fatalf("[%d] Eval(%q) failed with error: %v", i, test.cmd, err)
- }
- // Note since we called `eval` ourselves rather than `Run`, the instruction
- // pointer is not being used, i.e. is always zero. It's tested separately below.
- if err := checkInterpreter(bf, 0, test.d, test.cells, test.out); err != nil {
- t.Errorf("[%d] Unexpected interpreter state: %v", i, err)
- }
- }
-}
-
-func checkInterpreter(bf *Brainfuck, i, d int, cells map[int]byte, out []byte) error {
- if bf.i != i {
- return fmt.Errorf("instruction pointer; got %d, want %d", bf.i, i)
- }
- if bf.d != d {
- return fmt.Errorf("data pointer; got %d, want %d", bf.d, d)
- }
- for idx, got := range bf.cells {
- if want := cells[idx]; got != want {
- return fmt.Errorf("cell value at index %d; got %b, want %b", idx, got, want)
- }
- }
- if diff := cmp.Diff(out, bf.out.Bytes()); diff != "" {
- return fmt.Errorf("output diff (-want +got): %s", diff)
- }
- return nil
-}
-
-func TestParseProgram(t *testing.T) {
- invalidLoops := []string{"]", "[]]", "[", "[]["}
- for _, test := range invalidLoops {
- _, err := New(test, nil)
- if err == nil {
- t.Errorf("Parsed invalid program %q; expected error", test)
- }
- }
-}
-
-func TestLoops(t *testing.T) {
- // Program computes sum of two adjanct cells, read from input.
- program := ",>,[<+>-]<."
- tests := []struct {
- input, want []byte
- }{
- {[]byte{3, 2}, []byte{5}},
- {[]byte{2, 3}, []byte{5}},
- {[]byte{3, 3}, []byte{6}},
- {[]byte{0, 0}, []byte{0}},
- }
- for _, test := range tests {
- bf, err := New(program, test.input)
- if err != nil {
- t.Fatalf("New failed: %v", err)
- }
- out, err := bf.Run()
- if err != nil {
- t.Fatalf("Run failed: %v", err)
- }
- if diff := cmp.Diff(test.want, out); diff != "" {
- t.Errorf("Mismatched output data (-want +got):\n%s", diff)
- }
- }
-}
-
-func TestHelloWorld(t *testing.T) {
- program := `
- >++++++++[<+++++++++>-]<.
- >++++[<+++++++>-]<+.
- +++++++..
- +++.
- >>++++++[<+++++++>-]<++.
- ------------.
- >++++++[<+++++++++>-]<+.
- <.
- +++.
- ------.
- --------.
- >>>++++[<++++++++>-]<+.`
-
- bf, err := New(program, nil)
- if err != nil {
- t.Fatalf("New failed: %v", err)
- }
- out, err := bf.Run()
- if err != nil {
- t.Fatalf("Run failed: %v", err)
- }
- if diff := cmp.Diff("Hello, World!", string(out)); diff != "" {
- t.Errorf("Mismatched output data (-want +got):\n%s", diff)
- }
-}
