Description of an Abstract Machine and Its Interpreter

Introduction

This describes a simple byte-code language designed as a target language for compilers. This is not intended to be a general purpose byte code. The languages that can be compiled into this byte code are simple, and the programs must be fairly small. (For example, there can be no more than 256 integer constants or global variables.)

Nonetheless, this abstract machine provides some features that are not used by the C- language. For example, it handles real numbers, which C- does not support. Obviously, you will not use those extra features.

Architecture

Global variables

This abstract machine maintains an array of global variables. Each member of the array occupies a given number of consecutive words. An integer occupies M_SIZE_INTEGER words, a real number occupies M_SIZE_REAL words and an array occupies M_SIZE_ARRAY words. The variables of the array are accessed by indicating a word number, starting at 0. For example, if the array starts with a real number, then an integer and then another integer, the third variable (an integer) is found at index M_SIZE_REAL + M_SIZE_INTEGER.

Constant tables

The abstract machine has two constant tables, one holding integer constants and one holding real constants. Constants in the tables are referred to by their index, starting at 0. Each table has room for 256 constants.

The stack

The primary data structure is a stack. Operations such as addition and subtraction work on the stack. For example, the addition instructions pop two numbers from the stack and push their sum. Parameters and local variables are also stored in the stack.

Each function has a frame in the stack holding its local information. The frame has the following form.

The interpreter manages the stack frames automatically. For example, it sets up the return address and number of parameter words, and you do not need to pay attention to it. But you should note that parameters and local variables are stored in different places, so it is important to keep track whether a given variable is a parameter or a local variable.

Parameters and local variables occupy an amount of space according to their sizes, and are obtained by word number, starting at 0 for the first one. For example, if the first local variable is an array and the second is a real number, then the third local variable is found at index M_SIZE_ARRAY + M_SIZE_REAL.

Input flag

A flag tells whether the most recent input instruction failed. It can be tested by a conditional branch instruction.

Program structure

This part describes the byte code. It uses constant names such as MS_START and M_INTEGER_ADD that are names for integers. They are defined in machinedefs.h. Instructions whose names begin with MS begin sections of the program or describe general characteristics of a program. Instructions whose names begin with M_ are executable instuctions.

A program is a sequence of sections, each consisting of some number of bytes. Each section is either a constant section, a function section or a variable section. Each instruction that starts a section has a name that begins with MS.

Strings

In some places instructions must include null-terminated strings. That is a sequence of bytes ended by a byte that holds 0 (the null character).

Start function

You must indicate which function the interpreter should call initially.

Constant sections

A constant section is used to define an integer or real constant. It has one of the following forms.

Function sections

A function section is used to define a function. It has the following form.

Global variable sections

Global variable sections are used for defining global variables or arrays.

Executable instructions

These instructions are used in the body of a function. The one-byte instructions consist of only the operation code, one byte long. The two-byte instructions have an operation code followed by a one-byte parameter.

These instructions get their operands from the stack, and put their results on the stack. The top of the stack is shown, top to bottom, with the possibility that there is more underneath that. What is in the stack after column replaces what is in the stack before column. For example, the integer subtraction instruction is described as follows.

Instruction	Stack before	Stack after	Remark
M_INTEGER_SUBTRACT	n m	m-n	Pop two integers and push their difference.

This indicates that the top of the stack holds n, and m is just beneath that. This instruction pops n and m from the stack and then pushes m-n. There can be other things beneath m on the stack, and they are not altered.

One byte instructions: Stack manipulation
Instruction	Stack before	Stack after	Remark
M_POP_INTEGER	x		Pop one integer from the stack.
M_POP_REAL	x		Pop one real number from the stack.
M_POP_ARRAY	x		Pop one array from the stack.
M_DUP_INTEGER	x	x x	Duplicate the integer on top of the stack.
M_DUP_REAL	x	x x	Duplicate the real number on top of the stack.
M_DUP_ARRAY	x	x x	Duplicate the array on top of the stack.

