User documentation

Version 0.39

1. Introduction

Random Access Machine (RAM) is an abstract machine, invented to study algorithmic complexity of programs written on register-based computers. It is equivalent to Turing machine, and has a close relationship with a so-called Harvard computer architecture, which has separated storage for program and data. The implication of this model is that it is not possible to modify instructions.

In contrast, there exist a Random Access Stored Program machine (RASP), which is close to von-Neumann computer architecture.

Both RAM and RASP are implemented as emulators, or maybe better - simulators in emuStudio. This documents describes the RAM simulator.

2. Brief description

RAM machine consists of several parts: input tape (read-only), output tape (write-only), program memory, data memory or registers (read/write) and a control unit ("engine"), as can be seen in the following image:

RAM machine

Input tape acts as a water-tap; the input data can be read from it, causing the input head moving to the next unread symbol. The head can never return to previously read symbol.

Output tape, on the other hand, acts as a sink. The output data can be written to it, causing the output head moving to the next "empty" symbol. The head can also never return to the previously written symbol.

Data memory - registers tape - represents the random-access memory. It consists of so-called registers, abstract cells with arbitrary size. These registers are ordered - each one has assigned the index - its position within the tape, called the address. The tape head can move arbitrarily up and down - but it has its minimum position. It is the first register, R0, called the accumulator. Below there are unlimited number of higher-positioned registers.

The role of accumulator is kind of special - it often acts as an implicit operand for many instructions, or implicit place for storing the result of such instructions.

Program memory is a bounded ordered sequence of registers; each of them is identified by its index within the tape, called address. Data memory is also ordered sequence of registers, but like the I/O tapes - bounded just from one side.

Since RAM machine is somewhat abstract, it frees the user from thinking about some issues, and just assumes that:

  • The size of the problem is always small enough to fit in the RAM memory,

  • Data used within the computation are always small enough to fit in one register.

The RAM virtual machine in emuStudio consists of the following plug-ins:

  • ramc-ram: Compiler of the RAM language, very simple "assembler"-like language

  • ram-cpu: RAM simulator engine

  • ram-mem: Program memory

  • abstractTape-ram: Device which represents the "tape" used in RAM, other than program memory. The abstract schema must define three instances of this device, representing register, input and output tapes.

2.1. Abstract schema

In order to use RAM, there must exist the abstract schema of the "computer", saved in the configuration file. Abstract schemas are drawn in the schema editor in emuStudio (please see emuStudio main module documentation for more details). The following image shows the schema of RAM machine simulator:

RAM abstract schema

The "→" arrows are in direction of dependency. So for example ramc-ram depends on ram-mem, because compiled programs are directly loaded into memory.

The roles of the abstract tapes are assigned by the RAM "CPU" on runtime.

2.2. Automatic emulation

RAM is one of computers which supports automatic emulation. In general, automatic emulation can be interactive, or not interactive. In case of the RAM emulator, only non-interactive emulation is useful. It is because during emulation it is not possible to interact (e.g. pass new input to the input tape) in any way.

Changes to any abstract tapes are written to the corresponding output file. For more specific information, please see Automatic emulation section of the abstract tape chapter.

Command line for starting non-interactive automatic emulation:

java -jar emuStudio.jar --config RAM --input examples/ramc-ram/factorial.ram --auto --nogui
  • configuration config/RAM.conf will be loaded

  • input file for compiler is one of the examples

  • (--auto) automatic emulation mode will be performed

  • (--nogui) non-interactive version will be set

After the run, the following output on the stdout can be expected:

[INFO] Loading virtual computer: RAM
[INFO] All plugins were loaded successfully.
[INFO] Being verbose. Writing to file:registers_(storage_tape).out
[INFO] Being verbose. Writing to file:input_tape.out
[INFO] Being verbose. Writing to file:output_tape.out
[INFO] Starting emulation automatization...
[INFO] Compiler: RAM Compiler
[INFO] CPU: Random Access Machine (RAM)
[INFO] Memory: RAM Program Tape
[INFO] Memory size: 0
[INFO] Device #00: Abstract tape
[INFO] Device #01: Abstract tape
[INFO] Device #02: Abstract tape
[INFO] Compiling input file: examples/ramc-ram/factorial.ram
[INFO] Compiler started working.
[INFO] [Info    (000)] RAM Compiler, version 0.39-SNAPSHOT
[INFO] [Info    (000)] Compile was successful.
[INFO] [Info    (000)] Compiled file was loaded into operating memory.
[INFO] [Info    (000)] Compilation was saved to the file: /home/vbmacher/tmp/emustudio/examples/ramc-ram/factorial.ro
[INFO] Compiler finished successfully.
[INFO] Program start address: 0000h
[INFO] Resetting CPU...
[INFO] Running emulation...
[INFO] Normal stop
[INFO] Instruction position = 0011h
[INFO] Emulation completed

