caml-urm

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

(** Unlimited register machines

 This module provides various types and functions for manipulating unlimited
 register machines (URMs). This implementation is besed on the specification
 provided in Ramin Naimi's URM simulator, which is in turn based on that of
 {i Computability, An introduction to recursive function theory } by Nigel J.
 Cutland. For example, the instruction set is given by:

 - [T(n, m)] transfers the contents of the [n]-th register to [m]-th register.
 - [Z(n)] sets the value of the [n]-th register to zero.
 - [S(n)] increments the value of the [n]-th register.
 - [P(n)] decrements the value of the [n]-th register.
 - [J(n, m, i)] jumps to the [i]-th instruction if the values of the [n]-th and
 [m]-th coincide. The instruction count starts at 1, so [i = 1] jumps to the
 first instruction.

 The register set, however, is a bit different. In Nigel's specification the
 registers are indexed by natural numbers (starting from 1), while in this
 implementation the registers are indexed by arbitrary integers. Also, in
 Nigel's specification registers store natural numbers (starting from 0) and in
 this implementation they store arbitrary integers. I have also added the [P]
 instruction to help users handle negative integers.

 @see <sites.oxy.edu/rnaimi/home/URMsim.htm> URM simulator.
 @see <doi.org/10.1017/CBO9781139171496> Computability, An introduction to
 recursive function theory. *)

(** The type of instructions. *)
type instruction =
  | T of int * int
  | Z of int
  | S of int
  | P of int
  | J of int * int * int

(** The type of all possible states of a URM. *)
type t

(** An alias for {! t } *)
type machine = t

(** Returns a machine whose register values are given by a function. *)
val of_registers : (int -> int) -> machine

(** Returns a machine whose registers are given by the pairs in a list. All
    other registers are zero initialized. *)
val of_list : (int * int) list -> machine

(** [register m i] returns the value of the [i]-th register of [m]. *)
val register : machine -> int -> int

(** A machine whose registers are all zeros. *)
val zeros : machine

(** [exec m program] returns a machine whose register values are given by the
    register values of
    [m] with updates corresponding to the execution of [program].

    This function only returns when [program] actually halts. Please use {!
    nexec } if you don't trust [program].

    @raise Invalid_argument if [program] attempts to jump to a non-positive
    integer. *)
val exec : instruction array -> machine -> machine

(** A safe version of {! exec }, where the maximum number of clock-cycles
    allowed is controlled the first argument. Each instruction takes a single
    clock-cycle to execute.

    [nexec n program] returns [Some _] if [program] halts in at most [n]
    clock-cycles and [None] otherwise.

    @raise Invalid_argument if [program] attempts to jump to a non-positive
    integer.  @raise Invalid_argument if [n] is not a positive integer. *)
val nexec : int -> instruction array -> machine -> machine option

(** Exception raised when parsing fails. *)
exception Syntax_error of string

(** Parse a program from a string. The syntax used by the parser is based on
    the one used by Ramin Naimi's URM simulator, but again the register indexes
    can be arbitrary integers.

    @see <sites.oxy.edu/rnaimi/home/URMsim.htm> URM simulator.

    @raise Syntax_error in case any syntax error is encountered, including
    invalid syntax and jumps to invalid addresses. *)
val parse : string -> instruction array