vm

package
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Aug 14, 2016 License: Apache-2.0 Imports: 9 Imported by: 4

Documentation

Overview

Package vm provides an Ngaro Virtual Machine implementation.

Please visit http://forthworks.com/retro/ to get you started about the Retro language and the Ngaro Virtual Machine.

The main purpose of this implementation is to allow customization and communication between Retro programs and Go programs via custom I/O handlers (i.e. scripting Go programs in Retro) as well as supporting custom opcodes at the VM level. The package examples demonstrate various use cases. For more details on I/O handling in the Ngaro VM, please refer to http://retroforth.org/docs/The_Ngaro_Virtual_Machine.html.

This implementation passes all tests from the retro-language test suite and its performance when running tests/core.rx is slightly better than with the reference implementations:

1.20s for this implementation, compiled with Go 1.7rc6.
1.30s for the reference Go implementation, compiled with Go 1.7rc6
2.22s for the reference C implementation, compiled with gcc-5.4 -O3 -fomit-frame-pointer

For all intents and purposes, the VM behaves according to the specification. With one exception: if you implement custom opcodes, be aware that for performance reasons, the PC (aka. Instruction Pointer) is not incremented in a single place; rather each opcode deals with the PC as needed. Users of custom opcodes will need to take care of updating the PC accordingly. This should be of no concern to other users, even with custom I/O handlers. Should you find that the VM does not behave according to the spec, please file a bug report.

There's a caveat common to all Ngaro implementations: use of IN, OUT and WAIT from the listener (the Retro interactive prompt) will not work as expected. This is because the listener uses the same mechanism to read user input and write to the terminal and will clear port 0 before you get a chance to read/clear response values. This is of particular importance for users of custom IO handlers. To work around this issue, a synchronous OUT-WAIT-IN IO sequence must be compiled in a word, so that it will run atomically without interference from the listener. For example, to read VM capabilities, you can do this:

( io sends value n to port p, does a wait and puts response back on the stack )
: io ( np-n ) dup push out 0 0 out wait pop in ;

-1 5 io putn

should give you the size of the image.

Regarding I/O, reading console width and height will only work if the io.Writer set as output with vm.Output implements the Fd method. So this will only work if the output is os.Stdout or a pty (and NOT wrapped in a bufio.Writer).

TODO:

  • asm: macro assembler?
  • asm: symbolic image? i.e. generate images with symbol references.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Cell

type Cell int32

Cell is the raw type stored in a memory location.

const (
	OpNop Cell = iota
	OpLit
	OpDup
	OpDrop
	OpSwap
	OpPush
	OpPop
	OpLoop
	OpJump
	OpReturn
	OpGtJump
	OpLtJump
	OpNeJump
	OpEqJump
	OpFetch
	OpStore
	OpAdd
	OpSub
	OpMul
	OpDimod
	OpAnd
	OpOr
	OpXor
	OpShl
	OpShr
	OpZeroExit
	OpInc
	OpDec
	OpIn
	OpOut
	OpWait
)

Ngaro Virtual Machine Opcodes.

type Image

type Image []Cell

Image encapsulates a VM's memory

func Load

func Load(fileName string, minSize int) (i Image, fileCells int, err error)

Load loads an image from file fileName. Returns a VM Image ready to run, the actual number of cells read from the file and any error.

The returned Image should have its length equal equal to the maximum of the requested minimum size and the image file size + 1024 free cells.

func (Image) DecodeString

func (i Image) DecodeString(start Cell) string

DecodeString returns the string starting at position start in the image. Strings stored in the image must be zero terminated. The trailing '\0' is not returned.

func (Image) EncodeString

func (i Image) EncodeString(start Cell, s string)

EncodeString writes the given string at position start in the Image and terminates it with a '\0' Cell.

func (Image) Save

func (i Image) Save(fileName string, shrink bool) error

Save saves the image. If the shrink parameter is true, only the portion of the image from offset 0 to HERE will be saved.

type InHandler

type InHandler func(i *Instance, port Cell) error

InHandler is the function prototype for custom IN handlers.

