% $Id: float-vm-description.tex,v 1.21 2023/03/31 13:22:08 leavens Exp leavens $
\documentclass[11pt,letterpaper]{article}
\input{macros}
\thispagestyle{headings}
\newcommand{\CLASS}{COP 3402 --- Systems Software}
\markboth{\CLASS}{\CLASS}
\newcommand{\CHANGED}[1]{\textbf{#1}}
\newcommand{\BP}{\textsf{BP}}
\newcommand{\SP}{\textsf{SP}}
\newcommand{\PC}{\textsf{PC}}
\newcommand{\IR}{\textit{IR}}
\newcommand{\STACKNAME}{\textrm{stack}}
\newcommand{\STACK}[1]{\ensuremath{\STACKNAME[#1]}}
\newcommand{\AND}{\ensuremath{\:\wedge\:}}
\newcommand{\GETS}{\ensuremath{\leftarrow}}
\newcommand{\IFO}[2]{\textrm{\textbf{if} \ensuremath{#1} \textbf{then}
    \{\ensuremath{#2}\} }}
\newcommand{\IF}[3]{\textrm{\textbf{if} #1 \textbf{then} #2 \textbf{else} #3}}
\newcommand{\EQUALS}{\ensuremath{=}} % or {\ensuremath{\:\texttt{==}\:}}
\newcommand{\ROUND}[1]{\ensuremath{\textrm{round}(#1)}}
\newcommand{\TOINT}[1]{\ensuremath{\textrm{toInt}(#1)}}
\newcommand{\TOFLOAT}[1]{\ensuremath{\textrm{toFloat}(#1)}}
\newcommand{\LITopcode}{1}
\newcommand{\ADDopcode}{16}
%
\title{FLOAT Stack-based VM Description}
\author{Gary T. Leavens \\ Department of Computer Science
  \\ University of Central Florida \\ Leavens@ucf.edu}
\begin{document}
\maketitle
\begin{abstract}
In creating the code generator (for the FLOAT calculator),
we found that the stack machine as described previously (for homework 4) 
needed some revision.
In this document, the changed and revised features (from the homework
4 VM) are \CHANGED{highlighted in bold font}.
The major changes have to do with adapting the VM to deal with
floating point numbers.
\end{abstract}

\section{Overview}

The virtual machine (VM) is a word-addressible stack-based machine
that manipulates both floating-point numbers (C's \KW{float} type) and
integers (C's \KW{int} type).

The following subsections specify the interface between the Unix
operating system (as on Eustis) and the VM as a program.

\subsection{Inputs}

The VM understands the \texttt{-n} command line option,
which turns off the printing of the program and the VM's tracing output;
otherwise the VM prints the program and an execution
trace, on \texttt{stderr}, by default. The execution trace can be
turned off during a program's execution by using the NDB instruction.

The VM takes a single file name as a command line argument;
this file should be the name of a (readable) text file
containing the program that the VM should execute.
For example, if the executable is named \texttt{vm/vm} and the program it
should run is contained in the file named \texttt{test1.vmi} (and
both the input file and the \texttt{vm} subdirectory are in the
current directory),
then the VM should execute the program in the file \texttt{test1.vmi} by executing
the following command in the Unix shell (e.g., at the command prompt on Eustis):

\begin{lstlisting}
  vm/vm test1.vmi
\end{lstlisting}

When the program executes a CHI instruction to read a character, that
character will be read from standard input (\texttt{stdin}). However,
note that if you want the program to read a character, typing a single
character (say \texttt{c}) into the terminal (i.e., to the shell) 
while the program is running will not send that character immediately
to the program, as \texttt{stdin} is buffered.  To send
characters to the program it is best to use a pipe or file redirection
in the Unix shell, for example, to send the two characters \texttt{c}
and \texttt{e} to the VM running the program \texttt{progfile.vmi} one
could use the following command at the Unix shell:

\begin{lstlisting}
  echo ce | vm/vm progfile.vmi
\end{lstlisting}

One could also put those characters in a file 
say \texttt{ce-input.txt} and then to use the following Unix command:
\lstinline!vm/vm progfile.vmi < ce-input.txt!

\subsection{Outputs}

The VM prints its tracing output to the Unix standard error output (\texttt{stderr)}.
However, characters printed using the CHO instruction are 
printed on standard output (\texttt{stdout}).

All error messages (e.g., for division by zero) are sent to
standard error output (\texttt{stderr}).

\subsection{Exit Code}

When the machine halts normally, it exits with a success error code
(zero on Unix).
However, when the machine encounters an error it halts and the program
should exits with a failure error code (non-zero on Unix).

\section{VM Architecture}

The VM is a stack machine that conceptually has
two memory stores: the "stack," which is organized as a LIFO queue of
words and contains the data to be used by instruction evaluation,
and the "code," which is organized as a list of instructions.
The code list contains the instructions for the VM in order of
execution;
however, that order can be changed by executing instructions
(such as jump or call instructions).

\subsection{Registers}

The VM has a few built-in registers\footnote{What we call
``registers'' in this document are simply important concepts that
simulate what would be registers in a hardware implementation of the
virtual machine. In the VM as a C program, these are implemented
as variables.}
used for its execution: The registers are named:

\begin{itemize}
\item
base pointer (\BP), 

\item
stack pointer (\SP), which points to the next location in the stack to
allocate (i.e., one above the current top of the stack), and

\item
program counter (\PC).
\end{itemize}

The use of these registers will be explained in detail below. 

\subsection{Instruction Format}

The Instruction Set Architecture (ISA) of the VM has instructions that
each have two components, which are integers (i.e., they have the C
type int) named as follows:

\begin{tabular}{|l|l|}
\hline
OP &	is the operation code (an unsigned integer) \\
\hline
M  & 	a word, whose type depends on the operator it indicates, either: \\
   &    (a) A C \KW{float} (when the instruction is a LIT instruction, so
that OP is {\LITopcode}) or \\
   &    (b) A C \KW{int} (for all other instructions) \\
\hline
\end{tabular}

The list of instructions and details on their execution appears in Appendix A.
In some instructions the function $\TOINT{w}$ is used, which returns
the value of $\ROUND{f}$, when $w$ represents the float $f$, and
otherwise just the integer value of $w$.
Similarly, $\TOFLOAT{w}$ returns the value of $w$ as a float.

\subsection{VM Cycles}

The VM instruction cycle conceptually does the following for each
instruction:

\begin{enumerate}
\item
  Let $\IR$ be the instruction at the location that PC indicates.
  (Note that $\IR$ could be considered to be the contents of a register.)

\item
  The $\PC$ is made to point to the next instruction in the code list.

\item
The instruction $\IR$ is executed using the ``stack'' memory. (This does
not mean that the instruction is stored in the ``stack.'')
The OP component of this instruction ($\IR$.OP) indicates the operation
to be executed. For example, if $\IR$.OP encodes the instruction ADD,
then the machine adds the top two elements of the stack, popping them
off the stack in the process, and stores the result in the top of the
stack (so in the end $\SP$ is one less than it was at the start). Note
that the arithmetic instructions operate on numbers as in C's \textbf{float}
arithmetic.\footnote{
The VM's arithmetic was changed to be a combination of C's
  \KW{int} and \KW{float} arithmetic in this revision.
}
\end{enumerate}

\subsection{VM Initial/Default Values}

When the VM starts execution, $\BP$, $\SP$, and $\PC$ are all $0$.
This means that execution starts with the "code" element $0$.
Similarly, the initial "stack" store values are all zero ($0$).

\subsection{Size Limits}

The following constants define the size limitations of the VM.
\begin{itemize}
\item
\lstinline!MAX_STACK_HEIGHT! is 2048

\item
\lstinline!MAX_CODE_LENGTH! is 512
\end{itemize}

\subsection{Invariant Properties}

The VM enforces the following invariant properties and will halt with an error
message (written to stderr) if one of them is violated:

\begin{itemize}
\item
  $0 \leq \BP \AND \BP \leq \SP \AND 0 \leq \SP
   \AND \SP < \texttt{MAX\_STACK\_HEIGHT}$
  
\item
   $0 \leq \PC \AND \PC < \texttt{MAX\_CODE\_LENGTH}$
\end{itemize}

Although the VM tracks the format of data written on the stack (as a
\KW{float} or \KW{int}), it tries to convert these types to whatever
is needed for the instruction as needed, and it also allows
writing a location in the stack without regard to the format of the
data that was there previously.

\appendix
\section{Appendix A}

In the following tables, the meta-variable $f$ refers to a C float
used as data, while the meta-variables $p$ refers to
an (unsigned) integer used as an address and $o$ and $m$ are
meta-variables that stand for an (unsigned) integer used as an offset
or count.
If an instruction's M field is notated as $-$,
then its value does not matter (we use \texttt{0} as a
placeholder for such values in examples).
Note that stack[$SP-1$] is the top element of the stack.

\subsection{Basic Instructions}

\begin{tabular}{|r|l|l|p{11cm}|}
\hline
OP   & OP  & M   & Comment \\
Code & Mnemonic & & (Explanation) \\
\hline
0         & NOP & $-$ & do nothing (no-op) \\
\hline
\LITopcode  & LIT  & $f$ & Literal push: $\STACK{\SP} \GETS f$; $\SP \GETS \SP+1$ \\
\hline
2  & RTN  & $-$ & Returns from a procedure and restores the caller's AR: \\
   &      &     & $\PC \GETS \STACK{\SP-1}$;
                  $\BP \GETS \STACK{\SP-2}$; $\SP \GETS \SP - 3$ \\
\hline
3  & CAL  & $p$ & Call the procedure at code index $p$,
                        generating a new activation record
                        and setting $\PC$ to $p$: \\
   &      &     & $\STACK{\SP} \GETS \STACK{\BP}$; // static link \\
   &      &     & $\STACK{\SP + 1} \GETS \BP$; // dynamic link \\
   &      &     & $\STACK{\SP + 2} \GETS \PC$; // return address \\
   &      &     & $\BP \GETS \SP$; $\SP \GETS \SP + 3$; $\PC \GETS p$; \\
\hline
4  & POP  & $-$ & Pop the stack: $\SP \GETS \SP-1$; \\
\hline
5  & PSI  & $-$ & Push the element at address $\STACK{\SP - 1}$
                  on top of the stack: \\
   &      &     & $\STACK{\SP - 1} \GETS \STACK{\TOINT{\STACK{\SP - 1}}}$ \\
\hline
6  & LOD  & $o$ & The value at the address in the top of the stack + offset $o$ is put on top of the stack: \\
&      &     & $\STACK{\SP-1} \GETS \STACK{\TOINT{\STACK{\SP-1}}+o}$ \\
\hline
7  & STO  & $o$ & Store $\STACK{\SP-1}$ into the stack at address
                  $\TOINT{\STACK{\SP-2} + o}$ and pop the stack twice: \\
   &      &     & $\STACK{\TOINT{\STACK{\SP-2}}+o} \GETS \STACK{\SP-1}$;
                  $\SP \GETS \SP-2$ \\
\hline
8  & INC  & $m$ & Allocate $m$ locals on the stack: $\SP \GETS \SP + m$ \\
\hline
9  & JMP  & $o$ & Jump relative to the current
  instruction's code index: \\
   &      &     & $\PC \GETS \PC-1+o$ \\
\hline
10 & JPC  & $o$ & Jump conditionally relative to
  the current instruction's code index: \\
   &      &     & $\IFO{\STACK{\SP-1} \neq 0}{\PC \GETS \PC-1+o}$;
                 $\SP \GETS \SP-1$ \\
\hline
11 & CHO  & $-$ & Output the value in $\STACK{\SP-1}$ (rounded if need be)
                  to standard output as a character and pop: \\
   &      &     & \textbf{putc}($\TOINT{\STACK{\SP-1}}$, \texttt{stdout}); $\SP \GETS \SP-1$ \\
\hline
12 & CHI  & $-$ & Read an integer, as character value,
                  from standard input and push it in the top of the stack, 
                  but on EOF or error, push -1:  \\
   &      &     & $\STACK{\SP} \GETS \textbf{getc}(\texttt{stdin})$;
                  $\SP \GETS \SP+1$ \\
\hline
13 & HLT  & $-$ & Halt the program's execution \\
\hline
14 & NDB  & $-$ & Stop printing debugging output \\
\hline
\end{tabular}

\newpage

\subsection{Arithmetic/Logical Instructions}

For comparisons, note that the integer $0$ represents false
and $1$ represents true. 
That is, the result of a logical operation, such as $A > B$ is defined
as $1$ if the condition was met and $0$ otherwise.
\CHANGED{Arithmetic operations are performed as C's \texttt{float} arithmetic.}\footnote{
\CHANGED{The definition of arithmetic for the arithmetic operators was changed
to \texttt{float} arithmetic in this revision.}}
Errors such as division by $0$ cause the VM to halt
with an appropriate error message printed on stderr.

\begin{tabular}{|r|l|l|p{11cm}|}
\hline
OP   & Number & M & Comment (Explanation) \\
Code & Mnemonic &   &   \\
\hline
15 & NEG  & $-$ & Negate the value in the top of the stack:  \\
   &      &     & $\STACK{\SP-1} \GETS - \TOFLOAT{\STACK{\SP-1}}$ \\
\hline
\ADDopcode & ADD  & $-$ & Add the top two elements in the stack:  \\
   &      &     & $\STACK{\SP-2} \GETS \TOFLOAT{\STACK{\SP-2}} + \TOFLOAT{\STACK{\SP-1}}$;
                  $\SP \GETS \SP-1$ \\
\hline
17 & SUB  & $-$ & Subtract the top element from the 2nd to top one:  \\
   &      &     & $\STACK{\SP-2} \GETS \TOFLOAT{\STACK{\SP-2}} - \TOFLOAT{\STACK{\SP-1}}$; 
                  $\SP \GETS \SP-1$ \\
\hline
18 & MUL  & $-$ & Multiply the top two elements in the stack:  \\
   &      &     & $\STACK{\SP-2} \GETS \TOFLOAT{\STACK{\SP-2}} \times \TOFLOAT{\STACK{\SP-1}}$; 
                  $\SP \GETS \SP-1$ \\
\hline
19 & DIV  & $-$ & Divide the 2nd from top element by the top one:  \\
   &      &     & $\STACK{\SP-2} \GETS \TOFLOAT{\STACK{\SP-2}} / \TOFLOAT{\STACK{\SP-1}}$; 
                  $\SP \GETS \SP-1$ \\
\hline
20 & RND  & $-$ & \CHANGED{Round the result on top of the stack into
  an integer:} \\
   &      &     & $\STACK{\SP-1} \GETS \textrm{round}(\STACK{\SP-1})$; \\
\hline
21 & EQL  & $-$ & Are (the contents of) the top two elements equal? \\
   &      &     & $\STACK{\SP-2} \GETS \TOFLOAT{\STACK{\SP-2}} \EQUALS \TOFLOAT{\STACK{\SP-1}}$; 
                  $\SP \GETS \SP-1$ \\
\hline
22 & NEQ  & $-$ & Are (the contents of) the top two elements different? \\
   &      &     & $\STACK{\SP-2} \GETS \TOFLOAT{\STACK{\SP-2}} \neq \TOFLOAT{\STACK{\SP-1}}$;
                  $\SP \GETS \SP-1$ \\
\hline
23 & LSS  & $-$ & Is (the contents of) the second from the
  top element strictly less than the contents of the top element? \\
   &      &    & $\STACK{\SP-2} \GETS \TOFLOAT{\STACK{\SP-2}} < \TOFLOAT{\STACK{\SP-1}}$; 
                 $\SP \GETS \SP-1$ \\
\hline
24 & LEQ  & $-$ & Is (the contents of) the 2nd from top element no
greater than the contents of the top element?  \\
   &      &     & $\STACK{\SP-2} \GETS \TOFLOAT{\STACK{\SP-2}} \leq \TOFLOAT{\STACK{\SP-1}}$; 
                  $\SP \GETS \SP-1$ \\
\hline
25 & GTR  & $-$ & Is (the contents of) the 2nd from top
  element strictly greater than the contents of the top element?  \\
   &      &     & $\STACK{\SP-2} \GETS \TOFLOAT{\STACK{\SP-2}} > \TOFLOAT{\STACK{\SP-1}}$; 
                  $\SP \GETS \SP-1$ \\
\hline
26 & GEQ  & $-$ & Is (the contents of) the 2nd from top
  element no less than the contents of the top element? \\
   &      &     & $\STACK{\SP-2} \GETS \TOFLOAT{\STACK{\SP-2}} \geq \TOFLOAT{\STACK{\SP-1}}$; 
                  $\SP \GETS \SP-1$ \\
\hline
\end{tabular}

\subsection{VM State Examination Instructions}

These instructions allow the state of the VM to be examined and used
in computation.

\CHANGED{The RBP instruction was added to restore the break pointer
  from the top of the stack.}

\begin{tabular}{|r|l|l|p{11cm}|}
\hline
OP & Number & M & Comment (Explanation) \\
Code & Mnemonic &    &   \\
\hline
27 & PSP  & $-$ & Push $\SP$ (i.e., the address itself) on top of the
stack: \\
   &      &     & $\STACK{\SP} \GETS \SP$; $\SP \GETS \SP+1$ \\
\hline
28 & PBP  & $-$ & Push $\BP$ (i.e., the address itself) on top of the
stack: \\
   &      &     & $\STACK{\SP} \GETS \BP$; $\SP \GETS \SP+1$ \\
\hline
29 & PPC  & $-$ & Push $\PC$ (i.e., the address itself) on top of the
stack: \\
   &      &     & $\STACK{\SP} \GETS \PC$; $\SP \GETS \SP+1$ \\
\hline
30 & JMI  & $-$ & jump to the address on top of the stack: \\
   &      &     & $\STACK{\PC} \GETS \TOINT{\STACK{\SP-1}}$;
                  $\SP \GETS \SP-1$ \\
\hline
31 & \CHANGED{RBP} & $-$ & \CHANGED{restore the break pointer:} \\
   &      &     & \CHANGED{$\BP \GETS \TOINT{\STACK{\SP-1}}$;
                           $\SP \GETS \SP-1$} \\
\hline
\end{tabular}

\subsection{Examples}
As an example, consider the instruction \texttt{ADD 0}, which is input
as the line \texttt{{\ADDopcode} 0}; then assuming $\SP$ is $10$,
this means to place in $\STACK{8}$ the sum of the values
in $\STACK{8}$ and $\STACK{9}$, and then setting $\SP$ to $9$.

As another example: if we have instruction \texttt{LIT 9.0}, 
which is input as the line \texttt{{\LITopcode} 9.0}, 
then this means to push the float $9.0$ on the top of the stack:
$\STACK{\SP} \GETS 9.0$; $\SP \GETS \SP+1$.

\section{Appendix B: Examples}

\subsection{A Simple Example Showing Output Formatting}

The following very simple example shows the expected formatting.
Suppose the input is the following file (\texttt{hw1-test0.vmi}, 
the name of this file is passed to the VM on the Unix command line):

Running the VM with the command line argument \texttt{hw1-test0.vmi}
the following output (written to stderr).
Note that there are two parts to the output: (1)
a listing of the instructions in the program one per line, following a
header, with mnemonics for each instruction and (2) a trace of the
program's execution, following the line \texttt{Tracing ...} (all on
standard error output).  
The trace of execution shows the state of the built-in registers
($\PC$, $\BP$, and $\SP$)
and the stack's values at addresses between $\BP$ and $\SP-1$ (inclusive),
and then it shows the instruction being executed (following the text
\texttt{==> addr: });
this consists of: (a) the address of the instruction being executed,
then (b) the instruction with its mnemonic and M value,
then after showing the instruction being executed (and after the
instruction's execution by the VM) the state is again shown.
The output of the instruction and the
resulting state are show after is each instruction executed.

In this output, words that are floating-point numbers are printed to
look like floating point numbers, and words that are integers are
printed without a decimal point.

\LSTFILE{test0.out}

\section{Future Work}

To better support blocks (sequences of statements with declarations), 
there should be an instruction for entering
a block, which would push $\BP$ on the stack and set $\BP$ to point to
that address ($\SP - 1$).  The RBP instruction already supports exit
from a block.

The VM already understands the distinction between floating point
numbers and integers, but it could also be made to distinguish Boolean
values and print them using ``true'' and ``false''.

\subsection{A Slightly More Involved Example}

The following example is a bit more involved and shows some of the
details of the machine's execution.

\subsubsection{Input File}

The following is the contents of
the file \texttt{test1.vmi}:

\LSTFILE{test1.vmi}

\subsubsection{Output (to stderr)}

Running the VM with the above input produces the following output
on \texttt{stderr} (assuming that the \texttt{-n} option is not used).

\LSTFILE{test1.out}

\end{document}

