The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.

NAME

Language::RAM - A "Random Access Machine" Emulator

VERSION

Version 0.012

SYNOPSIS

This module provides a library and an interpreter to emulate a basic "Random Access Machine". This computer model uses an assembler-like syntax and can be used to test simple algorithms for their complexity.

You can use ram.pl to run Random Access Machines and get extensive information on memory usage, memory changes and complexity. See ram.pl --help for details.

    use Language::RAM;

    my $input = "INPUT 0\nOUTPUT 1\na <-- s[0]\na <-- a * s[0]\ns[1] <-- a\nHALT";

    my %machine = Language::RAM::asl($input);
    die "$machine{'error'}" if ($machine{'error'} ne '');

    my $ret = Language::RAM::run(\%machine, [8]); # Returns 8^2
    if($ret) {
      print STDERR "Error from machine: $machine{'error'}\n";
    }

    my %output = Language::RAM::get_output(\%machine);
    print "OUTPUT FROM MACHINE:\n";
    foreach (sort { $a <=> $b } keys %output) {
      printf "%4d=%d\n", $_, $output{$_} // 0;
    }

EXPORT

To use Language::RAM, you only need asl, run, get_output, get_code_stats, get_mem_stats, get_line, get_first_memory_snapshot, get_snapshots and replay_snapshot.

GENERAL

asl(input)

Return random access machine from input string (one command per line).

The returned hash has the following keys/values:

input_layout=list ref

Range of input slots defined by INPUT command.

output_layout=list ref

Range of output slots defined by OUTPUT command.

error=string

Empty string. Not empty on errors.

code=hash ref

Hash of address => AST-Token.

memory=hash ref

Hash of slot name => value.

ip=current address
stats=hash ref
memory_usage=hash ref

Hash of slot name => [(reads writes)].

command_usage=hash ref

Hash of address => counter.

snaps=hash ref

Memory snapshots of each assignment. Hash of step => [(ip, address, new_value)].

steps=step counter

run(machine, input, limit, snapshots)

Run machine until it halts or stepcounter reaches limit.

machine=machine ref
input=list ref

Values will be loaded into memory before execution according to paramters given by INPUT.

limit=number
snapshots=boolean

Set to true to generate detailed memory snapshots of each command.

Returns empty string on success, error string on error.

get_output(machine)

Return output from machine.

machine=machine ref

Returns a hash of slot => value.

get_code_stats(machine)

Return code statistics from machine.

machine=machine ref

Returns a hash of address => counter.

get_mem_stats(machine)

Return memory statistics from machine.

machine=machine ref

Returns a hash of slot => counter.

get_line(machine, id)

Return line at id.

machine=machine ref
id=number

Returns line as string.

get_first_memory_snapshot(machine)

Returns a memory snapshot (a hash) of index => value of the memory at step -1 (before the machine starts).

machine=machine ref

get_snapshots(machine)

Returns a hash ref of step => [(ip, addr, value)].

machine=machine ref

replay_snapshot(machine, memory, from, to)

Replay steps from to to of machine in memory.

machine=machine ref
memory=ref to memory snapshot
from=step number to start at
to=step number to stop at

ABSTRACT SYNTAX TREE

ast(line, machine, ip)

Return AST of line.

line=string
machine=machine ref
ip=current address

Returns (ip, ast).

ip=<address>

Address of line (either generated or read from line, see README).

-1 if line is INPUT/OUTPUT statement.

ast=<ast reference>

undef on error.

ast_eval_io(line, machine)

Return INPUT/OUTPUT layout.

line=string
machine=machine ref

Returns a reference to a list of indices or undef on error.

get_ast(input, machine, ip)

Return AST-Token from line.

input=string
machine=machine ref
ip=current address

Return AST-Token or undef.

ast_imm(value)

Returns AST-Token for immutable values.

value=number

Returns [('imm', value)].

ast_reg(register)

Returns AST-Token for a register (a, i1..i3).

register=register

Returns [('reg', register)].

ast_algo(left, op, right, machine, ip)

Returns AST-Token for an arithmetic expression.

left=left side of expression
op=operation
right=right side of expression
machine=machine ref
ip=current address

Returns [('algo', type, left, op, right)] or undef on error.

type=boolean

True if left side of expression is register a, otherwise false.

left=ast-token
op=string
right=ast-token

ast_mem(inner, machine, ip)

Returns AST-Token for memory slot.

inner=string
machine=machine ref
ip=current address

Returns [('mem', imm)], [('mmem', ast)] or undef on error.

ast_cond(cond, op, machine, ip)

Returns AST-Token for conditional.

cond=string
op=string
machine=machine ref
ip=current address

Returns [('cond', reg, op)] or undef on error.

reg=ast-token
op=string

ast_jump(imm, machine, ip)

Returns AST-Token for jump instruction.

