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":
      r = reader()
      return r.read()

    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():
  while True:
    r = reader()
    f = r.read()
    v = eval(f)
    display(v)
    print()

class getter:
  def __init__(self):
    self.line = ""
    self.pos = 0
    self.len = 0

  def getch(self):
    if self.line == None:
      return "<END>"
    if self.pos < self.len:
      r = self.line[self.pos]
      self.pos += 1
      return r
    self.line = input("> ")
    self.pos = 0
    self.len = len(self.line)
    if self.len == 0:
      self.line = None
      return "<END>"
    return " "

  def ungetch(self):
    if self.pos > 0:
      self.pos -= 1

  def get(self):
    c = self.getch()
    while c == " ":
      c = self.getch()
    if c == "<END>":
      return c
    if c == "(" or c == ")":
      return c
    if c.isalpha():
      s = ""
      while c.isalnum() or c == "_":
        s += c
        c = self.getch()
      self.ungetch()
      return s
    if c.isdecimal():
      n = 0
      while c.isdecimal():
        n = n * 10 + ord(c) - ord("0")
        c = self.getch()
      self.ungetch()
      return n
    s = ""
    while c != " " and c != "(" and c != ")":
      s += c;
      c = self.getch()
    self.ungetch()
    if s == "true":
      return True
    if s == "false":
      return False
    return s

class reader:
  def __init__(self):
    self.g = getter()

  def read(self, bracok = False):
    s = self.g.get()
    if s == ")" and not bracok:
      raise ValueException(") in wrong place")
    if s == "(":
      return self.readlist()
    return s

  def readlist(self):
    items = []
    while True:
      it = self.read(True)
      if it == ")":
        return tuple(items)
      if it == "<END>":
        raise ValueError("unmatched (")
      items.append(it)

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

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