[stack] rewriting + second order vs. higher order expressivity

I've recently been considering a concatenative language variant  
without first-class functions. In such a language, you'd have a clear  
hierarchy with objects at the bottom, functions that manipulate  
objects above that, and finally functionals (aka combining forms) that  
manipulate functions at the top. For the sake of clarity, we'll call  
this language C2 (as it is a second order concatenative language).

In order to get to my point, let me very briefly explain C2. In C2,  
functions are written solely in terms of the composition of other  
functions. For example:

    a = b c(d, e f) g

Here, we're defining some function 'a' that is the composition of  
functions 'b', 'c(d, e, f)', and 'g'. Note that 'c' is a combining  
form which takes the functions 'd', 'e', and 'f' as arguments and  
yields a new function as a result.

Functionals, however, are not written solely in terms of composition.  
Such a thing is impossible because functions are not first class  
objects. Instead, we express functionals using rewrite rules. For  
example, here is the definition for 'bi@' (uppercase letters are used  
for function variables):

    bi@($F) = dip($F) $F

Here's an example of how the rewriting works:

      2 4 bi@(8 *)
    = 2 4 dip(8 *) 8 *
    = 2 8 * 4 8 *
    = 16 4 8 *
    = 16 32

It is very important to note that, in C2, variables can only be used  
in definitions for functionals and that only function variables are  
allowed (i.e. you can't give a name to an object). For example, this  
is not legal in C2 (lowercase letters are used for object variables):

    $a $b hypot = $a sqr $b sqr + sqrt

The reason this is illegal in C2 is that '$a' and '$b' are objects,  
not functions. If this were legal, functions would not be defined  
solely in terms of composition of existing functions.

This restriction (a lack of object variables) leads to some  
expressivity problems. Say we want to write some function 'foo' that  
takes four arguments and multiplies the bottom three by the first. In  
other words, '1 2 3 4 foo = 4 8 12'. In a language with higher order  
functions, we might write 'foo' as such (where 'papply' is partial  
application):

    foo = [*] papply tri@

In C2, however, this is obviously not an option as we don't have first  
class functions or 'papply'. Hence, we'd need to write something like  
this, which is much uglier and opaque than the higher order version:

    foo = tuck 2dip(tuck) tri@(*)

One way to solve this problem is to introduce the language C2'. C2' is  
the same as C2 with the exception that functions and functionals can  
use object variables. These variables can only appear at the "base"  
level of a definition. For example, this is legal:

    $a $b swap = $b $a

But this is not (since $a is "lifted" into a functional):

    $a map-with($F) = map($a $F)

The reason for this restriction on C2' is that it means we can, using  
'dip' 'dup' 'drop' and 'swap', translate any C2' program into a C2  
program. In other words, C2' is essentially just a sort of syntactic  
sugar.

Using C2', we can now write 'foo' more easily (if still not quite as  
nicely as the higher order version):

    $a $b $c $d foo = $a $d * $b $d * $c $d *

Unfortunately, C2' also has expressivity problems. Let's return to the  
'map-with' example above. There's no way to write this functional in  
C2' unless the function given to 'map' is allowed to access the entire  
stack (as opposed to be restricted to an arity of 1 -> 1). If we  
assume the function can access the entire stack, we can write 'map- 
with' as such:

    map-with($F) = swap map(over $F)

What this does is call 'map' with some value under the list that gets  
copied above the value pushed onto the list each time '$F' is called.  
This works, but it's rather ugly compared to the higher order version:

    map-with = papply map

That, however, it only half of the problem. The other half is that we  
need an n-ary map. N-ary combinators are more difficult to explain and  
arguably more prone to error. They also have rather ugly rewriting  
rules. For example, the best rule we can come up with for an n-ary  
'map-with' in C2' is this:

    {$x0, $x1, ... $xN} $a map-with($F) ->
       null $a $x0 over $F cons $x1 over $F cons ... $xN over $F cons

It is necessary to expand everything like this because $F is allowed  
to access the entire stack. This is much uglier than how 'map-with'  
works if '$F' is restricted to an arity of 1 -> 1 and we lift '$a'  
directly:

    {$x0, $x1, ... $xN} $a map-with($F) ->
       {$x0 $a $F, $x1 $a $F, ... $xN $a $F}

The difference between the two is not merely cosmetic. In the second  
version, it is easy to reduce each list element separately and in any  
order you please. In the first version, each resulting list element  
depends on the call to 'over', and hence you're stuck doing everything  
left to right.

The way to solve this problem is to introduce the final language, C2R  
(C2 with unrestricted rewrite rules). In C2R, it is legal to "lift"  
objects into functionals. This essentially gives us back a way of  
doing partial application without needing first-class functions. For  
example, in C2R, we can write 'map-with' as such:

    $a map-with($F) = map($a $F)

This version is as clear as can be and permits the second version of  
the rewriting semantics given above.

Alright, so we have three languages. C2 is nice in that the right side  
of function definitions only consists of compositions. The benefit of  
C2' is that it makes writing certain functions (primarily mathematical  
formulas) easier while still being translatable with C2.

C2R, however, is not translatable to C2. The addition of unrestricted  
rewrite rules objectively increases the expressiveness of the  
language. This illustrates a big difference between the C2 languages  
and their higher order cousins: In a higher order concatenative  
language, variables can always be translated away, even if the lifting  
of objects into functions is permitted.

For 5th, it seems that C2R is the way to go. However, I have some  
serious reservations. In particular, I'm not sure if C2R is even a  
concatenative language, as there's no way to get rid of the variables  
and hence you can't deal solely with function composition. In fact,  
the introduction of unrestricted rewriting essentially gives you let  
expressions (although I'm not sure if I'd allow overlapping scopes).

I'm not really sure what I'm asking here. Perhaps I'm just looking for  
a gut response to the C2R proposal. If anyone has any thoughts, I'd  
very much appreciate them. This is the last "big decision" for 5th  
before I can release something.

- John