type Instance

type Instance struct {
	PC    int    // Program Counter (aka. Instruction Pointer)
	Image Image  // Memory image
	Ports []Cell // I/O ports
	Tos   Cell   // cell on top of stack
	// contains filtered or unexported fields
}

Instance represents an Ngaro VM instance.

func New

func New(image Image, imageFile string, opts ...Option) (*Instance, error)

New creates a new Ngaro Virtual Machine instance.

The image parameter is the Cell array used as memory by the VM.

The imageFile parameter is the fileName that will be used to dump the contents of the memory image. It does not have to exist or even be writable as long as no user program requests an image dump.

Options will be set by calling SetOptions.

func (*Instance) Address

func (i *Instance) Address() []Cell

Address returns the address stack. Note that value changes will be reflected in the instance's stack, but re-slicing will not affect it. To add/remove values on the address stack, use the Rpush and Rpop functions.

func (*Instance) Data

func (i *Instance) Data() []Cell

Data returns the data stack. Note that value changes will be reflected in the instance's stack, but re-slicing will not affect it. To add/remove values on the data stack, use the Push and Pop functions.

func (*Instance) Depth

func (i *Instance) Depth() int

Depth returns the data stack depth.

func (*Instance) Drop

func (i *Instance) Drop()

Drop removes the top item from the data stack.

func (*Instance) Drop2

func (i *Instance) Drop2()

Drop2 removes the top two items from the data stack.

func (*Instance) In

func (i *Instance) In(port Cell) error

In is the default IN handler for all ports.

func (*Instance) InstructionCount

func (i *Instance) InstructionCount() int64

InstructionCount returns the number of instructions executed so far.

func (*Instance) Out

func (i *Instance) Out(v, port Cell) error

Out is the default OUT handler for all ports.

func (*Instance) Pop

func (i *Instance) Pop() Cell

Pop pops the value on top of the data stack and returns it.

func (*Instance) Push

func (i *Instance) Push(v Cell)

Push pushes the argument on top of the data stack.

func (*Instance) PushInput

func (i *Instance) PushInput(r io.Reader)

PushInput sets r as the current input RuneReader for the VM. When this reader reaches EOF, the previously pushed reader will be used.

func (*Instance) Rpop

func (i *Instance) Rpop() Cell

Rpop pops the value on top of the address stack and returns it.

func (*Instance) Rpush

func (i *Instance) Rpush(v Cell)

Rpush pushes the argument on top of the address stack.

func (*Instance) Run

func (i *Instance) Run() (err error)

Run starts execution of the VM.

If an error occurs, the PC will will point to the instruction that triggered the error.

If the VM was exited cleanly from a user program with the `bye` word, the PC will be equal to len(i.Image) and err will be nil.

If the last input stream gets closed, the VM will exit and return io.EOF. This is a normal exit condition in most use cases.

Example

Shows how to load an image, setup the VM with multiple readers/init code.

package main

import (
	"bytes"
	"fmt"
	"os"
	"strings"

	"github.com/db47h/ngaro/vm"
)

func main() {
	imageFile := "testdata/retroImage"
	img, _, err := vm.Load(imageFile, 50000)
	if err != nil {
		panic(err)
	}

	// output capture buffer
	output := bytes.NewBuffer(nil)

	// Setup the VM instance with os.Stdin as first reader, and we push another
	// reader with some custom init code that will include and run the retro core tests.
	i, err := vm.New(img, imageFile,
		vm.Input(os.Stdin),
		vm.Input(strings.NewReader("\"testdata/core.rx\" :include\n")),
		vm.Output(vm.NewVT100Terminal(output, nil, nil)))

	// run it
	if err == nil {
		err = i.Run()
	}
	if err != nil {
		// in interactive use, err may be io.EOF if any of the IO channels gets closed
		// in which case this would be a normal exit condition
		panic(err)
	}

	// filter output to get the retro core test results.
	b := bytes.Split(output.Bytes(), []byte{'\n'})
	fmt.Printf("%s\n", b[len(b)-5])
	fmt.Printf("%s\n", b[len(b)-4])

}
Output:

