From cd699af1e7d3e64556d2f9373db1d337cf14d2f5 Mon Sep 17 00:00:00 2001 From: bnewbold Date: Tue, 18 Dec 2012 21:35:40 +0100 Subject: add more tests; cover ~~ case; fix bugs --- bytetunes.py | 12 +++++-- expr.py | 111 +++++++++++++++++++++++++++++++++++++++++++++++++++-------- notes.txt | 3 ++ 3 files changed, 110 insertions(+), 16 deletions(-) mode change 100644 => 100755 bytetunes.py diff --git a/bytetunes.py b/bytetunes.py old mode 100644 new mode 100755 index 1d2a8a7..8ed9641 --- a/bytetunes.py +++ b/bytetunes.py @@ -1,17 +1,25 @@ +#!/usr/bin/env python from expr import * import sys def play(s): - machine = parse(preparse(tokenize(s))[0]) + machine = parse(preparse(tokenize(s))) t = 0 while True: t += 1 sys.stdout.write(chr(execute(machine, t) & 0x000000FF)) def main(): - play("(t>>6)&(2*t)&(t>>1)") + if len(sys.argv) <= 1: + play("(t>>6)&(2*t)&(t>>1)") + elif sys.argv[1] == '--test': + test_tokenize() + test_preparse() + test_parse() + else: + play(sys.argv[1]) if __name__=='__main__': main() diff --git a/expr.py b/expr.py index 00435e9..0336ddd 100644 --- a/expr.py +++ b/expr.py @@ -45,7 +45,10 @@ def car(l): def cdr(l): return l[1:] -def preparse(l, depth=0): +def preparse(l): + return preparseh(l)[0] + +def preparseh(l, depth=0): """ match parens and set types """ @@ -53,11 +56,14 @@ def preparse(l, depth=0): for i in range(len(l)): if l[i] == '(': #print "%sleft: %s" % (" "*depth, ret) - middle, remains = preparse(l[i+1:], depth+1) + middle, remains = preparseh(l[i+1:], depth+1) #print "%smiddle: %s" % (" "*depth, middle) - right, moreright = preparse(remains, depth) + right, moreright = preparseh(remains, depth) #print "%sright: %s" % (" "*depth, right) - return ret + [tuple(cons('PARENS', middle))] + right, moreright + if middle: + return ret + [tuple(cons('PARENS', middle))] + right, moreright + else: + return ret + right, moreright elif l[i] == ')': if depth == 0: Exception("preparse: unexpected parens") @@ -77,35 +83,44 @@ def preparse(l, depth=0): raise Exception("preparse: unmatched parens") return ret, [] +def lastindex(l, item): + for i in range(len(l)-1, -1, -1): + if l[i] == item: + return i + return -1 + def parse(l): #print l if not l or len(l) == 0: - return [] + return tuple() if len(l) == 1: if car(car(l)) in ('VAR', 'NUM'): return ('ATOM', car(l)) elif car(car(l)) == 'PARENS': return parse(cdr(car(l))) + elif car(car(l)) == 'NOT': + # special case of NOT-NOT; already parsed + return l[0] else: raise Exception("parse error: %s" % l) # ~ has highest priority if ('NOTOPER',) in l: - i = l.index(('NOTOPER',)) + i = lastindex(l, ('NOTOPER',)) if i == len(l)-1: raise Exception("parse error: trailing ~") - return parse(l[:i] + ('NOT', parse(l[i+1])) + l[i+2:]) + return parse(l[:i] + [('NOT', parse([l[i+1]]))] + l[i+2:]) # helper function def hunt_opers(l, operlist): for i in range(1, len(l) - 1): if car(l[i]) == 'OPER' and l[i][1] in operlist: left = parse(l[:i]) right = parse(l[i+1:]) - if not car(left) in ['ATOM', 'BINARY', 'NOT']: + if not left[0] in ['ATOM', 'BINARY', 'NOT']: raise Exception("parse error: not a binary operand: %s" % - left) - if not car(right) in ['ATOM', 'BINARY', 'NOT']: + str(left)) + if not right[0] in ['ATOM', 'BINARY', 'NOT']: raise Exception("parse error: not a binary operand: %s" % - right) + str(right)) return ('BINARY', l[i][1], left, right) for operlist in binaryoper_priority: match = hunt_opers(l, operlist) @@ -125,8 +140,6 @@ def schemify(ast): def test_parse(): """ - () - ~~1 """ def tokenize(s): @@ -162,6 +175,9 @@ def tokenize(s): raise Exception("tokenization error: %s" % s) def execute(ast, t): + if ast == tuple(): + # null machine evals to 0; machine should have no null sub-expressions + return 0 if car(ast) == 'ATOM': if car(ast[1]) == 'VAR': return t @@ -196,9 +212,75 @@ def execute(ast, t): return left & right raise Exception("execute: unexpected node: %s" % car(ast)) - +def strmachine(ast): + if ast == tuple(): + return "" + if car(ast) == 'ATOM': + if car(ast[1]) == 'VAR': + return "t" + if car(ast[1]) == 'NUM': + return "%d" % ast[1][1] + elif car(ast) == 'NOT': + return "(~ %s)" % strmachine(ast[1]) + elif car(ast) == 'BINARY': + # UGH + oper, left, right = ast[1:4] + left = strmachine(ast[2]) + right = strmachine(ast[3]) + oper = oper.replace('r','>>').replace('l','<<') + return "(%s %s %s)" % (oper, left, right) + raise Exception("execute: unexpected node: %s" % car(ast)) + # ============================== +def test_preparse(): + """ + 0 + ()()()()()() + (((((()))))) + (1 + (2 >> 3) / 5) + """ + print "------ test_preparse" + assert preparse(tokenize("0")) == [('NUM', 0)] + assert preparse(tokenize("()()()()()()")) == [] + assert preparse(tokenize("(((((())))))")) == [] + assert preparse(tokenize("(1 + (2 >> 3) / 5)")) == \ + [('PARENS', ('NUM', 1), ('OPER', '+'), ('PARENS', ('NUM', 2), ('OPER', 'r'), ('NUM', 3)), ('OPER', '/'), ('NUM', 5))] + print "\tall passed!" + +def test_parse(): + """ + 0 + () + ~~1 + 1 + 2 * 3 ^ 5 | 6 & 7 >> 8 + ~ 9 + 1 + ~ 3 + anti: 1 (+ 3) + """ + print "------ test_parse" + assert parse(preparse(tokenize("()"))) == tuple() + assert parse(preparse(tokenize("0"))) == ('ATOM', ('NUM', 0)) + assert parse(preparse(tokenize("~1"))) == ('NOT', ('ATOM', ('NUM', 1))) + assert parse(preparse(tokenize("~~1"))) == ('NOT', ('NOT', ('ATOM', ('NUM', 1)))) + assert parse(preparse(tokenize("~~t"))) == ('NOT', ('NOT', ('ATOM', ('VAR',)))) + assert parse(preparse(tokenize("1<<1"))) == \ + ('BINARY', 'l', ('ATOM', ('NUM', 1)), ('ATOM', ('NUM', 1))) + assert parse(preparse(tokenize("1^1"))) == \ + ('BINARY', '^', ('ATOM', ('NUM', 1)), ('ATOM', ('NUM', 1))) + assert parse(preparse(tokenize("1 + ~ 3"))) == \ + ('BINARY', '+', ('ATOM', ('NUM', 1)), ('NOT', ('ATOM', ('NUM', 3)))) + try: + assert parse(preparse(tokenize("1 (+ 3)"))) == "SHOULD FAIL" + except: + pass + try: + assert parse(preparse(tokenize("1 ~"))) == "SHOULD FAIL" + except: + pass + assert strmachine(parse(preparse(tokenize("1 + 2 * 3 ^ 5 | 6 & 7 >> 8 + ~ 9")))) == \ + "(| (^ (+ 1 (* 2 3)) 5) (& 6 (>> 7 (+ 8 (~ 9)))))" + def test_tokenize(): + print "------ test_tokenize" assert tokenize("(t>>4)") == ['(','t','r',4,')'] assert tokenize("t") == ['t'] assert tokenize("i") == ['t'] @@ -232,4 +314,5 @@ def test_tokenize(): assert tokenize("x123") is "TOKENIZE ERROR" except: pass + print "\tall passed!" diff --git a/notes.txt b/notes.txt index 80773b8..102da5a 100644 --- a/notes.txt +++ b/notes.txt @@ -29,6 +29,9 @@ bytetros? original (to me): echo "main(i){for(i=0;;i++)putchar((i*(i>>8|i>>9)&46&i>>8)^(i&i>>13|i>>6));}" | gcc -x c - && ./a.out | aplay +favorite: + (t*9&t>>4|t*5&t>>7|t*3&t/1024)-1 + from http://countercomplex.blogspot.de/2011/10/algorithmic-symphonies-from-one-line-of.html main(t){for(t=0;;t++)putchar(t*(((t>>12)|(t>>8))&(63&(t>>4))));} -- cgit v1.2.3