Sunday, December 30

Types and Programming Languages Revisited

My previous brute-force approach to list all the 4-dimension combinations of S = {(latent, manifest), (static, dynamic), (weak, strong), (nominal, structural)} typing -by filtering the desired tuples from the powerset of S - wasn't very efficient.
It was a perfect example of The Danger of Naïveté: an inefficient algorithm that was nevertheless simple to devise and implement.

Moreover, quoting The eight rules of Dean Carney, I should have observed that "the first place to look for a solution is within the problem itself". If the problem involves 4 tuples of 2 elements each to begin with, the efficient solution is not likely to require the powerset of all 8 elements.

Thus, I figured I should give it another go.

First, for simplicity and better readability, let me replace the values of S with the character-tuples on the left hand side:

(A, B) = (latent, manifest)
(C, D) = (static, dynamic)
(E, F) = (weak, strong)
(G, H) = (nominal, structural)

S = {(A, B), (C, D), (E, F), (G, H)}

Next, I'll write down some 4-size combinations. After a short while, a pattern emerges:

ACEG
ACEH
ACFG
ACFH
ADEG
ADEH
...

The pattern becomes clear when I look at the elements like this:

X1=(A, B) x X2=(C, D) x X3=(E, F) x X4=(G, H)

This is a Cartesian product of X1 x X2 x ... x Xn, the set containing all possible combinations of one element from each set.

With this knowledge, implementing an efficient algorithm is easy. First, a method to return the Cartesian product of two sets:


# arguments must be lists, e.g.: cartesian([1, 2], [3, 4])
def cartesian(list1, list2):
     result = []
     for el in list1:
         for item in list2:
             if isinstance(el, list):
                 result.append(el + [item])
             else:
                 result.append([el] + [item])
     return result


Testing the method with input X=[1, 2] x Y=[3, 4] yields:


     [[1, 3], [1, 4], [2, 3], [2, 4]]


Which looks good.
Next, a method to process the Cartesian product of any number of sets. Here's a candidate implementation:



def types_cartesian(aList):
     head = aList[0]
     tail = aList[1:]
     for item in tail:
         head = cartesian(head, item)
     return head


The output of method types_cartesian(aList) given input aList=S is:

S={['static', 'dynamic'], ['weak', 'strong'], ['latent', 'manifest'], ['nominal', 'structural']}

S1 x S2 x ... Sn =


     ['static', 'weak', 'latent', 'nominal']
     ['static', 'weak', 'latent', 'structural']
     ['static', 'weak', 'manifest', 'nominal']
     ['static', 'weak', 'manifest', 'structural']
     ['static', 'strong', 'latent', 'nominal']
     ['static', 'strong', 'latent', 'structural']
     ['static', 'strong', 'manifest', 'nominal']
     ['static', 'strong', 'manifest', 'structural']
     ['dynamic', 'weak', 'latent', 'nominal']
     ['dynamic', 'weak', 'latent', 'structural']
     ['dynamic', 'weak', 'manifest', 'nominal']
     ['dynamic', 'weak', 'manifest', 'structural']
     ['dynamic', 'strong', 'latent', 'nominal']
     ['dynamic', 'strong', 'latent', 'structural']
     ['dynamic', 'strong', 'manifest', 'nominal']
     ['dynamic', 'strong', 'manifest', 'structural']


This is the same list as the one obtained earlier with the powerset approach.
The big difference is that with the powerset implementation the number of possible combinations explodes exponentially ( O(2n) ), whereas the Cartesian product is a quadratic ( O(n2) ) algorithm.

Here's the code.


Related:
Types and Programming Languages
http://en.wikipedia.org/wiki/Cartesian_product
http://programming-misc.googlecode.com/svn/trunk/python/types_cartesian.py
What to know before debating type systems

2 comments:

Anonymous said...

Parece-me que alguém anda com tempo a mais ;)
Bom ano fofinho :D ... para que nao penses que te ignorei preferi responder-te por aqui ao invés de um sms. É mais pessoal, o pessoal não percebe um corno porque é português, e ainda te posso mandar recados subliminares, como desejar-te felicidades e que sejas feliz nesse golpe do baú de que tu foste alvo, hehehe

Helen Neely said...

Nice and clear review. But I think beginners still need the basics to fully grasp what's going on her