One byte instructions: Integer arithmetic
Instruction	Stack before	Stack after	Remark
M_INTEGER_ADD	n m	m+n	Pop two integers and push their sum.
M_INTEGER_SUBTRACT	n m	m-n	Pop two integers and push their difference.
M_INTEGER_MULTIPLY	n m	m*n	Pop two integers and push their product.
M_INTEGER_DIVIDE	n m	m/n	Pop two integers and push their integer quotient. See M_INTEGER_MOD for details. It is an error if n = 0.
M_INTEGER_MOD	n m	m mod n	Pop two integers m and n and push the remainder when m is divided by n. It is an error if n = 0. If this instruction produces remainder r and the integer divide instruction produces quotient q then, m = qn + r. If n > 0 then 0 <= r < n. If n < 0 then n < r <= 0.

One byte instructions: Real arithmetic
Instruction	Stack before	Stack after	Remark
M_REAL_ADD	y x	x+y	Pop two real numbers and push their sum.
M_REAL_SUBTRACT	y x	x-y	Pop two real numbers and push their difference.
M_REAL_MULTIPLY	y x	x*y	Pop two real numbers and push their product.
M_REAL_DIVIDE	y x	x/y	Pop two real numbers and push their quotient. It is an error if y = 0.0.

One byte instructions: Comparisons
Instruction	Stack before	Stack after	Remark
M_COMPARE_INTEGERS	n m	c	Compare integers m and n and push -1 if m < n, 0 if m = n and 1 if m > n. The value c pushed is an integer.
M_COMPARE_REALS	y x	c	Compare integers x and y and push -1 if x < y, 0 if x = y and 1 if x > y. The value c pushed is an integer.

One byte instructions: Arrays
Instruction	Stack before	Stack after	Remark
M_MAKE_INTEGER_ARRAY	n	A	Pop integer n and push a new array A of n integers.
M_MAKE_REAL_ARRAY	n	A	Pop integer n and push a new array A of n real numbers.
M_DELETE_ARRAY	A		Pop array A and return the memory that it occupies to the free space pool.
M_INDEX	n A	A[n]	Pop array A and index n and push A[n] where indexing is from 0. (The first member of A is A[0].) The value pushed is an integer if A is an array of integers, and is a real number if A is an array of reals.
M_STORE_INTEGER_INDEXED	x n A		Store A[n] = x, where x is an integer and A is an array of integers. Indexing is from 0. (The first member of A is A[0].)
M_STORE_REAL_INDEXED	x n A		Store A[n] = x, where x is a real number and A is an array of reals. Indexing is from 0. (The first member of A is A[0].)
M_STORE_LEAVE_INTEGER_INDEXED	x n A	x	Store A[n] = x, where x is an integer and A is an array of integers. Indexing is from 0. (The first member of A is A[0].) Leave x on the stack.
M_STORE_LEAVE_REAL_INDEXED	x n A	x	Store A[n] = x, where x is a real number and A is an array of integers. Indexing is from 0. (The first member of A is A[0].) Leave x on the stack.

One byte instructions: Control
Instruction	Stack before	Stack after	Remark
M_RETURN_INTEGER	n		Return to the calling function, with return value n (an integer).
M_RETURN_REAL	r		Return to the calling function, with return value r (a real number).
M_RETURN			Return to the calling function, without a return value.

One byte instructions: Input and output
Instruction	Stack before	Stack after	Remark
M_READ_INTEGER		v	Read an integer v from standard input and push it. On success set the input failure flag false. On failure set the input failure flage true and push 0.
M_READ_REAL		v	Read a real number v from standard input and push it. On success set the input failure flag false. On failure set the input failure flage true and push 0.0.
M_READ_CHAR		v	Read a character from standard input and push its ascii code v (an integer). At end of file push 0. Set the input failure flag false on success and true if a real number could not be read.
M_WRITE_INTEGER	v		Pop integer v and write it in decimal to standard output.
M_WRITE_REAL	v		Pop real number v and write it in decimal to standard output.
M_WRITE_CHAR	v		Pop v and write the character whose ascii code is v to standard output.

Two byte instructions: Constants
Instruction	Stack before	Stack after	Remark
M_PUSH_INTEGER n		n	Push integer n onto the stack. Note that n is a one byte integer. It must be an integer from 0 to 255. To push other integers, see M_PUSH_INTEGER_CONSTANT.
M_PUSH_INTEGER_CONSTANT k		n	Push integer constant number k onto the stack.
M_PUSH_REAL_CONSTANT k		r	Push real constant number k onto the stack.

