14
\$\begingroup\$

So I've completely changed how BrainfuckSharp does things, and added some features. This is obviously a follow up to: Interpreting Brainfuck code to C#, then compiling to a .exe

It now features an OptimizationLevel (currently hardcoded, will fix for the future) that allows you to indicate how far you want the interpreted code optimized. The OptimizationLevel.Level1 level will smash subsequent calls to the increment/decrement and move left/right tokens together into one call. (Instead of >> turning into index++; index++; it now turns into index += 2;.)

Just as well, it's now much more like a "true" compiler in that it treats everything like a token.

Let's start with the TokenSymbol enum:

public enum TokenSymbol
{
    None,
    MoveLeft,
    MoveRight,
    LoopBegin,
    LoopEnd,
    Increment,
    Decrement,
    OutputValue,
    InputCharacter
}

This represents every possible token in Brainfuck, and a default "None" token.

Next, OptimizationLevel:

/// <summary>
/// Determines how the <see cref="Interpreter"/> will optimize Brainfuck code.
/// </summary>
public enum OptimizationLevel
{
    /// <summary>
    /// Do not apply any optimizations.
    /// </summary>
    None,
    /// <summary>
    /// Apply first level optimizations (combining sequences of increment/decrement characters into one increment/decrement per sequence).
    /// </summary>
    Level1,
}

This is self-explanatory. It represents the (currently two) possible optimization levels of BrainfuckSharp. Specifying None will not optimize the code, specifying Level1 will apply basic optimizations.

On to the Interpreter:

public class Interpreter
{
    public OptimizationLevel OptimizationLevel { get; set; } = OptimizationLevel.None;

    public List<string> Lines { get; } = new List<string>();

    private List<TokenSymbol> _symbols = new List<TokenSymbol>();
    private List<char> _validTokens = new List<char> { '<', '>', ',', '.', '+', '-', '[', ']' };
    private Dictionary<char, TokenSymbol> _tokenMap = new Dictionary<char, TokenSymbol>
    {
        { '<', TokenSymbol.MoveLeft },
        { '>', TokenSymbol.MoveRight },
        { ',', TokenSymbol.InputCharacter },
        { '.', TokenSymbol.OutputValue },
        { '[', TokenSymbol.LoopBegin },
        { ']', TokenSymbol.LoopEnd },
        { '+', TokenSymbol.Increment },
        { '-', TokenSymbol.Decrement }
    };

    private void Tokenize(string brainfuck)
    {
        foreach (char c in brainfuck)
        {
            if (_validTokens.Contains(c))
            {
                _symbols.Add(_tokenMap[c]);
            }
        }
    }

    public void WriteToFile(string filename)
    {
        using (var sw = new StreamWriter(filename))
        {
            foreach (string line in Lines)
            {
                sw.WriteLine(line);
            }
        }
    }

