Skip to content

Flying Roll #1: instructions.rs and the Dispatch Loop

Jump to bottom
Mark Thom edited this page Aug 13, 2024 · 4 revisions

The Flying Roll series of Wiki articles are meant to expose secret knowledge of Scryer Prolog architecture and development. They are especially intended for developers contributing work to Scryer on the Rust side of development though it is hoped they will be helpful to everyone.

Introduction

The aim of this flying roll is to demystify the process by which instructions.rs is generated, what "variants" of each instruction are produced, and how they modify the operation of the dispatch loop of dispatch.rs. It is also meant to guide Scryer Prolog developers on how to add new instructions.

Motivation: Instruction Dispatch and Variant Naming

One of the biggest changes of the second iteration of the rebis development branch (which have since been merged into the master branch) is the flattening of the instruction dispatch loop. Previously, dispatch flowed on the paths set by the tree decomposition of the Line enum, the predecessor of rebis-dev's Instruction enum. In many cases, the dispatcher would have to branch its way through a lengthy path to the bottom of the tree before an instruction could finally be executed.

To reduce runtime branching as much as possible, rebis compresses each path to a single variant of Instruction. The dispatch loop now accomplishes in a single jump what once took a sequence of nested ifs. The resulting dispatch performance is greatly improved but maintainability is hurt as we now have to maintain several "flavours" of each instruction.

This problem is ameliorated by generating both the Instruction enum and most of its helper functions programmatically, using procedural macros from the instructions_template.rs module. You may notice from perusing the Scryer Prolog source tree that instructions.rs isn't included anywhere. This is because instructions_template.rs programmatically generates it at build time (and in fact, isn't linked to the Scryer Prolog executable as a runtime module!).

The unvaried parts of the WAM instruction set are stored in the base InstructionTemplate enum of instructions_template.rs. The remaining instructions, all of which call predicates implemented in Rust, are derived fromClauseType. ClauseType variants determine the differences among the instructions they generate:

ClauseType variant Inference Counted (2) Meta-callable (1) Call/Execute (2)
BuiltInClauseType ✓ ✓ ✓
InlinedClauseType ✗ ✓ ✓
SystemClauseType ✗ ✗ ✓
CallN ✓ ✓ ✓
Named ✓ ✓ ✓

A clause is inference counted if calling it increments the inference count tracked in calls made from call_with_inference_limit/3, meta-callable if it can called by call/N, and in execute (call) position if it is (not) the final predicate of a clause.

The parenthesized numbers next to each column title are variant multipliers factoring into the number of instructions the ClauseType variant produces when the box is ticked in that column.

As an example, BuiltInClauseType::Sort produces these (2*1*2 = 4) instructions:

enum Instruction {
    ...
    CallSort(usize),
    ExecuteSort(usize),
    DefaultCallSort(usize),
    DefaultExecuteSort(usize),
    ...
}

"Default" variants toggle inference counting off. They're generated in code by wrapping the call in the '$call_with_default_policy/1 functor. Call and Execute decide whether the next instruction pointer value p is set by incrementing the current p by 1 or by copying the continuation pointer cp to it.

Reasons for the naming of the ClauseType variants are hinted in the table as well. Inlined clause types include semi-deterministic built-ins like var, atomic, number, etc. They have no need of "Default" variants because, being inlined, they never contribute to the inference count. Similarly, SystemClauseType variants aren't meta-callable or inference-counted. They follow the naming convention '$[a-zA-Z\_]+' to avoid probable collisions with ordinary predicate names. New variants are usually of the type SystemClauseType. Named and CallN aren't actually variants at all; they represent direct predicate calls and call/N appearances in compiled code respectively.

Tools and Conventions of the Dispatch Loop

Expanding further on the sort/2 example, we look to how the four variants are prepared for interpretation as match arms in the dispatch loop of src/machine/dispatch.rs.


