are concatenative languages applicative?

[John Nowak]

Apologies for starting a new thread of sorts, but the "Object Cat"  
thread already had run through three or four different topics, and it  
seems like a good idea to discuss this in such a way that it'll be  
archived properly. I'd really like an answer here.

First off, let me say that I'm not particularly interested in if Joy's  
'i' is an 'eval'. This does, as Chris pointed out, seem to get us  
bogged down in implementation details. As far as I can tell, 'eval' is  
defined to be some procedure that works on code, be that code a string  
or some more structured form of data. In a language like Cat, there's  
no such code being passed around as there is in Joy, and I don't think  
there's anyone here who would say Cat isn't concatenative.

What I'm interested in is this "dequotation" rule:

    [$A] i  ==  $A

In other words, these are all equivalent:

    1 2 [3 * *] i  ==  1 2 3 * *  ==  1 [2 3] i [* *] i

An important thing to note here is that this translation is just a  
rewriting of function-level code. '$A' is a function, not a value.  
This seems fundamentally different from this rule in the combinatory  
calculus, where 'x' is a *value*, not a function:

    (I x)  ==  x

(William already has said essentially the same thing with respect to  
operators and operands.)

I guess my questions are as follows: Are concatenative languages  
applicative, and if so, what's the equivalent of '[$A] i == $A' in the  
lambda calculus? If such a translation cannot be given, does that mean  
concatenative languages are non-applicative? If so, is there another  
term besides "concatenative" that can be used to describe their  
properties?

- John

[John Cowan]

John Nowak scripsit:

> What I'm interested in is this "dequotation" rule:
>
>     [$A] i  ==  $A
>
> In other words, these are all equivalent:
>
>     1 2 [3 * *] i  ==  1 2 3 * *  ==  1 [2 3] i [* *] i
>
> An important thing to note here is that this translation is just a  
> rewriting of function-level code. '$A' is a function, not a value.  

Well, yes and no.  In Joy, at least, *everything* is a value, and
every value may be applied to the stack.  So [1 2 3] is the value
"the list containing 1, 2, and 3" where 1, 2, 3, and the list itself
are just values.  Only when we apply i (which itself is just a symbol)
to a stack with [1 2 3] at the top of it are 1, 2, and 3 applied
to the rest of the stack.

This is quite different from Cat (or Scheme) where some values are
applyable and some are not.

--
Mos Eisley spaceport.  You will never           John Cowan
see a more wretched hive of scum and            cowan@...
villainy -- unless you watch the                http://www.ccil.org/~cowan
Jerry Springer Show.   --georgettesworld.com

[John Nowak]

On Apr 24, 2008, at 6:47 PM, John Cowan wrote:

> John Nowak scripsit:
>
>> What I'm interested in is this "dequotation" rule:
>>
>>    [$A] i  ==  $A
>>
>> In other words, these are all equivalent:
>>
>>    1 2 [3 * *] i  ==  1 2 3 * *  ==  1 [2 3] i [* *] i
>>
>> An important thing to note here is that this translation is just a
>> rewriting of function-level code. '$A' is a function, not a value.
>
> Well, yes and no.  In Joy, at least, *everything* is a value, and
> every value may be applied to the stack.  So [1 2 3] is the value
> "the list containing 1, 2, and 3" where 1, 2, 3, and the list itself
> are just values.

We need to be more careful. Joy programs are expressed entirely in  
terms of functions. Joy is a function-level language. I'll give three  
examples to make this clear:

- '[1 2 3]' is a *function* of type 'A -> A [B -> B Num Num Num]';  
when evaluated, it pushes the *value* [1 2 3] of type '[A -> A Num Num  
Num]' onto the stack

- '1 2 3' is a *function* of type 'A -> A Num Num Num'; when  
evaluated, the *values* 1, 2, and 3 get pushed onto the stack

- '3' is a *function* of type 'A -> A Num', not a value of type 'Num'  
as in Haskell or ML; when evaluated, the *value* 3 gets pushed onto  
the stack