    public void Interpret(string brainfuck)
    {
        Tokenize(brainfuck);

        var lastSymbol = TokenSymbol.None;
        var symbolRepeated = 0;
        var indents = 3;

        foreach (var symbol in _symbols)
        {
            switch (symbol)
            {
                case TokenSymbol.LoopBegin:
                    if ((OptimizationLevel & OptimizationLevel.Level1) >= OptimizationLevel.Level1)
                    {
                        if (lastSymbol != symbol && lastSymbol != TokenSymbol.None && (lastSymbol == TokenSymbol.Decrement || lastSymbol == TokenSymbol.Increment || lastSymbol == TokenSymbol.MoveLeft || lastSymbol == TokenSymbol.MoveRight))
                        {
                            Lines.AddRange(SymbolToLines(lastSymbol, symbolRepeated, indents));
                            symbolRepeated = 0;
                        }
                        else
                        {
                            lastSymbol = symbol;
                            symbolRepeated++;
                        }
                    }

                    symbolRepeated = 0;
                    Lines.AddRange(SymbolToLines(symbol, symbolRepeated, indents));
                    indents += 1;
                    break;
                case TokenSymbol.LoopEnd:
                    if ((OptimizationLevel & OptimizationLevel.Level1) >= OptimizationLevel.Level1)
                    {
                        if (lastSymbol != symbol && lastSymbol != TokenSymbol.None && (lastSymbol == TokenSymbol.Decrement || lastSymbol == TokenSymbol.Increment || lastSymbol == TokenSymbol.MoveLeft || lastSymbol == TokenSymbol.MoveRight))
                        {
                            Lines.AddRange(SymbolToLines(lastSymbol, symbolRepeated, indents));
                            symbolRepeated = 0;
                        }
                        else
                        {
                            lastSymbol = symbol;
                            symbolRepeated++;
                        }
                    }

                    indents -= 1;
                    symbolRepeated = 0;
                    Lines.AddRange(SymbolToLines(symbol, symbolRepeated, indents));
                    break;
                case TokenSymbol.InputCharacter:
                    if ((OptimizationLevel & OptimizationLevel.Level1) >= OptimizationLevel.Level1)
                    {
                        if (lastSymbol != symbol && lastSymbol != TokenSymbol.None && (lastSymbol == TokenSymbol.Decrement || lastSymbol == TokenSymbol.Increment || lastSymbol == TokenSymbol.MoveLeft || lastSymbol == TokenSymbol.MoveRight))
                        {
                            Lines.AddRange(SymbolToLines(lastSymbol, symbolRepeated, indents));
                            symbolRepeated = 0;
                        }
                        else
                        {
                            lastSymbol = symbol;
                            symbolRepeated++;
                        }
                    }

                    symbolRepeated = 0;
                    Lines.AddRange(SymbolToLines(symbol, symbolRepeated, indents));
                    break;
                case TokenSymbol.OutputValue:
                    if ((OptimizationLevel & OptimizationLevel.Level1) >= OptimizationLevel.Level1)
                    {
                        if (lastSymbol != symbol && lastSymbol != TokenSymbol.None && (lastSymbol == TokenSymbol.Decrement || lastSymbol == TokenSymbol.Increment || lastSymbol == TokenSymbol.MoveLeft || lastSymbol == TokenSymbol.MoveRight))
                        {
                            Lines.AddRange(SymbolToLines(lastSymbol, symbolRepeated, indents));
                            symbolRepeated = 0;
                        }
                        else
                        {
                            lastSymbol = symbol;
                            symbolRepeated++;
                        }
                    }

                    symbolRepeated = 0;
                    Lines.AddRange(SymbolToLines(symbol, symbolRepeated, indents));
                    break;
                case TokenSymbol.Decrement:
                case TokenSymbol.Increment:
                case TokenSymbol.MoveLeft:
                case TokenSymbol.MoveRight:
                    if ((OptimizationLevel & OptimizationLevel.Level1) >= OptimizationLevel.Level1)
                    {
                        if (lastSymbol != symbol && lastSymbol != TokenSymbol.None && (lastSymbol == TokenSymbol.Decrement || lastSymbol == TokenSymbol.Increment || lastSymbol == TokenSymbol.MoveLeft || lastSymbol == TokenSymbol.MoveRight))
                        {
                            Lines.AddRange(SymbolToLines(lastSymbol, symbolRepeated, indents));
                            symbolRepeated = 1;
                        }
                        else
                        {
                            lastSymbol = symbol;
                            symbolRepeated++;
                        }
                    }
                    else
                    {
                        symbolRepeated = 1;
                        Lines.AddRange(SymbolToLines(symbol, symbolRepeated, indents));
                    }
                    break;
            }

            lastSymbol = symbol;
        }
    }

