From: Lucas Bajolet Date: Wed, 15 Oct 2014 18:15:59 +0000 (-0400) Subject: brainfuck: Added a simple Brainfuck interpreter X-Git-Tag: v0.6.10~26^2 X-Git-Url: http://nitlanguage.org brainfuck: Added a simple Brainfuck interpreter Signed-off-by: Lucas Bajolet --- diff --git a/contrib/brainfuck/README.md b/contrib/brainfuck/README.md new file mode 100644 index 0000000..136b674 --- /dev/null +++ b/contrib/brainfuck/README.md @@ -0,0 +1,34 @@ +# Brainfuck + +Brainfuck is as its name implies a simple Brainfuck interpreter written in Nit. + +It has almost as much purposes as the language itself, except it provides a good example for Nit programs that work while being concise. + +[Specification](http://www.muppetlabs.com/~breadbox/bf/) + +The language is designed to need only a few things : + +* One instruction pointer to the current instruction +* One array of Bytes for all manipulations of data +* One data pointer to select where to write/read data + +Brainfuck a small instruction set, only eight instructions : + +* `>`: Increments the data pointer +* `<`: Decrements the data pointer +* `+`: Increments the byte in the current cell +* `-`: Decrements the byte in the current cell +* `[`: If the current cell's value is 0, jumps to the matching `]` +* `]`: If the current cell's value is non-zero, jumps to the matching `[` +* `.`: Writes the current cell's value to stdout +* `,`: Reads a char from stdin and stores it in the current cell + +## How to use + +First, compile the interpreter with the Nit compiler/interpreter, and launch the program on a brainfuck source file for interpretation. + +Example: +~~~ +nitg ./brainfuck.nit +./brainfuck ./examples/hello.bf +~~~ diff --git a/contrib/brainfuck/brainfuck.nit b/contrib/brainfuck/brainfuck.nit new file mode 100644 index 0000000..b614776 --- /dev/null +++ b/contrib/brainfuck/brainfuck.nit @@ -0,0 +1,134 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Simple brainfuck interpreter +module brainfuck + +# Interpreter for Brainfuck source code. +class BFInterpret + # Data cells + var dr = new Array[Char] + # Data pointer + var dp = 0 + # Instruction pointer + var ip = 0 + + # The program being interpreted + var program: String + + # Contains the set of valid instructions, used in next + var valid_instr: Set[Char] + + # Starts interpretation of file `filename` + init(filename: String) do + var ifs = new IFStream.open(filename.simplify_path) + valid_instr = new HashSet[Char] + valid_instr.add_all "><[].,+-".chars + dr.add 0.ascii + program = ifs.read_all + start + end + + # Starts the interpretation of the loaded program + fun start do + loop + if ip >= program.length then break + eval + next + end + end + + # Go to the next executable instruction + fun next do + ip += 1 + while ip < program.length and not valid_instr.has(program[ip]) do + ip += 1 + end + end + + # Evaluates the current instruction + fun eval do + var instr = program[ip] + if instr == '.' then printn dr[dp] + if instr == '[' then + if dr[dp] == 0.ascii then + ip = find_matching_rbra + return + end + end + if instr == ']' then + if dr[dp] != 0.ascii then + ip = find_matching_lbra + return + end + end + if instr == '>' then + dp += 1 + if dp >= dr.length then dr.add(0.ascii) + end + if instr == '<' then + dp -= 1 + if dp < 0 then abort + end + if instr == '+' then + dr[dp] = (dr[dp].ascii + 1).ascii + end + if instr == '-' then + dr[dp] = (dr[dp].ascii - 1).ascii + end + if instr == ',' then + dr[dp] = getc + end + end + + # Seeks for the position of the matching `]` for the `[` located at `ip` + fun find_matching_rbra: Int do + var pos = ip + 1 + var lbracnt = 0 + loop + if pos > program.length then abort + if program[pos] == ']' then + if lbracnt > 0 then + lbracnt -= 1 + else + break + end + end + if program[pos] == '[' then lbracnt += 1 + pos += 1 + end + return pos + end + + # Seeks for the position of the matching `[` for the `]` located at `ip` + fun find_matching_lbra: Int do + var pos = ip - 1 + var rbracnt = 0 + loop + if pos < 0 then abort + if program[pos] == '[' then + if rbracnt > 0 then + rbracnt -= 1 + else + break + end + end + if program[pos] == ']' then rbracnt += 1 + pos -= 1 + end + return pos + end +end + +var i = new BFInterpret(args[0]) diff --git a/contrib/brainfuck/examples/hello.bf b/contrib/brainfuck/examples/hello.bf new file mode 100644 index 0000000..8fa0f72 --- /dev/null +++ b/contrib/brainfuck/examples/hello.bf @@ -0,0 +1 @@ +++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++. diff --git a/contrib/brainfuck/examples/hello2.bf b/contrib/brainfuck/examples/hello2.bf new file mode 100644 index 0000000..8fc90f6 --- /dev/null +++ b/contrib/brainfuck/examples/hello2.bf @@ -0,0 +1,38 @@ +[ This program prints "Hello World!" and a newline to the screen, its + length is 106 active command characters [it is not the shortest.] + This loop is a "comment loop", it's a simple way of adding a comment + to a BF program such that you don't have to worry about any command + characters. Any ".", ",", "+", "-", "<" and ">" characters are simply + ignored, the "[" and "]" characters just have to be balanced. +] ++++++ +++ Set Cell #0 to 8 +[ + >++++ Add 4 to Cell #1; this will always set Cell #1 to 4 + [ as the cell will be cleared by the loop + >++ Add 2 to Cell #2 + >+++ Add 3 to Cell #3 + >+++ Add 3 to Cell #4 + >+ Add 1 to Cell #5 + <<<<- Decrement the loop counter in Cell #1 + ] Loop till Cell #1 is zero; number of iterations is 4 + >+ Add 1 to Cell #2 + >+ Add 1 to Cell #3 + >- Subtract 1 from Cell #4 + >>+ Add 1 to Cell #6 + [<] Move back to the first zero cell you find; this will + be Cell #1 which was cleared by the previous loop + <- Decrement the loop Counter in Cell #0 +] Loop till Cell #0 is zero; number of iterations is 8 +The result of this is: +Cell No : 0 1 2 3 4 5 6 +Contents: 0 0 72 104 88 32 8 +Pointer : ^ +>>. Cell #2 has value 72 which is 'H' +>---. Subtract 3 from Cell #3 to get 101 which is 'e' ++++++++..+++. Likewise for 'llo' from Cell #3 +>>. Cell #5 is 32 for the space +<-. Subtract 1 from Cell #4 for 87 to give a 'W' +<. Cell #3 was set to 'o' from the end of 'Hello' ++++.------.--------. Cell #3 for 'rl' and 'd' +>>+. Add 1 to Cell #5 gives us an exclamation point +>++. And finally a newline from Cell #6 diff --git a/contrib/brainfuck/examples/rot13.bf b/contrib/brainfuck/examples/rot13.bf new file mode 100644 index 0000000..85a97fa --- /dev/null +++ b/contrib/brainfuck/examples/rot13.bf @@ -0,0 +1,28 @@ +-,+[ Read first character and start outer character reading loop + -[ Skip forward if character is 0 + >>++++[>++++++++<-] Set up divisor (32) for division loop + (MEMORY LAYOUT: dividend copy remainder divisor quotient zero zero) + <+<-[ Set up dividend (x minus 1) and enter division loop + >+>+>-[>>>] Increase copy and remainder / reduce divisor / Normal case: skip forward + <[[>+<-]>>+>] Special case: move remainder back to divisor and increase quotient + <<<<<- Decrement dividend + ] End division loop + ]>>>[-]+ End skip loop; zero former divisor and reuse space for a flag + >--[-[<->+++[-]]]<[ Zero that flag unless quotient was 2 or 3; zero quotient; check flag + ++++++++++++<[ If flag then set up divisor (13) for second division loop + (MEMORY LAYOUT: zero copy dividend divisor remainder quotient zero zero) + >-[>+>>] Reduce divisor; Normal case: increase remainder + >[+[<+>-]>+>>] Special case: increase remainder / move it back to divisor / increase quotient + <<<<<- Decrease dividend + ] End division loop + >>[<+>-] Add remainder back to divisor to get a useful 13 + >[ Skip forward if quotient was 0 + -[ Decrement quotient and skip forward if quotient was 1 + -<<[-]>> Zero quotient and divisor if quotient was 2 + ]<<[<<->>-]>> Zero divisor and subtract 13 from copy if quotient was 1 + ]<<[<<+>>-] Zero divisor and add 13 to copy if quotient was 0 + ] End outer skip loop (jump to here if ((character minus 1)/32) was not 2 or 3) + <[-] Clear remainder from first division if second division was skipped + <.[-] Output ROT13ed character from copy and clear it + <-,+ Read next character +] End character reading loop