# Co-operators

# by Phil Last ([email protected])

Based on a presentation given at Dyalog’11 in Boston on 5 Oct 2011, Phil Last develops some demonstrative operators to solve some common programming problems.

## Preamble

I’ve been developing user-defined operators since a time when it was
only possible to simulate them by executing prepared
expressions that include a function name passed as left argument to
another function. The following allowed first-generation APLs to use
reduction with any dyad. (See the Appendix for definitions of the functions
`f`

, etc. used to explicate the parsing.)

∇ R←F RED W [1] ⍝ R←F⌿W [2] R←''⍴⍴W [3] R←⍎(⍴,F)↓,((R,⍴,F)⍴F),' ','W','[',(⍕(⍳R)∘.+,0),((R,-1-⍴⍴W)⍴';'),']' ∇ 'f' RED ⍳6 ( 0 f( 1 f( 2 f( 3 f( 4 f 5 ))))) '∊' RED 2 5⍴'aeiou','vowel' 0 1 0 1 0

So when IBM announced a mechanism for users to define their own operators in about 1983 I had a queue of them awaiting proper implementation.

When Dyalog announced D-fns with lexical scope in 1997 I unashamedly switched to using that as my standard notation for all new functions and operators and embedding D-fns for most amendments to old ones. So without apology I’ll warn you that almost everything you’ll see here is in D-notation. Also that some coding techniques might be new to you.

In the original paper to the Boston presentation I included a short note about those techniques. This time I refer you to a companion article that appears in the same edition of Vector as this: “A way to write functions”. If you see anything here that is confusing or appears to make no sense at all you’ll probably find it explained there.

Application-specific operators tend to be rare, often restricted to two or three in a large application while I currently have a collection of over forty more-or-less general purpose ones. It’s always mystified me that so few APLers seem to write or even use them at all.

A simple piece of code that maps or operates on one or two input arrays of known domain and structure can be extracted and encapsulated into a function that can be called upon whenever needed and this perhaps should almost always be done. An extension of that where different but syntactically congruent operations were to be applied would encourage us to write an operator and pass the operation in as a parameter along with the arrays.

I should mention here that, strictly speaking, when we write an operator what we are writing is the definition of the derived function of that operator. When we say an operator returns a function, the operator actually does nothing of the sort. The parser merely binds it with its one or two operands. All the work specific to that operator is still to be done by the derived function and that after it has one or two arguments to operate on. In what follows I’ll almost certainly forget this distinction between the derived function and the operator and refer to the operator’s doing things which are actually the province of the derivation. I doubt that this will confuse.

## Co-operators

A class of operator that I’ve become interested in comprises those that are designed to be called multiple times within the same expression:

[a] f op g op h op j op k op l w

where `a`

and `w`

are arrays; ```
f, g, h, j,
k
```

and `l`

are functions (see Appendix); and `op`

is the operator in question. The first and most obvious thing to notice
about this is that the operator is dyadic – it takes two operands – making
the number of operands in the expression one more than the number of calls
to the operator. I’ll mention here that I’ll use Iverson’s names for monadic
and dyadic operators – adverb and conjunction – if I need to distinguish them. Although without an awful lot of messy code an operator can’t examine its
operands – it just runs them on trust – in this context we need to know
something about them. I’m calling these co-operators because in order to
be useful they must take account of the likelihood that they are not
operating alone.

An examination of the calling sequence of the above expression will help. Redundant parentheses show how it’s parsed:

[a] f op g op h op j op k op l w [a](((((f op g)op h)op j)op k)op l)w

In first-generation APL this was explained as operators’ having ‘long left scope’ as opposed to functions’ having ‘long right scope’. Along with strand-notation and the generalisation of operators came the idea of ‘binding strength’. The above parsing is now explained on the basis of right-operand binding’s being stronger than left – so an operand between two conjunctions is bound by the one whose right operand it is; that to its left.

In the case above `g`

is bound by `op`

to its left,
`h`

by that to its left and so on to the rightmost `op`

that has the whole function expression to its left `f...k`

as
its left operand – ‘long left scope’. A corollary to this is that all but
the leftmost call to `op`

have left operands derived from
`op`

