Efficiency of the different implementations of integer->roman

In this post we explored different ways to express an algorithm in scheme, ranging from very functional to very imperative. Scheme is a hybrid language, like Python (here and here in python). The scheme implementations have been described here.

Usually we think imperative solutions are faster. About this common misconceptions, I advise reading Okasaki's "Purely functional data structures"[0][1].

I decided to time the operations. Given a single implementation, I run each function on each number from 1 to 2000 and I do that, for each value, a couple of hundred times.

I do not think that data about the difference in efficiency on specific numbers is relevant. We assume that each number is equally probable to be converted. I'm not interested in numbers greater than 2000 since thousands are dealt in the same manner by all implementations.

I sincerely expected the imperative versions to be among the fastest. I thought that racket compiler could essentially generate "C-like code". On the contrary, the functional versions are not only faster when interpreted, they also yield more efficient code.

The programs we are talking about are the ones from the last post. I recall briefly their features.


Program A
simplify-all-a uses a separate simplify-by-weight-a function. This auxiliary function uses a named let to loop.

Program B
simplify-all-b is constituted by exactly the same code than simplify-all-b. However, simplify-by-weight-b is called instead of simplify-by-weight-a. simplify-by-weight-b uses a recursive subfunction to loop.

Program C
Essentially simplify-by-weight-a is not a separate function anymore, but is defined inside simplify-all-c in a let form.

Program D
While Program A, Program B and Program C are functional in nature, Program D relies on state change. for-each is used to loop over the different weights, but n (the value yet to convert in roman) and digits (the list of roman digits) are modified with set! and are not carried over as parameters.

Program E
Program E is functional. Two nested named let perform the computation. The one with greater scope has 4 parameters: the value yet to convert, the list of digits derived from the already converted part the weight-pair to use and the remaining weight-pairs. The inner named let has only two parameters, which are the value and the digits.

Program F and G
They are imperative versions using the racket non-standard for. Program G uses the user-defined form "until", while program F uses a named let to recur in the inner loop.

Graphs

I run the programs both interpreted and compiled. As we can easily notice, Program E is fastest both when interpreted and when compiled. Imperative Program F and G are very slow: when compiled they take twice the time Program E takes. Program D (imperative) is relatively fast when interpreted. However, when compiled all the functional versions are faster.

The absolute execution time of the different programs

In order to better spot the difference I prepared a graph where the bar represent the relative times with respect to the fastest code (so, higher means worst, here).

How much each program is slower than the fastest

As Program E is faster both when compiled and when interpreted, it is the bottom line. This graphs show how the imperative versions comparatively perform worse when compiled. I suspect this means that Racket optimizer is geared towards optimizing functional code. Which is right, since scheme benefits from a very functional style (I would say it is the natural style).

Code

I slightly modified the code to fit in these scheme (pun intended). The main benchmarking function is:

(define simplify-all-versions 
  (list simplify-all-a simplify-all-b simplify-all-c
                   simplify-all-d simplify-all-e
                   simplify-all-f simplify-all-g))

(define (benchmark how-many)
  (for ([simplify-all simplify-all-versions])
    (let* ([integer->roman (integer->roman-builder simplify-all)]
          [times (build-list how-many values)]
          [numbers (build-list 2000 add1)])
      (let-values ([(results execution-time real-time gc-time)
                    (time-apply map
                                (list (lambda (n)
                                      (for-each (lambda (i)
                                                   (integer->roman n))
                                      times))
                                      numbers))])
        (printf "~a: ~a~n" simplify-all execution-time)))))

And the integer->roman has been substituted with integer->roman-builder, which takes as an argument the simplify-all variant to use and returns the integer->roman function using that simplify-all.