Then, in the current working directory, there will be created three new files:

  • input_tape.out

  • registers_(storage_tape).out

  • output_tape.out

The format of the files is described in already mentioned Automatic emulation section of the abstract tape chapter.

3. Compiler for RAM machine

RAM has a very simple assembler-like language, consisting of direct and indirect reading/writing from/to registers or input/output tape. In addition, there are three control-flow instructions.

3.1. Installation and run

The compiler is provided as part of emuStudio. It is not deployed as individual package. The compiler can be found in compilers/ directory with name ramc-ram.jar.

3.2. Language description

The program written for this compiler consists of two sections:

INPUT section
INSTRUCTIONS section

3.2.1. Input section

The INPUT section contains definitions the content of input tape - one or more lines in the form:

<input> ITEMS

where ITEMS is a space-separated list of inputs. Each input is one word - it might be any number or string. By default, every cell in the input tape is a string, and it is not interpreted as some data type. It is only in time when it is used - the instruction which works with the cell defines of which "type" it should be.

For example, input section might be:

<input> 1 2 3 hello world!

In this case, there are five inputs: numbers 1,2,3, then word "hello" and the last one is "world!".

3.2.2. Instructions section

There exist many possible formats or variations of RAM instructions, unfortunately the syntax is not very unified. I guess the reason is that RAM is not a real machine, and for the purposes of the algorithm analysis the machine is so simple that it’s description is repeated in almost every paper where it appears.

For this reason, instructions format or the whole vocabulary might be different of what you expected or used for. We have to live with it; but the differences are really small.

Instructions should follow the Input section, but the sections can be mixed. It is just good practice to have input separated from the code. Each instruction must be on separate line, in the form:

[LABEL:] INSTRUCTION [; optional comment]

Each instruction position can be optionally labelled with some identifier (LABEL field), followed by a colon (:) character. The labels can be then referred in other instructions.

Comments begin with a semicolon (;) character and continue to the end of the line. There are no multi-line comments.

Instructions consists of the operation code and optional operand, separated with space (` `).

Operation code is expressed as an abbreviation of corresponding operation (e.g. SUB for SUBtraction). Operand can be one of three types: constant (=i), direct operand (i), where i specifies the register index on tape and indirect operand (*i), where the address of operand specified is stored in register Ri.

The following table describes all possible instructions, usable in the RAM simulator:

=i i *i

HALT

halts the simulation

READ

Ri ← next input

WRITE

output ← i

output ← Ri

output ← M<Ri>

LOAD

R0i

R0Ri

R0M<Ri>

STORE

RiR0

M<Ri>R0

ADD

R0R0 + i

R0R0 + Ri

R0R0 + M<Ri>

SUB

R0R0 - i

R0R0 - Ri

R0R0 - M<Ri>

MUL

R0R0 * i

R0R0 * Ri

R0R0 * M<Ri>

DIV

R0R0 / i

R0R0 / Ri

R0R0 / M<Ri>

JMP

IPi

JZ

if R0 == 0 then IPi

JGTZ

if R0 > 0 then IPi

The table describes also the behavior of each instruction. Compiler does not care about the behavior, but about the instructions syntax, which is also incorporated in the table.

For example, this is a valid program:

; COPY(X,Y)
;
; input:  X -> r1
;         Y -> r2
;
; output: X -> Y
;         Y -> Y

<input> 3 4 world hello

<input> sss
; load X,Y
read 1
read 2

; load r.X, r.Y
read *1
read *2

; copy
load *2
store *1

halt

4. RAM Simulator Engine

The plug-in responsible for execution of the simulation of RAM machine is called ram-cpu. Even if we’re supposed to talk about RAM simulator, because emulation is connected more with imitation of real hardware than abstract machine, there is a plugin which calls itself a RAM CPU. It is really not accurate, but CPU nowadays means something as the main or core engine of the computation which the machine does. So the name is stick rather with this convention.

The plug-in strictly requires a ram-mem, and three instances of abstractTape-ram plug-ins, representing the tapes. After boot, the CPU assigns the specific meaning to each tape.

4.1. Installation and run

The RAM CPU can be run only as a part of emuStudio. It is installed in location cpu/ram-cpu.jar.

4.2. Status panel

