connecting the dots . . .

Multimethods in Python

Thu, 06 Jun 2013 23:23:00 -0400

So, PEP-443 aka Single-dispatch generic functions has made it into Python. There is a nice writeup of the singledispatch package features by Łukasz Langa.

Although I’m glad that Python is evolving in the right direction, I can’t see how single dispatch alone could be enough. In essence, PEP-443 defines a way of dynamically extending existing types with externally defined generic functions. Which is nice, of course, but too limited.

What is really interesting is multiple dispatch. There are a few packages bringing multimethods to Python; all of them are overcomplicated to my taste.

Here’s my take on it. I will not talk much, better show you the code.

This is the complete implementation:

# multidispatch.py

import operator
from collections import OrderedDict

class DuplicateCondition(Exception): pass

class NoMatchingMethod(Exception): pass

class defmulti(object):
    def __init__(self, predicate):
        self.registry = OrderedDict()
        self.predicate = predicate

    def __call__(self, *args, **kw):
        method = self.dispatch(*args, **kw)
        return method(*args, **kw)

    def dispatch(self, *args, **kw):
        for condition, method in self.registry.items():
            if self.predicate(condition, *args, **kw):
                return method
        return self.notfound

    def notfound(self, *args, **kw):
        raise NoMatchingMethod()

    def when(self, condition):
        if condition in self.registry:
            raise DuplicateCondition()
        def deco(fn):
            self.registry[condition] = fn
            return fn
        return deco

    def default(self, fn):
        self.notfound = fn
        return fn

    @classmethod
    def typedispatch(cls):
        return cls(lambda type, first, *rest, **kw: isinstance(first, type))

And here’s how to use it:

import types
from multidispatch import defmulti, NoMatchingMethod

# Exhibit A: Dispatch on the type of the first parameter.
#            Equivalent to `singledispatch`.

cupcakes = defmulti.typedispatch()

@cupcakes.when(types.StringType)
def str_cupcakes(ingredient):
    return "Delicious {0} cupcakes".format(ingredient)

@cupcakes.when(types.IntType)
def int_cupcakes(number):
    return "Integer cupcakes, anyone? I've got {0} of them.".format(number)

@cupcakes.default
def any_cupcakes(thing):
    return ("You can make cupcakes out of ANYTHING! "
            "Even out of {0}!").format(thing)

print cupcakes("bacon")
print cupcakes(4)
print cupcakes(cupcakes)


# Exhibit B: dispatch on the number of args, no default

@defmulti
def jolly(num, *args):
    return len(args) == num

@jolly.when(1)
def single(a):
    return "For {0}'s a jolly old fellow!".format(a)

@jolly.when(2)
def couple(a, b):
    return "{0} and {1} are such a jolly couple!".format(a, b)

print jolly("Lukasz")
print jolly("Fish", "Chips")
try:
    jolly("Good", "Bad", "Ugly")
except NoMatchingMethod:
    print "Noo! Angel Eyes!"

I will never CNAME my root domain again. I will never CNAME my root domain again. I will never...

Wed, 17 Apr 2013 23:43:29 -0400

I will never CNAME my root domain again.

NEVER. EVER.

Hello Tumblr

Sat, 13 Apr 2013 23:04:32 -0400

Good bye, Posterous. Rest in peace.

A simple callback chain macro for elisp

Wed, 06 Jun 2012 00:00:00 -0400

The Problem

As usual, it started with a tiny piece of ugly code:

