progs/sml/re.ML
author Chengsong
Tue, 14 Jun 2022 18:06:33 +0100
changeset 542 a7344c9afbaf
parent 359 fedc16924b76
permissions -rw-r--r--
chapter3 finished
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     1
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     2
datatype rexp =
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
     3
   ZERO
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
     4
 | ONE 
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     5
 | CHAR of char
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     6
 | ALT of rexp * rexp
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     7
 | SEQ of rexp * rexp 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     8
 | STAR of rexp 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     9
 | RECD of string * rexp
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    10
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    11
datatype value =
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
    12
   Empty
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    13
 | Chr of char
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    14
 | Sequ of value * value
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    15
 | Left of value
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    16
 | Right of value
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    17
 | Stars of value list
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    18
 | Rec of string * value
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    19
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    20
(* some helper functions for strings *)   
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    21
fun string_repeat s n = String.concat (List.tabulate (n, fn _ => s))
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    22
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    23
(* some helper functions for rexps *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    24
fun seq s = case s of
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
    25
    [] => ONE
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    26
  | [c] => CHAR(c)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    27
  | c::cs => SEQ(CHAR(c), seq cs)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    28
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    29
fun chr c = CHAR(c)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    30
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    31
fun str s = seq(explode s)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    32
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    33
fun plus r = SEQ(r, STAR(r))
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    34
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    35
infix 9 ++
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    36
infix 9 --
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    37
infix 9 $
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    38
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    39
fun op ++ (r1, r2) = ALT(r1, r2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    40
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    41
fun op -- (r1, r2) = SEQ(r1, r2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    42
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    43
fun op $ (x, r) = RECD(x, r)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    44
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    45
fun alts rs = case rs of
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
    46
    [] => ZERO
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    47
  | [r] => r
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    48
  | r::rs => List.foldl (op ++) r rs
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    49
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    50
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    51
(* size of a regular expressions - for testing purposes *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    52
fun size r = case r of
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
    53
    ZERO => 1
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
    54
  | ONE => 1
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    55
  | CHAR(_) => 1
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    56
  | ALT(r1, r2) => 1 + (size r1) + (size r2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    57
  | SEQ(r1, r2) => 1 + (size r1) + (size r2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    58
  | STAR(r) => 1 + (size r)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    59
  | RECD(_, r) => 1 + (size r)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    60
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    61
(* nullable function: tests whether the regular 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    62
   expression can recognise the empty string *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    63
fun nullable r = case r of
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
    64
    ZERO => false
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
    65
  | ONE => true
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    66
  | CHAR(_) => false
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    67
  | ALT(r1, r2) => nullable(r1) orelse nullable(r2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    68
  | SEQ(r1, r2) => nullable(r1) andalso nullable(r2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    69
  | STAR(_) => true
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    70
  | RECD(_, r) => nullable(r)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    71
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    72
(* derivative of a regular expression r w.r.t. a character c *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    73
fun der c r = case r of
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
    74
    ZERO => ZERO
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
    75
  | ONE => ZERO
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
    76
  | CHAR(d) => if c = d then ONE else ZERO
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    77
  | ALT(r1, r2) => ALT(der c r1, der c r2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    78
  | SEQ(r1, r2) => 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    79
      if nullable r1 then ALT(SEQ(der c r1, r2), der c r2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    80
      else SEQ(der c r1, r2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    81
  | STAR(r) => SEQ(der c r, STAR(r))
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    82
  | RECD(_, r) => der c r
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    83
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    84
(* derivative w.r.t. a list of chars (iterates der) *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    85
fun ders s r = case s of 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    86
    [] => r
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    87
  | c::s => ders s (der c r)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    88
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    89
(* extracts a string from value *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    90
fun flatten v = case v of 
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
    91
    Empty => ""
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    92
  | Chr(c) => Char.toString c
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    93
  | Left(v) => flatten v
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    94
  | Right(v) => flatten v
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    95
  | Sequ(v1, v2) => flatten v1 ^ flatten v2
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    96
  | Stars(vs) => String.concat (List.map flatten vs)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    97
  | Rec(_, v) => flatten v
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    98
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    99
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   100
(* extracts an environment from a value *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   101
fun env v = case v of 
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   102
    Empty => []
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   103
  | Chr(c) => []
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   104
  | Left(v) => env v
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   105
  | Right(v) => env v
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   106
  | Sequ(v1, v2) => env v1 @ env v2
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   107
  | Stars(vs) => List.foldr (op @) [] (List.map env vs)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   108
  | Rec(x, v) => (x, flatten v) :: env v
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   109
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   110
fun string_of_pair (x, s) = "(" ^ x ^ "," ^ s ^ ")"
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   111
fun string_of_env xs = String.concatWith "," (List.map string_of_pair xs)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   112
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   113
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   114
(* the value for a nullable rexp *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   115
fun mkeps r = case r of 
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   116
    ONE => Empty
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   117
  | ALT(r1, r2) => 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   118
      if nullable r1 then Left(mkeps r1) else Right(mkeps r2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   119
  | SEQ(r1, r2) => Sequ(mkeps r1, mkeps r2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   120
  | STAR(r) => Stars([])
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   121
  | RECD(x, r) => Rec(x, mkeps r)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   122
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   123
exception Error
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   124
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   125
(* injection of a char into a value *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   126
fun inj r c v = case (r, v) of
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   127
    (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj r c v1 :: vs)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   128
  | (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj r1 c v1, v2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   129
  | (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj r1 c v1, v2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   130
  | (SEQ(r1, r2), Right(v2)) => Sequ(mkeps r1, inj r2 c v2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   131
  | (ALT(r1, r2), Left(v1)) => Left(inj r1 c v1)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   132
  | (ALT(r1, r2), Right(v2)) => Right(inj r2 c v2)
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   133
  | (CHAR(d), Empty) => Chr(d) 
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   134
  | (RECD(x, r1), _) => Rec(x, inj r1 c v)
359
fedc16924b76 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 317
diff changeset
   135
  | _ => raise Error
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   136
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   137
(* some "rectification" functions for simplification *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   138
fun f_id v = v
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   139
fun f_right f = fn v => Right(f v)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   140
fun f_left f = fn v => Left(f v)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   141
fun f_alt f1 f2 = fn v => case v of
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   142
    Right(v) => Right(f2 v)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   143
  | Left(v) => Left(f1 v)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   144
fun f_seq f1 f2 = fn v => case v of 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   145
  Sequ(v1, v2) => Sequ(f1 v1, f2 v2)
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   146
fun f_seq_Empty1 f1 f2 = fn v => Sequ(f1 Empty, f2 v)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   147
fun f_seq_Empty2 f1 f2 = fn v => Sequ(f1 v, f2 Empty)
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   148
fun f_rec f = fn v => case v of
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   149
    Rec(x, v) => Rec(x, f v)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   150
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   151
exception ShouldNotHappen
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   152
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   153
fun f_error v = raise ShouldNotHappen
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   154
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   155
(* simplification of regular expressions returning also an 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   156
   rectification function; no simplification under STARs *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   157
fun simp r = case r of
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   158
    ALT(r1, r2) => 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   159
      let val (r1s, f1s) = simp r1  
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   160
          val (r2s, f2s) = simp r2 in
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   161
        (case (r1s, r2s) of
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   162
            (ZERO, _) => (r2s, f_right f2s)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   163
          | (_, ZERO) => (r1s, f_left f1s)
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   164
          | (_, _)    => if r1s = r2s then (r1s, f_left f1s)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   165
                         else (ALT (r1s, r2s), f_alt f1s f2s))
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   166
      end 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   167
  | SEQ(r1, r2) => 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   168
      let val (r1s, f1s) = simp r1 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   169
          val (r2s, f2s) = simp r2 in
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   170
        (case (r1s, r2s) of
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   171
          (ZERO, _)  => (ZERO, f_error)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   172
        | (_, ZERO)  => (ZERO, f_error)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   173
        | (ONE, _) => (r2s, f_seq_Empty1 f1s f2s)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   174
        | (_, ONE) => (r1s, f_seq_Empty2 f1s f2s)
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   175
        | (_, _)     => (SEQ(r1s, r2s), f_seq f1s f2s))
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   176
      end  
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   177
  | RECD(x, r1) => 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   178
      let val (r1s, f1s) = simp r1 in
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   179
        (RECD(x, r1s), f_rec f1s)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   180
      end
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   181
  | r => (r, f_id)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   182
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   183
fun der_simp c r = case r of
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   184
    ZERO => (ZERO, f_id)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   185
  | ONE => (ZERO, f_id)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   186
  | CHAR(d) => ((if c = d then ONE else ZERO), f_id)
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   187
  | ALT(r1, r2) => 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   188
      let 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   189
        val (r1d, f1d) = der_simp c r1 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   190
        val (r2d, f2d) = der_simp c r2 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   191
      in
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   192
        case (r1d, r2d) of
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   193
          (ZERO, _) => (r2d, f_right f2d)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   194
        | (_, ZERO) => (r1d, f_left f1d)
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   195
        | (_, _)    => if r1d = r2d then (r1d, f_left f1d)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   196
                       else (ALT (r1d, r2d), f_alt f1d f2d)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   197
      end
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   198
  | SEQ(r1, r2) => 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   199
      if nullable r1 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   200
      then 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   201
        let 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   202
          val (r1d, f1d) = der_simp c r1 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   203
          val (r2d, f2d) = der_simp c r2
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   204
          val (r2s, f2s) = simp r2 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   205
        in
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   206
          case (r1d, r2s, r2d) of
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   207
            (ZERO, _, _)  => (r2d, f_right f2d)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   208
          | (_, ZERO, _)  => (r2d, f_right f2d)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   209
          | (_, _, ZERO)  => (SEQ(r1d, r2s), f_left (f_seq f1d f2s))
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   210
          | (ONE, _, _) => (ALT(r2s, r2d), f_alt (f_seq_Empty1 f1d f2s) f2d)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   211
          | (_, ONE, _) => (ALT(r1d, r2d), f_alt (f_seq_Empty2 f1d f2s) f2d)
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   212
          | (_, _, _)     => (ALT(SEQ(r1d, r2s), r2d), f_alt (f_seq f1d f2s) f2d)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   213
        end
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   214
      else 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   215
        let 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   216
          val (r1d, f1d) = der_simp c r1 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   217
          val (r2s, f2s) = simp r2
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   218
        in
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   219
          case (r1d, r2s) of
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   220
            (ZERO, _) => (ZERO, f_error)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   221
          | (_, ZERO) => (ZERO, f_error)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   222
          | (ONE, _) => (r2s, f_seq_Empty1 f1d f2s)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   223
          | (_, ONE) => (r1d, f_seq_Empty2 f1d f2s)
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   224
          | (_, _) => (SEQ(r1d, r2s), f_seq f1d f2s)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   225
  	end	  
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   226
  | STAR(r1) => 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   227
      let 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   228
        val (r1d, f1d) = der_simp c r1 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   229
      in
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   230
        case r1d of
156
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   231
          ZERO => (ZERO, f_error)
6a43ea9305ba updated implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 3
diff changeset
   232
        | ONE => (STAR r1, f_seq_Empty1 f1d f_id)
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   233
        | _ => (SEQ(r1d, STAR(r1)), f_seq f1d f_id)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   234
      end
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   235
  | RECD(x, r1) => der_simp c r1 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   236
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   237
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   238
(* matcher function *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   239
fun matcher r s = nullable(ders (explode s) r)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   240
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   241
(* lexing function (produces a value) *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   242
exception LexError
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   243
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   244
fun lex r s = case s of 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   245
    [] => if (nullable r) then mkeps r else raise LexError
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   246
  | c::cs => inj r c (lex (der c r) cs)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   247
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   248
fun lexing r s = lex r (explode s)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   249
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   250
(* lexing with simplification *)
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   251
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   252
fun fst (a, b) = a
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   253
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   254
fun ders_simp r s = case s of 
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   255
  [] => r
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   256
| c::s => ders_simp (fst (simp (der c r))) s
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   257
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   258
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   259
fun lex_simp r s = case s of 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   260
    [] => if (nullable r) then mkeps r else raise LexError
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   261
  | c::cs => 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   262
    let val (r_simp, f_simp) = simp (der c r) in
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   263
      inj r c (f_simp (lex_simp r_simp cs))
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   264
    end
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   265
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   266
fun lexing_simp r s = lex_simp r (explode s)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   267
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   268
(* does derivatives and simplificatiomn in one step *)
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   269
fun lex_simp2 r s = case s of 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   270
    [] => if (nullable r) then mkeps r else raise LexError
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   271
  | c::cs => 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   272
    let val (r_simp, f_simp) = der_simp c r in
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   273
      inj r c (f_simp (lex_simp2 r_simp cs))
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   274
    end
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   275
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   276
fun lexing_simp2 r s = lex_simp2 r (explode s)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   277
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   278
(* uses an accumulator for the rectification functions *)
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   279
fun lex_acc r s f = case s of 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   280
    [] => if (nullable r) then f (mkeps r) else raise LexError
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   281
  | c::cs => 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   282
    let val (r_simp, f_simp) = simp (der c r) in
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   283
      lex_acc r_simp cs (fn v => f (inj r c (f_simp v)))
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   284
    end
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   285
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   286
fun lexing_acc r s  = lex_acc r (explode s) (f_id)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   287
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   288
fun lex_acc2 r s f = case s of 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   289
    [] => if (nullable r) then f (mkeps r) else raise LexError
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   290
  | c::cs => 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   291
    let val (r_simp, f_simp) = der_simp c r in
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   292
      lex_acc2 r_simp cs (fn v => f (inj r c (f_simp v)))
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   293
    end
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   294
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   295
fun lexing_acc2 r s  = lex_acc2 r (explode s) f_id
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   296
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   297
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   298
(* Lexing rules for a small WHILE language *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   299
val sym = alts (List.map chr (explode "abcdefghijklmnopqrstuvwxyz"))
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   300
val digit = alts (List.map chr (explode "0123456789"))
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   301
val idents =  sym -- STAR(sym ++ digit)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   302
val nums = plus(digit)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   303
val keywords = alts (List.map str ["skip", "while", "do", "if", "then", "else", "read", "write", "true", "false"])
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   304
val semicolon = str ";"
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   305
val ops = alts (List.map str [":=", "==", "-", "+", "*", "!=", "<", ">", "<=", ">=", "%", "/"])
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   306
val whitespace = plus(str " " ++ str "\n" ++ str "\t")
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   307
val rparen = str ")"
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   308
val lparen = str "("
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   309
val begin_paren = str "{"
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   310
val end_paren = str "}"
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   311
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   312
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   313
val while_regs = STAR(("k" $ keywords) ++
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   314
                      ("i" $ idents) ++
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   315
                      ("o" $ ops) ++ 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   316
                      ("n" $ nums) ++ 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   317
                      ("s" $ semicolon) ++ 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   318
                      ("p" $ (lparen ++ rparen)) ++ 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   319
                      ("b" $ (begin_paren ++ end_paren)) ++ 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   320
                      ("w" $ whitespace))
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   321
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   322
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   323
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   324
(* Some Tests
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   325
  ============ *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   326
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   327
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   328
fun time f x =
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   329
  let
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   330
  val t_start = Timer.startCPUTimer()
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   331
  val f_x = (f x; f x; f x; f x; f x)
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   332
  val t_end = Time.toReal(#usr(Timer.checkCPUTimer(t_start))) / 5.0
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   333
in
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   334
  (print ((Real.toString t_end) ^ "\n"); f_x)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   335
end
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   336
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   337
val prog = "ab";
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   338
val reg = ("x" $ ((str "a") -- (str "b")));
359
fedc16924b76 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 317
diff changeset
   339
print("Simp: " ^ (lexing_simp reg prog) ^ "\n");
fedc16924b76 updated
Christian Urban <christian.urban@kcl.ac.uk>
parents: 317
diff changeset
   340
print("Acc:  " ^ (lexing_acc  reg prog) ^ "\n");
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   341
print("Env   " ^ string_of_env (env (lexing_acc reg prog)) ^ "\n");
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   342
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   343
fun fst (x, y) = x;
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   344
fun snd (x, y) = y;
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   345
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   346
val derS = [reg,
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   347
            der #"a" reg,
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   348
            fst (simp (der #"a" reg)),
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   349
            fst (der_simp #"a" reg)];
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   350
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   351
val vS = [(snd (simp (der #"a" reg))) (Chr(#"b")),
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   352
          (snd (der_simp #"a" reg)) (Chr(#"b"))
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   353
         ];
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   354
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   355
print("Ders: \n" ^ 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   356
       String.concatWith "\n" (List.map PolyML.makestring derS)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   357
       ^ "\n\n");
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   358
print("Vs: \n" ^ 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   359
       String.concatWith "\n" (List.map PolyML.makestring vS)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   360
       ^ "\n\n");
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   361
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   362
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   363
val prog0 = "read n";
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   364
print("Env0 is: \n" ^  string_of_env (env (lexing_acc while_regs prog0)) ^ "\n");
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   365
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   366
val prog1 = "read  n; write (n)";
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   367
print("Env1 is: \n" ^ string_of_env (env (lexing_acc while_regs prog1)) ^ "\n");
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   368
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   369
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   370
val prog2 = String.concatWith "\n" 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   371
  ["i := 2;",
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   372
   "max := 100;",
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   373
   "while i < max do {",
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   374
   "  isprime := 1;",
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   375
   "  j := 2;",
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   376
   "  while (j * j) <= i + 1  do {",
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   377
   "    if i % j == 0 then isprime := 0  else skip;",
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   378
   "    j := j + 1",
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   379
   "  };",
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   380
   " if isprime == 1 then write i else skip;",
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   381
   " i := i + 1",
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   382
   "}"];
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   383
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   384
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   385
print("The prog2 string is of length: >>" ^ (PolyML.makestring (String.size prog2)) ^ "<<\n");
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   386
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   387
let 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   388
  val tst = (lexing_simp while_regs prog2 = lexing_acc while_regs prog2)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   389
in
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   390
  print("Sanity test: >>" ^ (PolyML.makestring tst) ^ "<<\n")
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   391
end;
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   392
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   393
print("Size after 50: " ^ 
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   394
  PolyML.makestring(size (ders_simp while_regs (explode (string_repeat prog2 50)))) ^ "\n");
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   395
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   396
print("Size after 5000: " ^ 
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   397
  PolyML.makestring(size (ders_simp while_regs (explode (string_repeat prog2 5000)))) ^ "\n");
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   398
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   399
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   400
(* loops in ML *)
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   401
datatype for = to of int * int
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   402
infix to 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   403
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   404
val for =
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   405
  fn lo to up =>
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   406
    (fn f => 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   407
       let fun loop lo = 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   408
         if lo > up then () else (f lo; loop (lo + 1))
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   409
       in loop lo end);
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   410
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   411
fun forby n =
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   412
  fn lo to up =>
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   413
    (fn f => 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   414
       let fun loop lo = 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   415
         if lo > up then () else (f lo; loop (lo + n))
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   416
       in loop lo end);
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   417
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   418
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   419
fun step_simp i = 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   420
  (print ((Int.toString i) ^ ": ") ;
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   421
   time (lexing_simp while_regs) (string_repeat prog2 i)); 
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   422
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   423
fun step_simp2 i = 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   424
  (print ((Int.toString i) ^ ": ") ;
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   425
   time (lexing_simp2 while_regs) (string_repeat prog2 i)); 
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   426
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   427
fun step_acc i = 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   428
  (print ((Int.toString i) ^ ": ") ;
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   429
   time (lexing_acc while_regs) (string_repeat prog2 i));
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   430
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   431
fun step_acc2 i = 
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   432
  (print ((Int.toString i) ^ ": ") ;
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   433
   time (lexing_acc2 while_regs) (string_repeat prog2 i)); 
3
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   434
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   435
94824659f6d7 added all toy implementations
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   436
317
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   437
print("\nTest step_simp\n");
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   438
val main1 = forby 1000 (1000 to 5000) step_simp;
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   439
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   440
print("\nTest step_simp2\n");
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   441
val main2 = forby 1000 (1000 to 5000) step_simp2;
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   442
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   443
(*
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   444
print("\nTest step_acc\n"); 
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   445
val main3 = forby 1000 (1000 to 5000) step_acc;
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   446
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   447
print("\nTest step_acc2\n");
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   448
val main4 = forby 1000 (1000 to 5000) step_acc2;
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   449
*)
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   450
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   451
db0ff630bbb7 updated
Christian Urban <urbanc@in.tum.de>
parents: 156
diff changeset
   452