caronte_parson.py

"""
derived from Kragen Sitaker's http://canonical.org/~kragen/sw/dev3/caronte.py
"""

from __future__ import division, print_function
from parson import Grammar

# TODO {'foo'} won't work quite right with FNORD

grammar_text = r"""
program :  '' expr :end.

expr    :  e10 ++ (';' :';').
e10     :  lvalue ( ':=' e10 :'put'
                  | '='  e10 :'init')
        |  e40.
lvalue  :  id (:'@' '[' expr ']')*.
e40     :  lvalue '<-' e60 '|' :'each' e40 :'done'
        |  e60.
e60     :  e65 ('?' :'if' e65 ':' :'else' e60 :'then')?.
e65     :  e70 ('==' e70 :'==')?.
e70     :  e110 ('+' e110 :'+')*.
e110    :  e120 ( '[' expr ']' :'@'
                | '(' actuals ')' :'call'
                )*.
e120    :  '(' expr ')'
        |  id :'@'
        |  :'con' string
        |  :'con' integer
        |  '{' '}'  :'newdict'.

actuals =  (e40 :'arg') ** ','.

id      :  :'id' /([A-Za-z_]\w*)/.

string  :  /"((?:[^\\"]|\\.)*)"/.
integer :  /(\d+)/ :int.

FNORD  ~:  /\s*/.
"""
parser = Grammar(grammar_text)()

def run(prog):

    # Scan program to set up jump targets
    jump_targets = {}

    cstack = []
    i = 0
    while i < len(prog):
        c = prog[i]
        if c in ('each', 'if'):
            cstack.append((c, i))
        elif c == 'done':
            a, b = cstack.pop()
            assert a == 'each'
            jump_targets[i] = b + 1
            jump_targets[b] = i
        elif c == 'else':
            a, b = cstack.pop()
            assert a == 'if'
            jump_targets[b] = i + 1
            cstack.append((c, i))
        elif c == 'then':
            a, b = cstack.pop()
            assert a == 'else'
            jump_targets[b] = i
        elif c in ('id', 'con'):
            i += 2
            continue
        i += 1
    assert not cstack

    pc = 0
    ram = {'iota': lambda n: list(range(n)), 'say': lambda v: print(*v, end='')}
    stack = []
    args = []
    loops = []

    # Now run it
    lenprog = len(prog)
    while pc < lenprog:
        c = prog[pc]
        if c == 'newdict':
            stack.append({})
        elif c == ';':
            stack.pop()
        elif c == 'con':
            pc += 1
            stack.append(prog[pc])
        elif c == '+':
            x = stack.pop()
            stack.append(stack.pop() + x)
        elif c == '==':
            x = stack.pop()
            stack.append('true' if stack.pop() == x else 'false')
        elif c == 'arg':
            args.append(stack.pop())
        elif c == 'call':
            f = stack.pop()
            stack.append(f(*args))
            args = []
        elif c == 'id':
            pc += 1
            stack.append(ram)
            stack.append(prog[pc])
        elif c == '@':
            idx = stack.pop()
            loc = stack.pop()
            stack.append(loc[idx])
        elif c in ('init', 'put'):
            val = stack.pop()
            idx = stack.pop()
            loc = stack.pop()
            loc[idx] = val
            stack.append(val)
        elif c == 'each':
            seq = stack.pop()
            idx = stack.pop()
            loc = stack.pop()
            loops.append([loc, idx, seq, 0])
            pc = jump_targets[pc]
            continue
        elif c == 'done':
            loc, off, seq, idx = loops[-1]
            if idx >= len(seq):
                loops.pop()
                pc += 1
                stack.append(seq) # was missing from Kragen's; I think it's the desired semantics?
                continue
            loc[off] = seq[idx]
            loops[-1][-1] += 1
            pc = jump_targets[pc]
            continue
        elif c == 'if':
            x = stack.pop()
            assert x in ('true', 'false')
            if x == 'false':
                pc = jump_targets[pc]
                continue
        elif c == 'else':
            pc = jump_targets[pc]
            continue
        elif c == 'then':
            pass
        else:
            assert 0, "bad insn %r at %d" % (c, pc)

        pc += 1

# Smoke test

sier = """
    c = {};
    x <- iota(128) | (c[x] = 0);
    c[0] := 1;
    y <- iota(128) | (
        x <- iota(127) | (c[x+1] := (c[x] + c[x+1] == 1) ? 1 : 0);
        x <- iota(128) | say((c[x] == 0) ? " " : "#");
        say("\n")
    )
"""

