Re: [stack] are concatenative languages applicative?

On 25/4/08 8:10 AM, "John Nowak" <[email protected]> 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]