Brainstract, a newly created dialect of Brainfuck adds a bit more elements to the syntax. In addition to the normal Brainfuck syntax, there are macros. To define a macro:

{macro_name ++++}

Then use it:

{macro_name} Adds 4 to the current cell


Your challenge is to take a valid Brainstract program as input (command-line-arguments, function arguments, STDIN or file), and output a valid Brainfuck program that is equivalent to the Brainstract program (non-brainfuck characters are allowed in output). You may assume all input will be valid Brainstract.

Brainstract Spec

Whitespace counts as ANY whitespace (tabs, spaces, etc.)

A macro is defined by an opening brace character ({) followed by a macro name which must be made up of any characters except whitespace, brainfuck, and Brainstract characters (anything except whitespace and {}[]<>+-.,)

Then, it is followed by any amount of whitespace and a macro definition, made up of macro calls and non-brace characters and finally the macro is closed off with a closing brace (})

A macro call is of the form {macro_name} where macro name is the same as above.


Format: Input -> Output

{cat ,.} {cat}{cat}{cat}            -> ,.,.,.
{add [>+<-]} ++++>+<{add}           -> ++++>+<[>+<-]
{recursive ,.{recursive}}           -> (undefined behavior)
++++ {decrement -} ++++ {decrement} -> ++++++++-
{a >>>---<<<} {b {a}{a}} {b}        -> >>>---<<<>>>---<<<

Standard Loopholes apply, and shortest code wins

  • \$\begingroup\$ Could you perhaps add some test cases? Example Brainstract programs and their expected Brainfuck program outputs? \$\endgroup\$ Commented Sep 19, 2018 at 13:42
  • \$\begingroup\$ @KevinCruijssen Will do \$\endgroup\$
    – kepe
    Commented Sep 19, 2018 at 13:44
  • \$\begingroup\$ Could you also link to a Brainstract documentation? \$\endgroup\$ Commented Sep 19, 2018 at 14:03
  • 1
    \$\begingroup\$ @FireCubez Under those circumstances, I would suggest mentioning that the language is newly created and adding a more sophisticated language definition -- what counts as a macro_name, which characters can be used as macros, etc. \$\endgroup\$ Commented Sep 19, 2018 at 14:19
  • 2
    \$\begingroup\$ Is {cat ,.} {cat3 {cat}{cat}{cat}} {cat3} a valid input? \$\endgroup\$
    – Arnauld
    Commented Sep 19, 2018 at 14:28

8 Answers 8


Java 8, 251 242 bytes

226 217 bytes of code + 25 bytes for `java.lang.regex.*` import. I can't lambda this since you can't use recursion in a lambda function (self-reference). This just about ignores recursive macros (the space is removed).
  • 9 bytes saved by ceilingcat
import java.util.regex.*;
String f(String s){var p=Pattern.compile("\\{(\\w+)\\s+(\\W+)\\}");for(var m=p.matcher(s);m.find();)s=s.replace("{"+m.group(1)+"}",m.group(2)).replace(m.group(0),"");return p.matcher(s).find()?f(s):s.replace(" ","");}

Try it online

Regex source


JavaScript (Node.js), 113 108 102 bytes

-5 bytes because input will always be valid brainstract
-6 bytes thanks to Cows quack for regex function golfs

x=>{while(m=/({\w+)\s+(\W+)}/.exec(x))x=x.replace(eval(`/${m[1]}}/g`),m[2]).replace(m[0],'');return x}

Try it online!

TIO Link includes a test suite of all 4 "valid" test cases provided in the OP.
The invalid recursive macro test was ignored as, given it's undefined behavior and our program can whatever, there's no need to test it; the result is irrelevant.

Ungolfed Explanation:

