| Andrew Cooke | Contents | Latest | RSS | Twitter | Previous | Next

C[omp]ute

Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Lepl parser for Python.

Colorless Green.

Photography around Santiago.

SVG experiment.

Professional Portfolio

Calibration of seismometers.

Data access via web services.

Cache rewrite.

Extending OpenSSH.

Last 100 entries

Poorest in UK, Poorest in N Europe; I Want To Be A Redneck!; Reverse Racism; The Lost Art Of Nomography; IBM Data Center (Photo); Interesting Account Of Gamma Hack; The Most Interesting Audiophile In The World; How did the first world war actually end?; Ky - Restaurant Santiago; The Black Dork Lives!; The UN Requires Unaninmous Decisions; LPIR - Steganography in Practice; How I Am 6; Clear Explanation of Verizon / Level 3 / Netflix; Teenage Girls; Formalising NSA Attacks; Switching Brakes (Tektro Hydraulic); Naim NAP 100 (Power Amp); AKG 550 First Impressions; Facebook manipulates emotions (no really); Map Reduce "No Longer Used" At Google; Removing RAID metadata; New Bike (Good Bike Shop, Santiago Chile); Removing APE Tags in Linux; Compiling Python 3.0 With GCC 4.8; Maven is Amazing; Generating Docs from a GitHub Wiki; Modular Shelves; Bash Best Practices; Good Emergency Gasfiter (Santiago, Chile); Readings in Recent Architecture; Roger Casement; Integrated Information Theory (Or Not); Possibly undefined macro AC_ENABLE_SHARED; Update on Charges; Sunburst Visualisation; Spectral Embeddings (Distances -> Coordinates); Introduction to Causality; Filtering To Help Colour-Blindness; ASUS 1015E-DS02 Too; Ready Player One; Writing Clear, Fast Julia Code; List of LatAm Novels; Running (for women); Building a Jenkins Plugin and a Jar (for Command Line use); Headphone Test Recordings; Causal Consistency; The Quest for Randomness; Chat Wars; Real-life Financial Co Without ACID Database...; Flexible Muscle-Based Locomotion for Bipedal Creatures; SQL Performance Explained; The Little Manual of API Design; Multiple Word Sizes; CRC - Next Steps; FizzBuzz; Update on CRCs; Decent Links / Discussion Community; Automated Reasoning About LLVM Optimizations and Undefined Behavior; A Painless Guide To CRC Error Detection Algorithms; Tests in Julia; Dave Eggers: what's so funny about peace, love and Starship?; Cello - High Level C Programming; autoreconf needs tar; Will Self Goes To Heathrow; Top 5 BioInformatics Papers; Vasovagal Response; Good Food in Vina; Chilean Drug Criminals Use Subsitution Cipher; Adrenaline; Stiglitz on the Impact of Technology; Why Not; How I Am 5; Lenovo X240 OpenSuse 13.1; NSA and GCHQ - Psychological Trolls; Finite Fields in Julia (Defining Your Own Number Type); Julian Assange; Starting Qemu on OpenSuse; Noisy GAs/TMs; Venezuela; Reinstalling GRUB with EFI; Instructions For Disabling KDE Indexing; Evolving Speakers; Changing Salt Size in Simple Crypt 3.0.0; Logarithmic Map (Moved); More Info; Words Found in Voynich Manuscript; An Inventory Of 3D Space-Filling Curves; Foxes Using Magnetic Fields To Hunt; 5 Rounds RC5 No Rotation; JP Morgan and Madoff; Ori - Secure, Distributed File System; Physical Unclonable Functions (PUFs); Prejudice on Reddit; Recursion OK; Optimizing Julia Code; Cash Handouts in Brazil; Couple Nice Music Videos; It Also Works!; Adaptive Plaintext; It Works!

© 2006-2013 Andrew Cooke (site) / post authors (content).

Monads in Python

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

Undo Example

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

Date: Sun, 4 May 2008 11:26:39 -0400 (CLT)

Here's an example of undo in action.  One advantage of the approach above
is that it's trivial to reverse the order of operations (necessary for
undo).  That would be trickier if we used nested lambdas.

class Add(Action):

    def __init__(self, n):
        super(Add, self).__init__(label='+%s' % n, n=n)

    def __call__(self, x, undo):
        undo < Subtract(self._n)
        x.value = x.value + self._n


class Subtract(Action):

    def __init__(self, n):
        super(Subtract, self).__init__(label='-%s' % n, n=n)

    def __call__(self, x, undo):
        undo < Add(self._n)
        x.value = x.value - self._n


class Multiply(Action):

    def __init__(self, n):
        super(Multiply, self).__init__(label='*%s' % n, n=n)

    def __call__(self, x, undo):
        undo < Divide(self._n)
        x.value = x.value * self._n


class Divide(Action):

    def __init__(self, n):
        super(Divide, self).__init__(label='/%s' % n, n=n)

    def __call__(self, x, undo):
        undo < Multiply(self._n)
        x.value = x.value / self._n


class Mutable(object):

    def __init__(self, value):
        self.value = value


class UndoTest(TestCase):

    def test_undo(self):
        u1 = Undo('undo initial operation')
        c = Composite('add 2 and multiply by 3')
        x = Mutable(0)
        c < Add(2)
        c < Multiply(3)
        c(x, u1)
        self.assertEqual(6, x.value)
        u2 = Undo('undo the undo')
        u1(x, u2)
        self.assertEqual(0, x.value)
        u2(x, Undo('unused'))
        self.assertEqual(6, x.value)

(note that add and multiply do not commute)

Andrew

Correction

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

Date: Sun, 11 May 2008 11:02:12 -0400 (CLT)

Crap.  The above only works because I used lambda in the tests to make
them shorter (and whose body introduces a new scope which is lazily
evaluated).

Conclusion

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

Date: Mon, 12 May 2008 10:49:25 -0400 (CLT)

So what I finally end up doing here was using futures/thunks whatever you
want to call them.  The getattr on the "monad" returns a function which
must be evaluated to get the actual value.  The idea being that this
evaluation occurs after the evaluation of the action that will generate
it.

Obviously that complicates the code because instead of just using values,
there are these special futures that need to be evaluated.  In the
particular use case I have here (see my later post on undo actions) I can
automate this, so that the code the user writes doesn't have to make the
check.

Andrew

Much Better via Co-Routines

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

Date: Fri, 3 Apr 2009 11:58:36 -0400 (CLT)

Someone else did a much better job than me using co-routines.

http://www.valuedlessons.com/2008/01/monads-in-python-with-nice-syntax.html

Andrew

Much Better via Co-Routines

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

Date: Fri, 3 Apr 2009 11:58:36 -0400 (CLT)

Someone else did a much better job than me using co-routines.

http://www.valuedlessons.com/2008/01/monads-in-python-with-nice-syntax.html

Andrew

Much Better via Co-Routines

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

Date: Fri, 3 Apr 2009 11:58:36 -0400 (CLT)

Someone else did a much better job than me using co-routines.

http://www.valuedlessons.com/2008/01/monads-in-python-with-nice-syntax.html

Andrew

Much Better via Co-Routines

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

Date: Fri, 3 Apr 2009 11:58:36 -0400 (CLT)

Someone else did a much better job than me using co-routines.

http://www.valuedlessons.com/2008/01/monads-in-python-with-nice-syntax.html

Andrew

Comment on this post