Two byte instructions: Allocating variables
Instruction	Stack before	Stack after	Remark
M_ALLOC k			Push k empty words onto the stack. Use this to allocate space for local variables.
M_DEALLOC k			Pop k words from the stack.

Two byte instructions: Fetching and storing local variables
Instruction	Stack before	Stack after	Remark
M_FETCH_LOCAL_INTEGER k		n	Push the value n of the integer variable located at offset k in the local variable section of the current stack frame.
M_FETCH_LOCAL_REAL k		r	Push the value r of the real variable located at offset k in the local variable section of the current stack frame.
M_FETCH_LOCAL_ARRAY k		A	Push the array A stored at at offset k in the local variable section of the current stack frame.
M_STORE_LOCAL_INTEGER k	n		Pop integer n from the stack and store n into the local variable at offset k in the local variable section of the current stack frame.
M_STORE_LOCAL_REAL k	r		Pop real number r from the stack and store r into the real variable at offset k in the local variable section of the current stack frame.
M_STORE_LOCAL_ARRAY k	A		Pop array A from the stack and store A into the local variable at offset k in the local variable section of the current stack frame.

Two byte instructions: Fetching and storing parameters
Instruction	Stack before	Stack after	Remark
M_FETCH_PARAM_INTEGER k		n	Push the value n of the integer variable located at offset k in the parameter section of the current stack frame.
M_FETCH_PARAM_REAL k		r	Push the value r of the real variable located at offset k in the parameter section of the current stack frame.
M_FETCH_PARAM_ARRAY k		A	Push the array A stored at at offset k in the parameter section of the current stack frame.
M_STORE_PARAM_INTEGER k	n		Pop integer n from the stack and store n into the variable at offset k in the parameter section of the current stack frame.
M_STORE_PARAM_REAL k	r		Pop real number r from the stack and store r into the real variable at offset k in the parameter section of the current stack frame.
M_STORE_PARAM_ARRAY k	A		Pop array A from the stack and store A into the variable at offset k in the parameter section of the current stack frame.

Two byte instructions: Fetching and storing global variables
Instruction	Stack before	Stack after	Remark
M_FETCH_GLOBAL_INTEGER k		n	Push the value n of the integer variable located at offset k in the global variable array.
M_FETCH_GLOBAL_REAL k		r	Push the value r of the real variable located at offset k in the global variable array.
M_FETCH_GLOBAL_ARRAY k		A	Push the array A stored at at offset k in the global variable array.
M_STORE_GLOBAL_INTEGER k	n		Pop integer n from the stack and store n into the variable at offset k in the global variable array.
M_STORE_GLOBAL_REAL k	r		Pop real number r from the stack and store r into the real variable at offset k in the global variable array.
M_STORE_GLOBAL_ARRAY k	A		Pop array A from the stack and store A into the variable at offset k in the global variable array.

Two byte instructions: Labels and jumps
Instruction	Stack before	Stack after	Remark
M_LABEL k			Label the next non-label instruction as label k. See the branch instructions (M_GOTO, etc.)
M_GOTO k			Jump to label k. The label is marked using a M_LABEL instruction. The jump can be either forward or backward.
M_GOTO_IF_ZERO k	n		Jump to label k if the top n of the stack is 0. The stack must have an integer on top.
M_GOTO_IF_NOT_ZERO k	n		Jump to label k if the top n of the stack is not 0. The stack must have an integer on top.
M_GOTO_IF_POSITIVE k	n		Jump to label k if the top n of the stack is a positive integer.
M_GOTO_IF_NOT_POSITIVE k	n		Jump to label k if the top n of the stack is not a positive integer.
M_GOTO_IF_NEGATIVE k	n		Jump to label k if the top n of the stack is a negative integer.
M_GOTO_IF_NOT_NEGATIVE k	n		Jump to label k if the top n of the stack is not a negative integer.
M_GOTO_IF_FAILED k			Jump to label k if the last input instruction failed.
M_GOTO_IF_EOF k			Jump to label k if the standard input is at the end of file.

Calling functions
Instruction	Stack before	Stack after	Remark
M_CALL k name	param n ... param 1	result	Value k is one byte and name is a null-terminated string. Call the function whose name is name. That function can be defined anywhere in the byte code, possibly after the function that performs this call. k must be the number of words in the list of parameters. The immediate consequence of this instruction is to push a new stack frame onto the stack and begin running function name. When the function returns, the parameters (k words) are popped and the result of the function (if there is one) is left on top of the stack. If there is no return value, then there will be no result on top of the stack.