fun = code => {
    // While there's a macro definition in the code
    while(match = /{(\w+)\s+(\W+)}/.exec(code)) {
        // Replace calls to the macro with the macro's code
        code = code.replace(eval(`/${m[1]}}/g`),m[2])
        // And remove the definition from the code
    // Remove all spaces from the code and return
    return x;

The entire function relies on the regex: /{(\w+)\s+(\W+)}/
This should match any valid macro definition and include the macro name in Capture Group 1, and the macro's code in Capture Group 2.

Due to how JS's regex.exec() returns, m[0] is the whole matched string (the entire macro definition), m[1] is the string matched by Capture Group 1 (the macro name) and m[2] is the string matched by Capture Group 2 (the macro's code)

We can then replace all instances of {m[1]} with m[2], then remove the first instance of m[0] in order to remove the macro definition. This is required in part due to the way brainfuck would interpret the macro definition, and in part due to the way the while loop in this function works (it finds the first definition in the code, if we don't remove the definition after we've processed it, it'll keep finding the first definition over and over)

However, our first capture group m[1] also includes the opening brace { of the macro definition. This is so that when replacing {m[1]} with m[2], we actually only need to replace m[1]}, which saves a byte.

Unfortunately including a variable m[1] in a RegExp in JS is a bit costly, as we need to eval the regex, which adds 6 bytes.

There's probably quite a bit of golfing room in this answer, as there tends to me in my NodeJS answers.
If anybody has any suggestions for golfing, let me know in the comments.

However if your answer involves using an entirely different approach to mine, please post your own answer :)

  • \$\begingroup\$ The new appears to be redundant, but eval(`/${m[1]}}/g`) is still shorter. Also exec is shorter than match \$\endgroup\$
    – user41805
    Commented Dec 20, 2018 at 16:20
  • \$\begingroup\$ @Cowsquack oh nice, thanks! \$\endgroup\$
    – Mayube
    Commented Dec 20, 2018 at 16:27
  • \$\begingroup\$ 85 \$\endgroup\$
    – ASCII-only
    Commented Dec 20, 2018 at 23:48
  • \$\begingroup\$ 80 \$\endgroup\$
    – ASCII-only
    Commented Dec 22, 2018 at 10:18
  • \$\begingroup\$ but according to the comment, 94 \$\endgroup\$
    – ASCII-only
    Commented Dec 22, 2018 at 10:20

Pip, 33 bytes


Try it online!

Very similar approach to Xcali's Perl solution, though mostly independently derived.*

                                   a is 1st cmdline argument (implicit)
Wa~`            `                  While this regex matches in a:
    ({\S+)                         First group: { followed by non-whitespace characters
          (.+?)                    Second group: more characters, as few as possible...
               }                   ... followed by }
                                   This matches a macro definition, including all the
                                   whitespace as part of the replacement code
                                   (It doesn't work for macro definitions with macro calls
                                   inside them, but the leftmost definition at any time
                                   will not have a macro call inside it)
                                   So while possible, match the first occurrence, and:
                 a:                  Set a to:
                   $`                 The portion of the string left of the match
                     .$'              concatenated to the portion right of the match
                        R             In that string, replace
                         $1.'}        match group 1 plus a trailing } (i.e. a macro call)
                              $2      with match group 2 (the macro's code)
                                a  When the loop exits, output the final value of a

* That is, I saw the Perl solution's byte count, went "How?!...", and finally realized I could assume a few things that made the code a lot shorter.


Ruby, 74+1 = 75 bytes

Add one byte for the p flag.

(k=$2;gsub(/#$1( .+?)?\}/){$1?p: k})while~/(\{\w+) (([^{}]|\{\g<2>\})*)\}/

Try it online!


PHP, 197 196 186 bytes

<?php $p=$argv[$c=1];$m=[];while($c)$p=preg_replace_callback("/\{(\w+)(\s((?0)|[^{])+)?\}/",function($a)use(&$m){return count($a)<3?$m[$a[1]]:[$m[$a[1]]=$a[2],""][1];},$p,-1,$c);echo $p;

Try it online!

185 if only one kind of whitespace is accepted (by changing the regex to /\{(\w+)( ((?0)|[^{])+)?\}/) but I'm not sure whether this is valid.

I was tempted to use JavaScript but the RegExp class in JS doesn't support RE recursion...


Python 2, 133 bytes

import re
while'{'in s:x=re.findall('{.*? (?:[^{]|{.+})*?}',s)[0];d,c=x.split(' ',1);s=s.replace(x,'').replace(d,c)
print s

Try it online!

  • \$\begingroup\$ 118, maybe. idk \$\endgroup\$
    – ASCII-only
    Commented Dec 22, 2018 at 10:35
  • \$\begingroup\$ @ASCII-only Maybe you want this 127-byte version, but it doesn't work if you stick a letter in the code part of the macro. \$\endgroup\$ Commented Dec 22, 2018 at 10:54
  • \$\begingroup\$ "non-brainfuck characters are allowed in output" \$\endgroup\$
    – ASCII-only
    Commented Dec 22, 2018 at 11:22
  • \$\begingroup\$ @ASCII-only No, I mean that, if you do {someMacro >>>--t-<<<} instead of {someMacro >>>---<<<}, your code doesn't work. \$\endgroup\$ Commented Dec 22, 2018 at 11:25

Perl 5 -p, 47 bytes

-11 bytes with ideas from @ASCII-only

$s=$2,s/\Q$1}/$s/g while s/(\{\S+)\s+(\S+?)\}//

Try it online!

  • \$\begingroup\$ 40? \$\endgroup\$
    – ASCII-only
    Commented Dec 22, 2018 at 10:25
  • \$\begingroup\$ Replacing \s+ with ` ` works for all the current testcases as well. hmm \$\endgroup\$
    – ASCII-only
    Commented Dec 22, 2018 at 10:28
  • \$\begingroup\$ @ASCII-only From a comment: "[The space between the macro name and definition must be] any whitespace character" \$\endgroup\$
    – kepe
    Commented Dec 22, 2018 at 11:12
  • \$\begingroup\$ @ASCII-only I don't think yours works in all cases. Take a look at the last test case in my new link. \$\endgroup\$
    – Xcali
    Commented Dec 22, 2018 at 18:35
  • \$\begingroup\$ This should work for 41 bytes. \$\endgroup\$
    – DLosc
    Commented Mar 7, 2019 at 5:27

Go, 249 bytes

func f(C string)string{M,R:=MustCompile,(*Regexp).ReplaceAllString
if len(K)<1{return R(M(`\s`),C,"")}
return f(U)}

Attempt This Online!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.