Ray Dillinger  <bear@sonic.net> wrote:
+---------------
| Even with the reduced power of a type-2 grammar (the context-free 
| languages, which includes nearly all modern computer languages)
| you can directly solve most math problems using string manipulation 
| rules. I know, because I implemented exactly that as homework once.
| You start by implementing incrementing, decrementing, doubling, 
| and halving as string transformation operations, introduce 
| nonterminal symbols that can prepend numbers indicating that one 
| of these operations is needed, and go from there. 
| 
| I guess my point is that "transforming strings into strings" 
| *is* a pretty darn good model of what a compiler does, and a 
| pretty good model of semantics, and understanding the theory 
| *is* relevant far beyond dealing with the surface syntax of a 
| language.
+---------------

Indeed. In this regard Kent Dybvig's PhD thesis[1] may be of interest
to some. It's most frequently cited for its contributions to showing
how/when one could use stack-based (versus heap-based) lexical variables
in Scheme, but also included a string-based model. From the abstract:

    This dissertation presents three implementation models for the
    Scheme Programming Language. The first is a heap-based model used
    in some form in most Scheme implementations to date; the second is
    a new stack-based model that is considerably more effcient than
    the heap-based model at executing most programs; and the third is
    a new string-based model intended for use in a multiple-processor
    implementation of Scheme. ... The string-based model allocates
    versions of these structures right in the program text, which
    is represented as a string of symbols. In the string-based model,
    Scheme programs are translated into an FFP language designed
    specifically to support Scheme. Programs in this language are
    directly executed by the FFP machine, a multiple-processor
    string-reduction computer.

And from "Chapter 5: The String-Based Model":

    The string-based implementation model proposed in this chapter is
    intended for the FFP machine... [which] employs string reduction,
    evaluating expressions in FFP by reducing the text of the FFP
    program piece by piece until each evaluable expression has been
    fully reduced. It would be possible to employ the techniques
    described herein to design a Scheme implementation for any
    processor capable of string reduction.

"Rewrite-rule" or "reduction" computers were a quite active area
of research several decades ago, though not so much these days.


-Rob

[1] http://www.cs.indiana.edu/~dyb/papers/3imp.pdf
    "Three Implementation Models for Scheme",
    R. Kent Dybvig,
    University of North Carolina Computer Science
    Technical Report 87-011 [Ph.D. Dissertation], April 1987.

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607