In short, even '3' is a function in Joy. This should be obvious as we  
can assign a name to it:

    foo = 3

Here, we're not binding 'foo' to the value of 3; we're declaring that  
'foo' is a function that pushes '3' onto the stack. According, in the  
expression 'foo foo +', we can substitute 'foo' for it's definition,  
yielding '3 3 +', which then evaluates to '6'. Never at any point are  
we manipulating values.

So this gets me back to my question...

- John

[Don Groves]

On Apr 24, 2008, at 3:10 PM, John Nowak wrote:

> Apologies for starting a new thread of sorts, but the "Object Cat"
> thread already had run through three or four different topics, and it
> seems like a good idea to discuss this in such a way that it'll be
> archived properly. I'd really like an answer here.
>
> First off, let me say that I'm not particularly interested in if Joy's
> 'i' is an 'eval'. This does, as Chris pointed out, seem to get us
> bogged down in implementation details. As far as I can tell, 'eval' is
> defined to be some procedure that works on code, be that code a string
> or some more structured form of data. In a language like Cat, there's
> no such code being passed around as there is in Joy, and I don't think
> there's anyone here who would say Cat isn't concatenative.
>
> What I'm interested in is this "dequotation" rule:
>
>    [$A] i  ==  $A
>
> In other words, these are all equivalent:
>
>    1 2 [3 * *] i  ==  1 2 3 * *  ==  1 [2 3] i [* *] i
>
> An important thing to note here is that this translation is just a
> rewriting of function-level code. '$A' is a function, not a value.
> This seems fundamentally different from this rule in the combinatory
> calculus, where 'x' is a *value*, not a function:
>
>    (I x)  ==  x
>
> (William already has said essentially the same thing with respect to
> operators and operands.)
>
> I guess my questions are as follows: Are concatenative languages
> applicative, and if so, what's the equivalent of '[$A] i == $A' in the
> lambda calculus?

As I understand it, the lambda calculus form  \X.E  represents an  
abstraction
(\X) and an application (E). Seems to me a straightforward reading of  
Joy's
[foo] as an abstraction and i as being/causing an application is the  
equivalence
you seek. Joy's i and lambda calculus' dot perform the same function  
in their
respective languages.

Am I the only one here who thinks the word "function" has too many  
meanings?
--
don


> ...If such a translation cannot be given, does that mean
> concatenative languages are non-applicative? If so, is there another
> term besides "concatenative" that can be used to describe their
> properties?
>
> - John

[Don Groves]

On Apr 24, 2008, at 6:58 PM, Don Groves wrote:

> On Apr 24, 2008, at 3:10 PM, John Nowak wrote:
>
>> Apologies for starting a new thread of sorts, but the "Object Cat"
>> thread already had run through three or four different topics, and it
>> seems like a good idea to discuss this in such a way that it'll be
>> archived properly. I'd really like an answer here.
>>
>> First off, let me say that I'm not particularly interested in if  
>> Joy's
>> 'i' is an 'eval'. This does, as Chris pointed out, seem to get us
>> bogged down in implementation details. As far as I can tell, 'eval'  
>> is
>> defined to be some procedure that works on code, be that code a  
>> string
>> or some more structured form of data. In a language like Cat, there's
>> no such code being passed around as there is in Joy, and I don't  
>> think
>> there's anyone here who would say Cat isn't concatenative.
>>
>> What I'm interested in is this "dequotation" rule:
>>
>>   [$A] i  ==  $A
>>
>> In other words, these are all equivalent:
>>
>>   1 2 [3 * *] i  ==  1 2 3 * *  ==  1 [2 3] i [* *] i
>>
>> An important thing to note here is that this translation is just a
>> rewriting of function-level code. '$A' is a function, not a value.
>> This seems fundamentally different from this rule in the combinatory
>> calculus, where 'x' is a *value*, not a function:
>>
>>   (I x)  ==  x
>>
>> (William already has said essentially the same thing with respect to
>> operators and operands.)
>>
>> I guess my questions are as follows: Are concatenative languages
>> applicative, and if so, what's the equivalent of '[$A] i == $A' in  
>> the
>> lambda calculus?
>
> As I understand it, the lambda calculus form  \X.E  represents an
> abstraction
> (\X) and an application (E). Seems to me a straightforward reading of
> Joy's
> [foo] as an abstraction and i as being/causing an application is the
> equivalence
> you seek. Joy's i and lambda calculus' dot perform the same function
> in their
> respective languages.
>
> Am I the only one here who thinks the word "function" has too many
> meanings?
> --
> don

