A Kind of Informal Introduction to π-Calculus

The π-Calculus is one of many approaches to concurrent computation by the means of formal modeling. Its purpose is to enable us to reason about concurrent processes in a disciplined fashion by manipulating expressions through formally defined algebraic rules.

Any exposition of the calculus will eventually introduce you to the primitive notions:

• Agents, which can be understood and even referred as processes.
• Actions, which are anything that can be done by an agent.
• Channels, which are links connecting agents, alowing them to communicate.
• Names, which are exchanged through channels.

The general idea is that we have a set of agents connected to each other through channels in some sort of network. These agents then use these channels communicate to each other by exchanging names.

The role of communication is central to the π-Calculus. In fact, there are only three possible actions for an agent to perform, and two of them regard communication:

• The Output action x̅a: The name a is sent through the channel x.
• The Input action x(a): The name a is bound to whatever is received through channel x.
• The Silent action τ: Any action internal to the agent (i.e. involving no communication).

Now that we have actions, we can already build some agents:

• The Nil, empty agent 0.
• The Prefix α.P that executes the action α and then continues as the agent P.
• The Restriction (νx)P that behaves as P having the name x in its local scope.
• The Parallel Composition P|Q that behaves as agents P and Q executing in parallel.
• The Sum P+Q that can behave either as P or Q (but not both).
• The Match [x=y].P that behaves as P if x and y are the same name.
• The Mismatch [x≠y].P that behaves as P if x and y are not the same name.

This may be a bit too abstract, but a small example will hopefully help: suppose we have a printer P, a server S and a client C. We would like to have a name sent by the client printed by the printer. We also define that the server is connected to the client by a channel y and to the printer by a channel x.

To achieve our goal, C should send a name to S which, in turn, should forward it to P. We can write:

C|S|P, where

• C=(νa)y̅a
• S=y(b).x̅b.S
• P=x(c).τ.P

Notice two things:

• First, although the client agent terminates after sending its message, the server and printer agents return to their initial state.
• Second, all communication in the π-Calculus is synchronous, so an agent sending a message will remain blocked until some other agent receives the message. Also, an agent listening on a channel for a name will remain blocked until a message is actually sent through this channel.

At this point, we’re ready to talk about what makes the calculus really powerful: in π-Calculus, all channels are names, which means that they can be sent through other channels just like any ordinary name. That’s really important: an agent receiving a name that is also a channel may now use this received channel to communicate with other agents. Essentially, such interactions modify the network between the agents in the computation. This is called dynamic reconfiguration.

We can illustrate this phenomenon by modifying our previous example. Previously, we had the client sending the message to the printer through the server. Now, we’ll have the client to send the message directly to the printer through a channel provided by the server. We’ll write:

C|S|P, where

• C=(νa)y(z).z̅a
• S=y̅(x).S
• P=x(c).τ.P

And that’s enough for now. A lot more can be found in the book written by Robin Milner, the main author of π-Calculus. I also find Parrow’s paper very readable.

Implementing interface contracts in Python with class decorators

Python decorators are quite useful and interesting. I've already written about function decorators in a previous post and class decorators are a worthy followup.

I order to illustrate this feature, we'll implement support for interface contracts for Python classes. In a language like Java, for instance, a contract can be declared this way:

public interface Comparable {
    public int compareTo(T o);
}

And a class declared as an implementation of this interface must provide the relevant methods (with the correct signature). Otherwise, a compilation error arises. For instance:

public final class Integer extends Number implements Comparable<Integer> {

    ...
    
    public int compareTo(Integer anotherInteger) {
        int thisVal = this.value;
        int anotherVal = anotherInteger.value;
        return (thisVal<anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1));
    }

    ...

}

We'll try to achieve a similar feature in Python, albeit with some limitations. First, as Python does not have an explicit compilation step, our errors will only arise in runtime. Second, in Python, the types of the arguments and return values aren't present in the signature of methods, so we'll leave it out too. This is a notable absence, but we can still verify the presence of desired methods in the implementer type and the following elements in the method's signature:

• Name


• Number of arguments


• Name of arguments (as Python supports named parameters)


• Default values for arguments (as Python supports default arguments)


• Support for variadic functions (indefinite number of arguments)

This said, we now have to declare our interfaces. I picked the following (somewhat cumbersome) syntax:

class some_interface(interface):
    simple_method = method(['self'])
    method_with_args = method(['self', 'arg1', 'arg2'])
    method_with_varargs = method(['self'], varargs='varargs')
    method_with_kwargs = method(['self'], keywords='kwargs')
    method_with_default_argument = method(['self', 'default_arg'], defaults=1)

Here we have an ordinary class subtyping an interface class. The methods are defined as attributes of the some_interface class, holding instances of the method class.

The interface class isn't really exciting or even necessary. Actually, it exists for the sole purpose of tagging an interface contract as such:

