2.5. Execution

This chapter describes the execution model.

The contents of this chapter ensures that, or requires that a particular implementation of a Kink runtime works as if it was implemented in the way described here. However, the runtime is not required to implement literally in the same way. For example, a runtime implemented on Scheme may implement operations of executors using call/cc.

2.5.1. Executor

The executor is a component of a runtime which performs function runs. The runtime can contain multiple executors.

The executor starts when the first invocation starts on the executor.

The executor terminates, if it does, in one of the two states: succeeded or failed. If the executor has terminated in the succeeded state, it has the result value. If the executor has terminated in the failed state, it has a message string and a vector of traces.

The executor has an execution stack. The execution stack is an array of stack frames.

2.5.2. Stack frames

There are six types of stack frames.

  • KSM snapshot frame
  • Termination frame
  • Trace frame
  • Delimitor frame
  • Dyn frame

KSM snapshot frame

A KSM snapshot frame is a snapshot of a run of a KSM procedure.

The frame consists of attributes which are required to resume the run. That is:

  • the procedure
  • the program counter
  • the context environment
  • the context receiver
  • the context arguments vector
  • the value stack

When continue operation is performed on the frame with a value R, a run of a KSM procedure starts with the following regiesters.

Register Data
procedure the procedure attribute of the frame
program counter the program counter attribute of the frame
context environment the context environment attribute of the frame
context receiver the context receiver attribute of the frame
context arguments vector the context arguments vector attribute of the frame
value stack a new value stack containing all the elements of the value stack attribute of the frame, appending R at the top

Termination frame

The termination frame is a special frame which is always on the bottom of the execution stack.

When continue operation is performed on the frame with a value R, the executor terminates successfully with R as the result.

Trace frame

A trace frame is a frame used to construct a stack trace element.

A trace frame consists of any attributes required to construct a stack trace element.

When continue operation is performed on the frame with a value R, continue operation is performed again with R to the new top frame.

Delimitor frame

A delimitor frame is a frame to delimit the continuation with a tag string.

A delimitor frame consists of a continuation tag string as an attribute.

When continue operation is performed on the frame with a value R, continue operation is performed again with R to the new top frame.

Dyn frame

A dyn frame is a frame to store a dyn value.

A dyn frame consists of two attributes:

  • dyn tag string
  • dyn value

When continue operation is performed on the frame with a value R, continue operation is performed again with R to the new top frame.

2.5.3. Executor operations

There are the following types of operations on executors.

  • push
  • pop
  • invoke
  • continue
  • test-delimitor-existence
  • extract-slice
  • remove-until-delimitor
  • restore-slice
  • terminate-failure
  • extract-traces
  • extract-dyn

push operation

push operation is performed with a stack frame as an operand. It appends the stack frame to the top of the execution stack.

If the frame is a trace frame, and there is a consequent series of trace frames on the top of the execution stack, the series may be squashed and modified to be shorter. The runtime must perform this squashing so that the length of a consequent series of trace frames does not exceed a certain number. By this squashing, it is assured that a tail recursion does not consume up the execution stack.

If there is not enough resource for the new stack frame, an exception is raised.

pop operation

pop operation removes the top stack frame from the execution stack.

Precondition: there must be at least one stack frame on the execution stack.

invoke operation

invoke operation takes the following operands.

Operand Description
callee The invoked function. Precondition: must be a function value.
receiver The actual receiver value of the invocation.
arguments vector The actual arguments of the invocation. Precondition: must be a vector value.
symbol (optional) The symbol where the invocation takes place. It is an optional operand.
location (optional) The location where the invocation takes place. It is an optional operand.

If either or both of symbol and location operands are given, the operation pushes a trace frame made of them.

Then it invokes an action specific to the callee function.

continue operation

continue operation is performed with a value as an operand.

The operation pops the top frame, and performs an action which is specific to the type of the frame, as described in the Stack frames section.

test-delimitor-existence operation

test-delimitor-existence operation is performed with a continuation tag string as an operand.

The operation tests whether there is at least one delimitor frame whose continuation tag is equal to the operand.

extract-slice operation

extract-slice operation is performed with a continuation tag string as an operand.

