Re: [stack] the concatenative wikipedia article

On Jan 12, 2009, at 9:44 AM, William Tanksley, Jr wrote:

> Sorry for the unclarity -- no. A 'sibling' operation refers to
> something like 'pair'; a way to encode two data items at the same
> level of nesting.

Ah. Thanks for clarifying.

> The minimal basis for applicative languages contains one combinator;
> the minimal basis for concatenative languages contains two
> (http://portal.acm.org/citation.cfm?id=967781.967785 has a proof).

This doesn't seem to be the case for a concatenative language with  
quotation (push). Okasaki is dealing with the additional limitation of  
"flatness". I suppose you could count quotation as a combinator of  
sorts, but in either case it's a very simple operation.

> See the page that ieros/Kerby wrote on concatenative combinators. In
> order to make up for this advantage, concatenative combinators have to
> be more complex than applicative ones

I'm not sure this is the case. Quotation, composition, and one  
combinator doesn't seem more complex than application and one  
combinator to me, just different. Here's Meertens on the subject (I  
believe from http://portal.acm.org/citation.cfm?id=746988):

"The basic problem is that the basic operation of the classical  
combinator calculus (and also of the closely related lambda calculus)  
is application instead of composition. Application has not a single  
property. Function composition is associative and has an identity  
element (if one believes in the 'generic' identity function)."

Perhaps I'm wrong, but I think you may be judging "complexity" simply  
by counting the number of primitive elements. I don't think this is a  
useful metric.

- John