(define (integer->roman-builder simplify-all)
  (let ([weights (sort '((1 "I") (4 "IV") (5 "V") (9 "IX") (10 "X")
                                 (40 "XL") (50 "L") (90 "XC") (100 "C")
                                 (400 "CD") (500 "D") (900 "CM"))
                       >
                       #:key car)])
    (lambda (n)
      (let-values ([(thousands n) (quotient/remainder n 1000)])
        (foldl string-append ""
               (simplify-all weights n
                             (build-list thousands (lambda (_) "M"))))))))

References

[0] Chris Okasaki, Purely functional data structures, Cambridge University Press
[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.64.3080&rep=rep1&type=pdf

Interesting DenyHosts...

http://think.random-stuff.org/posts/denyhosts-on-mac-os-x
http://ptone.com/dablog/2009/03/setting-up-denyhosts-to-block-ssh-attacks-on-leopard/

External Iterators for DFV and BFV in Python

In my post I started a brief discussion on internal interators and external iterators.
Here I show how a couple of external iterators can be implemented in Python using generators.
The code comes from the presentation I gave at Pycon Italia 4.

We are basically assuming a n-tree of nodes where each node has an attribute value where its value is held and an attribute children that is a list (but any iterable is ok) of its children.

def depth_first_visit(node):
    stack = [node, ]
    while stack:
        current_node = stack.pop()
        stack.extend(reversed(current_node.children))
        yield current_node.value
    
def breadth_first_visit(node):
    queue = collections.deque((node, ))
    while queue:
        current_node = queue.popleft()
        queue.extend(current_node.children)
        yield current_node.value

Romans in scheme

I described (here and here) three different ways to write the code to represent an integer in "roman" format.
Essentially, I think the best is the one using closures. In fact, while writing the python version, I also wrote a scheme version.

Although scheme is mostly a functional language, I will use the very same example to move towards a more imperative style. In Python I made my code "more functional"; the experiment is now making the code "more imperative" in scheme.

I show here the python code as an immediate reference:

@apply
def int2roman():
    weights = { 900 : 'CM', 500 : 'D', 400 : 'CD', 100 : 'C',
                90  : 'XC', 50  : 'L', 40  : 'XL', 10  : 'X',
                9   : 'IX', 5   : 'V', 4   : 'IV', 1   : 'I'}
    sorted_weights_tuples = sorted(weights.iteritems(), reverse=True)
    def int2roman(n):
        thousands, n = divmod(n, 1000)
        roman_digits = ['M', ] * thousands

        for m, s in sorted_weights_tuples:
            while n >= m:
                roman_digits.append(s)
                n -= m

        return ''.join(roman_digits)
    return int2roman

I wrote two helper functions: the first one essentially is equivalent to the inner while loop in Python, the other one to the for loop.

(define simplify-by-weight
  (lambda (weight ch n digits)
    (letrec ([sbw 
              (lambda (n digits)
                (cond ((< n weight) (cons n digits))
                      (else 
                       (sbw (- n weight) (cons ch digits)))))])
      (sbw n digits))))

(define simplify-all
  (lambda (weights n digits)
    (cond 
      ((null? weights) digits)
      (else
       (let* ([ret (simplify-by-weight (caar weights) (cadar weights) n digits)]
              [n (car ret)]
              [digits (cdr ret)])
         (simplify-all (cdr weights) n digits))))))

The idea to make the code more imperative looking or more imperative tout court comes from the idea that 4 lines in Python became 18 lines in scheme. This is not a "python vs. scheme". The solution I proposed in Python is, in my opinion, far more easier to read and undertand because it's so much shorter and the scheme version is cluttered with iteration details/function calls where it should have been much easier. New versions will be proposed. In the meantime, here it is the main function:

(define integer->roman-a
  (let ([weights (sort '((1 "I") (4 "IV") (5 "V") (9 "IX") (10 "X")
                                 (40 "XL") (50 "L") (90 "XC") (100 "C")
                                 (400 "CD") (500 "D") (900 "CM"))
                       >
                       #:key car)])
    (lambda (n)
      (let-values ([(thousands n) (quotient/remainder n 1000)])
        (foldl string-append ""
               (simplify-all weights n(build-list thousands (lambda (_) "M")))))))
  )

Apparently this is not a closure. However, remember that in scheme let is essentially syntactical sugar over a lambda form. In fact, we could have been made the closure more apparent writing the function this way:

(define integer->roman-b
  ((lambda (weights)
     (lambda (n)
       (let-values ([(thousands n) (quotient/remainder n 1000)])
         (foldl string-append ""
           (simplify-all weights n(build-list thousands (lambda (_) "M")))))))
   (sort '((1 "I") (4 "IV") (5 "V") (9 "IX") (10 "X")
                   (40 "XL") (50 "L") (90 "XC") (100 "C")
                   (400 "CD") (500 "D") (900 "CM"))
         >
         #:key car))) 

I have to confess that I like the foldl/string-append thing more than the python append/join.
This is, of course, just a matter of taste. I could have made the code simpler pushing the while logic in an iterator and then simply using list comprehensions. However, I believe the design would have been far more complicated.

In order to simplify the code of the first two functions, I will:

1. use more special forms (or different variants of special forms)
2. try to eliminate the functions as independent units
3. if necessary, use more forms provided by racket (most of them can be added to any scheme with macros)

Here is the first function; I often use a "sub-lambda" to iterate only on the parameters which change. Here I use a let form (remember... let is sugar over lambda). I believe code is simpler, here.

(define simplify-by-weight
  (lambda (weight ch n digits)
    (let loop ([n n] [digits digits])
      (cond ((< n weight) (cons n digits))
            (else 
             (loop (- n weight) (cons ch digits)))))))

It is simple enough to be removed:

(define simplify-all
  (lambda (weights n digits)
    (cond 
      ((null? weights) digits)
      (else
       (let* ([weight (caar weights)]
              [ch (cadar weights)]
              [ret (let loop ([n n] [digits digits])
                     (cond ((< n weight) (cons n digits))
                           (else 
                            (loop (- n weight) (cons ch digits)))))]
              [n (car ret)]
              [digits (cdr ret)])
         (simplify-all (cdr weights) n digits))))))

In fact, with let-values and values code could be simplified a lot.
Essentially here the problem is that we have two nested loops
and they loop on two different things and the value of n is logically modified.

Here we are simply using named lets to express loops:

(define simplify-all
  (lambda (weights n digits)
    (let next-weight ([n n]
                      [digits digits]
                      [weight-pair (car weights)]
                      [weights (cdr weights)])
      (let  ([weight (car weight-pair)]
             [ch (cadr weight-pair)])
        (let simplify-again ([n n] [digits digits])
          (cond
            ((< n weight)
             (cond 
               ((null? weights) digits)
               (else (next-weight n digits (car weights) (cdr weights)))))
            (else
             (simplify-again (- n weight) (cons ch digits)))))))))                   

Now the tentative is using the destructive state change:

(define simplify-all-e
  (lambda (weights n digits)
    (for-each 
     (lambda (weight-pair)
       (let  ([weight (car weight-pair)]
              [ch (cadr weight-pair)])
         (let simplify-again ()
           (cond
             ((< n weight) null)
             (else
              (set! n (- n weight))
              (set! digits (cons ch digits))
              (simplify-again))))))
     weights)
    digits))

The above code can be improved using the for special form and unless (which we should already have used):

(define simplify-all
  (lambda (weights n digits)
    (for ([weight-pair weights])
      (let  ([weight (car weight-pair)]
             [ch (cadr weight-pair)])
        (let simplify-again ()
          (unless (< n weight)
            (set! n (- n weight))
            (set! digits (cons ch digits))
            (simplify-again)))))
    digits))

We are still longer than the four python lines, but we are no longer more complicated. In fact, considering scheme macros, we can define a while/until pair of special forms which simplify the code greatly:

(define simplify-all-g
  (lambda (weights n digits)
    (for ([weight-pair weights])
      (let  ([weight (car weight-pair)]
             [ch (cadr weight-pair)])
        (until  (< n weight)
            (set! n (- n weight))
            (set! digits (cons ch digits)))))
    digits)) 

Some performance measures here.

Clojure Counter

One of the first programs I wrote in Clojure was a simple counter.
I am quite interested in the stateful/stateless mapping and that is the easiest possible example with refs. Refs are the simplest threadsafe state primitive.

This is a counter:

(defn  make-counter []
  (let [counter (ref 0)]
    (fn [] (dosync (alter counter inc)))))

Ok, this is a bit too schemish that it should have been. I encapsulated the actual counter in the local counter variable, which is accessible only from the function I return when one makes a counter. So this counter is basically a function which always return the next number.

In scheme that would have been something like:

(define make-counter
  (lambda ()
    (let ([counter 0])
      (lambda ()
        (let ([result counter])
          (set! counter (+ counter 1))
          result))))

The clojure variant (using dosync and alter) is thread-safe. Essentially modification to the ref is allowed only in a dosync context. Modification happens through the alter function (alter what update-function).

In order to try the code, I wrote this:

(defn print-some [get-next-function how-many]
  (dotimes [_ how-many]
    (print (.getName (Thread/currentThread)))
    (print ": ")
    (println (get-next-function))))

(let [counter (make-counter)]
  (dotimes [x 10]
    (.start (Thread.
             (fn [] (print-some counter 10))
             (Integer/toString x)))))

I particularly like it (even though it is obviously a mistake) because of the way it messes the output. In fact the three print functions (well, one is a println) are not atomic: the output is not locked. This means that the output is completely mixed.

This is good because it shows that threads are really running in parallel (well, I have an 8 virtual core machine, after all). On the other hand, the counter is always perfect: numbers can be swapped (but that is natural) but no number is repeated twice or skipped.

Perforce... goodby

It has been a nice partnership. But I'm so much happier with distributed version control systems.
It's just a PITA to move my huge Perforce archive... probably I will do it lazily.

And what about performance (closures and classes)?

In this post on classes and closures we entirely skipped the question of performance.
Which of the three solutions is "better"? In order to do this I wrote the following snippet and I put it at the end of the file.

if __name__ == "__main__":
    import timeit
    setup = '''import roman
numbers = range(1, 1000)
numbers += [3678, 3286, 5483, 8546, 1234, 5869, 97342]
'''
    statements = [
        '''int2roman = roman.int2roman%s
for n in numbers: int2roman(n)'''% ending
        for ending in ['_cl', '_dec', '']]
    for stmt in statements:
        print stmt, timeit.timeit(stmt, setup, number=1000)

Of course I also renamed the three functions:

• roman.int2roman_dec is the version with decorators
• roman.int2roman_cl is the version with callable classes
• roman.int3roman is the version with closures

Notice that the roman.int2roman_dec needed an internal change as well, since it accesses the attribute through the "external" function name. Thus, it became (note line 15):

if __name__ == "__main__":
def with_weights(weights):
    def _aux(f):
        f.weights = weights
        f.sorted_weights_tuples = sorted(weights.iteritems(), reverse=True)
        return f
    return _aux

@with_weights({ 900 : 'CM', 500 : 'D', 400 : 'CD', 100 : 'C',
                90  : 'XC', 50  : 'L', 40  : 'XL', 10  : 'X',
                9   : 'IX', 5   : 'V', 4   : 'IV', 1   : 'I'})
def int2roman_dec(n):
    thousands, n = divmod(n, 1000)
    roman_digits = ['M', ] * thousands

    for m, s in int2roman_dec.sorted_weights_tuples:
        while n >= m:
            roman_digits.append(s)
            n -= m

    return ''.join(roman_digits)

The times are:

Python 2.7 (r27:82508, Jul  3 2010, 21:12:11) 
[GCC 4.0.1 (Apple Inc. build 5493)] on darwin

% python roman.py
int2roman = roman.int2roman_cl
for n in numbers: int2roman(n) 4.19191408157
int2roman = roman.int2roman_dec
for n in numbers: int2roman(n) 3.88606595993
int2roman = roman.int2roman
for n in numbers: int2roman(n) 3.98288297653

So, the fastest is the class based. The version with closures is a little bit slower. And the slowest (though not very much slower) is the version with decorators. Since most of the code is cut and pasted, the difference in timings depend in the access of the sorted_weights_tuples list.

Please notice that essentially each run applied the function to millions of numbers.
Each test consists of repeating 1000 the transformation of each of the > 1000 elements in the number list.

The slowest version runs < 1.08 times slower than the fastest. With this numbers choosing one solution because of performance is clearly useless optimization. Design an algorithm using classes instead of closures because of performance, is premature optimization.

Oh, my Clojure [Emacs]

Clojure is very well supported in Emacs, of course. The instructions are here.
The Emacs Automatic Package Manager is needed!
Stuff on vim and TextMate, here.

I followed them I found myself with no usable REPL. I tried both with slime (which works, though I don't like how) and without, which basically does not work.

In fact I have to admit I'm not extremely pleased with the current situation. I suppose I will stick with IntelliJ. There is another Clojure plugin besides LaClojure, and perhaps that one works better. I may also be in the phase "I like scheme better than clojure right now" and that could explain my dissatisfaction.

I'm probably to try NetBeans with its plugin (LaClojure is broken right now).

for and for-permutation

When I'm prototyping scheme programs, I usually work in Racket. It's a nice environment and most things I need are ready. It's a battery included framework and I love that.

However, sometimes I think that when I used to play with gambit (pun intended) my scheme was better. I somewhat crafted minimal tools to solve the problem instead of fitting pre-made blocks. It's a bit on the design pattern as coarse grained way of thinking to engineering problems[0] line of thought.

Anyway, I used in my programs Racket for form too much and now I have troubles in porting them to other schemes. So I decided to implement the for form with syntax-rules.

(define-syntax for-permutation
  (syntax-rules ()
    [(_ () s1 s2 ...)
     (begin s1 s2 ...)]
    [(_ ([v1 l1] [v2 l2] ...) s1 s2 ...)
     (for-each
       (lambda (v1)
         (for-permutation ([v2 l2] ...)
           s1 s2 ...)) l1)]))

(define-syntax for
  (syntax-rules ()
    [(_ () s1 s2 ...)
     (begin s1 s2 ...)]
    [(_ ([v1 l1] [v2 l2] ...) s1 s2 ...)
     (for-each
       (lambda (v1 v2 ...)
         (begin s1 s2 ...))
       l1 l2 ...)]))

For-permutation works a bit like list comprehensions in Python:

[In]  [i+j for i in range(4) for j in range(3)]
[Out] [0, 1, 2, 1, 2, 3, 2, 3, 4, 3, 4, 5]

On the other hand for works just iterating on the sequences "together":

(for ([a '(1 2 3)] [b '(6 7 8)]) (display (+ a b)))
7911

Of course, since it depends on for-each, sequences must have the same length.

---
[0] more on this another day...

Internal vs External Iterators

In order to solve the problem of visiting each element of a collections, two solutions spring to mind: internal and external iterators. The main different is "who controls the iteration". In internal iterators the iteration is controlled by the iterator itself: the caller provides a callback function which is called on each element.
In this sense, the map function is essentially an internal iterator: iterates on each element of a collection and calls the function parameter on each element. Map is a primitive function in Python, scheme/lisp, Haskell and many other languages. All these languages have higher order functions and functions as first class citizens. In fact, this strategy could (and is) be employed with C/C++ as well.

On the other hand in External Iterators the caller controls the iteration. This is the case with Python for statement, for example.

In fact, object zealots usually regard the external iterators as more flexible, as they make it possible to compare two different structures or other similar stuff:

import itertools as it

for i, j in it.izip(left_collection, right_collection):
    if i != j:
        return False
else:
    return True

In fact, this could be rather easily done with higher order functions, as long as you have the right set. What is more difficult is to deal with control; you probably need call/cc and similar primitives for many things which are rather straightforward with external iterators.

They are the more widespread method for iteration in Java (Iterator class) and Python. On the other hand in Ruby and most functional languages it is very much more common to use internal iterators. Though nothing prevents from using internal iterators in Python, it is much more common to use external iterators.

In C++, using Boost, internal iterators become somewhat more common. This comes from a project of mine:

std::transform(items.begin(), items.end(), sizes.begin(),
                   bind(&relation::size,
                        bind(&iset::value_type::second, ::_1)));
    std::for_each(sizes.begin(), sizes.end(),
                  var(counter) += boost::lambda::_1);

Let alone the items.begin(), which [b]is[/b] an external iterator, although used in an internal iterator manner.

Clojure and CPS

Here I translated the reverse in cp-style example in clojure.
This is more an exercise than everything else: since in Clojure there is no TCO at all
(unless explicitly through recur calls), the example grows the stack.

I began translating to trampoline style... but that was not very entertaining. :)

(defn cp-reverse [lst k]
  (loop [current-lst lst current-k k]
    (if (empty? current-lst) (current-k '())
        (recur (rest current-lst)
          (fn [v] (cons (first current-lst)
                        (current-k v)))))))

Classes and closures

Let us write some python code to transform an integer into "roman" format.
Here we use a class:

class Int2RomanConverter(object):
    weights = { 900 : 'CM', 500 : 'D', 400 : 'CD', 100 : 'C',
                90  : 'XC', 50  : 'L', 40  : 'XL', 10  : 'X',
                9   : 'IX', 5   : 'V', 4   : 'IV', 1   : 'I'}
    sorted_weights_tuples = sorted(weights.iteritems(), reverse=True)

    def __call__(self, n):
        thousands, n = divmod(n, 1000)
        roman_digits = ['M', ] * thousands

        for m, s in self.sorted_weights_tuples:
            while n >= m:
                roman_digits.append(s)
                n -= m

        return ''.join(roman_digits)

int2roman = Int2RomanConverter()

This class is a callable and works as a function. We probably should have made
the class non public (_Int2RomanConverter) and made only the int2roman function
available to clients.

The more straightforward way to write the code, would have been a simple function.
In fact, I consider this an example of premature optimization. The point was
to show how functions which rely on some sort of static data (the sorted weight)
could be constructed as classes.

In this case, I think there is no perceivable difference without the "optimization".
But an example is an example.

The very first thing coming to my mind would have been creating a function
with the sorted tuples as a default argument. Something like:

def int2roman(n, weights=sorted(
              { 900 : 'CM', 500 : 'D', 400 : 'CD', 100 : 'C',
                90  : 'XC', 50  : 'L', 40  : 'XL', 10  : 'X',
                9   : 'IX', 5   : 'V', 4   : 'IV', 1   : 'I'}.iteritems(), reverse=True)):
...

But I find this rather ugly since the weights are not a true argument,
the intention (having some data not evaluated every time) is rather masked
and users could think they can provide their own sets of weights. Well,
actually this code blatantly sucks.

Another idea was using decorators. I love decorators...
This decorator essentially adds the sorted weights to the function
as an attribute (in Python functions are objects).

def with_weights(weights):
    def _aux(f):
        f.weights = weights
        f.sorted_weights_tuples = sorted(weights.iteritems(), reverse=True)
        return f
    return _aux

The rest of the code becomes:

@with_weights({ 900 : 'CM', 500 : 'D', 400 : 'CD', 100 : 'C',
                90  : 'XC', 50  : 'L', 40  : 'XL', 10  : 'X',
                9   : 'IX', 5   : 'V', 4   : 'IV', 1   : 'I'})
def int2roman(n):
    thousands, n = divmod(n, 1000)
    roman_digits = ['M', ] * thousands

    for m, s in int2roman.sorted_weights_tuples:
        while n >= m:
            roman_digits.append(s)
            n -= m

    return ''.join(roman_digits)

This code has its merits. It's rather easy to understand, provided
that you know decorators (and these are decorators with arguments,
which is slightly more complicated). You have a function, with the
right number of arguments and you are not tempted to modify
the weights.

Then a voice in the back of my head suggested "Use the closure, Riko!"
The voice sounded a lot like the one of Alec Guinness, but that's enterely
another story.

Ideally I was already using closures, only it was not obvious.
In the decorator solution, I have a function modifying the original
function. This is not very different from having a function returning
a function. It's only less general and (in other circumstances easier
to grasp).

The class based solution is rather similar (only more verbose) to
a solution using closures. In fact I have a "function" which returns
a "function". Only the first function is a constructor and the second
function is a callable object (whose only capability is being called).

Frankly I'm ashamed. The first solution is terribly javish. The second
looks a lot like... well, python has decorators, let's use them. So,
a better code is, in my opinion:

@apply
def int2roman():
    weights = { 900 : 'CM', 500 : 'D', 400 : 'CD', 100 : 'C',
                90  : 'XC', 50  : 'L', 40  : 'XL', 10  : 'X',
                9   : 'IX', 5   : 'V', 4   : 'IV', 1   : 'I'}
    sorted_weights_tuples = sorted(weights.iteritems(), reverse=True)
    def int2roman(n):
        thousands, n = divmod(n, 1000)
        roman_digits = ['M', ] * thousands

        for m, s in sorted_weights_tuples:
            while n >= m:
                roman_digits.append(s)
                n -= m

        return ''.join(roman_digits)
    return int2roman

Notice the apply trick.

Emacs Automatic Package Installer

While following the instructions to install clojure support for Emacs, I stumbled in  an automatic package installer. Installing the package installer is the nicer thing I have done with emacs.

You basically put this snippet in the *scratch* and C-j. I wonder why more packages do not follow this procedure... well, perhaps it's not necessary after I installed the package manager.

(let ((buffer (url-retrieve-synchronously
        "http://tromey.com/elpa/package-install.el")))
  (save-excursion
    (set-buffer buffer)
    (goto-char (point-min))
    (re-search-forward "^$" nil 'move)
    (eval-region (point) (point-max))
    (kill-buffer (current-buffer))))

Why I hate binary package managers...

No matter how many packages they have: they always miss some. Or some sensible configuration.
E.g., my Ubuntu does not have Racket in the package list. The more recent PLT scheme it has is PLT 4.2.1.
And that is rather good... afterall in April (that is to say when this Ubuntu came out) there was PLT-Scheme 4.2.5. Yes, I know... if I want something done I could always do it.

There is worse... The packaged Gambit version is 4.2. There have been many major improvements to Gambit since then (it has reached version 4.6; 4.2 is about two years old, maybe more). And if I have a package manager, but still have to install things by hand...

Oh, my clojure! [TextMate and Vim]

I started hacking with clojure some time ago. I was looking for a decent language on the JVM and I found a wonderful language. Since it was "JVM stuff" I started working with JVM tools. That it to say, Idea.
Which is great, by the way.

Now I believe my reluctancy to use clojure is related to Idea. Idea has a rigid "project-based" approach. I kind of circumvented it creating a "clojure" project where I put all my scripts, and it kind of works. However, most of the wonderful features of IntelliJ are not useful in Clojure (I have HOF and macros, who needs IDE code-generation?).

On the other hand, I happily use Emacs for most lispish (and functional languages in general) I use. It works great: the interpreter is in its frame and I can just try snippets of code. By the way this is available with LaClojure (that is to say IntelliJ clojure plugin) as well. Well, it was, since now it is broken and does not work with clojure 1.1.

Here I found instructions on adding nice clojure support to TextMate. In principle the support looks rather good, though it seems broken. I have no time right now to fix it.
Edit: apparently it is not an issue with TM bundle. I had issues with cake related to the interaction between some environment variables set by zsh (with my custom zshrc file) and cake. Now the thing works as expected. Still, no REPL by design. Probably the REPL is meant to be in the terminal and that's it. Nonetheless, I don't like it very much.

The instruction for vim are here and here you can directly download the package. Unfortunately the package seems to have been compiled for windows and I probably should recompile and do a bit of configuration. The documentation is not extremely clear, though it should do. Probably I will try to make it work. Right now does syntax highlighting and all the nice editor things: the piece which I did not manage to make it work is the REPL inside vim.

Python example on atomic files

This is a very simple example on how to write atomically to a file in Python. We already dealt with the subject here.

The code here essentially works only if you plan to rewrite the file from scratch. Append and similar stuff is not supported. Reading is not supported (as it does not make sense, since it has no troubles with letting the filesystem dirty). Notice that this code does not work on windows with the intended semantics, since rename is not guaranteed to be atomic (as far as I know).

'''Simple module containing a file-like object whose behavior is
to actually save the file only when closed. Before that, data is
stored in a temporary file: thus when creating a file, if another file
with the same name exists that is never substituted with a partial
file.'''

import os
import tempfile

class AtomicFile(object):
    '''A file-like object where writes are committed only when closed.

    A temporary named file is used in order to store the results.
    On close, the temporary is renamed according to the name parameter.

    AtomicFiles are meant to be used with context managers.'''

    # Unfortunately the TemporaryFile interface uses a dir parameter
    # pylint: disable-msg=R0913
    # pylint: disable-msg=W0622
    def __init__(self, name, bufsize=-1, suffix='', prefix='', dir=None):
        mode = 'r+b'
        self.name = name
        self.tempfile = tempfile.NamedTemporaryFile(
            mode=mode, bufsize=bufsize, suffix=suffix, prefix=prefix,
            dir=dir, delete=False)

    def __enter__(self):
        return self

    def __exit__(self, _exc_type, _exc_val, _exc_tb):
        self.swap()
        return False

    def swap(self):
        'Explicitly closes and renames the temporary file.'
        self.tempfile.close()
        os.rename(self.tempfile.name, self.name)
    close = swap


    def write(self, what):
        'Writes a string to the file'
        self.tempfile.write(what)

And now a bit of unit-testing (and example usage):

import unittest
import tempfile
import atomic_file

import os
from os import path

class TestAtomicFile(unittest.TestCase):
    def setUp(self):
        self.directory = path.dirname(__file__)
        self.name = tempfile.mktemp()

    def tearDown(self):
        try:
            os.remove(self.name)
        except OSError:
            pass

    def testCreate(self):
        af = atomic_file.AtomicFile(name=self.name, dir=self.directory)
        self.assert_(not path.exists(self.name))
        self.assert_(path.exists(path.join(self.directory,
                                           af.tempfile.name)))
        af.swap()
        self.assert_(path.exists(self.name))
        self.assert_(not path.exists(path.join(self.directory,
                                           af.tempfile.name)))
    def testClose(self):
        af = atomic_file.AtomicFile(name=self.name, dir=self.directory)
        self.assert_(not path.exists(self.name))
        self.assert_(path.exists(path.join(self.directory,
                                           af.tempfile.name)))
        af.close()
        self.assert_(path.exists(self.name))
        self.assert_(not path.exists(path.join(self.directory,
                                           af.tempfile.name)))

    def testContext(self):
        with atomic_file.AtomicFile(name=self.name, dir=self.directory) as af:
            self.assert_(not path.exists(self.name))
            self.assert_(path.exists(path.join(self.directory,                                               af.tempfile.name)))
        self.assert_(path.exists(self.name))
        self.assert_(not path.exists(path.join(self.directory,
                                           af.tempfile.name)))

    def testWrite(self):
        with atomic_file.AtomicFile(name=self.name, dir=self.directory) as af:
            text = 'THE TEXT\n'
            af.write(text)
        self.assertEqual(file(self.name).read(), text)

    def testMoreWrite(self):
        with atomic_file.AtomicFile(name=self.name, dir=self.directory) as af:
            lines = ['THE TEXT', 'MORE TEXT', 'AGAIN!']
            for line in lines:
                print >> af, line
        self.assertEqual(file(self.name).read(), '\n'.join(lines) + '\n')

    def hasExplosion(self):
        with atomic_file.AtomicFile(name=self.name, dir=self.directory) as af:
            raise RuntimeError()
        self.assert_(not path.exists(self.name))
        self.assert_(not path.exists(path.join(self.directory,
                                               af.tempfile.name)))
    def testBoom(self):
        self.assertRaises(RuntimeError, self.hasExplosion)

Gist... awesome?

This github service is amazing: http://gist.github.com/

Many in the bitbucket/mercurial community seem to dislike the idea.
Are they right? Who knows.

while/until in scheme

I don't really to pervert language philosophies. Scheme is a functional language, and I like to use it as such.
However, Scheme is not a pure functional language and has all the state changing features one would expect from an imperative language (e.g., set!).

The idea here is not new nor a good one: we are to define a while form. Of course, you have to manually modify the looping variables in the while body. As you would in C. Besides, this was one of my first attempts at not completely trivial macros in scheme.

Here we are using scheme hygienic macros, and in particular the syntax-rules variant, which is standard in R5RS and R6RS. There are other systems, but as far as I know none of them is completely standard.

Here we are essentially saying: if you find a while "function", treat it like in a special way.
Don't loop for the "while" function, but transform the s-expression in the way specified in the second s-expression inside the square brackets.

(define-syntax while
  (syntax-rules ()
    [(_ c b1 b2 ...)
     (let loop ()
       (when c b1 b2 ... (loop)))]))

(define-syntax until
  (syntax-rules ()
    [(_ c b1 b2 ...) (while (not c) b1 b2 ...)]))

And now you can write ugly stuff like:

(define-syntax while
(let ([i 10]) 
  (until (zero? i) 
         (displayln i) 
         (set! i (- i 1))))

My scheme has no when!

If your scheme has no when/until forms, they can be easily defined with:

(define-syntax when
  (syntax-rules ()
    [(_ c b1 ...)
     (cond (c b1 ...) (else #f))]))

(define-syntax unless
  (syntax-rules ()
    [(_ c b1 ...)
     (cond (c #f) (else b1 ...))]))

Atomicity and files

We all greatly value atomic operations. Either they fully succeed or they completely fail. Even better, if they fail, it is like they never occurred, so that it is not necessary to clean things up.

The term itself is widely used in the database community (the A of ACID stands for Atomicity) and in the parallel computing community. The meaning is essentially very similar, though the scope is different. Moreover, the idea is pervasive in computer science.

Writing exception safe code in C++[0] is essentially a strive for atomicity. C++ code is strongly exception safe if it has rollback semantics. That is to say failed operations have no side effects and consequently leave all data as it never happened. More details here [1]. It is usually considered extremely expensive to write all the code to be strongly exception safe.

In languages such as Clojure this comes for free. Memory is transactional[2], that is to say, it support the ACI (without D) properties of a relational database. Of course durability is not an issue: we are dealing with memory, after all. This is not extremely expensive as, by default, variables in Clojure are not modifiable. Essentially they are but names of const object. If a variable needs to change its value, vars, refs or atoms (but they are an entirely different story) must be used. And they are governed by a software transactional memory system [3].

Another famous source of atomic operations, is the POSIX standard. Some system calls are guaranteed to be atomic. In the following, we are mostly concerned with open (2)[4] and rename (2)[5].

In the open(2) system call, the check for the existence of the file and the creation of the file if it does not exist shall be atomic with respect to other threads executing open() naming the same filename in the same directory with O_EXCL and O_CREAT set.
For this reason, open can be used to implement concurrency structures such as locks; the link (2)[6] system call is often used as well. Moreover, the open function shall be used in Easier to Ask Forgiveness (EAFP) strategies [7], which are fare more secure and effective because open is atomic.

Unfortunately for us, the write(2) [8] system call is only partially atomic. That is to say if the requested write is “small enough” (that is to say the number of bytes are < PIPE_BUF), then the single write action is atomic. If this is not the case, the write is not atomic. Moreover, multiple write actions are, of course, not atomic.

To make things even worse, the whole open-write-close thing is not atomic at all. And is destructive. The typical problem is that when you open a file with O_TRUNC (or with something which in turns calls an open with O_TRUNC set) you destroy the content of the file. However, you may have successive errors which prevents the correct and complete writing of the new file. The typical solution is using temporaries.

References

[0] “Strive for exception safe code”, Effective C++, 3rd ed, S. Meyers, Addison-Wesley, pp. 127-134
[1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1997/N1077.asc
[2] http://clojure.org/refs
[3] http://en.wikipedia.org/wiki/Software_transactional_memory
[4] http://www.opengroup.org/onlinepubs/009695399/functions/open.html
[5] http://www.opengroup.org/onlinepubs/009695399/functions/rename.html
[6] http://www.opengroup.org/onlinepubs/009695399/functions/link.html
[7] Python in a Nutshell, 2nd ed., A. Martelli, O’Reilly Media, pp. 134-136
[8] http://www.opengroup.org/onlinepubs/009695399/functions/write.html

The apply decorator trick

From wikipedia:

In computer science, a closure is a first-class function with free variables that are bound in the lexical environment. Such a function is said to be "closed over" its free variables. A closure is defined within the scope of its free variables, and the extent of those variables is at least as long as the lifetime of the closure itself. The explicit use of closures is associated with functional programming and with languages such as ML and Lisp. Closures are used to implement continuation passing style, and in this manner, hide state. Constructs such as objects and control structures can thus be implemented with closures.

In terms of python you have a closure when a function returns another function. This is something you often do when you use decorators, for example.

However, this is not about decorators. The classical example is the "adder":

>>> def add_creator(n):
...   def adder(m):
...     return m + n
...   return adder
... 
>>> add5 = add_creator(5)
>>> add5(6)
11

This is fun and nice. However, I often use closures in a more functional way to hide state instead of using classes. In this cases you often are not interested in the higher order function.
You use it to hide state in local variables/parameters, but you plan to use the returned function.

E.g.,

def do_something_builder():
    val = very_long_computation(...)
    def do_something(z):
        x = use(val)
        y = do_other_things(z)
        return g(x, y)
do_something = do_something_builder()

In this cases, I use the "apply trick". Apply "calls" the callable argument and
returns the result. apply can be used as a decorator as well.

@apply
def do_something():
    val = very_long_computation(...)
    def do_something(z):
        x = use(val)
        y = do_other_things(z)
        return g(x, y)

This is very similar to schemish things like, which I have seen often:

(define do-something
  (let ([val (very-long-computation)])
     (lambda (z)
       (let ([x (use val)]
             [y (do-other-things z)])
        (g x y)))))

Mastermind/Bulls and Cows Breaker

Introduction

Mastermind is a classical code breaking game. And I bet almost everyone has played it at least one time (at least, any geek[0]). I won't explain the rules here. If you really don't know the rules, here there is an explanation. Besides, we are playing Bulls and Cows, which is very similar, but has no copyright.

I sincerely find the game rather boring, though I find writing programs solving boring games quite entertaining. This is a very old prolog program I wrote to break the code. The algorithm is extremely trivial, and is more an example in how easy to solve are this class of problems in Prolog with native backtracking than anything else.

Wikipedia page also list some scientific papers on Mastermind/Bulls and Cows code breaking algorithms. I find them really interesting, indeed. But this is about Prolog and backtracking, indeed.

The code

:- use_module(library(lists)).
:- dynamic query/3.

mastermind(Code) :-
 cleanup, guess(Code), check(Code), announce.

guess(Code) :-
 Code = [_X1, _X2, _X3, _X4],
 selects(Code, [1,2,3,4,5,6,7,8,9]).

check(Guess) :-
 \+ inconsistent(Guess),
 ask(Guess).

inconsistent(Guess) :-
 query(OldGuess, Bulls, Cows),
 \+ bulls_and_cows_match(OldGuess, Guess, Bulls, Cows).

bulls_and_cows_match(OldGuess, Guess, Bulls, Cows):-
 exact_matches(OldGuess, Guess, N1),
 N1 =:= Bulls,
 common_members(OldGuess, Guess, N2),
 Cows =:= N2-Bulls.

ask(Guess) :-
 repeat,
 format('How many bulls and cows in ~p?~n', [Guess]),
 read((Bulls, Cows)),
 sensible(Bulls, Cows), !,
 assert(query(Guess, Bulls, Cows)),
 Bulls =:= 4.

sensible(Bulls, Cows) :-
 integer(Bulls),
 integer(Cows),
 Bulls + Cows =< 4.


%%  Helpers
exact_matches(Xs, Ys, N) :-
 exact_matches(Xs, Ys, 0, N).
exact_matches([X|Xs], [Y|Ys], K, N) :-
 (   X = Y ->
 K1 is K + 1
 ;   
 K1 is K),
 exact_matches(Xs, Ys, K1, N).
exact_matches([], [], N, N).

common_members(Xs, Ys, N) :-
 common_members(Xs, Ys, 0, N).
common_members([X|Xs], Ys, K, N) :-
 (   member(X, Ys) ->
 K1 is K+1
 ;   
 K1 is K),
 common_members(Xs, Ys, K1, N).
common_members([], _Ys, N, N).

cleanup :-
 retractall(query(_,_,_)), !.
cleanup.

announce :-
 size_of(X, query(X, _A, _B), N),
 format('Found the answer after ~d queries.~n', [N]).
%%  Utilities
selects([X|Xs], Ys) :-
 select(X, Ys, Ys1),
 selects(Xs, Ys1).
selects([], _Ys).

size_of(X, G, N) :-
 findall(X, G, Xs),
 length(Xs, N).

Notes

[0] Most of the type when you say "any" or "everyone" you are wrong. This applies to me as well.

Pydistutil Configuration

Something I rather hate is mixing up my development environment with my ordinary system environment. I like having things I installed by myself separated from system stuff (and I'm not the only one... think about the convention of /usr/local).

My development machine are essentially single user machines. I am the only user. Thus, global installations are simply an overkill. And I hate pervasive package management systems. For the MacOS, for example, I chose brew. I love it. It does the minimum to automate tedious stuff, but it leaves me complete freedom.

Of course, since I want my package manager to do the minimum necessary stuff, I don't want it to touch my python modules.

Don't touch my Python!

 Well... anyway. As a consequence I heavily rely on python own module manager, that is to say pip/easy_install. You can tell distutils the default base install directory. For example, on Linux, I have in my home directory this .pydistutil.cfg file:

% cat .pydistutils.cfg  
[install]
prefix = ~/.local
install_scripts = ~/bin
install_lib = ~/.local/lib/python$py_version_short/site-packages

which basically makes all the installation in my home-directory.
More information here and here. I use this for modules I plan to use in multiple projects.
Otherwise, virtualenv.

Racket, can it be a Good Thing?

On June, 7th 2010 PLT Scheme changed name. Now it is called Racket.
I will not indulge in how bad does it sound (especially if you live in countries where racket is a social plague). I bet if some developer had his project dubbed "Rape" (Recursive Anamorphic Program Environment?) some people would argue. However, the authors do like it, and that's it.

PLT Scheme was a very good programming environment. I love scheme. I love Planet. There is a huge quantity of modules (which is something I really appreciate as a pythonista) and they are not only academic tools. Which is good. This comes with Racket as well.

Before the name change, PLT scheme was somewhat different from most scheme environments out there. First, it came batteries included. And as someone new to the platform I often found myself using functions which were srfi or even non standard. In both cases some alternative platforms I used did non include them. This was somewhat annoying...

Moreover the #scheme first line makes a "scheme" source non valid scheme. Thus this was not a minor issue to work with multiple environments. These stuffs is rather trivial to solve, simply I would have preferred to spend my time currying rather that understanding how each scheme environment extended r5rs with modules and make things r6rs compatible as well.

At least now it is Racket. It's based on scheme, but it's not scheme (which is something that, when done by Microsoft is regarded as a criminal offense). So I don't have to expect my racket programs work with scheme compilers.

Moreover, you can write in your CV:
IT skills: racket

... and that is not something to underestimate.

Quicksort in Continuation Passing Style

Quicksort is ugly. I hate quicksort. Still everyone praises quicksort...
... and Hoare did worse things. Such as Hoare logic. I had to manually verify some short programs using Hoare logic and sometimes I still wake up screaming at night after dreaming pages of Hoare triples.

Well, this is a problem of mine. Back to quicksort... among the elementary sorting algorithms it is one of the more difficult to understand. But it is rather efficient despite its worse case N^2 running time. Moreover, quicksort can be implemented in constant space (well, almost... you still have double recursive calls which means log n, if you consider the stack).

That is why (the idea that quicksort modifies an array in place) some believe functional implementations of quicksort are not quicksort. And I'm not going to argue. I don't care, in fact. Here my concern are the double recursive calls. Normally you could not tail call optimize such a thing (pseudo code from wikipedia):

procedure quicksort(array, left, right)
     if right > left
         select a pivot index //(e.g. pivotIndex := left+(right-left)/2)
         pivotNewIndex := partition(array, left, right, pivotIndex)
         quicksort(array, left, pivotNewIndex - 1)
         quicksort(array, pivotNewIndex + 1, right)

Luckily for us, we can use continuation passing style to trick this into tail call optimizable. Code in continuation passing style is always tail recursive.

Append:

(define cp-append 
  (lambda (lst1 lst2 k)
    (cond ((null? lst1) (k lst2))
          (else (cp-append (cdr lst1) lst2 
                           (lambda (rest)
                             (k (cons (car lst1) rest))))))))

The continuation function for the partition function shall take two parameters.
The first one "accumulates" less than items, the second one greater than items.

(define cp-partition
  (lambda (lst p? k)
    (letrec ([cpp 
              (lambda (lst k)
                (cond
                  ((null? lst) (k '() '()))
                  ((p? (car lst)) 
                   (cpp (cdr lst)
                        (lambda (p-true p-false)
                          (k (cons (car lst) p-true)
                             p-false))))
                  (else
                   (cpp (cdr lst)
                        (lambda (p-true p-false)
                          (k p-true
                             (cons (car lst) p-false)))))))])
      (cpp lst k))))

And eventually, his majesty the quicksort:

(define quicksort
  (lambda  (lst less?)
    (letrec 
        ([qs
          (lambda (lst k)
            (cond
              ((null? lst) (k '()))
              (else
               (let ([pivot (car lst)]
                     [rest (cdr lst)])
                 (cp-partition 
                  rest
                  (lambda (x) (less? x pivot))
                  (lambda (less-than greater-than)
                    (qs greater-than
                        (lambda (sorted-gt)
                          (qs less-than
                              (lambda (sorted-lt)
                                (cp-append
                                 sorted-lt
                                 (cons pivot sorted-gt) k)))))
      (qs lst (lambda (v) v)))))

Although the testing based on random data is a Very Bad Idea, this was the easiest way to rough up my code.

(define (random-list max length)
  (letrec ([rl (lambda (length)
                 (cond ((= length 0) '())
                       (else (cons (random max)
                                   (rl (- length 1))))))])
    (rl length)))

(define (test-quicksort)
  (let ([tests-per-length 50]
        [random-top-integer 1000]
        [list-lengths '(0 1 10 11 25 40 64 128)])
    (for-each 
     (lambda (length)
       (do ([i tests-per-length (- i 1)])
         ((zero? i))
         (let* ([the-list (random-list random-top-integer length)]
                [lt-sorted-list (sort the-list <)]
                [lt-qsorted-list (quicksort the-list <)]
                [gt-sorted-list (sort the-list >)]
                [gt-qsorted-list (quicksort the-list >)])
           (when (not (equal? lt-sorted-list lt-qsorted-list))
             (printf "~a[<]:~n~a~n~a~n~n" the-list
                     lt-sorted-list lt-qsorted-list))
           (when (not (equal? gt-sorted-list gt-qsorted-list))
             (printf "~a[>]:~n~a~n~a~n~n" the-list
                     gt-sorted-list gt-qsorted-list)))))
     list-lengths)))

I tried to avoid racket specific constructs, but I'm not sure that one or two slipped in the testing code.

BTW, here a version with named-let:

(define quicksort
  (lambda  (lst less?) 
    (let qs ([lst lst] [k (lambda (v) v)])
      (cond 
        ((null? lst) (k '()))
        (else
         (let ([pivot (car lst)]
               [rest (cdr lst)])
           (cp-partition 
            rest 
            (lambda (x) (less? x pivot))
            (lambda (less-than greater-than)
              (qs greater-than
                  (lambda (sorted-gt)
                    (qs less-than
                        (lambda (sorted-lt)
                          (cp-append 
                           sorted-lt
                           (cons pivot sorted-gt) k)))))))))))))

Seems I already wrote on Quicksort...

Reverse in continuation passing style

A simple reverse in continuation passing style...

(define cp-reverse
  (lambda (lst)
    (letrec ([cpr (lambda (lst k)
                 (cond 
                   ((null? lst) (k '()))
                   (else 
                    (cpr (cdr lst)
                         (lambda (v)
                           (cons (car lst) (k v)))))))])
      (cpr lst (lambda (v) v)))))

This is a rather classical example, indeed. Performance wise it's much slower than the reverse builtin in PLT-Scheme/Racket, still it's a lot faster than even more classical trivial implementations such as:

(define (sl-reverse lst)
  (cond
    ((null? lst) '())
    (else (append (sl-reverse (cdr lst)) (list (car lst))))))

In fact the example relies on TCO modulo cons.

In order to test the whole thing in racket I used this snippet:

(define (print-times min max step)
  (for ([m (in-range min max step)])
    (let ([lst (for/list ([i (in-range m)]) i)])
      (time (reverse lst))
      (time (cp-reverse lst))
      (time (sl-reverse lst)))))

> (print-times 5000 10000 1000)
cpu time: 0 real time: 10 gc time: 0
cpu time: 5 real time: 61 gc time: 0
cpu time: 1320 real time: 2088 gc time: 1099
cpu time: 1 real time: 0 gc time: 0
cpu time: 2 real time: 2 gc time: 0
cpu time: 463 real time: 493 gc time: 185
cpu time: 0 real time: 0 gc time: 0
cpu time: 2 real time: 21 gc time: 0
cpu time: 888 real time: 926 gc time: 505
cpu time: 0 real time: 0 gc time: 0
cpu time: 2 real time: 2 gc time: 0
cpu time: 2729 real time: 2766 gc time: 2235
cpu time: 0 real time: 0 gc time: 0
cpu time: 2 real time: 2 gc time: 0
cpu time: 2157 real time: 2227 gc time: 1522