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 Kink programs. The translation from Kink programs into KSM procedures is given in Semantics chapter.

Interpreters do not have to provide direct implementations of KSM, but they must behave as if KSM works.

2.4.1. Concepts

Evaluators

KSM consists of multiple evaluators each of which corresponds to a thread.

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 #.

Processing of procedures

Evaluators process procedures.

Each processing is performed with a collection of threee values: the context environment, the context receiver, and the context argument list.

When an evaluator processes a procedure, the evaluator executes instructions in the procedure in the order they appear.

Each processing is furnished with a value stack as a work space. 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.

When an instruction is executed, it pops zero or more values from the value stack, and at the end of the execution, pushes zero or more values to the value stack.

On the end of the processing of a procedure, the evaluator checks that the value stack contains one or more values. If the check succeeds, the topmost value becomes the result of the processing.

Checks

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

Exceptions

An exception might occur during the processing. If so, the process terminates with the exception, leaving the remaining instructions not executed,

2.4.2. Instructions

2.4.2.1. num Num

Pop:(none)
Push:num

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

The instruction pushes a number value which represents the number.

2.4.2.2. str Str

Pop:(none)
Push:str

The instruction takes a string token as the operand.

The instruction pushes a string value which represents the string.

2.4.2.3. base

Pop:(none)
Push:base

The instruction pushes the base value.

2.4.2.4. emptylist

Pop:(none)
Push:list

The instruction pushes a new empty list.

2.4.2.5. add

Pop:list element
Push:newlist

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

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

2.4.2.6. concat

Pop:first, second
Push:newlist

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

Finally, the value pushes a new list concatenating the two lists first and second in the order.

2.4.2.7. dup

Pop:value
Push:value, value

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

2.4.2.8. flip

Pop:a, b
Push:b, a

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

2.4.2.9. remove

Pop:value
Push:(none)

The instruction pops a value.

2.4.2.10. env

Pop:(none)
Push:contextenv

The instruction pushes the context environment.

2.4.2.11. recv

Pop:(none)
Push:contextrecv

The instruction pushes the context receiver.

2.4.2.12. args

Pop:(none)
Push:contextargs

The instruction pushes a new list cloning the context argument list.

2.4.2.13. arg Index

Pop:(none)
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 argument lists contains an element corresponding to the index. And then it pushes the element.

2.4.2.14. 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 whose owner is owner and with the symbol.

2.4.2.15. deref Symbol

Pop:owner
Push:target

The instruction takes a symbol token as the operand.

The instruction pops a value owner. It dereferences the variable of owner with the symbol.

2.4.2.16. 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 made from the procedure, and enclosingenv as the enclosing environment.

The function, when called, makes the evaluator process the procedure, with the context environment which is a new child of the enclosing environment, the context receiver which is passed to the call as the receiver, and the context argument list which is passed to the call as the argument list. And then it returns the result of the processing as the result of the function call.

2.4.2.17. call

Pop:recv, args, fun
Push:result

The instruction pops values recv, args and fun. It checks that fun is a function value, and args is a list value. And then it calls fun with recv as the receiver, and args as the argument list.

If the instruction is the last instruction of the procedure, the function is called by a tail call.

2.4.3. Example

This section provides an example of the translation from a Kink program to a KSM procedure.

The Kink program:

:List = [10 20 30]
List.loop{ print_line(\0) }

The KSM procedure translated from the above program:

{
    env             # (env)
    varref List     # (:List)
    dup             # (:List :List)
    emptylist       # (:List :List [])
    emptylist       # (:List :List [] [])
    num 10          # (:List :List [] [] 10)
    add             # (:List :List [] [10])
    num 20          # (:List :List [] [10] 20)
    add             # (:List :List [] [10 20])
    num 30          # (:List :List [] [10 20] 30)
    add             # (:List :List [] [10 20 30])
    add             # (:List :List [[10 20 30]])
    flip            # (:List [[10 20 30]] :List)
    deref op_set    # (:List [[10 20 30]] $op_set)
    call            # (result-of-$op_set)
    remove          # ()
    env             # (env)
    deref List      # (List)
    dup             # (List List)
    emptylist       # (List List [])
    env             # (List List [] env)
    fun {
        env
        dup
        emptylist
        arg 0
        add
        flip
        deref print_line
        call   # this is a tail call
    }               # (List List [] fun)
    add             # (List List [fun])
    flip            # (List [fun] List)
    deref loop      # (List [fun] $loop)
    call            # (result-of-$loop), this is a tail-call
}