[stack] Combining Combinators

Years ago I sometimes wondered whether there could be
any higher order combinators. Just as ordinary combinators
take a (quoted program to compute a) function as argument
from the stack, so a second order combinator would take
a (quoted program to compute a) combinator as argument
from the stack. I never found anything that is distinctly
second order ­ anything I found also worked first order.

Recently I approached the topic again, this time from a different
angle, restricting myself just to existing unary combinators,
those that take just one quotation as argument.

Let C and D be any from i, dip, nullary, unary, map, step, infra
and filter. C and D could be the same. Now look at all
combinations of the form

[C] D

So the D combinator is to take as its parameter the quotation
[C] from the stack, and below that whatever else is needed.

First, to get the feel for it all, let [C] be the simplest: [i], and
let D range over the list given above.

(1) D = i: (Boring!)
2 3 [+] [i] i  => 5

(2) D = dip:
2 3 [+] 999 [i] dip => 5 999

(3) D = nullary:
2 3 [+] [i] nullary => 2 3 [+] 5

(4) D = unary:
2 3 [+] [i] unary => 2 3 5

Comment: 2 3 [+] nullary => 2 3 5,
So we conclude: [i] unary == nullary

(5) D = map. So below the [i] quotation, a list is expected.
and it will have to be a list of quotations for i to execute.
2 3 [[+][*][>][dup *]] [i] map => 2 3 [5 6 false 9]

(6) D = step
Recall that step expects a list below its quotation parameter,
it sequentially puts the members of that list onto the stack
and the executes the quotation for each of them. So if the
quotation is [i], the list will have to be a list of quotations.
2 3 [[+][dup *]] [i] step  => 25
So [i] step behaves as if it first concatenates the list of quotations
and then executes it: 2 3 [+ dup *] => 25

(7) D = infra
Recall that infra expects a list below its quotation parameter,
It then treats that list as the stack, and replaces that list by
the result stack.
[[dup *] 3 4 5] [i] infra => [9 4 5]

(8) D = filter
5 [[3 <][10 <][4 <][20 <]] [i] filter => 5 [[10 <][20 <]]

That is quite a collection already, all giving a few surprising
results. These should really be in the toolbox of any
concatenative programmer ­ or perhaps just for the Joy
programmer. But this collection is only the start, because
[C] could be any of the list of 8 combinators. In total
there  are 8*8 = 64 combinations to be examined. I have
a few more, but I am far from having a systematic collection.
I shall report on my progress soon.

  - Manfred 


[Non-text portions of this message have been removed]