Concatenative Programming

[Libor Spacek]

Hi Albert, I wonder what you think of Concatenative (stack based) Programming (e.g. Postscript, Factor, Kitten) and whether there might be scope for bringing its principles into Pure?

[Albert Graef]

Well, you could easily define some operators like, say, push, pop,
drop, rot etc. and overload the +, -, * etc. operators if you wanted
to program in that style in Pure. Is that what you mean?

> --
> You received this message because you are subscribed to the Google Groups
> "pure-lang" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to pure-lang+...@googlegroups.com.
> To post to this group, send email to pure...@googlegroups.com.
> Visit this group at http://groups.google.com/group/pure-lang?hl=en.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>



--
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email: agg...@gmail.com
WWW: http://www.musikinformatik.uni-mainz.de/ag

[Yuri D'Elia]

On 05/03/2013 10:49 AM, Albert Graef wrote:
> Well, you could easily define some operators like, say, push, pop,
> drop, rot etc. and overload the +, -, * etc. operators if you wanted
> to program in that style in Pure. Is that what you mean?

I feel it's more in the general terms, like what do you generally think
of the stack-based languages and concatenative approaches in general.

I personally think there's not that much usefulness of a stack-based
approach without being able to manipulate the dictionary of words
dynamically.

IE, you can essentially perform anything parameter-less by manipulating
an implicit stack/parameter/state in any language. In functional
languages in particular, I find there's a fine line, IMHO, between
partial application and monads - with the mayor difference that in
stack-based languages the state is always global, and manipulated
explicitly.

What actually makes concatenative languages different, though, is that
you are essentially on a stack-based virtual machine which also happens
to run the interpreter itself, which makes it very akin to lisp, minus
the homoiconicity.

I find it fascinating, given how simple concatenative languages can be
and are implemented. But they also lead to systems which are incredibly
hard to optimize, and sometimes _understand_.

I know this doesn't answer your question or necessarily mean anything
for pure ;)

[Libor Spacek]

Thanks for the replies. I agree with most of the comments, except I read that stack based languages are supposed to be easy to optimise.

[Eddie Rucker]

Hi Libor,

I've always read that register based code allowed for far more optimization opportunities than does stack based code. Are you sure you didn't read "easy to implement?" Where did you read that? I would like to see what they are doing.

Eddie Sent from my iPhone

On May 22, 2013, at 6:37 PM, "Libor Spacek" <lib...@gmail.com> wrote:

Thanks for the replies. I agree with most of the comments, except I read that stack based languages are supposed to be easy to optimise.

[me22]

On Wed, May 22, 2013 at 4:51 PM, Eddie Rucker <eru...@bmc.edu> wrote:
>
> I've always read that register based code allowed for far more optimization
> opportunities than does stack based code. Are you sure you didn't read "easy
> to implement?" Where did you read that? I would like to see what they are
> doing.
>

Maybe this is an input language vs output language issue?

I can absolutely believe that register-based target machines would
allow more optimizations than stack-based targets, but whether the
pre-code-gen AST is stack-like or register-like seems as though it
oughtn't make a meaningful difference.

[Yuri D'Elia]

On 05/23/2013 01:51 AM, Eddie Rucker wrote:
> Hi Libor,
>
> I've always read that register based code allowed for far more optimization opportunities than does stack based code. Are you sure you didn't read "easy to implement?" Where did you read that? I would like to see what they are doing.

I also read this argument a lot (Dalvik VS Java VM for instance).
It got me tingling this time, as I never did any fact-checking on it.

This (very readable) article from 2003 gives a small peek into the issue:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.5817

I always guessed that a good argument for a stack based approach is
being devoid of register limits, though this article claims that on JVM
bytecode, the average number of registers required by an _automatic_
translation would be less that 25. Which would probably be even less if
the bytecode was directly produced from SSA-form into register-based
allocation _directly_.

Still, it's quite unfair to true stack based languages. Java's strict
stack policy prevents common forth idioms, such as accumulation. You
cannot do the same kind of stack-to-register translation in forth
without peeking into future instructions, which inherently prevents
branch prediction, pipelining and actual concurrency.

I couldn't find any article about optimizing the Forth VM itself. I'm
quite curious if one could exploit optimistic concurrency using an STM
approach instead.

[John Cowan]

Yuri D'Elia scripsit:

> I always guessed that a good argument for a stack based approach is
> being devoid of register limits, though this article claims that on JVM
> bytecode, the average number of registers required by an _automatic_
> translation would be less that 25. Which would probably be even less
> if the bytecode was directly produced from SSA-form into register-based
> allocation _directly_.

Indeed, the difference between the two architectures is not so radical
as is often supposed. The famous Burroughs B machines, revolutionary
in their day, provided a stack architecture in hardware into which
the modified Algol 60 dialect they used for all purposes (there was
no assembler) was translated. But in the actual hardware, the top N
locations of the stack were kept in random logic, essentially registers,
while the rest was spilled to memory.

So in essence a stack machine is a register machine with a certain simple
allocation and register-spill strategy. It's not surprising that using
a register machine with more flexible strategies can sometimes do better.

--
Work hard, John Cowan
play hard, co...@ccil.org
die young, http://www.ccil.org/~cowan
rot quickly.

[Yuri D'Elia]

They are only the same if assumptions/restrictions on how the stack can
be manipulated are made. Look up some infos about Java's strict stack
policy.

[Yuri D'Elia]

On 05/23/2013 01:46 PM, John Cowan wrote:
> Indeed, the difference between the two architectures is not so radical
> as is often supposed. The famous Burroughs B machines, revolutionary
> in their day, provided a stack architecture in hardware into which
> the modified Algol 60 dialect they used for all purposes (there was
> no assembler) was translated. But in the actual hardware, the top N
> locations of the stack were kept in random logic, essentially registers,
> while the rest was spilled to memory.
>
> So in essence a stack machine is a register machine with a certain simple
> allocation and register-spill strategy. It's not surprising that using
> a register machine with more flexible strategies can sometimes do better.

In this case, could one consider the number of registers simply a
constraint to the optimization/register allocation? Clearly doing
register allocation at a higher level has greater advantages, since
there's greater knowledge to the variable over a longer lifetime than
cursory bytecode lookahead.

Conversely, if you already know the number of available registers, you
can either annotate the bytecode or perform registry allocation as-if on
a register machine to avoid stack spilling. At this point, it's just a
different representation.

Indeed by looking at the literature, this stuff seems to have been
studied to death, with one of the earlier references being:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.5429

Though I'm left wondering what exactly OpenJDK is currently implementing
(it it doing preemptive registry allocation apart from stack annotations?).

The Java HotSpot performance architecture
(http://www.oracle.com/technetwork/java/whitepaper-135217.html) mentions
register allocation late in the client compiler, but no mention of
annotations or attempts at stack height reduction earlier than bytecode
generation.

But I digress, this is no longer about "Pure"...