Example 1

Program

  int g;

  int fun(int y)
  {
    return y+1;
  }

  void main(void)
  {
    int x;
    g = 5;
    x = 1000;
    output(fun(g+x));
  }

  MS_START                    --Start with main. So, when this
  m                           --function is run, the interpreter
  a                           --will run function main.
  i
  n
  \0
  MS_INTEGER_GLOBAL           --Create global variable g.
  MS_FUNCTION                 --START FUNCTION fun.
  f                           --What follows is the executable code
  u                           --for fun.
  n
  \0
  M_FETCH_PARAM_INTEGER       --Fetch y onto the stack.
  \0
  M_PUSH_INTEGER              --Push integer 1 onto the stack.
  \1
  M_INTEGER_ADD               --This leaves y+1 on the stack.
  M_RETURN_INTEGER            --Return the value y+1 that is on the stack.
  MS_END                      --End of function fun.
  MS_FUNCTION                 --START FUNCTION main.
  m
  a
  i
  n
  \0
  M_ALLOC                     --Allocate one word for local variable x.
  \1
  M_PUSH_INTEGER              --Push 5 onto the stack.
  \5
  M_STORE_GLOBAL_INTEGER      --Store 5 into global variable g.
  \0
  M_PUSH_INTEGER_CONSTANT     --Push 1000 onto the stack.
  \0
  M_STORE_LOCAL_INTEGER       --Store 1000 into local variable x.
  \0
  M_FETCH_GLOBAL_INTEGER      --Fetch global variable g.
  \0
  M_FETCH_LOCAL_INTEGER       --Fetch local variable x.
  \0
  M_INTEGER_ADD               --Now the stack holds g+x.
  M_CALL                      --Call fun with 1 parameter. The parameter
  \1                          --is on top of the stack.
  f
  u
  n
  \0
  M_WRITE_INTEGER             --Print the result that fun returned.
  M_PUSH_INTEGER              --Push 10, a newline character.
  \10
  M_WRITE_CHAR                --Write a newline character.
  M_DEALLOC                   --Deallocate the local variable x.
  \1
  M_RETURN                    --Return from main.
  MS_END                      --End of main.
  MS_INTEGER_CONSTANT         --First integer constant, 1000.
  1
  0
  0
  0
  \0

Example 2

