2005-06-21
http://xahlee.org/tree/tree.html

----------

here's the Python spec for the Table function:

'''Table(f,[iStart,iEnd,iStep]) returns a list of f applied to the
range range(iStart,iEnd,iStep).  Example: Table(f,[3,10,2]) returns
[f(3),f(5),f(7),f(9)] Table(f,[iStart,iEnd,iStep],
[jStart,jEnd,jStep], ...) returns a nested list of f(i,j,...) applied
thru the iterators.  Example: Table(f,[1,2,1],[2,6,2]) returns
[[f(1,2),f(1,4),f(1,6)],[f(2,2),f(2,4),f(2,6)]]'''

it is slightly shortcut from the full form in that it doesn't allow
short cut conveniences. For example, one should be able to write
Table(f,[4], [1,9,2]) for Table(f,[1,4,1], [1,9,2])

Also, the first argument of expression has changed to a function
instead. Expression is much more convenient, but in languages that
isn't symbols oriented, a function is more appropriate.

anyhow, for simplicity, let's start with this simpler spec.

I started to code this problem but this is quite a large problem, so i
figured it'd be fruitful to discuss it as we go.

The first problem i noted is that in Python, one cannot assign
elements in arrays where it doesn't exist yet. i.e.  a[7]=2 is
illegal. This is in contrast to Perl, where one can do: $a[3][7][2]=4
and automatically have a 3-dimensional nested array, where other
members simply have undefined values.

(This behavior of Perl is convenient when needed, but i recall in 2001
i spend the whole half a day trying to debug a program and it turned
out is caused by this behavior.)

With perl, a solution is to have Table simply generate code like the
following, as a string, then eval it.

--------------
my ($i,$j,$k,);
my @resultArray;

foreach $i (0 .. scalar(@{$ref_rangeSequence->[0]}) -1 ) {
foreach $j (0 .. scalar(@{$ref_rangeSequence->[1]}) -1 ) {
foreach $k (0 .. scalar(@{$ref_rangeSequence->[2]}) -1 ) {
$resultArray[$i][$j][$k] = &{Function(\@parameterList,$exprString)} ($ref_rangeSequence->[0]->[$i],$ref_rangeSequence->[1]->[$j],$ref_rangeSequence->[2]->[$k],);
};};};

return \@resultArray;
------------

(in the above code, note the line $resultArray[$i][$j][$k]=...)

Another issue noted is that the so-called “list comprehension” syntax
construction in Python actually also contained a semantic
irregularity. That is to say, when the loops are nested inside a
list-comprehension, it still produced a flat list, instead of a nested
list.

This is quite a pain. I didn't realize this until i completed my code
and realized the result is a flat list. Here's the "wrong" solution:

def Table2(fun, *itrs):
    dim=len (itrs)
    dummies = ['i'+repr(i) for i in Range(0,dim-1)]
    ll = [ (dummies[i],itrs[i][0],itrs[i][1],itrs[i][2]) for i in Range(0,dim-1)]
    funString='f('
    for i in dummies: funString += i + ','
    funString = funString[0:len(funString)-1]
    funString += ')'
    loopStr= '[ ' + funString
    for i in range(0,dim):
        loopStr += ' for ' + dummies[i] + ' in Range(' + repr(itrs[i][0])+','+repr(itrs[i][1])+','+repr(itrs[i][2]) + ') '
    loopStr += ' ]'
    print loopStr
    return eval(loopStr)

I was happy thinking that i'm done until am really dismayed by a
realization of this semantic irregulary. Both syntax irregularity and
semantic irregularity are ubiquitous in imperative languages.

So, now i have two choices:

(1) add another code to make a structure out of a flat list.
e.g. turn [1,2,3,4,5,6] to [[[1,2]],[[3,4]],[[5,6]]]

(2) rewrite the Table function to not use list comprehension. Instead, use for loops.

I started to do (1) by writing a separate Partition function... but in
the process i think perhaps (2) is better...

• Python: Generate List (List Comprehension)
• Why List Comprehension is Bad