List combiners in Klink

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\Family	And	Or	Map	Each
Non-op	and?	or?	copy-list
Eval	$and?	$or?	mapeval1	$sequence
Operate on donut	every?	some?	map	for-each
Neighbors	>? et al		list-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:

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