Program

  int gcd(int u, int v)
  {
    if(v == 0) return u;
    else return gcd(v, u-u/v*v);
  }

  void main(void)
  {
    int x; int y;
    x = input();
    y = input();
    while(x >= 0) {
      output(gcd(x,y));
      x = input();
      y = input();
    }
  }

  MS_START                    --Start at main.
  m
  a
  i
  n
  \0
  MS_FUNCTION                 --Begin function gcd.
  g
  c
  d
  \0
  M_FETCH_PARAM_INTEGER       --Push v onto the stack (param 1).
  \1
  M_PUSH_INTEGER              --Push 0 onto the stack.
  \0
  M_COMPARE_INTEGERS          --Compare v and 0.
  M_GOTO_IF_NOT_ZERO          --Jump to label 0 if v is not equal to 0.
  \0
  M_FETCH_PARAM_INTEGER       --Push u onto the stack (param 0).
  \0
  M_RETURN_INTEGER            --Return u.
  M_LABEL                     --Begin of else part of the if.
  \0
  M_FETCH_PARAM_INTEGER       --Push v onto the stack (param 1).
  \1                          --Stack(top to bottom): v
  M_FETCH_PARAM_INTEGER       --Push u onto the stack (param 0).
  \0                          --Stack(top to bottom): u  v
  M_FETCH_PARAM_INTEGER       --Push u onto the stack (param 0).
  \0                          --Stack(top to bottom): u  u  v
  M_FETCH_PARAM_INTEGER       --Push v onto the stack (param 1).
  \1                          --Stack(top to bottom): v  u  u  v
  M_INTEGER_DIVIDE            --Stack(top to bottom): u/v  u  v
  M_FETCH_PARAM_INTEGER       --Push v onto the stack (param 1)
  \1                          --Stack(top to bottom): v  u/v  u  v 
  M_INTEGER_MULTIPLY          --Stack(top to bottom): (u/v)*v  u  v
  M_INTEGER_SUBTRACT          --Stack(top to bottom): (u-(u/v)*v)  v
  M_CALL                      --Call gcd with two parameters.
  \2                          --They are on the stack.
  g
  c
  d
  \0
  M_RETURN_INTEGER            --Return the result that gcd produces.
  MS_END                      --End of function gcd.
  MS_FUNCTION                 --BEGIN FUNCTION main
  m
  a
  i
  n
  \0
  M_ALLOC                     --Allocate space for x and y.
  \2
  M_READ_INTEGER              --Read an integer and push it onto the stack.
  M_STORE_LOCAL_INTEGER       --Store it into x (local 0).
  \0 
  M_READ_INTEGER              --Read an integer and push it onto the stack.
  M_STORE_LOCAL_INTEGER       --Store it into y (local 1).
  \1
  M_LABEL                     --Top of the while loop.
  \0
  M_FETCH_LOCAL_INTEGER       --Fetch x (local 0).
  \0
  M_GOTO_IF_NEGATIVE          --Exit the loop if x is negative.
  \1
  M_FETCH_LOCAL_INTEGER       --Fetch x (local 0).
  \0
  M_FETCH_LOCAL_INTEGER       --Fetch y (local 0).
  \1
  M_CALL                      --Call gcd with 2 parameters, on the stack.
  \2
  g
  c
  d
  \0
  M_WRITE_INTEGER             --Write the result that gcd produces.
  M_PUSH_INTEGER              --Push a newline character.
  \10
  M_WRITE_CHAR                --Print the newline character.
  M_READ_INTEGER              --Read in integer and push it.
  M_STORE_LOCAL_INTEGER       --Store it into x (local 0).
  \0
  M_READ_INTEGER              --Read in integer and push it.
  M_STORE_LOCAL_INTEGER       --Store it into y (local 1).
  \1
  M_GOTO                      --Jump to label 0, the top of the while loop.
  \0
  M_LABEL                     --Here is the bottom of the while loop.
  \1
  M_DEALLOC                   --Deallocate the local variables.
  \2
  M_RETURN                    --And return.
  MS_END                      --End of main.

The assembly language

The assemble language allows you to use a text file, which you can check and read. Each line contains just one instruction.

Comments start at a semicolon and go for the rest of the line.

In the instructions, k stands for an integer constant, written in decimal, and str stands for a string. Strings are written without quotes, and are delimited by white space or the comment marker ';'. You cannot put a space in a string. Real numbers are written in decimal notation suitable as input to atof.

Sections

The following are the forms of sections. For the meaning, see the corresponding byte-code above.

Executable instructions

Example 1

The following is example 1 from above, but written in assembly language. This is a text file.

  MS_START main             ;start at main
  MS_INTEGER_GLOBAL
  MS_FUNCTION fun           ;begin fun
  M_FETCH_PARAM_INTEGER 0
  M_PUSH_INTEGER  1
  M_INTEGER_ADD 
  M_RETURN_INTEGER
  MS_END 
  MS_FUNCTION main          ;begin main
  M_ALLOC 1
  M_PUSH_INTEGER  5
  M_STORE_GLOBAL_INTEGER 0
  M_PUSH_INTEGER_CONSTANT 0
  M_STORE_LOCAL_INTEGER 0
  M_FETCH_GLOBAL_INTEGER 0
  M_FETCH_LOCAL_INTEGER 0
  M_INTEGER_ADD
  M_CALL 1 fun
  M_WRITE_INTEGER
  M_PUSH_INTEGER 10
  M_WRITE_CHAR
  M_DEALLOC 1
  M_RETURN
  MS_END 
  MS_INTEGER_CONSTANT 1000

Using the interpreter

The interpreter is available as a C program called machine.c. If the executable code for machine.c is in file machine, then command line

  machine myfile.m

  machine -t myfile.m

  machine -T myfile.m

An assembler and disassembler are also available. If you compile assemble.c to executable file assemble, and compile disassemble.c to executable file disassemble, then

  dissassemble myfile.m myfile.i

  assemble myfile.i myfile.m

Get the following files.

• machine.c
• disassemble.c
• assemble.c
• machinetypes.h
• machinedefs.h
• instinfo.c (needed by machine.c, disassemble.c, assemble.c)