I didn't finish answering your question: The lambda calculus equivalent
of [$A] i is \A.S where S is the stack.
--
don

>
>
>
>> ...If such a translation cannot be given, does that mean
>> concatenative languages are non-applicative? If so, is there another
>> term besides "concatenative" that can be used to describe their
>> properties?
>>
>> - John
>
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>
>

[John Cowan]

John Nowak scripsit:

> We need to be more careful. Joy programs are expressed entirely in  
> terms of functions. Joy is a function-level language. I'll give three  
> examples to make this clear:
>
> - '[1 2 3]' is a *function* of type 'A -> A [B -> B Num Num Num]';  
> when evaluated, it pushes the *value* [1 2 3] of type '[A -> A Num Num  
> Num]' onto the stack

I deny this.  I say that the type of [1 2 3] as a value is [Int Int Int],
and as a function its type is A -> A [Int Int Int].

> - '1 2 3' is a *function* of type 'A -> A Num Num Num'; when  
> evaluated, the *values* 1, 2, and 3 get pushed onto the stack

I agree with that.

> - '3' is a *function* of type 'A -> A Num', not a value of type 'Num'  
> as in Haskell or ML; when evaluated, the *value* 3 gets pushed onto  
> the stack [...]

You are making a distinction between '3' and 3 that I believe to be
unwarranted.  There is only 3, and it is both a numeric value and
a function to be applied to the stack.

> In short, even '3' is a function in Joy. This should be obvious as we  
> can assign a name to it:
>
>     foo = 3
>
> Here, we're not binding 'foo' to the value of 3; we're declaring that  
> 'foo' is a function that pushes '3' onto the stack.

We are doing both at once.

> Never at any point are we manipulating values.

The function +, among many others, can only be understood in terms
of values.

--
Barry gules and argent of seven and six,        John Cowan
on a canton azure fifty molets of the second.   cowan@...
        --blazoning the U.S. flag               http://www.ccil.org/~cowan

[John Nowak]

On Apr 24, 2008, at 10:35 PM, John Cowan wrote:

> John Nowak scripsit:
>
>> - '1 2 3' is a *function* of type 'A -> A Num Num Num'; when
>> evaluated, the *values* 1, 2, and 3 get pushed onto the stack
>
> I agree with that.
>
>> - '3' is a *function* of type 'A -> A Num', not a value of type 'Num'
>> as in Haskell or ML; when evaluated, the *value* 3 gets pushed onto
>> the stack [...]
>
> You are making a distinction between '3' and 3 that I believe to be
> unwarranted.  There is only 3, and it is both a numeric value and
> a function to be applied to the stack.

Maybe I'm not being precise enough. The type of the term '3' is 'A ->  
A Num', just like the type of '1 2 3' is 'A -> A Num Num Num'.

>> In short, even '3' is a function in Joy. This should be obvious as we
>> can assign a name to it:
>>
>>    foo = 3
>>
>> Here, we're not binding 'foo' to the value of 3; we're declaring that
>> 'foo' is a function that pushes '3' onto the stack.
>
> We are doing both at once.

No we're not; we don't evaluate the right-hand side to figure out what  
to bind 'foo' too.

>> Never at any point are we manipulating values.
>
> The function +, among many others, can only be understood in terms  
> of values.

Sure, but when we're manipulating programs, such as translating '1 [2  
+] i' to '1 2 +', we're not manipulating any terms bound to values.

