Exploring Languages

with Interpreters

and Functional Programming

Chapter 46

**H. Conrad Cunningham**

**04 April 2022**

Copyright (C) 2017, 2018, 2022, H. Conrad Cunningham

Professor of Computer and Information Science

University of Mississippi

214 Weir Hall

P.O. Box 1848

University, MS 38677

(662) 915-7396 (dept. office)

Professor of Computer and Information Science

University of Mississippi

214 Weir Hall

P.O. Box 1848

University, MS 38677

(662) 915-7396 (dept. office)

**Browser Advisory:** The HTML version of this textbook
requires a browser that supports the display of MathML. A good choice as
of April 2022 is a recent version of Firefox from Mozilla.

This is a partially developed chapter.

TODO: - Add goals to intro. - Complete and revise the conditional expression sections as needed (e.g., the compilation subsection does not discuss the handling of labels/addresses sufficiently) - Consider adding separate compilation units and linking of units together

Consider a stack virtual machine [[2]} as a means for executing the ELI Calculator language expressions. The operation of this machine is similar to the operation of a calculator that uses Reverse Polish Notation [3] (or postfix notation) such as the calculators from Hewlett-Packard.

Consider a stack-based virtual machine with a symbolic instruction set defined by the following abstract syntax:

```
data SInstr = SVal Int
| SVar String
| SPop
| SSwap
| SDup
| SAdd
| SMul
deriving (Show, Eq)
```

Suppose the state of the virtual machine consists an *evaluation
stack* of values and a program counter indicating the next
instruction to be executed. Further suppose the above instructions have
the following semantics. The machine executes much like a calculator
that uses “reverse Polish notation”.

`SVal i`

pushes value`i`

onto the top of the evaluation stack.`SVar v`

pushes the value of “variable”`v`

from the current environment onto the top of the evaluation stack. (Here we are simulating a memory with the environment.)`SPop`

removes the top element from the stack. (That is, if the stack from the top is`10:xs`

, then the resulting stack is`xs`

.)`SSwap`

exchanges the top two elements on the stack. (That is, if the stack from the top is`10:20:xs`

, then the resulting stack is`20:10:xs`

.)`SDup`

pushes another copy of the top element onto the stack. (That is, if the stack from the top is`10:xs`

, then the resulting stack is`10:10:xs`

.)`SAdd`

pops the top two elements from the stack, adds the second to the first, and pushes the result back on top of the stack. (That is, if the stack from the top is`10:20:xs`

then the resulting stack is`30:xs`

.)`SMul`

pops the top two elements from the stack, multiplies the second times the first, and pushes the result back on top of the stack. (That is, if the stack from the top is`10:20:xs`

then the resulting stack is`200:xs`

.)

We extend this instruction set later to provide other operations.

We can define a simple skeletal execution mechanism for the Stack
Virtual Machine as follows. Function `execSInstr`

takes the state,
environment, and instruction and returns the modified state and
environment. (This version does not modify the environment, but a
version in the future may do so.)

```
data SState = SState [Int] Int
deriving (Show, Eq)
execSInstr :: SState -> Env -> SInstr -> (SState, Env)
SState es pc) env (SVal i) =
execSInstr (SState (i:es) (pc+1), env)
(SState es pc) env (SVar v) =
execSInstr (case lookup v env of
Just i -> (SState (i:es) (pc+1), env)
Nothing -> error ("Variable " ++ show v ++ " undefined")
SState es pc) env SPop =
execSInstr (SState es pc, env) -- REPLACE
(SState es pc) env SSwap =
execSInstr (SState es pc, env) -- REPLACE
(SState es pc) env SDup =
execSInstr (SState es pc, env) -- REPLACE
(SState es pc) env SAdd =
execSInstr (case es of
:l:xs) -> (SState ((l+r):xs) (pc+1), env)
(r-> error ("Cannot Add. Stack too short: " ++ show es)
_ SState es pc) env SMul = (SState es pc, env) -- REPLACE execSInstr (
```