360 tests run: 360 passed, 0 failed.
186 words checked, 0 words unchecked, 37 i/o words ignored.

func (*Instance) SetOptions

func (i *Instance) SetOptions(opts ...Option) error

SetOptions sets the provided options.

func (*Instance) Wait

func (i *Instance) Wait(v, port Cell) error

Wait is the default WAIT handler bound to ports 1, 2, 4, 5 and 8. It can be called manually by custom handlers that override default behaviour.

func (*Instance) WaitReply

func (i *Instance) WaitReply(v, port Cell)

WaitReply writes the value v to the given port and sets port 0 to 1. This should only be used by WAIT port handlers.

type OpcodeHandler

type OpcodeHandler func(i *Instance, opcode Cell) error

OpcodeHandler is the prototype for opcode handler functions. When an opcode handler is called, the VM's PC points to the opcode. Opcode handlers must take care of updating the VM's PC.

type Option

type Option func(*Instance) error

Option interface

func AddressSize

func AddressSize(size int) Option

AddressSize sets the address stack size. It will not erase the stack, but data nay be lost if set to a smaller size. The default is 1024 cells.

func BindInHandler

func BindInHandler(port Cell, handler InHandler) Option

BindInHandler binds the porvided IN handler to the given port.

The default IN handler behaves according to the specification: it reads the corresponding port value from Ports[port] and pushes it to the data stack. After reading, the value of Ports[port] is reset to 0.

Custom hamdlers do not strictly need to interract with Ports field. It is however recommended that they behave the same as the default.

func BindOpcodeHandler

func BindOpcodeHandler(handler OpcodeHandler) Option

BindOpcodeHandler binds the given function to handle custom opcodes (i.e. opcodes with a negative value).

When an opcode handler is called, the VM's PC points to the opcode. Opcode handlers must take care of updating the VM's PC.

Example

Demonstrates how to use custom opcodes. This example defines a custom opcode that pushes the n-th fibonacci number onto the stack.

package main

import (
	"fmt"
	"strings"

	"github.com/db47h/ngaro/asm"
	"github.com/db47h/ngaro/vm"
)

func main() {
	fib := func(v vm.Cell) vm.Cell {
		var v0, v1 vm.Cell = 0, 1
		for v > 1 {
			v0, v1 = v1, v0+v1
			v--
		}
		return v1
	}

	handler := func(i *vm.Instance, opcode vm.Cell) error {
		switch opcode {
		case -1:
			i.Tos = fib(i.Tos)
			i.PC++ // DO NOT FORGET !
			return nil
		default:
			return fmt.Errorf("Unsupported opcode value %d", opcode)
		}
	}

	img, err := asm.Assemble("test_fib_opcode", strings.NewReader(`
		.opcode fib -1
		46 fib
		`))
	if err != nil {
		panic(err)
	}

	i, err := vm.New(img, "dummy", vm.BindOpcodeHandler(handler))
	if err != nil {
		panic(err)
	}

	err = i.Run()
	if err != nil {
		panic(err)
	}

	// So, what's Fib(46)?
	fmt.Println(i.Data())

}
Output:

[1836311903]

func BindOutHandler

func BindOutHandler(port Cell, handler OutHandler) Option

BindOutHandler binds the porvided OUT handler to the given port.

The default OUT handler just stores the given value in Ports[port]. A common use of OutHandler when using buffered I/O is to flush the output writer when anything is written to port 3. Such handler just ignores the written value, leaving Ports[3] as is.

Example

Shows a common use of OUT port handlers.

package main

import (
	"fmt"
	"io"
	"os"
	"strings"

	"github.com/db47h/ngaro/vm"
)

