User:Marinus/Oozlybub and Murphy interpreter
Jump to navigation
Jump to search
This is a prototype of an Oozlybub and Murphy interpreter. All the functionality should be there, but:
- it is slow and buggy,
- the parser is too inefficient for practical use,
- there's no optimalisation at all, so the canonical way to loop slows down on each iteration.
I might get round to fixing it.
#!/usr/bin/env python3
#################
## oozly.py
## Oozlybub & Murphy interpreter
##
## written by Marinus Oosters
##
#################
##
## For parsing, I use the LEPL library:
## * http://www.acooke.org/lepl/
##
## For the regexp equivalency tests, I am using Sam Hughes's 'greenery' library:
## * https://github.com/ferno/greenery
## * http://qntm.org/greenery
#################
def die(error):
print("\x1b[1;40;31mError:\x1b[0m", error, file=sys.stderr)
# only actually exit if the file is running as a script
if __name__ == "__main__": sys.exit()
# check for Python 3
import sys, re, math, operator, random, argparse
if (sys.version_info.major < 3):
die("This program needs Python 3")
# check if the greenery library is installed
try:
# Depending on installation, the parse function might end up as greenery.parse or greenery.lego.parse
# I have no idea why, but here's a workaround
import greenery
if not "parse" in greenery.__dict__:
from greenery import lego
greenery = lego
except ImportError:
die("This program needs the Greenery library. See: http://qntm.org/greenery")
# check if the lepl libary is installed
try:
from lepl import*
except ImportError:
die("This program needs LEPL. See: http://www.acooke.org/lepl")
# debug/verbose function
DEBUG = True
def debug(message):
if DEBUG:
print("\x1b[1;7m?>\x1b[0m", message, file=sys.stderr)
VERBOSE = True
def verbose(message):
if VERBOSE:
print("\x1b[1;7m>>\x1b[0m", message, file=sys.stderr)
################
# Code error
class CodeError(Exception): pass
# Generate ordinal suffix
def ordsuffix(num):
if num in (11,12,13): return 'th'
if num % 10 == 1: return 'st'
if num % 10 == 2: return 'nd'
if num % 10 == 3: return 'rd'
return 'th'
# Primes
class Primes(object):
def __init__(self, pregen = 1000, primality_test = None):
self.primes = []
self.lastnum = 1
self.pregen = pregen
if primality_test:
self.__primality_test = primality_test
self.__more_primes(pregen)
def __more_primes(self, amount):
verbose('Generating %d primes. (Have %d, last: %d)' % (amount, len(self.primes), self.lastnum))
for _ in range(amount): self.__sieve()
def below(self, num):
# generate primes upto num if necessary
while num > self.lastnum:
self.__more_primes(self.pregen)
# get all primes below num
# don't use list comprehension because it'll go through the whole list and it's sorted
primes = []
for prime in self.primes:
if prime > num: break
primes.append(prime)
# return them in descending order (for for-each-prime)
return reversed(primes)
def isPrime(self, num):
# if we already have it, use it
if (num <= self.lastnum): return num in self.primes
else: return self.primality_test(num)
@staticmethod
def __primality_test(num):
for n in self.primes:
if num%n==0: return False
for n in range(self.lastnum, math.sqrt(num)):
if num%n==0: return False
return True
def __sieve(self):
prime = False
while not prime:
self.lastnum += 1
prime = True
for n in self.primes:
if self.lastnum % n == 0:
prime = False
break
if n>math.sqrt(self.lastnum):
prime = True
break
self.primes.append(self.lastnum)
return self.lastnum
# This class holds variable functions
class BaseVar(object):
_regexp = None
# the variable names may only contain [A-Za-z0-9 ].
allowedAlphabet = greenery.parse("[A-Za-z0-9 ]").fsm().alphabet
def _makeRegexp(self, varname):
# variable names must be infinite, so there must be at least one '*' or '+' in the varname
if not ('*' in varname or '+' in varname):
raise ValueError("Invalid varname regexp: /%s/ does not match an infinite string." % varname)
# create reduced fsm for matching
try:
fsm = greenery.parse(varname).fsm().reduce()
except Exception as e:
# throw something better than just an exception
raise ValueError("Invalid varname regexp: /%s/" % e.args[0])
# see if no invalid characters are used
if self.allowedAlphabet != (self.allowedAlphabet | fsm.alphabet):
raise ValueError("Invalid varname regexp: /%s/ matches dissalowed characters: [%s]." % (
varname, ''.join(fsm.alphabet - self.allowedAlphabet)))
# finally store the regexp
self._regexp = fsm.lego()
def matches(self,othervar):
if not self._regexp: self._makeRegexp(self.getName())
return self._regexp == othervar.getRegexp()
def getName(self): return NotImplemented()
def getRegexp(self):
if not self._regexp: self._makeRegexp(self.getName())
return self._regexp
# Parse Streams
# A ring of parse streams (the objects it contains must be parse streams)
class Ring(object):
def __init__(self, first):
self.streams = [first]
self.index = 0
def add(self, stream):
self.streams.insert(self.index+1, stream)
def current(self):
return self.streams[self.index]
def left(self):
self.current().add(' ') # to separate lexemes
if self.index <= 0: self.index = len(self.streams)
self.index -= 1
def right(self):
self.current().add(' ') # to separate lexemes
self.index += 1
if self.index >= len(self.streams): self.index = 0
def delete(self):
if len(self.streams) == 0:
die("{@-}, but there are no more parse streams left to delete.")
curstream = self.streams[self.index]
del self.streams[self.index]
self.index -= 1
curstream.finalize()
return curstream
def flush(self):
streams = []
while len(self.streams):
streams.append(self.delete())
return streams
class ParseStream(object):
def __init__(self):
self.data = ""
def finalize(self):
verbose("Parse stream finalized: " + self.data)
def add(self, data):
self.data += data
@staticmethod
def parseStreams(data):
try:
data = data.strip()
verbose("Separating parse streams...")
ring = Ring(ParseStream())
streams = []
i = 0
while i < len(data):
# check pragmas
if data[i:i+4] == '{@+}':
ring.add(ParseStream())
i += 4
elif data[i:i+4] == '{@>}':
ring.right()
i += 4
elif data[i:i+4] == '{@<}':
ring.left()
i += 4
elif data[i:i+4] == '{@-}':
streams.append(ring.delete())
i += 4
else:
ring.current().add(data[i])
i += 1
verbose("Deleting all active parse streams...")
streams += ring.flush()
return [stream.data.strip() for stream in streams]
except IndexError:
die("Extra data after deleting final parse stream.")
## expressions
class Exprs(object):
class Val(object): # holds a value + type
def __init__(self, type, value):
self.value = value
self.type = type
def __eq__(self, other):
if other == None: return False
if self.type != other.type:
if self.type in 'pi' and other.type in 'pi':
# prime and int may be compared
return self.value == other.value
else:
raise CodeError("Type mismatch, comparing %s (%s) to %s (%s)"
% (self.value, self.type, other.value, other.type))
if self.type == 'a':
# compare all inner values.
allSetVals = set(self.value.keys()) + set(other.value.keys())
for val in allSetVals:
if self[val] != other[val]: return False
return True
else:
return self.value == other.value
def copy(self):
if self.type != 'a':
return Exprs.Val(self.type, self.value)
else:
newval = Exprs.Val(self.type, {})
for setval in self.value:
newval[setval] = self[setval].copy()
return newval
def __getitem__(self, attr):
if self.type != 'a': raise CodeError("Type mismatch, attempt to subscript non-array")
if not attr.type in 'pi': raise CodeError("Type mismatch, array subscript must be integer")
if not attr.value in self.value: return Exprs.Val('i', 0)
return self.value[attr.value]
def __setitem__(self, attr, val):
if self.type != 'a': raise CodeError("Type mismatch, attempt to subscript non-array")
if not attr.type in 'pi': raise CodeError("Type mismatch, array subscript must be integer")
if not val.type in 'pi': raise CodeError("Type mismatch, array value must be integer")
self.value[attr.value] = Exprs.Val('i', val.value)
def __repr__(self):
return "Val<%s,%s>"%(self.type,str(self.value))
class Expr(object):
def eval(self,env): raise NotImplemented()
def vars(self): raise NotImplemented()
class BracedExpr(Expr):
def __init__(self, expr): self.expr = expr
def eval(self,env): return self.expr.eval(env)
def __repr__(self):
return '(.' + str(self.expr) + '.)'
def vars(self): return self.expr.vars()
class HashFn(Expr):
def __init__(self, name): self.name = name
def eval(self,env): return env.hashfn(self.name)
def __repr__(self): return '#'+self.name+'#'
def vars(self): return []
class Number(Expr):
def __init__(self, num): self.num = int(num)
def eval(self,env): return Exprs.Val('i', self.num)
def __repr__(self): return str(self.num)
def vars(self): return []
class Var(Expr, BaseVar):
def __init__(self, var):
self.var = var
#self._makeRegexp(var)
def eval(self,env):
x = env.lookup(self)
#debug("Var<%s> = %s"%(str(self), str(x)))
return x
def __repr__(self): return '/' + str(self.var) + '/'
def vars(self): return [self]
def getName(self): return self.var
class Assign(Expr):
def __init__(self, var, expr):
self.var = var
self.expr = expr
def eval(self,env):
val = self.expr.eval(env)
#debug("Assign<%s := %s>"%(str(self.var),str(val)))
env.assign(self.var, val)
return val
def __repr__(self): return str(self.var) + ' := ' + str(self.expr)
def vars(self): return [self.var] + self.expr.vars()
class ArrLookup(Expr):
def __init__(self, var, iexpr):
self.var = var
self.iexpr = iexpr
def eval(self,env):
ival = self.iexpr.eval(env)
#debug("Lookup<%s[%s]>"%(str(self.var),str(ival)))
return env.lookup(self.var, index = ival)
def __repr__(self): return (str(self.var)
+ '['
+ str(self.iexpr)
+ ']')
def vars(self): return [self.var] + self.iexpr.vars()
class ArrAssign(Expr):
def __init__(self, var, iexpr, newexpr):
self.var = var
self.iexpr = iexpr
self.newexpr = newexpr
def eval(self,env):
ival = self.iexpr.eval(env)
val = self.newexpr.eval(env)
#debug("Assign<%s[%s] := %s>"%(str(self.var),str(ival),str(val)))
env.assign(self.var, val, index = ival)
return val
def __repr__(self): return (str(self.var)
+ '['
+ str(self.iexpr)
+ '] := '
+ str(self.newexpr)
)
def vars(self): return [self.var] + self.iexpr.vars() + self.newexpr.vars()
class ArrCheck(Expr):
def __init__(self, var, iexpr):
self.var = var
self.iexpr = iexpr
def eval(self,env):
ival = self.iexpr.eval(env)
arrval = env.lookup(self.var, index = ival)
#debug("?<%s ? %s> (=%s)"%(str(self.var),str(ival),str(arrval)))
return Exprs.Val('c', ival == arrval)
def __repr__(self):
return (str(self.var) + '?' + str(self.iexpr))
def vars(self): return [self.var] + self.iexpr.vars()
class Minus(Expr):
def __init__(self, iexpr): self.iexpr = iexpr
def eval(self, env):
val = self.iexpr.eval(env)
#debug("Minus<%s>"%str(val))
if not val.type in 'pi':
raise CodeError("Type mismatch: 'minus' needs i or p, not %s"%val.type)
return Exprs.Val('i', -val.value)
def __repr__(self):
return "minus " + str(self.iexpr)
def vars(self): return self.iexpr.vars()
class Write(Expr):
def __init__(self, iexpr): self.iexpr = iexpr
def eval(self, env):
val = self.iexpr.eval(env)
#debug("Write<%s>"%str(val))
if not val.type in 'pi':
raise CodeError("Type mismatch: 'write' needs i or p, not %s"%val.type)
if 0 <= val.value < 0x110000:
#print(val.value)
sys.stdout.buffer.write(chr(val.value).encode('utf-8'))
sys.stdout.flush()
else:
raise CodeError("Attempt to write value (%x) outside of unicode range." % val.value)
return val
def __repr__(self):
return "write " + str(self.iexpr)
def vars(self): return self.iexpr.vars()
class Not(Expr):
def __init__(self, zexpr): self.zexpr = zexpr
def eval(self, env):
val = self.zexpr.eval(env)
#debug("Not<%s>"%str(val))
if not val.type == 'z':
raise CodeError("Type mismatch: 'not?' needs z, not %s"%val.type)
return Exprs.Val('b', not val.value)
def __repr__(self):
return 'not? ' + str(self.zexpr)
def vars(self): return self.zexpr.vars()
class If(Expr):
def __init__(self, bexpr): self.bexpr = bexpr
def eval(self, env):
val = self.bexpr.eval(env)
#debug("If<%s>"%str(val))
if not val.type == 'b':
raise CodeError("Type mismatch: 'if?' needs b, not %s"%val.type)
return Exprs.Val('c', val.value)
def __repr__(self): return 'if? ' + str(self.bexpr)
def vars(self): return self.bexpr.vars()
class Cvt(Expr):
def __init__(self, cexpr): self.cexpr = cexpr
def eval(self, env):
val = self.cexpr.eval(env)
#debug("Cvt<%s>"%str(val))
if not val.type == 'c':
raise CodeError("Type mismatch: 'cvt?' needs c, not %s"%val.type)
return Exprs.Val('t', val.value)
def __repr__(self): return 'cvt? ' + str(self.cexpr)
def vars(self): return self.cexpr.vars()
class To(Expr):
def __init__(self, texpr): self.texpr = texpr
def eval(self, env):
val = self.texpr.eval(env)
#debug("To<%s>"%str(val))
if not val.type == 't':
raise CodeError("Type mismatch: 'to?' needs t, not %s"%val.type)
return Exprs.Val('z', val.value)
def __repr__(self): return 'to? ' + str(self.texpr)
def vars(self): return self.texpr.vars()
class Prime(Expr):
def __init__(self, iexpr, tvar):
self.iexpr = iexpr
self.tvar = tvar
def eval(self, env):
val = self.iexpr.eval(env)
#debug("P?<%s>"%str(val))
if not val.type in 'pi':
raise CodeError("Type mismatch: 'P?' needs i or p, not %s"%val.type)
if env.isPrime(val.value):
return Exprs.Val('p', val.value)
else:
env.assign(self.tvar, Exprs.Val('t', 0))
return Exprs.Val('p', 2)
def __repr__(self): return 'P? ' + str(self.iexpr) + ' [' + str(self.tvar) + ']'
def vars(self): return self.iexpr.vars() + [self.tvar]
class MathOp(Expr):
def __init__(self, op, iexpr1, iexpr2):
self.op=op
self.iexpr1=iexpr1
self.iexpr2=iexpr2
def eval(self, env):
ival1 = self.iexpr1.eval(env)
ival2 = self.iexpr2.eval(env)
#debug("Math<%s %s %s>"%(str(ival1),self.op,str(ival2)))
if (not ival1.type in 'pi') or (not ival2.type in 'pi'):
raise CodeError("Type mismatch: %s needs i or p, not %s/%s" % (self.op, ival1.type, ival2.type))
newval = {'+': operator.add, '*': operator.mul}[self.op](ival1.value, ival2.value)
return Exprs.Val('i', newval)
def __repr__(self):
return str(self.iexpr1) + ' ' + self.op + ' ' + str(self.iexpr2)
def vars(self): return self.iexpr1.vars() + self.iexpr2.vars()
class ExistsDynast(Expr):
def __init__(self, iexpr): self.iexpr = iexpr
def eval(self, env):
ival = self.iexpr.eval(env)
#debug("Exists/Dynast<%s>"%str(ival))
if not ival.type in 'pi':
raise CodeError("Type mismatch: exists/dynast needs i or p, not %s" % ival.type)
return Exprs.Val('z', env.existsDynast(ival.value))
def __repr__(self):
return 'exists/dynast ' + str(self.iexpr)
def vars(self): return self.iexpr.vars()
class CopyDynast(Expr):
def __init__(self, iexpr, pexpr1, pexpr2):
self.iexpr=iexpr
self.pexpr1=pexpr1
self.pexpr2=pexpr2
def eval(self,env):
ival = self.iexpr.eval(env)
pval1 = self.pexpr1.eval(env)
pval2 = self.pexpr2.eval(env)
#debug("Copy/Dynast<%s,%s,%s>"%(str(ival),str(pval1),str(pval2)))
if (not ival.type in 'pi') or pval1.type!='p' or pval2.type!='p':
raise CodeError("Type mismatch: copy/dynast needs i,p,p not %s,%s,%s" %
(ival.type, pval1.type, pval2.type))
env.copyDynast(ival.value, pval1.value + pval2.value)
return Exprs.Val('i', ival.value)
def __repr__(self):
return 'copy/dynast ' + str(self.iexpr) + ', ' + str(self.pexpr1) + ', ' + str(self.pexpr2)
def vars(self): return self.iexpr.vars() + self.pexpr1.vars() + self.pexpr2.vars()
class CreateCountablyManyDynasts(Expr):
def __init__(self, iexpr1, iexpr2):
self.iexpr1 = iexpr1
self.iexpr2 = iexpr2
def eval(self,env):
ival1 = self.iexpr1.eval(env)
ival2 = self.iexpr2.eval(env)
#debug("Create/Countably/Many/Dynasts<%s,%s>"%(str(ival1),str(ival2)))
if (not ival1.type in 'pi') or (not ival2.type in 'pi'):
raise CodeError("Type mismatch: create/countably/many/dynasts needs i,i not %s,%s" %
(ival1.type, ival2.type))
env.createCountablyManyDynasts(ival1.value, ival2.value)
return ival1
def __repr__(self):
return 'create/countably/many/dynasts ' + str(self.iexpr1) + ', ' + str(self.iexpr2)
def vars(self): return self.iexpr1.vars() + self.iexpr2.vars()
class And(Expr):
def __init__(self, bexpr1, bexpr2):
self.bexpr1 = bexpr1
self.bexpr2 = bexpr2
def eval(self, env):
bval1 = self.bexpr1.eval(env)
bval2 = self.bexpr2.eval(env)
#debug("And<%s,%s>"%(str(bval1),str(bval2)))
if bval1.type!='b' or bval2.type!='b':
raise CodeError("Type mismatch: 'and' needs b,b not %s,%s"%(bval1.type,bval2.type))
return Exprs.Val('z', bval1.value and bval2.vale)
def __repr__(self):
return str(self.bexpr1) + ' and ' + str(self.bexpr2)
def vars(self): return self.bexpr1.vars() + self.bexpr2.vars()
class Or(Expr):
def __init__(self, cexpr1, cexpr2):
self.cexpr1 = cexpr1
self.cexpr2 = cexpr2
def eval(self, env):
cval1 = self.cexpr1.eval(env)
cval2 = self.cexpr2.eval(env)
#debug("Or<%s,%s>"%(str(cval1),str(cval2)))
if cval1.type!='c' or cval2.type!='c':
raise CodeError("Type mismatch: 'or' needs c,c not %s,%s"%(cval1.type,cval2.type))
return Exprs.Val('t', cval1.value or cval2.value)
def __repr__(self):
return str(self.cexpr1) + ' or ' + str(self.cexpr2)
def vars(self): return self.cexpr1.vars() + self.cexpr2.vars()
class Do(Expr):
def __init__(self, expr): self.expr = expr
def eval(self, env):
#debug("Do")
self.expr.eval(env)
return Exprs.Val('c', True)
def __repr__(self):
return 'do ' + str(self.expr)
def vars(self): return self.expr.vars()
class WimpThen(Expr):
def __init__(self, cexpr, expr):
self.cexpr = cexpr
self.expr = expr
def eval(self, env):
if (not env.wimpmode):
raise CodeError("'then' is a wimpmode instruction but wimpmode is not on")
val = self.cexpr.eval(env)
#debug("WimpThen<%s>"%str(val))
if (val.type != 'c'):
print("\x1b[1;7m>>\x1b[0m", "'then' takes a c-expr, and this wasn't (it was %s)."%val.type,
"However, you are a wimp so I will let it slide.")
return self.expr.eval(env)
def __repr__(self):
return str(self.cexpr) + ' then ' + str(self.expr)
def vars(self): return self.expr.vars()
class Then(Expr):
def __init__(self, cexpr, iexpr):
self.cexpr = cexpr
self.iexpr = iexpr
def eval(self, env):
cval = self.cexpr.eval(env)
#debug("Then<%s>"%str(cval))
if cval.type != 'c':
raise CodeError("',then' takes a c, not a %s" % cval.type)
if cval.value:
ival = self.iexpr.eval(env)
if not ival.type in 'pi':
raise CodeError("',then' takes an i, not a %s" % ival.type)
return Exprs.Val('i', ival.value)
else:
return Exprs.Val('i', 1 + int(random.random() * 1e6))
def __repr__(self):
return str(self.cexpr) + ' ,then ' + str(self.iexpr)
def vars(self): return self.cexpr.vars() + self.iexpr.vars()
class ForEach(Expr):
def __init__(self, var, iexpr1, iexpr2):
self.var = var
self.iexpr1 = iexpr1
self.iexpr2 = iexpr2
def eval(self, env):
ival1 = self.iexpr1.eval(env)
if not ival1.type in 'pi':
raise CodeError("foreach: 'below' value is not i.")
#debug("ForEach<%s>"%str(ival1))
primes = env.primesBelow(ival1.value)
ival2 = Exprs.Val('i', 0) # returned if no primes below ival1
for prime in primes:
env.assign(self.var, Exprs.Val('p', prime))
ival2 = self.iexpr2.eval(env).copy()
if not ival2.type in 'pi':
raise CodeError("foreach: body returned non-i. (%s)" % ival2.type)
return Exprs.Val('i', ival2.value) # cast to i (for if it was p)
def __repr__(self):
return 'for each prime ' + str(self.var) + ' below ' + str(self.iexpr1) + ' do ' + str(self.iexpr2)
def vars(self): return [self.var] + self.iexpr1.vars() + self.iexpr2.vars()
## parser for the actual code
class CodeParser(object):
# types
class OToken(object):
def __init__(self, obj):
self.contents = obj
def __repr__(self):
return self.__class__.__name__ + '<' + str(self.contents) + '>'
class Var(OToken, BaseVar):
def __init__(self, type, name):
self.contents=name
self.type=type
self._makeRegexp(name)
def getName(self): return self.contents
def __repr__(self):
return 'Var<%s,%s>'%(self.type,self.contents)
class VarDecl(OToken): pass
class Dynast(OToken):
def __init__(self, id, expr):
self.id=int(id);
self.contents=expr
def __repr__(self):
return 'Dynast<%d,%s>'%(self.id,str(self.contents))
class ParseStream(OToken):
def __init__(self, vars, dynast):
self.vars=vars
self.contents=dynast
def __repr__(self):
return 'Stream<%s,%s>'%(str(self.vars),str(self.dynast))
# parsers
# whitespace
wspace = Any(' \t\r\n')[:]
owspace = Any(' \t\r\n')[1:]
# variable name: /something/
varname = (~Literal('/')
& (Literal(r'\/') | (~Lookahead('/') & Any())) [1:]
& ~Literal('/') > (lambda x: ''.join(x))
)
# variable types: (i)nteger (p)rime (a)rray (b)ool (t)ruth bit(z) (c)ondition
vartype = Any('ipabtzc')
# variable
var = vartype & ~wspace & varname > args(Var)
# variable declaration
vardecl = (~Literal('VARIABLES')
& ~wspace
& ~Literal('ARE')
& ~wspace
& var[Drop(Literal(',') & wspace)]
& ~Literal('.')
) > VarDecl
## expressions
expri, expr1i, expr2i, expr3i, expr4i, expr5i, expr6i = [Delayed() for _ in range(7)]
exprp, expr1p, expr2p, expr3p, expr4p, expr5p, expr6p = [Delayed() for _ in range(7)]
exprb, expr1b, expr2b, expr3b, expr4b, expr5b, expr6b = [Delayed() for _ in range(7)]
exprt, expr1t, expr2t, expr3t, expr4t, expr5t, expr6t = [Delayed() for _ in range(7)]
exprz, expr1z, expr2z, expr3z, expr4z, expr5z, expr6z = [Delayed() for _ in range(7)]
exprc, expr1c, expr2c, expr3c, expr4c, expr5c, expr6c = [Delayed() for _ in range(7)]
expr = Delayed()
# hash function
hashfn = (~Literal('#')
& ((~Lookahead('#') & Any())[:]>(lambda x:''.join(x)))
& ~Literal('#')) > args(Exprs.HashFn)
# braces
openbrace = Literal('(')[1:] & Literal('.')
closebrace = Literal('.') & Literal(')')[1:]
bracedexp = (lambda openbrace,wspace,closebrace:
(lambda what: (~openbrace
& ~wspace
& what
& ~wspace
& ~closebrace) > args(Exprs.BracedExpr)))(openbrace,wspace,closebrace)
# constant expr
constant = hashfn | ( Integer() > args(Exprs.Number) )
# variable expr
varexp = varname > args(Exprs.Var)
#
minus = (~Literal("minus") & ~wspace & expri) > args(Exprs.Minus)
write = (~Literal("write") & ~wspace & expri) > args(Exprs.Write)
not_ = (~Literal("not?") & ~wspace & exprz) > args(Exprs.Not)
if_ = (~Literal("if?") & ~wspace & exprb) > args(Exprs.If)
cvt = (~Literal("cvt?") & ~wspace & exprc) > args(Exprs.Cvt)
to = (~Literal("to?") & ~wspace & exprt) > args(Exprs.To)
prime = (~Literal("P?") & ~wspace
& expri & ~wspace
& ~Literal('[') & ~wspace
& varexp & ~wspace
& ~Literal(']')) > args(Exprs.Prime)
exists = (~Literal("exists/dynast") & ~wspace & expri) > args(Exprs.ExistsDynast)
copy = (~Literal("copy/dynast") & ~wspace
& expri & ~wspace & ~Literal(",") & ~wspace
& exprp & ~wspace & ~Literal(",") & ~wspace
& exprp & ~wspace) > args(Exprs.CopyDynast)
create = (~Literal("create/countably/many/dynasts") & ~wspace
& expri & ~wspace & ~Literal(",") & ~wspace
& expri & ~wspace) > args(Exprs.CreateCountablyManyDynasts)
#do = lambda what: (~Literal("do") & ~wspace & what) > args(Exprs.Do)
do = (~Literal("do") & ~wspace & expr) > args(Exprs.Do)
foreach = (
~(Literal("for")&wspace&Literal("each")&wspace&Literal("prime")&wspace)
& varexp & ~wspace
& ~Literal("below") & ~wspace
& expri & ~wspace
& ~Literal("do") & ~wspace
& expri) > args(Exprs.ForEach)
# array lookup
arrlookup = (varexp
& ~wspace
& ~Literal('[')
& ~wspace
& expri
& ~wspace
& ~Literal(']')
) > (lambda x: Exprs.ArrLookup(x[0], x[1]))
#prim = foreach|do|create|copy|exists|prime|to|cvt|if_|not_|write|minus|varexp|constant|bracedexp
primp = varexp|bracedexp(exprz)|prime
primi = arrlookup|primp|bracedexp(expri)|constant|minus|write|copy|create|foreach
primb = varexp|bracedexp(exprb)|not_
primt = varexp|bracedexp(exprt)|cvt
primz = varexp|bracedexp(exprz)|to|exists
primc = varexp|bracedexp(exprc)|do|if_
# assignment
#assign = (lambda varexp,wspace:
# (lambda what: (varexp
# & ~wspace
# & ~Literal(':=')
# & ~wspace
# & what) > (lambda x: Exprs.Assign(x[0], x[1]))))(varexp,wspace)
assign = (varexp & ~wspace & ~Literal(':=') & ~wspace & expr) > (lambda x: Exprs.Assign(x[0], x[1]))
# array assign
arrassign = (varexp & ~wspace
& ~Literal('[') & ~wspace
& expri & ~wspace
& ~Literal(']') & ~wspace
& ~Literal(':=') & ~wspace
& expri) > (lambda x: Exprs.ArrAssign(x[0], x[1], x[2]))
#expr6 += arrassign | arrlookup | assign | prim
expr6p += assign | primp
expr6i += assign | arrassign | arrlookup | expr6p | primi
expr6b += assign | primb
expr6t += assign | primt
expr6z += assign | primz
expr6c += assign | primc
arrcheck = (varexp & ~wspace & ~Literal("?") & ~wspace & expr6i) > args(Exprs.ArrCheck)
expr5p = expr6p
expr5i = expr6i
expr5b = expr6b
expr5t = expr6t
expr5z = expr6z
expr5c += arrcheck | expr6c
multiply = (expr5i & ~wspace & ~Literal("*") & ~wspace & expr5i) > (lambda x: Exprs.MathOp("*", *x))
expr4p = expr5p
expr4i += multiply | expr5i
expr4b = expr5b
expr4t = expr5t
expr4z = expr5z
expr4c = expr5c
add = (expr4i & ~wspace & ~Literal("+") & ~wspace & expr4i) > (lambda x: Exprs.MathOp("+", *x))
expr3p = expr4p
expr3i += add | expr4i
expr3b = expr4b
expr3t = expr4t
expr3z = expr4z
expr3c = expr4c
and_ = (expr3b & ~wspace & ~Literal("and") & ~wspace & expr3b) > args(Exprs.And)
expr2p = expr3p
expr2i = expr3i
expr2b = expr3b
expr2t = expr3t
expr2z += and_ | expr3z
expr2c = expr3c
or_ = (expr2c & ~wspace & ~Literal("or") & ~wspace & expr2c) > args(Exprs.Or)
expr1p = expr2p
expr1i = expr2i
expr1b = expr2b
expr1t += or_ | expr2t
expr1z = expr2z
expr1c = expr2c
wimpthen = (lambda expr1c,wspace:
(lambda what: (expr1c
& ~wspace
& ~Literal("then")
& ~wspace
& what) > args(Exprs.WimpThen)))(expr1c,wspace)
then = (expr1c & ~wspace & ~Literal(",then") & ~wspace & expri) > args(Exprs.Then)
#wimpthen.config.left_memoize()
#then.config.left_memoize()
#expr += wimpthen | then | expr1
exprp += wimpthen(exprp) | expr1p
expri += wimpthen(expri) | then | expr1i
exprb += wimpthen(exprb) | expr1b
exprt += wimpthen(exprt) | expr1t
exprz += wimpthen(exprz) | expr1z
exprc += wimpthen(exprc) | expr1c
expr += expri | exprp | exprc | exprb | exprt | exprz
expr.config.left_memoize()
fullexpr = ~wspace & expr & ~wspace
###
dynast = (~wspace & ~Literal("dynast")
& ~wspace & ~Literal("(")
& ~wspace & Integer()
& ~wspace & ~Literal(")")
& ~wspace & ~Literal("<->")
& ~wspace & fullexpr) > args(Dynast)
parsestream = (~wspace & Optional(vardecl & ~wspace) & Optional(dynast))
# parse a parse stream
@staticmethod
def parse(code):
CodeParser.fibonacci_check(code)
debug("Parsing: " + code)
return CodeParser.parsestream.parse(code)
# check fibonacci indentation
@staticmethod
def fibonacci_check(code):
# remove the keywords with slashes in them
code = (code
. replace('exists/dynast', '')
. replace('create/countably/many/dynasts', '')
. replace('copy/dynast', ''))
# remove the variables (which might contain dots)
acc = []
i = 0
invar = False
while i < len(code):
if code[i]=='\\': i+=1; continue
if code[i]=='/': invar = not invar
if not invar and not code[i] == '/': acc.append(code[i])
i += 1
debug("Removed slashes: " + ''.join(acc))
# make a list of consecutive braces, and get their lengths
# this should be [fibonacci, 0, reverse fibonacci]
removed = ''.join(x for x in acc if x in '(.)')
# remove the first dot if there's a variable declaration
if 'VARIABLES' in code: removed=removed[1:]
# remove the ()s from dynast if they're there
if 'dynast' in code: removed=removed[2:]
braces = removed.split('.')
# split the places where braces meet
brace_split = []
for x in braces:
if not x: continue
if ')(' in x:
splitplace = 1 + x.index(')(')
brace_split.append(x[:splitplace])
brace_split.append(x[splitplace:])
else:
brace_split.append(x)
debug("Split braces: " + str(brace_split))
# check fibonacci
fibonacci = [1,1]
level = 0
num = 0
for x in brace_split:
num += 1
if ')' in x: level -= 1
# generate more fibonacci numbers if needed
while level >= len(fibonacci):
fibonacci.append(sum(fibonacci[-2:]))
debug(str(level) + ' ' + str(fibonacci[level]) + ' ' + x + ' ' + str(fibonacci))
# level ok?
if len(x) != fibonacci[level]:
raise ValueError(('braces do not match fibonacci at %d%s group in dynast. found %d, should be %d'
)% (num, ordsuffix(num), len(x), fibonacci[level]))
# next level
if '(' in x: level += 1
# base class for var holder
class VarHolder(object):
class Var(BaseVar):
defaultValues = {'i': 0, 'p': 2, 'a': None, 'b': 0, 't': 0, 'z': 0, 'c': 0}
def __init__(self, varexp):
self._regexp = varexp.getRegexp()
self.name = varexp.getName()
self.type = varexp.type
if isinstance(varexp, VarHolder.Var):
self.__value = varexp.__value.copy()
else:
defaultval = self.defaultValues[self.type]
if defaultval==None: defaultval={}
self.__value = Exprs.Val(self.type, defaultval)
def getName(self):
return self.name
def get(self):
return self.__value
def set(self, value):
if (self.type != value.type) and not (self.type == 'i' and value.type == 'p'):
raise CodeError("Type error: cannot assign %s value to %s variable" % (self.type, value.type))
if self.type == 'a':
# arrays need to be copied
self.__value = value.copy()
else:
self.__value = value
def __init__(self, varexps):
self.vars = [VarHolder.Var(x) for x in varexps]
self.matching = {}
def __getitem__(self, attr):
if not isinstance(attr, BaseVar):
raise TypeError("attr must be basevar")
if id(attr) in self.matching:
return self.matching[id(attr)]
else:
for v in self.vars:
if v.matches(attr):
self.matching[id(attr)]=v
return v
raise KeyError("There is no variable named /%s/" % attr.getName())
# holds a dynast + associated vars
class Dynast(VarHolder):
def __init__(self, number, vars, expr):
super(Dynast, self).__init__(vars)
self.number = number
self.expr = expr
def copy(self, newnumber):
return Dynast(newnumber, self.vars, self.expr)
def run(self, env):
self.expr.eval(env)
def __repr__(self):
return '<%d: %s>' % (self.number,self.expr)
# the environment, also holds global vars
class Environment(VarHolder):
def __init__(self, globalvars, dynasts):
super(Environment, self).__init__(globalvars)
self.dynasts = {}
for dynast in dynasts:
debug("Dynast %d: %s" % (dynast.number, str(dynast.expr)))
self.dynasts[dynast.number] = dynast
debug(str(self.dynasts))
self.infiniteDynasts = None
self.infiniteDynastsBegin = 0
self.primes = Primes()
# check for wimpmode
wimpvar = CodeParser.Var("i", "am *a *wimp")
self.wimpmode = False
for var in globalvars:
if var.type == 'i' and var.matches(wimpvar):
self.wimpmode = True
break
verbose("Wimpmode is %s." % ["OFF", "ON"][self.wimpmode])
# activate the dynast with the lowest number
self.activeDynast = self.dynasts[min(self.dynasts.keys())]
def createCountablyManyDynasts(self, dynast, begin):
begin += 1 + begin % 2 # first odd integer greater than 'begin'
verbose("Creating countably many dynasts from dynast %d starting at %d." % (dynast, begin))
# check if there are already infinitely many dynasts
if self.infiniteDynasts:
verbose("Exiting: dynasts already exist on the uneven numbers.")
sys.exit(0)
# check if the infinite dynasts conflict with a previously existant dynast
for dyn in self.dynasts:
if dyn >= begin and dyn % 2:
verbose("Exiting: dynast %d already exists." % dyn)
sys.exit(0)
# set the infinite dynast
self.infiniteDynasts = self.dynasts[dynast]
self.infiniteDynastsBegin = begin
debug("Dynast expr: %s" % str(self.infiniteDynasts.expr))
self.dynasts[begin] = self.infiniteDynasts.copy(begin)
def existsDynast(self, number):
if self.infiniteDynasts and number >= self.infiniteDynastsBegin and number % 2: return True
return number in self.dynasts
def getDynast(self, number):
debug("Retrieving dynast %d" % number)
if number in self.dynasts: return self.dynasts[number]
debug("Dynast not in dynast list <%d,%d,%d,%d>"%(
(self.infiniteDynasts != None), number, self.infiniteDynastsBegin, number%2))
if self.infiniteDynasts and number >= self.infiniteDynastsBegin and number % 2:
debug("Copying dynast %d" % number)
newdynast = self.infiniteDynasts.copy(number)
self.dynasts[number] = newdynast
return newdynast
verbose("Exiting: attempting to access nonexistant dynast %d." % number)
sys.exit(0)
def primesBelow(self, number):
return self.primes.below(number)
def copyDynast(self, old, new):
verbose("Copying dynast %d to %d" % (old, new))
if not self.existsDynast(old):
raise CodeError("Cannot copy dynast %d: dynast does not exist." % old)
if self.existsDynast(new):
verbose("Exiting: dynast %d already exists." % new)
sys.exit(0)
self.dynasts[new] = self.dynasts[old].copy(new)
def isPrime(self, number):
return self.primes.isPrime(number)
def lookup(self, varname, index=None):
try: var = self.activeDynast[varname]
except KeyError: var = self[varname]
value = var.get()
if index != None:
return value[index]
else:
return value
def assign(self, varname, value, index=None):
try: var = self.activeDynast[varname]
except KeyError: var = self[varname]
if index == None:
var.set(value) # set whole variable
else:
# set var index
var.get()[index] = value
def hashfn(self, hashfn):
if hashfn == 'myself':
return Exprs.Val('i', self.activeDynast.number)
elif hashfn == 'read':
char = sys.stdin.read(1)
if not char:
num = -1 # EOF
else:
num = ord(char)
return Exprs.Val('i', num)
else:
raise CodeError("No such function: #%s%#" % hashfn)
def run(self):
while True:
debug("Current expr: " + str(self.activeDynast.expr))
self.activeDynast.run(self)
self.activeDynast = self.getDynast(self.activeDynast.number + 1)
# interpreter
class Interpreter(object):
def __init__(self, code):
# parse the code
try:
streams = ParseStream.parseStreams(code)
verbose("Parsing streams...")
parsed = [CodeParser.parse(stream) for stream in streams]
except RuntimeError as e:
die("Parse error: " + str(e))
verbose("Getting vars and dynasts from streams...")
globalvars = []
dynasts = []
for stream in parsed:
if any(isinstance(x, CodeParser.Dynast) for x in stream):
# this is a dynast
if len(stream) == 2:
# with local vars
vars = stream[0].contents
num = stream[1].id
expr = stream[1].contents
dynasts.append(Dynast(num, vars, expr))
elif len(stream) == 1:
num = stream[0].id
expr = stream[0].contents
dynasts.append(Dynast(num, [], expr))
else:
raise RuntimeError("impossible situation: stream is of wrong length")
else:
# these are global vars
vars = stream[0].contents
globalvars += vars
# create the environment
self.environment = Environment(globalvars, dynasts)
# if we're not in wimpmode, check if a variable name is reused literally
if not self.environment.wimpmode:
verbose("Checking for literally repeated variables...")
vardefs = []
for var in globalvars:
if var.getName() in vardefs:
die("reused variable name while not in wimpmode: /%s/" % var.getName())
vardefs.append(var.getName())
for dynast in dynasts:
for var in dynast.expr.vars():
if var.getName() in vardefs:
die("reused variable name while not in wimpmode: /%s/" % var.getName())
vardefs.append(var.getName())
def run(self): self.environment.run()
def main():
global VERBOSE, DEBUG
parser = argparse.ArgumentParser(description='Oozlybub & Murphy interpreter')
parser.add_argument('-v', action='store_const', const=True, default=False, help='Verbose output')
parser.add_argument('-d', action='store_const', const=True, default=False, help='Show debug messages')
parser.add_argument('program', type=argparse.FileType('r'), nargs=1, help='Source code file')
args = parser.parse_args()
DEBUG=args.d
VERBOSE=args.v
try:
Interpreter(args.program[0].read()).run()
except Exception as e:
raise e
die(str(e))
if __name__ == '__main__': main()