Skip to content
/ URM Public

Unbounded Register Machine Emulator : a fun project written in C++

Notifications You must be signed in to change notification settings

Jakjm/URM

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

12 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

This is a project that aims to allow students to run URM programs using an emulator written in C++.
Unbounded Register Machines (URMs) are a creation of Shepherdson and Sturgis.
URMs are not very practical - something as simple as variable assignment takes multiple loops, as demonstrated in the program swap.uxe that I wrote to test the URM.
However, it is enjoyable to write programs that overcome the challenges posed by the language - which makes this quite valuable. 

How to write URM programs:
There are 5 different kinds of URM instructions. 

L: Xi <- a				//Assignment Instruction
L: Xi <- Xi + 1				//Increment Instruction 
L: Xi <- Xi - 1				//Decrement Instruction 
L: if Xi = 0 goto X else goto Y 	//Conditional Goto Instruction
L: stop					//Stop Instruction 

The instructions of a URM program are ordered using a label (denoted L above).
The first label of a URM program is 1. 
Each additional instruction has a label that is one greater than the previous label. 

The stop instruction occurs exactly ONCE in a URM program, and must be the last instruction in the program.

The variables of a URM program are of the following form: X1, X11, X111, etc. 
However, using the -m or --meta option, one can use any string that does not contain whitespace characters as variables (called metavariables).

Each variable is given the initial value of 0. The variables of URMs are natural numbers, so they cannot take on negative values.
While this may feel limiting, you may still code floating point and negative numbers using prime-power coding.

For example, a signed variable can be expressed as a URM variable that is equal to 2^(1+sign) * 3^(1+value).
Where a sign value of 0 indicates the variable is positive and 1 indicates the variable is negative.
Is this ridiculously inefficient? Of course it is! 
But it is very useful to observe that despite the limited number of instructions, URMs can any partial computable function!
(However, this emulator limits the maximum value so far to the maxmimum size of a signed 32 bit integer for now)


An example URM program is as follows:
1: X1 <- 5
2: X1 <- X1 + 1
3: if X1 = 0 goto 4 else goto 1
4: stop

As you can see, there is no requirement that a URM program comes to a halt - the above program is partial computable, but it is not in the set of recursive functions (asit does not halt).

Running programs: 
Use the 'make' command to compile the runurm executable file, which allows you to emulate urm programs. 
If the above program was stored in the file program.txt, you can run it using the command:
./runurm program.txt

If the program uses metavariables, you can run it using:
./runurm program.txt -m 
or 
./runurm program.txt --meta 

I've been a little lazy, so you must put the filename argument before the metavariable argument. 

Todo list: 
-Variables currently have a maximum value of (2^31) -1, but this will soon change to allow variables of arbitrary size. 

About

Unbounded Register Machine Emulator : a fun project written in C++

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published