imm=number
machine=machine ref
ip=current address

Returns [('jump', imm)] or undef on error.

ast_cond_jump(cond, jump, machine, ip)

Returns AST-Token for if cond then jump k.

cond=string
jump=string
machine=machine ref
ip=current address

Returns [('if', cond, jump)] or undef on error.

cond=ast-token
jump=ast-token

ast_assign(left, right, machine, ip)

Returns AST-Token for assignment.

left=left side of expression
right=right side of expression
machine=machine ref
ip=current address

Returns [('assign', left, right)] or undef on error.

left=ast-token
right=ast-token

EVALUATION

eval(ast, machine)

Evaluate ast.

ast=ast reference
machine=machine reference

Returns undef on error.

eval_imm(ast)

    my $ast = [qw(imm 2)];

Returns immutable value of ast.

ast=ast reference

eval_mem(ast, machine, type)

    my $ast = [qw(mem 2)];

Returns value of/reference to/address of memory block.

ast=ast reference
machine=machine reference
type=number

Returns value of memory block if type is 0.

Returns reference to memory block if type is 1.

Returns address of memory block if type is 2.

eval_mmem(ast, machine, type)

    my $ast = [('mmem', "algo here, see eval_algo")];

Same as eval_mem, but evaluate inner expression.

Returns undef if inner expression could not be evaluated.

eval_algo(ast, machine)

    my $ast = [('algo', 1, [qw(reg a)], '+', [qw(mem 2)])];

Return result of arithmetic expression.

ast=ast reference
machine=machine reference

Returns undef if left side, right side or operation failed to evaluate.

eval_cond(ast, machine)

    my $ast = [('cond', [qw(reg a)], '<=')];

Return result of conditional (always compares against 0).

ast=ast reference
machine=machine reference

Returns undef if left side or operation failed to evaluate.

eval_if(ast, machine)

    my $ast = [('if', "cond here, see eval_cond", "jump here, see eval_jump")];

Jump if conditional evaluates to true.

ast=ast reference
machine=machine reference

Returns undef if conditional returned an error.

eval_jump(ast, machine)

    my $ast = [('jump', [qw(imm 2)])];

Jump to address.

ast=ast reference
machine=machine reference

Returns undef if address could not be evaluated.

eval_assign(ast, machine)

    my $ast = [('assign', "left side", "right side")];

Evaluate assignment.

ast=ast reference
machine=machine reference

Returns undef if left or right side could not be evaluated.

STATISTICS

inc_mem_stat(machine, mem, action)

Increases access counter of one memory slot. These stats can later be retrieved with get_mem_stats.

machine=machine ref
mem=memory address
action=boolean

Add write action to memory slot if action is true.

Add read action to memory slot if action is false.

add_snapshot(machine, addr, value)

Add replayable snapshot where memory slot addr changes to value.

machine=machine ref
addr=number
value=number

report(machine, message)

Set error string of machine to message.

machine=machine ref
message=string

Returns undef.

AUTHOR

Fabian Stiewitz, <deprint at cpan.org>

BUGS

Please report any bugs or feature requests to bug-language-ram at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Language-RAM. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

SUPPORT

You can find documentation for this module with the perldoc command.

    perldoc Language::RAM

You can also look for information at:

ACKNOWLEDGEMENTS

LICENSE AND COPYRIGHT

Copyright 2015 Fabian Stiewitz.

This program is free software; you can redistribute it and/or modify it under the terms of the the Artistic License (2.0). You may obtain a copy of the full license at:

http://www.perlfoundation.org/artistic_license_2_0

Any use, modification, and distribution of the Standard or Modified Versions is governed by this Artistic License. By using, modifying or distributing the Package, you accept this license. Do not use, modify, or distribute the Package, if you do not accept this license.

If your Modified Version has been derived from a Modified Version made by someone other than you, you are nevertheless required to ensure that your Modified Version complies with the requirements of this license.

This license does not grant you the right to use any trademark, service mark, tradename, or logo of the Copyright Holder.

This license includes the non-exclusive, worldwide, free-of-charge patent license to make, have made, use, offer to sell, sell, import and otherwise transfer the Package with respect to any patent claims licensable by the Copyright Holder that are necessarily infringed by the Package. If you institute patent litigation (including a cross-claim or counterclaim) against any party alleging that the Package constitutes direct or contributory patent infringement, then this Artistic License to you shall terminate on the date that such litigation is filed.

Disclaimer of Warranty: THE PACKAGE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS "AS IS' AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES. THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT ARE DISCLAIMED TO THE EXTENT PERMITTED BY YOUR LOCAL LAW. UNLESS REQUIRED BY LAW, NO COPYRIGHT HOLDER OR CONTRIBUTOR WILL BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING IN ANY WAY OUT OF THE USE OF THE PACKAGE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.