Re: [stack] function/object ambiguity + quotation alternative

On Feb 27, 2009, at 2:37 PM, Stevan Apter wrote:

> i appreciate your forebearance.  i may have a useful analogy from
> planet k.

Thanks, that does make sense. Maybe I can put it in those terms.

Take this expression:

    2 [dup] first

Here, '2' is a verb. So are '[dup]' and 'first'. Indeed, everything is  
a verb in a concatenative *program* (very careful emphasis on  
"program" there) because all terms denote functions.

The problem occurs when you *reduce* the program. Let's go step by step:

    2 [dup] first     (initial state)
    2 [dup] first     (after evaluating the function '2')
    2 [dup] first     (after evaluating the function '[dup]')
    2 dup             (after evaluating the function 'first')

The end of this evaluation is '2 dup'. The important thing here though  
is now '2' and 'dup' are nouns. You cannot further reduce '2 dup' to  
'2 2' even though the syntax makes it look like you should be able to.

It's this syntactic confusion I want to address. I want to be able to  
do reductions like I did above--that is, without keeping an explicit  
stack--while making it clear which things are verbs and which things  
are nouns.

To reiterate, nouns do not occur in the programs you write, but they  
*do* occur when reducing those programs.

One way to solve this problem is to use some symbol, perhaps a quote  
as zallambo suggested, to indicate which things are nouns. Using this  
technique, we can do our reduction again:

    2 [dup] first     (initial state)
    '2 [dup] first    (after evaluating the function '2')
    '2 '[dup] first   (after evaluating the function '[dup]')
    '2 'dup           (after evaluating the function 'first')

In this case, we end up with "'2 'dup". It's clear from looking at the  
expression that we're done reducing the program. It avoids the  
confusion of looking at '2 dup' and not being sure if we're supposed  
to do reduce it to '2 2' or not.

(Hopefully the issue I want to address is clear now. It may get fuzzy  
from this point on...)

Unfortunately, I take issue with zallambo's proposal. My problem with  
it--if I understand it correctly--is that it creates two languages,  
one for writing programs and another to use when reducing them.  
Perhaps I'm being overly pedantic, but he said 'foo denotes an  
*object*, and objects are not part of the term language when writing a  
program. "All terms denote functions."

My proposal differs from zallambo's in that I prefer to add a "push"  
functional form to the language itself so that you do not have a two  
syntaxes. Instead, you use the same syntax for writing a program and  
for reducing a program.

The "push" form would be written with a back-tick and would indicate a  
function that pushes itself onto the stack; essentially, it self- 
evaluates like a quoted expression does in Scheme. Also as in Scheme,  
it would not be necessary to quote things which always evaluate to  
themselves (like numbers); only things that don't (namely functions).

To make this model compatible with open quotations, quotation would  
apply "push" to every *noun* within it to lift them to verbs. For  
example, the following would be equivalent:

    `foo `bar [] cons cons
    [foo bar]

Here's the same reduction again with my proposal:

    2 [dup] first     (initial state)
    2 [dup] first     (after evaluating the function '2')
    2 [dup] first     (after evaluating the function '[dup]')
    2 `dup            (after evaluating the function 'first')

(Remember that quotation applies "push" to everything with it, so  
'`dup' really is the first element of '[dup]'.)

This syntax has the advantages of zallambo's, but it has an important  
additional benefit; each step of the reduction is itself a valid  
program. To repeat, the syntax we use for the reduction can also be  
used for writing programs.

- John