    private string[] SymbolToLines(TokenSymbol symbol, int repeated, int indentLevels)
    {
        switch (symbol)
        {
            case TokenSymbol.Decrement:
                if (repeated == 1)
                {
                    return new[] { $"{GetIndents(indentLevels)}buffer[index]--;" };
                }
                else
                {
                    return new[] { $"{GetIndents(indentLevels)}buffer[index] -= {repeated};" };
                }
            case TokenSymbol.Increment:
                if (repeated == 1)
                {
                    return new[] { $"{GetIndents(indentLevels)}buffer[index]++;" };
                }
                else
                {
                    return new[] { $"{GetIndents(indentLevels)}buffer[index] += {repeated};" };
                }
            case TokenSymbol.InputCharacter:
                return new[] { $"{GetIndents(indentLevels)}buffer[index] = ReadChar();" };
            case TokenSymbol.LoopBegin:
                return new[] { "", $"{GetIndents(indentLevels)}while (buffer[index] != 0)", $"{GetIndents(indentLevels)}{{" };
            case TokenSymbol.LoopEnd:
                return new[] { $"{GetIndents(indentLevels)}}}", "" };
            case TokenSymbol.MoveLeft:
                if (repeated == 1)
                {
                    return new[] { $"{GetIndents(indentLevels)}index--;" };
                }
                else
                {
                    return new[] { $"{GetIndents(indentLevels)}index -= {repeated};" };
                }
            case TokenSymbol.MoveRight:
                if (repeated == 1)
                {
                    return new[] { $"{GetIndents(indentLevels)}index++;" };
                }
                else
                {
                    return new[] { $"{GetIndents(indentLevels)}index += {repeated};" };
                }
            case TokenSymbol.OutputValue:
                return new[] { $"{GetIndents(indentLevels)}Console.Write((char)buffer[index]);" };
        }

        return null;
    }

    public static string GetIndents(int levels) => new string(' ', levels * 4);
}

This interprets the Brainfuck to it's appropriate lines.

The Transpiler:

public class Transpiler
{
    public ILogger Logger { get; }

    public string SourceFile { get; set; }
    public string ProgrammeName { get; set; }
    public string DestinationFile { get; set; }
    public string ExecutableFile { get; set; }
    public int BufferSize { get; set; }
    public string DotNetVersion { get; set; }
    public OptimizationLevel OptimizationLevel { get; set; }

    private static Dictionary<string, string> _dotNetFolders = new Dictionary<string, string> { { "2.0", "v2.0.50727" }, { "3.5", "v3.5" }, { "4.0", "v4.0.30319" } };

    public Transpiler(ILogger logger)
    {
        Logger = logger;
    }

    public void AcquireInput(IPrompt prompt)
    {
        SourceFile = AddExtension(prompt.Prompt<string>("Enter the source filename (.bf)", PromptOptions.Required, validationMethod: x => !string.IsNullOrWhiteSpace(x)), ".bf");
        ProgrammeName = SourceFile.Substring(0, SourceFile.LastIndexOf('.'));
        DestinationFile = AddExtension(prompt.Prompt("Enter the destination filename (.cs)", PromptOptions.Optional, ProgrammeName + ".cs", validationMethod: x => !string.IsNullOrWhiteSpace(x)), ".cs");
        ExecutableFile = AddExtension(prompt.Prompt("Enter the destination executable (.exe)", PromptOptions.Optional, ProgrammeName + ".exe", validationMethod: x => !string.IsNullOrWhiteSpace(x)), ".exe");
        BufferSize = prompt.Prompt("Enter buffer size", PromptOptions.Optional, 2048);
        DotNetVersion = prompt.Prompt("Enter .NET version to compile with", PromptOptions.Optional, "4.0", "Version can be any of: 2.0, 3.5, 4.0", x => _dotNetFolders.ContainsKey(x));
    }

    private static string AddExtension(string data, string extension)
    {
        if (data.IndexOf('.') == -1)
        {
            data += extension;
        }

        return data;
    }

    public string LoadBrainfuckCode(string filename) => File.ReadAllText(filename);

