Since I got the Beta 1 of Visual Studio 2010 I have wanted to take the new extensions to System.Linq.Expressions for a test drive. I can’t remember why I thought doing a Brainfuck compiler to test out the new things was a good idea, but either way that’s what I implemented.

This tiny compiler uses some of the new extensions to the System.Linq.Expressions that will be available in .NET 4.0, so I think it will serve as a good starting point in showing what can be done.

These are the new extensions I use in the example:

• Expression.Variable
• Expression.Increment
• Expression.Decrement
• Expression.Block
• Expression.Assign
• Expression.Loop
• Expression.Break
• Expression.ArrayAccess
• Expression.IfThen
• Expression.Lable
• Expression.PreDecrementAssign
• Expression.PreIncrementAssign

Lets look at the code:

namespace Demo
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Linq.Expressions;

    class BrainfuckCompiler
    {
        private Expression<Action> expression;
        private ParameterExpression stackPointer;
        private ParameterExpression stack;

        public BrainfuckCompiler(string commands)
        {
            BuildExpression(commands);
        }

        public Expression<Action> ExpressionTree { get { return this.expression; } }

        private void BuildExpression(string commands)
        {
            stackPointer = Expression.Variable(typeof(int), "stackPointer");
            stack = Expression.Variable(typeof(byte[]), "stack");

            var expressionStack = new Stack<List<Expression>>();
            expressionStack.Push(new List<Expression>());

            foreach (var command in commands)
            {
                var block = expressionStack.Peek();
                switch (command)
                {
                    case '+': block.Add(Increment()); break;
                    case '-': block.Add(Decrement()); break;
                    case '>': block.Add(IncrementDataPointer()); break;
                    case '<': block.Add(DecrementDataPointer()); break;
                    case ',': block.Add(ReadByte()); break;
                    case '.': block.Add(WriteByte()); break;
                    case '[': expressionStack.Push(new List<Expression>()); break;
                    case ']':
                        var loopBlock = Loop(expressionStack.Pop());
                        expressionStack.Peek().Add(loopBlock);
                        break;
                    default: break;
                }
            }

            this.expression = Expression.Lambda<Action>(Expression.Block(
                new[] { stack, stackPointer },
                Expression.Assign(stack,
                  Expression.New(typeof(byte[]).GetConstructor(new[] { typeof(int) }),
                                 Expression.Constant(131072)
                  )
                ),
                Expression.Assign(stackPointer, Expression.Constant(0)),
                Expression.Block(expressionStack.Pop())));
        }

        private Expression IncrementDataPointer()
        {
            // ++stackPointer;
            return Expression.PreIncrementAssign(stackPointer);
        }

        private Expression DecrementDataPointer()
        {
            // --stackPointer;
            return Expression.PreDecrementAssign(stackPointer);
        }

        private Expression Increment()
        {
            // stack[stackPointer] = stack[stackPointer] + 1;
            return Expression.Assign(
                                Expression.ArrayAccess(stack, stackPointer),
                                Expression.Convert(
                                    Expression.Increment(
                                      Expression.Convert(
                                        Expression.ArrayAccess(stack, stackPointer),
                                        typeof(int)
                                      )
                                    ),
                                    typeof(byte)
                                )
                            );
        }

        private Expression Decrement()
        {
            // stack[stackPointer] = stack[stackPointer] - 1;
            return Expression.Assign(
                                Expression.ArrayAccess(stack, stackPointer),
                                Expression.Convert(
                                    Expression.Decrement(
                                      Expression.Convert(
                                        Expression.ArrayAccess(stack, stackPointer),
                                        typeof(int)
                                      )
                                    ),
                                    typeof(byte)
                                )
                            );
        }

        private Expression Loop(List<Expression> loopBlock)
        {
            // while (true) {
            //   if (stack[stackPointer] == 0x00) break;
            //   ... loopBlock ...
            // }
            var block = new List<Expression>(loopBlock.Count + 1);
            var brk = Expression.Label();
            block.Add(Expression.IfThen(
              Expression.Equal(
                Expression.ArrayAccess(stack, stackPointer),
                Expression.Constant((byte)0x0)), Expression.Break(brk))
            );
            block.AddRange(loopBlock);
            return Expression.Loop(Expression.Block(block), brk);
        }

        private Expression WriteByte()
        {
            // Console.Write((char)stack[stackPointer]);
            return Expression.Call(
              typeof(Console).GetMethod("Write", new[] { typeof(char) }),
              Expression.Convert(Expression.ArrayAccess(stack, stackPointer), typeof(char))
            );
        }

        private Expression ReadByte()
        {
            // stack[stackPointer] = (byte)Console.Read();
            return Expression.Assign(Expression.ArrayAccess(stack, stackPointer),
              Expression.Convert(Expression.Call(typeof(Console).GetMethod("Read")),
              typeof(byte))
            );
        }

        public Action Compile()
        {
            if (this.expression.CanReduce)
                this.expression = (Expression<Action>)this.expression.Reduce();
            return this.expression.Compile();
        }
    }
}

The BrainfuckCompiler loops over all commands in the provided string, and adds a corresponding expression for each command to the block list. If the bf command [ (loop) is encountered a new loop block is pushed as the active block and all command parsed until the end loop command ] is encountered is placed inside the loop block. With this simple construct we are able to build nested statement blocks, with call flows, assignments and variables something that was not possible in .NET 3.

++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.
+++.------.--------.>+.>.

namespace Demo
{
    using System;
    using System.IO;

    class Program
    {
        static void Main(string[] args)
        {
            var helloWorld = new BrainfuckCompiler(File.ReadAllText("hello_world.bf"));
            helloWorld.Compile()();

            Console.ReadKey();
        }
    }
}

The above example will print “Hello World!” to the stdout. Even with the limited instruction set it’s still possible to do
some fairly advanced things. Like the example bellow is a universal Turning machine (for more information se utm.b)
for a complete test-case for the Turning machine write this in the console “b1b1bbb1c1c11111d” and hit enter,
the expected output is “1c11111″.

+++>++>>>+[>>,[>+++++<[[->]<<]<[>]>]>-[<<+++++>>-[<<---->>-[->]<]]
<[<-<[<]+<+[>]<<+>->>>]<]<[<]>[-[>++++++<-]>[<+>-]+<<<+++>+>
  [-
    [<<+>->-
      [<<[-]>>-
        [<<++>+>-
          [<<-->->>+++<-
            [<<+>+>>--<-
              [<<->->-
                [<<++++>+>>+<-
                  [>-<-
                    [<<->->-
                      [<<->>-
                        [<<+++>>>-<-
                          [<<---->>>++<-
                            [<<++>>>+<-
                              [>[-]<-
                                [<<->>>+++<-
                                  [<<->>>--<-
                                    [<<++++>+>>+<-
                                      [<<[-]>->>++<-
                                        [<<+++++>+>>--<-
                                          [<->>++<
                                            [<<->>-
]]]]]]]]]]]]]]]]]]]]]]<[->>[<<+>>-]<<<[>>>+<<<-]<[>>>+<<<-]]>>]
>[-[---[-<]]>]>[+++[<+++++>--]>]+<++[[>+++++<-]<]>>[-.>]

namespace Demo
{
    using System;
    using System.IO;

    class Program
    {
        static void Main(string[] args)
        {
            var bf2 = new BrainfuckCompiler(File.ReadAllText("utm.bf"));
            bf2.Compile()();

            Console.ReadKey();
        }
    }
}