Re: [stack] Advantages of cat, joy ..?

John Nowak wrote: 
> Don Groves wrote:
> > Now, while this method of problem solving can be used in any
> > programming language, concatenative languages are built upon
> > this foundation. So, concatenative languages enable a programmer
> > to use provably-correct formal methods by their very nature.
> Interesting point. Two questions:

> 1) How much of this is due to the "flatness" of concatenative  
> languages? In a flat concatenative language, it's as easy as it could  
> possibly be to concatenate, splice, and otherwise manipulate programs.  
> Nothing gets in your way.

>From a formal analysis point of view, 'flat' isn't as useful a term as
'associative'. (I invented 'flat', so shame on me!) All languages that
have any concatenativity, to that extent have associative syntax and
semantics.

A completely flat language is completely associative -- there are no
operators that block associativity in any way. This helps theoretical
analysis because one can separate out any part of a word for analysis,
and once one understands one sequence, that understanding is valid no
matter what context it appears in. For an example where this isn't true,
consider the word 'then' in most languages (including Forth). What does
it mean? Its meaning is largely dependant on context. In PL/I it might
be a variable name OR part of the if/then syntax. A milder example is
the "[" and "]" in nested concatenative languages, and the definition
boundaries in most languages (colorForth is an interesting exception,
since almost everything's a definition, and the syntax that defines an
entry point doesn't also terminate a word).

> 2) If flatness helps, do first class quotations make things more  
> difficult? Instead of being able to split at any point, quotations  
> mean that you can only split within a certain context. I'm assuming  
> the answer here is "yes", but I've not attempted to show this yet.

Quotations with listlike operations are very, very hard to analyse.
Let's simply exclude them from discussion. Quotations themselves simply
form a boundary point -- you can't associate across an "[" or "]", but
you can freely associate within them. That's not a huge difficulty,
unless the programmer uses a ton of fragmented quotations (and if the
fragmentation follows simple syntactic rules, like always quoting
exactly one word and never nesting, those difficulties reduce to the
trivial).

> If a large part of what makes concatenative languages well-suited to  
> formal methods is their flat nature, then that would be a strong  
> argument for the stack as the proper datatype for a concatenative  
> language.

Nesting gets in the way... But not being able to quickly notate nesting
gets in the way, too. I've never figured out how to implement a
completely flat language that's any fun to program in. I may be looking
in the wrong places.

But I'm now as certain as I can be that associativity is the heart of
why concatenative languages are generally easy to analyse. The more your
language allows that, the more "concatenative" people will tend to think
it is.

> My experiments with other datatypes have all resulted in a  
> much more "nested" language with many additional functional forms.  
> William has correctly remarked that they don't even "feel"  
> concatenative.

The stack might possibly be the simplest concatenative datatype. It's
easy to add more complexity: A second stack, or a dictionary, or a
readable/writable terminal, or a queue to handle continuations, etc.
I've seen nothing that provides similar power to a stack, although I'd
like to.

Oh, by the way, ANS Forth has an optional floating point stack that it's
possible to implement as a separate stack; the programmer is supposed to
write code that's agnostic about whether floating point numbers are
stored on the data stack or somewhere else.

> If first class quotations make things more difficult, then that would  
> be a strong argument for trying the second order approach I've  
> described previously; it keeps most of the benefits of the higher  
> order approach while offering a trivial translation to a first order  
> (i.e. "flat") program.

Your second order ideas look very interesting, actually. Have you taken
a break on working with it -- I haven't heard anything... ?

> - John

-Wm