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 display(v):
  if type(v) != tuple:
    print(v, end = "")
  elif v[0] == "function":
    print(v, end = "")
  elif v[0] == "nil":
    print("nil", end = "")
  elif v[0] == "conscell":
    print("(", end = "")
    display(v[1])
    displayrest(v[2])
  else:
    print("[[[[bad: ", v, "]]]]", sep = "", end = "")

def displayrest(v):
  while True:
    ok = False
    if type(v) == tuple:
      if v[0] == "nil":
        print(")", end = "")
        return
      if v[0] == "conscell":
        print(" ", end = "")
        display(v[1])
        v = v[2]
        ok = True
    if not ok:
      print(" ~ ", end = "")
      display(v)
      print(")", end = "")
      return

def eval(form):

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

  if form == "nil":
    return ("nil", )

  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 == "cons":
      return ("conscell", eval(form[1]), eval(form[2]))

    if op == "car":
      v = eval(form[1])
      if type(v) != tuple or v[0] != "conscell":
        raise ValueError("car of " + str(v))
      return v[1]

    if op == "cdr":
      v = eval(form[1])
      if type(v) != tuple or v[0] != "conscell":
        raise ValueError("cdr of " + str(v))
      return v[2]

    if op == "list":
      v = ("nil", )
      for i in range(len(form) - 1, 0, -1):
        v = ("conscell", eval(form[i]), v)
      return v

    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 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

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

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", "between", ("a", "b"),
                        ("if", (">", "a", "b"),
                               "nil",
                               ("cons", "a", ("between", ("+", "a", 1), "b")))))       

eval(("def", "len", ("s", ),
                    ("if", ("==", "s", "nil"), 
                           0,
                           ("+", 1, ("len", ("cdr", "s"))))))   

eval(("def", "irev", ("s", "t"),
                     ("if", ("==", "s", "nil"),
                            "t",
                            ("irev", ("cdr", "s"),
                                     ("cons", ("car", "s"), "t")))))

eval(("def", "reverse", ("s"), ("irev", "s", "nil")))

eval(("def", "insert", ("t", "x"), 
                       ("if", ("==", "t", "nil"),
                              ("list", "nil", "x", "nil"),            
                              ("if", ("<", "x", ("car", ("cdr", "t"))),
                                     ("list", ("insert", ("car", "t"), "x"), 
                                              ("car", ("cdr", "t")), 
                                              ("car", ("cdr", ("cdr", "t")))),     
                                     ("list", ("car", "t"), 
                                              ("car", ("cdr", "t")), 
                                              ("insert", ("car", ("cdr", ("cdr", "t"))), "x"))))))   

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)))))