I had a bit of time today to do some more work on that which is soon to be called something other than csnake. I’ve added a couple of features:

• You can now define custom pragmas, providing a Python handler function. Unfortunately Boost Wave, which csnake uses for preprocessing, only provides callbacks for pragmas that start with “#pragma wave”.
• Built-in pragmas and macros to support defining Python macros inline in C/C++ code.
• A main program in the csnake package. So you can now do “python3.2 -m csnake ”, which will print out the preprocessed source.

// factorial macro.
py_def(factorial(n))
    import math
    f = math.factorial(int(str(n)))
    return [Token(T_INTLIT, f)]
py_end

int main()
{
    std::cout << factorial(3) << std::endl;
    return 0;
}

Rats, looks like I didn’t do enough homework on the name “csnake”. Turns out there’s another Python-based project called CSnake: https://github.com/csnake-org/CSnake/. Incidentally - and not that it matters much - I had the name picked out before that project was released. Now I need to think up another puntastic name.

TL;DR: I’ve started a new project, csnake, which allows you to write your C preprocessor macros in Python.

Long version ahead…

You want to do what now?

I had this silly idea a couple of years ago, to create a C preprocessor in which macros can be defined in Python. This was borne out of me getting sick of hacking build scripts to generate code from data, but pursued more for fun.

I started playing around with Boost Wave, which is a “Standards conformant, and highly configurable implementation of the mandated C99/C++ preprocessor functionality packed behind an easy to use iterator interface”. With a little skulduggery coding, I managed to define macros as C++ callable objects taking and returning tokens. Then it was a simple matter of adding a Python API.


The Result

What we end up with is a Python API that looks something like this:

import sys
from _preprocessor import *
def factorial(n):
    import math
    return [Token(T_INTLIT, math.factorial(int(str(n))))]

p = Preprocessor(“test.cpp”)
p.define(factorial)
for t in p.preprocess():
    sys.stdout.write(str(t))
sys.stdout.write(”\n”)

int main(){return factorial(3);}

int main(){return 6;}

• All the cool kids are doing it: it’s the way of the future. But seriously, Python 3.x needs more projects to become more mainstream.
• Python 3.2 implements PEP 384, which allows extension modules to be used across Python versions. Finally. I always hated that I had to recompile for each version.

• A way of detecting (or at least configuring) pre-defined macros and include paths for a target compiler/preprocessor. A standalone C preprocessor isn’t worth much. It needs to act like or delegate to a real preprocessor, such as GCC.
• A #pragma to define Python macros in source, or perhaps if I’m feeling adventurous, something like #pydefine.
• A simple, documented Python API.
• A simple command line interface with the look and feel of a standard C preprocessor.
• Some unit tests.

After just a few short months since the 0.4 release, I am pleased to announce Pushy 0.5. As usual, this release is mostly bug fixes, with a couple of features to make life easier. Instructions on downloading and installing can be found here:
    http://awilkins.id.au/pushy/install.php

On top of standard bug fixes and features, I have made an effort to beautify some of the code, and speed everything up in general, based on code profiling. This will be evident if your Pushy program performs a lot of proxying: 0.5 performs up to ~2x  faster than 0.4 in my tests.


New Features

There are two new features in Pushy 0.5: with-statement support, and a simple “execute” interface.

With-statement support
Pushy connections now support the “with” statement. This is functionally equivalent to wrapping a Pushy connection with “contextlib.closing”: it will close the connection when the with-statement exits. For example:

with pushy.connect(“local:“) as con:
    …

code_obj = con.eval(“compile”)(“print ‘Hello, World!’”, “<filename>”, “exec”)
con.eval(code_obj, locals=…, globals=…)

con.execute(“print ‘Hello, World!’”)

def local_function(*args, **kwargs):
    return (args, kwargs)
remote_function = con.compile(local_function)
remote_function(…)

A workmate of mine recently brought Fabric to my attention. If you’re not familiar with Fabric, it is a command-line utility for doing sys-admin type things over SSH. There’s an obvious overlap with Pushy there, so I immediately thought, “Could Pushy be used to back Fabric? What are the benefits, what are the downsides?”

from fabric_pushy import remote_import

def get_platform():
    platform = remote_import(“platform”)
    print platform.platform()

    $ fab -H localhost get_platform
    [localhost] Executing task ‘get_platform’
    Linux-2.6.35-27-generic-i686-with-Ubuntu-10.10-maverick

    Done.
    Disconnecting from localhost… done.

from fabric.state import env, default_channel
from fabric.network import needs_host

import pushy
import pushy.transport
from pushy.transport.ssh import WrappedChannelFile