def testme():
    prog = parser.program(sier)
    print(prog)
    run(prog)

if __name__ == '__main__':
    testme()

## foo = 'say( (c[x] == 0) ? " " : "#" )'
## parser.expr(foo)
#. ('id', 'say', '@', 'id', 'c', '@', 'id', 'x', '@', '@', 'con', 0, '==', 'if', 'con', ' ', 'else', 'con', '#', 'then', 'arg', 'call')

## testme()
#. ('id', 'c', 'newdict', 'init', ';', 'id', 'x', 'id', 'iota', '@', 'con', 128, 'arg', 'call', 'each', 'id', 'c', '@', 'id', 'x', '@', 'con', 0, 'init', 'done', ';', 'id', 'c', '@', 'con', 0, 'con', 1, 'put', ';', 'id', 'y', 'id', 'iota', '@', 'con', 128, 'arg', 'call', 'each', 'id', 'x', 'id', 'iota', '@', 'con', 127, 'arg', 'call', 'each', 'id', 'c', '@', 'id', 'x', '@', 'con', 1, '+', 'id', 'c', '@', 'id', 'x', '@', '@', 'id', 'c', '@', 'id', 'x', '@', 'con', 1, '+', '@', '+', 'con', 1, '==', 'if', 'con', 1, 'else', 'con', 0, 'then', 'put', 'done', ';', 'id', 'x', 'id', 'iota', '@', 'con', 128, 'arg', 'call', 'each', 'id', 'say', '@', 'id', 'c', '@', 'id', 'x', '@', '@', 'con', 0, '==', 'if', 'con', ' ', 'else', 'con', '#', 'then', 'arg', 'call', 'done', ';', 'id', 'say', '@', 'con', '\n', 'arg', 'call', 'done')
#. ################################################################################################################################
#. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
#. ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  
#. #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   
#. ####    ####    ####    ####    ####    ####    ####    ####    ####    ####    ####    ####    ####    ####    ####    ####    
#. # #     # #     # #     # #     # #     # #     # #     # #     # #     # #     # #     # #     # #     # #     # #     # #     
#. ##      ##      ##      ##      ##      ##      ##      ##      ##      ##      ##      ##      ##      ##      ##      ##      
#. #       #       #       #       #       #       #       #       #       #       #       #       #       #       #       #       
#. ########        ########        ########        ########        ########        ########        ########        ########        
#. # # # #         # # # #         # # # #         # # # #         # # # #         # # # #         # # # #         # # # #         
#. ##  ##          ##  ##          ##  ##          ##  ##          ##  ##          ##  ##          ##  ##          ##  ##          
#. #   #           #   #           #   #           #   #           #   #           #   #           #   #           #   #           
#. ####            ####            ####            ####            ####            ####            ####            ####            
#. # #             # #             # #             # #             # #             # #             # #             # #             
#. ##              ##              ##              ##              ##              ##              ##              ##              
#. #               #               #               #               #               #               #               #               
#. ################                ################                ################                ################                
#. # # # # # # # #                 # # # # # # # #                 # # # # # # # #                 # # # # # # # #                 
#. ##  ##  ##  ##                  ##  ##  ##  ##                  ##  ##  ##  ##                  ##  ##  ##  ##                  
#. #   #   #   #                   #   #   #   #                   #   #   #   #                   #   #   #   #                   
#. ####    ####                    ####    ####                    ####    ####                    ####    ####                    
#. # #     # #                     # #     # #                     # #     # #                     # #     # #                     
#. ##      ##                      ##      ##                      ##      ##                      ##      ##                      
#. #       #                       #       #                       #       #                       #       #                       
#. ########                        ########                        ########                        ########                        
#. # # # #                         # # # #                         # # # #                         # # # #                         
#. ##  ##                          ##  ##                          ##  ##                          ##  ##                          
#. #   #                           #   #                           #   #                           #   #                           
#. ####                            ####                            ####                            ####                            
#. # #                             # #                             # #                             # #                             
#. ##                              ##                              ##                              ##                              
#. #                               #                               #                               #                               
#. ################################                                ################################                                
#. # # # # # # # # # # # # # # # #                                 # # # # # # # # # # # # # # # #                                 
#. ##  ##  ##  ##  ##  ##  ##  ##                                  ##  ##  ##  ##  ##  ##  ##  ##                                  
#. #   #   #   #   #   #   #   #                                   #   #   #   #   #   #   #   #                                   
#. ####    ####    ####    ####                                    ####    ####    ####    ####                                    
#. # #     # #     # #     # #                                     # #     # #     # #     # #                                     
#. ##      ##      ##      ##                                      ##      ##      ##      ##                                      
#. #       #       #       #                                       #       #       #       #                                       
#. ########        ########                                        ########        ########                                        
#. # # # #         # # # #                                         # # # #         # # # #                                         
#. ##  ##          ##  ##                                          ##  ##          ##  ##                                          
#. #   #           #   #                                           #   #           #   #                                           
#. ####            ####                                            ####            ####                                            
#. # #             # #                                             # #             # #                                             
#. ##              ##                                              ##              ##                                              
#. #               #                                               #               #                                               
#. ################                                                ################                                                
#. # # # # # # # #                                                 # # # # # # # #                                                 
#. ##  ##  ##  ##                                                  ##  ##  ##  ##                                                  
#. #   #   #   #                                                   #   #   #   #                                                   
#. ####    ####                                                    ####    ####                                                    
#. # #     # #                                                     # #     # #                                                     
#. ##      ##                                                      ##      ##                                                      
#. #       #                                                       #       #                                                       
#. ########                                                        ########                                                        
#. # # # #                                                         # # # #                                                         
#. ##  ##                                                          ##  ##                                                          
#. #   #                                                           #   #                                                           
#. ####                                                            ####                                                            
#. # #                                                             # #                                                             
#. ##                                                              ##                                                              
#. #                                                               #                                                               
#. ################################################################                                                                
#. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #                                                                 
#. ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##                                                                  
#. #   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #                                                                   
#. ####    ####    ####    ####    ####    ####    ####    ####                                                                    
#. # #     # #     # #     # #     # #     # #     # #     # #                                                                     
#. ##      ##      ##      ##      ##      ##      ##      ##                                                                      
#. #       #       #       #       #       #       #       #                                                                       
#. ########        ########        ########        ########                                                                        
#. # # # #         # # # #         # # # #         # # # #                                                                         
#. ##  ##          ##  ##          ##  ##          ##  ##                                                                          
#. #   #           #   #           #   #           #   #                                                                           
#. ####            ####            ####            ####                                                                            
#. # #             # #             # #             # #                                                                             
#. ##              ##              ##              ##                                                                              
#. #               #               #               #                                                                               
#. ################                ################                                                                                
#. # # # # # # # #                 # # # # # # # #                                                                                 
#. ##  ##  ##  ##                  ##  ##  ##  ##                                                                                  
#. #   #   #   #                   #   #   #   #                                                                                   
#. ####    ####                    ####    ####                                                                                    
#. # #     # #                     # #     # #                                                                                     
#. ##      ##                      ##      ##                                                                                      
#. #       #                       #       #                                                                                       
#. ########                        ########                                                                                        
#. # # # #                         # # # #                                                                                         
#. ##  ##                          ##  ##                                                                                          
#. #   #                           #   #                                                                                           
#. ####                            ####                                                                                            
#. # #                             # #                                                                                             
#. ##                              ##                                                                                              
#. #                               #                                                                                               
#. ################################                                                                                                
#. # # # # # # # # # # # # # # # #                                                                                                 
#. ##  ##  ##  ##  ##  ##  ##  ##                                                                                                  
#. #   #   #   #   #   #   #   #                                                                                                   
#. ####    ####    ####    ####                                                                                                    
#. # #     # #     # #     # #                                                                                                     
#. ##      ##      ##      ##                                                                                                      
#. #       #       #       #                                                                                                       
#. ########        ########                                                                                                        
#. # # # #         # # # #                                                                                                         
#. ##  ##          ##  ##                                                                                                          
#. #   #           #   #                                                                                                           
#. ####            ####                                                                                                            
#. # #             # #                                                                                                             
#. ##              ##                                                                                                              
#. #               #                                                                                                               
#. ################                                                                                                                
#. # # # # # # # #                                                                                                                 
#. ##  ##  ##  ##                                                                                                                  
#. #   #   #   #                                                                                                                   
#. ####    ####                                                                                                                    
#. # #     # #                                                                                                                     
#. ##      ##                                                                                                                      
#. #       #                                                                                                                       
#. ########                                                                                                                        
#. # # # #                                                                                                                         
#. ##  ##                                                                                                                          
#. #   #                                                                                                                           
#. ####                                                                                                                            
#. # #                                                                                                                             
#. ##                                                                                                                              
#. #