Execute Brain****/OCaml: Difference between revisions
Content added Content deleted
mNo edit summary |
m (Fixed syntax highlighting.) |
||
(6 intermediate revisions by 5 users not shown) | |||
Line 1: | Line 1: | ||
{{implementation|Brainf***}}{{collection|RCBF}} |
{{implementation|Brainf***}}{{collection|RCBF}} |
||
Quick implementation of a [[Brainfuck]] interpreter in OCaml. |
Quick implementation of a [[Brainfuck]] interpreter in [[OCaml]]. |
||
Like the Haskell version but without the lazy lists: |
Like the [[Haskell]] [[RCBF/Haskell|version]] but without the lazy lists: |
||
Pairs of lists are used to implement both the two-side infinite band of cells, and the program storage. |
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 '' |
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. |
||
<syntaxhighlight lang="ocaml">let move_left (x::l, r) = (l, x::r) |
|||
let move_right (l, x::r) = (x::l, r) |
|||
val move_left : 'a list * 'a list -> 'a list * 'a list = <fun> |
|||
let rec match_left d = |
|||
# let move_right (l, x::r) = (x::l, r);; |
|||
match d with |
|||
val move_right : 'a list * 'a list -> 'a list * 'a list = <fun> |
|||
'['::_, _ -> |
|||
d |
|||
# let rec match_left d = |
|||
| ']'::_, _ -> |
|||
match_left (move_left (match_left (move_left d))) |
|||
'['::_, _ -> |
|||
| _ -> |
|||
match_left (move_left d) |
|||
| ']'::_, _ -> |
|||
match_left (move_left (match_left (move_left d))) |
|||
let rec match_right d = |
|||
| _ -> |
|||
match d with |
|||
match_left (move_left d);; |
|||
_, '['::_ -> |
|||
val match_left : char list * char list -> char list * char list = <fun> |
|||
move_right d |
|||
| _, '['::_ -> |
|||
# let rec match_right d = |
|||
match_right (match_right (move_right d)) |
|||
match d with |
|||
| _ -> |
|||
move_right d |
match_right (move_right d) |
||
| _, '['::_ -> |
|||
let pad = function |
|||
match_right (match_right (move_right d)) |
|||
[], [] -> [0], [0] |
|||
| [], r -> [0], r |
|||
match_right (move_right d);; |
|||
| l, [] -> l, [0] |
|||
val match_right : char list * char list -> char list * char list = <fun> |
|||
| d -> d;; |
|||
# let pad = function |
|||
let modify f (l, x::r) = l, f x :: r |
|||
| [], r -> [0], r |
|||
let rec exec p d = |
|||
| l, [] -> l, [0] |
|||
match p, d with |
|||
(_, []), _ -> () |
|||
| (_, '>'::_), _ -> |
|||
exec (move_right p) (pad (move_right d)) |
|||
# let modify f (l, x::r) = l, f x :: r;; |
|||
| (_, '<'::_), _ -> |
|||
exec (move_right p) (pad (move_left d)) |
|||
| (_, '+'::_), _ -> |
|||
# let dec x = |
|||
exec (move_right p) (modify succ d) |
|||
if x = 0 then 0 |
|||
| (_, '-'::_), _ -> |
|||
else x - 1;; |
|||
exec (move_right p) (modify pred d) |
|||
val dec : int -> int = <fun> |
|||
| (_, ','::_), _ -> |
|||
let c = read_int () in |
|||
# let rec exec p d = |
|||
exec (move_right p) (modify (fun _ -> c) d) |
|||
match p, d with |
|||
| (_, '.'::_), (_, x::_) -> |
|||
print_int x; |
|||
| (_, '>'::_), _ -> |
|||
print_newline (); |
|||
exec (move_right p) (pad (move_right d)) |
|||
exec (move_right p) d |
|||
| (_, '<'::_), _ -> |
|||
| (_, '['::_), (_, 0::_) -> |
|||
exec (move_right p) (pad (move_left d)) |
|||
exec (match_right (move_right p)) d |
|||
| (_, '+'::_), _ -> |
|||
| (_, '['::_), _ -> |
|||
exec (move_right p) d |
|||
| (_, '-'::_), _ -> |
|||
| (_, ']'::_), (_, 0::_) -> |
|||
exec (move_right p) (modify dec d) |
|||
exec (move_right p) d |
|||
| (_, ','::_), _ -> |
|||
| (_, ']'::_), _ -> |
|||
exec (match_left (move_left p)) d |
|||
| (_, '.'::_), (_, x::_) -> |
|||
let run s = exec ([], s) ([0], [0])</syntaxhighlight> |
|||
print_int x; |
|||
print_newline (); |
|||
Example output: |
|||
exec (move_right p) d |
|||
| (_, '['::_), (_, 0::_) -> |
|||
<pre># let char_list_of_string s = |
|||
exec (match_right (move_right p)) d |
|||
let result = ref [] in |
|||
| (_, '['::_), _ -> |
|||
String.iter (fun c -> result := c :: !result) s; |
|||
List.rev !result;; |
|||
| (_, ']'::_), (_, 0::_) -> |
|||
val char_list_of_string : string -> char list = <fun> |
|||
exec (move_right p) d |
|||
| (_, ']'::_), _ -> |
|||
# run (char_list_of_string ",[>+<-].>.");; |
|||
exec (match_left (move_left p)) d;; |
|||
''5'' |
|||
val exec : char list * char list -> int list * int list -> unit = <fun> |
|||
0 |
|||
5 |
|||
# let run s = exec ([], s) ([0], [0]);; |
|||
- : unit = ()</pre> |
|||
# let char_list_of_string s = |
|||
let result = ref [] in |
|||
String.iter (fun c -> result := c :: !result) s; |
|||
List.rev !result;; |
|||
val char_list_of_string : string -> char list = <fun> |
|||
# run (char_list_of_string ",[>+<-].>.");; |
|||
''5'' |
|||
0 |
|||
5 |
|||
- : unit = () |
Latest revision as of 11:48, 1 September 2022
Execute Brain****/OCaml is an implementation of Brainf***.
Other implementations of Brainf***.
Execute Brain****/OCaml is part of RCBF. You may find other members of RCBF at Category:RCBF.
Quick implementation of a Brainfuck interpreter in OCaml.
Like the Haskell version but without the lazy lists:
Pairs of lists are used to implement both the two-side infinite band of cells, and the program storage.
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 match_left and match_right which need linear time.
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 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 pred 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])
Example output:
# let char_list_of_string s = let result = ref [] in String.iter (fun c -> result := c :: !result) s; List.rev !result;; val char_list_of_string : string -> char list = <fun> # run (char_list_of_string ",[>+<-].>.");; ''5'' 0 5 - : unit = ()