In the following image, you can see the status panel of ram-cpu.

RAM CPU status panel

It is split into three parts. Within 'Internal status' part, there is shown content of registers R0 (accumulator) and IP. Register IP is the position of the program memory head. It stands for "instruction pointer". It is pointing at the next instruction being executed.

The input/output part shows the next unread symbol ("next input"), and the last symbol written to the output tape ("last output"). This is just for the convenience; it is possible to see the same values in particular tape devices.

The last part, "Run state", shows in which state the whole emulation is, and it is common to all emulators in emuStudio. The state "breakpoint" means that the emulation is paused.

5. Program Memory

RAM memory is used as a part of RAM simulator, which acts as the "program memory", holding just the program.

RAM CPU reads instructions from this memory. The instructions can be written here only by compiling the source code, or loading already compiled binary image.

The memory plug-in contains simple graphical window, a GUI, which provides a set of the following features:

  • It computes time and space complexity of the program

  • It shows the memory content (the "program") as the list of disassembled instructions

5.1. Installation and run

The RAM memory can be run only as a part of emuStudio. It is installed in location mem/ram-mem.jar.

5.2. Graphical user interface (GUI)

The memory GUI can be seen in the following picture.

RAM memory window
  • A: Opens already compiled program into memory. Previous program will be dismissed.

  • B: Clears memory.

  • C: Shows uniform time complexity for the actual program.

  • D: Shows uniform space complexity for the actual program.

Uniform time complexity means maximum number of instructions based on the input N. Uniform space complexity means maximum number of used registers.

6. Abstract tapes

Abstract tapes, in general, are used in various abstract machines. Probably the best known are Turing machine, RAM machine and RASP machine. Plug-in of the abstract tape for emuStudio is called abstractTape-ram.

There are several properties which an abstract tape might have:

  • Bounded, one-side bounded or unbounded

  • Random access (allowing to move head in both directions) or linear access (allowing to move head only in one direction)

  • Specific or any cell content type (e.g. cells are integers, or strings, or can be any value?)

  • Read only, or read-write cells

  • Purpose of the tape (title)

This plug-in allows to set up such properties, but those are set up by the virtual computer which uses it, not by the user. For more information, please see the Using abstract tapes in your emulator section.

Currently, there are just two virtual computers utilizing this plug-in:

  • RAM machine

  • RASP machine

After emuStudio is run, RAM CPU (or RASP CPU) sets up properties for all used tapes. So the tape "purpose" and behavior is set in run time.

6.1. Installation and run

The abstract tape can be run only as a part of emuStudio. It is installed in location devices/abstractTape-ram.jar.

6.2. Graphical user interface (GUI)

The graphical user interface of the abstract tape is very simple. In order to open it, select the tape in the peripheral devices list in the Emulator panel. Then, click on the "Show" button.

Abstract tape window (Input tape of the RAM machine)

The symbol, highlighted with the blue color is the current head position, in this case. In order to manipulate with particular symbols, one must select the symbol, which appears in bold, as in the following image:

Selected symbol in the abstract tape
  • A: If the tape allows it, one can add new symbol before the selected one in the tape. In the image, the tape does not allow it.

  • B: The tape content area. Usually, each row consists of the symbol "index" or position within the tape, followed by the symbol itself.

  • C: If the tape allows it, one can add new symbol after the last one in the tape. In the image, the tape allows it.

  • D: Removes selected symbol from the tape.

  • E: Edits the tape symbol. The symbol must be selected.

  • F: Clears the tape content

6.2.1. Settings

The tape allows to edit some settings from the graphical mode; to open the settings window click on the "Settings" button below the peripheral devices list in the Emulator panel. The window can be seen in the following image:

Abstract tape settings
  • A: Do not allow the tape to fall behind other window

  • B: Show the tape right after emuStudio start (see Configuration file section)

6.3. Configuration file

Configuration file of virtual computers contain also settings of all the used plug-ins, including devices. Please read the section "Accessing settings of plug-ins" in the user documentation of Main module to see how the settings can be accessed.

The following table shows all the possible settings of Abstract tape plug-in:

Table 1. Settings of Abstract tape
Name Default value Valid values Description

alwaysOnTop

false

true, false

Whether the tape GUI should not allow to fall behind other windows

showAtStartup

false

true, false

If the tape should be shown automatically after emuStudio is started

6.4. Automatic emulation

Abstract tape supports automatic emulation. It means, that every change to it is being written to a file. The file name is devised from the title of the tape, by the following algorithm:

  • At first, all spaces in the title are replaced with underscore (_)

  • Then, all "unwanted" characters are also replaced with underscore

  • Every character is converted to lower-case

  • Finally, the .out extension is added at the end.

