Tuesday, May 12, 2009

Oz: Translating Python into Oz

I've been working my way through Concepts, Techniques, and Models of Computer Programming. In chapter 3, one of the exercises was to transpose a matrix.

I immediately felt completely overwhelmed. I couldn't even remember what it meant to transpose a matrix, and I definitely hadn't seen anything matrix-related in the book. I went to Wikipedia and figured out that transposing a matrix just means swapping the rows and the columns. That seemed more possible, but I still didn't think I had the necessary tools to code it in Oz yet.

I decided to try solving the problem in Python. Python is sometimes called "executable pseudocode", and sure enough, the solution came to me pretty easily:
m = [[1, 2, 3],
[4, 5, 6]]

def transpose(m):
transposed = []
if len(m) >= 1:
len_cols = len(m[0])
for col in xrange(len_cols):
transposed_row = []
for row in m:
return transposed

print transpose(m)
Now, in real life, I might refactor that into the following:
m = [[1, 2, 3],
[4, 5, 6]]

def transpose(m):
if not m:
return []
return [[row[col] for row in m]
for col in xrange(len(m[0]))]

print transpose(m)
However, the goal was to write the solution in Oz, not Python. Hence, I started refactoring the code into something I could translate to Oz. Oz uses Lisp-like lists, not arrays, and at least for the chapter I'm in, it uses recursion, not foreach loops. Hence I ended up with:
m = [[1, 2, 3],
[4, 5, 6]]

def transpose(m):

def transpose_row(m, i, transposed_row):
if not m:
return transposed_row
car, cdr = m[0], m[1:]
transposed_row.insert(0, car[i])
return transpose_row(cdr, i, transposed_row)

def iter_row_len(i, transposed):
if i == row_len:
return transposed
transposed.insert(0, transpose_row(m, i, []))
return iter_row_len(i + 1, transposed)

if not m:
return m
row_len = len(m[0])
transposed = iter_row_len(0, [])
return transposed

print transpose(m)
At this point, it was fairly straightforward to translate that into Oz:
declare M
M = [[1 2 3]
[4 5 6]]

fun {Transpose M}
fun {TransposeRow M I TransposedRow}
case M
of nil then
{Reverse TransposedRow}
[] M1|Mr then
{TransposeRow Mr I {List.nth M1 I}|TransposedRow}
fun {IterRowLen I Transposed}
if I==RowLen+1 then
{Reverse Transposed}
{IterRowLen I+1 {TransposeRow M I nil}|Transposed}
case M
of nil then nil
[] M1|Mr then
RowLen={Length M1}
{IterRowLen 1 nil}

{Browse {Transpose M}} % Prints [[1 4] [2 5] [3 6]]
Viola! Problem solved!

That solution is pretty long, which just goes to show how bad an Oz programmer I am. I found someone else's solution online:
fun {Transpose Matrix}
{List.foldR Matrix
fun {$ R1 R2} {List.zip R1 R2 fun {$ E1 E2} E1|E2 end} end
for E in Matrix.1 collect:C do {C nil} end}
Obviously, he knows Oz and functional programming in general a heck of a lot better than I do.

The moral of the story is that Python can indeed serve as executable pseudocode, but it won't help me to think like an Oz programmer.


Paddy said...

A cute way of transposing
m = [[1, 2, 3], [4, 5, 6]]

thats it..done

Shannon -jj Behrens said...

Bravo! I'd add the following, though, to make sure the lists stay lists:

map(list, zip(*m))