    public void Transpile()
    {
        if (string.IsNullOrWhiteSpace(SourceFile)
            || string.IsNullOrWhiteSpace(ProgrammeName)
            || string.IsNullOrWhiteSpace(DestinationFile)
            || string.IsNullOrWhiteSpace(ExecutableFile)
            || string.IsNullOrWhiteSpace(DotNetVersion)
            || BufferSize <= 0)
        {
            throw new ArgumentException($"The values for {nameof(SourceFile)}, {nameof(ProgrammeName)}, {nameof(DestinationFile)}, {nameof(ExecutableFile)}, {nameof(DotNetVersion)} cannot be null or whitespace, and {nameof(BufferSize)} cannot be zero or negative. Did you forget to call {nameof(AcquireInput)}?");
        }

        // Now that that's over.
        var interpreter = new Interpreter();
        interpreter.OptimizationLevel = OptimizationLevel;

        var brainfuck = LoadBrainfuckCode(SourceFile);

        interpreter.Interpret(brainfuck);

        var template = AcquireTemplate("CompiledTemplate.cs");

        var sb = new StringBuilder();

        foreach (var line in interpreter.Lines)
        {
            sb.AppendLine(line);
        }

        var result = template;
        result = result.Replace("BufferSize", BufferSize.ToString());
        result = result.Replace("BrainfuckCode;", sb.ToString().TrimStart());

        WriteToCsFile(DestinationFile, result);
        CompileCsFile(_dotNetFolders[DotNetVersion], DestinationFile, ExecutableFile);
    }

    public void WriteToCsFile(string filename, string data)
    {
        using (StreamWriter sw = new StreamWriter(filename))
        {
            sw.WriteLine(data);
        }
    }

    public string AcquireTemplate(string filename) => File.ReadAllText(filename);

    public void CompileCsFile(string dotNetPath, string sourceFile, string executableFile)
    {
        Logger.LogImportant($"C:\\Windows\\Microsoft.NET\\Framework\\{dotNetPath}\\csc.exe /t:exe /out:\"{Directory.GetCurrentDirectory()}\\{executableFile}\" \"{Directory.GetCurrentDirectory()}\\{sourceFile}\"");
        ProcessStartInfo info = new ProcessStartInfo($@"C:\Windows\Microsoft.NET\Framework\{dotNetPath}\csc.exe", $"/t:exe /out:\"{Directory.GetCurrentDirectory()}\\{executableFile}\" \"{Directory.GetCurrentDirectory()}\\{sourceFile}\"");
        var process = Process.Start(info);
        process.WaitForExit();
    }
}

This does the heavy-lifting of the compiler to call the appropriate methods to convert the Brainfuck to C#.

Lastly, the new Program:

class Program
{
    static void Main(string[] args)
    {
        var logger = new ConsoleLogger(LoggingType.All);
        var transpiler = new Transpiler.Transpiler(logger);
        transpiler.OptimizationLevel = Transpiler.OptimizationLevel.Level1;
        var prompter = new ConsolePrompt(logger);
        transpiler.AcquireInput(prompter);
        transpiler.Transpile();

        Process.Start(transpiler.ExecutableFile);

        Console.WriteLine("Press enter key to exit...");
        Console.ReadLine();
    }
}

Pretty self-explanatory.

Major notes: The project is no longer one huge Program.cs, but features a somewhat object-oriented approach to the Brainfuck interpretation and compilation.

Example HelloWorld.bf:

[ This program prints "Hello World!" and a newline to the screen, its
  length is 106 active command characters. [It is not the shortest.]

 This loop is a "comment loop", a simple way of adding a comment
  to a BF program such that you don't have to worry about any command
  characters. Any ".", ",", "+", "-", "<" and ">" characters are simply
  ignored, the "[" and "]" characters just have to be balanced. This
  loop and the commands it contains are ignored because the current cell
  defaults to a value of 0; the 0 value causes this loop to be skipped.
]
+++++ +++               Set Cell #0 to 8
[
    >++++               Add 4 to Cell #1; this will always set Cell #1 to 4
    [                   as the cell will be cleared by the loop
        >++             Add 2 to Cell #2
        >+++            Add 3 to Cell #3
        >+++            Add 3 to Cell #4
        >+              Add 1 to Cell #5
        <<<<-           Decrement the loop counter in Cell #1
    ]                   Loop till Cell #1 is zero; number of iterations is 4
    >+                  Add 1 to Cell #2
    >+                  Add 1 to Cell #3
    >-                  Subtract 1 from Cell #4
    >>+                 Add 1 to Cell #6
    [<]                 Move back to the first zero cell you find; this will
                        be Cell #1 which was cleared by the previous loop
    <-                  Decrement the loop Counter in Cell #0
]                       Loop till Cell #0 is zero; number of iterations is 8

