Rewriting (was: Type-checking, GC, Forth, rewriting..)

[Massimo Dentico]

Hendrik Boom wrote:

> > > Ugh Rewriting is slow.
> > 
> > Well, I'm not familiar with its implementation (an interpreter
> > written in C) but consider that:
> > 
> > a) Joy semantics is about pure functions from stack to stack;
> >   rewriting rules are used only to clarify this semantics
> >   and to reason about programs; there is nothing in the
> >   language which prevent use of Forth-like implementation
> >   techniques, both for interpretation - with various
> >   threaded code techniques - that for compilation.
> 
> The description I saw suggested that it was actually interpreted
> using a rewriting tool.  This would be slow.  If it was just a
> formal description, but execution was by other means, that would
> be different, of course.

I see. You need, preferably, a language with a good implementation
already. Again, I don't know much about its current C implementation,
but I think it is quite slow.


> My aversion to rewriting is not absolute.  One of my most-used
> tools here is a rewriting engine that compiles its rewriting
> rules directly into C code.  But it imposes a lot of structure
> in the rewriting system, a lot of context (symbol tables and
> the like), and a backtracking mechanism for when things fail.
> My experience is that when the real point of your application
> is the rewriting of trees, then a rewriting system is fine.
> But when it is something else that has been encoded as a
> rewriting system (rewriting is a universal computational
> formalism, after all),  you lose big.

Yes, I understood your point. But consider this:

as you noted, rewriting is a universal computational
formalism, but is *not* really so distant to the execution
model of the "bare metal"; in fact every time you
JSR (Jump to SuBroutine) you are rewriting, in a sense.

This analogy is so striking that Philip Koopman
(http://www.ece.cmu.edu/~koopman/) based his Architecture
for Combinator Graph Reduction (you know, rewriting under
another name) on Threaded Code. See Threaded Interpretive
Graph Reduction Engine (TIGRE):

  http://cliki.tunes.org/TIGRE

Now, if you note that there is a form of threaded code called
"subroutine-threaded code", the circle is closed; see details
at the URI below, under "What is Threaded Code?":

  http://www.complang.tuwien.ac.at/forth/threaded-code.html

IIRC, even Koopman used it as an optmization, on CPUs where
subroutine-threaded code is more efficient than pure
threaded code.

A variation on the same theme is AGATE

  http://pages.cpsc.ucalgary.ca/~aycock/agate/

here John Aycock do computations expanding grammar production
rules (rewriting again).

Some Forth compilers start from subroutine-threaded code,
add inlining of primitives, stack caching (mapping stack to
registers), peephole optimizations and obtain reasonable
machine code (see, for example, http://c2.com/cgi/wiki?ForthCompiler
and "Performance of Forth systems"
http://www.complang.tuwien.ac.at/forth/performance.html)

People is often convinced that powerful abstractions, like
rewriting rules, cannot be implemented efficiently because
CS researchers implement they abstrusely and inefficiently in
prototypes. They (CS researchers) seems so proud to be detached
from the machine level, these days. A sad state of affairs.
(Note that Koopman has an engineering background.)

 
> I just saw how long this letter I'm answering is, and
> I appreciate it -- it's so rare to get an extensive,
> well-thought-out answer on a mailing list, and you
> deserve the same. But I'm running out of time today --
> -- I still have tax forms to file.  A proper reply
> would probably take an entire essay, which I intend to get
> around to soon.

No problem, really. Take your time to respond.

 
> Thanks again

I thank you also, you stimulated me to write down about
all these points, connected in my mind. 


P.S.: to much relevant material and so I forgetted to mention,
      in my previous e-mail, Vlerq by Jean-Claude Wippler
      
        http://www.vlerq.org/
      
      this will be a GCed Forth-like language mixed with
      APL-like vector operators (he speaks about "relations"
      also, but they are not relations as per relational
      data model, at least for now: I consider this a mistake,
      relational operators gave incorrect results in presence
      of duplicate tuples).

 
> -- hendrik

--
Massimo Dentico