Amoeba
Amoeba is the instruction set for the Amoeba virtual processor.
The Amoeba
Processor
The Amoeba processor has the following components:
Environment
The environment is a linked collection of hash maps that associate names with variables.
Variable
An integer container.
Instruction
An opcode specifying an operation and zero to three operands. Operands may be numbers or variables.
(Note: For now we use Instruction = String and use a scanner to extract opcodes and operands.)
Program
An array of instructions to be executed.
Label Table
A hash map that associates labels with program array indices.
Instruction Pointer (ip)
A variable containing the index of the next instruction in the program array to be executed.
Instruction Register (ir)
A variable holding the current instruction being executed or pre-processed.
Pre-processor
The pre-processor reads a program from a specified file.
It loads each line of the file into the next available cell of the program array.
If an instruction is a label declaration, then it associates the label with the index of the instruction (+ 1) in the label table.
Fetch-execute cycle
Repeatedly
1. load next instruction from the program array into ir and increments ip:
ir = program[ip++]
2. executes the instruction in ir.
3. halts if ir contains the halt instruction.
Amoeba Instruction
Set
Comment
Comment "instructions are ignored. Here's an example:
comment: Dave was right!
Label Declaration
Label declarations are executed by the pre-processor. Here's an example:
label: next
Variable Declaration
Variable declarations create entries in the environment. Here's an example:
def x 2
Load Command
The load command loads a variable in the environment with a number or the content of another number. Here's the format:
load var src
Where
var = any variable
src = any variable or integer
Note: this changes the content of the variable, not the variable or the environment.
Arithmetic and Logic
Most of the AL instructions have the format:
opcode var src1 src2
When executed, src1 and src2 are combined according to the opcode. The result is loaded into var.
Opcodes are:
add, mul, div, sub, and, or, equal, not
For example, here's how we would increment a variable named result:
add result result 1
The logic instructions interpret 0 to mean false and all other numbers to represent true.
The not opcode only takes to operands:
not result answer
This last instruction loads result with 1 if answer contains zero, otherwise it loads result with 0.
Sequence Control
The goto command changes ip. For example:
goto label
When executed, this instruction looks up the index associated with label in the label table, then loads that index in ip:
ip = labelTable(label)
The if command is like the goto command, but the ir is only modified if the condition var is not zero. For example, executing the command:
if var label
is essentially:
if (env(var).content != 0) ip = labelTable(label)
When the fetch-execute loop sees the halt instruction, it terminates:
halt
I/O
The printmsg command can be thought of as a macro (a built-in function). It prints any message to the console window. For example:
printmsg enter a number:
The answer can be read into a variable with the read command:
read response
The content of a variable can be written to the console window:
print response
Procedure call/return
Using procedures, we can view an Amoeba program as a sequence of procedure declarations. The program begins with the main procedure. This ends with the halt command. After the main procedure we may find declarations of "helper" procedures. A helper procedure begins with a label naming the procedure and ends with a return command.
The call command is how a procedure calls a helper. It specifies the name of the procedure being called and any arguments being passed to the procedure. (These may be variables or numbers. Variables are passed by value.):
call proc arg0 arg1 ...
When a procedure is called, a temporary extension is added to the environment:
environment = new Environment(environment)
This is where all arguments are stored and given the default names of arg0, arg1, etc. Also, the ip is stored here just before it is set to labelTabel(proc).
The return command takes a variable or a number as an operand. This is the value being returned to the caller:
return result
The return command restores the ip and restores the environment to the caller's environment:
var result = environment.get(result)
ip = environment("ip")
environment = environment.extension
Every environment has a special, automatically created variable called "return". (I know, it's a hack.) The return command loads the result into the caller's return variable.
Example: Computing
Triangle Numbers in Amoeba
Output:
Enter program name: triangle
enter staircase height: height = 6
number of blocks needed: => 15
go again? response = 1
enter staircase height: height = 10
number of blocks needed: => 45
go again? response = 0
bye ...
Example: Computing
Triangle Numbers in Amoeba using a subroutine
Using the formula tri(n) = n * (n + 1)/2 to compute triangle numbers:
Output:
Enter program name: triangle2
enter staircase height: height = 6
number of blocks needed: => 21
go again? response = 1
enter staircase height: height = 10
number of blocks needed: => 55
go again? response = 0
bye ...
Implementation
Complete the following implementation