1 // Part 2 about an Interpreter for the Brainf*** language

     2 //========================================================

     3 

     4 object CW8b {

     5 

     6 type Mem = Map[Int, Int]

     7 

     8 // (2a) Complete the functions for safely reading  

     9 // and writing brainf*** memory. Safely read should

    10 // Return the value stored in the Map for a given memory

    11 // pointer, if it exists; otherwise it Returns 0. The

    12 // writing function generates a new Map with the

    13 // same data, except at the given memory pointer the

    14 // value v is stored.

    15 

    16 

    17 //def sread(mem: Mem, mp: Int) : Int = ...

    18 

    19 //def write(mem: Mem, mp: Int, v: Int) : Mem = ...

    20 

    21 

    22 // (2b) Implement the two jumping instructions in the 

    23 // brainf*** language. In jumpRight, given a program and 

    24 // a program counter move the counter to the right 

    25 // until the command after the *matching* ]-command. Similarly, 

    26 // jumpLeft implements the move to the left to just after

    27 // the *matching* [-command. The levels are used to find the

    28 // *matching* bracket.

    29 

    30 //def jumpRight(prog: String, pc: Int, level: Int) : Int = ...

    31 

    32 //def jumpLeft(prog: String, pc: Int, level: Int) : Int = ...

    33 

    34 

    35 

    36 // (2c) Complete the run function that interprets (runs) a brainf***

    37 // program: the arguments are a program, a program counter,

    38 // a memory counter and a brainf*** memory. It Returns the

    39 // memory at the stage when the execution of the brainf*** program

    40 // finishes. The interpretation finishes once the program counter

    41 // pc is pointing to something outside the program string.

    42 // If the pc points to a character inside the program, the pc, 

    43 // memory pointer and memory need to be updated according to 

    44 // rules of the brainf*** language. Then, recursively, the run 

    45 // function continues with the command at the new program

    46 // counter. 

    47 //

    48 // Implement the start function that calls run with the program

    49 // counter and memory counter set to 0.

    50 

    51 //def run(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = ...

    52 

    53 //def start(prog: String, mem: Mem) = ...

    54 

    55 

    56 

    57 

    58 

    59 

    60 // some sample bf programs collected from the Internet

    61 //==================================================

    62 

    63 

    64 /*

    65 // first some contrived (small) programs

    66 

    67 // clears the 0-cell

    68 start("[-]", Map(0 -> 100)) 

    69 

    70 // copies content of the 0-cell to 1-cell

    71 start("[->+<]", Map(0 -> 10))

    72 

    73 // copies content of the 0-cell to 2-cell and 4-cell

    74 start("[>>+>>+<<<<-]", Map(0 -> 42))

    75 

    76 start("+++[>+++++<-]", Map(0 -> 10))

    77 

    78 

    79 // prints out numbers 0 to 9

    80 start("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""", Map())

    81 

    82 

    83 // some more "useful" programs

    84 

    85 // hello world program 1

    86 start("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++

    87        ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", Map())

    88 

    89 // hello world program 2

    90 start("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+

    91       +.<<+++++++++++++++.>.+++.------.--------.>+.>.""", Map())

    92 

    93 

    94 // draws the Sierpinski triangle

    95 start("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[

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

    97       ]>.>+[>>]>+]""", Map())

    98 

    99 //Fibonacci numbers below 100

   100 start("""+++++++++++

   101       >+>>>>++++++++++++++++++++++++++++++++++++++++++++

   102       >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>

   103       +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-

   104       <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<

   105       -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]

   106       >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++

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

   108       ++++++++++++++++++++++++++++++++++++++++++++.[-]<<

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

   110       [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""", Map())

   111 

   112 

   113 //outputs the square numbers up to 10000

   114 start("""++++[>+++++<-]>[<+++++>-]+<+[

   115     >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+

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

   117     <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""", Map())

   118 

   119 

   120 //Collatz numbers (need to be typed in)

   121 start(""">,[[----------[

   122       >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<]

   123       ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[

   124       <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>]

   125       >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]]

   126       >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>>

   127       ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""", Map())

   128 

   129 

   130 // infinite Collatz (never stops)

   131 start(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[<

   132       <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++

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

   134       [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>->

   135       [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[

   136       <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+

   137       ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<

   138       +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<-

   139       ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<-

   140       >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>

   141       -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++

   142       +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[<

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

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

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

   146       [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""", Map())

   147 

   148 

   149 */ 

   150 

   151 }