itself, that exception being the greatest complication in
all that follows; we need to identify what is that ‘leftmost call’ because
we’ll have to treat it differently. We also can be sure that the right operand
of every instance of `op`

is one of the original operands
of the unparenthesised expression. The arguments to the expression become the
arguments to the first call, the rightmost.

## Function selection

Here’s a simple operator to start us off. I never got into writing case statements like:

:Select whatever :Case this ⋄ ... :Case that ⋄ ... ...

because I’d already started using operators to control program flow
before control structures were implemented in APL and D-fns don’t permit
them even if I wanted them. Instead consider an operator – call it
`or`

– to be used as:

0 0 1 0 f or g or h or j w ←→ 0 0 1 0(((f or g)or h)or j)w

I hope you can guess what this is intended to do. In the specific case
above I want the result to be the result of `h w`

, the boolean vector being
used as a mask to select from the four operand functions which to apply
to argument `w`

.

We could imagine this as being implemented something like:

(0 0 1 0 / (f g h j))w

where a boolean compression is applied to an isolated list of functions but such a list is not recognised by APL as something it can deal with in any way let alone being able to apply compression to it. More about this later.

I’ll allow only the first, leftmost, 1 to select the function,
effectively treating the boolean as if it’s its own less-than scan
`<\`

. If the mask is all zeros we shouldn’t actually want to
run any function at all; we should merely return the argument. So here
are the first two lines:

or←{ ~∨/⍺:⍵

Looking at the parenthesised version above we can see that the
rightmost `or`

has:

⍺⍺ ←→ f or g or h ⍵⍵ ←→ j

So if only the final element of `⍺`

is a 1 we can run `j`

:

</⍺:⍵⍵ ⍵

If this isn’t the case then we need to do something with `⍺⍺`

.
We need to call it without the final element of `⍺`

that
applied to `j`

. So:

or←{ ~∨/⍺:⍵ </⍺:⍵⍵ ⍵ (¯1↓⍺)⍺⍺ ⍵ } 0 0 0 0 f or g or h or j 23 23 0 0 0 1 f or g or h or j 23 (j 23 ) 0 0 1 1 f or g or h or j 23 (h 23 ) 0 1 0 0 f or g or h or j 23 (g 23 ) 1 0 0 1 f or g or h or j 23 ( 1 f 23 )

These all look right except for `f`

. I mentioned the
complication of the leftmost call in the eponymous section above. In
this we’ve called `f`

as dyad `⍺⍺`

in the final line
of `or`

. Another statement is needed to call `⍺⍺`

when it’s the leftmost of the supplied operands. We know that by then
our expression is `f or g`

so `⍺`

must
have a length of 2. If it were 0 0 we should have returned `⍵`

unchanged on line:

[1] ~∨/⍺:⍵

If it were 0 1 we should have run `g`

on line:

[2] </⍺:⍵⍵ ⍵

So it must be 1 0 or 1 1 and in either case we should run `f`

:

[2.1] 2=⍴⍺:⍺⍺ ⍵

So:

or←{ ~∨/⍺:⍵ </⍺:⍵⍵ ⍵ 2=⍴⍺:⍺⍺ ⍵ (¯1↓⍺)⍺⍺ ⍵ } 1 0 0 0 f or g or h or j 23 (f 23 )

We can make an alternative version of this that, rather than selecting the function indicated by only the first 1, will select all corresponding functions:

0 1 0 1 f or g or h or j 23 (g(j 23 ))

We need to look at the last item of `⍺`

whether it’s the only one or
not and use the power operator to run `⍺⍺`

and `⍵⍵`

conditionally:

or←{ ~∨/⍺:⍵ g←⍵⍵⍣(⊢/⍺) 2=⍴⍺:⍺⍺⍣(⊣/⍺)g ⍵ (¯1↓⍺)⍺⍺ g ⍵ } 1 0 1 0 1 1 f or g or h or j or k or l 45 (f(h(k(l 45 ))))

## Function sequence

If we look at the reduction operator we see:

f/12 23 34 45 ( 12 f( 23 f( 34 f 45 )))

the function is inserted between the items of the argument. If the function could be a list then perhaps we could do:

(f g h j)/12 34 56 78 90 ( 12 f( 34 g( 56 h( 78 j 90 ))))

Again we can’t do this because `f g h j`

is illegal in APL. J
implements this concept with the `tie`

conjunction ```