func main() {
	imageFile := "testdata/retroImage"
	img, _, err := vm.Load(imageFile, 0)
	if err != nil {
		panic(err)
	}

	// Our out handler, will just take the written value, and return its square.
	// The result will be stored in the bound port, so we can read it back with
	// IN.
	outputHandler := func(i *vm.Instance, v, port vm.Cell) error {
		i.Ports[port] = v * v
		return nil
	}
	// Create the VM instance with our port handler bound to port 42.
	// We do not wire any output, we'll just read the results from the stack.
	i, err := vm.New(img, imageFile,
		vm.Input(strings.NewReader(": square 42 out 42 in ; 7 square bye\n")),
		vm.BindOutHandler(42, outputHandler))
	if err != nil {
		panic(err)
	}

	if err = i.Run(); err != nil && err != io.EOF {
		fmt.Fprintf(os.Stderr, "%v\n", err)
	}

	fmt.Println(i.Data())

}
Output:

[49]

func BindWaitHandler

func BindWaitHandler(port Cell, handler WaitHandler) Option

BindWaitHandler binds the porvided WAIT handler to the given port.

WAIT handlers are called only if the value the following conditions are both true:

  • the value of the bound I/O port is not 0
  • the value of I/O port 0 is not 1

Upon completion, a WAIT handler should call the WaitReply method which will set the value of the bound port and set the value of port 0 to 1.

Example

A simple WAIT handler that overrides the default implementation. It's used here to implement a (dummy) canvas. We'll need to override port 5 in order to report canvas availability and its size and implement the actual drawing on port 6. See http://retroforth.org/docs/The_Ngaro_Virtual_Machine.html

package main

import (
	"fmt"
	"io"
	"os"
	"strings"

	"github.com/db47h/ngaro/vm"
)

func main() {
	imageFile := "testdata/retroImage"
	img, _, err := vm.Load(imageFile, 50000)
	if err != nil {
		panic(err)
	}

	waitHandler := func(i *vm.Instance, v, port vm.Cell) error {
		switch port {
		case 5: // override VM capabilities
			switch v {
			case -2:
				i.WaitReply(-1, port)
			case -3:
				i.WaitReply(1920, port)
			case -4:
				i.WaitReply(1080, port)
			default:
				// not a value that we handle ourselves, hand over the request
				// to the default implementaion
				return i.Wait(v, port)
			}
			return nil
		case 6: // implement the canvas
			switch v {
			case 1:
				/* color */ _ = i.Pop()
			case 2:
				/* y */ _ = i.Pop()
				/* x */ _ = i.Pop()
				// draw a pixel at x, y...
			case 3:
				// more to implement...
			}
			// complete the request
			i.WaitReply(0, port)
		}
		return nil
	}

	// no output set as we don't care.
	// out program first requests the VM size just to check that our override of
	// port 5 properly hands over unknown requests to the default implementation.
	i, err := vm.New(img, imageFile,
		vm.Input(strings.NewReader(
			": cap ( n-n ) 5 out 0 0 out wait 5 in ;\n"+
				"-1 cap -2 cap -3 cap -4 cap bye\n")),
		vm.BindWaitHandler(5, waitHandler),
		vm.BindWaitHandler(6, waitHandler))
	if err != nil {
		panic(err)
	}

	if err = i.Run(); err != nil && err != io.EOF {
		fmt.Fprintf(os.Stderr, "%+v\n", err)
	}

	fmt.Println(i.Data())

}
Output:

[50000 -1 1920 1080]
Example (Async)

A more complex example of WAIT port handlers to communicate with Go. In this example, we use a pair of handlers: a request handler that will initiate a backround job, and a result handler to query and wait for the result.

package main

import (
	"fmt"
	"io"
	"os"
	"strings"

	"github.com/db47h/ngaro/vm"
)