- John

[John Cowan]

John Nowak scripsit:

> Maybe I'm not being precise enough. The type of the term '3' is 'A ->  
> A Num', just like the type of '1 2 3' is 'A -> A Num Num Num'.

That is, those are their types when they are seen as functions.  When
seen as values, their types are 'Num' and 'Num Num Num'.

> No we're not; we don't evaluate the right-hand side to figure out what  
> to bind 'foo' too.

Correct.  The declaration "foo == 3" means that as functions 'foo' and '3'
have the same function type, namely 'A -> A Int'.  (As values, they are
still different:  '3' has type Int, 'foo' has type Symbol.)

But where we differ, or did differ, is about '[1 2 3]', which I say has a
function type of 'A -> A [Num Num Num]', not 'A -> [A -> A Num Num Num]]'.
And that is because Joy lists are not inherently quotations, though they
are treated as quotations by certain functions.

--
Man has no body distinct from his soul,                 John Cowan
for that called body is a portion of the soul           cowan@...
discerned by the five senses,                           http://www.ccil.org
the chief inlets of the soul in this age.  --William Blake

[John Nowak]

On Apr 24, 2008, at 11:56 PM, John Cowan wrote:

> But where we differ, or did differ, is about '[1 2 3]', which I say  
> has a
> function type of 'A -> A [Num Num Num]', not 'A -> [A -> A Num Num  
> Num]]'.
> And that is because Joy lists are not inherently quotations, though  
> they
> are treated as quotations by certain functions.

Well, to be clear, I said A -> A [B -> B Num Num Num]. Either way, I  
should've said that I don't give a damn about Joy, but rather  
concatenative languages in general. I think I've answered my own  
question anyway: No, they're not applicative.

- John

[Manfred Von Thun]

On 25/4/08 11:58 AM, "Don Groves" <dgroves@...> wrote:

> On Apr 24, 2008, at 3:10 PM, John Nowak wrote:
>
>> > First off, let me say that I'm not particularly interested in if Joy's
>> > 'i' is an 'eval'. This does, as Chris pointed out, seem to get us
>> > bogged down in implementation details.
>
Emphatically, it is not an implementation detail. Any programming
language ultimately runs in machine language, which is sequential
(with jumps, though). At intermediate levels it can be implemented
in functional or in procedural languages. Any functional language
can be implemented in a functional or a procedural language, or
by rewriting ­ even concurrent rewriting. The details of the rewriting
will depend on the syntax of the functional language. For a
concatenative language, here is a (crazy, but correct) algorithm
for rewriting an expression in the language, using several clerical
workers concurrently:
>
REPEAT:
    The workers at random select an operator in the expression.
    If it is immediately preceded by the appropriate number of
    operands, replace the operands and the operator by a value.
    (For example, (... 2  3 +  ...) is replaced by (... 5 ...).)
UNTIL there are no more operators in the expression
>
This is a way of implementing any concatenative language, even
if crazy. The usual stack implementation of concatenative languages
is just an efficient way of finding operators that are immediately
preceded by their operands.

Whether Joy¹s i combinator is an eval is a semantic question that
is independent of the implementation, whether by stack or by
rewriting.
>
 - Manfre


[Non-text portions of this message have been removed]

[Manfred Von Thun]

On 25/4/08 8:10 AM, "John Nowak" <john@...> wrote:

> [..]
> What I'm interested in is this "dequotation" rule:
>
> [$A] i  ==  $A
>
> In other words, these are all equivalent:
>
> 1 2 [3 * *] i  ==  1 2 3 * *  ==  1 [2 3] i [* *] i
>
> An important thing to note here is that this translation is just a
> rewriting of function-level code. '$A' is a function, not a value.
> This seems fundamentally different from this rule in the combinatory
> calculus, where 'x' is a *value*, not a function:
>
> (I x)  ==  x
>

Indeed, they are different, and there is no exact equivalent because the
combinatory calculus does not have any kind of quoting mechanism.