Unwanted characters are the following: *, ., #, %, &, +, !, ~, /, ?, <, >, ,, |, {, }, [, ], ", `, =

6.5. Using abstract tapes in your emulator

This section is for developers of emulators. If you do not plan to create custom virtual computers, you can safely skip this section. In order to get started with developing plug-ins for emuStudio, please read tutorial "Developing emuStudio Plugins".

The Abstract tape plug-in can be used in various computers. Besides standard operations which are provided by emulib.plugins.device.DeviceContext interface, it provides custom context API, enabling to setting up properties described in the introduction section.

Usually, the tapes are used by CPU plug-ins, but it is ofcourse possible to use it in any other plug-in. You can obtain the context during the initialize() method of the plug-in main class. The context is named net.sf.emustudio.devices.abstracttape.api.AbstractTapeContext:

...

public void initialize(SettingsManager settings) {
    ...

    AbstractTapeContext tape = contextPool.getDeviceContext(pluginID, AbstractTapeContext.class);
    ...
}

The tape context interface is as follows:

package net.sf.emustudio.devices.abstracttape.api;

import emulib.annotations.ContextType;
import emulib.plugins.device.DeviceContext;

/**
 * Public API of the abstract tape.
 */
@ContextType
public interface AbstractTapeContext extends DeviceContext<String> {

    /**
     * Clear content of the tape.
     */
    void clear();

    /**
     * Set this tape to left-bounded or unbounded.
     *
     * @param bounded true if the tape should be left-bounded,
     *                false if unbounded.
     */
    void setBounded(boolean bounded);

    /**
     * Determine if the tape is left-bounded.
     *
     * @return true - left-bounded, false - unbounded.
     */
    boolean isBounded();

    /**
     * Move the tape one symbol to the left.
     *
     * If the tape is left-bounded and the old position is 0, tape won't move. Otherwise the tape
     * will expand to the left - add new empty symbol to position 0 and shift the rest of the content to the right.
     *
     * @return true if the tape has been moved; false otherwise (if it is left-bounded and the position is 0).
     */
    boolean moveLeft();

    /**
     * Move tape to the right. If the tape is too short, it is expanded to the right (added new empty symbol).
     */
    void moveRight();

    /**
     * Allow or disallow to edit the tape.
     *
     * If the tape is editable, the user (in GUI) can add, modify or remove symbols from the tape.
     * Otherwise it is driven only by the CPU.
     *
     * @param editable true if yes, false if not.
     */
    void setEditable(boolean editable);

    /**
     * Get symbol at the specified position.
     *
     * @param pos position in the tape, starting from 0
     * @return symbol at given position; if the position is out of bounds, then empty string is returned.
     */
    String getSymbolAt(int pos);

    /**
     * Set symbol at the specified position.
     *
     * If the position is < 0, then no symbol will be set.
     *
     * If the position is > tape size, empty symbols will be added until the required tape size is ensured.
     * Then, the symbol is added at the specified position.
     *
     * This method should be used only when loading some initial content to the tape.
     *
     * @param pos position in the tape, starting from 0
     * @param symbol symbol value
     */
    void setSymbolAt(int pos, String symbol);

    /**
     * Sets whether the symbol at which the head is pointing should be "highlighted" in GUI.
     *
     * @param visible true if yes; false otherwise.
     */
    void setHighlightHeadPosition(boolean visible);

    /**
     * Seths whether the tape should be cleared at emulation reset.
     *
     * @param clear true if yes; false otherwise.
     */
    void setClearAtReset(boolean clear);

    /**
     * Set title (purpose) of the tape.
     *
     * @param title title of the tape
     */
    void setTitle(String title);

    /**
     * Determines if the symbol positions should be displayed in GUI.
     *
     * @return true if yes; false otherwise
     */
    boolean showPositions();

    /**
     * Set whether the symbol positions should be displayed in GUI.
     *
     * @param showPositions true if yes; false otherwise.
     */
    void setShowPositions(boolean showPositions);

    /**
     * Get the tape head position.
     *
     * @return current position in the tape; starts from 0
     */
    int getHeadPosition();

    /**
     * Get the size of the tape
     *
     * @return tape size
     */
    int getSize();

    /**
     * Determine if the tape is empty.
     *
     * @return true if the tape is empty; false otherwise.
     */
    boolean isEmpty();

    @Override
    default Class<String> getDataType() {
        return String.class;
    }

}