Commits

vfiack  committed a13a871

brainfuck interpreter

  • Participants
  • Parent commits d77a23f

Comments (0)

Files changed (3)

File brainfuck/brainfuck.ml

+type token =
+  | IncrPtr | DecrPtr
+  | IncrData | DecrData
+  | Write | Read
+  | Open | Close
+  | Comment of char
+
+module Lexer = struct
+  let tokenize = function
+    | '>' -> IncrPtr
+    | '<' -> DecrPtr
+    | '+' -> IncrData
+    | '-' -> DecrData
+    | '.' -> Write
+    | ',' -> Read
+    | '[' -> Open
+    | ']' -> Close
+    | c -> Comment c
+  
+  let to_list charstream =
+    let tokens = ref [] in
+    Stream.iter (fun t -> tokens := (tokenize t) :: !tokens) charstream;
+    List.rev !tokens
+end
+
+type operation =
+  | PtrAdd of int
+  | DataAdd of int
+  | Output
+  | Input
+  | Conditional of operation list
+
+module Compiler = struct  
+  let string_of_op ops =    
+    let open Printf in 
+    let rec to_string indent = function
+    | PtrAdd i -> sprintf "%sPtrAdd(%d)" indent i
+    | DataAdd i -> sprintf "%sDataAdd(%d)" indent i
+    | Output -> sprintf "%sOutput" indent
+    | Input -> sprintf "%sInput" indent
+    | Conditional nodes ->
+        sprintf "%sConditional <<\n%s\n%sConditional >>"
+        indent
+        (String.concat "\n" (List.map (to_string ("| "^indent)) nodes))
+        indent
+    in to_string "" ops        
+  
+  let ptr_add tokens =
+    let rec loop i lst = match lst with
+      | IncrPtr :: rest -> loop (succ i) rest
+      | DecrPtr :: rest -> loop (pred i) rest
+      | _ -> (PtrAdd i), lst
+    in
+    loop 0 tokens
+  
+  let data_add tokens =
+    let rec loop i lst = match lst with
+      | IncrData :: rest -> loop (succ i) rest
+      | DecrData :: rest -> loop (pred i) rest
+      | _ -> (DataAdd i), lst
+    in
+    loop 0 tokens
+  
+  let conditional tokens =
+    let rec loop acc opened = function
+      | [] -> failwith "malformed conditional"
+      | Open :: rest -> loop (Open :: acc) (succ opened) rest
+      | Close :: rest ->
+          if opened = 0 then (List.rev acc), rest
+          else loop (Close :: acc) (pred opened) rest
+      | other:: rest -> loop (other :: acc) opened rest
+    in
+    loop [] 0 (List.tl tokens)
+  
+  let rec compile tokens =
+    let rec loop tokens acc =
+      match tokens with
+      | [] -> acc
+      | (IncrPtr|DecrPtr) :: _  ->
+          let op, rest = ptr_add tokens in
+          loop rest (op:: acc)
+      | (IncrData|DecrData) :: _ ->
+          let op, rest = data_add tokens in
+          loop rest (op:: acc)
+      | Write :: rest -> loop rest (Output :: acc)
+      | Read :: rest -> loop rest (Input :: acc)
+      | Open :: rest ->
+          let sublist, rest = conditional tokens in
+          let cond = compile sublist in
+          loop rest ((Conditional cond) :: acc)
+      | Close :: rest -> failwith "Close should have been consumed by conditional"
+      | (Comment _) :: rest -> loop rest acc
+    in
+    List.rev (loop tokens [])
+end
+
+module Vm = struct
+  let memory = Array.make 30_000 0
+  let pointer = ref 0
+  
+  let rec exec ast =
+    let exec_node = function
+      | PtrAdd i -> pointer := !pointer + i
+      | DataAdd i -> memory.(!pointer) <- memory.(!pointer) + i
+      | Output -> Printf.printf "%c%!" (char_of_int memory.(!pointer))
+      | Input ->
+        let c = input_char stdin in
+        memory.(!pointer) <- int_of_char c
+      | Conditional nodes ->
+          while memory.(!pointer) <> 0 do
+            exec nodes;
+          done
+    in
+    List.iter exec_node ast
+end
+
+let output ast =   
+  List.iter (fun op -> print_endline (Compiler.string_of_op op)) ast
+
+let brainfuck dump filename =
+  let stream = Stream.of_channel (open_in filename) in
+  let tokens = Lexer.to_list stream in
+  let ast = Compiler.compile tokens in
+  if !dump then output ast else Vm.exec ast
+
+let _ = 
+  let dump = ref false in
+  let args = [("-dump", Arg.Set dump, "dump ast, don't execute")] in
+  Arg.parse args (brainfuck dump) "usage"

File brainfuck/hello.bf

+ ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

File brainfuck/prime.bf