class interface(object):
    pass

The method class holds the method signature.

class method(object):
    def __init__(self, args=None, varargs=None, keywords=None, defaults=0):
        self.args = args or []
        self.varargs = varargs
        self.keywords = keywords
        self.defaults = defaults

Notice that the constructor takes a few arguments:

• args — the list of arguments


• varargs — the name of the list holding extra arguments, if any


• kwargs — the name of the dictionary holding extra named arguments, if any


• defaults — the number of arguments with a default value

Now we can create a new type implementing some_interface. And it follows:

@implements(some_interface)
class some_class(object):
    
    def simple_method(self):
        pass

    def method_with_args(self, arg):
        pass
    
    def method_with_varargs(self, *varargs):
        pass
    
    def method_with_kwargs(self, **kwargs):
        pass
    
    def method_with_default_argument(self, default_arg=100):
        pass

Notice that we declare the class as implementing the contract through the implements class decorator.

First thing we have to observe is the initialization of the implements decorator. Once the decorated class is loaded by the interpreter, an instance of the decorator is produced. The argument some_interface is passed to the constructor during the initialization (and it's stored as an attribute for future reference).

class implements(object):
    
    def __init__(self, interface):
        self.interface = interface
    
    ...

Then, the __call__ method of the decorator is invoked. The decorated class (some_class in this example) is passed as argument. In this method, it is verified whether the given class satisfies all of its contractual obligations. If no problem arises, the class is returned at the end of the call.

class implements(object):
    
    ...
    
    def __call__(self, clazz):
        methods = [each for each in dir(self.interface) if self._is_method(each)]
        for each in methods:
            self._assert_implements(clazz, each)
        return clazz
    
    ...

Notice that the _assert_implements method is called against each method declared in the interface. This method, listed ahead, verifies whether the given method, as implemented by the class, has the desired signature, as specified in the interface. In case it doesn't, an exception is raised (effectively interrupting the program).

class implements(object):
    
    ...
    
    def _assert_implements(self, clazz, method_name):
        method_contract = object.__getattribute__(self.interface, method_name)
        method_impl = getargspec(object.__getattribute__(clazz, method_name))
        assert method_name in dir(clazz)
        assert method_contract.args == method_impl.args
        assert method_contract.varargs == method_impl.varargs
        assert method_contract.keywords == method_impl.keywords
        if (method_impl.defaults is not None):
            assert method_contract.defaults == len(method_impl.defaults)
        else:
            assert method_contract.defaults == 0
    
    ...

The object.__getattribute__() (documentation) call is one thing worth of note as it is part of Python's introspection features and targeted at retrieving attributes from classes and objects. Here, it's used both to retrieve method objects from the interface and and to obtain references to the actual methods in the concrete class (the clazz argument).

The getargspec function (documentation) is also an interesting introspection feature. Given a function, it will return an object with information about the given function's signature.

So, having both the expected signature from the method object hosted in the interface and the signature of the method implemented in the concrete class, we can simply compare them both and hope for a match.

(Postscript: although the source code presented above works fine, it's actually a shorter version of the code originally developed for the purpose and available here.)

Dependency Injection in Ruby as inspired by Scala

A recent discussion in the GOOS' group has lead me to consider different ways to compose objects in Ruby. Specifically, as module inclusion seems to be the favored approach for adding stuff to classes in Ruby, I've became interested in finding a more flexible idiom for this.

The objective, therefore, is to define an instance variable in a module and be able to have it injected in instances of some class. Of course, as a Ruby noob, I'm forced to turn to other languages for inspiration. The solution in Scala, presented ahead, is kind of intuitive (I guess it can be considered a variation of the Cake pattern).

Let's start defining a simple trait Lightsource.

trait Lightsource {
  def on
  def off
}

The goal is to have a instance of a class implementing this trait injected in every instance of the class Room below.

abstract class Room {
  val lightsource:Lightsource
  def enter = lightsource.on
  def leave = lightsource.off
}

The injection can be performed by mixing-in the Room class with traits designed to provide a Lightsource. For example:

trait FluorescentLamp {
  val lightsource = new Lightsource {
    def on = println("Sad light on")
    def off = println("Sad light off")
  }
}

The actual composition reads nicely:

val sadRoom = new Room with FluorescentLamp

If the fluorescent lamp is unsatisfactory, an alternative implementation can be provided:

trait IncandescentLamp {
  val lightsource = new Lightsource {
    def on = println("Warm light on")
    def off = println("Warm light off")
  }
}

val warmRoom = new Room with IncandescentLamp

And I will stop at this point. Although there is opportunity for improvement, the implementation is satisfactory enough for me.

Having succeeded at the Scala front, we can tackle the same issue using Ruby. Here, we find ourselves both unable and not required to declare interfaces, so we move directly to the definition of our Room class.

class Room
  
  def enter
    @lightsource.on
  end
  
  def leave
    @lightsource.off
  end
  
end

The next step is to define a module responsible for providing an @lightsource object to instances of the Room class. For instance:

module FluorescentLamp
  class FluorescentLampImpl
    def on
      puts "Sad light on"
    end
  
    def off
      puts "Sad light off"
    end
  end
  
  def initialize(*args, &b)
    super
    @lightsource = FluorescentLampImpl.new
  end
end

Alternatively:

module IncandescentLamp
  class IncandescentLampImpl
    def on
      puts "Warm light on"
    end
  
    def off
      puts "Warm light off"
    end  
  end
  
  def initialize(*args, &b)
    super
    @lightsource = IncandescentLampImpl.new
  end
end

The actual composition does not read so nicely, but surely it can be improved by some sort of DSL. Being lazy, I'll skip that, though:

sadRoom = Class.new(Room) do
  include FluorescentLamp
end.new

warmRoom = Class.new(Room) do
  include IncandescentLamp
end.new

Now, I'm suppose that this approach is not really within Ruby's orthodoxy, but I found it interesting nevertheless. Also, it surprised me that the Scala version is both cleaner and smaller than the Ruby version, while still providing the safety advantages of the static typing. Perhaps someone more skilled in Ruby might improve upon this.

In which I give my own half-baked workaround to the lack of tail call optimization in Python

A tail call is a function call such that it is the last action performed by a procedure. Therefore, the value returned by the caller procedure is the value returned by the called procedure. Many compilers and interpreters take advantage of this situation by using the caller's stack space to execute the called procedure, instead of allocating more space for it. Because no extra space is consumed by these calls, recursive tail calls can be nested at will without risk of overflowing the stack.

Unfortunately, Python's interpreter does not perform this optimization trick. This can be easily learned from the example bellow:

>>> def f(x):
...     if (x>0): return f(x-1)
...     else: return 0
... 
>>> f(10)
0
>>> f(1000)
Traceback (most recent call last):
  File "", line 1, in 
  File "", line 2, in f
  ...
  File "", line 2, in f
RuntimeError: maximum recursion depth exceeded

This limitation in the interpreter is unlikely to disappear anytime soon, if at all. But, as tail call optimization is often very convenient, many workarounds were written. These workarounds, with different levels of success, make use of decorators (which are functions that are executed before the decorated function) to control the execution of function calls.

This post presents yet another solution, also based on decorators. The objective here is to avoid any limit on the number of recursive tail calls performed by a function by decorating it like bellow.

@tail_recursive
def f(x):
    if (x>0): return f(x-1)
    else: return 0

Every call to f, then, will be intercepted by the decorator. Depending on the situation, it may continue and execute the function as usual, or return an object that may be used to perform the issued call later. The next listing presents the class for these objects (note that they store both a reference to a function and the arguments for a specific call).

class _continue(object):
    
    def __init__(self, func, *args, **kwargs):
        self.func = func
        self.args = args
        self.kwargs = kwargs

Each call to a decorated function f implies on a independent run of the decorator code. On the first call, the decorator will allow f to be executed, but instead of returning immediately, it will await for _continue objects to execute them. Subsequent tail-recursive calls to f, on the other hand, will just return an instance of _continue filled with the call arguments without executing f. Non tail-recursive are allowed to proceed unmolested.

This approach keeps the stack from growing by avoiding nested calls whenever possible. Still, detecting recursion and tail recursion are tricky jobs. The former is performed by checking if penultimate frame in the stack refers to our decorator. The later is performed by checking whether the bytecode associated with the previous stack frame will return immediately after the completion of the call.

The source code for the decorator follows. An instance of it is produced for each decorated function, and the method __call__ is executed on every invocation of them.

OPCODES = [chr(opmap['RETURN_VALUE']), chr(opmap['POP_TOP'])]

class tail_recursive(object):

    def __init__(self, function):
        self.function = function
        
    def _is_tailcall(self, frame):
        caller_frame = frame.f_back
        code = caller_frame.f_code.co_code
        ip = caller_frame.f_lasti
        return code[ip + 3] in OPCODES

    def __call__(self, *args, **kwargs):
        
        frame = getframe()
        
        if frame.f_back and \
            frame.f_back.f_back and \
            frame.f_back.f_back.f_code == frame.f_code and \
            self._is_tailcall(frame):
            return _continue(self.function, *args, **kwargs)
        
        retval = self.function(*args, **kwargs)
        while (True):
            if (type(retval) == _continue):
                retval = retval.func(*retval.args, **retval.kwargs)
            else:
                return retval

(The entire code, with tests, is available here.)

Of course, this isn't true tail call optimization, but only a trick to achieve unlimited tail recursion. Properly implemented, the optimization should also provide increased performance by reducing the work needed to perform a function call; here, performance is actually harmed.