C[omp]ute

From: "andrew cooke" <andrew@...>

Date: Sun, 4 May 2008 08:14:08 -0400 (CLT)

[When I sat down to write this note I thought I better do due diligence
and see if there's already a solution out there - although of course I'd
already written the code.  I found this amazing work -
http://www.valuedlessons.com/2008/01/monads-in-python-with-nice-syntax.html
- which is a completely different take.  I don't understand exactly how
that works, but I think it's interesting to compare the two approaches:

My code below is, I think, much more aligned with the rest of Python
(where context is frequently explicit - for example 'self').  On the other
hand, it's nowhere near as impressive (and perhaps my code isn't even
right - I am not sure if I am "really" implementing Monads, or just making
something that looks vaguely like them)]


OK, so I am writing some client code (a GUI desktop app) and I have
finally got to the part where the program does something.  Trouble is, I
would also like to be able to undo that something.  So I need an "undo"
action.  And to implement that I need to be careful about what an "action"
is.

I won't go into all the details, but it became obvious that I needed a way
to define a sequence of events, and then to execute that sequence of
events (for "undo" each event also generates its inverse and appends it to
a separate "undo sequence" that is created as the "do" sequence
evaluates).

I also needed some way to refer to the results of a previous event.  For
example, if I had a two step process where the first step created a Foo
and the next step called Foo.bar() then I needed to be able to reference
the Foo I had created in the first step.

When I was half way through implementing a couple of classes to do what I
just sketched I realised it was *awfully* like the IO Monad in Haskell. 
So I started thinking about how I could make it closer.  At first I
focused on syntax, but it soon dawned on me (being less smart than whoever
wrote the post above) that I was making really slow progress because I was
fighting against the language.

Once I stopped fighting Python and instead tried to "roll with it", things
became a lot easier.  Instead of trying to somehow get arbitrary chunks of
code into my syntax I decided that each "action" in a sequence would be a
"callable" (ie a function or an object that implements __call__).  And
instead of trying to bind names in the current context, I decided to use
an explicit context, much like "self".

The result is code like this test case:

class SequenceTest(TestCase):

    def test_sequence(self):
        self.called = False
        def foo():
            self.called = True
        s = Sequence()
        s.a = lambda: 'A'
        s.b = lambda: self.assertEqual('A', s.a)
        s.c = lambda: self.assertFalse('c' in dir(s))
        s < (lambda: self.assertTrue('c' in dir(s)))
        s < foo
        self.assertFalse(self.called)
        self.assertFalse('a' in dir(s))
        s()
        self.assertTrue(self.called)
        self.assertTrue('a' in dir(s))

That might be a bit opaque, so I'll explain:

 - First, foo() is defined as a function that sets "called" to True.
   We use that later to test the timing of calls.

 - Next, s is defined as a Sequence.  This is my equivalent of the
   IO Monad.  All it really does is store a bunch of steps to execute
   later.

 - Next I defined the steps.
   - First a function that returns "A" will be evaluated and the
     result ("A") bound to "a".
   - Next we'll execute a function that tests the above (and
     bind None to "b" as it happens).
   - Next we'll execute a test showing that the action "in progress"
     is not yet bound (a bit obscure)
   - Next an "anonymous" step that tests that the step above had
     worked correctly.
   - Finally an anonymous step (ie result not bound to anything)
     that calls foo and so sets "called"

 - Before we call the sequence we check that called is still false
   and that the value "a" is unbound.

 - Then we execute the sequence by calling it "s()"

 - The sequence runs OK (all the tests pass) and we can then see
   that "called" true and the name "a" is bound.


I also used the same basis to write a Maybe monad.  I won't explain the
details, but here are the two tests.  Note that, again, I am going with
the flow and using Python's "None" as the failure value (this is a very
common Python idiom - much like NULL in SQL, and probably as ill-advised).

class MaybeTest(TestCase):

    def test_something(self):
        m = Maybe()
        m.a = lambda: 1
        m.b = lambda: False
        m.c = lambda: m.a + 2
        self.assertEqual(3, m())

    def test_nothing(self):
        m = Maybe()
        m.a = lambda: 1
        m.b = lambda: None
        m.c = lambda: m.a + 2
        self.assertEqual(None, m())


Note that I used lamda above for simple tests.  In practice my "actions"
implement __call__ so look more like:

    s = Sequence()
    s.foo = CreateFoo()
    s < CallBar(s.foo)

and they are invoked with:

    undo = Sequence()
    s(undo)

which lets them append their inverse actions to the undo sequence as they
execute.


OK, so the implementation:


class Monad(object):

    def __init__(self, *args, **kargs):
        super(Monad, self).__init__(*args, **kargs)
        self._sequence = []
        self._context = {}

    def __setattr__(self, name, value):
        '''
        Value should be a callable and will be invoked with the
        arguments passed to __call__

        On evaluation, name will be bound to the value returned and
        then available via normal attribute access
        '''
        if name in dir(self) or name.startswith('_'):
            super(Monad, self).__setattr__(name, value)
        else:
            self._sequence.append((name, value))

    def __lt__(self, value):
        '''
        Anonymous version of __setattr__
        '''
        self._sequence.append((None, value))


class Sequence(Monad):

    def __init__(self, *args, **kargs):
        super(Sequence, self).__init__(*args, **kargs)

    def __call__(self, *args, **kargs):
        for (name, callable) in self._sequence:
            result = callable(*args, **kargs)
            if name:
                self.__dict__[name] = result


class Maybe(Monad):

    def __init__(self, *args, **kargs):
        super(Maybe, self).__init__(*args, **kargs)

    def __call__(self, *args, **kargs):
        result = None
        for (name, callable) in self._sequence:
            result = callable(*args, **kargs)
            if result is None:
                return None
            if name:
                self.__dict__[name] = result
        return result


Re-reading the above, I see I have used a,b,c as variable names each time.
 I should probably just add that there's no special significance there -
you can use whatever you want: it's the order in which they are defined
that matters.

Andrew