The operation locates a delimitor frame whose continuation tag is equal to the operand, and extracts a slice from the delimitor frame to the top. The slice includes both ends.

Precondition: there must be at least one delimitor frame whose continuation tag is equal to the operand.

remove-until-delimitor operation

remove-until-delimitor operation is performed with a continuation string as an operand.

The operation locates a delimitor frame whose continuation tag is equal to the operand, and removes all stack frames above the delimitor frame.

Precondition: there must be at least one delimitor frame whose continuation tag is equal to the operand.

restore-slice operation

restore-slice operation is performed with a slice of stack frames as an operand.

The operation pushes the stack frames in the slice in order, to the execution stack.

terminate-failure operation

terminate-failure operation is performed with two operands:

  • a message string
  • a vector of traces

If the operation is performed, the executor terminates in the failed status, with the operand string as a message, and the operand traces.

extract-traces operation

extract-traces operation constructs a vector of traces in the execution stack, from the bottom to the top.

extract-dyn operation

extract-dyn operation is performed with a dyn tag string as an operand.

The operation constructs a vector of dyn values of the dyn frames from the bottom to the top, whose dyn tag is equal to the operand.

2.5.4. Kinds of functions

When a function is invoked, it performs various actions specific to the kind. Here is an incomprehensive list of the kinds of functions.

Top level functions

Top level functions are functions made by kink/PROGRAM.compile. See the detail on Top level functions section.

Enclosed functions

Enclosed functions are functions made by fun instruction of the KSM. See the detail on fun Procedure section.

Host system functions

Host system functions, or host funs are functions defined in the host system of the runtime. A host fun continues with a thunk fun.

Every host fun is wrapped by an enclosed fun, and the wrapper enclosed fun invokes the thunk with no arguments.

So, if the host fun is to raise an exception, or call a fun, or just return a val and so on, the host fun has to do is to return a thunk which does such an action.

注釈

The reason why the host fun is defined to perform trampoline here is not to introduce a new frame type. Of course, the runtime does not have to implement host funs literally in the same way.

kink/CORE.reset(Kont_tag $thunk)

kink/CORE.reset(Kont_tag $thunk) pushes a delimitor frame with Kont_tag as the continuation tag string, and invokes $thunk with no arguments.

kink/CORE.can_shift?(Kont_tag)

kink/CORE.can_shift?(Kont_tag) performs test-delimitor-existence operation with Kont_tag as the continuation tag string.

If a delimitor frame with the continuation tag exists, it continues with true value. If no delimitor frame with the continuation tag exists, it continues with false value.

kink/CORE.shift(Kont_tag $fun)

kink/CORE.shift(Kont_tag $fun) performs test-delimitor-existence operation with Kont_tag as the continuation tag string. If no delimitor frame with the continuation tag exists, an exception is raised.

If a delimitor frame with the continuation tag exists, it performs extract-slice operation, and makes a continuation function with the slice.

It then performs remove-until-delimitor operation with the continuation tag, and invokes $fun with the continuation function as the argument.

Continuation function

A continuation function is made by kink/CORE.shift with a slice of stack frames. It takes an optional argument.

If the continuation function is called with an argument, it performs restore-slice operation with the slice, and performs continue operation with the argument.

If the continuation function is called with no argument, it performs restore-slice operation with the slice, and performs continue operation with nada.

kink/CORE.dyn_vec(Dyn_tag)

kink/CORE.dyn_vec(Dyn_tag) performs extract-dyn operation with Dyn_tag as the dyn tag string.

It then continues with the constructed vector of dyn values.

kink/CORE.dyn_wind(Dyn_tag Dyn_val $thunk)

kink/CORE.dyn_wind(Dyn_tag Dyn_val $thunk) pushes a dyn frame with Dyn_tag as the dyn tag string, and Dyn_val as the dyn value.

It then invokes $thunk with no arguments.

kink/CORE.traces

kink/CORE.traces performs extract-traces operation. It then continues with the constructed vector of traces.

kink/CONTROL.try($body $on_returned $on_raised)

kink/CONTROL.try($body $on_returned $on_raised) is a fun to handle possible exceptions during the invocation of $body. The fun can be roughly defined as the following Kink code.

