FunPy

FunPy makes functional programming in Python easy by using MacroPy to reduce boilerplate.

FunPy currently has the following features:

• Case Classes, also known as algebraic data types
• Pattern Matching
• Tail-call Optimization
• Quick Lambdas

Case Classes

from macropy.macros.adt import macros, case

@case
class Point(x, y): pass

p = Point(1, 2)

print str(p)    #Point(1, 2)
print p.x       #1
print p.y       #2
print Point(1, 2) == Point(1, 2)
#True

Case classes are classes with extra goodies:

• Nice __str__ and __repr__ methods autogenerated
• An autogenerated constructor
• Structural equality by default
• A Copy-constructor, for creating modified copies of instances

The reasoning being that although you may sometimes want complex, custom-built classes with custom features and fancy inheritance, very (very!) often you want a simple class with a constructor, pretty __str__ and __repr__ methods, and structural equality which doesn't inherit from anything. Case classes provide you just that, with an extremely concise declaration:

@case
class Point(x, y): pass

As opposed to the equivalent class, written manually:

class Point(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return "Point(" + self.x + ", " + self.y + ")"

    def __repr__(self):
        return self.__str__()

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __ne__(self, other):
        return not self.__eq__(other)

Whew, what a lot of boilerplate! This is clearly a pain to do, error prone to deal with, and violates DRY in an extreme way: each member of the class (x and y in this case) has to be repeated 6 times, with loads and loads of boilerplate. It is also buggy, and will fail at runtime when the above example is run, so see if you can spot the bug in it! Given how tedious writing all this code is, it is no surprise that most python classes do not come with proper __str__ or useful __eq__ functions! With case classes, there is no excuse, since all this will be generated for you.

Case classes also provide a convenient copy-constructor, which creates a shallow copy of the case class with modified fields, leaving the original unchanged:

a = Point(1, 2)
b = a.copy(x = 3)
print a #Point(1, 2)
print b #Point(3, 2)

Like any other class, a case class may contain methods in its body:

@case
class Point(x, y):
    def length(self):
        return (self.x ** 2 + self.y ** 2) ** 0.5

print Point(3, 4).length() #5

or class variables. The only restrictions are that only the __init__, __repr__, ___str__, __eq__ methods will be set for you, and it may not manually inherit from anything. Instead of manual inheritence, inheritence for case classes is defined by nesting, as shown below:

@case
class List():
    def __len__(self):
        return 0

    def __iter__(self):
        return iter([])

    class Nil:
        pass

    class Cons(head, tail):
        def __len__(self):
            return 1 + len(self.tail)

        def __iter__(self):
            current = self

            while len(current) > 0:
                yield current.head
                current = current.tail

print isinstance(Cons(None, None), List)    # True
print isinstance(Nil(), List)               # True

my_list = Cons(1, Cons(2, Cons(3, Nil())))
empty_list = Nil()

print my_list.head              # 1
print my_list.tail              # Cons(2, Cons(3, Nil()))
print len(my_list)              # 5
print sum(iter(my_list))        # 6
print sum(iter(empty_list))     # 0

This is an implementation of a singly linked cons list, providing both head and tail (LISP's car and cdr) as well as the ability to get the len or iter for the list.

As the classes Nil are Cons are nested within List, both of them get transformed into top-level classes which inherit from it. This nesting can go arbitrarily deep.

Overall, case classes are similar to Python's namedtuple, but on steroids (methods, inheritence, etc.), and provides the programmer with a much better experience.

Pattern Matching

One important thing you might want to do with case classes is match them against some patterns. For example, suppose that you are writing a function to transform an AST. You want to try to macro-expand with-blocks which represent macro invocation, but not affect anything else.

The code for this without pattern matching might look something like:

def expand_macros(node):
    if (isinstance(node, With) and isinstance(node.context_expr, Name)
        and node.context_expr.id in macros.block_registry:
        return macros.block_registry[node.context_expr.id](node)
    else:
        return node

With pattern matching (specifically, using the switch macro), we could instead write:

def expand_macros(node):
    with switch(node):
        if With(Name(macro_name)):
            return macros.block_registry[macro_name](node)
        else:
            return node

Once you're used to this, it is much simpler both to read and to write, and the benefits of pattern matching only grow as the matched data structures get more complex.

Here is another, more self-contained example of an implementation of a <a href="http://en.wikipedia.org/wiki/Fold_(higher-order_function)"> left fold</a> from functional programming:

@case
class List:
    class Nil():
        pass

    class Cons(x, xs):
        pass

def foldl1(my_list, op):
    with switch(my_list):
        if Cons(x, Nil()):
            return x
        elif Cons(x, xs):
            return op(x, foldl1(xs, op))

The switch macro is actually just syntactic sugar for using the more general patterns macro. foldl1 is approximately desugared into the following, with one important caveat: the bodies of the if statements are not subject to pattern matching, in case you actually want to use bitshifts in your code.

def foldl1(my_list, op):
    with patterns:
        tmp = my_list
        try:
            Cons(x, Nil()) << tmp
            return x
        except PatternMatchException:
            try:
                Cons(x, xs) << tmp
                return op(x, foldl1(xs, op))
            except PatternMatchException:
                pass

I think you can agree that the first version is much easier to read, and the second version hasn't even been fully expanded yet!

It's also possible to do away with the if statements if you know what the structure of your input will be. This also has the benefits of throwing an exception if your input doesn't match the expected form.

from macropy.macros.adt import macros, patterns

def area(rect):
    with patterns:
        Rect(Point(x1, y1), Point(x2, y2)) << rect
        return (x2 - x1) * (y2 - y1)

If the match fails, a PatternMatchException will be thrown.

    # Throws a PatternMatchException
    area(Line(Point(1, 2), Point(3, 4)))

###Class Matching Details

When you pattern match Foo(x, y) against a value Foo(3, 4), what happens behind the scenes is that the constructor of Foo is inspected. We may find that it takes two parameters a and b. We assume that the constructor then contains lines like:

self.a = a
self.b = b

(We don't have access to the source of Foo, so this is the best we can do). Then Foo(x, y) << Foo(3, 4) is transformed roughly into

tmp = Foo(3,4)
tmp_matcher = ClassMatcher(Foo, [NameMatcher('x'), NameMatcher('y')])
tmp_matcher.match(tmp)
x = tmp_matcher.getVar('x')
y = tmp_matcher.getVar('y')

In some cases, constructors will not be so standard. In this case, we can use keyword arguments to pattern match against named fields. For example, an equivalent to the above which doesn't rely on the specific implementation of th constructor is Foo(a=x, b=y) << Foo(3, 4). Here the semantics are that the field a is extracted from Foo(3,4) to be matched against the simple pattern x. We could also replace x with a more complex pattern, as in Foo(a=Bar(z), b=y) << Foo(Bar(2), 4).

###Custom Patterns It is also possible to completely override the way in which a pattern is matched by defining an __unapply__ class method of the class which you are pattern matching. The 'class' need not actually be the type of the matched object, as in the following example borrowed from Scala. The __unapply__ method takes as arguments the value being matched, as well as a list of keywords.

The method should then return a tuple of a list of positional matches, and a dictionary of the keyword matches.

class Twice(object):
    @classmethod
    def __unapply__(clazz, x, kw_keys):
        if not isinstance(x, int) or x % 2 != 0:
            raise PatternMatchException()
        else:
            return ([x/2], {})

with patterns:
    Twice(n) << 8
    print n     # 4

Tail-call Optimization

We have also implemented a macro which will optimize away the stack usage of functions which are actually implemented in a tail-recursive fashion. This even works for mutually recursive functions by using trampolining.

The 'hello world' of tail-recursive functions is a factorial function, so I'll show that first.

@tco
def fact(n, acc):
    if n == 0:
        return acc
    else:
        return fact(n-1, n * acc)

print fact(10000)  # doesn't stack overflow

More complicated mutually recursive examples also work too.

from macropy.ma