Created
January 19, 2021 16:15
-
-
Save darius/fafde90ad3cf527b867f3df847e4bf3f to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ | |
| 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') | |
| #. ################################################################################################################################ | |
| #. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | |
| #. #### #### #### #### #### #### #### #### #### #### #### #### #### #### #### #### | |
| #. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # # # # # # # # # | |
| #. ######## ######## ######## ######## ######## ######## ######## ######## | |
| #. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # # # # # # # # # | |
| #. #### #### #### #### #### #### #### #### | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. ################ ################ ################ ################ | |
| #. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # # # # # # # # # | |
| #. #### #### #### #### #### #### #### #### | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. ######## ######## ######## ######## | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. #### #### #### #### | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. ################################ ################################ | |
| #. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # # # # # # # # # | |
| #. #### #### #### #### #### #### #### #### | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. ######## ######## ######## ######## | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. #### #### #### #### | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. ################ ################ | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. #### #### #### #### | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. ######## ######## | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. #### #### | |
| #. # # # # | |
| #. ## ## | |
| #. # # | |
| #. ################################################################ | |
| #. # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # # # # # # # # # | |
| #. #### #### #### #### #### #### #### #### | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. ######## ######## ######## ######## | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. #### #### #### #### | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. ################ ################ | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. #### #### #### #### | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. ######## ######## | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. #### #### | |
| #. # # # # | |
| #. ## ## | |
| #. # # | |
| #. ################################ | |
| #. # # # # # # # # # # # # # # # # | |
| #. ## ## ## ## ## ## ## ## | |
| #. # # # # # # # # | |
| #. #### #### #### #### | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. ######## ######## | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. #### #### | |
| #. # # # # | |
| #. ## ## | |
| #. # # | |
| #. ################ | |
| #. # # # # # # # # | |
| #. ## ## ## ## | |
| #. # # # # | |
| #. #### #### | |
| #. # # # # | |
| #. ## ## | |
| #. # # | |
| #. ######## | |
| #. # # # # | |
| #. ## ## | |
| #. # # | |
| #. #### | |
| #. # # | |
| #. ## | |
| #. # |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment