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

> 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" <[email protected]>
To: "concatenative" <[email protected]>
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
>