ITECH 5403 Comparative Programming Languages

 ASSIGNMENT 2. Modelling Unlimited Register Machines 

35 MARKS

Introduction

Unlimited Register Machines (or URMs) are mathematical abstractions of real-life computers. They are more user-friendly than Turing Machines and make an ideal introduction to machine models of computability. Any effectively computable function can be computed on a URM.

URMs were introduced by John C. Shepherdson and Howard E. Sturgis in 1963.

In this assignment you are required to implement Unlimited Register Machines (URMs) using four different languages – C, Java, Python and LISP. i.e., you are required to write programs in these languages that imitate the functionality of URMs (to develop Virtual URMs).

1.Description of the Unlimited Register Machines,

A URM has registers R0,R1,R2,…, which store natural numbers r0,r1,r2,…:

R0    R1    R2    R3    R4    R5    …
r0    r1    r2    r3    r4    r5    …

A URM program is a finite list of instructions, each having one of the four following basic types:

Instruction Type 

Notation    Effect
Zero    Z(n)    rn = 0
Successor    S(n)    rn = rn+1
Transfer    T(m,n)    rn = rm
Jump    J(m,n,q)    If rn = rm go to instruction q, else go to the next instruction.

Z(n) – sets value of register Rn to zero and moves to the next instruction in the program list.

S(n) – increases the value of register Rn by one and moves to the next instruction in the program list.

T(m,n) – copies the value of Rm to Rn and moves to the next instruction in the program list.

J(m,n,q) – if rm = rn, the instruction at index q in the program list is executed. Else the next instruction in the program list is executed.
URM programs are zero-based indexed lists of instructions, i.e., instructions in a program can be accessed via indexes and the index of the first instruction is 0.

A URM program starts with the first instruction (at index 0) and executes instructions consecutively, one by one, unless it encounters the Jump instruction. 

The program halts after execution reaches the end of the program list or a Jump instruction J(m,n,q) is executed, where q is not a valid index in the program list.

URM is used to compute functions that take integer parameters and return an integer value.

Input and Output conventions: To compute a function
𝑓(𝑛𝟏𝟏, … , 𝑛𝑘),  we  start  with  𝑛𝟏𝟏, … , 𝑛𝑘    in  registers
𝘙𝟎𝟎, … , 𝘙𝑘−𝟏𝟏, respectively, and with 0 in all the other registers. If computation halts, the output is the number in register R0.
Example 1. Addition function, m + n, can be computed by the following URM program:
0) J(1,2,4)
1) S(0)
2) S(2)
3) J(0,0,0)

Example 2. Product function, m*n, can be computed by the following URM program:
0) T(0,2)
1) Z(0)
2) Z(3)
3) Z(4)
4) J(2,4,13)
5) J(1,3,13)
6) S(0)
7) S(4)
8) J(2,4,10)
9) J(1,1,6)
10)S(3)
11)Z(4)
12)J(1,1,5)

2.Programming tasks.
You are required to implement Unlimited Register Machines (URMs) in four different languages – C, Java, Lisp and Python.

Implementation Requirements:
Set of URM’s registers should be implemented as an array or list of integers.
Instruction types should be coded by the integers
{0,1,2,3}: use 0 for Z, 1 for S, 2 for T and 3 for J.
Instructions should be represented by arrays or lists of integers, for example, in your Python program instruction J(1,2,4) should be represented by the list [3,1,2,4].
Programs should be implemented as arrays or lists of instructions. For example, in your Python implementation the program from Example 1 should be represented by the following list of lists:
program = [[3,1,2,4], [1,0], [1,2], [3,0,0,0]]

Also, you are required to write the following three

 functions/methods in each of the implementations:
(1)isValidCommand(command) – takes a list/array of integers and returns true if it is a valid URM command, otherwise returns false.

(2)isValidProgram(program) – takes a list of instructions and returns true if it is a valid URM program, otherwise returns false.

(3)run(program, registers) – runs the URM program on the list/array of registers.

(4)main() – this is a testing method/function where you test your implementation of URM by running the programs from Example 1 and Example 2.

3.Write a URM power program.

In this task, using one of your URM implementations you are required to write and test, , a URM program that computes the power function. I.e., power(m,n) computes mn. For example, power(2,3) returns 8, power(3,4) returns 81.

Allocated Marks: See Course Description

Due Date: See Course Description
Please refer to the Course Description for information relating to late assignments and special consideration.

Assignment Submission:
You must supply your program source code files and report documentation as single compressed archive called: ITECH5403_Assignment_2_<YOUR-NAME>_<YOUR-STUDENT-ID>.zip
 

Assignments will be marked on the basis of fulfilment of the requirements and the quality of the work. In addition to the marking criteria, marks may be deducted for failure to comply with the assignment requirements, including (but not limited to):

successful compilation

successful completion of the required tasks

adherence to the guidelines provided

quality of code that adheres to the programming standards for the Course, including:

1.comments and documentation

2.code layout

3.meaningful variable names

Submit your assignment (all program source files plus your discussion document) to the Assignment 2 upload location on Moodle before the deadline.

The mark distribution for this assignment is explained on the next page.

ITECH5403 ASSIGNMENT 2 Marking Rubric.

Student ID:

Student Name:

    Weight    Awarded
Marks deducted for badly commented or badly written code    (-4)    

isValidCommand:        
C implementation    1    
Java implementation    1    
Python implementation    1    
LISP implementation    1    

isValidProgram:        
C implementation    1    
Java implementation    1    
Python implementation    1    
LISP implementation    1    

run:        
C implementation    5    
Java implementation    5    
Python implementation    5    
LISP implementation    5    

main:        
C implementation    1    
Java implementation    1    
Python implementation    1    
LISP implementation    1    
URM power program    
3    
Total    
35 + (-4)