We can translate the ELI Calculator language to the instruction set
as follows. We call this process *code generation* and call the
whole process of converting from source code to the instruction set
*compilation*.

We consider compilation of the Calculator langauge to the stack virtual machine in Exercise Set A.

TODO: Does reference [1] fit here?

TODO

The source code module for this section is in file SInstr-2.hs.

In this exercise set, we consider the Stack Virtual Machine and translation of the ELI Calculator language’s abstract syntax trees to equivalent sequences of instructions.

Complete the development of the function

`execSInstr`

, adding the code for the`SPop`

,`SSwap`

,`SDup`

, and`SMul`

instructions.Extend the Stack Virtual Machine instruction set (i.e.,

`SInstr`

) to support the extensions to the`Expr`

data type defined in Exercise Set A (i.e.,`Sub`

,`Div`

,`Neg`

,`Min`

, and`Max`

). The operators take top value as their*right*operands and the value under that as the*left*operand.Develop a Haskell function

`execSeq :: SState -> Env -> [SInstr] -> (SState, Env)`

that executes a sequence of Stack Virtual Machine instructions given the initial state and environment. (Although the machine in this case study so far does not modify the environment, allow for the future possibility of modification. A later exerces may extend the ELI Calculator language to add assignment statements, imperative loops, and variable and function declarations.)

Also develop a function

`exec`

that executes a sequence of instructions from an initially empty stack with the given environment and returns the result on top of the stack after execution. (You may use`execSeq`

.)`exec :: Env -> [SInstr] -> Int`

Develop a Haskell function

`compile :: Expr -> [SInstr]`

that translates the extended expression tree from Exercise Set A to a sequence of Stack Virtual Machine instructions as extended in this exercise set.

Develop a Haskell function

`compGo`

that takes an expression tree, simplifies, compiles, and executes it using the given environment. You may use the functions`exec`

and`compile`

from the previous exercises.`compGo :: Env -> Expr -> Int`

Let’s examine how to extend the ELI Calculator language to include comparisons and conditional expressions.

TODO: This was introduced as a operator in a previous chapter.

Suppose that we redefine `Expr`

to
include binary operators `Eq`

(equality)
and `Lt`

(less-than comparison), logical unary operator `Not`

, and the
ternary conditional expression `If`

(if-then-else).

```
data Expr = ...
| Eq Expr Expr
| Lt Expr Expr
| Not Expr
| If Expr Expr Expr
...
deriving Show
```

This extended language does not have Boolean values. We represent “false” by integer 0 and “true” by a nonzero integer, primarily by 1.

We express the semantics of the various ELI Calculator language expressions as follows:

`Eq l r`

evaluates to the value 1 if`l`

and`r`

have the same value and to 0 otherwise.`Lt l r`

evaluates to the value 1 if the value of`l`

is smaller then the value of`r`

and to 0 otherwise.`Not i`

evaluates to 1 if`i`

is zero and evaluates to 0 if`i`

is nonzero.`If c l r`

first evaluates`c`

; if`c`

is nonzero, the`if`

evaluates to the value of`l`

; otherwise the`if`

evaluates to the value of`r`

.

TODO: This discussion in the remainder of the Conditional Expression section is not complete! In particular, the discussion of labels/addresses must be clarified and expanded—probably changed.

Suppose we redefine `SInstr`

, the
Stack Virtual Machine to include the new instructions:

```
data SInstr = ...
| SEq
| SLt
| SLnot
| SLabel String
| SGo String
| SIfZ String
| SIfNZ String
deriving (Show, Eq)
```

These Stack Virtual Machine instructions execute as follows:

`SEq`

pops the top two values from the stack; if the values are equal, it pushes a`1`

onto the stack; otherwise, it pushes a`0`

. (For example, if the stack from the top is`3:4:xs`

, the resulting stack is`0:xs`

.)`SLt`

