diff options
| -rw-r--r-- | vm1/README.md | 37 | ||||
| -rw-r--r-- | vm1/vm.go | 143 | ||||
| -rw-r--r-- | vm1/vm_test.go | 82 |
3 files changed, 262 insertions, 0 deletions
diff --git a/vm1/README.md b/vm1/README.md new file mode 100644 index 0000000..d95ec46 --- /dev/null +++ b/vm1/README.md @@ -0,0 +1,37 @@ +# vm1 + +`vm1` is bytecode based stack machine. + +The purpose of `vm1` is to provide a simple, fast, embeddable and +portable Go execution environment. + +```mermaid +graph LR +s:::hidden --> |source| a(scanner) +--> |tokens| b(parser) +--> |AST| c(codegen) +--> |bytecode| d[vm] +subgraph vm1 + d +end +``` + +The bytecode consists of a dozen of instructions, each taking 0 or 1 +immediate argument (non-immediate arguments are only passed through the +stack). Only a few operators for a few types are implemented. I expect +to have 1 instruction per operator per numerical type, all with the same +pattern, which would be generated from a template. Estimate is around 20 +operators and 10 numerical types, so around 200 instructions in final. + +Structurally, the vm implements logical and arithmetic operators, +condional jumps for `if`, `for` and `switch` control flow, and function +call, return and frame management. + +the memory state of the vm is a slice of Go interfaces (`[]any`). + +The whole vm is coded in a single function of 80 lines with no +dependencies. The size will grow as we add missing instructions, but the +code complexity will remain the same. + +the vm1 package is totally standalone and could be used for any purpose +outside of parscan and/or gno. diff --git a/vm1/vm.go b/vm1/vm.go new file mode 100644 index 0000000..5cea5cf --- /dev/null +++ b/vm1/vm.go @@ -0,0 +1,143 @@ +package vm1 + +import ( + "fmt" // for tracing only + "reflect" // for optional CallX only + "strconv" // for tracing only +) + +// Byte-code instruction set. +const ( + // instruction effect on stack: values consumed -- values produced + Nop = iota // -- + Add // n1 n2 -- sum ; sum = n1+n2 + Assign // addr val -- ; mem[addr] = val + Call // f [a1 .. ai] -- [r1 .. rj] ; r1, ... = prog[f](a1, ...) + CallX // f [a1 .. ai] -- [r1 .. rj] ; r1, ... = mem[f](a1, ...) + Dup // addr -- value ; value = mem[addr] + Fdup // addr -- value ; value = mem[addr] + Enter // -- ; enter frame: push(fp), fp = sp + Exit // -- ; + Jump // -- ; ip += $1 + JumpTrue // cond -- ; if cond { ip += $1 } + Lower // n1 n2 -- cond ; cond = n1 < n2 + Pop // v -- + Push // -- v + Return // [r1 .. ri] -- ; exit frame: sp = fp, fp = pop + Sub // n1 n2 -- diff ; diff = n1 - n2 +) + +var strop = [...]string{ // for VM tracing. + Nop: "Nop", + Add: "Add", + Assign: "Assign", + Call: "Call", + CallX: "CallX", + Dup: "Dup", + Fdup: "Fdup", + Enter: "Enter", + Exit: "Exit", + Jump: "Jump", + JumpTrue: "JumpTrue", + Lower: "Lower", + Pop: "Pop", + Push: "Push", + Return: "Return", + Sub: "Sub", +} + +// Machine represents a virtual machine. +type Machine struct { + code [][]int64 // code to execute + mem []any // memory, as a stack + ip, fp int // instruction and frame pointer + // flags uint // to set debug mode, restrict CallX, etc... +} + +// Run runs a program. +func (m *Machine) Run() { + code, mem, ip, fp, sp := m.code, m.mem, m.ip, m.fp, 0 + + defer func() { m.mem, m.ip, m.fp = mem, ip, fp }() + + trace := func() { + var op1 string + if len(code[ip]) > 1 { + op1 = strconv.Itoa(int(code[ip][1])) + } + fmt.Printf("ip:%-4d sp:%-4d fp:%-4d op:[%-8s %-4s] mem:%v\n", ip, sp, fp, strop[code[ip][0]], op1, mem) + } + _ = trace + + for { + sp = len(mem) // stack pointer + trace() + switch op := code[ip]; op[0] { // TODO: op[0] will contain file pos ? + case Add: + mem[sp-2] = mem[sp-2].(int) + mem[sp-1].(int) + mem = mem[:sp-1] + case Assign: + mem[mem[sp-2].(int)] = mem[sp-1] + mem = mem[:sp-1] + case Call: + mem = append(mem, ip+1) + ip += int(op[1]) + continue + case CallX: // Should be made optional. + in := make([]reflect.Value, int(op[1])) + for i := range in { + in[i] = reflect.ValueOf(mem[sp-1-i]) + } + f := reflect.ValueOf(mem[sp-len(in)-1]) + mem = mem[:sp-len(in)-1] + for _, v := range f.Call(in) { + mem = append(mem, v.Interface()) + } + case Dup: + mem = append(mem, mem[int(op[1])]) + case Enter: + mem = append(mem, fp) + fp = sp + 1 + case Exit: + return + case Fdup: + mem = append(mem, mem[int(op[1])+fp-1]) + case Jump: + ip += int(op[1]) + continue + case JumpTrue: + cond := mem[sp-1].(bool) + mem = mem[:sp-1] + if cond { + ip += int(op[1]) + continue + } + case Lower: + mem[sp-2] = mem[sp-2].(int) < mem[sp-1].(int) + mem = mem[:sp-1] + case Pop: + mem = mem[:sp-1] + case Push: + mem = append(mem, int(op[1])) + case Return: + ip = mem[fp-2].(int) + ofp := fp + fp = mem[fp-1].(int) + mem = append(mem[:ofp-int(op[1])-2], mem[sp-int(op[1]):]...) + continue + case Sub: + mem[sp-2] = mem[sp-2].(int) - mem[sp-1].(int) + mem = mem[:sp-1] + } + ip++ + } +} + +func (m *Machine) PushCode(code [][]int64) (p int) { + p = len(m.code) + m.code = append(m.code, code...) + return +} +func (m *Machine) SetIP(ip int) { m.ip = ip } +func (m *Machine) Push(v any) (l int) { l = len(m.mem); m.mem = append(m.mem, v); return } +func (m *Machine) Pop() (v any) { l := len(m.mem) - 1; v = m.mem[l]; m.mem = m.mem[:l]; return } diff --git a/vm1/vm_test.go b/vm1/vm_test.go new file mode 100644 index 0000000..33ace00 --- /dev/null +++ b/vm1/vm_test.go @@ -0,0 +1,82 @@ +package vm1 + +import ( + "fmt" + "testing" +) + +func TestVM(t *testing.T) { + for _, test := range tests { + t.Run("", func(t *testing.T) { + m := &Machine{} + for _, v := range test.sym { + m.Push(v) + } + m.PushCode(test.code) + m.Run() + t.Log(m.mem) + r := fmt.Sprintf("%v", m.mem[test.start:test.end]) + if r != test.mem { + t.Errorf("got %v, want %v", r, test.mem) + } + }) + } +} + +var tests = []struct { + sym []any // initial memory values + code [][]int64 // bytecode to execute + start, end int // + mem string // expected memory content +}{{ // #00 -- A simple addition. + code: [][]int64{ + {Push, 1}, + {Push, 2}, + {Add}, + {Exit}, + }, + start: 0, end: 1, mem: "[3]", +}, { // #01 -- Calling a function defined outside the VM. + sym: []any{fmt.Println, "Hello"}, + code: [][]int64{ + {CallX, 1}, + {Exit}, + }, + start: 0, end: 2, mem: "[6 <nil>]", +}, { // #02 -- Defining and calling a function in VM. + code: [][]int64{ + {Jump, 4}, // 0 + {Enter}, // 1 + {Push, 3}, // 2 + {Return, 1}, // 3 + {Push, 1}, // 4 + {Call, -4}, // 5 + {Exit}, // 6 + }, + start: 0, end: 1, mem: "[3]", +}, { // #03 -- Fibonacci numbers, hand written. Showcase recursivity. + code: [][]int64{ + {Jump, 18}, // 0, goto 18 + {Enter}, // 1, + {Fdup, -2}, // 2, [i] + {Push, 2}, // 3, [i 2] + {Lower}, // 4, [true/false] + {JumpTrue, 11}, // 5, [], goto 16 + {Fdup, -2}, // 6 [i] + {Push, 2}, // 7 [i 2] + {Sub}, // 8 [(i-2)] + {Call, -8}, // 9 [fib(i-2)] + {Fdup, -2}, // 10 [fib(i-2) i] + {Push, 1}, // 11 [(i-2) i 1] + {Sub}, // 12 [(i-2) (i-1)] + {Call, -12}, // 13 [fib(i-2) fib(i-1)] + {Add}, // 14 [fib(i-2)+fib(i-1)] + {Return, 1}, // 15 return i + {Fdup, -2}, // 16 [i] + {Return, 1}, // 17 return i + {Push, 6}, // 18 [1] + {Call, -18}, // 19 [fib(*1)] + {Exit}, // 20 + }, + start: 0, end: 1, mem: "[8]", +}} |