Astarte abstract machine description

The abstract machine maintains a collection of data structures that describe the program and its state. This section describes those data structures.

The abstract machine supports multiple threads. Some structures are global, shared by all threads, while others are local to a particular thread. Some data structures are local to a particular frame of the call stack, representing one function call.

Those whose names are shown in blue are generally more important, and those in dark red less important to know about.

Major Thread-Local Data Structures (Each thread has its own copy of these)
Structure	Description
Data stack	The data stack is a stack where data items are pushed and popped during computation. Most of the machine instructions get their inputs from the top of this stack, and push their results onto this stack. Parameters to functions are pushed here, and function results are left on this stack.
Type stack	Programs can produce complex types. The type is a stack where types are pushed and popped while building types and taking them apart.
Type store	This is an array where types are stored by index. (You get a type by specifying an index, such as 0 or 1.) Some instructions store types into this array, and others fetch types out of this array. The type store also keeps track of the index of the first unoccupied spot in the array, so an instruction can ask for a type to be put into this first unoccupied index. This array is not used for long-term storage, but is for temporary storage during the construction of types. It allows you to build a type and use that type in several places. The values of type variables are typically stored here.
Call stack	The call stack holds information about functions that have called another function and are waiting for it to return. This is the usual run-time stack. Each node in the call stack remembers information such as an environment that can be restored when the function is resumed.
Control	The control provides information about exception handlers, backtrack points and other threads that are running concurrently with the current thread. It is used to determine how to respond to failure, and to perform cuts and related actions. You can think of the control as a tree with the current thread as one of its leaves. The internal nodes provide information on exception handlers and other threads.