:try <- {(:body :on_returned :on_raised)
  # checks parameters, then

  :handler = reset('kink/CONTROL-try'){
    :R = body
    { on_returned(R) }
  }
  handler($on_raised)
}

kink/CORE.reraise(Msg Traces)

kink/CORE.reraise(Msg Traces) raises an exception with Msg as the message, and Traces as the traces. It can be roughly defined in the next pseudo Kink code.

:EVALUATOR.require_from('kink/')

:reraise <- {(:Msg :Traces)
  can_shift?('kink/CONTROL-try').if_else(
    { :Candidate_cleanups = dyn_vec('kink/CONTROL-cleanup')
      shift('kink/CONTROL-try'){
        :Base_cleanup_count = dyn_vec('kink/CONTROL-cleanup').size
        :Cleanups = Candidate_cleanups.drop_front(Base_cleanup_count)
        Cleanups.reverse.each{(:cleanup)
          EVALUATOR.run({ cleanup } {} {})
        }
        {(:on_raised)
          on_raised(Msg Traces)
        }
      }
    }
    { :Cleanups = dyn_vec('kink/CONTROL-cleanup')
      Cleanups.reverse.each{(:cleanup)
        EVALUATOR.run({ cleanup } {} {})
      }
      __terminate_failure__(Msg Traces.dup)
    }
  )
}

Where __terminate_failure__ is a function to perform terminate-failure operation.

kink/CORE.raise(Msg)

kink/CORE.raise(Msg) raises an exception with Msg as the message, and the current traces as the traces. It can be roughly defined in the next pseudo Kink code.

:raise <- {(:Msg)
  reraise(Msg traces)
}

kink/EVALUATOR.run($body $on_returned $on_raised)

kink/EVALUATOR.run($body $on_returned $on_raised) is a method to invoke $body in a new executor.

It makes an executor and invokes $body in the new executor, and then waits for the termination of the executor.

If the executor terminates in the succeeded state, it invokes $on_returned in the current executor, with the result of the terminated executor.

If the executor terminates in the failed state, it invokes $on_raised in the current executor, with the message string and the vector of traces of the terminated executor.

2.5.5. Exceptions

When an exception is raised in an executor with a message string, kink/CORE.raise(Msg) is invoked with the message string, or almost the same action is performed by the executor itself.

In the next program, dereference of the variable No_such_var raises an exception, and the exception is caught by kink/CONTROL.try fun.

:CONTROL.require_from('kink/')

CONTROL.try(
  { No_such_var }
  {(:Result) raise('must not reach here') }
  {(:Msg :Traces)
    stdout.print_line('exception traces:')
    Traces.each{(:T)
      stdout.print_line(T.desc)
    }
    stdout.print_line('exception message: {}'.format(Msg))
  }
)
# Output:
#   exception traces:
#   [launch]
#   [builtin:kink-mods/kink/_launch/LAUNCH_KINK.kn L195 C11 try] CONTROL.-->try(
#   [builtin:kink-mods/kink/CONTROL.kn L201 C14 reset] :handler = -->reset('kink/CONTROL-try'){
#   [builtin:kink-mods/kink/CONTROL.kn L202 C10 body] :R = -->body
#   [builtin:kink-mods/kink/_launch/LAUNCH_KINK.kn L197 C7 start] -->start(Non_opts)
#   [builtin:kink-mods/kink/_launch/LAUNCH_KINK.kn L132 C19 if_else] Non_opts.empty?.-->if_else(
#   [builtin:kink-mods/kink/_launch/LAUNCH_KINK.kn L140 C7 _run_script] -->_run_script($script_fun Script_args)
#   [builtin:kink-mods/kink/_launch/LAUNCH_KINK.kn L123 C3 script_fun] -->script_fun(Env)
#   [(stdin) L3 C9 try] CONTROL.-->try(
#   [builtin:kink-mods/kink/CONTROL.kn L201 C14 reset] :handler = -->reset('kink/CONTROL-try'){
#   [builtin:kink-mods/kink/CONTROL.kn L202 C10 body] :R = -->body
#   [(stdin) L4 C5] { -->No_such_var }
#   exception message: no such var: No_such_var