class FabricPopen(pushy.transport.BaseTransport):
    “””
    Pushy transport for Fabric, piggy-backing the Paramiko SSH connection
    managed by Fabric.
    “””

    def init(self, command, address):
        pushy.transport.BaseTransport.init(self, address)

        # Join arguments into a string
        args = command
        for i in range(len(args)):
            if “ ” in args[i]:
                args[i] = “‘%s’” % args[i]
        command = “ “.join(args)

        self.channel = default_channel()
        self.channel.exec_command(command)
        self.stdin  = WrappedChannelFile(self.channel.makefile(“wb”), 1)
        self.stdout = WrappedChannelFile(self.channel.makefile(“rb”), 0)
        self.stderr = self.__channel.makefile_stderr(“rb”)

    def del(self):
        self.close()

    def close(self):
        if hasattr(self, “stdin”):
            self.stdin.close()
            self.stdout.close()
            self.stderr.close()
        self.__channel.close()

# Add a “fabric” transport”, which piggy-backs the existing SSH connection, but
# otherwise operates the same way as the built-in Paramiko transport.
class pseudo_module:
    Popen = FabricPopen
pushy.transports[“fabric”] = pseudo_module

###############################################################################

# Pushy connection cache
connections = {}

@needs_host
def remote_import(name, python=“python”):
    “””
    A Fabric operation for importing and returning a reference to a remote
    Python package.
    “””

    if (env.host_string, python) in connections:
        conn = connections[(env.host_string, python)]
    else:
        conn = pushy.connect(“fabric:“, python=python)
        connections[(env.host_string, python)] = conn
    m = getattr(conn.modules, name)
   if “.” in name:
        for p in name.split(“.”)[1:]:
            m = getattr(m, p)
    return m

It’s been some time since I’ve spruiked Pushy, so here we go. One of my colleagues was talking the other day about how he had implemented a netcat-like service for STAF, an automation framework aimed at testing. This got me thinking about how this could be done relatively easily, using the pushy.net package, something I haven’t written about much, primarily because it’s still a work in progress.

import java.net.ServerSocket;
import java.net.Socket;
import pushy.Client;

public class Test {
    public static void main(String[] args) throws Exception {
        Client conn = new Client(“local:“);
        try {
            ServerSocket server = new pushy.net.RemoteServerSocket(conn, 0);
            try {
            } finally {
                server.close();
            }
        } finally {
            conn.close();
        }
    }
}

Socket client = server.accept();
try {
} finally {
    client.close();
}

InputStream in = client.getInputStream();
byte[] buf = new byte[1024];
int nread = in.read(buf, 0, buf.length);
while (nread != -1) {
    System.out.write(buf, 0, nread);
    System.out.flush();
    nread = in.read(buf, 0, buf.length);
}

So a couple of weeks ago I came across a forum post on XKCD about programming puzzles.Figuring that’s a significantly better way to while away the hours I’d previously been spending playing computer games, I thought I’d take a crack.

So after browsing around, I came across Facebook Puzzles, which seems to be part of Facebook’s recruitment tools. Solve some puzzles, apply for a job, and say how rad you are for having solved all of their puzzles. Something like that. Anyway, I had no intention of applying to Facebook, I just wanted to revive my fading computer science knowledge, and have a bit of fun in the progress. I don’t see what the big fuss is about working there; so many other companies are producing much more interesting, constructive things.

Naturally I went straight to the most difficult puzzle on the list, Facebull. It didn’t take long for me to realise this was an NP-hard problem. It’s fairly straight forward to see that this is a graph problem. A little more formally, we’re given a directed graph (digraph), and we’re asked to find a minimum cost strongly-connected sub-digraph, containing all vertices, but a subset of the edges.

Spoilers ahead. Turn back now if you don’t want any help.

Originally I had thought that it was the Asymmetric Traveling Salesman Problem (ATSP) in disguise, which is just the Traveling Salesman Problem (TSP) with directed edges. I spent a couple of hours here and there reading the literature, since I didn’t know anything about exact solutions (which is what the puzzle requires), and was only vaguely aware of approximation algorithms (which might help, for example, to reduce the search space.) For anyone wanting to read up on the TSP problem, I would definitely recommend the survey paper The Traveling Salesman Problem, by Jünger, Reinelt and Rinaldi. Also, this website provides a great, gentle introduction.

Not too long after, it dawned on me that the problem was not ATSP at all, since vertices (“compounds”) might be visited more than once. For example, consider a graph with the following edges:
    (C1, C2), (C2, C1)
    (C1, C3), (C3, C1)
This could not be solved by the ATSP, since we would have to visit C1 twice to complete a cycle from C1 to C2 to C3 and back to C1. However, it is required to be solvable for the Facebull puzzle. Back to the drawing board…

The general approach I took was similar to the one that would be taken for ATSP, though, and that is to use a “Branch and Bound” algorithm. This is a fancy way of saying, enumerate all possible solutions, backtracking at the earliest possible opportunity by computing lower and upper bounds. For example, we might start with an upper bound of infinity, and update it whenever we find a candidate solution with a lower cost than the upper bound. A lower bound can be computed by taking into a constraint: each vertex must have an in-degree of at least one, and an out-degree of at least one. By remembering the cost of each edge in the graph, we can easily compute a lower bound.