match &self.machine_st.code[self.machine_st.p] {
&Instruction::CallSort(_) => {
    try_or_throw!(self.machine_st, self.machine_st.sort()); // 1

    if self.machine_st.fail {
        self.machine_st.backtrack();
    } else {
        try_or_throw!(
            self.machine_st,
            (self.machine_st.increment_call_count_fn)(&mut self.machine_st) // 2
        );

        self.machine_st.p += 1; // 3
    }
}
&Instruction::ExecuteSort(_) => {
    try_or_throw!(self.machine_st, self.machine_st.sort());

    if self.machine_st.fail {
        self.machine_st.backtrack();
    } else {
        try_or_throw!(
            self.machine_st,
            (self.machine_st.increment_call_count_fn)(&mut self.machine_st)
        );

        self.machine_st.p = self.machine_st.cp; // 4
    }
}
&Instruction::DefaultCallSort(_) => {
    try_or_throw!(self.machine_st, self.machine_st.sort());
    step_or_fail!(self, self.machine_st.p += 1); // 5
}
&Instruction::DefaultExecuteSort(_) => {
    try_or_throw!(self.machine_st, self.machine_st.sort());
    step_or_fail!(self, self.machine_st.p = self.machine_st.cp); // 5
}

The instruction pointer of the Scryer WAM is always stored as a usize in self.machine_st.p. It indexes into the self.machine_st.code global code vector, fetching the next instruction for execution. As with all direct threaded interpreters, it is the responsibility of each instruction to tell the interpreter from where to fetch the next instruction by setting self.machine_st.p.

We discuss the features top-down highlighted by the commented numbers in bold.

  1. All four variants of sort/2 rely on the Rust function MachineState::sort for their implementation. MachineState::sort has return type CallResult, which is an alias of the type Result<(), MachineStub>. MachineStub, the Err variant return type, is a vector of HeapCellValue cells representing an error functor. The Ok variant is the unit type, (), signifying success and nothing else.

    The utility macro try_or_throw! inspects the return value of MachineState::sort. It proceeds normally, to the remaining code of the arm, upon success. Upon failure, it throws the exception inside the Scryer WAM by sending the MachineStub payload to MachineState::throw_exception before calling MachineState::backtrack.

  2. Since sort/2 is a BuiltInClauseType, it is inference counted. Since MachineState::sort succeeded in the conventional Prolog sense (by not setting self.machine_st.fail to true), the inference count must be incremented by calling the self.machine_st.increment_call_count_fn function pointer. This pointer points to a no-op if sort/2 was not ultimately called through call_with_inference_limit/3. Whatever its value, this function pointer has return type CallResult, so it is again necessary to wrap it in try_or_throw! so the exception is thrown without evacuating the dispatch loop.

  3. This variant is of Call rather than Execute type, which means it is not the final call of its host predicate. Thus, self.machine_st.p is simply incremented by 1.

  4. Everything is otherwise the same, but this call to sort/2 being in last call position means that self.machine_st.p must be overwritten by the WAM continuation pointer, self.machine_st.cp.

  5. step_or_fail! is a utility macro taking a single expression $expr and expanding to this block:

if self.machine_st.fail {
    self.machine_st.backtrack();
} else {
    $expr
}

A similar pattern is used in cases where the inference count is incremented, of course. By definition, Default-type variants do not increment it.

Generating instructions.rs

The atom names and arities of built-in predicates are encoded in the build/instructions_template.rs source file by annotating the variants of the ClauseType subtypes with name and arity attributes. The attribute macros of the strum crate, like EnumProperty and EnumDiscriminants, scan their host types and generate accessor functions for these properties. An example:

#[derive(ToDeriveInput, EnumDiscriminants)]
#[strum_discriminants(derive(EnumProperty, EnumString))]
enum CompareNumber {
    #[strum_discriminants(strum(props(Arity = "2", Name = ">")))]
    NumberGreaterThan(ArithmeticTerm, ArithmeticTerm),
    #[strum_discriminants(strum(props(Arity = "2", Name = "<")))]
    NumberLessThan(ArithmeticTerm, ArithmeticTerm),
    #[strum_discriminants(strum(props(Arity = "2", Name = ">=")))]
    NumberGreaterThanOrEqual(ArithmeticTerm, ArithmeticTerm),
    #[strum_discriminants(strum(props(Arity = "2", Name = "=<")))]
    NumberLessThanOrEqual(ArithmeticTerm, ArithmeticTerm),
    #[strum_discriminants(strum(props(Arity = "2", Name = "=\\=")))]
    NumberNotEqual(ArithmeticTerm, ArithmeticTerm),
    #[strum_discriminants(strum(props(Arity = "2", Name = "=:=")))]
    NumberEqual(ArithmeticTerm, ArithmeticTerm),
}

You are encouraged to read the strum documentation for info on how to define further discriminants and access the annotated data. I stress that strum is a strictly build time crate, similarly to how instructions_template.rs is only built and run at build time.

Beyond generating Instructions from template types definitions, instructions_template.rs generates the implementation of Instructions (i.e., the functions of impl Instructions) using the proc-macro2 family of metaprogramming crates. They provide a kind of quasiquotation-based syntax expansion similar to that available in the Lisp family of programming languages. The functions they're used to generate are simply transformation and property predicate functions primarily used by the code generator. They are:

Function Function Description
fn to_name_and_arity(&self) -> (Atom, usize) Returns the predicate indicator of the instruction 1
fn to_default(&self) -> Instruction Returns the Default variant of the instruction if one exists
fn to_execute(&self) -> Instruction Returns the Execute variant of the instruction if one exists
fn is_execute(&self) -> bool Is an Execute variant
fn perm_vars_mut(&mut self) -> Option<&mut usize> Returns a mutable reference to the permament variables slot of the variant if it exists 2
fn is_ctrl_instr(&self) -> bool Is a so-called "control instruction" 3
fn is_query_instr(&self) -> bool Is an instruction that may appear in the body of a compiled predicate
1. Primarily used by Instruction::to_functor to produce code listings of WAM instructions as Prolog functors and to generate stubs for exceptions.
2. Some instructions track the number of active permanent variables at their time of execution inside their host predicate. This is to support a WAM optimization known as environment trimming which Scryer does not yet (and may never) implement.
3. One of `allocate`, `deallocate`, `proceed`, `rev_jmp_by`.

To add a new built-in predicate to Scryer Prolog, the following steps should be taken in instructions_template.rs:

  1. Identify the variants you want to generate for the instruction using the variant table and place your new instruction variant in the corresponding ClauseType subtype (this will very probably be SystemClauseType). The variant should be named by translating the Prolog predicate name from snake case to Pascal case as Rust convention dictates.

  2. Add strum_discriminants attribute properties Name and Arity by mimicking surrounding attributed variants.

  3. Add your instruction and its generated variants as arms to the appropriate section of Instruction::to_functor. For now, Instruction::to_functor is unfortunately written and maintained by hand.

  4. Add generated variants as arms to the dispatch loop of dispatch.rs.

Importantly, you MUST NOT add wildcards to any manually maintained functions or try to modify any of the auto-generated functions listed above. Match arms for new variants will be inserted into the auto-generated functions automatically.

We conclude the flying roll with a small note on the instr! macro.

The instr! Macro

instr! is a declarative macro generated in instructions_template.rs for the convenience of the code generator. It takes as its first input the strum-annotated Name of an Instruction variant along with any arguments the named variant takes, and expands to a declaration of that variant. An example:

instr!("jmp_by_call", vars.len(), 0, pvs)

==>

Instruction::JmpByCall(vars.len(), 0, pvs)

rustfmt doesn't format macro_rules! readably yet, but the generated instr! declaration can still be viewed, warts and all, at instructions.rs.

Clone this wiki locally