Archive for March, 2010

"di" con i sostantivi

March 21st, 2010

Sto pensando all'uso della preposizione "di" con dei (eccomi!) sostantivi. È una cosa piuttosto strana per non averla in nessuna delle lingue da me conosciute.

Mi fa venire in mente la situazione in cui le persone, la cui lingua materna è slava (il russo, il polacco..), stanno imparando una lingua germanica. In alcune lingue non esistono articoli da usare con i sostantivi, perciò qualcuno scriverà "Ho visto macchina" anziché "una macchina" oppure "la macchina". L'articolo non ti serve se non l'hai mai usato prima. Certamente non capiresti il perché bisognerebbe usarlo nella forma indeterminativa oppure determinativa.

Per chi conosce una lingua germanica oppure romanza usa gli articoli perché sembrano appartenere ai sostantivi. Senza di loro, c'è qualcosa che manca. Allo stesso modo, immagino, per chi parla italiano usare la preposizione "di" con i sostantivi è normale.

Per noi "germanici" questa è una stranezza. Io tento di metterla quando mi sembra possibile, ma non so esattamente come cambia il significato, o se è veramente necessario.

Direi che sottintende più o meno una quantità di qualcosa non meglio specificata.
- Ho comprato un nuovo televisore.
- Ci sono (dei) programmi interessanti?

