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

Stevan Apter wrote:
> the way i see the stack is that it's the price you pay for postfix
> syntax.  information is subtracted from expressions written in 
> applicative syntax and shoved into the stack order.  to recover
> that information, you shuffle the stack around.  mentally, you're
> now doing work that the syntax previously did for you.  that *may*
> not be a bad trade-off.  it depends on whether the syntactic 
> simplification offers new benefits in writing, extending, re-
> reading, &c., e.g. factoring.

I think this is a nuanced and accurate view of the situation. Yes, the
applicative syntax carries information that can't be carried by the much
lighter concatenative syntax.

Because of this, converting from applicative to concatenative requires
information processing, and the final result will normally be more
verbose (because words, normally stack shuffle words, will be used to
replace what used to be done with syntax).

In fact, stack languages require MORE information than data-name
languages, because every item is associated with a unique, non-constant
stack depth. This additional information is troublesome to track, but
does have one useful benefit: an optimizer can use it as a quick
heuristic for how soon the data item will be used. This means that items
deep in the stack can (conceptually) be stored in slower memory, while
items at the top should be stored in fast registers or on a cache line.

Because this information is actually present in every stack-based
program and NOT present (in general) in non-stack programs, it means
that when the optimizer uses it, it's actually using information that
the programmer put there on purpose. Thus, when you're writing
neat-looking stack code, you're accidentally writing efficient stack
code.

There's a big problem with this "insight" (which is not a new one).
There's a LOT more information involved in assigning a total order to
the stack than an optimizer can use. The optimizer can only assign a few
datums to the registers and ten or twenty items to each cache line, and
there's overhead from managing all those levels of caching. I'm not
aware of any optimizer that actually manages more than two levels
(register and memory); to the best of my knowledge, none of them try to
manage cache beyond following simple best-practice static rules. This
means that although every stack programmer tracks each level of the
stack uniquely and in detail, the optimizer blurs out most of that
information and uses only a few very broad levels.

> well, i'm skeptical that collection-based languages will make any
> further headway, mainly for cultural/economic reasons.

I hope you're wrong.

I think one severe problem with array languages has been the insularity
of their application... Their notation was itself difficult to approach,
and then their implementations were placed under extremely proprietary
licenses, so that learning them would be profitable only when one is
well-funded. The notation problem was gone with the introduction of J,
although K improved on that; but the license problem is still present.
Kx can take away every non-customer's ability to even run ANY K or Q
software at any time, and the specific capabilities of such software is
limited to what Kx wants to provide.

A+ is open source, but it has the same notation problem as APL (and
providing an ASCII encoding doesn't solve that; it's not what the
language is designed for, and the shortcoming is immediately obvious).

Q'NIAL is open source and has a nice encoding. After I learn Q (because
of its excellent freely available book) I plan to learn Q'NIAL. I'm not
confident in its design... The fact that the "I" stands for
"Interpreted" makes me nervous. Perhaps the fact that I want to design
an entirely different (stack based) language makes me happier.

Anyhow, I have one more thing to add to this huge, inconclusive essay.

Elsewhere in this thread there's been some discussion about static
shapechecking of arrays. IMO, there's a huge win in making the stack
static, but arrays dynamic. Arrays can represent iteration, while the
stack represents sequencing.

-Wm