combinator_conversion.py

#!/usr/bin/env python

class Application(object):
  def __init__(self, lhs, rhs):
    self.lhs = lhs
    self.rhs = rhs

  def __repr__(self):
    if isinstance(self.rhs, Variable):
      return str(self.lhs) + str(self.rhs)
    else:
      return str(self.lhs) + '(' + str(self.rhs) + ')'

  def __contains__(self, char):
    return (char in self.lhs) or (char in self.rhs)

class Variable(object):
  def __eq__(self, rhs):
    if isinstance(rhs, Variable) and rhs.char == self.char:
      return True
    else:
      return False

  def __init__(self, char):
    self.char = char

  def __repr__(self):
    return self.char

  def __contains__(self, char):
    return self.char == char

def parse(s):
  """Parse string."""
  result = None
  while True:
    if len(s) == 0:
      return result, s
    elif s[0] == ')':
      return result, s
    else:
      if s[0] == '(':
        rhs, s = parse(s[1:len(s)])
      else:
        rhs = Variable(s[0])
      s = s[1:len(s)]

      if result:
        result = Application(result, rhs)
      else:
        result = rhs

def elimination(expr, alpha):
  """Perform alpha-elimination."""
  if isinstance(expr, Variable) and expr.char == alpha:
    return Variable('I')
  elif alpha not in expr:
    return Application(Variable('K'), expr)
  elif isinstance(expr, Application) and \
        isinstance(expr.rhs, Variable) and \
        expr.rhs.char == alpha and \
        alpha not in expr.lhs:
    return expr.lhs
  else:
    Y = elimination(expr.lhs, alpha)
    Z = elimination(expr.rhs, alpha)
    return Application(Application(Variable('S'), Y), Z)

def simulation(expr):
  """Simulate SKI combinator calculus."""
  def list_to_expr(l):
    """Convert list to expression."""
    top = l[-1]
    l = l[0:-1]
    if isinstance(top, list):
      top = list_to_expr(top)
    ret = top
    while len(l) > 0:
      top = l[-1]
      l = l[0:-1]
      if isinstance(top, list):
        top = list_to_expr(top)
      ret = Application(ret, top)
    return ret
  def expr_to_list(expr):
    """Convert expression to list."""
    if isinstance(expr, Variable):
      return [expr]
    elif isinstance(expr.rhs, Variable):
      return [expr.rhs] + expr_to_list(expr.lhs)
    else:
      return [expr_to_list(expr.rhs)] + expr_to_list(expr.lhs)
  def one_step(l):
    """Do one step evaluation."""
    if len(l) == 0:
      return l
    else:
      operator = l[-1]
      l = l[0:-1]
      if isinstance(operator, list):
        operator = one_step(operator)
        if len(operator) == 1:
          return l + operator
        else:
          return l + [operator]
      elif operator.char == 'S':
        x = l[-1]
        y = l[-2]
        z = l[-3]
        if not isinstance(x, list):
          x = [x]
        if not isinstance(y, list):
          y = [y]
        if not isinstance(z, list):
          z = [z]
        return l[0:-3] + [z + y] + z + x
      elif operator.char == 'K':
        x = l[-1]
        y = l[-2]
        if not isinstance(x, list):
          x = [x]
        return l[0:-2] + x
      elif operator.char == 'I':
        x = l[-1]
        if not isinstance(x, list):
          x = [x]
        return l[0:-1] + x
      else:
        return one_step(l) + [operator]
  print "= " + str(expr)
  l = expr_to_list(expr)
  reduced = one_step(l)
  while l != reduced:
    print "= " + str(list_to_expr(reduced))
    l = reduced
    reduced = one_step(l)
  return list_to_expr(reduced)

import sys
def main():
  if len(sys.argv) != 2:
    print "Please specify an argument like \"xy(yz)\""
    sys.exit(1)
  target = sys.argv[1]
  arguments = list(set(target.replace('(','').replace(')','')))

  arguments.sort(reverse=True)
  result, s = parse(target)
  for alpha in arguments:
    result = elimination(result, alpha)

  arguments.sort()
  for alpha in arguments:
    result = Application(result, Variable(alpha))

  print "  " + target
  print "= A" + ''.join(arguments)
  simulation(result)

if __name__ == '__main__':
  main()