Vermeille's blog

Resume && contactProjetsC++BullshitLanguage TheoryArtificial Intelligence¬LinkedIn

Tag - modern

Entries feed - Comments feed

Saturday 24 March 2012

Playing with templates

Templates are good

Continue reading...

Thursday 16 February 2012

Variadic Templated Brainfuck "Compiler"

I let you consult wikipedia page about Brainfuck, an array oriented language, which recognizes only 8 chars. The global idea was to metaprogram, from brainfuck code, a compiled (not interpreted) executable. C++11 gives us variadic templates, which allows any number of arguments

In order to have a main line like this:

Exec<'+', '+', '>', '[', '-', ']'>(environment, ptr);

We have to use static class members as workaround since we can't partially specialize templated functions.

We can easily define operators <, >, +, -, ',', '.'. e is the environment and i the index

typedef std::vector<char> Env;

template <char... Cs>
struct Exec;

template <char... Cs>
struct Exec<'+', Cs...>
{
    static inline void Exe(Env& e, int& i)
    {
        ++e[i];
        Exec<Cs...>::Exe(e, i);
    }
};

template<char... Cs>
struct Exec<'-', Cs...>
{
    static inline void Exe(Env& e, int& i)
    {
        --e[i];
        Exec<Cs...>::Exe(e, i);
    }
};

template <char...Cs>
struct Exec<'<', Cs...>
{
    static inline void Exe(Env& e, int& i)
    {
        --i;
        Exec<Cs...>::Exe(e, i);
    }
};

template <char...Cs>
struct Exec<'>', Cs...>
{
    static inline void Exe(Env& e, int& i)
    {
        if (++i > e.size())
            e.push_back(0);
        Exec<Cs...>::Exe(e, i);
    }
};

template <char...Cs>
struct Exec<'.', Cs...>
{
    static inline void Exe(Env& e, int& i)
    {
        std::cout << e[i];
        Exec<Cs...>::Exe(e, i);
    }
};

template <char... Cs>
struct Exec<',', Cs...>
{
    static inline void Exe(Env& e, int& i)
    {
        std::cin >> e[i];
        Exec<Cs...>::Exe(e, i);
    }
};

template <>
struct Exec<>
{
    static inline void Exe(Env&, int&)
    {
        return;
    }
};


Each function does current token's instruction, then execute the following. The first symbol of token list is matched, the corresponding specialization is called, et everything goes on. Inlining avoids overheads of function calls for each instruction, and linearizes brainfuck execution. But we still don't handle the loop ('[' and ']').

Handling adds complexity : when we meet '[', we have to start a loop ending on ']'. Let's implement it.

template <char... Cs>
struct Exec<'[', Cs...>
{
    static inline void Exe(Env& e, int& i)
    {
        while (e[i])
        {
            Exec<Cs...>::Exe(e, i);
        }
    }
};

template <char... Cs>
struct Exec<']', Cs...>
{
    static inline void Exe(Env& e, int& i)
    {
        return ;
    }
};

The loop is correctly executed, but the program stops here. Something in missing when we call '[': the code to execute after the loop. We can imagine something like this:

struct Exec<'[', Cs...>
{
    static inline void Exe(Env& e, int& i)
    {
        while (e[i])
        {
            Exec<Cs...>::Exe(e, i);
        }
        Wait<Cs...>::WaitBracket(e, i);
    }
};

WaitBracket should ignore all chars until ']', then continues the execution.

template <char C, char... Cs>
struct Wait
{
    static inline void WaitBracket(Env& e, int& i)
    {
        return Wait<Cs...>::WaitBracket(e, i) ;
    }
};

template <char... Cs>
struct Wait<']', Cs...>
{
    static inline void WaitBracket(Env& e, int& i)
    {
        return Exec<Cs...>::Exe(e, i);
    }
};

And we're done ! Only the main() is missing:

int main(void)
{
    int i = 0;
    Env e(10, 0);
    // Un petit Hello World en BrainFuck
    Exec<'+', '+', '+', '+', '+', '+', '+', '+', '+', '+',
      '[',
        '>', '+', '+', '+', '+', '+', '+', '+',
        '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+',
        '>', '+', '+', '+',
        '>', '+',
        '<', '<', '<', '<', '-',
      ']',
      '>', '+', '+', '.',
      '>', '+', '.',
      '+', '+', '+', '+', '+', '+', '+', '.',
      '.',
      '+', '+', '+', '.',
      '>', '+', '+',
      '.',
      '<', '<',
      '+', '+', '+', '+', '+', '+', '+', '+',
                '+', '+', '+', '+', '+', '+', '+', '.',
      '>', '.',
      '+', '+', '+', '.',
      '-', '-', '-', '-', '-', '-', '.',
      '-', '-', '-', '-', '-', '-', '-', '-', '.',
      '>', '+', '.',
      '>', '.'>::Exe(e, i);
    return 0;
}

Et tout fonctionne à Vermeille !