to bind the functions in a list of ‘gerunds’ that it applies with `/`

:

+`-`*`% / 1 2 3 4 5 0.6

But we can interpose a defined operator both to bind the functions and insert them:

f seq g seq h seq j 12 34 56 78 90 ←→ ((f seq g)seq h)seq j 12 34 56 78 90 ←→ 12 f 34 g 56 h 78 j 90

Notice we have one more item in the argument than there are operands in the expression and one more of them than there are calls to the operator. Also that the operands are dyads while the derived function is a monad. The first (rightmost) call will have:

⍺⍺ ←→ f seq g seq h ⍵⍵ ←→ j ⍵ ←→ entire right argument

so we can run `j`

between the last two items using reduction
and catenate its result to the rest running `⍺⍺`

on that result:

seq←{ ⍺⍺(¯2↓⍵),⍵⍵/¯2↑⍵ } f seq g seq h seq j 12 34 56 78 90 (f 12 ( 34 g( 56 h( 78 j 90 ))) )

Visually scanning from the right looks good until we get to `f`

.
Again it’s the leftmost function that adds the complication. When `f`

is the left operand, `f seq g`

must be the sub-expression, there must be three items in `⍵`

so we do almost the same but we apply `⍺⍺`

between rather than to the remaining pair after doing the same with `⍵⍵`

:

seq←{ 3=⍴⍵:⍺⍺/(¯2↓⍵),⍵⍵/¯2↑⍵ ⍺⍺ (¯2↓⍵),⍵⍵/¯2↑⍵ } f seq g seq h seq j 12 34 56 78 90 ( 12 f( 34 g( 56 h( 78 j 90 )))) + seq - seq × seq ÷ 1 2 3 4 5 0.6

and get our expected result.

## Function arrays

Another meaning that could be attributed to an isolated list of functions was in fact my first accidental encounter with them after about three months of APL. I had to solve the simple problem of the dimensions of a matrix formed from three others; one above the juxtaposition of the other two:

.----------------------------. | A | |-------------.---------------------. | | C | | B | | | |---------------------' '-------------'

APL seemed so good at doing whatever I hoped it would that what I wrote was:

(⍴A)(+⌈)(⍴B)(⌈+)(⍴C)

expecting the pairs of functions to be distributed between the pairs of dimensions of the three matrices:

.----.-------.----.-------. | | | | | (⍴A)[0 1](+⌈)(⍴B)[0 1](⌈+)(⍴C)[0 1] | | | | | '---'--------'---'--------'

Of course it didn’t work, for the same reason that the other constructs
above didn’t work. Although in this case there are only two functions in
each list we can extrapolate this to a list of functions corresponding
to a vector of any length. If we define conjunction `fv`

(function
vector) we’ll want:

a b c d (f fv g fv h fv j) w x y z ⍝ [0] a b c d (f fv g fv h fv j) ⊂w ⍝ [1] (⊂a) (f fv g fv h fv j) w x y x ⍝ [2] (f fv g fv h fv j) w x y z ⍝ [3]

Our perennial problem of identifying the leftmost operand will depend on
the length of the argument(s) as they must conform to the number of
functions. We can check for a monad and for the two-item final call. But
in cases [1] and [2] above `⍺`

or `⍵`

is a scalar
so before the length check we’ll resolve scalar extension with laminate
and split creating `A`

as 0 if `⍺`

isn’t supplied.
If that’s the case we won’t use it anyway but it’s easier to do it
redundantly than to skip it:

fv←{ ⍺←⊢ m←1≡⍺ 1 (A W)←↓(⍺⊣0),[-0.1]⍵ t←2=⍴W

For the two-item monad we want the two functions `⍺⍺`

and `⍵⍵`

applied
to the two items of `W`

:

t∧m:(⍺⍺ 0⊃W)(⍵⍵ 1⊃W)

If it’s a monad and this doesn’t run it must have more than two items. We
apply `⍵⍵`

to the last item of `W`

and `⍺⍺`

to the rest:

m:(⍺⍺ ¯1↓W),⍵⍵¨⊢/W

If it’s still two items it must be a dyad so we do similar to the
`t∧m:`

case but using `A`

also:

t:((0⊃A)⍺⍺ 0⊃W)((1⊃A)⍵⍵ 1⊃W)

We must be left with the dyad with more than two items so we do similar
to the `m:`

case but with `A`

also:

((¯1↓A)⍺⍺ ¯1↓W),(⊢/A)⍵⍵¨⊢/W }

Putting this all together:

fv←{ ⍺←⊢ m←1≡⍺ 1 (A W)←↓(⍺⊣0),[-0.1]⍵ t←2=⍴W t∧m:(⍺⍺ 0⊃W)(⍵⍵ 1⊃W) m:(⍺⍺ ¯1↓W),⍵⍵¨⊢/W t:((0⊃A)⍺⍺ 0⊃W)((1⊃A)⍵⍵ 1⊃W) ((¯1↓A)⍺⍺ ¯1↓W),(⊢/A)⍵⍵¨⊢/W }

1 2 3 4 f fv g fv h fv j 5 6 7 8 ( 1 f 5 ) ( 2 g 6 ) ( 3 h 7 ) ( 4 j 8 ) 1 2 3 4 f fv g fv h fv j 5 ( 1 f 5 ) ( 2 g 5 ) ( 3 h 5 ) ( 4 j 5 ) 1 f fv g fv h fv j 5 6 7 8 ( 1 f 5 ) ( 1 g 6 ) ( 1 h 7 ) ( 1 j 8 ) f fv g fv h fv j 5 6 7 8 (f 5 ) (g 6 ) (h 7 ) (j 8 ) 1 2 3 4 + fv - fv × fv ÷ 5 6 7 8 6 ¯4 21 0.5

## Conditionals

:If f w :AndIf g w r←h w :Else r←j w :End

As I mentioned above I really can’t do with having to do stuff like that. It was always easy to write operators that did:

f then g w ⍝ if f w then r←g w else r←w t g else h w ⍝ if t then r←g w else r←h w ⍝ see *else* below

But putting them together to form something like:

f then g else h w ⍝ if f w then r←g w else r←h w

was never going to be so easy. The two conjunctions `then`

and```
else
```

need to co-operate, `f then g`

being an
operand of `else`

, and introducing interdependencies should be
avoided whenever possible. So how about a single co-operator that fulfils
both tasks? The biggest problem is what to call it. I believe at least
one language uses `?`

for this – not a bad choice:

antecedent ? consequent ? alternative arg

I’ll use cond which I also believe is used elsewhere so that in:

f cond g cond h w ←→ ((f cond g)cond h) w

we apply `f w`

first then `g w`

if `f w`

proves true or `h w`

otherwise. The length of the argument isn’t
going to help as it could be anything at all. One thing we do know is that
there’s no left argument. It wouldn’t make any sense if there was. The right
call has:

⍺⍺ ←→ (f cond g) ⍵⍵ ←→ h

We can’t do anything with `h`

yet as that’s the alternative we want
to run if `f`

returns false so we need to run `⍺⍺`

and
we need to do it in such a way that it runs one or other of `f`

and `g`

. We can use that missing left argument as an internal flag
to tell the left call what to do. Arbitrarily we’ll give it a 1 to tell it
to run `f`

and a 0 for `g`

if `f`

returns true:

cond←{ ⍺←⊢ 1 ⍺⍺ ⍵:0 ⍺⍺ ⍵

but this is no good because as soon as we call it it’ll just call itself
again unconditionally. We actually need to test `⍺`

for being a 1
or 0 before we use it! Please see the companion article if lines [2] and [3]
below confuse:

cond←{ ⍺←⊢ 1=⍺⊣0:⍺⍺ ⍵ ⍝ if ⍺ is 1 run f ⍵ 0=⍺⊣1:⍺⍺ ⍵ ⍝ if ⍺ is 0 run g ⍵

If `⍺`

is ever going to be 1 or 0 we need to make it so, so now we
run the line higher up with the two calls to `⍺⍺`

. If
`1 ⍺⍺ ⍵`

which calls `f ⍵`

is true we run `0 ⍺⍺ ⍵`

that calls `g ⍵`

1 ⍺⍺ ⍵:0 ⍺⍺ ⍵

but if `f w`

isn’t true we run `h ⍵`

instead.

⍵⍵ ⍵ } cond←{ ⍺←⊢ 1=⍺⊣0:⍺⍺ ⍵ ⍝ if ⍺ is 1 run f ⍵ 0=⍺⊣1:⍵⍵ ⍵ ⍝ if ⍺ is 0 run g ⍵ 1 ⍺⍺ ⍵:0 ⍺⍺ ⍵ ⍝ if f ⍵ then g ⍵ ⍵⍵ ⍵ ⍝ else h ⍵ } >∘0 cond j cond k 23 (j 23 ) >∘0 cond j cond k ¯45 (k ¯45 )

*else*: now if we look at the `else`

expression that
we saw a couple of pages back; I’ve copied it here for convenience:

t g else h w ⍝ if t then r←g w else r←h w

and just out of interest we try it with `cond`

we find:

1 g cond h 67 (g 67 ) 0 g cond h 67 (h 67 )

that cond is indeed a working else and we can see why on those lines [2]
and [3] above. This isn’t the way we should have written `else`

because
lines [4] and [5] won’t run in either case but it’s quite nice that the
co-operator also works as a stand-alone:

f cond g cond h w ⍝ if f w then r←g w else r←h w t g cond h w ⍝ if t then r←g w else r←h w

It turns out that that arbitrary 1 and 0 were not so arbitrary after all.

And if we want the usual semantics we can define:

then←{⍺←⊢ ⋄ ⍺ ⍺⍺ cond ⍵⍵ ⍵} else←{⍺←⊢ ⋄ ⍺ ⍺⍺ cond ⍵⍵ ⍵}

## More conditionals

I started the previous section with an `:If`

construct that included
`:AndIf`

. It turns out that conjunctions `and`

and
`or`

are very easy to write. They aren’t co-operators. They just
happen to work together:

and←{⍺⍺ ⍵:⍵⍵ ⍵ ⋄ 0} ⍝ if ⍺⍺ ⍵ then r←⍵⍵ ⍵ else r←0 or←{⍺⍺ ⍵:1 ⋄ ⍵⍵ ⍵} ⍝ if ⍺⍺ ⍵ then r←1 else r←⍵⍵ ⍵ f and g or h ←→ (f and g)or h

This is *not* the same as `(f ⍵)∧(g ⍵)∨(h ⍵)`

that would run all
functions, `f, g`

and `h`

and determine the result in
the usual APL right to left mode. Operands here are run in left to right
order and then only if they are capable of changing the result exactly as
a series of `:AndIf`

or `:OrIf`

clauses in an
`:If`

clause.

We can now construct the statement at the very top of the “Conditionals” section:

f and g then h else j w ←→ (((f and g)then h)else j)w ⍝ if f w and g w then r←h w else r←j w

but unlike the exclusivity of `:AndIf`

and `:OrIf`

control clauses and remembering that those operands that run will do so in
a strictly left to right order we can write:

f or g and h and j then k else l w ←→ (((((f or g)and h)and j)then k)else l)w

## Forks

J refers to lists of functions as trains and parses them in a very particular way:

A train of 2 functions (2-train) is called a hook, which counts as a function in its own right; an APL equivalent would be:

(f g) ←→ f∘g⍨⍨

so that:

a(f g)w ←→ a f(g w) (f g)w ←→ w f(g w)

A 3-train constitutes a fork (another function) where:

a(f g h)w ←→ (a f w)g(a h w) (f g h)w ←→ ( f w)g( h w)

Beyond the 3-train a fork peels off from the right and becomes the right tine of the next construct, hook or fork, recursively:

(g f h j) ←→ (g(f h j)) (g f h j k) ←→ (g f(h j k)) (g f h j k l) ←→ (f(g h(j k l)))

Even-trains above 2 that simulate a hook whose right tine is a fork aren’t
possible with a single defined operator but we can simulate an odd-train
with a fork operator `fk`

. The only difference will be that due to
operand binding as mentioned above forks will be bound from the left:

f fk g fk h fk j fk k ←→ (f fk g fk h)fk j fk k

We’ll only consider a ‘simple’ fork of three functions here:

a(f fk g fk h)w (a f w)g(a h w) (f fk g fk h)w ( f w)g( h w)

Again at the first call we have:

⍺⍺ ←→ f fk g ⍵⍵ ←→ h

so can do something with `h`

, but we need to pass its result along with the
original argument(s) to the next call where `f`

and `g`

will be available:

fk←{ ⍺⍺(⍺ ⍵)(⍺ ⍵⍵ ⍵) }

But at that next call we don’t want to do the same thing at all.

⍺⍺ ←→ f ⍵⍵ ←→ g

We want to apply `g`

between the results of `f`

and `h`

.
This is the same problem as ever – identifying the subsequent call – but this time we
can’t rely on the length of the argument(s) to tell us when we are there. We need
to pass in a flag to the second call to tell it – as with `cond`

above –
and we might as well have two; one for the monad and one for the dyad. In the
first monadic call we present the flag as left argument to the next call. We
have to hope no-one ever calls our fork with these flags as supplied arguments:

fk←{ ⍺←⊢ (m d)←'left monadic fork' 'left dyadic fork'

if it’s a monad, `⍺`

will be assigned `⊢`

and for all
`x`

` ``x ≡ ⍺ x`

so we pass `m, ⍵`

and the result of
`h`

to the left call:

⍵≡⍺ ⍵:m ⍺⍺(⍵)(⍵⍵ ⍵)

If we get past here we know `⍺`

exists so if it’s our monadic flag
we run `g`

between results of `f`

applied to the origin
`⍵`

and that of `h`

which we computed above as
`(⍵⍵ ⍵)`

:

fk←{ ⍺←⊢ (m d)←'left monadic fork' 'left dyadic fork' ⍵≡⍺ ⍵:m ⍺⍺(⍵)(⍵⍵ ⍵) ⍺≡m:(⍺⍺ 0⊃⍵)⍵⍵ 1⊃⍵ } f fk g fk h 23 ((f 23 )g(h 23 ))

So far so good. The dyad should be very similar. If `⍺`

is
`d`

– the dyadic flag – we run `f`

between our original
arguments and `g`

between that result and `h`

:

⍺≡d:(⊃⍺⍺/0⊃⍵)⍵⍵ 1⊃⍵

If not we’d better make it so passing `d`

, `⍺ ⍵`

, and
`⍺ h ⍵`

in the right dyad:

d ⍺⍺(⍺ ⍵)(⍺ ⍵⍵ ⍵) } fk←{ ⍺←⊢ (m d)←'left monadic fork' 'left dyadic fork' ⍵≡⍺ ⍵:m ⍺⍺(⍵)(⍵⍵ ⍵) ⍺≡m:( ⍺⍺ 0⊃⍵)⍵⍵ 1⊃⍵ ⍺≡d:(⊃⍺⍺/0⊃⍵)⍵⍵ 1⊃⍵ d ⍺⍺(⍺ ⍵)(⍺ ⍵⍵ ⍵) }

f fk g fk h 23 ((f 23 )g(h 23 )) +/fk÷fk⍴ 12 23 34 45 56 67 78 45 12 f fk g fk h 23 (( 12 f 23 )g( 12 h 23 )) 12 34 56 78 90 >fk∨fk= 98 76 54 32 10 0 0 1 1 1

## Afterword

If it were decided to allow APL to acknowledge an isolated list of functions as a valid syntactic construct it would remain to be decided how it should be applied and how the individual members should interact.

The designers of J decided to go for hook and fork.

There is currently discussion that Dyalog might make the same decision.

It isn’t necessary to go for a single solution except as a default. The selection of hook and fork as default behaviour wouldn’t need to preclude the introduction of operators that apply the list in some other way. The co-operators described here hint at some of those other ways. Instead of building up a derived function by alternating with their operands, they could take the list as a single operand and apply its members appropriately.

## Appendix

Functions used to demonstrate calling sequences:

f←{⍺←⊢ ⋄ '(',⍺,'f',⍵,')'} g←{⍺←⊢ ⋄ '(',⍺,'g',⍵,')'} h←{⍺←⊢ ⋄ '(',⍺,'h',⍵,')'} j←{⍺←⊢ ⋄ '(',⍺,'j',⍵,')'} k←{⍺←⊢ ⋄ '(',⍺,'k',⍵,')'} l←{⍺←⊢ ⋄ '(',⍺,'l',⍵,')'}