Wed Jul 16 13:00:14 CEST 2008
documentation -> parser itches
I feel that the most important layer Scat -> Coma + Control is
ready. It's simple enough now to be documented. However, the Forth +
parser part isn't very well written.. Does it make sense to spend some
time on cleaning it up? The main questions are:
Q: Is it possible to write the compiler more as a substitution system
instead of a CPS parser?
Q: Is that desireable?
Sticking with the CPS approach, the state that's passed might need
some simplification. The mistake I made is to pass an expression that
will only be added to on the outside, but what is really necessary is
to be able to insert into expressions. This requires a cursor into a
tree. The problem is that I don't know that data structure well enough
to get to this implementation from an intuitive approach.
Q: What is a zipper?
There are two views, one is a fairly straightforward 'reversal of
pointers' where each node encodes a path through to the top node using
the following data structures:
(define-struct path (left path right))
(define-struct cursor (current path))
A path contains a list of left sibling trees, a list of right sibling
trees and a path. If path is #f the current node is the top node.
According to this:
Zipper can be represented as a delimited continuation of a depth first
traversal. It seems this works only for updating nodes, not for adding
them. (or not?)
Anyways, simple straightforward manipulation might be enough to
transform the tree used in the expression accumulator of the Scat
parser into a zipper structure, to get rid of the 'wrapping'
Zipper as continuation is actually not so hard to understand: the
'reversed pointers' are really nothing more than stack frame links in
the recursive decent of the structure.