Re: [stack] the concatenative wikipedia article

John Nowak <[email protected]> wrote:
> William Tanksley, Jr wrote:
>> 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.

I have to blush -- I'd forgotten that part. Yes, you're right; I was
thinking of a purely concatenative language, one with no
non-associative syntax at all (AKA "flat"). Quotation is a strange
thing to throw into an allegedly concatenative combinator base,
though; unlike application, it's not an inherent part of the language
paradigm; thus, I think my confusion is justified.

>> 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):

I'm not saying that the entire language is more complex; I'm saying
that the combinator basis is more complex, as measured by the fact
that you must have two combinators rather than only one.

Meertens is interesting; thank you for the reference. I've put it on
my "read immediately" stack.

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

http://barker.linguistics.fas.nyu.edu/Stuff/Iota/
There are many ways to measure the "complexity" of a combinator. None
of them are obviously correct.

> - John

-Wm