[<<][compsci][>>][..]
Fri Jun 5 12:04:02 CEST 2009

Stacks

I'm trying to figure out some abstract structure of 2-stack Forth
systems, combined with parsing (input and output stream).

The structure of Forth is quite remarkable.  It is implemented very
compactly by using different stacks and streams.  However, its
(sparse) use of direct mutation to break cycles during compilation
makes it difficult to analyse and cast into a stream / stack / tree /
directed-graph / graph structure.

The idea I'd like to develop serves to answer the question:

    "Why are 2 stacks different than 1 stack?"

From programming in Forth I can answer this in vague terms as:

    "It's possible to save work to the 2nd stack when you need to
     perform a subtask using the 1st one."

This can probably be generalized to:

    "It's possible to save work to the Nth stack when you need to
    perform a subtask using the other N-1 stacks.

This doesn't need to be ordered, so you could see all stacks as
equivalent and pick one to save work while the others are used in a
subproblem.

The question then is: can this be formalized a bit more?  Can Forth,
its (self-hosted) compilation algorithm and 2-stack computation and
composition model be expressed as some structure with morphisms, and
are there relations of transforming N-stack machines to N-1 stack
machines?

Pardon my rambling..  A stack might be seen as a prototypical
complexity reducer.  The most basic data structure to encode
composition mechanism in a way that is simple to express in hardware.
A stack is the "mother of locality".  And locality is an essential
concept in (physical) computation: if the data ain't in your hand, you
can't do anything with it.  Stacks connect "now" with "later" in a
flexible way.

The mutation that's present in Forth actually only happens as part of
a mechanism to compute forward and backward loops.  It is what turns a
flat code stream into a directed (control flow) graph.  So, in order
to simplify Forth, this mechanism needs to be replaced by something
that can be _reduced_ to it, i.e. higher order functions and their
partial evaluation (jumps are PE of applications).




[Reply][About]
[<<][compsci][>>][..]