def var(x):
  return isinstance(x,str) and x and x[0] == "?"

fail = "?"

def assoc(x,pairs):
  for a,b in pairs:
    if a==x:
      return b
  return fail

def assocp(x,pairs):
  return not assoc(x,pairs) == fail

def binding(x,pairs,level=0) :
  y = assoc(x,pairs)
  if y == fail: 
    return fail
  else:
    if var(y):
      return binding(pairs[x],pairs,level+1)
    else:
      return y

#########################################################
# detect if something is a "variable" (starts with a "?")
def _var():
  """
  should print 
  True
  False
  """
  print(var("?gg"))
  print(var(22))

_var()

######################################################
# chasing bindings in an environment 


def _binding():
  """
  should print 
  ?x 10
  ?y 100
  ?z 100
  ?w ?
  10 ?
  """
  mypairs= {"?x":10,
          "?y":"?z",
          "?z":100
          }
  for goal in ["?x","?y","?z","?w",10]:
    print goal, binding(goal,mypairs)

_binding()

###################################################
# matching

"""
1. If x and y are eql they match; otherwise,

2. If x is a variable that has a binding, 
   they match if it matches y;otherwise,

3. If y is a variable that has a binding, 
   they match if it matches x;otherwise,

4. If x is a variable (without a binding), 
   they match and thereby establish a binding for it; otherwise,

5. If y is a variable (without a binding), 
   they match and thereby establish a binding for it; otherwise,

6. They match if they are both tuples, and the heads match, 
   and the rest match with the bindings generated thereby.
"""

# returns true
print 0,match("p","p")

#returns true
print 1,match(("a","b","c"),
              ("a","b","c"))

# returns true and updates the ?x binding
print 2,match(("a","b","?x"),
              ("a","b","c"))

# returns true and updates the ?x binding
print 3,match(("a","b", "c"),
              ("a","b","?x"))

# fails
print 4,match(("a","b","c"),
              ("a","b","d"))

# returns true and updates the ?x and ?y binding
print 5,match(("p","a" , "b","c","a"),
              ("p","?x","?y","c","?x"))

# returns fail since we try to bind ?x to two things
print 6,match(("p","a" , "b","c","d"),
              ("p","?x","?y","c","?x"))

# returns true and updates the ?x and ?y binding and ?y binds to ?x
print 7,match(("p","?x","b","?y","a"),
              ("p","?y","b","c" ,"a"))

# returns true and no env updates
print 8,match(("p", "?x"),
              ("p", "?x"))

# say what?
print 9,match(("p","?v" ,"b" ,"d",("?z", "?z")),
              ("p","a","?w","c","?y", ("e", "e")),
              [("?z","e"),
               ("?y","d"),
               ("?x","c"),
               ("?v","a"),
               ("?w","b")])