The result of this is:
Cell No :   0   1   2   3   4   5   6
Contents:   0   0  72 104  88  32   8
Pointer :   ^

>>.                     Cell #2 has value 72 which is 'H'
>---.                   Subtract 3 from Cell #3 to get 101 which is 'e'
+++++++..+++.           Likewise for 'llo' from Cell #3
>>.                     Cell #5 is 32 for the space
<-.                     Subtract 1 from Cell #4 for 87 to give a 'W'
<.                      Cell #3 was set to 'o' from the end of 'Hello'
+++.------.--------.    Cell #3 for 'rl' and 'd'
>>+.                    Add 1 to Cell #5 gives us an exclamation point
>++.                    And finally a newline from Cell #6

Converts to:

using System;

namespace Brainfuck_Interpreter
{
    class CompiledTemplate
    {
        static byte ReadChar()
        {
            return (byte)Console.ReadKey().KeyChar;
        }

        static void Main(string[] args)
        {
            byte[] buffer = new byte[2048];
            int index = 0;

            while (buffer[index] != 0)
            {
                buffer[index] = ReadChar();
                Console.Write((char)buffer[index]);

                while (buffer[index] != 0)
                {
                    Console.Write((char)buffer[index]);
                }

                buffer[index] = ReadChar();
                Console.Write((char)buffer[index]);
                Console.Write((char)buffer[index]);
                buffer[index] = ReadChar();
                buffer[index] = ReadChar();
                buffer[index] = ReadChar();
                buffer[index]++;
                buffer[index] = ReadChar();
                buffer[index]--;
                buffer[index] = ReadChar();
                index--;
                index++;
                buffer[index] = ReadChar();

                while (buffer[index] != 0)
                {
                }

                Console.Write((char)buffer[index]);
                Console.Write((char)buffer[index]);
            }

            buffer[index] += 8;

            while (buffer[index] != 0)
            {
                index++;
                buffer[index] += 4;

                while (buffer[index] != 0)
                {
                    index++;
                    buffer[index] += 2;
                    index++;
                    buffer[index] += 3;
                    index++;
                    buffer[index] += 3;
                    index++;
                    buffer[index]++;
                    index -= 4;
                    buffer[index]--;
                }

                index++;
                buffer[index]++;
                index++;
                buffer[index]++;
                index++;
                buffer[index]--;
                index += 2;
                buffer[index]++;

                while (buffer[index] != 0)
                {
                    index--;
                }

                index--;
                buffer[index]--;
            }

            index += 2;
            Console.Write((char)buffer[index]);
            index++;
            buffer[index] -= 3;
            Console.Write((char)buffer[index]);
            buffer[index] += 7;
            Console.Write((char)buffer[index]);
            Console.Write((char)buffer[index]);
            buffer[index] += 3;
            Console.Write((char)buffer[index]);
            index += 2;
            Console.Write((char)buffer[index]);
            index--;
            buffer[index]--;
            Console.Write((char)buffer[index]);
            index--;
            Console.Write((char)buffer[index]);
            buffer[index] += 3;
            Console.Write((char)buffer[index]);
            buffer[index] -= 6;
            Console.Write((char)buffer[index]);
            buffer[index] -= 8;
            Console.Write((char)buffer[index]);
            index += 2;
            buffer[index]++;
            Console.Write((char)buffer[index]);
            index++;
            buffer[index] += 2;
            Console.Write((char)buffer[index]);


            Console.WriteLine("Program terminated successfully...");
            Console.ReadLine();
        }
    }
}
\$\endgroup\$

