[stack] function/object ambiguity + quotation alternative

I've hinted at this recently, but never properly explained it. It may  
be entirely uninteresting or even an incorrect observation, so I'd  
appreciate a whack on the hand if I'm off track. I think, however,  
that it may be important in letting us further develop a firm  
theoretical basis for concatenative languages.

In a concatenative language, all terms denote functions. I don't think  
this is too contentious to say. For example, '42' denotes the function  
that pushes the value 42 onto a stack. '[foo bar]' is a function that  
pushes the quotation/list [foo bar] onto the stack. Et cetera.

This seem to be a unique property. I have never seen a non- 
concatenative language in which every term denoted a function.

John Backus invented the term "function-level programming", of which  
his language FP is the canonical example. In FP however, the term '42'  
represents an object. You use the combining form '~', aka "constant",  
to produce a function that returns the object 42 when passed any  
value, e.g. '~42'.

Assume application is written ":", composition is written ".", a list  
is written in angle brackets, and construction is written with square  
brackets. Given this, the semantics of 'dup' in FP are as follows:

    dup:X   ->  <X, X>
    dup.~X  ==  [~X, ~X]

The former gives the semantics of applying 'dup' to some object X. The  
latter states an equivalence between composing 'dup' with the constant  
function '~X' and construction over two functions that are both the  
constant function '~X'.

With concatenative languages, we always use the second form for  
expressing the semantics of some function, e.g. 'X dup == X X'. We do  
this because we have no syntax for application and no way of  
expressing objects. There's something strange here though. Because all  
terms denote functions, 'X' must be a function. However, 'X' cannot be  
any function; it must be a function that pushes a value (and always  
the same value) onto a stack.

I'm now wondering if this function/object ambiguity in concatenative  
languages is really a good thing. Take the Joy expression '[1 2 3]'.  
We can say that '[1 2 3]' is a function that pushes the value [1 2 3]  
onto a stack, but we also have to say that the term '1' within the  
term '[1 2 3]' itself denotes a function. This seems strange because,  
if you gets the first element of the list, you certainly can't use it  
as a function; it's a number.

This strangeness is more evident in the following example. The  
expression '[dup swap] head' yields 'dup', but 'dup != [dup swap]  
head'! This is because the left side of the equality is the *function*  
'dup', but the right side gets reduced to the *object* 'dup'. You  
might think this problem is due to Joy's "open" quotations, but you  
have the same problem in Factor. For example, 'sq != { sq } first'  
despite the fact that '{ sq } first' yields sq!

I believe I know how to solve this problem: Get rid of the function/ 
object ambiguity.

To do this, we drop the requirement that all terms denote functions.  
'42' will now denote the *number* 42. To push 42 onto the stack, we'll  
write '`42', i.e. the push function '`' applied to the object 42.

The presence of '`' allows us to get rid of quotation. Instead of '[+]  
map', we would write '`+ map'; the '`' function applied to the '+'  
function yields a new function that pushes the '+' function onto a  
stack. We'd also need to add parentheses for grouping; you'd write  
'`(foo bar)' instead of '[foo bar]'.

This allows us a solution to the problem with Factor's array literals  
shown above: Array literals would only be allowed to contain terms  
representing objects. For example, '`{ 42 `42 }' would be a function  
that pushes an array onto a stack where the first element of the array  
is the number 42 and the second element is a function that pushes 42  
onto a stack.

I would also suggest adding an additional array syntax that takes  
*functions* that evaluate to single objects. If 'x' is defined as '1 2  
drop', then we could write '{| x |}' to push an array of one element  
containing the number 1 onto the stack. Alternatively, because we now  
have parentheses for grouping, we could replace 'x' with its  
definition and write '{| ( 1 2 drop ) |}' instead.

In Joy, where creating multiple "copies" of the stack is cheap, you  
could use my parallel "banana" combinator to construct lists. For  
example, you could write the function '2 3 (|+ -|)' which would be  
equivalent to the function '`{5 -1}' (assuming we also adopted closed  
quotations for Joy and added '{ }' as a list literal syntax).

Since we have lost the object/function ambiguity, we can now express  
the semantics of our functions in terms of application. I propose the  
syntax '<object>:<function>' to indicate an application. Assuming our  
concatenative language is stack-based, the object will always be a  
stack.

I represent the stack as a null-terminated list (using angle brackets)  
which is necessary to show how the function in question handles the  
"rest of the stack". The right-most element of a list is the "top"  
element. '<>' denotes the null list.

Here are the semantics of six functions in terms of application:

    R:`42  ->  <R, 42>
    <R,X>:dup  ->  <R,<X,X>>
    <R,<X,Y>>:swap  ->  <R,<Y,X>>
    <R,F>:i  ->  R:F
    <R,<X,F>>:dip  ->  <R:F, X>
    R:clear  ->  <>

Alternatively, we can express our semantics in terms of equivalencies.  
This isn't as generally useful as the application form above (e.g. you  
can't express 'clear' in this form), but it is perhaps a bit easier to  
read:

    `42  ==  `42
    `X dup  ==  `X `X
    `X `Y swap  ==  `Y `X
    `F i  ==  F
    `X `F dip  ==  F `X

If you made it this far, thank you. Any thoughts would be appreciated.

- John