pops the top two values from the stack; if the second value is smaller than the top value, it pushes a`1`

onto the stack; otherwise, it pushes a`0`

. (For example, if the stack from the top is`3:4:xs`

, the resulting stack is`0:xs`

.)`SLnot`

pops the top value from the stack; if the top is`0`

, it pushes`1`

back onto the stack; if it is nonzero, it pushed`0`

back onto the stack. (For example, if the stack from the top is`0:xs`

, the resulting stack is`1:xs`

. If the stack is`7:xs`

, then the result is`0:xs`

.)`SLabel n`

does not change the stack. It is a pseudo-instruction to enable a jump to this point in the program using label`n`

.`SGo n`

makes the next instruction to be executed the one labelled`n`

; it does not change the stack.`SIfZ n`

pops the value from the top of the stack; if this value is zero, then the next instruction executed will be the one labelled`n`

; otherwise the next instruction is the one following the`SIfZ`

instruction.`SIfNZ n`

pops the value from the top of the stack; if this value is nonzero, then it makes the next instruction executed the one labelled`n`

; otherwise the next instruction is the one following the`SIfNZ`

instruction.

TODO

We can translate the expression

`If (Eq (Var "x") (Val 1)) (Val 10) (Val 20) `

to a sequence of Stack Virtual Machine instructions such as:

```
SVar "x", SVal 1, SEq, SIfZ "else", SVal 10, SGo "end",
[ SLabel "else', SVal 20, SLabel "end" ]
```

Of course, each `If`

needs a
unique set of labels.

TODO

Extend the

`eval`

function to support the`Eq`

,`Lt`

,`Not`

, and`If`

operators.Extend the

`simplify`

function to support the`Eq`

,`Lt`

,`Not`

, and`If`

operators.Extend the data type

`Expr`

and the`eval`

function to support the other comparison operators`Ne`

(not equal),`Le`

(less or equal),`Gt`

(greater than), and`Ge`

(greater or equal) and the logical operators`And`

and`Or`

.Extend the

`simplify`

function to support the comparison operators`Ne`

,`Le`

,`Gt`

, and`Ge`

and the logical operators`And`

and`Or`

added in the previous exercise.(UNFINISHED) Extend the

`execSInstr`

,`execSeq`

, and`exec`

functions from Exercise Set C to include the new Stack Virtual Machine instructions.(UNFINISHED) Extend the

`compile`

and`compileGo`

functions from Exercise Set C to include support for`Eq`

,`Lt`

, and`Not`

.(UNFINISHED) Extend the

`compile`

and`compileGo`

functions from the previous exercise to include expressions`Ne`

,`Le`

,`Gt`

,`Ge`

,`And`

,`Or`

, and`If`

. Each of these may need to be translated to a sequence of Stack Virtual Machine instructions.

For the general acknowledgements for the ELI Calculator case study and Chapters 41-46 through Spring 2019, see the Acknowledgements section of Chapter 41.

I retired from the full-time faculty in May 2019. As one of my post-retirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional separately developed materials, reformatting the document (e.g., using CSS), constructing a unified bibliography (e.g., using citeproc), and improving the build workflow and use of Pandoc.

I maintain this chapter as text in Pandoc’s dialect of Markdown using embedded LaTeX markup for the mathematical formulas and then translate the document to HTML, PDF, and other forms as needed.

TODO

[1]

C.
L. Hamblin. 1962. Translation to and from Polish
Notation. *The Computer Journal* 5, 3 (1962),
210–213. Retrieved from https://doi.org/10.1093/comjnl/5.3.210

[2]

Wikpedia: The Free Encyclopedia. 2022. Stack
machine. Retrieved from https://en.wikipedia.org/wiki/Stack_machine

[3]

Wikpedia: The Free Encyclopedia. 2022. Reverse
polish notation. Retrieved from https://en.wikipedia.org/wiki/Reverse_Polish_notation