- Vuoi (dell')acqua?

- Che fai nel tempo libero?
- Leggo (dei) libri.

Come sarebbe escludendo "di"? Cambierebbe il significato?

aopy: aspect oriented python

March 12th, 2010

Aspect oriented programming is one of those old new ideas that haven't really made a big impact (although perhaps it still will, research ideas sometimes take decades to appear in the professional world). The idea is really neat. We've had a few decades now to practice our modularity and the problem hasn't really been solved fully (the number of design patterns that have been invented I think is telling). What's different about AOP from just plain old "architecture" is the notion of "horizontal" composition. That is to say you don't solve the problem by decomposing and choosing your parts more carefully, you inject code into critical places instead. The technique is just as general, but I would suggest differently applicable.

I realized I haven't really explained anything yet, so let's look at a suitably contrived example.

A network manager

Suppose you're writing a network manager type of application (I actually tried that once). You might have a class called NetworkIface. And the class has an attribute ip. So how does ip get its value? Well, it can be set statically, or via dhcp. In the latter case there is a method dhcp_request, which requests an ip address and assigns to ip.

# <./main.py>
class NetworkIface(object):
    def __init__(self):
        self.ip = None

    def dhcp_request(self):
        self.ip = (10,0,0,131) # XXX magic goes here


if __name__ == '__main__':
    iface = NetworkIface()
    iface.ip = (10,0,0,1)
    iface.ip = (10,0,0,2)
    iface.dhcp_request()

Now suppose you are in the course of writing this application, and you need to do some debugging. It would be nice to know a few things about NetworkIface:

  1. The dhcp server seems to be assigning ip addresses to clients in a (possibly) erroneous manner. We'd like to keep a list of all the ips we've been assigned.
  2. Sometimes the time between making a dhcp request and getting a response seems longer than reasonable. We'd like to time the execution of the dhcp_request method.
  3. Some users are reporting strange failures that we can't seem to reproduce. We would like to do exhaustive logging, ie. every method entry and exit, with parameters.

Now, this kind of debugging logic, however we realize it, is not really something we want in the release version of the application. It doesn't belong. It belongs in debug builds, and we're probably not going to need it permanently.

Here we will demo how to achieve the first point and omit the other two for brevity.

Where AOP comes in

Common to these issues is the fact that they all have to do with information gathering. But that's not necessarily the only thing we might want to do. We might want to tweak the behavior of dhcp_request for the purpose of debugging. For instance, if it took too long to get an ip, we could set one statically after some seconds. Again, that would be a temporary piece of logic not meant to be in the release version.

Now, AOP says "don't change your code, you'll only make a mess of it". Instead you can write that piece of code you need to write, but quite separately from your codebase. This you call an aspect, with the intention that it captures some aspect of behavior you want to inject into your code. And then, during compilation from source code to bytecode (or object code) you inject the aspect code where you want it to go. Compiler? Yes, AOP comes with a special compiler, which makes injection very toggable. Want vanilla code? Use the regular compiler. Want aspected code? Use the AOP compiler.

How does the compiler know where to inject the aspect code? AOP defines strategic injection points called join points. Exactly what these are depends on the programming language, but typically there is a join point preceding a method body, a join point preceding a method call, a method return and so on. (As we shall see, in aopy we are being more Pythonic.) Join points are defined by the AOP framework. But how do you tell it to inject there? With point cuts. A point cut is a matching string (ie. regular expression) which is matched against every join point and determines if injection happens there.

Back to you, John

Enough chatter, the code is getting cold! As it happens, Python has first rate facilities for writing AOP-ish code. We already have language features that can modify or add behavior to existing code:

  • Properties let us micromanage assignment to/reading from instance variables.
  • Decorators let us wrap function execution with additional logic, or even replace the original function with another.
  • Metaclasses can do just about anything to a class by rebinding the class namespace arbitrarily.

We will use these language constructs as units of code injection, called advice in AOP. This way we can reuse all the decorators and metaclasses we already have and we can do AOP much the way we write code already. Let's see the aspects then.

A caching aspect

The first thing we wanted was to cache the values of ip. For this we have a pair of functions which will become methods in NetworkIface and make ip a property.

# <aspects/cache.py>
class Cache():
    def __init__(self):
        self.values = set()
        self.value = None
cache = Cache()

def get(self):
    return cache.value

def set(self, value):
    if value:
        print "c New value: %s" % str(value)
    if any(cache.values):
        prev = ", ".join([str(val) for val in cache.values])
        print "c  Previous values: %s" % prev
    if value:
        cache.values = cache.values.union([value])
    cache.value = value

Cache is the helper class that will store all the values.

A spec

Aspects are defined in specification files which provide the actual link between the codebase and the aspect code.

# <./spec.py>
import aopy

import aspects.cache

caching_aspect = aopy.Aspect()
caching_aspect.add_property('main:NetworkIface/ip', 
    fget=aspects.cache.get, fset=aspects.cache.set)

__all__ = ['caching_aspect']

We start by importing the aopy library and the aspect code we've written. Then we create an Aspect instance and call add_property to add a property advice to this aspect. The first argument is the point cut, ie. the matching string which defines what this property is to be applied to. Here we say "in a module called main, in a class called NetworkIface, find a member called ip". The other two arguments provide the two functions we wish to use in this property.

Compiling

To compile the aspect into the codebase we run the compiler, giving the spec file. And we give it a module (or a path) that indicates the codebase.

$ aopyc -t spec.py main.py
Transforming module /home/alex/uu/colloq/aopy/code/main.py
Pattern matched: main:NetworkIface/ip on main:NetworkIface/ip

The compiler will examine all the modules in the codebase (in this case only main.py) and attempt code injection in each one. Whenever a point cut matches, injection happens. The transformed module is then compiled to bytecode and written to disk (as main.pyc).

main.pyc now looks like this:

# <./main.py> transformed
import sys ### <-- injected
for path in ('.'): ### <-- injected
    if path not in sys.path: ### <-- injected
        sys.path.append(path) ### <-- injected

import aspects.cache as cache ### <-- injected

class NetworkIface(object):
    def __init__(self):
        self.ip = None

    def dhcp_request(self):
        self.ip = (10,0,0,131) # XXX magic goes here
    
    ip = property(fget=cache.get, fset=cache.set) ### <-- injected


if __name__ == '__main__':
    iface = NetworkIface()
    iface.ip = (10,0,0,1)
    iface.ip = (10,0,0,2)
    iface.dhcp_request()

Injected lines are marked. First we find some import statements that are meant to ensure that the codebase can find the aspect code on disk. Then we import the actual aspect module that holds our advice. And finally we can ascertain that NetworkIface has gained a property, with get and set methods pulled in from our aspect code.

Running aspected

When we now run main.pyc we get a message every time ip gets a new value. We also get a printout of all the previous values.

c New value: (10, 0, 0, 1)
c New value: (10, 0, 0, 2)
c  Previous values: (10, 0, 0, 1)
c New value: (10, 0, 0, 131)
c  Previous values: (10, 0, 0, 1), (10, 0, 0, 2)

And the yet the codebase has not been touched, if we execute main.py instead we find the original code.

Here the show endeth

And that wraps up a hasty introduction to AOP with aopy. There is a lot more to be said, both about AOP in Python and aopy in particular. Interested parties are kindly directed to these two papers:

  1. Strategies for aspect oriented programming in Python
  2. aopy: A program transformation-based aspect oriented framework for Python

If you prefer reading code rather than English (variable names are still in English though, sorry about that), here is the repo for your pleasure:

And if you still have no idea what AOP is and think the whole thing is bogus then you can watch this google talk (and who doesn't love a google talk!) by mr. AOP himself.

python patterns for graph traversal

March 8th, 2010

python_graphtraversal_picGraphs, they are fun. You can use them for all sorts of things, like drawing a picture of the internet (or your favorite regular expression!)

For example, look at that handsome guy there on the right. Is that a gorgeous graph, or what? (Incidentally, if you aren't yet a fan of graphviz, it's time to become one, it's superb!)

Now take a gander at the code snippet below, that's the python representation of it.

class Node(object):
    def __init__(self, name):
        self.name = name

a, b, c, d = Node('a'), Node('b'), Node('c'), Node('d')
a.refs = [b, d]
b.refs = [c]
c.refs = [a]
d.refs = []

But it's not there just to be stared at, so let's do something with it! One thing we could do is go over the graph and print out the nodes. But let's do one better, let's also show how deep into the graph we are by indenting the output! What we want is this:

a
__b
____c
__d

We don't have the nice arrows here, but you can still make out the shape of the graph.

First iteration

def traverse_naive(node, depth):
    print('__'*depth + node.name)
    for ref in node.refs:
        traverse_naive(ref, depth+1)

Very simple. Print the name of the node at the current level of depth, and then recurse down the outgoing edges. But when we run this something bad happens:

>>> traverse_naive(a, 0)
a
__b
____c
______a
________b
..
RuntimeError: maximum recursion depth exceeded

There's no sign of d, instead we keep going round and round along the path a-b-c-a. Woops.

Preempting cycles

Traditionally, graph traversal algorithms have set properties on nodes in the graph to indicate to themselves that a particular node had been seen before. For example, we could set node.been_here_before = True every time we enter a node, and then we could check for this property to make sure we don't re-enter the node later.

But this is not awesome, because we then have to change the graph as we traverse it. What if we want to traverse it again later, do we then need another traversal algorithm to remove all the markers or what?

There is another way to do this, however. We can use a data structure completely outside the graph in which we keep track of what we've seen so far (imagine a guy walking around a warehouse with a clipboard, he then doesn't have to mark any of the merchandise!).

So instead of checking the value of node.been_here_before, we're going to check the value of cache[node].

Now, there are two main strategies for where to do this check. We can do it right before the recursive call, or right after.

def traverse_check_before(node, depth, cache):
    cache[node] = None

    print('__'*depth + node.name)
    for ref in node.refs:
        # we are about to recurse, first check if the node we want
        # to recurse on is in the cache
        if ref in cache:
            print('Already in cache: %s' % ref.name)
            continue
        # recurse if we reach this point
        traverse_cached(ref, depth+1, cache)


def traverse_check_after(node, depth, cache):
    # we have just recursed, return if this node is already in
    # the cache
    if node in cache:
        print('Already in cache: %s' % node.name)
        return
    cache[node] = None

    print('__'*depth + node.name)
    for ref in node.refs:
        # recurse without exception
        traverse_cached(ref, depth+1, cache)

Here it doesn't matter which one we use, so we're just going to use the second option.

Second iteration

At this point you might be thinking that everything is going swimmingly, but in fact a small problem has crept up. It cannot have escaped your attention that we've snuck another parameter into that function definition. This means that we have to call the function like this:

>>> traverse_check_after(a, 0, {})
a
__b
____c
Already in cache: a
__d

The function works, but we really, really don't want to have to do it like this. There is no reason the caller has to know about the cache, let alone that it is a dictionary. And if we ever decide to change the cache mechanism, we have to update all the client code.

So what can we do? We can't set up the cache in the function body, because the function is recursive!

This is where you might get that look in your eye that you get when you're being clever. Hah, but what about this:

def traverse_cached(node, depth, cache={}):
    if node in cache:
        print('Already in cache: %s' % node.name)
        return
    cache[node] = None

    print('__'*depth + node.name)
    for ref in node.refs:
        traverse_cached(ref, depth+1, cache=cache)

Brilliant! We don't have to set up the cache neither inside the function body nor at the call site. This cache has to be initialized somewhere between the call and the function being executed, but somehow we've found a magical in-between, haven't we!

Keyword parameters really are a tremendous boon, but unfortunately they will not save our skin this time. Do you know what happens if we do this?

>>> traverse_cached(a, 0)
>>> traverse_cached(a, 0)

Read and weep:

>>> traverse_cached(a, 0)
a
__b
____c
Already in cache: a
__d
>>> traverse_cached(a, 0)
Already in cache: a

Keyword parameters

Keyword parameters don't do what you thought they did. You thought traverse_cached would get a new dictionary every time it was called without a cache argument. But that's not what happens. (But isn't python magical???)

In fact, it works like this. The cache keyword parameter gets initialized once and for all when the function is compiled. Since the value it is set to is an empty dictionary, the dict object is initially empty. But every time you call the function, it's the same dictionary that gets passed in!

Third iteration

It's come to this, I'm afraid. The problem is unsurmountable. We can't not pass the cache parameter. But we definitely don't want to do it at the call site. Which leaves no other option than...

def traverse_cached_fixed(node, depth):
    def rec(node, depth, cache):
        if node in cache:
            print('Already in cache: %s' % node.name)
            return
        cache[node] = None

        print('__'*depth + node.name)
        for ref in node.refs:
            rec(ref, depth+1, cache)
    rec(node, depth, {})

I really hate using an inner function just for this. It makes it messier, you have to route the arguments through an extra function call. But that's the price you pay, I'm afraid.

Postscript

By now you must be fuming at the fact that I've come all this way while pretending that the function call didn't have another parameter that was completely pointless and indeed deserving of the very same criticism.

Well, the difference is that you can set depth=0 as a keyword parameter in the function definition, so that you don't have to pass it. And this doesn't break anything. But why??

The answer is found when poking around python. A function is in fact a mutable object. Have a look:

def f(a=0):
    a = 1

>>> print f.func_defaults
(0,)

func_defaults is the tuple that stores the values of the keyword parameters which have a default value. The value we see here is the integer 0, and it will not change no matter how many times we execute the function.

But collection types (and your own types too) are different:

def g(a=[]):
    a.append(1)
    print a

>>> print g.func_defaults
([],)
>>> g()
[1]
>>> print g.func_defaults
([1],)
>>> g()
[1, 1]

Despite different, it actually works the same way (sorta). The binding of the keyword default is constant. But with an integer, the parameter is bound to the constant 0, whereas with "heavier" objects, it is bound to the object, but the object's inner properties can very well mutate!!!

we assume that you said yes

March 7th, 2010

It seems I'm late to the party. I read the call to arms on Ars Technica this morning (a site I like a lot, I have to say, although I don't really visit much), and I immediately felt like I should have some reaction to it. I've made a pass or two over the topic in the past, and so I felt hooked in. But nothing came to mind with immediate effect. So I put it away until I saw Brian's shot heard around the world on Planet Larry. And that's when it finally hit me what this whole thing is about.

Ars Technica is bending over backwards not to make The Big Accusation, namely "if you skip the ads you are stealing". And yet they still try to guilt trip you saying "well gosh, our business is on the line here, y'know?".

I don't know where Al Gore is, but there is a highly Inconvenient Truth here. And it is this: publishers are working from the assumption that the viewer has implicitly agreed to make them money without ever agreeing to it. This is why the Ars Technica article has to do that weird dance around the issue where they're not calling you a cheat, but then they are, but then they're not etc. Because if they did just come out and say it, they couldn't look themselves in the mirror, because they have more self respect than certain muppets.

Ars Technica couldn't live with themselves if they actually came out and said: Dear viewer, when we built this site we made the assumption that you would help us pay for it by looking at our ads. We never ran this by you, but we take it for granted that you have accepted this deal. Now we expect you to honor it.

There are others who are not so "modest", like the entertainment industry claiming billions in damages based on sales they would have had if the people who downloaded stuff had paid for it. Here again, the assumption is that the consumer agreed to pay for something, and then refused. So who's being cheated? The publisher!

But the viewer agreed to no such thing.

non devi scrivere per migliorare

March 5th, 2010

Chi impara le lingue sul serio probabilmente conosce il nome Krashen, o almeno conosce il principio per il quale lui è noto. È lo stesso che si trova alla base dei metodi di noti poliglotti come alljapaneseallthetime.com e Steve Kaufmann. Il principio si chiama "The input hypothesis", che si potrebbe tradurre in "L'ipotesi del osservatore".

Veramente è molto semplice. Si tratta di un lungo periodo durante il quale non fai nient'altro che osservare la lingua che vuoi conoscere. Puoi non capire neanche una parola, tuttavia si dice che i nostri cervelli siano stati formati per migliaia d'anni precisamente per eseguire questo compito (tra altri, naturalmente). Così dovrebbe bastare osservare (come fanno i bambini), e piano piano cominciare a capire qualcosa. Persino Noam Chomsky ha detto che non sarebbe possibile per i bambini imparare le lingue senza avere qualche meccanismo impiantato in testa per farlo, perché quasi mai si sono trovati dei casi in cui delle persone abbiano fallito ad imparare la lingua materna, in qualsiasi circostanza si fossero trovati nella vita.

Inoltre, si dice che non è per niente consigliato per chi vuole imparare di fare pratica al più presto possibile, come si fa abitualmente nei corsi di lingue. Se accettiamo l'idea che impari da ciò che osservi, vuol dire che verrai ad imparare dai tuoi stessi errori, e quanto più li ripeti tanto più saranno rafforzati. Questo può sembrare un po' sconvolgente, non diresti?

Ma Krashen ha anche condotto una ricerca sull'abilità dello scrivere. Ritiene che - e questo è molto interessante, visto che lo sto facendo proprio adesso - non si guadagna nello scrivere, non ce n'è bisogno per migliorare! La verità è che non ho ancora scritto molto in italiano, per lo più sono stato.. ad osservare. Leggo dei libri, guardo la tv. E il fatto è che nello scrivere ho migliorato - direi - molto, tra una volta e l'altra. Quindi non è stata la scrittura a farlo, ma probabilmente è stata l'osservazione.