(bd-create-stage datafile-id
                 (lambda (stage-id)
                   (bd-insert-rows stage-id 
                                   [[10 20 30] [40 50 60]]
                                   (lambda (stage-id)
                                     (bd-commit-stage stage-id 
                                                      #'ignore)))))

The snippet above is basically a callback chain. When bd-create-stage finishes its work, it calls the first lambda, which calls bd-insert-rows with the second lambda as its callback argument and so on, until it all stops at the ignore function.

I wanted to rewrite it as something like this:

(=> datafile-id
    (bd-create-stage it next)
    (bd-insert-rows  it [[1 2 3 4 5] [6 7 8 9 0]] next)
    (bd-commit-stage it next))

Where the it variable would represent the current callback’s parameter and next would refer to the next callback in the chain. As with the -> macro, I wanted explicit anaphoric variables.

The Idea

Each line in the snippet above could be wrapped in a lambda, lust like this:

(=> datafile-id
    (lambda (next it)
      (bd-create-stage it next))
    (lambda (next it)
      (bd-insert-rows it [[1 2 3 4 5] [6 7 8 9 0]] next)
    (lambda (next it)
      (bd-commit-stage it next))))

Then it should somehow call each function in the list with the consequent function as the first parameter and the result of execution of the previous function as the second parameter.

The Solution

This function chaining thing looks a lot like a binary function fold:

(defun chain2 (f1 f2)
  (apply-partially f1 f2))

(defun chain (&amp;rest fns)
  (if fns
      (reduce #'chain2 fns :from-end t)
    #'identity))

Applying chain to a function list creates a new function taking one parameter and passing it through the whole function list, much like the -> macro does.

In fact, this is enough to start working on the macro.

(defmacro => (initial &amp;rest forms)
  `(funcall ,(build-form-chain forms) ,initial))

The build-form-chain function wraps each form into a lambda and then chains them together:

(defun build-form-chain (forms)
  `(apply #'chain 
          (list ,@(mapcar #'build-form-link forms) #'ignore)))

At the end it adds ignore as a terminator. The terminator is necessary because the last callback’s result is almost always ignored.

The build-form-link’s implementation is trivial:

(defun build-form-link (form)
  `(lambda (next it) ,form))

Done! Here’s the full source for your convenience:

(defun chain2 (f1 f2)
  (apply-partially f1 f2))

(defun chain (&rest fns)
  (if fns
      (reduce #'chain2 fns :from-end t)
    #'identity))

(defun build-form-link (form)
  `(lambda (next it) ,form))

(defun build-form-chain (forms)
  `(apply #'chain 
          (list ,@(mapcar #'build-form-link forms) #'ignore)))

(defmacro => (initial &rest forms)
  `(funcall ,(build-form-chain forms) ,initial))

Now let’s see how the macro expands:

ELISP> (macroexpand
     '(=> datafile-id
          (bd-create-stage it next)
          (bd-insert-rows  it [[1 2 3 4 5] [6 7 8 9 0]] next)
          (bd-commit-stage it next)))

(funcall (apply (function chain) 
                (list (lambda (next it) 
                        (bd-create-stage it next))
                      (lambda (next it)
                        (bd-insert-rows it [[1 2 3 4 5] [6 7 8 9 0]] next))
                      (lambda (next it)
                        (bd-commit-stage it next))
                      (function ignore)))
          datafile-id)

Exactly as intended.

This macro covers 95% of my callback chaining needs. For the rest 5% there is the all-powerful deferred.el library.

Thread operator in Elisp

Wed, 09 May 2012 00:00:00 -0400

TL;DR

ELISP> (-> 1
           (+ 2 it)
           (* 3 it))
9
ELISP> (macroexpand
           '(-> 1
                (+ 2 it)
                (* 3 it)))
(let* ((it 1) (it (+ 2 it)) (it (* 3 it))) it)

Implementation:

(defmacro -> (arg &rest forms)
  `(let* ((it ,arg) .
      ,(mapcar (lambda (form) `(it ,form))
           forms))
     it))

The Long Story

When I see code like this, I frown:

(defun bd-search (api-key query callback)
  (send-request "GET"
            (format "search?%s"
                (make-query-string `(("api_key" . ,api-key)
                             ("query" . ,query))))
        callback))

It’s a very simple case, yet the parameter list is already at the fourth level of indentation. When it gets really ugly I usually wrap the whole thing into a let statement and start moving inner parts into variables.

What I have noticed, however, is that almost always constructs like this are sequential by their nature, in other words the output of the innermost statement serves as input for the statement one level up, and so on and so forth. This is the very reason why Clojure had its thread operator macro since beginning.

Remembering that, I started literally morphing my bd-search function into something more prettier. I came up with this variant:

  (-> `(("api_key" . ,api-key)
    ("query" . ,query))
      (make-query-string it)
      (format "search?%s" it)
      (send-request "GET" it callback)))

Then I put together the -> macro and that was it.

I decided to make the macro anaphoric instead of implicitly injecting an extra parameter as in Clojure. This allowed me to put the threaded parameter at any place, not just at the beginning or at the end of the parameter list.

How much can be done in four hours

Sat, 27 Aug 2011 00:00:00 -0400

Today I had an awesome day at the first OpenDataBC hackathon which took place at Mozilla Labs Vancouver.

Tara Gibbs pitched this wonderful idea of consolidating shelter availability data and displaying it on a few window displays, so the homeless people living DTES would not waste their time going from one shelter to another just to find a free spot.

This doesn’t solve all the problems of course, but it does solve a little yet very annoying one.

So… At 11:30 we had nothing but an idea. We discussed possible approaches for a while, then came David Eaves and suggested using Twitter as a message queue service.

At approximately 12:00 we still had nothing but a piece of paper covered with boxes and arrows, then we started coding. Tara did the frontend, I was busy hacking the backend and the Twitter stuff.

Four hours later we had a fully functional, production ready system - https://github.com/mikeivanov/vanshelter

How it is supposed to work:

Shelters tweet their availability data (they all have internet access)
VanShelter monitors — each of them independently — receive Twitter updates and
Refresh their displays when something changes.

For displays we can use cheap LCD monitors, probably even donated. The software will run on those amazing Raspberry thingies - http://www.raspberrypi.org/, $25 each. This brings the full cost of installing 10 displays down to $250+.

Thank you Tara and David. Also, thank you Jeff and all the people who made this hackathon possible.

Pure Python Paillier Homomorphic Cryptosystem Implementation

Tue, 28 Jun 2011 00:00:00 -0400

What

This is a very basic Paillier Homomorphic Cryptosystem implemented in pure Python.

The idea is, in short, to encrypt two numbers, perform an “add” operation on cyphertexts, decrypt the result and find it to be the sum of the original plaintext numbers.

How

The code is loosely based on the thep project and a few ActiveState recipes. The code is pure Python and all objects are serializable.

Where

Here: https://github.com/mikeivanov/paillier

Why

I was bored.

How to mount an NTFS-formatted USB drive in read-write mode on Mac OS X

Thu, 09 Jun 2011 00:00:00 -0400

Actually, it’s very easy. No additional software is required. Just seven easy steps:

Attach your USB drive
Open the Terminal app (Command-Space, then type “Terminal”, hit Enter)

Type or copy/paste these commands:

sudo sh -c "mkdir -p /mnt \
$(mount | grep ntfs | head -n 1 \
   | awk '{ print "&& umount " $3 \
               " && mount_ntfs -o nosuid,rw " $1 " /mnt" }')"

Locate your drive in Finder
Drag/drop files there
Unmount the drive as usual
DONE!

The command breakdown, if you’re interested:

mkdir -p /mnt creates a mount point — a place in the file system where the drive is going to be attached
The mount command without parameters gives you a list of the currently attached drives
grep ntfs filters non-ntfs drives out the list
head -n 1 grabs the first line (we’re assuming only one ntfs drive can be attached at a time)
The awk part produces two commands:
- umount /Volumes/ — unmounts the drive from its original place
- mount_ntfs -o nosuid,rw /dev/ /mnt — mounts the drive again, but this time in the read-write mode
Now, the sudo sh -c "..." thing allows code execution with superuser privileges.

That’s it.

Tail recursion without TCO

Fri, 20 Aug 2010 00:00:00 -0400

Emacs lisp has no Tail Call Optimization (TCO), neither do many other lisp dialects. The lack of TCO is not a big deal—it’s always possible to transform a tail recursive algorithm into a loop. However, it makes functions look uglier. Here is a very simple method of enabling Clojure-style tail call recursion in Emacs lisp:

;; A very simple linearized Y combinator.
;; All the state management stuff is incapsulated here.
;; Don't call it directly.
(defun rloop- (body &rest args)
  (let ((res nil))
    (while (progn
             ;; here's the idea: we keep calling body 
             ;; while it returns the recursion marker
             (setq res (apply body args))
             (when (and (consp res)
                        (eq :loop-recur-marker (car res)))
               (progn (setq args (cdr res))
                      t))))
    res))

;; Recursion marker factory
(defun recur (&rest args)
  ;; instead of a real recursive call,
  ;; just signal an intention to make one
  (cons :loop-recur-marker args))

;; The form macro
(defmacro rloop (init body)
  (let ((args (mapcar 'car init)))
    ;; a little courtesy to the macro users
    `(let* ,init
       ;; make a lambda from the body and pass it 
       ;; to the combinator function
       (rloop- (function (lambda (,@args) ,body))
               ,@args))))

Here’s how to use it:

(defun factorial (x)
  ;; this is the recursion entry point
  (rloop ((x   x) 
          (acc 1))
         (if (< x 1)
             acc ;; done, just return the result
           ;; not done, start the whole rloop block again
           (recur (1- x) 
                  (* x acc)))))

ELISP> (factorial 10)
3628800

The funny part is defun is not necessary. You can have as many sequential inlined rloops as you want. I like this approach: all the state management stuff is off the sight. The function code is almost identical to the underlying algorithm. Another classic example:

(defun fibo (x)
  (rloop ((x    x)
          (curr 0)
          (next 1))
         (if (= x 0)
             curr
           (recur (1- x) 
                   next 
                  (+ curr next)))))

ELISP> (fibo 10)
55

Nice, eh? Of course, this kind of beauty comes with a price. Here is how the rloop macro expands:

ELISP> (macroexpand '(rloop ((n 0)) (if (> n 5) n (recur (1+ n)))))

(let*
    ((n 0))
  (rloop-
   #'(lambda
       (n)
       (if
           (> n 5)
           n
         (recur
          (1+ n))))
   n))

…which means two extra function calls on each iteration. But realistically, it’s not such a big deal. Clarity of the code is way more important.

Clouds and entropy

Tue, 06 Apr 2010 00:00:00 -0400

In a post titled A Trusted Cloud Entropy Authority Reuven Cohen writes:

…maybe there an opportunity to create a trusted cloud authority to provide signed verified and certified entropy. Think of it like a certificate authority (CA) but for chaos. Actually, Amazon Web Service itself could act as this entropy authority via a simple encrypted web service call. I even have a name for it, Simple Entropy Service (SES).”

This is really a good idea. Amazon should have provided such a service long time ago.

When an SSL connection is being established, a browser and a server perform the Handshake protocol. This protocol involves exchanging random bits between the parties. The important thing is that security depends on how random those bits are. If they are not, the connection is effectively insecure.

In the case of AWS, there is no source of true randomness, therefore SSL on AWS is inherently insecure. Moreover, instances running on the same physical machine can affect each other’s security by draining the shared random pool in the host system.

Further he writes:

a website called http://random.org [is] a true random number service that generates randomness via atmospheric noise. Looks cool, maybe this may help solve the problem.”

I don’t think that random.org is a good choice.

One problem is a connection to such a service. It should be as secure as the most secure secret handled on your system. If the random bit connection is encrypted with 256 bit AES (and it actually is), this is the highest level of security your system can provide. Plus, there should be guarantee that no unencryped random bits are stored anywhere. The same is true for the proposed SAS service, too.

Another problem with random.org is… well, randomness is perceptive. What you see as “random” can be quite deterministic to the people who run the random.org service. Even though they might not store anything, their present is your future—just think about relativistic effects. A temptation to tamper with someone’s future can be, you know, very strong.

The overall quality of the service is not known. There is no guarantee it is random at all. A quote from their FAQ: “Q1.2: Is the source code for the generator available? — Not currently, no. Maybe I’ll make it available as open source some day.”

Even though the Whois database indicates the domain name’s registrant is located in France, the SSL certificate owner is not specified. I have no reasons for not believing the guy running the service, but I would not entrust my customers’ data into a total stranger’s hands, even though he or she seems to be a nice person.

So the conclusion is: while there is no trusted entropy generator on the AWS side, we, the AWS customers, are on our own.

Here is a hint: entropy seeds can be generated in-house and smuggled into instances over a secure channel. Then those seeds could be fed to a cryptographically secure RNG like Isaac to produce actual “random” bits. I think there should be a way of injecting those into the instance’s random pool.

Dynamic queries: the Postgres way

Fri, 17 Jul 2009 13:00:00 -0400

Have you ever been in a situation when you needed a query to be generated and executed dynamically as a result of another query?

If yes, read further: there is a simple and elegant way to achieve that.

First, create this function:

CREATE OR REPLACE FUNCTION dselect(varchar)
  RETURNS SETOF record AS $$
    DECLARE rec record;
    BEGIN
      FOR rec IN EXECUTE $1 LOOP
        RETURN NEXT rec;
      END LOOP;
    END
  $$ LANGUAGE 'plpgsql';

Second, umm.. well, that’s it.

Anything you pass as a parameter will be interpreted and executed as an SQL statement.

The function is SELECT-able. That is, you can use it in SELECTs:

SELECT * FROM dselect('SELECT id, name FROM users') AS t(id int, name varchar);

Note the AS t(id int, name varchar) part. Postgres has no idea about what this function returns, so a column definition list should be provided. If not, Postgres will complain:

SELECT * FROM dselect('SELECT id, name FROM users');
ERROR:  a column definition list is required for functions returning "record"

Of course, the column definition list depends on the query and should match the actual query results.

So why this function is needed at all?

Because of situations like this:

CREATE SCHEMA sc_foo;
CREATE TABLE sc_foo.activity (date date, descr text);
INSERT INTO sc_foo.activity (date, descr) VALUES ('2009-08-07', 'went there');
INSERT INTO sc_foo.activity (date, descr) VALUES ('2009-06-04', 'hanging around');

CREATE SCHEMA sc_bar;
CREATE TABLE sc_bar.activity (date date, descr text);
INSERT INTO sc_bar.activity (date, descr) VALUES ('2009-10-11', 'came here');

It allows you to do this:

SELECT 
    nspname 
FROM
    pg_namespace 
WHERE
    nspname LIKE 'sc_%'  AND
    (SELECT date FROM 
        dselect('SELECT max(date) FROM ' || nspname || '.activity') AS t(date date)) &lt; '2009-09-09';

 nspname 
---------
 sc_bar
(1 row)

In one pass this query goes over all the schemas whose names start with sc_, grabs the latest date from the schema’s activity tables and matches the result against the provided date.

Of course, this approach is quite ineffective. Each time the function is called, a query is parsed and executed using a separate plan. A simple UNION of two queries would do the same, but… what if there are ten schemas? How about a hundred? I’m actually working with a database containing thousands of them.

I use this function when I need to collect statistics or do some db administration tasks, it saves me a lot of time.

Why Tk matters

Wed, 17 Dec 2008 13:00:00 -0500

Tk probably is one of the most underlooked GUI toolkits. It is a nice small toolkit which is really, I mean REALLY simple to use.

Tk by the way, has something common with Vi. Oh no, it’s not that it beeps all the time; I meant that it works everywhere. I bet you can find Tk ported to any single platform having a GUI and it will work consistently on all of them.

Tk is ubiquitous. Guess what? Almost certainly you have Tk already installed on your computer. Got Python? Go look into /usr/lib/python2.5/lib-tk, it’s right there!

Using it is very easy. Here is a ‘Hello, world’ program in Python (using Tk bindings called Tkinter):

from Tkinter import *
Label(text='Hi there').pack()

Expectedly, this program pops up a window with some text inside. Yes, it’s that simple. And this is the area where Tk shines: quick, small GUI tools.

Yet Tk is very powerful. People create big, sophisticated systems using just this toolkit. The most prominent example is definitely AC3D, a 3D modeling program.

Tk, however, has some issues. I think nobody will argue that Tk looks ugly on the Linux platform. While the Windows and Mac versions got the native look, the Linux port looks unattractive. Some work is being done in this department but it’s not quite completed.

Somebody might ask why use Tk if there is wxPython. Well, for the same reason why there are bicycles and airplanes. They are good for different purposes. Tk is way more lightweight and much easier to learn and use than wxPython.

Tk is very well documented. Here is the official Tkinter documentation with links to tutorials and such: http://docs.python.org/library/tkinter.html

If you’re going to learn Tk, it’s worth to mention that Tk is actually a part of something called Tcl/Tk. Tcl stands for Tool Command Language, a Shell-like scripting language easy to learn and fun to use. Even though all you want might be just Tkinter, some knowledge of Tcl will be rewarding.