leonardo - A recursive combinator
View:Recent Entries.
View:Archive.
View:Friends.
View:Profile.
View:Website (My Website).

Tags:, , ,
Security:
Subject: A recursive combinator
Time:11:49 am
This interesting blog page "Refactoring Methods with Recursive Combinators" shows Ruby implementations of a recursive combinator:
http://github.com/raganwald/homoiconic/tree/master/2008-11-23%2Frecursive_combinators.md

I like the idea of putting a blog in a version control, I just hope the usability will improve a little more for blog readers (removing some noise from the page).

Here you can find my Python and D versions:
http://www.fantascienza.net/leonardo/js/multirec.zip

The translation to Python was painless and not too much difficult, so Python is up to the task:
def divide_and_conquer(value, isdivisible, conquer, divide, recombine):
    if isdivisible(value):
        return recombine(divide_and_conquer(sub_value, isdivisible, conquer, divide, recombine)
                         for sub_value in divide(value))
    else:
        return conquer(value)

identity = lambda x: x

def rotate2(square):
    def divide(square):
        half_len = len(square) // 2
        def sub_square(nrow, ncol):
            return [row[ncol: ncol + half_len] for row in square[nrow: nrow + half_len]]
        upper_left = sub_square(0, 0)
        lower_left = sub_square(half_len, 0)
        upper_right = sub_square(0, half_len)
        lower_right = sub_square(half_len, half_len)
        return [upper_left, lower_left, upper_right, lower_right]

    def recombine((upper_left, lower_left, upper_right, lower_right)):
        return [l + r for l,r in zip(upper_right, lower_right)] + \
               [l + r for l,r in zip(upper_left, lower_left)]

    return divide_and_conquer(square,
                              isdivisible=lambda value: len(value) > 1,
                              conquer=    identity,
                              divide=     divide,
                              recombine=  recombine)
I think this Python code is also a little more readable than the original Ruby one (and probably faster too).

This code is a cute exercise, but it's less readable than the original version (that doesn't use a combinator), longer, more difficult to debug and modify, and slower. And using multiple threads doesn't help much in normal Python code.

Then I have tried to translate the code to the D language, that is a statically typed language that is more flexible than the usual C++ or C, but not as flexible for example as Scala or Haskell.

First of all I have translated the original functions (function templates), it's doable, and the result looks even nice enough, especially if you use my dlibs:
BaseType!(TyIter) sum_squares3(TyIter)(TyIter value) {
    static if (IsIterable!(TyIter)) {
        BaseType1!(TyIter) x;
        return sum(select(sum_squares3(x), x, value));
    } else
        return value * value;
}

T[][] rotate1(T)(T[][] square) {
    if (len(square) > 1) {
        int half_len = len(square) / 2;
        T[][] sub_square(int nrow, int ncol) {
            T[] row;
            return select(row[ncol.. ncol + half_len], row, square[nrow.. nrow + half_len]);
        }
        auto upper_left = rotate1(sub_square(0, 0));
        auto lower_left = rotate1(sub_square(half_len, 0));
        auto upper_right = rotate1(sub_square(0, half_len));
        auto lower_right = rotate1(sub_square(half_len, half_len));
        T[][] lr;
        return select(lr[0] ~ lr[1], lr, azip(upper_right, lower_right)) ~
               select(lr[0] ~ lr[1], lr, azip(upper_left, lower_left));
    } else
        return square;
}
Note that static if (IsIterable!(TyIter)), it's necessary because as the sum_squares3 drills down, the type of value changes. So you need a static if to manage the change in a static language like D.

Note that the D version sum_squares3() isn't as flexible as the Python version. In normal D you can't define an array with mixed elements:
[iter([1, {2:0, 3:0}]), [set([4, 5]), 6], [[[7]]]]
Or even an array with a mixed number of levels:
[1, 2, 3, [[4, 5], 6], [[[7]]]]
You are allowed to use a fixed number or levels, with subarrays of different length:
[[1, 2], [3], [4, 5], [6], [7]]

