[stack] Syntax for combinators

From time to time I have considered various alternative notations for
concatenative languages. In particular the syntax for combinators would seem
to allow some variants the might be explored. In this note I only present
some alternatives, I do not argue for or against one or the other.

When writing Joy programs with combinators, in about 95% of cases I seem to
push the quotation parameters just before the combinator. Using the ifte
combinator, a piece of program would look like this:

[if-part]  [then-part]  [else-part]  ifte

The ifte combinator  immediately removes the three quotations, and all other
combinators do the same. Could one have a different notation? Perhaps to
avoid the needless pushes, perhaps for better intelligibility, perhaps for
other reasons. Starting at one extreme of the possibilities we have several
choices:

(1)  Write instead something like this mixfix notation

IF  if-part  THEN  then-part  ELSE  elsepart  ENDIF

in analogy with some procedural languages. Make IF, THEN, ELSE, ENDIF
reserved words, perhaps. Do something analogous for other combinators, but
restrict the palette of combinators to a fixed useful minimum. This is what
procedural languages tend to do with statements ­ sequencing, conditionals,
various loops. Do not allow the user to define their own. (Something needs
to be said here about procedures taking other procedures as parameters ­ but
I¹ll skip that for the moment.) The Pascals and the Cs do this, and so does
the FP language by Backus (if memory serves right). I don¹t know what a
suitable minimal set for Joy or other concatenative languages would be.

(2) Allow user defined combinators, but (probably) without the mixfix
notation. Instead do functional notation:

ifte(ifpart, then-part, else-part)

Definitions for user declared combinators now look like this:

DEFINE  foo(f1, f2, ..)  ==  ... .

The extension to the parser is trivial, and checking for agreement of formal
and actual parameters in calls is not difficult either.

Both (1) and (2) introduce more structure into programs, and allow the
language processor to check that the required structure is not violated.
In each case the combinators take stack functions (such as dup * ) as
parameters and the result behaves just like a simple stack function. Calls
now look like this:

IF ... THEN dup * ELSE  ...
ifte(...,  dup *, ...)
foo(..., dup *, ..., ...)

In other words the parameters have to be literally the verbatim programs
to be executed by the combinator, the program dup * in this case. Note also
that as described so far there is no need for quotation brackets in the
comma-separated list of actual parameters.

(3) But in languages like the lisps there is another possibility. In most
cases
the combinators are given their function parameters literally, but at least
for the apply combinator actual function parameter is an expression which
has to be evaluated to give the function to be applied. Suppose we allow
that for the concatenative language sketched so far. Assume we have defined
a list of quotations, with the squaring quotation in third position:

DEFINE quotelist ==  [ [..]  [..] [dup *] [..] ....]

Now we could write things like these:

ifte(..., quotelist third, ...)

which will be equivalent to

ifte(..., [dup *], ...)

but now with quotation brackets. So there is more expressive power again,
but still the parameters are in predetermined positions which can be
enforced
by the language processor.

(4) Allow the quotation parameters to be constructed just before they are
used by the
combinator:

ifte(..., quotelist third dup concat, ...)

which is equivalent to

ifte(..., [dup * dup *], ...)

(5) Drop the restriction of predetermined positions of the parameters. Allow
them to come from anywhere on the stack, but put them in the right position
just before the combinator uses them. Examples in Joy:

...  rollup quotelist third swap ifte
...  rollup quotelist third dup concat swap ifte

Just as in (4), even the concat example builds up a quotation from existing
ones.

(6) Allow quotation parameters to be built by taking other quotations apart:
Examples:

ifte( ..., quotelist third rest cons, ...)
... rollup 3 quotelist third rest cons swap ifte

which are equivalent to

ifte( ..., [3 *], ...)
... rollup [3 *] swap ifte

As you the steps from 3 to 5 and 6 show, the ³spectrum² of possible
notations is not quite linear, but never mind.

We have started with a very inflexible version of combinators and allowed
more and more freedom. There may be even more restrictive and more
flexible notations than the two extremes outlined here.

Question: which level is best? Safety bought by inflexible rigidity, or
flexibility at the cost of obfuscation? I¹ll leave it at that. Pick your
level
and tell us about it.

 - Manfred













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