gccg.py

import sys, re

# convert lispy-like language to 'lambda-man' ICFP2014 assembler.
# output is JavaScript, loaded in browser

def parse(s, i):
    node = []
    while 1:
        while i < len(s) and (s[i] == ' ' or s[i] == '\n' or s[i] == '\r' or s[i] == '\t'):
            i = i+1
        if i == len(s):
            break
        if i < len(s):
            if s[i] == '(':
                i += 1
                n2, i = parse(s, i)
                node.append(n2)
                assert s[i-1] == ')'
            elif s[i] == ')':
                i += 1
                break
            else:
                id = ''
                while i < len(s) and (s[i] not in ' ()\r\n'):
                    id += s[i]
                    i += 1
                node.append(id)
    return node, i


def gen_all(tree, game_mode):  #game mode - environment call us with 2 parameters
    code = []
    env0 = {}
    append = code.append
    
    if game_mode:
        append('LD 0 0'.split())
        append('LD 0 1'.split())
    
    def gen(x, env):
        if not isinstance(x, str):
            f = x[0]
            if f == 'if':
                # TSEL A B
                # A: ...
                # LDC 0 
                # TSEL X X
                # B: ...
                # X:
                c, t, f = x[1:]
                gen(c, env)
                tsel = ['TSEL', None, None] #jump values are filled after
                append(tsel)
                tsel[1] = str(len(code))
                gen(t, env)
                append(['LDC', '0'])
                tsel2 = ['TSEL', None, None] #jump values are filled after
                append(tsel2)
                tsel[2] = str(len(code))
                gen(f, env)
                tsel2[1] = tsel2[2] = str(len(code))
            elif f == 'dbug':
                assert len(x) == 2, repr(x)
                gen(x[1], env)
                append(['DBUG'])
                append(['LDC', '0'])
            elif f in (list('+-*/') + ['==', '>', '>='] + ['<', '<='] + ['cons']):
                assert len(x) == 3, repr(x)
                a, b = x[1], x[2]
                if f in ['<', '<=']:
                    a, b = b, a
                gen(a, env)
                gen(b, env)
                append([{
                    '+':'ADD','-':'SUB','*':'MUL','/':'DIV',
                    '==':'CEQ', 
                    '>':'CGT','<=':'CGT',
                    '>=':'CGTE','<':'CGTE',
                    'cons': 'CONS'
                }[f]]);
            elif f in ('car', 'cdr', 'atom'):
                assert len(x) == 2, repr(x)
                gen(x[1], env)
                append([{
                    'car':'CAR','cdr':'CDR','atom':'ATOM',
                }[f]]);                
            elif f == 'ff': 
                #ff - define lambda function
                vars = x[1:-1]
                func = ['LDF', None] #second field is filled after
                append(func)
                append(['LDC', '0'])
                tsel = ['TSEL', '?', '?']
                append(tsel)
                #replace current visible variables with new from function parameters
                new_env = dict((name, (depth+1, i)) for name, (depth, i) in env.iteritems())
                for i, name in enumerate(vars):
                    assert isinstance(name, str), name #todo: pattern matching for tuples
                    new_env[name] = (0, i)
                func[1] = str(len(code))
                gen(x[-1], new_env)
                code.append(['RTN'])
                tsel[1] = tsel[2] = str(len(code))
            else:
                #treat everything else as function call.
                for arg in x[1:]:
                    gen(arg, env)
                gen(f, env)
                code.append(['AP', str(len(x)-1)])
        else:
            is_int = True
            try: x_int_val = int(x)
            except: is_int = False
            
            if is_int:
                append(['LDC', str(x_int_val)])
            elif x in env:
                #treat as variable name
                append(['LD', '%s %s' % env[x], ';', str(x)])
            else:
                assert False, 'unknown constant ' + repr(x)
    gen(tree, env0)
    
    if game_mode:
        append(['TAP', '2'])
    else:
        append(['DBUG'])
        append(['RTN'])
    
    return code
    
def rewrite(tree):
    if isinstance(tree, str):
        return tree
    if tree[0] != 'let':
        return map(rewrite, tree)
        
    #convert 'let' to 'ff': 
    # ( let (x x_val) (y y_val) code ) -> ((ff x ((ff y code) x_val)) x_val)
    vars = tree[1:-1] #variable (name, value) pairs
    code = tree[-1] #last piece - is code
    code = rewrite(code)
    for name, val in reversed(vars):
        code = [['ff', name, code], rewrite(val)]
    return code
    
def fix_tail_call(code):
    for i in xrange(len(code)-1):
        if (code[i][0] == 'AP' and code[i+1][0] == 'RTN'):
            code[i] = ['TAP'] + code[i][1:]
            # leave 'RTN' in code, because it can be target of jump, 
            # and avoid remapping of code offsets
            # NOTE: do not fork for first branch of (if (something) (First) (Second))
        
def main():
    #src = '(if (> (* 5 5) 25) (* 3 x) (/ 77 7))'
    src_file = sys.argv[1]
    src = open(src_file).read()
    src = re.sub(';.*', '', src) #delete comments. We don't have string literals now, so every ';' is comment
    tree, _ = parse(src, 0)
    tree = tree[0]
    #print tree
    tree = rewrite(tree)
    #print tree
    code = gen_all(tree, game_mode = 1)
    
    fix_tail_call(code)
    
    #print as-is to stdout:
    #for i, c in enumerate(code):
    #    print '%-18s ; %02d' % (' '.join(c), i)
    
    #print to javascript data-file:
    template = '''
        function my_lambda_prog() {
            return (
            ""
AAA
            );
        }
        
    '''
    lines = ['%-18s ; %02d' % (' '.join(c), i) for i, c in enumerate(code)]
    open('my_prog.js', 'w').write(
        template.replace('AAA', ''.join('+%s\n' % repr(line + '\n') for line in lines))
    )
    
main()