+===================================================================
+======================== OUTPUT STRING ============================
+===================================================================
+>++++++++[<++++++++>-]<++++++++++++++++.[-]
+>++++++++++[<++++++++++>-]<++++++++++++++.[-]
+>++++++++++[<++++++++++>-]<+++++.[-]
+>++++++++++[<++++++++++>-]<+++++++++.[-]
+>++++++++++[<++++++++++>-]<+.[-]
+>++++++++++[<++++++++++>-]<+++++++++++++++.[-]
+>+++++[<+++++>-]<+++++++.[-]
+>++++++++++[<++++++++++>-]<+++++++++++++++++.[-]
+>++++++++++[<++++++++++>-]<++++++++++++.[-]
+>+++++[<+++++>-]<+++++++.[-]
+>++++++++++[<++++++++++>-]<++++++++++++++++.[-]
+>++++++++++[<++++++++++>-]<+++++++++++.[-]
+>+++++++[<+++++++>-]<+++++++++.[-]
+>+++++[<+++++>-]<+++++++.[-]
+
+===================================================================
+======================== INPUT NUMBER  ============================
+===================================================================
++                          cont=1
+[
+ -                         cont=0
+ >,
+ ======SUB10======
+ ----------
+ 
+ [                         not 10
+  <+>                      cont=1
+  =====SUB38======
+  ----------
+  ----------
+  ----------
+  --------
+
+  >
+  =====MUL10=======
+  [>+>+<<-]>>[<<+>>-]<     dup
+
+  >>>+++++++++
+  [
+   <<<
+   [>+>+<<-]>>[<<+>>-]<    dup
+   [<<+>>-]
+   >>-
+  ]
+  <<<[-]<
+  ======RMOVE1======
+  <
+  [>+<-]
+ ]
+ <
+]
+>>[<<+>>-]<<
+
+===================================================================
+======================= PROCESS NUMBER  ===========================
+===================================================================
+
+==== ==== ==== ====
+numd numu teid teiu
+==== ==== ==== ====
+
+>+<-
+[
+ >+
+ ======DUP======
+ [>+>+<<-]>>[<<+>>-]<
+
+ >+<--
+
+ >>>>>>>>+<<<<<<<<   isprime=1
+
+ [
+  >+
+
+  <-
+
+  =====DUP3=====
+  <[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<<
+
+  =====DUP2=====
+  >[>>+>+<<<-]>>>[<<<+>>>-]<<< <
+
+
+  >>>
+
+
+  ====DIVIDES=======
+  [>+>+<<-]>>[<<+>>-]<   DUP i=div
+  
+  <<
+  [
+    >>>>>+               bool=1
+    <<<
+    [>+>+<<-]>>[<<+>>-]< DUP
+    [>>[-]<<-]           IF i THEN bool=0
+    >>
+    [                    IF i=0
+      <<<<
+      [>+>+<<-]>>[<<+>>-]< i=div
+      >>>
+      -                  bool=0
+    ]
+    <<<
+    -                    DEC i
+    <<
+    -
+  ]
+  
+  +>>[<<[-]>>-]<<          
+  >[-]<                  CLR div
+  =====END DIVIDES====
+
+
+  [>>>>>>[-]<<<<<<-]     if divides then isprime=0
+
+
+  <<
+
+  >>[-]>[-]<<<
+ ]
+
+ >>>>>>>>
+ [
+  -
+  <<<<<<<[-]<<
+
+  [>>+>+<<<-]>>>[<<<+>>>-]<<<
+
+  >>
+
+
+
+
+  ===================================================================
+  ======================== OUTPUT NUMBER  ===========================
+  ===================================================================
+  [>+<-]>
+ 
+  [
+   ======DUP======
+   [>+>+<<-]>>[<<+>>-]<
+  
+  
+   ======MOD10====
+   >+++++++++<
+   [
+    >>>+<<              bool= 1
+    [>+>[-]<<-]         bool= ten==0
+    >[<+>-]             ten = tmp
+    >[<<++++++++++>>-]  if ten=0 ten=10
+    <<-                 dec ten     
+    <-                  dec num
+   ]
+   +++++++++            num=9
+   >[<->-]<             dec num by ten
+  
+   =======RROT======
+      [>+<-]
+   <  [>+<-]
+   <  [>+<-]
+   >>>[<<<+>>>-]
+   <
+  
+   =======DIV10========
+   >+++++++++<
+   [
+    >>>+<<                bool= 1
+    [>+>[-]<<-]           bool= ten==0
+    >[<+>-]               ten = tmp
+    >[<<++++++++++>>>+<-] if ten=0 ten=10  inc div
+    <<-                   dec ten     
+    <-                    dec num
+   ]
+   >>>>[<<<<+>>>>-]<<<<   copy div to num
+   >[-]<                  clear ten
+  
+   =======INC1=========
+   <+>
+  ]
+  
+  <
+  [
+   =======MOVER=========
+   [>+<-]
+  
+   =======ADD48========
+   +++++++[<+++++++>-]<->
+  
+   =======PUTC=======
+   <.[-]>
+  
+   ======MOVEL2========
+   >[<<+>>-]<
+  
+   <-
+  ]
+ 
+  >++++[<++++++++>-]<.[-]
+ 
+  ===================================================================
+  =========================== END FOR ===============================
+  ===================================================================
+
+
+  >>>>>>>
+ ]
+ <<<<<<<<
+
+
+
+ >[-]<
+  [-]
+ <<-
+]
+ 
+======LF========
+ 
+++++++++++.[-]