Incidentally, the quote/eval relationship holds in any language
that has these two operators, where eval is essentially dequote
(I did not invent the term dequote, it is used by semanticists as in
the first example:)

    eval(quote(snow is white) = (show is white) = true
    eval(quote((2 + 3) * 4)) = ((2 + 3) * 4) = 20

> I guess my questions are as follows: Are concatenative languages
> applicative, ....
>
The ones I know about do not have an explicit application operation
(unlike +). Nor do they have an implicit application operation
(unlike function composition).

The semantics of function composition can be explained in terms
of application (apl):

     (A B C..)  apl  X  =  (B C..) apl (A apl X)
     () apl X  =  X

This is quite general, independent of what sort of a thing X
might be. It also holds for languages which have function operations
other than function composition. But it is independent of how
the language is implemented. It is true that for implementations
of concatenative languages the X is invariably a stack and the
two clauses above are at the heart of the implementation.

> .... and if so, what's the equivalent of '[$A] i == $A' in the
> lambda calculus? ....
>
There is no equivalent. Lambda calculus, like combinatory
calculus, does not have a quote operator. The equivalent of
your combinatory calculus (I x) = x is of course (lambda x. x).
>
> ....If such a translation cannot be given, does that mean
> concatenative languages are non-applicative? ...

Having the quote/eval pair (or a syntactic variant) should not be
part of the definition a concatenative language. The two issues
(of quote/eval pair and concatenativity) are entirely independent.
So the lack of such a translation does not ..mean.. that concatenative
languages are non-applicative.

Nevertheless concatenative languages ..are.. non-applicative.
The lambda calculus and its derivatives (Lisp) are applicative,
and so is the combinatory calculus. Both have the important
operation of applying a function to arguments(s). Lambda calculus
also has function abstraction, combinatory calculus does not.

>
> ... If so, is there another
> term besides "concatenative" that can be used to describe their
> properties?
>
Billy Tanksley invented the term when he founded this group.
(thanks William). I prefer his term to the ludicrous alternative:

Language-in-which-the-associative-operation-of­program-
concatenation-denotes-the-associative-operation-of-function-
composition-as-the-principal-program-forming-construction.
>
  - Manfred
>



[Non-text portions of this message have been removed]

[Robbert van Dalen-2]

> The details of the rewriting
> will depend on the syntax of the functional language. For a
> concatenative language, here is a (crazy, but correct) algorithm
> for rewriting an expression in the language, using several clerical
> workers concurrently:
> >
> REPEAT:
>     The workers at random select an operator in the expression.
>     If it is immediately preceded by the appropriate number of
>     operands, replace the operands and the operator by a value.
>     (For example, (... 2  3 +  ...) is replaced by (... 5 ...).)
> UNTIL there are no more operators in the expression
> >
> This is a way of implementing any concatenative language, even
> if crazy. The usual stack implementation of concatenative languages
> is just an efficient way of finding operators that are immediately
> preceded by their operands.

This possibility to do concurrent rewritings of expressions is the
sole reason why Enchilada has postfix syntax. Therefor I would claim
it isn't crazy at all :)

- Robbert.

[Manfred Von Thun]

Still on the topic of quote and eval, it occurred to me that the Unix
command
languages (sh, csh, ksh, bash,..) have their own eval operator. It is the
backquote mechanism, which will evaluate what is enclosed inside the
backquotes `...` (I don¹t know what my mailer will do to it, it is the key
just under escape key at the top left). Example:

echo ³Today¹s date and the current time is `date`, have a nice day!²

Here the echo means print the following message which contains a short
backquoted command. The command returns a string that will be spliced
into the message. More complex commands can be backquoted:

echo ³In your home directory you have `ls ­la ~ | wc ­l ` files²

Here the ls command produces an output which is piped (with |)
to the wordcount facility wc to count just the lines.

The beauty of the various Unix utilities is that you can pipe the output
of one to become the input to the next. The backquote substitution
can make good use of it.

Is there a lesson to be learned for concatenative languages?
We have discussed Unix pipes briefly before, and their semantics
is clear: a pipe  X | Y | Z computes the composition of the functions
X, Y and Z, just as any other concatenative language. But the
backquote is something else deserving a thorough examination.

  - Manfred



[Non-text portions of this message have been removed]

[Rahul-17]

....
> Is there a lesson to be learned for concatenative languages?
> We have discussed Unix pipes briefly before, and their semantics
> is clear: a pipe  X | Y | Z computes the composition of the functions
> X, Y and Z, just as any other concatenative language. But the
> backquote is something else deserving a thorough examination.

You may find this interesting

http://rosettacode.org/wiki/Category:UnixPipes

(Using unix pipes and files rather than the shell language).

>   - Manfred

Rahul

------------------------------------

Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/concatenative/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/concatenative/join
    (Yahoo! ID required)

<*> To change settings via email:
    mailto:concatenative-digest@...
    mailto:concatenative-fullfeatured@...

<*> To unsubscribe from this group, send an email to:
    concatenative-unsubscribe@...

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/

[William Tanksley, Jr]

Manfred Von Thun <m.vonthun@...> wrote:
> Still on the topic of quote and eval, it occurred to me that the Unix
>  command
>  languages (sh, csh, ksh, bash,..) have their own eval operator. It is the
>  backquote mechanism, which will evaluate what is enclosed inside the
>  backquotes `...` (I don¹t know what my mailer will do to it, it is the key
>  just under escape key at the top left).

>  Is there a lesson to be learned for concatenative languages?

I don't know what the lesson would be. Backquotes escape from a string
context to an executation/evaluation context. I suppose one could do
that in a concatenative language that had a string syntax.

More generally, I suppose one could "escape" from any context to an
evaluation, thus allowing you to compute a value at runtime which will
be compiled into the current quotation.

>   - Manfred

-Wm

[John Cowan]

Manfred Von Thun scripsit:

> The beauty of the various Unix utilities is that you can pipe the output
> of one to become the input to the next. The backquote substitution
> can make good use of it.

Backquotes -- as is clearly shown by the alternative syntax $(...) --
essentially belong to the lexical level of the shell, just like $name
substitution.  So they are very like Lisp macros: code inside backquotes
runs in a subshell to produce *source code* which is then evaluated by
the main shell in context, just as a Lisp macro runs in an subordinate
evaluator to generate Lisp code to be run by the main evaluator in
context.

--
What has four pairs of pants, lives             John Cowan
in Philadelphia, and it never rains             http://www.ccil.org/~cowan
but it pours?                                   cowan@...
        --Rufus T. Firefly

[Christopher Diggins]

So IIUC applying the idea to a concatenative language like Cat:

   [is_weekend ["happy'] ["sad"] if] ` apply

Will generate different code depending on the day of week it is compiled.

Neat!

- Christopher

On Tue, May 13, 2008 at 4:35 PM, John Cowan <cowan@...> wrote:

>
>
>
>
> Manfred Von Thun scripsit:
>
>
> > The beauty of the various Unix utilities is that you can pipe the output
> > of one to become the input to the next. The backquote substitution
> > can make good use of it.
>
> Backquotes -- as is clearly shown by the alternative syntax $(...) --
> essentially belong to the lexical level of the shell, just like $name
> substitution. So they are very like Lisp macros: code inside backquotes
> runs in a subshell to produce *source code* which is then evaluated by
> the main shell in context, just as a Lisp macro runs in an subordinate
> evaluator to generate Lisp code to be run by the main evaluator in
> context.
>
> --
> What has four pairs of pants, lives John Cowan
> in Philadelphia, and it never rains http://www.ccil.org/~cowan
> but it pours? cowan@...
> --Rufus T. Firefly
>
>
>

[Manfred Von Thun]

On 14/5/08 6:19 AM, "William Tanksley, Jr" <wtanksleyjr@...</