{"id":264,"date":"2007-01-05T14:03:04","date_gmt":"2007-01-05T14:03:04","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/01\/05\/pathological-macros-for-brainfk\/"},"modified":"2007-01-05T14:03:04","modified_gmt":"2007-01-05T14:03:04","slug":"pathological-macros-for-brainfk","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/01\/05\/pathological-macros-for-brainfk\/","title":{"rendered":"Pathological Macros for BrainF**k"},"content":{"rendered":"

Today, I have something really fun and twisted for you. It’s my favorite variation on
\nBrainF**k<\/a>, called “BFM”<\/a>, which is short for “BrainFunct-Macro”. It’s a doubly-Turing-equivalent language – it’s got two complete and distinct Turing equivalent computing systems in it: it’s
\ngot regular BF on the bottom… But before BF gets going to run the program,
\nthe program is pre-processed by a complete lambda-calculus macro expander. <\/p>\n

<\/p>\n

Basically, you start with a BF interpreter, and you observe, quite logically, that there’s a
\nton of repetition in a typical BF program – stuff that could<\/em> be nicely extracted. An
\nobvious example is: suppose you want to add a + b, where they’re stored in neighboring cells, and
\nstore the result where a was. In BF, that’s [-<+>]<<\/code>. <\/p>\n

So, you add a way of defining that as a macro:<\/p>\n

\n&add=[-<+>]<;\n<\/pre>\n
 Next, you notice that gosh, there’s a lot of similar macros, which you could make the
\nsame if you could only parameterize them. For instance, what if you wanted to add “a” and “b”, but
\nthey were actually three cells apart? The program would be: “[-<<<+>>>]<<<<\/code>“. That’s almost the same as the original adder. But wouldn’t it be easier to be able to write
\nrepetitions like that in a smarter way? Like, say, “3(x)” to be the equivalent of “x x x”? So
\nthen, as a macro, that program would be:<\/p>\n
\n&addThreeApart=[-3(<)+3(>)]3(<);\n<\/pre>\n
 And the, you might notice that “add” and “addThreeApart” are pretty much the same thing – the only difference is really a parameter, for how many times to repeat the “<” and “>”s. So you
\nadd parameters.<\/p>\n
\n&addApart(n)=[-n(<)+n(>)]n(<);\n&add=addApart(1);\n&addThreeApart=addApart(3);\n<\/pre>\n
 Now, you notice that the “n”s are really macros themselves, and what you’re doing is allowing
\nyou to write macros that take macros as parameters. So just forget about worrying about it, and just
\nlet macros be parameters to other macros. And bingo – you’ve just created a macro system
\nwhich is pretty much lambda calculus.<\/p>\n
 So, you’ve got a lambda calculus macro system. Well, in Scheme, which is also based on lambda
\ncalculus, they make code a lot easier to read by allowing you to write local<\/em> function
\ndefinitions. So why not local macros?<\/p>\n
\n&addNApart(n) =\n&left=n(<);\n&right=n(>)\n[- left + right ] left;\n<\/pre>\n
 Of course, we’d also like to be able to use more than one parameter, so that we don’t need
\nto curry everything out, right? No problem. Just separate the parameters by “|”. We’ll use this
\nto built something really crazy; let’s treat the BF tape as if it were a stack, and write
\nsome stack-oriented code so that we can build a multiply operator.<\/p>\n
\n&zero=[-];\n&lefttwo = <<;\n&righttwo = >>;\n#copy the nth value on the stack to the top of the stack.\n&rotn(n)=\n&leftn=n(<);\n&rightn=n(>);\n# Push two zeros onto the stack\n2(> zero) 2(<)\n# copy nth value down the stack to the two new stack cells.\nleftn [ - rightn >+>+ lefttwo leftn] rightn\n# copy the second new value back to the nth cell down\nrighttwo\n[- leftwo leftn + righttwo rightn ]\n# move the stack pointer to the first copy of the value.\n>;\n&pushzero = > zero;\n&mult=\npushzero\nlefttwo\n[- righttwo rotn(1) add lefttwo]\nrighttwo\n[- lefttwo + righttwo ]\nlefttwo\n>\n<\/pre>\n
 Gosh, BF starts to look downright legible<\/em>!<\/p>\n","protected":false},"excerpt":{"rendered":"
Today, I have something really fun and twisted for you. It’s my favorite variation on BrainF**k, called “BFM”, which is short for “BrainFunct-Macro”. It’s a doubly-Turing-equivalent language – it’s got two complete and distinct Turing equivalent computing systems in it: it’s got regular BF on the bottom… But before BF gets going to run the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[92],"tags":[],"class_list":["post-264","post","type-post","status-publish","format-standard","hentry","category-pathological-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-4g","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/264","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=264"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/264\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=264"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=264"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=264"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}