Records and pattern matching

##record.py
##
##"record" is an implementation of a simple record
##type constructor for records with labeled fields.
##The record types will be subclasses of "tuple".
##
##"match" is a pattern matcher for matching patterns
##of complex record structures to a record object and
##binding elements in the matched structure to parameters
##in a handler function.
##
##Example:
##from record import record, match, sym
##tree = record(sym.tree, sym.left, sym.right)
##def flatten(t):
##    return (match(t).
##    case(tree(sym.left, sym.right),
##          lambda left, right: flatten(left)+flatten(right)).
##    case(sym.leaf, lambda leaf: [leaf])
##    ())
##
##t = tree(tree(1, tree(2, 4)), 3)
##print flatten(t)
##prints:
##[1, 2, 4, 3]


class symbol(object):
    """
    Symbols for place holders for pattern matching
    """
    syms = {}
    
    def __new__(kls, name):
        if name in symbol.syms:
            return symbol.syms[name]
        else:
            o = object.__new__(kls)
            symbol.syms[name] = o
            return o
        
    def __init__(self, name):
        self.name = name

    def __str__(self):
        return self.name

    def __repr__(self):
        return self.name

class _symbol(object):
    def __getattribute__(self, name):
        return symbol(name)

sym = _symbol()

def record(name, *labels):
    """
    Construct a record type. Records are subclasses of tuple:
    <new record class> = record(name, label1, ...)
    
    Usage:
    user = record(sym.user, sym.name, sym.password)
    ram = user(name="ram", password="*****")
    shyam = user("shyam", "*")
    print "ram's name = ", ram.name
    name, password = ram
    """
    labels = [str(label) for label in labels]
    name = str(name)
    def new(kls, *labels):
        return tuple.__new__(kls, labels)
    def __str__(self):
        return "%s(%s)" % (name,
                           ", ".join(("%s=%s"%(label, val)
                                      for label, val
                                      in zip(labels, self))))
    d = {"__new__":new,
         "__str__":__str__,
         "__repr__":__str__}
    exec ("""def __init__(self, %s):pass""" %
          ", ".join(labels)) in d
    
    for i in range(len(labels)):
        d[labels[i]] = (lambda i:
                        property(lambda self:
                                 self[i]))(i)

    return type(name, (tuple,), d)

def _combine(obj, pattern):
    if isinstance(pattern, symbol):
        return [(str(pattern), obj)]
    elif isinstance(pattern, tuple) and type(obj)==type(pattern):
        return sum((_combine(o, p) for o, p in zip(obj, pattern)), [])
    elif pattern == obj:
        return []
    else:
        return False

class MatchFailed(Exception):pass       

class match(object):
    """
    Match the given object and do some actions
    """
    def __init__(self, obj):
        self.obj = obj
        self.matchers = []
        def onDefault(obj):
            raise MatchFailed
        self._onDefault = onDefault
        
    def case(self, pattern, onMatch):
        """
        Add a match case.
        
        The match case matches a pattern to an action
        """
        self.matchers.append((pattern, onMatch))
        return self

    def default(self, onDefault):
        """
        Set a default handler if all matches fail.
        
        The handler must accept one parameter which
        will be the match object.
        """
        self._onDefault = onDefault

    def __call__(self):
        """
        Execute the match
        """
        for pattern, onMatch in self.matchers:
            c = _combine(self.obj, pattern)
            if c!=False:
                return onMatch(**dict(c))
        self._onDefault(self.obj)