Other Thread-Local Data Structures (Each thread has its own copy of these)
Structure	Description
Local return address stack	Normally, when one function calls another function, quite a bit of bookkeeping information is created to allow a return to the calling function's context. In some situations you can avoid that bookkeeping information. A thread can perform a local call, which does not do all of that setup, but only remembers a return address. The local return address stack is used to hold those return addresses.
State	The state holds the contents of nonshared boxes for this thread. Each time the content of a nonshared box is obtained, it is looked up in the current thread's state. When a nonshared box has its content modified, that modification is only made in the state of the current thread.
State stack	Sometimes a thread needs to remember its state so that it later it will be able to return to this state. The state stack holds states that the thread is remembering.
Affiliation set	Each thread has a set of affiliations, which can be thought of as groups to which this thread belongs. An affiliation is a positive integer. Some instructions send a message to all threads that have a given affiliation. The interpreter maintains a forest of control trees. At any given time, only one of those trees belongs to an @EXECUTE block. All others were created because a thread detached itself. A thread that is part of a detached control tree always has affiliation 1. The execute threads never have that affiliation.
Trap stack	When an exception occurs, it is either handled normally (using information in the control, or is trapped. When an exception is trapped, the machine stops immediately and reports the failure. Each thread keeps a set of exceptions that are trapped if they occur while this thread is running. To allow for embedded contexts, there is a stack of exception sets. The top set in this stack is the active one.
Locked boxes	This is a list of shared boxes that this thread has locked. A thread can have multiple locks on a box. If it does, the box occurs more than once in the list of locked boxes.
No-suspend count	The nosuspend-count is a counter that always contains a nonnegative number. When a thread's no-suspend count is 0, it can be suspended by other threads. When the count is positive, any message to suspend will be remembered, and only applied when the thread's nosuspend count becomes 0.
No-terminate count	The no-terminate-count is a counter that always contains a nonnegative number. When a thread's no-terminate count is 0, it can be terminated by other threads. When the count is positive, any message to terminate or suspend will be remembered, and only applied when the thread's no-terminate count becomes 0.
Current directory	Each thread has a current directory that controls how it accesses the file system.
View flag	This is a counter, initiallly 0. When it is positive, functions that show items as strings are asked not to evaluate promises, but instead to show them as strings that describe them as promises. Also, an attempt is made to prevent more than one thread from running until this counter becomes 0 again.

Frame-Local Data Structures (Each frame of the call stack has its own copy of these)
Structure	Description
Environment	A function can have local variables, and the bindings of those variables are held in the environment. The environment is chain of arrays. The first array in the chain is the most local environment, storing bindings of variables in the most local scope. The next array in the chain is for the scope that statically encloses the most local scope. As you go deeper into the chain, you reach more and more outward in lexical scope. The last array in this chain is called the static environment, which is a cache where globally defined items that are needed by a particular function are stored. Some types can also be stored here. When a function is created, it grabs some globally defined data items and types that it will need and stores them in the static environment so that it does not need to ask for them repeatedly from the global tables (which are more expensive to use than the static environment), or does not need to rebuild the types each time they are needed. Each individual environment in chain is an array indexed from 0. So the data items are referred to as item 0, item 1, etc. Each identifier has an associated index. For example, identifier x might be found at index 1 in the environment. Instructions are available for fetching and storing items by index.
Exception stack	When a failure occurs there is a data item called an exception that provides some information about the reason for the failure. Exception values are stored in a stack, so that several failure contexts can be remembered.
Type variable binding stack	Occassionally a thread needs to bind type variables. Each member of the type variable binding stack is a table giving bindings of type variables for this thread. The top table is the active one, and other tables in the stack can be restored to active status later. Each table also holds a collection of constraints that indicate relationships among variables and species. The constraints limit the bindings that variables can take on. A constraint has the form A `>=` B, where A and B are (polymorphic) species.
Instruction counter	The instruction counter tells the address of the next instruction that the current frame will perform.
Name	The name indicates which function is running in this frame.

Global Data Structures
Structure	Description
Instruction store	The instruction store is an area where the program is stored (in internal form).
Shared box state	The shared box state holds the contents of shared boxes, and can be changed as the program runs.
Initial nonshared box state	When a nonshared box is given an initial value, that value is stored into the initial state. All threads initially see that box as holding its initial value. If no initial value is assigned, the box is initially empty.
Environment descriptors	There is an array of descriptors of local environments. This is used for debugging, to keep track of the names of local variables.
Polymorphic global definition table	This is a table where definitions are kept. Only definitions done by declarations are stored in this table. Each definition is a triple (name, type, how-to-compute) indicating a binding of a given name with a given polymorphic type, and a method of computing the item that is defined. There can be several definitions for each name. There can even be several that have the same name and the same type. The bindings of a given name are kept as an ordered list. A binding is looked up by providing a (name, type) pair. The first binding for this name that matches the desired type is selected.
Monomorphic global definition table	The monomorphic global table is a cache for information found from the polymorphic global table. When a binding of a name with a specific type is found from the polymorphic global table, that binding is is stored, with its type, in the monomorphic global table. Later, when it is needed again with the same species, it is looked up in this table.
Type tables	The machine maintains tables of information about the relationships among different types. These relationships are used when performing operations on types and when looking up bindings in the polymorphic global table.

There are a few issues that you need to be aware of in order to understand how the abstract machine works, and what its instructions do.

Important Issues
Numbers and Characters	Numbers are stored in three representations: as integers, as rational numbers (a quotient of two integers) and in floating point form. Numbers can have arbitrary precision. The precision of floating point numbers is controlled by box precision. The integer representation is universal; all instructions that need numbers, of any kind, can understand integer representation. The rational representation can also be used where a real number is needed. There are four standard numeric species. Species Natural (nonnegative integers) and Integer (all integers) use exactly the same representation for nonnegative integers. As a consequence, any instruction that works on an integer will also work on a natural number. In some places, the documentation indicates that a natural number is required. That just means that the number must be nonnegative. Characters are integers from 0 to 255. (The Ascii alphabet is currently used.) Instructions that work on integers or produce integers in this range can be used for characters as well. Numbers are stored internally in base 2¹⁶. This is important to a few of the instrutions, where it is called the internal base.
Strings	A string is a list of characters, and has species List(Char). Any instruction that works on general list or lists of integers also works on strings. Any instruction that produces a list of integers in the required range for characters can be used to produce a string.
Path names	File path names can be written using either / or \ to separate directories. The interpreter will use the correct symbol when interacting with the operating system, regardless of what you use in your program.
Tagged values	Some values are tagged with a species. They are indicated in the form (X:T) where X is the value and T is the species. These are represented as structures holding both the value and the species. Operations that work on numbers can handle tagged numbers. Operations that require characters or lists of characters require that the characters not be tagged. Some values are tagged with a nonnegative integer. They are indicated in the form (X:n). An item that is tagged with an integer tag can get another integer or species tag attached to it. For example, ((X:2):5) is acceptable.
Boxes	A box is a variable, or a reference, that has a content that can be changed. A box can also be empty, having no content, and you can detect whether a box is empty. There are three kinds of boxes. A shared box is shared by all threads. When one thread modifies the content of a shared box (or empties it), all threads see the change. A nonshared is local to a thread. When a thread modifies the content of a nonshared box (or empties it) only that one thread's view of the box is changed. The contents of nonshared boxes is kept in a separate table for each thread. A computed box is represented as a collection of functions whose action is intended to simulate modifying and fetching the contents of the box. A box can have a collection of demons attached to it, where each demon is a function. (See ATTACH-DEMON.) When the box has its contents modified, the demons attached to the box are normally run. A special kind of demon that can be attached to a box is a finalizer. This is a function that is only run when the box is destroyed by the garbage collector. It allows you to perform some additional cleanup. To clean up a larger object, you can put a box inside that larger object, and attach a finalizer to that box. Boxes can present problems for multithreaded programs because the threads can interfere with one another. Shared and computed boxes can be locked. A thread can check whether a box is locked. It can lock a box, but if it tries to lock a box that is already locked by another thread, then it will wait until it can lock the box. Locks are only advisory; a thread can fetch or modify the content of a locked box by simply ignoring the lock. Locks are a little unusual in two ways. A thread can hold a lock more than once on a given box. If a thread tries to lock a box that it already has locked, then it gets two locks on that box, and is allowed to continue. When the thread unlocks the box, it only removes one of those locks. This allows a thread to perform a lock/modify/unlock sequence on a box without performing a check to see whether it already owns a lock on that box. More than one thread can have a box locked. When a thread forks, each of the new threads owns exactly the same locks. It is up to the programmer to choose one of those threads to relinquish its locks. Nonshared boxes cannot be locked since they are not shared among different threads.
Promises and lazy evaluation	A data item can be stored as a promise, indicating a deferred computation that will be done when its result is needed. Some instructions need to evaluate those promises, either fully or partially. As a result, evaluating an instruction might cause a side computation to be performed before it returns. In effect, instructions can do implicit calls to functions. So a short and simple instruction like an add instruction does not always complete quickly, and could perform an arbitrarily long side computation in order to evaluate the numbers to be added. A promise remembers the state and other thread-local data structures that were in effect when the promise was created. When the promise is evaluated, those data structures are restored. In effect, creating a promise also creates a thread that will (if necessary) evaluate the promise. So the contents of nonshared boxes will be the same as they would be if the eager evaluation had been used. The values of shared boxes, however, are part of the global information. The contents that a promise sees for them can depend on when the promise is evaluated. Computations can fail, and it is possible for a deferred computation to fail to produce a value. In that case, the fact that the computation failed is remembered, and each subsequent attempt to evaluate the promise will immediately lead to the same kind of failure.
Unknowns	There is a kind of item called an unknown that indicates an unknown value. Instructions are available for creating and binding unknowns. An unknown can only be bound once; when it becomes bound, it is no longer an unknown at all. This is important to know because, normally, trying to look at the value of an unknown will cause a thread to wait for another thread to bind the unknown. Some of the instructions are active. When they encounter an unknown, they automatically bind it to something (with the value depending on the instruction). Unknowns can be shared or nonshared. The bindings of nonshared unknowns are stored in a thread's state, and binding a nonshared unknown only affects what the current thread sees. Bindings of shared unknowns, on the other hand, are visible to all threads. Unknowns can also be protected or unprotected. An unprotected unknown can be bound at any time by any thread. A protected unknown has a key, and an attempt to bind it must be accompanied by the key.
Multiple threads	The interpreter can run several threads. As a result, any thread might be suspended temporarily at any time to allow another thread to run. Two instructions that occur one after another in the program are not necessarily performed without any intervening instructions, even when no promises are involved. Threads are related to one another. There is no notion of one thread being a parent of another, but there is a sibling relationship. One thread can split into two, and the two threads become siblings. The thread structure is a tree, where all of the threads are leaves of the tree. When a thread forks, a leaf is replaced by an internal node with two children. The internal node is only present to hold the tree together; it does not represent a thread. The interpreter maintains a forest of these thread trees. A thread can detach itself from its tree, and become a new root in the forest.
Failure	Computations do not always succeed. When a computation fails, the abstract machine takes action as indicated by the nature of the failure and by the context in which the failure occurs. Failure can indicate a serious error that should cause computation to stop immediately; an exceptional condition that must be handled by the program; failure to compute a value in a certain way, suggesting that a different way be tried; an end of a branch in a backtracking computation; termination of a thread.
Types	The abstract machine is partly *typed, but partly untyped. Many of the instructions work in an untyped manner. But some of the instructions handle types explicitly, so that this abstract machine provides support for run-time type checking. A type is called a species. A type constructor is called a parameterized species* or a family. See here for details about species in the abstract machine.

Program formats

Package heading

A package has an interface part and an implementation part. You can select a name for each part, or use the same name for both parts.

A package must begin with a heading that provides the name(s) of the package and the abstract machine version that it uses.

The rest of the package

The remainder of the package, after the heading, consists of a sequence of declarations, as described in the declaration section below. The package must end on an @END-PACKAGE instruction. Any bytes after the @END-PACKAGE are ignored.

Numbers in the byte code

Some of the instructions contain integers as part of the instruction. Numbers in a program are represented in one of three forms: (1) one byte, (2) three bytes or (3) multiple bytes. Single byte integers are unsigned, from 0 to 255. Three byte integers can be either signed or unsigned, depending on the instruction, and can range from 0 to 2^24-1 (unsigned) or from -2²³ to 2²³-1 (signed). Multibyte integers can be arbitrarily large, and signed or unsigned.

In the byte-code format, three byte numbers are stored low order byte first in biased form. To store n, the three byte integer is 0x800000 + n as an unsigned three byte integer.

Labels and Names
Declaration	Purpose
@LABEL n	Make it possible to refer to what is defined in the next declaration by a numeric label.
@ID name	Define a name for a data item
@NAME name	Define a name that does not refer to a data item

Defining Constants
Declaration	Purpose
@STRING "str"	Define a string constant
@INT n	Define an integer constant
@REAL x	Define a real constant
@RAT x	Define a rational constant
@LIST	Define a list constant

Making Definitions and Performing Actions
Declaration	Purpose
@EXECUTE	Evaluate some instructions.
@HIDDEN-EXECUTE	Evaluate some instructions.
@DEFINE	Define an named data item.

Creating New Types and Altering the Hierarchy
Declaration	Purpose
@BEGIN-EXTENSION	Begin an extension where types can be defined
@END-EXTENSION	End an extension
@NEW-SPECIES name	Create a new species
@IMPORTED-SPECIES name	Declare a species that is created in another package
@NEW-FAMILY opts name	Create a new parameterized species
@IMPORTED-FAMILY name	Declare a parameterized species that is defined in another package
@NEW-GENUS opt name	Create a new genus
@IMPORTED-GENUS name	Declare a genus that is defined in another package
@NEW-COMMUNITY opts name	Create a new parameterized abstraction
@IMPORTED-COMMUNITY name	Declare a parameterized abstraction that is defined in another package
@RELATE A B	State that the thing declared at label A is beneath the thing declared at label B in the hierarchy.
@MEET A B C	State that the meet of A and B is C, where each is given by the global label where it is declared.
@EMPTY-MEET A₁ ... A_k	State that the meet of A₁ ... A_k is empty, each is given by the global label where it is declared.
@DEFAULT A	Declare a default for the abstraction declared at label A.

Miscellaneous
Declaration	Purpose
@IMPORT path	Import file path.
@BEGIN-IMPLEMENTATION	End the interface part of the package and begin the implementation.

Building Types
Instruction	Purpose
STD-SPECIES name	Push a built-in primary species or primary parameterized species onto the type stack.
STD-SECONDARY-SPECIES name	Push a built-in secondary species or secondary parameterized species onto the type stack.
SPECIES-ID L	Push the species or parameterized species that is defined at label L (using, for example, a @NEW-SPECIES or @IMPORTED-SPECIES or @NEW-FAMILY or @IMPORTED-FAMILY declaration).
STD-SPECIES-VAR name	Push a new variable that ranges over the genus or parameterized genus name.
SPECIES-VAR L	Push a new variable that ranges over the genus or parameterized genus defined at label L (using, for example, a @NEW-GENUS or @IMPORTED-GENUS declaration).
STD-PRIMARY-SPECIES-VAR name	Push a new variable that ranges over all primary species or parameterized species in the genus or parameterized genus name.
PRIMARY-SPECIES-VAR L	Push a new variable that ranges over the genus or parameterized genus defined at label L (using, for example, a @NEW-GENUS or @IMPORTED-GENUS declaration).
STD-SECONDARY-SPECIES-VAR name	Push a new variable that ranges over all secondary species or parameterized species in the genus or parameterized genus name.
SECONDARY-SPECIES-VAR L	Push a new variable that ranges over the genus or parameterized genus defined at label L (using, for example, a @NEW-GENUS or @IMPORTED-GENUS declaration).
FUNCTION-SPECIES	Create a function species.
PAIR-SPECIES	Create a cartesian product species.
LIST-SPECIES	Create a list species.
BOX-SPECIES	Create a box species.
FAM-MEM-SPECIES	Apply a parameterized species as a species constructor.
SECONDARY-DEFAULT	Mark the variable on the top of the type stack as preferring a secondary default.

Taking Types Apart
Instruction	Purpose
UNPAIR-SPECIES	Take apart a function, cartesian product or constructed type.
HEAD-SPECIES	Get part of a function, cartesian product or constructed type.
TAIL-SPECIES	Get part of a function, cartesian product or constructed type.
POP-SPECIES	Pop the top thing off the type stack.
SWAP-SPECIES	Swap the top two things on the type stack.

Using the Type Store and Static Environment
Instruction	Purpose
CLEAR-SPECIES-STORE	Empty out the type store array.
STORE-SPECIES	Pop the top thing from the type stack and store it at the next available place in the type store.
STORE-AND-LEAVE-SPECIES	Store the top thing from the type stack into the next available place in the type store, but leave it on the type stack.
GET-SPECIES n	Push the thing that was stored at index n in the type store onto the type stack.
GLOBAL-FETCH-SPECIES n	Push the thing that was stored at index n in the current function's static environment onto the type stack.

Handling Polymorphic Types
Instruction	Purpose
UNIFY	Unify the two types on top of the type stack.
CONSTRAIN-SPECIES	Introduce a constraint on species.
FREEZE-SPECIES	Replace the thing on the top of the type stack by a copy of itself where all bound variables have been replaced by the values to which they are bound.
PUSH-SPECIES-BINDINGS	Push the current thread's type variable bindings onto its type-binding stack.
POP-SPECIES-BINDINGS	Pop a binding table from the current thread's type variable binding stack, and make that table the current thread's binding table.
COMMIT-SPECIES-BINDINGS	Make it so that the next pop of the species binding table stack will not change the binding table.

Types as Data Items
Instruction	Purpose
SPECIES-AS-VALUE	Move the top of the species stack to the data stack.
DS-MAKE-SPECIES	Pop the name of a species from the data stack and push the species that is named.
DS-FUNCTION-SPECIES	Build a function type as a data item.
DS-PAIR-SPECIES	Build a cartesian-product type as a data item.
DS-FAM-MEM-SPECIES	Use a parameterized species to construct a species as a data item.
DS-SPECIES-COMPATIBLE	Compare two species.
DS-COMPARE-SPECIES	Compare two species.
DS-PRIMARY?	Determine whether the species on the top of the data stack is primary.
DS-UNFAM-MEM-SPECIES	Take apart a constructed species into the family that constructed it and the parameter species.
DS-UNPAIR-SPECIES	Get the component types of a cartesian product species.
DS-UNFUNCTION-SPECIES	Get the domain and codomain of a function type.
DS-SPECIES-TO-STRING	Create a string that describes a species.

These instructions should only be used in parts where a static environment is being built.

Building the Static Environment
Instruction	Purpose
GET-GLOBAL-ID L	Get the binding of an identifier in the global definition table and store it into the static environment.
SPECIES-ONLY	Pop the type stack and store the popped type into the static environment.

Data Stack Manipulation
Instruction	Purpose
DUP	Duplicate the top of the data stack.
POP	Pop the data stack.
SWAP	Swap the top two items on the top of the data stack.

Constants
Instruction	Purpose
SMALL-INT n	Push a very small (one byte) integer onto the data stack.
CONST L	Push the constant defined at label L onto the data stack.
ZERO	Push 0 onto the data stack. The number pushed has type Natural or Integer.
HERMIT	Push () onto the data stack.

Numbers and Arithmetic
Instruction	Purpose
ZERO?	Test whether a number is zero.
PLUS	Pop two numbers and push their sum.
MINUS	Pop two numbers and push their difference.
ABSDIFF	Pop two numbers and push the absolute value of their difference.
NEGATE	Take the negation of a number.
TIMES	Pop two numbers and push their product.
DIVIDE	Pop two numbers and push their quotient.
RECIPROCAL	Compute the reciprocal (1/x) of a number.
MAKE-RAT	Pop two integers and push their quotient as a rational number.
INT-DIVIDE	Perform an integer division, obtaining a quotient and a remainder.
INTEGER-RECIPROCAL	Compute the integer reciprocal of a number. (Probably not what you think.)
GCD	Pop two integers and push their greatest common divisor.
POW	Compute a number to an integer power.
ABS	Compute the absolute value of a number.
ODD?	Test whether an integer or natural number is odd.
SIGN	Compute the sign of a number.
SQRT	Compute the square root of a real number.
EXP	Compute exp(x) (e^x).
LN	Compute the natural logarithm ln(x).
SIN	Compute sin(x).
INVTAN	Compute tan^-1(x).
FLOOR	Take the floor of a real or rational number.
CEILING	Take the ceiling of a real or rational number.
TO-NATURAL	Convert a number to species Natural.
TO-INTEGER	Convert a number to species Integer.
TO-RATIONAL	Convert a number to species Rational.
TO-REAL	Convert a number to species Real.
AS	Convert one number to the same kind as another.
STRING-TO-NATURAL	Convert a decimal number as a string to a natural number.
STRING-TO-INTEGER	Convert a decimal number as a string to an integer.
STRING-TO-RATIONAL	Convert a decimal number as a string to a rational number.
STRING-TO-REAL	Convert a decimal number as a string to a real number.
HEX-TO-NAT	Convert a hexadecimal number as a string to a natural number.
NAT-TO-HEX	Convert a natural number to a hexadecimal string.
NUM-DIGITS	Get an approximation to the number of digits in a number, using the internal working base of the interpreter.
NUM-DECIMAL-DIGITS	Get an approximation to the number of decimal digits in a number.
PULL-APART-REAL	Get the mantissa and exponent of a real number.
BUILD-REAL	Make a real number from its mantissa and exponent.
GET-PRECISION	Get the current real arithmetic precision in internal digits.

Conversion to string
Instruction	Purpose
TO-STRING	Convert a number, box or function to a string.
TO-STRING-FORMATTED	Convert a number, box or function to a string.

Comparisons
Instruction	Purpose
COMPARE	Compare two numbers, telling whether one is <, > or = to the other.
EQ	Determine whether two numbers are equal.
NE	Determine whether two numbers are not equal.
LE	Determine whether one number is <= another.
LT	Determine whether one number is < another.
GE	Determine whether one number is >= another.
GT	Determine whether one number is > another.

Booleans
Instruction	Purpose
FALSE	Push false onto the data stack.
TRUE	Push true onto the data stack.
NOT	Take the logical negation of the top of the data stack.
And/Or	See AND-SKIP and OR-SKIP.

Lists, Strings and Ordered Pairs
Instruction	Purpose
NIL	Push [] onto the data stack.
NIL?	Test whether the top of the data stack is [].
NONNIL-TEST	Test whether the top of the data stack is not [].
NIL-FORCE	Test whether the top of the data stack is []. If it an unbound unprotected unknown, bind it to [] first. (This is an active instruction.)
NONNIL-FORCE	Test whether the top of the data stack is not []. If it an unbound unprotected unknown, bind it to a nonempty list (ordered pair) first. (This is an active instruction.)
PAIR	Pop y and x from the type stack and push an item that is either x::y or (x,y). Its type can be either a list or a product type.
MULTI-PAIR n	Same as n consecutive PAIR instructions.
HEAD	Get the head of a list or the left-hand member of an ordered pair.
LAZY-HEAD	Same as HEAD, but do not evaluate the argument.
TAIL	Get the tail of a list or the right-hand member of an ordered pair.
LAZY-TAIL	Same as TAIL, but do not evaluate the argument.
ACTIVE-HEAD	Get the head of a list or the left-hand member of an ordered pair, but if the list or pair is currently an unbound unprotected unknown, then bind it to a pair first. (This is an active instruction.)
ACTIVE-LAZY-HEAD	Same as LEFT, but do not evaluate the argument.
ACTIVE-TAIL	Get the tail of a list or the right-hand member of an ordered pair, but if the list or pair is currently an unbound unprotected unknown, then bind it to a pair first. (This is an active instruction.)
ACTIVE-LAZY-TAIL	Same as RIGHT, but do not evaluate the argument.
MULTI-RIGHT n	Same as n consecutive ACTIVE-TAIL instructions.
SPLIT	Get the head and tail of a list, or the left-hand and right-hand members of an ordered pair.
LENGTH	Compute the length of a list.
LIMITED-LENGTH	Compute the length of a list, but stop if a limit is exceeded.
REVERSE	Compute the reversal of a list.
APPEND	Compute the concatenation of two lists.
SUBSCRIPT	Select a member from a list by position.
SUBLIST	Get a sublist of a list, given by a start position and length.
BITE	Split a list into a prefix and suffix.
SCAN-FOR	Search for a character in a string.
START-LIST	Begin building a list.
ADD-LIST-MEM	Add a member to a list that was started with START-LIST.
UPTO	Pop two integers n and m and push the list [m,m+1,...,n].
DOWNTO	Pop two integers n and m and push the list [m,m-1,...,n].
MAPPED-LIST	Create a dynamically mapped list.
MAP-WRAP k	Create a dynamically mapped list that maps the wrap function.
PACK	Pack a list into random-access representation.
INTERN-STRING	Return a string that has been interned into a hash table.

Bit Vectors
Instruction	Purpose
BV-AND	Take the bitwise and of two integers.
BV-OR	Take the bitwise or of two integers.
BV-XOR	Take the bitwise exclusive or of two integers.
BV-SHL	Shift an integer to the left a given number of bits.
BV-SHR	Shift an integer to the right a given number of bits.
SHIFT-LEFT-DIGITS	Shift an integer to the left by a given number of internal digits.
SHIFT-RIGHT-DIGITS	Shift an integer to the right by a given number of internal digits.
BV-SET-BITS	Modify selected bits of an integer.
BV-FIELD	Extract a selected region of the bits of an integer.
BV-MASK	Produce a bit vector consisting of a given number of 1 bits.
BV-MIN	Find the position of the rightmost 1 bit in a bit vector.
BV-MAX	Find the position of the leftmost 1 bit in a bit vector.

Enumerated Species
Instruction	Purpose
ENUM-CHECK n	Test whether a value is in a given range.
PRED	Get the predecessor of a value in an enumerated type.

Boxes and Arrays
Instruction	Purpose
EMPTY-BOX?	Pop a box from the top of the data stack, and push true if the box is empty, false if it is not empty.
MAKE-EMPTY-NONSHARED-BOX	Push a new empty nonshared box onto the data stack.
MAKE-EMPTY-SHARED-BOX	Push a new empty shared box onto the data stack.
ASSIGN	Store an item into a box.
ASSIGN-INIT	Store an item into a box, making it the box's initial value.
ASSIGN-NODEMON	Store an item into a box, but do not run a demon if the box has one attached to it.
MAKE-BOX-EMPTY	Make a box have no content.
MAKE-BOX-EMPTY-NODEMON	Make a box have no content, but do not run any demon that is attached to the box.
CONTENT	Get the content of a box.
CONTENT-TEST	Same as CONTENT, but has a more benign failure mode if the box is empty.
STD-BOX name	Push one of the built-in boxes.
COMPUTED-BOX	Create a computed box.
NONSHARED-ARRAY	Create a new array consisting of nonshared boxes.
SHARED-ARRAY	Create a new array consisting of shared boxes.
FLAVOR	Get the flavor of a box.
BEGIN-PRESERVE	Push the current state (holding bindings of nonshared boxes) onto the state stack.
END-PRESERVE	Pop the state stack and make the popped state be the current state.
ATTACH-DEMON	Attach a demon to a box.
RANK-BOX	Push the "address" (or rank) of a box.
BOX-TO-STRING	Get a string that describes a box.

Unknowns
Instruction	Purpose
NONSHARED-UNKNOWN	Push a new nonshared, unprotected unknown onto the data stack.
SHARED-UNKNOWN	Push a new shared, unprotected unknown onto the data stack.
PROTECTED-NONSHARED-UNKNOWN	Push a new nonshared, protected unknown onto the data stack.
PROTECTED-SHARED-UNKNOWN	Push a new shared, protected unknown onto the data stack.
BIND-UNKNOWN	Bind an unknown to a value.
UNKNOWN?	Test whether an item is an unknown.
PROTECTED-UNKNOWN?	Test whether an item is a protected unknown.
UNPROTECTED-UNKNOWN?	Test whether an item is an unprotected unknown.
SAME-UNKNOWN?	Test whether two things are the same unbound unknown.

Tagging and Untagging Items
Instruction	Purpose
WRAP	Tag an item with a species.
WRAP-FUN k	Tag an item with a species.
WRAP-NUMBER k	Tag a number with a species that is consistent with its representation.
UNWRAP	Remove a species tag from an item, and get the tag.
ATTACH-ITAG n	Tag an item with an integer tag.
ATTACH-COMPUTED-ITAG	Tag an item with an integer tag.
GET-ITAG	Get the integer tag of an item that was created using ATTACH-ITAG.
TEST-ITAG n	Check for a certain integer tag on a tagged item.
REMOVE-ITAG	Remove the tag from an item that is tagged with an integer tag.
SPLIT-ITAGGED	Get both the integer tag and the tagged item from an item that was created by a ATTACH-ITAG instruction.

Branches and local labels
Instruction	Purpose
LOC-LABEL n	Label the next instruction by local label n.
GOTO L	Jump to the instruction just after local label L.
PAIR-GOTO L n	Same as p PAIR instructions followed by GOTO L.
GOTO-IF-FALSE L	Pop the data stack, and jump to the instruction just after local label L if the popped value is false or 0 or []. Only a Natural or Integer 0 is recognized as 0.
GOTO-IF-FALSE-LEAVE L	This is similar to GOTO-IF-FALSE L, but it leaves the value that was just examined on the stack.
AND-SKIP L	Look at the top of the data stack. If it is false, leave that value on the data stack and jump to local label L. If the stack top is true, then pop the stack and do not do the jump.
OR-SKIP L	Look at the top of the data stack. If it is true, leave that value on the data stack and jump to local label L. If the stack top is false, then pop the stack and do not do the jump.

Functions and Function Application
Instruction	Purpose
FUNCTION L	Build a new function.
APPLY	Apply a function to a parameter.
TAIL-APPLY	Apply a function to a parameter. But pop the calling function from the run-time stack before pushing information about this new function.
PAIR-APPLY n	Equivalent to n PAIR instructions followed by an APPLY instruction.
PAIR-TAIL-APPLY n	Equivalent to n PAIR instructions followed by a TAIL-APPLY instruction.
SHORT-APPLY	Apply a function to a parameter, but only run it for a short time before cutting it off.
QEQ-APPLY	Apply a restricted equality testing function to a pair of items.
RETURN	Return from a function application.
INVISIBLE-RETURN	Return from a function application.
CALL-LOCAL L	Push the address of the instruction that follows this one onto the return address stack and jump to local label L.
RETURN-LOCAL	Pop the return-address stack and jump to the popped address.

Lazy Evaluation
Instruction	Purpose
TEST-NOT-LAZY	Test whether an item has been evaluated.
TEST-NOT-LAZY-MAYBE	Test whether an item has been evaluated.
LAZY L	Build a promise to evaluate an expression later.
LAZY-RECOMPUTE L	Same as LAZY, but suppress memoization.
LAZY-LIST L	Build a lazy list out of a collection of threads.
LAZY-LIST-RECOMPUTE L	Build a lazy list out of a collection of threads, and suppress memoization.
TOP-FORCE	Force evaluation of an item until it is at least partially known.
FULL-FORCE	Force evaluation of an item until it is fully known.

Using the Environment
Instruction	Purpose
FETCH n	Fetch a binding at index n in the closest local environment.
FINAL-FETCH n	Fetch a binding at index n in the closest local environment. This is the last time this binding will be used by this function, so it can be destroyed.
LONG-FETCH n k	Fetch a binding at index n in the frame that is k frames offset from the closest frame in the local environment.
FINAL-LONG-FETCH n k	Fetch a binding at index n in the frame that is k frames offset from the closest frame in the local environment. This is the last time this binding will be used by this function, so it can be destroyed.
BIND n (name)	Pop the data stack and store the popped value at index n in the closest environment frame.
DEAD-BIND n (name)	Same as a STORE, but this binding will never be used.
BIND-AND-LEAVE n (name)	Same as a STORE, but do not pop the stack. Leave the item that was stored in the environment on the stack.
DEAD-BIND-AND-LEAVE n (name)	Same as a DEAD-STORE, but do not pop the stack. Leave the item that was stored in the environment on the stack.
REBIND n	Same as a BIND, but indicate a modification of an existing entry rather than a new entry.
REBIND-AND-LEAVE n	Same as a STORE-AND-LEAVE, but indicate a modification of an existing entry rather than a new entry.
DEAD-REBIND-AND-LEAVE n	Same as a DEAD-STORE-AND-LEAVE, but indicate a modification of an existing entry rather than a new entry.
DEFINE L n (name)	Similar to a let, but create a promise, and store the promise in the environment.
EXIT-SCOPE n	Remove all bindings after the first n indices from the closest environment frame.

Using the Static Environment and Fetching Globals
Instruction	Purpose
FETCH-GLOBAL n	Fetch a binding from the static environment of the current thread.
DYNAMIC-FETCH-GLOBAL	Fetch a definition directly from the global definition table. The name is given by a label where the name is defined.
OUTER-BINDING	Fetch a definition directly from the global definition table. The name is a string that can be computed by the program.
OUTER-BINDING2	Fetch a definition directly from the global definition table. The name is a string that can be computed by the program.

Failure and Exception Handling
Instruction	Purpose
TEST name	Fail if the type of the data stack is not true. The exception is a standard exception, name.
FAIL	Pop the data stack and fail with the exception that was popped. That is, raise the exception.
FAILC name	Fail with standard exception name.
PROPAGATE-FAILURE	Repeat the failure that is on the top of the exception stack, as if it was caused by its original source, not as if it was caused by this instruction.
TRY opt L	Create an exception handler.
QUICK-TRY L	Create a restricted exception handler.
TRY-THEN	Indicate success of a try-block.
PUSH-EXCEPTION	Push an exception onto the exception stack.
PUSH-EXCEPTION-PROPAGATABLE	Push an exception onto the exception stack in a way that can be propagate later.
POP-EXCEPTION	Pop the exception stack.
EXCEPTION	Push the top of the exception stack onto the data stack.
PUSH-TRAP	Push the current trap set onto the trap set stack.
POP-TRAP	Pop the trap set stack and make the popped trap set be the current trap set.
TRAP	Indicate that an exception should be trapped if it occurs. (Add it to the current trap set.)
UNTRAP	Indicate that an exception should not be trapped if it occurs. (Remove it from the current trap set.)
WILL-TRAP	Determine whether a given exception is in the current thread's trap set.

Backtracking and Multiple Threads
Instruction	Purpose
BACKTRACK L	Fork the current thread into two, causing one of the threads to wait for the other to complete.
FORK L	Fork the current thread into two, letting both run in parallel.
BEGIN-CUT	Push a cut mark into the control.
END-CUT	Remove the most recently added cut mark from the control.
CUT	Terminate all other threads that were created since the most recent cut mark was pushed onto the control.
WAIT-MILLISECONDS	Cause the current thread to wait for a given number of milliseconds.
PAUSE	Tell the current thread to yield to another thread.
REPAUSE	Same as PAUSE, but indicate that this thread has not made any progress since the last time it did a PAUSE or REPAUSE.
Terminating a thread	A thread terminates itself by failing. See FAIL and FAILC.
TERMINATE	Terminate all threads with a given affiliation.
SUSPEND	Suspend all threads with a given affiliation.
RESUME	Resume all suspended threads with a given affiliation.
SUSPEND-SELF	Cause the current thread to mark itself suspended.
BEGIN-NOSUSPEND	Add 1 to the current thread's no-suspend count.
END-NOSUSPEND	Subtract 1 from the current thread's no-suspend count.
BEGIN-NOTERMINATE	Add 1 to the current thread's no-terminate count.
END-NOTERMINATE	Subtract 1 from the current thread's no-terminate count.
CHECK-FOR-THREAD	Test whether there exists another thread that has a given affiliation.
DETACH	Detach the current thread.
DETACH-AND-CUT	Detach the current thread. Follow this instruction by an implicit `FAILC endThreadX` instruction.

Affiliations
Instruction	Purpose
AFFILIATE	Add an affiliation to the current thread's affiliation set.
UNAFFILIATE	Add an affiliation to the current thread's affiliation set.
CURRENT-AFFILIATIONS	Push a list of the affiliations of the current thread onto the data stack.
INSTALL-AFFILIATIONS	Make the list of affiliations that is on the data stack be this thread's affiliations.

Locking Boxes
Instruction	Purpose
LOCK-BOX	Lock a shared box.
UNLOCK-BOX	Unlock a shared box by decrementing the current thread's lock count for that box.
UNLOCK-BOX-COMPLETELY	Unlock a shared box, setting the current thread's lock count for that box to zero.
UNLOCK-ALL	Remove all locks held by the current thread.
LOCKED-BOX	Test whether a shared box is locked by another thread.

System Calls and Related Functions
Instruction	Purpose
OPEN-OUTFILE	Create a SysOutfile object that is tied to a file.
CLOSE-FILE	Close a SysOutfile.
PRINT-CHAR	Print a character on a file.
PRINT	Print a list of strings on a file.
FLUSH-FILE	Flush the output buffer of a SysOutfile.
OUTFILE-TO-STRING	Convert a SysOutfile value to a string that describes it, by describing the file to which it is tied.
READ-FILE	Get the content of a file.
CHDIR	Change the current working directory.
RENAME-FILE	Remove a file.
UNLINK-FILE	Remove a file.
RMDIR	Remove a directory.
MKDIR	Create a directory.
DIRLIST	Get a list of all of the files in a given directory.
SYM-LINK	Create a symbolic link.
READ-LINK	Read a symbolic link.
STAT-FILE	Get information about the status of a file.
GET-ENV	Get the value of an environment variable.
PUT-ENV	Modify the value of an environment variable.
OS-ENV	Get the entire operating-system environment.
MILLISECONDS-NOW	Get the number of milliseconds from the Epoch to the current time.
FILE-REF-STRING	Back up a string on disk so that the string can be removed by the garbage collector, if necessary.
REFERENCED-FILES	Determine the files to which the abstract machine currently has references.
PROCESS-NUM	Get the name of the process that is running the abstract machine.
SIGNAL-PROCESS	Send a signal to another process.
CREATE-PROCESS	Send a signal to another process.

Sockets and Network Support
Instruction	Purpose
OPEN-SOCKET	Open a new socket.
CLOSE-SOCKET	Close a socket.
READ-SOCKET-BLOCK	Read from a socket. Block until some data is available.
READ-SOCKET-NOBLOCK	Read from a socket. Do not block if no data is available.
WRITE-SOCKET-BLOCK	Write to a socket. Block until finished writing.
WRITE-SOCKET-NOBLOCK	Write to a socket. Do not block if unable to write.
SOCKET-NUMBER	Return a number that identifies a socket.
IP-ADDRESS	Convert a host name to an IP address.
IP-NAME	Convert an IP address to a host name.

Miscellaneous
Instruction	Purpose
FINALIZER	Attach a procedure to a box that will be done when the box is destroyed.
LINE n	The following section of code is compiled from source line n.
NAME L	Tell the interpreter what to call this section of code.
SNAME	Tell the interpreter what to call this section of code.
BEGIN-VIEW	Begin a section of code that is responsible for taking a snapshot of an item.
END-VIEW	End a section of code that is responsible for taking a snapshot of an item.
LAZY-TO-STRING	Produce a description of a value that has not been computed.
PRIM-TRACE	Set the abstract machine to trace its actions.
CONTINUATION-NAME	Get the name of the function that called the current function.
RAW-SHOW	Dump the internal representation of an item.
SHOW-ENV	Print the current environment on a file.
SHOW-CONFIG	Print the current configuration on a file.
PROFILE	Turn on profiling of abstract machine instructions.
SET-STACK-LIMIT	Set the soft call stack depth limit to a given value.
GET-STACK-LIMIT	Get the current soft call-stack depth limit.
GET-STACK-DEPTH	Get the current depth of the call stack.
SET-HEAP-LIMIT	Set the soft memory size limit to a given value.
GET-HEAP-LIMIT	Get the current soft limit on the memory size.
SET-THREAD-LIMIT	Set the soft limit on the number of threads.
GET-THREAD-LIMIT	Get the current soft limit on the number of threads.
SET-LAZY-LIMIT	Set the soft limit on the depth of deferred evaluations.
GET-LAZY-LIMIT	Get the current soft limit on the depth of deferred evaluations.
GARBAGE-COLLECT	Force a garbage collection. You probably never want to do this.
SUPPRESS-COMPACTIFY	Turn on or off compactification during garbage collection.

Creating New Exceptions and Exception Sets
Declaration	Purpose
@EXCEPTION opt name	Create a new exception or refer to an exception defined in another package.
@NEW-EXCEPTION-SET name	Create a new exception set.
@NEW-SIMPLE-EXCEPTION-SET s mem	Create a new singleton exception set.
@IMPORTED-EXCEPTION-SET name	Refer to an exception set declared in another package.
@EXTEND-EXCEPTION-SET name	Refer to an exception set declared in another package.

Working with Exceptions and Exception Sets
Instruction	Purpose
EXCEPTION-CONST L	Push an exception onto the data stack.
EXCEPTION-WRAP L	Push a structured exception onto the data stack.
EXCEPTION-UNWRAP L	Take apart a structured exception.
EXCEPTION-TEST L	Test whether an exception has a given kind.
EXCEPTION-DESCRIPTION	Get the description of an exception.
EXCEPTION-TO-STRING	Convert an exception to a string that describes it.
EXCEPTION-SET	Push an exception set onto the data stack.
EXCEPTION-SET-EQUAL	Determine whether two exception sets are the same.
EXCEPTION-SET-MEMBER	Determine whether an exception is a member of an exception set.
EXCEPTION-SET-COMPLEMENT	Compute the complement of an exception set.
EXCEPTION-SET-UNION	Compute the union of two exception sets.
EXCEPTION-SET-INTERSECTION	Compute the union of two exception sets.
EXCEPTION-SET-TO-STRING	Convert an exception set to a string that describes it.

Description of Astarte Abstract Machine

Program formats

Package heading

The rest of the package

Numbers in the byte code