view release on metacpan or  search on metacpan

test.pl  view on Meta::CPAN

1. INTRODUCTION

Hundreds of different microcomputers with various architectures are
currently in use. Some of these microcomputers are quite fast but have a
small directly addressable random-access memory. The development of
compilers or cross-compilers from algorithmic high-level languages, file
systems, text editors, and other software tools for all microcomputers
is a very difficult problem. The following technique may be applied for
this purpose: create a single standard architecture and instruction set
for some virtual machine (VM) and design all the software tools for this
VM only; then implement VM interpreters on each particular microcomputer
[1]. This approach, in addition to software standardization, usually
achieves a 3-5 times saving of RAM at the cost of a 2-4 times slowdown
in computations.

The idea of using a VM is not new. Recall the simple stack machines
created by Wirth for the implementation of Pascal [2]. Subsequently
Wirth created a more modern VM design for Modula 2. This VM was
hardware-implemented as the computer LILITH [3]. Similar work is being
carried out at the Computational Center of the Siberian Division of the
Academy of Sciences of the USSR [4].

The first VMs had a fairly primitive design in order to simplify the
interpreter implementation for new computers. For example, the well
known P-code [2] included loading into a stack and unloading from the
stack into RAM, four arithmetic operations, conditional jumps, and a
number of auxiliary instructions (fewer than 10). Although the LILITH
instruction set [3] comprised nearly 250 instructions, most of the codes
were for short instructions packed into one byte with the addresses
(e.g., load into stack a local variable with address 0,1, ..., 15,
dittofor a global variable, etc.). A single action in a high-level
language is executed by several small instructions, while on the other
hand an excessively strong influence of a single language is felt
(Modula 2 in this particular case), and therefore many of the
architectural features are uncomfortable even in related languages.

This paper is a continuation and further development of [5], which
originally proposed a VM architecture and instruction set designed for a
class of algorithmic high-level languages with static type checking
(Pascal, Modula 2, Algol 68, Ada, and similar languages). For this class
of languages, it was possible to standardize the representation of the
main data types, memory allocation schemes, procedure call organization,
and array manipulation. The clear separation of duties and
responsibilities between the compiler from the high-level language to VM
codes and the VM interpreter for a specific computer made it possible to
simplify the VM structure (e.g., items checked in compile time are never
checked again in execution time). The compiling process was
substantially simplified by the use of inverse Polish notation in object
code, the use of a stack for computations, the provision of special
instructions for the most frequent high-level language constructs, and
the orthogonality of the VM instruction set.

Orthogonality of the instruction set is understood in the sense of
uniformity of instruction types and addressing types and absence of
exclusions and nonstandard actions. For instance, if a transfer
instruction may have nine types of sources and three types of
destinations, then there should be a total of 27 transfer instructions.
If there are three types of addition instructions (A + B, A+ := B, A[I]+
:= B), then the same types of instructions should be provided for
multiplication, for logical operations, etc. On ES computers say,
formula generation is a major part of any compiler, because integer
addition is performed by one technique, decimal addition by another
technique, and logical addition by yet another technique; the
instructions AH, SH, MH are provided, while DH (half-word division) is
missing. With an orthogonal design, the instruction set may obviously
include rarely used commands, but this is necessary in the interest of
simpler compiling.

1.1. Modifications. The following aspects of the VM were modified
compared with [5].

a) The register stack was eliminated. The arithmetic expressions are
evaluated in a stack which overlaps the procedure static space (i.e.,
the memory allocated to the procedure identifiers and work area). As a
result, we avoid quantitative restrictions on stack depth, simplify the
call scheme, reduce the variety of instructions, and no longer restrict
the stack top to single-word values.

b) The representation of Boolean and real variables, the coding of
characters and the specification of base registers is not fixed in the
VM description. The compiler should be tuned to a specific VM
interpreter by introducing appropriate interchangeable procedures.

c) The representation of the array ticket is hidden from the compiler.
The array construct is supported by array generation instructions
(allowing multidimensional arrays), array assignments, copy
instructions, creation of arrays from separate elements, evaluation of
array bounds and array element addresses. The compiler always works with
a reference to the array ticket and never overrides standard
instructions to manipulate the ticket attributes. Other VMs provide only
a rudimentary support of array manipulation.

Cross-compilers are currently available for the VH assembler language,
Pascal, and Algol 68; these compilers will be transported to the VM
using generation methods. All the points with explicit ties to a
particular computer architecture and OS have been identified (their
number is quite small). When the software tools are transported to a new
computer, these tie points will be reprogrammed.

The VM is often useful not only from standardization considerations.
Many process control problems and other real-time applications impose
memory constraints, while not more than 10% of programs are
time-critical. It is therefore better to use two cross-compilers in each
system: time-critical programs should be compiled directly into a
special-purpose computer code, while all other programs should be
compiled into virtual computer code with subsequent execution by
interpretation. This technique will save hundreds of thousands of RAM
bytes.

2. THE MAIN VIRTUAL-MACHINE ELEMENTS

We start with an informal description of VM architecture. The formal
model (which is not given here) has been implemented in Algol 68 and may
be used as the basis for VM implementation on various object computers.

The VM architecture includes a set of internal registers and several
types of memory, specifically: program memory, work memory, and a call
stack.

2.1. Internal Registers of the VM Processor. Several registers are
provided (pointers to program and work memory, counters), which are used