#!/usr/bin/python
 
fail = "?" # need a marker for fail
 
#############################################
# how to define one variable
 
def var(x):
  "Match needs variables to mark what can be matched."
  return isinstance(x,str) and x and x[0] == "?"
 
def _var():
  """
  should print 
  True
  False
  """
  print(var("?gg"))
  print(var(22))
 
_var()
 
#############################################
# how to define a list of bindongs
 
def assoc(x,pairs):
  "Finding one item in a list of pairs."
  for a,b in pairs:
    if a==x:
      return b
  return fail
 
def assocp(x,pairs):
  "True if the pairs contains an association"
  return not assoc(x,pairs) == fail
 
def binding(x,pairs) :
  "Recursive chase of associations."
  y = assoc(x,pairs)
  if y == fail: 
    return fail
  else:
    if var(y):
      return binding(y,pairs)
    else:
      return y
  
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,
     - note that this recursive call would look like this:
      
             match(binding(x,pairs),y,pairs)
 
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.
"""
 
 
def _match():
  # 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")])