Execute Brain****/OCaml: Difference between revisions

Content added Content deleted

Inline

@@ Line 6: / Line 6: @@
 Pairs of lists are used to implement both the two-side infinite band of cells, and the program storage.
-''run'' interprets a Brainfuck program and reads integers from ''stdin'' and outputs them to ''stdout''.
+''run'' interprets a Brainfuck program as a list of characters and reads integers from ''stdin'' and outputs them to ''stdout''.
-A more efficient implementation could for example only admit well-bracketed brainfuck programs, and parse bracket blocks first, to replace the ''matchLeft'' and ''matchRight'' which need linear time.
+A more efficient implementation could for example only admit well-bracketed brainfuck programs, and parse bracket blocks first, to replace the ''match_left'' and ''match_right'' which need linear time.
+<ocaml>
+let move_left  (x::l, r) = (l, x::r)
+let move_right (l, x::r) = (x::l, r)
+let rec match_left d =
+  match d with
+    '['::_, _ ->
+      d
+  | ']'::_, _ ->
+      match_left (move_left (match_left (move_left d)))
+  | _ ->
+      match_left (move_left d)
+let rec match_right d =
+  match d with
+    _, '['::_ ->
+      move_right d
+  | _, '['::_ ->
+      match_right (match_right (move_right d))
+  | _ ->
+      match_right (move_right d)
+let pad = function
+    [], [] -> [0], [0]
+  | [], r  -> [0], r
+  | l,  [] -> l,   [0]
+  | d      -> d;;
+let modify f (l, x::r) = l, f x :: r
+let dec x =
+  if x = 0 then 0
+  else x - 1
+let rec exec p d =
+  match p, d with
+    (_, []),     _         -> ()
+  | (_, '>'::_), _         ->
+      exec (move_right p) (pad (move_right d))
+  | (_, '<'::_), _         ->
+      exec (move_right p) (pad (move_left  d))
+  | (_, '+'::_), _         ->
+      exec (move_right p) (modify succ d)
+  | (_, '-'::_), _         ->
+      exec (move_right p) (modify dec  d)
+  | (_, ','::_), _         ->
+      let c = read_int () in
+        exec (move_right p) (modify (fun _ -> c) d)
+  | (_, '.'::_), (_, x::_) ->
+      print_int x;
+      print_newline ();
+      exec (move_right p) d
+  | (_, '['::_), (_, 0::_) ->
+      exec (match_right (move_right p)) d
+  | (_, '['::_), _         ->
+      exec (move_right p) d
+  | (_, ']'::_), (_, 0::_) ->
+      exec (move_right p) d
+  | (_, ']'::_), _         ->
+      exec (match_left (move_left p)) d
+let run s = exec ([], s) ([0], [0])
+</ocaml>
+Example output:
- # let move_left  (x::l, r) = (l, x::r);;
- val move_left : 'a list * 'a list -> 'a list * 'a list = <fun>
- # let move_right (l, x::r) = (x::l, r);;
- val move_right : 'a list * 'a list -> 'a list * 'a list = <fun>
- # let rec match_left d =
-   match d with
-     '['::_, _ ->
-       d
-   | ']'::_, _ ->
-       match_left (move_left (match_left (move_left d)))
-   | _ ->
-       match_left (move_left d);;
- val match_left : char list * char list -> char list * char list = <fun>
- # let rec match_right d =
-   match d with
-     _, '['::_ ->
-       move_right d
-   | _, '['::_ ->
-       match_right (match_right (move_right d))
-   | _ ->
-       match_right (move_right d);;
- val match_right : char list * char list -> char list * char list = <fun>
- # let pad = function
-     [], [] -> [0], [0]
-   | [], r  -> [0], r
-   | l,  [] -> l,   [0]
-   | d      -> d;;
- val pad : int list * int list -> int list * int list = <fun>
- # let modify f (l, x::r) = l, f x :: r;;
- val modify : ('a -> 'a) -> 'b * 'a list -> 'b * 'a list = <fun>
- # let dec x =
-   if x = 0 then 0
-   else x - 1;;
- val dec : int -> int = <fun>
- # let rec exec p d =
-   match p, d with
-     (_, []),     _         -> ()
-   | (_, '>'::_), _         ->
-       exec (move_right p) (pad (move_right d))
-   | (_, '<'::_), _         ->
-       exec (move_right p) (pad (move_left  d))
-   | (_, '+'::_), _         ->
-       exec (move_right p) (modify succ d)
-   | (_, '-'::_), _         ->
-       exec (move_right p) (modify dec  d)
-   | (_, ','::_), _         ->
-       let c = read_int () in
-         exec (move_right p) (modify (fun _ -> c) d)
-   | (_, '.'::_), (_, x::_) ->
-       print_int x;
-       print_newline ();
-       exec (move_right p) d
-   | (_, '['::_), (_, 0::_) ->
-       exec (match_right (move_right p)) d
-   | (_, '['::_), _         ->
-       exec (move_right p) d
-   | (_, ']'::_), (_, 0::_) ->
-       exec (move_right p) d
-   | (_, ']'::_), _         ->
-       exec (match_left (move_left p)) d;;
- val exec : char list * char list -> int list * int list -> unit = <fun>
- # let run s = exec ([], s) ([0], [0]);;
- val run : char list -> unit = <fun>
  # let char_list_of_string s =
    let result = ref [] in