Thu Jul 3 20:34:44 CEST 2008

image iterators + dont-care regions

Algorithms simplify a whole lot if dont-care regions can be
constructed: no need to handle border conditions, except for the
initial tiling step (duplication). The duplication this gives is
probably not problematic since it's 2nd order.

The players:

  * unary operators + 1 image mapper
  * binary operators + 3 image mappers:
      - 2 images
      - 1 image with X or Y shift

  * image accumulators
  * coordinate iterators

Maybe I'm just getting tired, but it's really hard to chop this into
primitives. One of the things that keeps getting in the way is to
create the correct type of result accumulator from the input type. The
problem is: the right model is not (+ a b) but (set! r (+ a b)) which
can then be used to create a (+ a b).

Maybe build it around this:

(define (inner-loop! i i->j fn r a b)
  (vector-set! r i
               (fn (vector-ref a i)
                   (vector-ref b (i->j i)))))

r:    result vector
i:    main index
i->j: main index to secondary index map
fn:   binary function
a:    first input vector
b:    second input vector (can be same as first)

Funny, what i'm re-inventing here are the x and y operators in the
generating function / Z transform (xy transform?) representation of 2D
sequences, but bound to a function. I.e.

  lifters : function => sequence operator

   lift   : +    ->   +
   lift-x : +    ->   1 + x
   lift-y : +    ->   1 + y

Maybe the base language should just be ordinary math functions and
2-variate polynomials? This should be more than enough to generate
tiling + appropriate iterators.

I've come full circle: starting with algebra -> DSP -> implementation
of algorithms -> generalization in language -> algebra.

Anyways, for the 2 shifts in a framework of 2^n tiles, it is possible
to use modulo addressing, which simplifies code a lot.

Sobel:   (1 - y)^2 + (1 - x)^2

Ok, got it to work:

(define (sobel i)
  (define ^2 (U (lambda (x) (* x x))))
  ((B +)
   (^2 ((X -) i))
   (^2 ((Y -) i))))

U unary lift
B binary lift
X binary x-shift lift
Y binary y-shift lift

So.. These are 2 different views: the operator view (where X and Y
denote the shift operators) and the higher order function view, where
unary and binary scalar operations are mapped to unary and binary
image operations. The latter language seems more general: easier to
work with multiple arguments.