NAME

Acme::URM - URM (unlimited register machine) emulation

SYNOPSIS

  use Acme::URM;

  my $rm  = Acme::URM->new();
  # program that summarize parameters given in R0,R1
  $urm->program(
               'T(0,2)',
               'T(1,3)',
               'J(3,4,6)',
               'S(2)',
               'S(4)',
               'J(0,0,2)',
               'T(0,3)',
               'J(3,1,'.Acme::URM::LAST.')',
               'J(3,2,11)',
               'S(3)',
               'J(0,0,7)',
               'T(1,0)',
               );

  $urm->register( 0, 2, 2 );    # fill the registers
  my $res       = $urm->run();  # res must be 4

DESCRIPTION

This module gives you the methods needed to emulate an URM in Perl.

Why? Because we can.

What is URM?

URM stands for unlimited register machine.

URM has unlimited number of registers: R0, R1, ... Those contain natural numbers: r0, r1, ... Default values for ri are 0.

Instruction for URM is one of the following instructions:

• Z(n) - set up register with index n to zero

• S(n) - increment value of register with index n by 1

• T(m, n) - set up register with index n to value of register with index m

• J(m, n, q) - conditional instruction: if values of registers with indexes m, n are equal, then go to insturction with index q (zero based index), else move to following instruction

Program of URM is a finite list of URM instructions.

METHODS

new

Creates the URM machine object.

program [new_instructions]

New instructions are added to program if given. Returns reference to array with the current program of URM object

clear_program

Clears current program of URM object

register n [value [values]]

Set up nth register with "value" if given. Returns value of nth register. If values parameters is specified, values of registers following nth are set accordingly.

clear_registers

Clears current registers of URM object

clear

Clears current program & registers of URM object

max_steps [value]

Set up value of maximum steps for URM if given. Returns current values for maximum steps for URM.

This value is designed to prevent URM from infinite execution.

run

Run program of URM object. Possible return values: - value of R0 register; - MAX_STEPS constant (see max_steps function)

EXAMPLE

The following example computes the maximum of 2 numbers:

  use Acme::URM;
  my $urm  = Acme::URM->new();
  $urm->program(
                         'T(0,2)',
                         'T(1,3)',
                         'J(3,4,6)',
                         'S(2)',
                         'S(4)',
                         'J(0,0,2)',
                         'T(0,3)',
                         'J(3,1,11)',
                         'J(3,2,'.Acme::URM::LAST.')',
                         'S(3)',
                         'J(0,0,7)',
                         'T(1,0)',
                         );

  $urm->register( 0, 2, 3 );
  $urm->run() == 3;

DEBUG MODE

You can use this module in debug mode, like this:

  use Acme::URM qw/debug/;

Which will produce some output while running the program.

USEFULNESS

I coded this module while checking out TA (theory of algorithms) materials.

REFERENCES

Russian wiki link: http://ru.wikipedia.org/wiki/%D0%9C%D0%9D%D0%A0

AUTHOR

Alexander Soudakov (cygakoB@gmail.com), April 2008.