My first fifteen compilers

Since I'm not sure how understandable the explanation was, here is an example, a simple interpreter for a Lisp-like language, using Python lists as the syntax tree.

    def interpret(state, function_table, expression):
        function = function_table[expression[0]]
        return function(state, function_table, *expression[1:])
    
    def interpret_all(state, function_table, expressions):
        return [interpret(state, function_table, e) for e in expressions]
    
    interpreter_table = {
        '+': lambda s, ft, *es: reduce(lambda a, b: a + b, interpret_all(s, ft, es)), # sum
        '*': lambda s, ft, *es: reduce(lambda a, b: a * b, interpret_all(s, ft, es)), # product
        '!': lambda s, ft, k, v: s.update({k: interpret(s, ft, v)}),                  # set variable
        '?': lambda s, ft, k: s[k],                                                   # get variable
        ';': lambda s, ft, *es: interpret_all(s, ft, es)[-1],                         # execute a sequence and get the last value
    }

An example program for 'x = a * (b + a), return x * x' looks like this:

    program = [';',
                ['!', 'x', ['*', ['?', 'a'], ['+', ['?', 'b'], ['?', 'a']]]],
                ['*', ['?', 'x'], ['?', 'x']]]

You can execute the interpreter with initial values for a and b like this:

    >>> interpret({'a': 10, 'b': 20}, interpreter_table, program)
    90000

The compiler can be implemented by swapping out the interpreter_table with different functions to print code instead of executing it:

    def fresh_variable(state):
        next_tmp = state.get('__next_tmp__', 0)
        var = 'tmp_%s' % next_tmp
        state['__next_tmp__'] = next_tmp+1
        return var
    
    def compile_sum(state, a, b):
        var = fresh_variable(state)
        print(var+' = '+a+' + '+b)
        return var
    
    def compile_product(state, a, b):
        var = fresh_variable(state)
        print(var+' = '+a+' * '+b)
        return var
    
    def compile_set(state, key, value):
        state[key] = key
        print(key+' = '+value)
    
    compiler_table = {
        '+': lambda s, ft, *es: reduce(lambda a, b: compile_sum    (s, a, b), interpret_all(s, ft, es)), # sum
        '*': lambda s, ft, *es: reduce(lambda a, b: compile_product(s, a, b), interpret_all(s, ft, es)), # product
        '!': lambda s, ft, k, v: compile_set(s, k, interpret(s, ft, v)),                                 # set variable
        '?': lambda s, ft, k: s[k],                                                                      # get variable
        ';': lambda s, ft, *es: interpret_all(s, ft, es)[-1],                                            # execute a sequence and get the last value
    }

Then you can easily compile the program:

    >>> interpret({'a': '10', 'b': '20'}, compiler_table, program)
    tmp_0 = 20 + 10
    tmp_1 = 10 * tmp_0
    x = tmp_1
    tmp_2 = x * x
    'tmp_2' # this is the return value, telling you where to find the result

Depending on the syntax of your target language, control flow might require additional compiler state. In Python, I would have to store the current indentation level. If someone is interested, I could show how to do if-statements.

Blender is a toolset for creating nanopass compilers: https://github.com/keyboardDrummer/Blender

Close parallels to partial evaluation and the Futamura projections. https://en.wikipedia.org/wiki/Partial_evaluation#Futamura_pr...

As a favor for a friend, I wrote a mini-"compiler" that translated detailed specs for story game scenes into code. I had never done anything similar (my background is more on the Math/Stats side) but I figured hey, what the hell.

There were only a few types of possible scenes, so my first approach was to create a data structure for each type of scene that had a method converting it to code. However, this broke badly with conditional/branching paths that could potentially have arbitrary levels of nesting.

So my next approach was to create multiple passes using some simple recursive data structures "Parseables" where conditional branches could contain other Parseables (including other conditional branches) as well as multiple passes (Text -> Parseable -> Printable -> Code instead of Text -> Screen -> Code.) This worked quite nicely.

Had I realized this was a compiler, I could have probably read some tutorials and not had to do everything from scratch. This would probably have resulted in better engineering, but been a lot less fun.

My amateurish code, if anyone is curious: https://github.com/Satvik/spec-compiler

That paper is amazing.

Plug for my course, which is built around the ideas in Ghuloum's paper, and I've talked about before on HN:

https://news.ycombinator.com/item?id=13207695 https://news.ycombinator.com/item?id=15005853