Sat Mar 31 12:14:13 EDT 2007


border values

using finite grids, borders need to be handled. basicly, invalid
indexing operations need to be replaced by valid ones. some

constant:    (a -1 0 0) -> c
repeat:      (a -1 0 0) -> (a 0 0 0)
wrap:        (a -1 0 0) -> (a (wrap -1) 0 0)

how to name border regions? there are several distinct cases, for
example a square grid has these:

(L L) (I L) (H L)
(L I) (I I) (H I)
(L H) (I H) (H H)

L  low boundary
I  bound to iterator
H  high boundary

with looping indicated by { ... } a full 2D loop looks like:

   (L L)           ;; top left
   { (I L) }       ;; top
   (H L)           ;; top right
       (L I)       ;; left
       { (I I) }   ;; bulk
       (H I)       ;; right
   (L H)           ;; bottom left
   { (I H) }       ;; bottom
   (H H)           ;; bottom right

that basicly solves the problem. note that it's best to lay out the
code in a L I H fashon to keep locality of reference.

on to representation.

the loop body is a serialization of an N-dimensional 3-grid. (a 2-grid
is a hypercube). it's serialized into a ternary tree.

how to represent ternary trees? the following representation looks
best in standard lisp notation:

     ((L . H) . I)

other variants have the dot in an awkward place. another possible rep
is (I H L) which can be written in mzscheme's infix notation as

      (H . I . L)

i'm going for the former, as it allows to use (B . I) in case L and H
are the same. in order to generate the full loop body.

EDIT: it's easier to just use s-expressions: (range H I L), and have
'range' to be a keyword..

loop borders can be constructed using the data structure provided by

ah! it's possible to separate the operations performing loop order
allocation and pre/post expansion, but probably not very
desirable.. so let's combine them, so we can get rid of using natural

note: i found out that when i needs index lists, i'm doing something
wrong: applying a certain order on things...

so, in order to generate the tree above, we consume coordinates from
left to right. all loop transformations need to be done on the source
code before generating loop bodies.