Fundamental Problems of Lisp

xahlee@gmail.com wrote:


> First, lets note few facts:
>
> • there is no formal and universally accepted definition of what is
> meant by “semantics”.

This statement is false. Formal semantics is mathematics. Figuring
out what a statement is supposed to do is proving a theorem given the
defined axioms of the formal semantics. The semantics of a statement
are a transformation of one program state into another. Usually we
represent the program states as strings, hence the relevance of grammars
for transforming one string into another.

> There may be some, if so defined, they are
> typically based on “models” over idealized, abstract hardware (i.e.
> operations on values in storage; as in finite state machine).

Granted, actual implementations on machines with finite memory tend
to be unable to fully implement the formal semantics of a language,
in much the same way that automated theorem provers on machines with
finite memory are unable to prove some theorems.

> • semantics is tied to syntax. There cannot be semantics without
> syntax. We could conceptualize a semantic without any syntax, but this
> is basically not done.

In current languages, semantics is tied much more closely to the parse
tree of an expression than it is to the syntax, but whatever - there
is a connection, because the parse tree is computed from the grammar
and the syntax.

> One of the question we want to ask is, what is a computer language? As
> we know, formal methods, such as those based on automata, has nothing
> to do with actual langs and is basically just the study of syntax. A
> formal languages, of course does also have semantics, but that
> semantics basically means transformation of strings. This sense is far
> different from what mean by “semantics” in pop books that deal with
> real langs (such as the the text book “Programming Languages:
> Application and Interpretation”", by Shriram Krishnamurth).

Hm. Okay, granted, a grammar transforms strings into strings.
But if the input string is program text and the output string
is machine instructions, we call that grammar a compiler. This
is not how most actual compilers are written, but this is a
complete formal model of what a compiler is and does, and therefore
allows us to prove theorems about what is and isn't possible
for compilers.

Anyway, type-0 grammars are Turing equivalent, which means they
provide a general model of computability and can calculate any
computable function. What this means is that you can implement
the semantics of any computer language as a type-0 grammar that
transforms program source and input directly into output without
ever bothering to create instructions for a specific machine along
the way. You can also implement a grammar that transforms your
program text into another grammar, which will transform input
into output.

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.




> The other question we want to ask, related to the above, is “what
> exactly is a computer language?”. There is a popular, unconcious

true

> belief, that a computer language is made up of syntax and semantics.

....

> another reason syntax is far more important can be seen from the
> history of math notations. ... if you are acquainted
> in history of math notation, you'll know that notation largely drove
> many development and directions of mathematics. Examples include
> arabic numeral with decimal positional notation, symbols for variables
> → abstract algebra, matrix notation → linear algebra, some notations →
> calculus. (notations, is somewhat like terminology, in that sometimes
> the existance of a notation/terminology have huge impact from
> awareness of the concept to major influence on thought of a subject.)
>

This is definitely true. A good notation makes something easier to
reason about, usually by associating or "bundling" related concepts
in a more efficient or useful way.

Bear

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

rpw3@rpw3.org (Rob Warnock) writes:
> "Rewrite-rule" or "reduction" computers were a quite active area
> of research several decades ago, though not so much these days.

I think Haskell is just about always implemented with graph rewriting
(reduction), though specified in lambda calculus. Clean is specified
in terms of graph rewriting which the authors claim has advantages.