Skip to content

Instantly share code, notes, and snippets.

@Eloitor

Eloitor/Brainfuck.fm

Last active December 28, 2019 23:14
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Eloitor/af876876c0b95d543621c4540758de31 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Eloitor/af876876c0b95d543621c4540758de31 to your computer and use it in GitHub Desktop.
Download ZIP
Brainfuck interpreter on Formality
Raw
Brainfuck.fm
import Base#
T Tape
| tape(left: List(Number), current: Number, right: List(Number))
newTape: Tape
tape(nil(_), 0, nil(_))
T Instruction
| right
| left
| inc
| dec
| write
| read
| loop(code: List(Instruction))
Program: Type
List(Instruction)
// > Move to the right, extend the tape if necessary
Right(t: Tape): Tape
case t
| tape =>
case t.right as r
| nil => tape(cons(_ t.current, t.left), 0 , nil(_))
| cons => tape(cons(_ t.current, t.left), r.head, r.tail)
// < Move to the left, extend the tape if necessary
Left(t: Tape): Tape
case t
| tape =>
case t.left as l
| nil => tape(nil(_), 0, cons(_ t.current, t.right))
| cons => tape(l.tail, l.head, cons(_ t.current, t.right))
// . Write to screen
Write(t: Tape): IO(Unit)
case t
| tape => //print(number_to_string(10,t.current) )
print(cons(_ t.current, nil(_)))
//UNCOMMENT TO PRINT CHARACTERS
// , Read from user
Read(t: Tape): IO(Tape)
do {
var num = question("Enter character")
case t
| tape => return(_ tape(t.left, head(_ 0, num) , t.right))
}
Inc(t: Tape): Tape
case t
| tape => tape(t.left, t.current .+. 1, t.right)
Dec(t: Tape): Tape
case t
| tape => tape(t.left, t.current .-. 1, t.right)
// ignore everithing before the matching ']'
ignoreLoop(s: String): String
case s
| nil => nil(Char;)
| cons =>
if s.head .==. '[' then
case ignoreLoop(s.tail) as code
| nil => nil(_)
| cons => ignoreLoop(code.tail)
: String
else if s.head .==. ']' then
s.tail
else
ignoreLoop(s.tail)
: String
compile(s: String): Program
case s
| nil => nil(_)
| cons =>
// Right/Left
if s.head .==. '<' then
cons(_ left , compile(s.tail))
else if s.head .==. '>' then
cons(_ right , compile(s.tail))
// Inc/Dec
else if s.head .==. '+' then
cons(_ inc , compile(s.tail))
else if s.head .==. '-' then
cons(_ dec , compile(s.tail))
// Write/Read
else if s.head .==. '.' then
cons(_ write , compile(s.tail))
else if s.head .==. ',' then
cons(_ read , compile(s.tail))
// Loops (possibly nested)
else if s.head .==. '[' then
cons(_ loop(compile(s.tail)), compile(ignoreLoop(s.tail)))
else if s.head .==. ']' then
nil(_)
//ignores char
else
compile(s.tail)
: Program
// For testing purposes
toBrainFuck(p : List(Instruction)) : String
case p
| nil => nil(_)
| cons =>
case p.head as ins
+ toBrainFuck : List(Instruction) -> String
| right => cons(_ '>', toBrainFuck(p.tail))
| left => cons(_ '<', toBrainFuck(p.tail))
| inc => cons(_ '+', toBrainFuck(p.tail))
| dec => cons(_ '-', toBrainFuck(p.tail))
| write => cons(_ '.', toBrainFuck(p.tail))
| read => cons(_ ',', toBrainFuck(p.tail))
| loop =>
concat(_ concat(_ cons(_ '[' , toBrainFuck(ins.code)), "]"), toBrainFuck(p.tail))
// Helper for run,
Loop(p: Program, t: Tape): IO(Tape)
case t
| tape =>
if t.current .==. 0 then
return(_ t) // skips the loop
else
do{
var newtape = run(p, t) // runs the loop
Loop(p, newtape) // repeat
}
run(p: Program, t: Tape): IO(Tape)
do{
case p
| nil => return(_ t)
| cons => case p.head as ins
+ run : Program -> Tape -> IO(Tape)
| right => run(p.tail, Right(t))
| left => run(p.tail, Left(t))
| inc => run(p.tail, Inc(t))
| dec => run(p.tail, Dec(t))
| write =>
do{
Write(t)
run(p.tail, t)
}
| read =>
do{
var tape = Read(t)
run(p.tail, tape)
}
| loop =>
do{
var tape = Loop(ins.code, t)
run(p.tail, tape)
}
}
main : IO(Tape)
let helloWorld = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++."
let p = compile(helloWorld)
do{
print(toBrainFuck(p)) // prints back the code
run(p,newTape)
}
Raw
PureBrainfuck.fm
import Base#
T Tape
| tape(left: List(Number), current: Number, right: List(Number), input: String, output: String)
newTape(input: String): Tape
tape(nil(_), 0, nil(_), input ,"")
T Instruction
| right
| left
| inc
| dec
| write
| read
| loop(code: List(Instruction))
Program: Type
List(Instruction)
// > Move to the right, extend the tape if necessary
Right(t: Tape): Tape
case t
| tape =>
case t.right as r
| nil => tape(cons(_ t.current, t.left), 0 , nil(_), t.input, t.output)
| cons => tape(cons(_ t.current, t.left), r.head, r.tail, t.input, t.output)
// < Move to the left, extend the tape if necessary
Left(t: Tape): Tape
case t
| tape =>
case t.left as l
| nil => tape(nil(_), 0, cons(_ t.current, t.right), t.input, t.output)
| cons => tape(l.tail, l.head, cons(_ t.current, t.right), t.input, t.output)
// . Write to screen
Write(t: Tape): Tape
case t
| tape => tape(t.left, t.current, t.right, t.input, concat(Char; t.output, [t.current] ))
// , Read from user
Read(t: Tape): Tape
case t
| tape => case t.input as inp
| nil => tape(t.left, 0 , t.right, nil(_), t.output)
| cons => tape(t.left, inp.head , t.right, inp.tail, t.output)
Inc(t: Tape): Tape
case t
| tape => tape(t.left, t.current .+. 1, t.right, t.input, t.output)
Dec(t: Tape): Tape
case t
| tape => tape(t.left, t.current .-. 1, t.right, t.input, t.output)
// ignore everithing before the matching ']'
ignoreLoop(s: String): String
case s
| nil => nil(Char;)
| cons =>
if s.head .==. '[' then
case ignoreLoop(s.tail) as code
| nil => nil(_)
| cons => ignoreLoop(code.tail)
:String
else if s.head .==. ']' then
s.tail
else
ignoreLoop(s.tail)
: String
compile(s: String): Program
case s
| nil => nil(_)
| cons =>
// Right/Left
if s.head .==. '<' then
cons(_ left , compile(s.tail))
else if s.head .==. '>' then
cons(_ right , compile(s.tail))
// Inc/Dec
else if s.head .==. '+' then
cons(_ inc , compile(s.tail))
else if s.head .==. '-' then
cons(_ dec , compile(s.tail))
// Write/Read
else if s.head .==. '.' then
cons(_ write , compile(s.tail))
else if s.head .==. ',' then
cons(_ read , compile(s.tail))
// Loops (possibly nested)
else if s.head .==. '[' then
cons(_ loop(compile(s.tail)), compile(ignoreLoop(s.tail)))
else if s.head .==. ']' then
nil(_)
//ignores char
else
compile(s.tail)
: Program
// For testing purposes
toBrainFuck(p : List(Instruction)) : String
case p
| nil => nil(_)
| cons =>
case p.head as ins
+ toBrainFuck : List(Instruction) -> String
| right => cons(_ '>', toBrainFuck(p.tail))
| left => cons(_ '<', toBrainFuck(p.tail))
| inc => cons(_ '+', toBrainFuck(p.tail))
| dec => cons(_ '-', toBrainFuck(p.tail))
| write => cons(_ '.', toBrainFuck(p.tail))
| read => cons(_ ',', toBrainFuck(p.tail))
| loop =>
concat(_ concat(_ cons(_ '[' , toBrainFuck(ins.code)), "]"), toBrainFuck(p.tail))
// Helper for run,
Loop(p: Program, t: Tape): Tape
case t
| tape =>
if t.current .==. 0 then
t // skips the loop
else
let newtape = run(p, t) // runs the loop
Loop(p, newtape) // repeat
run(p: Program, t: Tape): Tape
case p
| nil => t
| cons => case p.head as ins
+ run : Program -> Tape -> Tape
| right => run(p.tail, Right(t))
| left => run(p.tail, Left(t))
| inc => run(p.tail, Inc(t))
| dec => run(p.tail, Dec(t))
| write => run(p.tail, Write(t))
| read => run(p.tail, Read(t))
| loop =>
let tape = Loop(ins.code, t)
run(p.tail, tape)
main : String
let helloWorld = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++."
let p = compile(helloWorld)
//toBrainFuck(p) // prints the original code
case run(p, newTape("")) as t
| tape => t.output
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment