{"id":18,"date":"2006-09-19T22:11:55","date_gmt":"2006-09-19T21:41:20","guid":{"rendered":""},"modified":"2017-03-07T16:05:43","modified_gmt":"2017-03-07T16:05:43","slug":"brainfuck","status":"publish","type":"post","link":"https:\/\/blogs.gentoo.org\/blubb\/2006\/09\/19\/brainfuck\/","title":{"rendered":"Brainfuck…"},"content":{"rendered":"

…is a truly fascinating language. So simple, so sexy. It’s Turing-complete, so there’s literally nothing you can’t do with it. Well, at least as far as theory goes. Sure, there’s nothing you can’t do with it, but there’s nothing you can do easily<\/b> with it either, unfortunately. One thing that has always bothered me whenever I attempted to write an application in BF is that all the addresses are relative. Relative in the sense of that you can’t say “go to register 3” but only “go 2 registers up”. Another thing that really bothered me is that all the addresses are absolute. Absolute in the sense of that they are all in the same array, that you can’t have your seperate set of registers for a sub-program.<\/p>\n

So I tinkered a bit around and ended up with something I would call a “functional brainfuck compiler”. It lets you define functions and takes care of the variable<->register mappings for the whole program. An example:<\/p>\n

\r\nmain(0) {\r\n\t$0++\r\n\t$1+++\r\n\tpower(0;1;2)\r\n\tasciify(2)\r\n\t$2.\r\n}\r\n\r\npower(3) {\r\n\t\/\/ a ^ b = c\r\n\r\n\tcopy(0;2)\r\n\tcopy(1;3)\r\n\t$3-[\r\n\t\tmultiply(0;2;4)\r\n\t\tcopy(4;2)\r\n\t\t$3-\r\n\t]\r\n}\r\n\r\nmultiply(3) {\r\n\t\/\/ a * b = c\r\n\t\r\n\tclear(2)\r\n\tcopy(1;3)\r\n\t$3[\r\n\t\tadd(0;2)\r\n\t\t$3-\r\n\t]\r\n}\r\n\r\ncopy(2) {\r\n\t\/\/ $0 = source\r\n\t\/\/ $1 = dest\r\n\r\n\tclear(1)\r\n\tadd(0;1)\r\n}\r\n\r\nmove(2) {\r\n\t\/\/ $0 = source\r\n\t\/\/ $1 = dest\r\n\t\r\n\t$0[-$1+$0]\r\n}\r\n\r\nadd(2) {\r\n\tclear(2)\r\n\t$0[-$1+$2+$0]\r\n\tmove(2;0)\r\n}\r\n\r\nclear(1) {\r\n\t$0[-]\r\n}\r\n\r\nasciify(1) {\r\n\t\/\/ only works for 0 >= numbers >= 9\r\n\tclear(1)\r\n\tclear(2)\r\n\tclear(3)\r\n\t$1+++++++\r\n\tcopy(1;2)\r\n\tmultiply(1;2;3)\r\n\t$3-\r\n\tadd(3;0)\r\n}\r\n<\/pre>\n
You can see the language is pretty close to C in some ways. The syntax is roughly:<\/p>\n
function-specifier(argc) { code block }<\/code><\/p>\n
A main() function is required and must have zero arguments given (should be evident ;-)). Function definitions are the only thing that is allowed in global scope, C\/C++-like comments are supported. Function calls are of the form<\/p>\n
function-specifier(arg1;arg2;argN)<\/code> where arg1...argN<\/code> are the numbers of the variables given as arguments. The character $<\/code> followed by a number is interpreted as a “go to the register assigned to that variable” and replaced with the necessary amount of <<\/code> or ><\/code> at compilation time.<\/p>\n
So, running the code above through the compiler gives you this:<\/p>\n
$ .\/fbf bf.b\r\n++>+++>[-]>>>[-]<<<<<[->>+>>>+<<<<<]>>>>>[-<<<<<+>>>>>]<<[-]>>[-]<<<<[->>+>>+\r\n<<<<]>>>>[-<<<<+>>>>]<<-[>[-]>[-]>[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<[>[-]<\r\n<<<<<[->>>>+>>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<-]<<<[-]>>>[-]<[-<<+>>>+<]>[-<+>\r\n]<<-][-]>[-]>[-]<<+++++++>[-]>>[-]<<<[->+>>+<<<]>>>[-<<<+>>>]<[-]>[-]>[-]<<<[\r\n->>+>+<<<]>>>[-<<<+>>>]<[>[-]<<<<[->>+>>+<<<<]>>>>[-<<<<+>>>>]<-]<->[-]<[-<<<\r\n+>>>>+<]>[-<+>]<<<<.<\/pre>\n
This looks already whole dimensions more geeky. \ud83d\ude09 As you can see from the main()<\/code> above, it calculates 2^3<\/code> and uses asciify()<\/code> to then print the result.<\/p>\n
To verify everything, i used dev-lang\/bff<\/a>, the fastest BF interpreter I could find:<\/p>\n
$ bff bf.bc\r\n8<\/pre>\n
Now, if you have a closer look at the output, you see that there is quite a lot of crap that could be just left out. For example, the first two [-]<\/code>s are completely redundant. This comes from the fact that most functions clear()<\/code> their local variables prior to usage to ensure that the result is correct.<\/p>\n
So, the code could be optimized quite a bit, and I decided to write another app that cleans up the code the compiler throws out. It’s still a bit buggy and doesn’t work on every piece of code, but it’s progressing. The really hard problem is to debug that beast, though. Currently it only drops code that is not needed, it does not rearrange nor re-write code, so the easiest method to verify that it works correctly is to replace the dropped code with blanks. The outcome happens to look rather funny:<\/p>\n
\"optimizer<\/a><\/p>\n
Cool, eh? \ud83d\ude09<\/p>\n","protected":false},"excerpt":{"rendered":"
…is a truly fascinating language. So simple, so sexy. It’s Turing-complete, so there’s literally nothing you can’t do with it. Well, at least as far as theory goes. Sure, there’s nothing you can’t do with it, but there’s nothing you can do easily with it either, unfortunately. One thing that has always bothered me whenever … Continue reading Brainfuck…<\/span><\/a><\/p>\n","protected":false},"author":12,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[3],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/blogs.gentoo.org\/blubb\/wp-json\/wp\/v2\/posts\/18"}],"collection":[{"href":"https:\/\/blogs.gentoo.org\/blubb\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.gentoo.org\/blubb\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.gentoo.org\/blubb\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.gentoo.org\/blubb\/wp-json\/wp\/v2\/comments?post=18"}],"version-history":[{"count":1,"href":"https:\/\/blogs.gentoo.org\/blubb\/wp-json\/wp\/v2\/posts\/18\/revisions"}],"predecessor-version":[{"id":28,"href":"https:\/\/blogs.gentoo.org\/blubb\/wp-json\/wp\/v2\/posts\/18\/revisions\/28"}],"wp:attachment":[{"href":"https:\/\/blogs.gentoo.org\/blubb\/wp-json\/wp\/v2\/media?parent=18"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.gentoo.org\/blubb\/wp-json\/wp\/v2\/categories?post=18"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.gentoo.org\/blubb\/wp-json\/wp\/v2\/tags?post=18"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}