Then I have tried to translate the multirec combinator itself. But I think here the static type system of D shows the limits of its flexibility. The translation was a pain. This a result:
ReturnType!({ return F2.init(Init!(T)().init); }) divide_and_conquer(T, F1, F2, F3, F4)
                                                                    (T value, F1 isdivisible,
                                                                     F2 conquer, F3 divide,
                                                                     F4 recombine) {
    if (isdivisible(value)) {
        T[] aux;
        foreach (sub_value; divide(value))
            aux ~= divide_and_conquer(sub_value, isdivisible, conquer, divide, recombine);
        return recombine(aux);
    } else
        return conquer(value);
}

struct _identity { static T opCall(T)(T x) { return x; } }
_identity identity;

T[][] rotate2(T)(T[][] square) {
    T[][][] divide(T[][] square) {
        int half_len = len(square) / 2;
        T[][] sub_square(int nrow, int ncol) {
            T[] row;
            return select(row[ncol ..ncol + half_len], row, square[nrow .. nrow + half_len]);
        }
        auto upper_left = sub_square(0, 0);
        auto lower_left = sub_square(half_len, 0);
        auto upper_right = sub_square(0, half_len);
        auto lower_right = sub_square(half_len, half_len);
        return [upper_left, lower_left, upper_right, lower_right][];
    }

    T[][] recombine(T[][][] parts) {
        auto upper_left = parts[0];
        auto lower_left = parts[1];
        auto upper_right = parts[2];
        auto lower_right = parts[3];
        T[][] lr;
        return select(lr[0] ~ lr[1], lr, azip(upper_right, lower_right)) ~
               select(lr[0] ~ lr[1], lr, azip(upper_left, lower_left));
    }

    return divide_and_conquer(square,
                              (T[][] square){return len(square) > 1;},
                              identity,
                              ÷,
                              &recombine);
}
Note the complex return type, that infers the type from a little function built on the fly:
ReturnType!({ return F2.init(Init!(T)().init); })
In D V.2 you can just replace that with "auto", simplifying the code, using type inference on the return type.

Init!(T)().init replaces a T.init, it's a way I have invented to work around a bug of the DMD compiler, that gives a wrong result if T is a static array.

divide_and_conquer() in D doesn't currently work for a sum_squares4() function, because it requires isdivisible to be a compile-time template (used as a function, and passed with an alias, to the outer template) to the function template divide_and_conquer(), instead of being passed as delegate (or function pointer) as now. You can call it like this:

divide_and_conquer2!(IsItetrable)(seq, sqr, identity, sumb)

Where sqr and sumb are something like:
struct _sqr { static typeof(T.init * T.init) opCall(T)(T x) { return x * x; } }
_sqr sqr;

struct _sumb { static typeof(sum(Init!(T)().init)) opCall(T)(T seq) { return sum(seq); } }
_sumb sumb;
Probably there's a way to make this work, but after some tried I have given up. I think that such working code can be written, but you end with two different versions of divide_and_conquer(), so if you want a single function you probably need a language with a more flexible type system than the current D1 one (I presume Haskell is up to the task).

Finally I have tried to adapt the Python code to ShedSkin Python, I have had to pull out nested functions and to replace a generator expression with a list comp. I think that currently you can't write sum_squares4() because there's no way to write that isiterable() function shown in the Python code:
def isiterable(value):
    try:
        iter(value)
    except TypeError:
        return False
    else:
        return True
(And even once writing such function becomes possible, I don't know if the type system of ShedSkin is able to compile divide_and_conquer() that becomes polimorphic). So currently ShedSkin seems quite less flexible than the D language.
comments: Leave a comment Previous Entry Add to Memories Share Next Entry

leonardo - A recursive combinator
View:Recent Entries.
View:Archive.
View:Friends.
View:Profile.
View:Website (My Website).