3 Answers 3

8
\$\begingroup\$
if ((OptimizationLevel & OptimizationLevel.Level1) >= OptimizationLevel.Level1)
{
    if (lastSymbol != symbol && lastSymbol != TokenSymbol.None && (lastSymbol == TokenSymbol.Decrement || lastSymbol == TokenSymbol.Increment || lastSymbol == TokenSymbol.MoveLeft || lastSymbol == TokenSymbol.MoveRight))
    {
        Lines.AddRange(SymbolToLines(lastSymbol, symbolRepeated, indents));
        symbolRepeated = 0;
    }
    else
    {
        lastSymbol = symbol;
        symbolRepeated++;
    }
}

These lines are duplicated* 5 times in void Interpret(string): once in every single case block.. not ideal.

Start by copying it again a 6th time, here:

foreach (var symbol in _symbols)
{
    if (lastSymbol != symbol && lastSymbol != TokenSymbol.None && (lastSymbol == TokenSymbol.Decrement || lastSymbol == TokenSymbol.Increment || lastSymbol == TokenSymbol.MoveLeft || lastSymbol == TokenSymbol.MoveRight))
    {

    }

    switch (symbol)
    {
        ...

Now remove it from every single case block, except the last one* - and then turn this:

if (lastSymbol != symbol && lastSymbol != TokenSymbol.None && (lastSymbol == TokenSymbol.Decrement || lastSymbol == TokenSymbol.Increment || lastSymbol == TokenSymbol.MoveLeft || lastSymbol == TokenSymbol.MoveRight))

Into this:

if (lastSymbol != symbol && lastSymbol != TokenSymbol.None 
       && (lastSymbol == TokenSymbol.Decrement 
        || lastSymbol == TokenSymbol.Increment 
        || lastSymbol == TokenSymbol.MoveLeft 
        || lastSymbol == TokenSymbol.MoveRight))

Ah, now we can read it! Or can we? What's it saying anyway? What do the Decrement, Increment, MoveLeft and MoveRight symbols have in common?

Could we say that they're the instructions you consider optimizable?

private static readonly TokenSymbol[] OptimizableInstructions = 
{
    TokenSymbol.Decrement,
    TokenSymbol.Increment,
    TokenSymbol.MoveLeft,
    TokenSymbol.MoveRight
};

And that condition is verifying what exactly, whether the current symbol ends a sequence of repeating previous symbol?

private static bool IsRepeatedSymbolSequenceEnding(TokenSymbol previous, TokenSymbol current) 
        => previous != current 
        && previous != TokenSymbol.None 
        && OptimizableInstructions.Contains(previous);

That little static function is just enough abstraction to know what's going on without being bothered with the whole 12-operator logic:

if (IsRepeatedSymbolSequenceEnding(lastSymbol, symbol))
{
    Lines.AddRange(SymbolToLines(lastSymbol, symbolRepeated, indents));
    symbolRepeated = 0;
}
else
{
    lastSymbol = symbol;
    symbolRepeated++;
}

Not sure I like the naming - I mean, IsRepeatedSymbolSequenceEnding is kinda awful, but I'm thinking more of lastSymbol versus symbolRepeated - "last symbol" reads well. "repeated symbol" would read better than symbolRepeated.. but the variable is an int and is actually counting repetitions - wouldn't repetitions be a much better name for it?

Anyway, I skipped something:

if ((OptimizationLevel & OptimizationLevel.Level1) >= OptimizationLevel.Level1)

Why the bitwise operation on a non-flag enum here? What's wrong with simplicity here?

if (OptimizationLevel >= OptimizationLevel.Level1)

Per C# spec. 7.9.5, enum comparison operators operate like their underlying type:

In other words, the enumeration type comparison operators simply compare the underlying integral values of the two operands.

KISS dude.

*The last block is slightly different.


So, that last block.

case TokenSymbol.Decrement:
case TokenSymbol.Increment:
case TokenSymbol.MoveLeft:
case TokenSymbol.MoveRight:

Where have I seen those...

Ah, yes!

private static readonly TokenSymbol[] OptimizableInstructions = 
{
    TokenSymbol.Decrement,
    TokenSymbol.Increment,
    TokenSymbol.MoveLeft,
    TokenSymbol.MoveRight
};

I think you could turn that foreach loop into this then:

foreach (var symbol in _symbols)
{
    if (OptimizationLevel >= OptimizationLevel.Level1)
    {
        var isOptimizableSymbol = OptimizableInstructions.Contains(symbol);
        if (IsRepeatedSymbolSequenceEnding(lastSymbol, symbol))
        {
            Lines.AddRange(SymbolToLines(lastSymbol, repetitions, indents));
            repetitions = isOptimizableSymbol ? 1 : 0;
        }
        else
        {
            if (isOptimizableSymbol)
            {
                repetitions++;
            }
            else
            {
                repetitions = 0;
            }
        }
    }

    switch (symbol)
    {
        case TokenSymbol.LoopBegin:
            Lines.AddRange(SymbolToLines(symbol, repetitions, indents));
            indents += 1;
            break;

        case TokenSymbol.LoopEnd:
            indents -= 1;
            Lines.AddRange(SymbolToLines(symbol, repetitions, indents));
            break;

        case TokenSymbol.InputCharacter:
        case TokenSymbol.OutputValue:
            Lines.AddRange(SymbolToLines(symbol, repetitions, indents));
            break;
    }

    lastSymbol = symbol;
}

Notice lastSymbol = symbol appears once, at the end of the loop, and symbolRepeated doesn't need to be handled in the individual case blocks... which don't need a block for the OptimizableInstructions - and input/output can share the same case block.

I'm sure it could be further simplified - I don't like that nested if I've given you there... but it's already a bit better than it was, I think. Right?

\$\endgroup\$
1
  • \$\begingroup\$ Great stuff! I was having issues figuring out how I could abstract away that massive if block, and this handles it. :) \$\endgroup\$ Nov 24, 2015 at 15:13
5
\$\begingroup\$

MatsMug's answer is very good. However, I would "Keep It Even Simpler" with the following improvements:


You created the TokenSymbol enum... but why? You already have a perfectly good enumeration: + - < > [ ] , .. If you use these character values as the enumerators, then you can get rid of the entire Tokenize function.


You have this concept of a repeated TokenSymbol (for example, "+ repeated 3 times"), but you haven't encapsulated this concept into a single entity. How about introducing something like this?

struct RepeatedToken {
    public char token;
    public int repetitions;
}

List<RepeatedToken> Tokenize(string brainfuck) { ... }

Then you can generate code for a RepeatedToken all in one go.

switch (rt.token) {
    case '>':
        Lines.Append($"{GetIndents(indentLevels)}index += {rt.repetitions};");
    case '<':
        Lines.Append($"{GetIndents(indentLevels)}index -= {rt.repetitions};");
    case '[':
        for (int i=0; i < reptok.repetitions; ++i) {
            Lines.Append($"{GetIndents(indentLevels)}while (buffer[index] != 0) {");
            indentLevels += 1;
        }
    ...

and so on.


Once you've got this working (with about half the number of lines you have right now), the next complication I'd think of adding would be a special case optimization for [-] (a.k.a. buffer[index] = 0;). But this sequence of tokens doesn't fit into the RepeatedToken paradigm we were just developing! You'll have to generalize again. Perhaps what we mean when we say RepeatedToken is really more like Opcode — it could be "increment by N" (an opcode taking an operand), or "set current location to zero" (our new case), or "start a loop" (note: not "start N loops"; let's back off from the idea that everything has to be Repeated).

So now you've got the basic outline of a compiler: it'll take the input string, chunk it up into Opcodes according to the maximal munch rule, and then pretty-print each of those Opcodes to the output string.


You would also benefit from designing a little class to manage your pretty-print indentation, so you can stop writing so many curly braces and dollar signs. I would imagine something like this:

PrettyPrinter.Print("while (buffer[index] != 0) {");
PrettyPrinter.Indent();
PrettyPrinter.Print("index += 1;");
PrettyPrinter.Outdent();
PrettyPrinter.Print("}");

As for "optimization levels", that's probably premature optimization ...levels. :) However, if you do want to implement optimization levels, I strongly advise that the best practice in this department is not to hard-code tests like "if OptimizationLevel > 1 ..." into the actual code generator. What you should do instead is:

Implement a set of (ideally orthogonal) flags, for example

bool SquashRepetitions;
bool OptimizeSetToZero;
bool PrettyPrintWithIndentation;
...

Hard-code tests of these flags into your code-generator.

Then, at the very topmost level of your program, where you parse the command-line options passed in by the user (or however your user is going to specify that he wants -O0 versus -O1), write something like this:

SquashRepetitions = (OptimizationLevel >= 1);
OptimizeSetToZero = (OptimizationLevel >= 2);
PrettyPrintWithIndentation = (OptimizationLevel == 0);
...

(The exact method of doing this — whether you use a switch on OptimizationLevel, or a nest of ifs, or a bunch of independent ifs, or a bunch of independent assignments as shown here — is a matter of taste. Doesn't matter. The important point is that you are setting the backend's low-level flags based on the high-level optimization strategy, not scattering high-level strategy decisions throughout the backend.

For bonus points, you could replace that bunch of bool variables with a single bool array indexed by an enumeration, and then use Enum.Parse() to support command-line switches such as /GSquashRepetitions, /GOptimizeSetToZero, etc.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I will admit that the TokenSymbol seems redundant, but I forget what the actual characters mean so it's nice to have an enum to tell me what they do. \$\endgroup\$ Nov 24, 2015 at 15:17
1
\$\begingroup\$

Let us take a look at OptimizationLevel enum and your description:

/// <summary>
/// Determines how the <see cref="Interpreter"/> will optimize Brainfuck code.
/// </summary>
public enum OptimizationLevel
{
    /// <summary>
    /// Do not apply any optimizations.
    /// </summary>
    None,
    /// <summary>
    /// Apply first level optimizations (combining sequences of increment/decrement characters into one increment/decrement per sequence).
    /// </summary>
    Level1,
}   

This is self-explanatory. It represents the (currently two) possible optimization levels of BrainfuckSharp. Specifying None will not optimize the code, specifying Level1 will apply basic optimizations.

Well I don't think this is as self-explanatory as it could be. I see 3 terms to be used for that OptimizationLevel which isn't None.

We have the name Level1, the summary states Apply first level optimizations and in your description you talk about basic optimizations. Which of these should it be ? I guess this will just depend wether you will extend this some more.

By the way, I guess you had some more values in that enum... having a , after Level1 is a clear indicator ;-).


IMO the _validTokens should be initialized in the constructor using the Keys of the _tokenMap dictionary. In this way you need, for any future changes (maybe BrainFuck 4.0), only need to change that dictionary.

public Interpreter() 
{
    _validTokens = _tokenMap.Keys.ToList();
}

The WriteToFile() method can be optimized by using string.Jouin() like so

public void WriteToFile(string filename)
{
    using (var sw = new StreamWriter(filename))
    {
        sw.WriteLine(string.Join(Environment.NewLine,Lines));
    }
}  

Most of the remaining is already reviewed by @MatsMug.

\$\endgroup\$
1
  • \$\begingroup\$ Having a trailing comma does not necessarily mean that there are, or will be, new enum entries. I often use trailing commas myself just to make the version control diffs cleaner (I hate it when a line is considered changed just to add a comma) \$\endgroup\$ Nov 24, 2015 at 11:11

Your Answer

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

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