2.4. Kink Stack Machine (KSM)

This chapter provides the specification of Kink Stack Machine (KSM), which is an imaginary stack machine to explain the behavior of functions made from Kink programs. The translation from Kink programs into KSM procedures is given in Semantics chapter.

The runtime do not have to provide direct implementations of KSM, but it must behave as if KSM works.

2.4.1. Concepts

Instructions

An instruction consists of a mnemonic and at most one operand. Each instruction represents an operation to the current value stack. If the mnemonic is foo and the operand is Bar, the instruction is written as foo Bar. If the mnemonic is baz and it takes no operand, the instruction is written as baz.

Semicolons can be placed optionally after instructions, such as foo Bar; and baz;.

Procedures

A procedure is a unit of processing comprised of a series of one or more instructions. A procedure is written enclosing the series of instructions by { and }.

For example, a procedure comprised of instructions foo, bar Baz and qux is written as { foo; bar Baz; qux }.

The syntax accepts inline comments headed by #.

Registers

Registers are data used in a run of the procedure.

Register Description
procedure the procedure
program counter the zero based index of a instruction of the procedure
context environment \env
context receiver \recv
context arguments vector the source of \args
value stack the stack of values used in the run.

Value stacks

The value stack is one of the registers of the run.

Values can be pushed to and popped from the value stack. When values a, b and c are pushed to the value stack, a will be the third topmost value, b will be the second topmost value, and c will be the topmost value. When values d, e, f are popped from the value stack, first the evaluator checks that the value stack contains enough values (in this case 3 values), then d is taken from the third topmost value, e is taken from the second topmost value, and f is taken from the topmost value.

Runs

A run starts by invoke operation, or continue operation for a KSM snapshot frame. If there is not enough resource to start the run, an exception is raised.

The run proceedes as the following.

  • Fetches the instruction at the program counter, and executes it.
  • Increments the program counter if the run does not end in the execution of the instruction.
  • If the program counter is equal to the length of the procedure, the run ends and continue operation is performed with the topmost value of the value stack for the executor.
  • Goes back to the first line.

Checks

When this chapter writes “checks that ...,” the specified condition is tested. If the condition turns out to be false, an exception is raised.

Exceptions

An exception might be raised during the run.

If so, the run ends and the exception is raised in the executor.

2.4.2. Instructions

num Num

Pop:
Push:num

The instruction takes an integer token or a decimal token as the operand.

The instruction pushes a num val which represents the number.

str Str

Pop:
Push:str

The instruction takes a string token as the operand.

The instruction pushes a str val which represents the string.

nada

Pop:
Push:()

The instruction pushes the value () (nada).

emptyvec

Pop:
Push:vec

The instruction pushes a new empty vector.

add

Pop:vec element
Push:newvec

The instruction pops two values vec and element, then checks that vec is a vector value

The instruction pushes a new vector which contains all the elements of vec, and element as the last element.

concat

Pop:first, second
Push:newvec

The instruction pops two values first and second, and checks that both values are vector values.

Finally, the value pushes a new vector concatenating the two vectors first and second in the order.

dup

Pop:value
Push:value, value

The instruction pops a value, and puts the value twice.

flip

Pop:a, b
Push:b, a

The instruction pops two values, and pushes the values flipping the order.

remove

Pop:value
Push:

The instruction pops a value.

env

Pop:
Push:contextenv

The instruction pushes the context environment.

recv

Pop:
Push:contextrecv

The instruction pushes the context receiver.

args

Pop:
Push:contextargs

The instruction pushes a new vector copying the context arguments vector.

arg Index

Pop:
Push:contextarg

The instruction takes an integer token as the operand, which represents the index of the argument.

The instruction checks that the the context arguments vector contains an element corresponding to the index. And then it pushes the element.

varref Symbol

Pop:owner
Push:varref

The instruction takes a symbol token as the operand.

The instruction pops a value owner. And then it pushes a variable reference or a varref whose owner is owner and with the symbol.

deref Symbol

Pop:owner
Push:target

The instruction takes a symbol token as the operand.

The instruction pops a value owner. It checks that the the variable (owner, Symbol) is nonempty. And then it pushes the target of the variable.

fun Procedure

Pop:enclosingenv
Push:fun

The instruction takes a procedure as the operand.

The instruction pops a value enclosingenv. And then it pushes a function value made with the procedure. This function is said to be an enclosed function.

When an executor invokes the function, a KSM procedure run starts with the following registers.

Register Data
procedure the operand Procedure
program counter 0
context environment a new env value which copies all the variables of enclosingenv
context receiver the actual receiver passed to the invocation
context arguments vector the actual arguments apssed to the invocation
value stack a new empty value stack

call

Pop:fun, recv, args
Push:∅ (the result of the function is pushed when the run is continued)

The instruction pops values fun, recv, and args. It checks that fun is a function value, and args is a vector value.

If the instruction is not at the end of the procedure, it pushes a KSM snapshot frame with the following attributes.

Frame attribute Data
procedure the current procedure
program counter the current program counter + 1
context environment the current context environment
context receiver the current context receiver
context arguments vector the current context arguments vector
value stack the current value stack

And then, whether the instruction is at the end or not, the current KSM procedure run ends and invoke operation is performed on the executor with the following operands.

Operand Data
callee fun
receiver recv
arguments vector args
symbol the symbol of the calling, if available
location the location of the calling, if available

2.4.3. Top level functions

When a program text is compiled by kink/PROGRAM.compile, the function makes a function with the procedure translated from the program. It is said to be a top level function.

When an executor invokes the top level function, it is checked that the size of the argument vector is 1, and the only argument is an env value. Then a KSM procedure run starts with the following registers.

Register Data
procedure the procedure translated from the program
program counter 0
context environment the env value given as the argument of the invocation
context receiver nada
context arguments vector a new empty vector
value stack a new empty value stack