import sys

_typeDefinitions = {}

def _variantsInit(self, *args, **kwargs):
    i = 0
    for arg in _typeDefinitions[self.__class__.__name__.split('.')[-1]]:
        if kwargs.has_key(arg):
            self.__dict__[arg] = kwargs[arg]
            del kwargs[arg]
        else:
            self.__dict__[arg] = args[i]
            i += 1

class _VariantMcs(type):
    def __new__(mcs, name, bases, dct):
        if 'variants' in dct:
            if type(bases) == type(""): bases = (bases,)
            for typeName, typeArgs in dct['variants'].iteritems():
                if type(typeArgs) == type(""): typeArgs = (typeArgs,)
                _typeDefinitions[typeName] = typeArgs
        return type.__new__(mcs, name, bases, dct)

class VariantBase:
    __metaclass__ = _VariantMcs

    def __init__(self):
        for typeName, typeArgs in _typeDefinitions.iteritems():
            setattr(sys.modules[self.__module__], typeName, type(typeName, (type(self),), {'__init__': _variantsInit}))

from pyvariants import VariantBase

class Expr(VariantBase):
    variants={
        'Literal'   : ('value'),
        'Plus'      : ('expr1', 'expr2'),
        'Minus'     : ('expr1', 'expr2'),
    }

    def __str__(self):
        typeName = self.__class__.__name__
        return \
            typeName == 'Literal' and str(self.value) or \
            typeName == 'Plus'    and str(self.expr1) + ' + ' + str(self.expr2) or \
            typeName == 'Minus'   and str(self.expr1) + ' - ' + str(self.expr2)

    def eval(self):
        typeName = self.__class__.__name__
        return \
            typeName == 'Literal' and self.value or \
            typeName == 'Plus'    and self.expr1.eval() + self.expr2.eval() or \
            typeName == 'Minus'   and self.expr1.eval() - self.expr2.eval()


Expr()

expr = Plus(Literal(10), Literal(15))

print expr, '=', expr.eval()

10 + 15 = 25

KV>Продолжаем велосипедостроение

def evl(expr):
    if   expr[0] == 'Plus':
        return evl(expr[1]) + evl(expr[2])
    elif expr[0] == 'Mul':
        return evl(expr[1]) * evl(expr[2])
    elif expr[0] == 'Literal':
        return expr[1]

# TEST:
print evl(["Plus",["Literal",1],["Literal",41]]) #=> 42

Z>def evl(expr):
Z>    if   expr[0] == 'Plus':
Z>        return evl(expr[1]) + evl(expr[2])
Z>    elif expr[0] == 'Mul':
Z>        return evl(expr[1]) * evl(expr[2])
Z>    elif expr[0] == 'Literal':
Z>        return expr[1]

Z># TEST:
Z>print evl(["Plus",["Literal",1],["Literal",41]]) #=> 42
Z>

print 41+1

from pyvariants import VariantBase
from string import replace

def do_call(name, parms):
    if name in calls_example:
        return calls_example[name](*parms)
    else:
        raise NotImplementedError, '%s(%s) is not implemented' % name, parms

calls_example = {
    #function name    implementation
    'min'           : lambda *x: max(x),
    'max'           : lambda *x: min(x),
}

grammar_example = {
    #AST token    arguments             string representation       delegate
    'Call'      : [('name', 'parms'),   '%(name)s%(parms)s',        lambda **x: do_call(x['name'], x['parms'])],
    'Mul'       : [('expr1', 'expr2'),  '(%(expr1)s) * %(expr2)s',  lambda **x: x['expr1'] * x['expr2']],
    'Div'       : [('expr1', 'expr2'),  '(%(expr1)s) / %(expr2)s',  lambda **x: x['expr1'] / x['expr2']],
    'Plus'      : [('expr1', 'expr2'),  '%(expr1)s + %(expr2)s',    lambda **x: x['expr1'] + x['expr2']],
    'Minus'     : [('expr1', 'expr2'),  '%(expr1)s - %(expr2)s',    lambda **x: x['expr1'] - x['expr2']],
    'Literal'   : [('value',),          '%(value)s',                lambda **x: x['value']]
}

class Expr(VariantBase):

    grammar = grammar_example
    variants = dict(map(lambda item: [item[0], item[1][0]], grammar.iteritems()))

    def _evaluator(self, f):
        return dict(map(lambda arg:
            [arg,
            f(getattr(self, arg)) if isinstance(getattr(self, arg), Expr) else
                  tuple(map(lambda x: f(x), getattr(self, arg))) if isinstance(getattr(self, arg), tuple) else
                      getattr(self, arg)
            ],
            self.__dict__))

    def __str__(self):
        return replace(self.__class__.grammar[self.__class__.__name__][1] % self._evaluator(lambda x: str(x)), '\'', '')

    def eval(self):
        return self.__class__.grammar[self.__class__.__name__][2](**self._evaluator(lambda x: x.eval()))

Expr()

expr = Mul(Plus(Call('min', (Literal(6), Literal(4))), Literal(32)), Literal(0.2))
result = expr.eval()
print '%s = %s' % (expr, result)

>>> expr = Plus(666,"FooBar")  # must be error
>>> expr.expr1
666
>>> expr.expr2
'FooBar'

;; Пример с 6-ой страницы PLAI (AE - сокращенно от ArithmeticExpression) 
;; Обратите внимание на предикаты 'AE?' и 'number?'
(define-type AE
  [num (n number?)]
  [add (lhs AE?)
       (rhs AE?)]
  [sub (lhs AE?)
       (rhs AE?)])

(define (calc an-ae)
  (type-case AE an-ae  ;; <-- проверка правильности типа an-ae
    [num (n) n]                                ;; \
    [add (l r) (+ (calc l) (calc r))]          ;; | <- pattern-matching
    [sub (l r) (- (calc l) (calc r))]))        ;; /

class Wildcard(object):
    def __eq__(self, other):
        return True
   
    def __ne__(self, other):
        return False

wildcard = Wildcard()