Is this enough? Perhaps, but we can do better. One more thing we can do is to prune edges. For example, if we have the edges (Ci, Cj), (Ci, Ck), and (Ck, Cj), and the sum of the cost of the latter two is less than the cost of the first, then we can eliminate the first.

In total, I submitted my solution nine times. Why so many, you might ask? Because I didn’t parse the input correctly, and didn’t realise this while I was banging my head against the problem for two weeks. I wasn’t handling white space at the end of the file, and I (foolishly) assumed that the test cases would not assign multiple edges to the same pair of vertices. Why would you have such a trivial test case to trip people up, when the underlying puzzle is hard enough as it is? It turns out my accepted solution (written in C++) ran in 300ms, so I guess the focus was more or less centred on correctness, rather than speed. That was a little frustrating, but at least I had some fun and learnt a few tricks along the way.

There is still something wrong with my solution, however. It is not finding the optimal solution to some of the test cases people have published. But it passed the puzzle robot, so that’s the main thing that matters. I had one more optimisation, which was to identify edges which are absolutely required, up-front. This can be done very cheaply, and may significantly reduce the search space in sparse graphs. This optimisation was interacting badly with my enumeration function, though; I’m not sure what the problem is, perhaps I’ll go back and take another look some time.

Now, back to wasting my time playing computer games…

So, I finally got around to writing some proper documentation for Pushy.

I had originally used Epydoc to extract docstrings, and generate API documents, which I have been hosting. Then I realised I could publish HTML to PyPI, so I thought I’d do something a little more friendly than presenting the gory details of the API.

In the past I’ve used Asciidoc, a lightweight markup language, in the vein of Wiki markup languages. I found Asciidoc fairly simply to write, and there is a standard tool for processing and producing various output, including of course HTML. I wanted to make my documentation to have the look and feel of the Python standard library, so I’ve been looking into reStructuredText.

I have to say that reStructuredText is very easy to learn, and Sphinx, which is the processing tool used to generate the HTML output for the Python documentation, is a pleasure to use. The format of reStructuredText is similar to that of Asciidoc. So far I don’t have any particular affinity to either - I mainly went with reStructuredText/Sphinx for the Python documentation theming.

Did you ever want to call Python code from Java?

Until Java 5, I wasn’t much of a fan of the Java language. The addition of enums, generics, and some syntactic sugar (e.g. foreach) makes it more bearable to develop in. But all of this doesn’t change the fact that Java purposely hides non-portable operating system functions, such as signal handling and Windows registry access. Sure, you can do these things with JNI, but that makes application deployment significantly more complex.

Python, on the other hand, embraces the differences between operating systems. Certainly where it makes sense, platform-independent interfaces are provided - just like Java, and every other modern language. But just because one platform doesn’t deal in signals shouldn’t mean that we can’t use signals on Linux/UNIX.

I realise it’s probably not the most common thing to do, but calling Python code from Java needn’t be difficult. There’s Jython, which makes available a large portion of the Python standard library, but still has some way to go. Some modules are missing (e.g. _winreg, ctypes), and others are incomplete or buggy. That’s not to say that the project isn’t useful, it’s just not 100% there yet.

Enter Pushy (version 0.3). In version 0.3, a Java API was added to Pushy, making it possible to connect to a Python interpreter from a Java program, and access objects and invoke functions therein. So, for example, you now have the ctypes module available to your Java program, meaning you can load shared objects / DLLs and call arbitrary functions from them. See below for a code sample.

import pushy.Client;
import pushy.Module;
import pushy.PushyObject;

public class TestCtypes {
    public static void main(String[] args) throws Exception {
        Client client = new Client(“local:“);
        try {
            // Import the “ctypes” Python module, and get a reference to the
            // GetCurrentProcessId function in kernel32.
            Module ctypes = client.getModule(“ctypes”);
            PushyObject windll = (PushyObject)ctypes.getattr(“windll”);
            PushyObject kernel32 = (PushyObject)windll.getattr(“kernel32”);
            PushyObject GetCurrentProcessId =
                (PushyObject)kernel32.getattr(“GetCurrentProcessId”);

            // Call GetCurrentProcessId. Note that the Python interpreter is
            // running in a separate process, so this is NOT the process ID
            // running the Java program.
            Number pid = (Number)GetCurrentProcessId.call();
            System.out.println(pid);
        } finally {
            client.close();
        }
    }
}

• Connecting a Java program to a freshly created Python interpreter on the local host.
• Importing the ctypes module therein, and then getting a reference to kernel32.dll (this assumes Windows, obviously. It would be much the same on Linux/UNIX platforms.)
• Executing the GetCurrentProcessId function to obtain the process ID of the Python interpreter, and returning the result as a java.lang.Number object.