import functools, operator

arith = { "+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv,
          "%": operator.mod, "^": operator.pow, 
          "and": operator.and_, "or": operator.or_, "xor": operator.xor }
compa = { "==": operator.eq, "<": operator.lt, ">": operator.gt,
          "!=": operator.ne, "<=": operator.le, ">=": operator.ge }

mem = {}

def eval(form):

  if type(form) in (int, float, bool):
    return form

  if type(form) == str:
    if form in mem:
      return mem[form]
    else:
      raise ValueError("unknown variable " + form)

  if type(form) == tuple:
    if form == ():
      raise ValueError("empty")
    op = form[0]

    if op in arith:
      return functools.reduce(arith[op], (eval(f) for f in form[1:]))

    if op in compa:
      return compa[op](eval(form[1]), eval(form[2]))

    if op == "neg":
      v = eval(form[1])
      if type(v) == bool:
        return not v
      if type(v) == int:
        return - v
      raise ValueError("wrong type for neg")        

    if op == "set":
      mem[form[1]] = eval(form[2])
      return mem[form[1]]

    if op == "seq":
      v = 0
      for f in form[1:]:
        v = eval(f)
      return v

    if op == "print":
      v = eval(form[1])
      display(v)
      print()
      return v

    if op == "if":
      if eval(form[1]):
        return eval(form[2])
      else:
        return eval(form[3])

    if op == "read":
      return readvalue()

    if op == "def":
      mem[form[1]] = ("function", form[2], form[3])
      return 0

    if op in mem:
      func = mem[op]
      if type(func) != tuple or func[0] != "function":
        raise ValueError("not a function: " + op)
      if len(func[1]) != len(form) - 1:
        raise ValueError("wrong parameters for " + op)
      saved = { (var, mem[var]) for var in func[1] if var in mem }
      notsaved = [ var for var in func[1] if var not in mem ]
      vals = [eval(f) for f in form[1:]]
      for i in range(0, len(func[1])):
        mem[func[1][i]] = vals[i]
      v = eval(func[2])
      for var in notsaved:
        del mem[var]
      for (var, val) in saved:
        mem[var] = val
      return v

  raise ValueError("unknown " + str(form))

def run(form):
  try:
    v = eval(form)
    display(v)
    print()
  except BaseException as e:
    print(e)
    print(e.args)
    raise

def readvalue():
  while True:
    x = input("? ")
    if x:      
      break
  if x == "true":
    return True
  if x == "false":
    return False
  if x.isdecimal():
    return int(x)
  return x

f1 = ("*", 3, 4, 5)
f2 = ("*", ("+", 1, 2), ("*", 2, 2), ("+", 1, ("*", 2, 2)))
f3 = ("<", f1, f2)
f4 = ("set", "x", f2)
f5 = ("seq", ("set", "x", 17), ("set", "y", 3), ("print", "x"), ("*", "x", "y"))
f6 = ("def", "f", ("x", "y"), ("*", ("+", "x", 1), ("+", "y", 1)))

eval(("def", "factorial", ("n", ), 
                          ("if", ("==", "n", 0), 1, ("*", "n", ("factorial", ("-", "n", 1))))))

eval(("def", "isdivisor", ("n", "d"), ("==", ("%", "n", "d"), 0)))

eval(("def", "hasdivisorleq", ("n", "maxd"), 
                              ("if", ("<=", "maxd", 1),
                                     False,
                                     ("if", ("isdivisor", "n", "maxd"),
                                            True,
                                            ("hasdivisorleq", "n",
                                                              ("-", "maxd", 1))))))

eval(("def", "isprime", ("n", ),
                        ("neg", ("hasdivisorleq", "n", ("-", "n", 1)))))