function/object ambiguity + quotation alternative

[John Nowak]

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

[stevan apter]

> 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'.

i've always assumed that [dup swap] head is the function dup.  e.g. in XY:


  2 [dup swap] first i
2 2

that is, [dup swap] first leaves the function dup on the stack.
then i moves the top item of the stack to the head of the queue.

what am i missing?


----- Original Message -----
From: "John Nowak" <john@...>
To: "concatenative" <concatenative@...>
Sent: Thursday, February 26, 2009 9:34 AM
Subject: [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
>

[John Nowak]

On Feb 26, 2009, at 10:21 AM, Stevan Apter wrote:

>> 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'.
>
> i've always assumed that [dup swap] head is the function dup.  e.g.  
> in XY:
>
>  2 [dup swap] first i
> 2 2
>
> that is, [dup swap] first leaves the function dup on the stack.
> then i moves the top item of the stack to the head of the queue.
>
> what am i missing?

I don't know XY, but XY does not work the same way as Joy and Factor  
apparently.

Factor:

    >> 5 { dup } first call
    Generic word call does not define a method for the word class.
    Dispatching on object: dup

Joy:

    >> 5 [dup] first i
    run time error: quotation as top parameter needed for i

This is the problem I'm referring to.

What XY does seems even worse though! Here's why:

    1. [dup] i == [dup] first i  (given, as per your example)
    2. [dup] == [dup] first      (removing shared 'i' suffix)
    3. id == first               (removing share '[dup]' prefix)

Certainly first cannot be the identity function! Is the algebra of XY  
broken? Am I missing something?

- John

[John Nowak]

On Feb 26, 2009, at 10:47 AM, John Nowak wrote:

> This is the problem I'm referring to.

Maybe this is an even simpler way of stating the problem in Joy and  
Factor, where '->' means "evaluates to":

    1. [X] first    ->  X    (given)
    2. [dup] first  ->  dup  (valid, following from 1)
    3. [dup] first  !=  dup  (given, in contradiction to 2)

The problem is that the 'dup' on the right side of 2 is a function  
reified as an object, but the 'dup' on the right side of 3 is a  
function. 'dup' "the function" is not the same as 'dup' "the function  
object", yet they are represented by the same term. This causes  
problems with algebraic manipulation of programs as plainly seen  
above. My solution is to get rid of this ambiguity.

- John

[stevan apter]

----- Original Message -----
From: "John Nowak" <john@...>
To: <concatenative@...>
Sent: Thursday, February 26, 2009 10:47 AM
Subject: Re: [stack] function/object ambiguity + quotation alternative

>
> On Feb 26, 2009, at 10:21 AM, Stevan Apter wrote:
>
>>> 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'.
>>
>> i've always assumed that [dup swap] head is the function dup.  e.g.  
>> in XY:
>>
>>  2 [dup swap] first i
>> 2 2
>>
>> that is, [dup swap] first leaves the function dup on the stack.
>> then i moves the top item of the stack to the head of the queue.
>>
>> what am i missing?
>
> I don't know XY, but XY does not work the same way as Joy and Factor  
> apparently.
>
> Factor:
>
>    >> 5 { dup } first call
>    Generic word call does not define a method for the word class.
>    Dispatching on object: dup
>
> Joy:
>
>    >> 5 [dup] first i
>    run time error: quotation as top parameter needed for i
>
> This is the problem I'm referring to.
>
> What XY does seems even worse though! Here's why:
>
>    1. [dup] i == [dup] first i  (given, as per your example)

>    2. [dup] == [dup] first      (removing shared 'i' suffix)

no.  dup = [dup] first.

>    3. id == first               (removing share '[dup]' prefix)
>
> Certainly first cannot be the identity function! Is the algebra of XY  
> broken? Am I missing something?
>
> - John
>

[William Tanksley, Jr]

Stevan Apter wrote:
> From: "John Nowak" <john@...>
> > What XY does seems even worse though! Here's why:
> >    1. [dup] i == [dup] first i  (given, as per your example)
> >    2. [dup] == [dup] first      (removing shared 'i' suffix)
>>    3. id == first               (removing share '[dup]' prefix)

> no.  dup = [dup] first.

You're right, but he's also right -- you should always be able to remove
identical suffixes from both sides of the equation, and in this case you
can't do that.

-Wm

[John Nowak]

On Feb 26, 2009, at 12:22 PM, Stevan Apter wrote:

>>   2. [dup] == [dup] first      (removing shared 'i' suffix)
>
> no.  dup = [dup] first.

You're missing the point. I know that 'dup = [dup] first', but I can  
prove '[dup] == [dup] first'!

I'll start with your example (minus the swap); after each step, I'll  
indicate how I came upon the given equality:

1. 2 [dup] first i == 2 2        (given)
2. [F] i == F                    (given)
3  2 dup == 2 2                  (given)
4. 2 [dup] i == 2 2              (2+3: substituted '[dup] i' for 'dup')
5. 2 [dup] i == 2 [dup] first i  (1+4: both equal '2 2')
6. i == first i                  (5: removed shared '2 [dup]' prefix)
7. id == first                   (6: removed 'i' suffix)

To repeat, I know this is a bogus conclusion; that's my point. The  
problem arises from the fact that '[dup] i' functions identically to  
'[dup] first i' in XY; or, at least that's my understanding.

If my little derivation is wrong, please correct me. If not, I believe  
this to be a problem in XY's semantics.

- John

[John Nowak]

On Feb 26, 2009, at 12:45 PM, John Nowak wrote:

>
> On Feb 26, 2009, at 12:22 PM, Stevan Apter wrote:
>
>>>  2. [dup] == [dup] first      (removing shared 'i' suffix)
>>
>> no.  dup = [dup] first.
>
> You're missing the point. I know that 'dup = [dup] first', but I can
> prove '[dup] == [dup] first'!

To be more precise, I know '[dup] first' evaluates to the function  
object 'dup'. I assume this is what you mean.

That said, the function 'dup' does *not* equal the function '[dup]  
first'. Obviously '2 dup' yields a different answer than '2 [dup]  
first'. This is the initial problem I brought up and it may affect XY;  
I know it affects Joy and Factor. The ability to prove '[dup] == [dup]  
first' is an additional issue that is XY-specific.

- John

[stevan apter]

----- Original Message -----
From: "John Nowak" <john@...>
To: <concatenative@...>
Sent: Thursday, February 26, 2009 12:45 PM
Subject: Re: [stack] function/object ambiguity + quotation alternative

>
> On Feb 26, 2009, at 12:22 PM, Stevan Apter wrote:
>
>>>   2. [dup] == [dup] first      (removing shared 'i' suffix)
>>
>> no.  dup = [dup] first.
>
> You're missing the point. I know that 'dup = [dup] first', but I can  
> prove '[dup] == [dup] first'!
>
> I'll start with your example (minus the swap); after each step, I'll  
> indicate how I came upon the given equality:
>
> 1. 2 [dup] first i == 2 2        (given)
> 2. [F] i == F                    (given)
> 3  2 dup == 2 2                  (given)
> 4. 2 [dup] i == 2 2              (2+3: substituted '[dup] i' for 'dup')
> 5. 2 [dup] i == 2 [dup] first i  (1+4: both equal '2 2')
> 6. i == first i                  (5: removed shared '2 [dup]' prefix)
> 7. id == first                   (6: removed 'i' suffix)
>
> To repeat, I know this is a bogus conclusion; that's my point. The  
> problem arises from the fact that '[dup] i' functions identically to  
> '[dup] first i' in XY; or, at least that's my understanding.
>
> If my little derivation is wrong, please correct me. If not, I believe  
> this to be a problem in XY's semantics.

i see the problem.  in XY, [X]first != [X]i.

i moves the top of the stack to the head of the queue, whence it executes,
immediately.

first replaces the top of the stack with the first element of the top of
the stack.  

to make things just a little more confusing, there is no stack underflow
in XY, so e.g.

    [dup] first i = [{ a \ a \ a }]

and:
 
    10 20 [dup] [i] infra = 10 20 [[{ a \ a \ a }]]

which is the unit list of dup's "object code".  repeatedly applying i
to this has no effect.

but:

    [dup] first i 10 swap i = 10 10

but this is an implementation detail.  an underflow exception could be
thrown instead.

>
> - John
>

[stevan apter]

----- Original Message -----
From: "William Tanksley" <wtanksleyjr@...>
To: <concatenative@...>
Sent: Thursday, February 26, 2009 12:44 PM
Subject: Re: [stack] function/object ambiguity + quotation alternative

> Stevan Apter wrote:
>> From: "John Nowak" <john@...>
>> > What XY does seems even worse though! Here's why:
>> >    1. [dup] i == [dup] first i  (given, as per your example)
>> >    2. [dup] == [dup] first      (removing shared 'i' suffix)
>>>    3. id == first               (removing share '[dup]' prefix)
>
>> no.  dup = [dup] first.
>
> You're right, but he's also right -- you should always be able to remove
> identical suffixes from both sides of the equation, and in this case you
> can't do that.

1 is true, 2 is false.

first != i != id

i don't see the problem.


>
> -Wm
>
>
>

[stevan apter]

if you search way back in the archives, you'll see that this problem
surfaced fairly early on.  billy and i batted around the idea that the
evaluator could be made "voracious":

    2 [dup] first -> 2 2

i.e. the evaluator would not abide naked functions on the stack; it
would apply repeatedly until that was not the case.

----- Original Message -----
From: "John Nowak" <john@...>
To: <concatenative@...>
Sent: Thursday, February 26, 2009 12:53 PM
Subject: Re: [stack] function/object ambiguity + quotation alternative

>
> On Feb 26, 2009, at 12:45 PM, John Nowak wrote:
>
>>
>> On Feb 26, 2009, at 12:22 PM, Stevan Apter wrote:
>>
>>>>  2. [dup] == [dup] first      (removing shared 'i' suffix)
>>>
>>> no.  dup = [dup] first.
>>
>> You're missing the point. I know that 'dup = [dup] first', but I can
>> prove '[dup] == [dup] first'!
>
> To be more precise, I know '[dup] first' evaluates to the function  
> object 'dup'. I assume this is what you mean.
>
> That said, the function 'dup' does *not* equal the function '[dup]  
> first'. Obviously '2 dup' yields a different answer than '2 [dup]  
> first'. This is the initial problem I brought up and it may affect XY;  
> I know it affects Joy and Factor. The ability to prove '[dup] == [dup]  
> first' is an additional issue that is XY-specific.
>
> - John
>

[John Nowak]

On Feb 26, 2009, at 1:06 PM, Stevan Apter wrote:

> i see the problem.  in XY, [X]first != [X]i.
> i moves the top of the stack to the head of the queue, whence it  
> executes,
> immediately.
> first replaces the top of the stack with the first element of the  
> top of
> the stack.

Your assessment that the problem is '[X]first != [X]i' is incorrect.

Currently in XY, this is true:

    [dup] first i  ==  [dup] i

The problem is that this means I can prove that 'first' is the  
identity function.

If we change XY such that '[dup] first == [dup] i', I can take this:

    [dup] first i  ==  [dup] i

And substitute '[dup] i' for '[dup] first':

    [dup] i i  ==  [dup] i

And hence I can prove 'i i == i', and then from there prove that 'i'  
is the identity function.

The only way to solve this problem is to have '[dup] first i' cause an  
error. 'i' must be correctly restricted to performing "dequotation" as  
in Joy, Factor, Cat, etc.

- John

[Christopher Diggins]

>> the evaluator would not abide naked functions on the stack; it would apply repeatedly until that was not the case.

Then you have a first order language. I don't really see what that
buys you. Why not allow functions on the stack? It seems to me that
higher-order languages are only a positive thing. Joy and its ilk are
only interesting to me because they allow functions on the stack.

[John Nowak]

On Feb 26, 2009, at 2:57 PM, Christopher Diggins wrote:

>>> the evaluator would not abide naked functions on the stack; it  
>>> would apply repeatedly until that was not the case.
>
> Then you have a first order language. I don't really see what that
> buys you. Why not allow functions on the stack?

I think you're misunderstanding what Stevan was saying. Stevan is not  
suggesting anything that would eliminate quotations or make a language  
first order.

Joy and XY have "open" quotations. You can modify them as if they were  
lists. This causes two problems.

The first is that the language becomes non-extensional. For example,  
say you know that 'a b == c d'. In Joy and XY, it does not follow that  
'[a b] == [c d]' as it does in Cat.

The second problem is that, because you can take "things" out of a  
quotation, you end up with weird problems. Factor has this problem too  
with its array literals; or at least I'm pretty sure it does.

Take the program '5 [dup] first' for example. The result of this is '5  
dup'. However, the 'dup' here is *not* a function the same way 'first'  
was; it's a function object. Accordingly, the result of evaluation '5  
[dup]' is a stack with two elements; the first is the value 5 and the  
second is the value 'dup'.

What Stevan was suggesting was to evaluate "unquoted function objects"  
like 'dup' in the example above. In this system '5 [dup] first' would  
reduce to '5 dup', but then further reduce to '5 5' without the need  
to explicitly re-quote 'dup' and call 'i'.

> It seems to me that higher-order languages are only a positive thing.

Certain forms of reasoning are a lot easier without higher order  
functions. It's a tradeoff.

- John

[John Nowak]

On Feb 26, 2009, at 3:08 PM, John Nowak wrote:

> Accordingly, the result of evaluation '5 [dup]' is a stack with two  
> elements; the first is the value 5 and the  second is the value 'dup'.

Sorry, that should read as follows:

"Accordingly, the result of evaluation '5 [dup] first' is a stack with  
two elements; the first is the value 5 and the second is the value dup."

- John

[stevan apter]

i don't disagree.  so in cat, what's on the stack after evaluating [dup]first?

----- Original Message -----
From: "Christopher Diggins" <cdiggins@...>
To: <concatenative@...>
Sent: Thursday, February 26, 2009 2:57 PM
Subject: Re: [stack] function/object ambiguity + quotation alternative


>>> the evaluator would not abide naked functions on the stack; it would apply repeatedly until that was not the case.
>
> Then you have a first order language. I don't really see what that
> buys you. Why not allow functions on the stack? It seems to me that
> higher-order languages are only a positive thing. Joy and its ilk are
> only interesting to me because they allow functions on the stack.
>

[John Nowak]

On Feb 26, 2009, at 3:11 PM, Stevan Apter wrote:

>>> the evaluator would not abide naked functions on the stack; it  
>>> would apply repeatedly until that was not the case.
>>
>> Then you have a first order language. I don't really see what that
>>
>> buys you. Why not allow functions on the stack? It seems to me that
>> higher-order languages are only a positive thing. Joy and its ilk are
>> only interesting to me because they allow functions on the stack.
>
> i don't disagree.

You should disagree unless you're suggesting that '5 [dup]' evaluate  
to '5 5'. Are you? I wasn't under the impression that you meant to  
make that point. If you weren't suggesting that, the language would  
remain higher-order.

> so in cat, what's on the stack after evaluating [dup]first?

This is not possible in Cat because quotations are not manipulatable  
as such. This is necessary to preserve extensionality (e.g. '[1 2  
drop] == [1]') and to allow the language to be typed.

- John

[stevan apter]

well, it's worth pointing out that

    5 [dup] first i
    5 [dup] i

both evaluate to 5 5 in XY because 'i' doesn't quite mean
disquotation.  it means "take the top of the stack and
prepend it to the head of the queue."  where Q is the queue
and S is the stack, the k code which implements this is
roughly:

    Q:(last S),Q
    S:-1_S

x,y is concatenation, x_y is drop from the head or tail.

suppose last S = dup, then Q = dup,Q.  suppose last S = [dup],
then Q = [dup],Q.  but Q is the same in both cases.  concatenation
of a unit list is the same as the concatenation of atom.

if i can remember what i was thinking at the time, it was
something like this:  i want to be able to put naked functions
on the stack.  but i also want to be able to evaluate them
once they're there.  so reinterpret 'i' to mean 'move to the
queue'.



----- Original Message -----
From: "John Nowak" <john@...>
To: <concatenative@...>
Sent: Thursday, February 26, 2009 3:08 PM
Subject: Re: [stack] function/object ambiguity + quotation alternative

>
> On Feb 26, 2009, at 2:57 PM, Christopher Diggins wrote:
>
>>>> the evaluator would not abide naked functions on the stack; it  
>>>> would apply repeatedly until that was not the case.
>>
>> Then you have a first order language. I don't really see what that
>> buys you. Why not allow functions on the stack?
>
> I think you're misunderstanding what Stevan was saying. Stevan is not  
> suggesting anything that would eliminate quotations or make a language  
> first order.
>
> Joy and XY have "open" quotations. You can modify them as if they were  
> lists. This causes two problems.
>
> The first is that the language becomes non-extensional. For example,  
> say you know that 'a b == c d'. In Joy and XY, it does not follow that  
> '[a b] == [c d]' as it does in Cat.
>
> The second problem is that, because you can take "things" out of a  
> quotation, you end up with weird problems. Factor has this problem too  
> with its array literals; or at least I'm pretty sure it does.
>
> Take the program '5 [dup] first' for example. The result of this is '5  
> dup'. However, the 'dup' here is *not* a function the same way 'first'  
> was; it's a function object. Accordingly, the result of evaluation '5  
> [dup]' is a stack with two elements; the first is the value 5 and the  
> second is the value 'dup'.
>
> What Stevan was suggesting was to evaluate "unquoted function objects"  
> like 'dup' in the example above. In this system '5 [dup] first' would  
> reduce to '5 dup', but then further reduce to '5 5' without the need  
> to explicitly re-quote 'dup' and call 'i'.
>
>> It seems to me that higher-order languages are only a positive thing.
>
> Certain forms of reasoning are a lot easier without higher order  
> functions. It's a tradeoff.
>
> - John
>

[stevan apter]

i meant that i don't disagree that functions on the stack are a
good thing.


----- Original Message -----
From: "John Nowak" <john@...>
To: <concatenative@...>
Sent: Thursday, February 26, 2009 3:15 PM
Subject: Re: [stack] function/object ambiguity + quotation alternative

>
> On Feb 26, 2009, at 3:11 PM, Stevan Apter wrote:
>
>>>> the evaluator would not abide naked functions on the stack; it  
>>>> would apply repeatedly until that was not the case.
>>>
>>> Then you have a first order language. I don't really see what that
>>>
>>> buys you. Why not allow functions on the stack? It seems to me that
>>> higher-order languages are only a positive thing. Joy and its ilk are
>>> only interesting to me because they allow functions on the stack.
>>
>> i don't disagree.
>
> You should disagree unless you're suggesting that '5 [dup]' evaluate  
> to '5 5'. Are you? I wasn't under the impression that you meant to  
> make that point. If you weren't suggesting that, the language would  
> remain higher-order.
>
>> so in cat, what's on the stack after evaluating [dup]first?
>
> This is not possible in Cat because quotations are not manipulatable  
> as such. This is necessary to preserve extensionality (e.g. '[1 2  
> drop] == [1]') and to allow the language to be typed.
>
> - John
>

[Don Groves]

On Feb 26, 2009, at 11:57 AM, Christopher Diggins wrote:

>>> the evaluator would not abide naked functions on the stack; it  
>>> would apply repeatedly until that was not the case.
>
> Then you have a first order language. I don't really see what that
> buys you. Why not allow functions on the stack? It seems to me that
> higher-order languages are only a positive thing. Joy and its ilk are
> only interesting to me because they allow functions on the stack.

I'll second that.
--
don