## Regularities in list combiners in Klink

Yesterday I was writing list combiners for Klink, my interpreter for a Scheme-derived languages called Kernel. I couldn't help noticing many regularities between them. Not just obvious regularities, such as and? / $and? / or? /$or?, but deeper ones that pervaded the set of list-oriented combiners. They seemed to all fall into one of a small set of families, and one of a small set of argument arrangements.

Here's a table of existing (or planned shortly) combiners that followed this pattern:

Args\FamilyAndOrMapEach
Non-opand?or?copy-list
Eval$and?$or?mapeval1$sequence Operate on donutevery?some?mapfor-each Neighbors>? et allist-neighbors The families are as follows: and Value must be boolean, stop early on #f. or Value must be boolean, stop early on #t. map Collect values, no specified order. each Evaluate for side-effects, in order. And the argument arrangements are: Non-op Non-operative on given values Eval Evaluate the list element as a form Rectangular Operate on transposed rectangular args • Takes 2 length-counts • Unsafe itself but used as a worker by safe combiners. • Name format: counted-NAME Unary Operate on args to a unary operative • Takes 1 length count, the other is always 1. • Specializes "rectangular". • Name format: NAME1 Donut Operate on possibly infinite lists ("donuts") • Called thru apply-counted-proc Neighbors Operate on list-neighbors ## Some tempting extensions: argument arrangements I also envision other argument arrangements that aren't part of the Kernel spec, but which I've found useful over the years: ### Ragged This is the indeterminate-length variant of "Donut" and "Rectangular". It operates on "ragged" transposed args that need not all be the same length, and may in fact be streams. It produces a stream. Ie, each iteration it returns: (cons value ($lazy (start the next iteration)))


It terminates when any input stream or list runs out of arguments. It returns:

(\$lazy (termination-combiner streams))


where termination-combiner' is a parameter. That is done to reveal the final state, which the caller may be interested in.

It is allowed to never terminate, since a caller need not evaluate the entire stream.

Combiners of this type would have the same name as donut combiners plus "-ragged", eg "map-ragged".

### Indexed

Operate on transposed args plus an "index" argument. This is just providing an argument that already exists internally. It doesn't constrain the order of operations.

### Blackboard - probably not

Operate on transposed args plus a "blackboard" argument. Intended for providing and collecting results that don't fit neatly as mapped returns. It maintains the overall control structure of visiting each element of a list, but can collect results in more varied ways.

In its favor as an argument arrangement, most of the families combine with it to provide useful behavior: Stop on false, stop on true, or keep going for side effects.

Against it, it's not clear that it can co-operate coherently with the map' family, which has no specified order of evaluation.

It also seems to require another argument arrangement underneath it.

And finally, it's not clear that it is sufficiently distinct from reduce' to be worth having. And blackboard is an argument arrangement, while reduce is proposed as a family. That suggests that something is wrong with one or both.

So probably no to "blackboard". Some variant of "reduce" will likely do it instead.

## Some tempting extensions: Families

### Reduce

In reduce, the value cascades thru each element. Though superficially related to the list-neighbors argument arrangement, it's not the same thing. It considers the elements one by one, not two by two. Its binary combiner gets two arguments only because one is an accumulator.

In its favor as a family, it already comes in counted and donut versions.

Standing against it is that its counted form is abnormally a non-op arrangement instead of a unary or rectangular arrangement. But non-op can be considered a specialization of unary' with identity' as the operative.

And it's not clear that an eval' arrangement could ever make sense. But again, the eval' arrangement is a specialization of unary, with eval' as the operative and the single argument as the form.

So I'll wait and see whether reduce can fit in or not. But it looks promising.

## Footnotes:

1 mapeval is internal, used by the C code for the `eval' operation. However, I see no problem exposing it and it might be useful.