Fri Jun 5 10:44:08 CEST 2009

metacircular forth unrolling

Ha.. Again, it's not so simple as I thought: Scat needs to be extended
to make the macros based on "branch" and "?branch" work.

I believe here lies the "almost a new thing" part of unifying the
prefix parser and the inner interpreter.  I've been trying to make
this explicit for a while.  The idea is this:

  * Parsing words read the next word from the input stream before the
    normal interpreter has a chance to interpret it in the default way
    (lookup + execute/compile)

  * "doLIT", "branch" and "?branch" implement control flow exceptions
    for the inner interpreter.

Note that in both cases a proper quoting mechanism can reduce the
number of words that do this to one.  This is what the (quote _) form
does in the rpn syntax: it loads an atom from the input stream on the
stack, upon which normal semantics can be used to manipulate it

So.. There's something simple hidden here. It's all about stacks.

   Prefix parsers in Staapl use the input stream as a stack.  Forth's
   parsing words don't do this, neither does the inner interpreter.

   The reason Scat seems to not need a stack is because it implicitly
   uses a tree instead (Scheme's closure structure).

What is a procedure call?  It prefixes the current continuation (a
code list) with a code list.  There is something disturbingly
non-circular about this..  A trap I fell into many times before..

There are really 3 stacks, and they correspond to the 3 registers of
the CEK machine:

  * Code (input threaded code)
  * Environment (data stack)
  * Kontinuation (return stack)

But there is this interesting relation between C and K.

Anyway.. I'm getting confused and need to re-establish contact with
the concrete.


  - how to unify rpn-parse with rpn-lambda, writing parsers in terms
    of scat code that accesses the code stack?

It is important to see that (prefix-parsers ...) is also a stack

The problem however is that it is really arbitrary what function these
stacks have..  It's only the number of stacks that is important, and
whether they are used as stacks or as streams.

This story is really about parsing and rewriting..  Is there some
theory about this?  Is a 2-stack machine fundamentally different from
a 1-stack machine or a 3-stack machine?

One of Chuck Moore's slogans is: you need stacks, and you need at
least two.

So why is one different from two?  I'm missing a lot of theoretical
knowledge to know where not to look..  I'd say in general the
introduction of an extra stack would help you to save whatever you
_were_ doing with N-1 stacks on the Nth stack, and solve a subproblem
that needs N-1 stacks.

It might be an interesting problem to define all functionality in scat
in terms of an N-stack machine.  It is already very much like that,
just not explicit:

   - prefix parsers (rewrite rules) use the input stream as a stack.
   - prefix parsers use the dictionary (a stack of stacks)
   - the CFG compiler uses a set of stack of stacks.

the basic structure of Forth is the interpreter:

  D D E x x x D D D D

where "D" are tokens to be interpreted in the default way and "E"
exception tags that change the meaning of subsequent terms.  By
interleaving the "D" with their semantics you get:

  (C D) (C D) (E x x x) (C D) (C D)

Where "C" is the default compilation action.

But I'm moving too far away into the abyss..