[nolan@nprescott.com] $  cat weblog archive feed

Refactoring Klong

2019-08-08

Thinking some about my last post, trying to identify contours in an image using Klong; I realized I had not attached the full source as I have been for these weird little Klong programs and it got me thinking about how to write more concisely.

Where We Left Off

Below is pretty much the entire program (and test data!) that was developed by the end of the last post:

vf::{(-|/{#$x}'x)$x}
mf::{+vf'+x}
pm::{{{.d(" ");.d(x)}'x;.p("")}'mf(x);[]}
pbm::{.p("P1"); pm(,1:+^x); pm(x)}

move::{[a b]; a::x; b::y; {a:+x}({+b:++x}(z))}
neighbors::{[a]; a::x; +/,/{[b]; b::x; move(b;;a)'[-1 0 1]}'[-1 0 1]}
MaxN::{[a]; a::x; |/,/{[b]; b::x; move(b;;a)'[-1 0 1]}'[-1 0 1]}

example::[
[0 0 0 0 0 0 0 0 0 0] 
[0 1 1 1 0 0 0 0 0 0] 
[0 1 1 1 0 1 1 1 0 0] 
[0 1 1 1 1 1 1 1 0 0] 
[0 1 1 1 1 1 1 1 0 0] 
[0 1 1 1 1 1 1 1 0 0] 
[0 0 1 1 1 1 0 0 1 0] 
[0 1 1 1 1 1 0 0 1 0] 
[0 1 1 0 0 0 0 0 1 0] 
[0 0 0 0 0 0 0 0 0 0]]

border::(~~neighbors(example))-example
MaxN(border)&example

A Higher Order Function Appears

One neat trick that I came up with after a bit of thinking was a way to abstract the two similar "neighbor search" functions (above they are neighbors and MaxN). Each does nearly the same thing, creating 9 separate matrices shifted in a different direction (of course I know now I'm creating a Moore Neighborhood) and aggregating them together. I realized I could make a higher-order function where the function argument could be this aggregation:

aggregate::{[f a]; f::x; a::y; 
            f/,/{[b]; b::x; move(b;;a)'[-1 0 1]}'[-1 0 1]}

What it does is accept a dyad as its first argument and a matrix with which to apply the shifts and aggregation. In the case of the Game of Life-style "sum surrounding points" the aggregation is just a sum between successive matrices, which can be defined like so:

localSum::{aggregate({x+y}; x)}

Perhaps one tricky bit is to realize the x within the curly braces is not the same as the second x. The first is bound within the function definition of the nested curly braces, the second is the first argument to our new function localSum.

In the case of the second application of the neighbor-like pattern, instead of a sum I wanted a max, which Klong provides (|), so I just have to wrap it in the same manner:

localMax::{aggregate({x|y}; x)}

Over all this felt like a cool kind of realization that some standard functional programming patterns can still apply in array programming and the end result is (to me) approaching readable.

A Realization

It finally occurred to me I was creating more work than really necessary, there's no need to do a sum and then double-negate it — this is doable entirely with the second aggregation function, localMax! Doubly negating a sum is really just serving to flag a point as having a neighboring, occupied point; which is the same as asking for a maximum of the two in a bitmap such as this.

The end result is perhaps a bit anticlimactic, my higher-order function is used only once as a means to improve the readabilty.

:"pretty printing and display output helpers"
vf::{(-|/{#$x}'x)$x}
mf::{+vf'+x}
pm::{{{.d(" ");.d(x)}'x;.p("")}'mf(x);[]}
pbm::{.p("P1"); pm(,1:+^x); pm(x)}

move::{[a b]; a::x; b::y; {a:+x}({+b:++x}(z))}

:"first argument is a dyad, second a matrix"
aggregate::{[f a]; f::x; a::y; 
            f/,/{[b]; b::x; move(b;;a)'[-1 0 1]}'[-1 0 1]}
localMax::{aggregate({x|y}; x)}

example::[
[0 0 0 0 0 0 0 0 0 0] 
[0 1 1 1 0 0 0 0 0 0] 
[0 1 1 1 0 1 1 1 0 0] 
[0 1 1 1 1 1 1 1 0 0] 
[0 1 1 1 1 1 1 1 0 0] 
[0 1 1 1 1 1 1 1 0 0] 
[0 0 1 1 1 1 0 0 1 0] 
[0 1 1 1 1 1 0 0 1 0] 
[0 1 1 0 0 0 0 0 1 0] 
[0 0 0 0 0 0 0 0 0 0]]

border::(localMax(example))-example
contour::localMax(border)&example

pbm(contour)