func main() {
	imageFile := "testdata/retroImage"
	img, _, err := vm.Load(imageFile, 0)
	if err != nil {
		panic(err)
	}

	// we use a channel map to associate a task ID with a Go channel.
	channels := make(map[vm.Cell]chan vm.Cell)

	// our background task.
	fib := func(v vm.Cell, c chan<- vm.Cell) {
		var v0, v1 vm.Cell = 0, 1
		for v > 1 {
			v0, v1 = v1, v0+v1
			v--
		}
		c <- v1
	}

	// The request hqndler will be bound to port 1000. Write 1 to this port with
	// any arguments on the stack, then do a WAIT.
	// It will respond on the same channel with a task ID.
	execHandler := func(i *vm.Instance, v, port vm.Cell) error {
		// find an unused job id
		idx := vm.Cell(len(channels)) + 1
		// make i/o channel and save it
		c := make(chan vm.Cell)
		channels[idx] = c
		// launch job
		go fib(i.Pop(), c)
		// respond with channel ID
		i.WaitReply(idx, port)
		return nil
	}

	// The result handler will be wired to port 1001. Write the job id to this
	// port followed by a wait and get the result with:
	//
	//	1001 IN
	resultHandler := func(i *vm.Instance, v, port vm.Cell) error {
		c := channels[v]
		if c == nil {
			// no such channel. No need to error: if we do not reply, port 0
			// will be 0, so client code should check port 0 as well.
			return nil
		}
		i.WaitReply(<-c, port)
		delete(channels, v)
		return nil
	}

	// No output, we'll just grab the values from the stack on exit. Note that
	// the port communication MUST be compiled in words (here fibGo and fibGet).
	// Issuing IN/OUT/WAIT from the listener would fail because of interference
	// from the I/O code.
	i, err := vm.New(img, imageFile,
		vm.Input(strings.NewReader(
			`: fibGo ( n-ID ) 1 1000 out 0 0 out wait 1000 in ;
			 : fibGet ( ID-n ) 1001 out 0 0 out wait 1001 in ;
			 46 fibGo fibGet bye `)),
		vm.BindWaitHandler(1000, execHandler),
		vm.BindWaitHandler(1001, resultHandler))
	if err != nil {
		panic(err)
	}

	if err = i.Run(); err != nil && err != io.EOF {
		fmt.Fprintf(os.Stderr, "%+v\n", err)
	}

	// So, what's Fib(46)?
	fmt.Println(i.Data())

}
Output:

[1836311903]

func DataSize

func DataSize(size int) Option

DataSize sets the data stack size. It will not erase the stack, but data nay be lost if set to a smaller size. The default is 1024 cells.

func Input

func Input(r io.Reader) Option

Input pushes the given RuneReader on top of the input stack.

func Output

func Output(t Terminal) Option

Output configures the output Terminal. For simple I/O, the helper function NewVT100Terminal will build a Terminal wrapper around an io.Writer.

func Shrink

func Shrink(shrink bool) Option

Shrink enables or disables image shrinking when saving it. The default is false.

type OutHandler

type OutHandler func(i *Instance, v, port Cell) error

OutHandler is the function prototype for custom OUT handlers.

type Terminal

type Terminal interface {
	io.Writer
	Flush() error
	Size() (width int, height int)
	Clear()
	MoveCursor(x, y int)
	FgColor(fg int)
	BgColor(bg int)
	Port8Enabled() bool
}

Terminal encapsulates methods provided by a terminal output. Apart from WriteRune, all methods can be implemented as no-ops if the underlying output does not support the corresponding functionality.

WriteRune writes a single Unicode code point, returning the number of bytes written and any error.

Flush writes any buffered unwritten output.

Size returns the width and height of the terminal window. Should return 0, 0 if unsupported.

Clear clears the terminal window and moves the cursor to the top left.

MoveCursor moves the cursor to the specified column and row.

FgColor and BgColor respectively set the foreground and background color of all characters subsequently written.

Port8Enabled should return true if the MoveCursor, FgColor and BgColor methods have any effect.

func NewVT100Terminal

func NewVT100Terminal(w io.Writer, flush func() error, size func() (width int, height int)) Terminal

NewVT100Terminal returns a new Terminal implementation that uses VT100 escape sequences to implement the Clear, CusrosrPos, FgColor and BgColor methods.

The caller only needs to provide the functions implementing Flush and Size. Either of these functions may be nil, in which case they will be implemented as no-ops.

type WaitHandler

type WaitHandler func(i *Instance, v, port Cell) error

WaitHandler is the function prototype for custom WAIT handlers.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL