Making Python Functional Again

Making Python Functional Again

Once upon a time, there was a urban legend saying that Python has some functional programming features.

Well, sadly that’s not even close.

During the time past, I’ve collected some functional pieces while working with Python, and assembled and polished them into a library: fpy.

The Root of Everything

If you still remember this and this (which I don’t expect at all lol), the tools I used to build them are, unfortunately, now taken as my previous company’s intellectual property.

From the same spirit of them, I started a fresh and new project: fpy, and tried to be as close to Haskell as possible. Since I’m writing this blog post, you can assume that I’m at least somehow satisfied by this already.

FPy

Before getting into it, let me show you some code:

def foo(x, y):
    return Just(x + y)
    
def testNested(self):
    @do(Just)
    def test():
        x <- Just(1)
        y <- Just(2)
        z <- foo(x, y)
        return z + z

    res = test()
    self.assertTrue(isJust(res))
    self.assertEqual(fromJust(res), 6)

dash = and_(isInstr, __.name == "UNARY_NEGATIVE")
arrowHead = and_(isInstr, and_(__.name == "COMPARE_OP", __.arg == bc.Compare.LT))
popTop = and_(isInstr, __.name == "POP_TOP")
parseArrow = one(dash) >> one(arrowHead) >> one(popTop)
parseDoBody = many(parseArrow | one(const(True)))

add = cont(lambda a, b: a + b)
mul = cont(lambda a, b: a * b)
div = cont(lambda a, b: a / b)

def testCont(self):
    res = add(2, 2) >> mul(3) >> div(1)
    self.assertEqual(Under(4), res & forget)
    self.assertEqual(Under(2), ac(1, 1) & forget)

Python’s Type System Sucks, What’s the Point???

Well, this is a cruel fact, but we can at least have the nice monadic control. Therefore the core spirit of FPy is not to make 100% type safe Python with higher order types (which is not possible), but to bring the good part of functional programming to Python.

Composable

The most important concept is composablity, in FPy, we have fpy.composable.function.func as one of the foundation block of FPy, which allows us to compose functions easily:

def add1(x):
    return x + 1

def mul2(x):
    return x * 2
    
def testFunc(self):
    f1 = func(add1)
    f2 = func(mul2)
    self.assertEqual(4, (f1 ^ f2)(1))
    self.assertEqual(3, (f2 ^ f1)(1))

Unfortunately, Python doesn’t allow custome infix operators, therefore I chose ^ as it looks the most similar to \circ among the available operators. Partial evaluation is also supported by func functions.

Then, voila, you can compose functions to make new functions.

It works like a charm:

store = and_(
    isInstr,
    __.name
    ^ of_(
        "STORE_FAST",
        "STORE_NAME",
        "STORE_DEREF",
    ),
)

Algebric Structure

A monad is just a monoid in the category of endofunctors, what’s the problem?

Although Python’s type system doesn’t support them, we can still mimic their behaviours :(

In fpy.control, you can find functor, applicative, monad and natural_transform whose meanings can be implied from their names.

For functors, you have fmap whose operator is |.

For applicatives, you have liftA2, and sadly I didn’t give it an operator.

For monads, you have bind whose operator is >>.

For natural_transform, you have ntrans which takes an object of a functor type and transform it to another functor type, using the operator &.

They work in the way as you would expect (and if you don’t have some self dicipline, Python won’t stop you from messing them up).

Helper

In languages such as Scala, you have some shorthand version than the long lambda expression for some small stuffs, e.g. in Scala:

(_ : int) * (_ : int)

gives you a quick multiply function.

In fpy.utils.placeholder, you have a special object __ which can be used in a similar manner, so that instead of writing:

lambda x: x.name == "LOAD"

you can write:

__.name == "LOAD"

Parsing

Back to the very beginning, I created those tools for writing parsers, they were brought to FPy and had some evolve. In fpy.parsec.parsec, you can find combinators for you to write parsers elegantly.

Simply, a parser is something:

parser :: [S] -> Either [S] ([T] * [S])

Then everything in the parsec package is a constructor of new parsers.

Do Notation

The desugaring of Haskell’s do notation is simple:

do
  a <- comp1
  expr
  ...

is desugared into:

comp1 >>= (\a -> do { expr; ... })

But in Python, there is no way except messing around with the Python codecs to achieve this.

My approach was to modify the bytecode at the import time, then achieved something like this:

@do(Just)
def foo(x):
  y <- Just(x + 1)
  z <- Just(y + 1)
  return z

Firstly, what is <-?

It is COMPARE_OP.LT and UNARY_NEGATIVE loooooooool.

It is easy to observe from the compiled bytecode that

a <- b

is compiled into

LOAD a
LOAD b
UNARY_NEGATIVE
COMPARE_OP.LT
POP_TOP

Even if some one is really using the compare with a negated value, the result will not be poped, therefore it is safe to simply replace the UNARY_NEGATIVE, COMPARE_OP.LT, POP_TOP part into an Arrow token.

The following transformation is straightforward, firstly wrap the Arrow token with the name and the computation, then put the code below it into a nested function, then recurse until there is no more <- left.

When there are multiple symbols on the left of <-, the transformation is similar but counting the given number of names instead of taking only one symbol.

The return statement in a do notation is different from the primitive behaviour, instead of returning the plain value, this returns the value wrapped in the given Monad type (the argument of @do). If you want to return an already wrapped value, just leave it on the top of the stack and it will be implicitly returned.