🚀 go-pugleaf

On 22 Sep 90 06:10:27 GMT, norman@d.cs.okstate.edu (Norman Graham) said:

norman> From article <2581@l.cc.purdue.edu>, by cik@l.cc.purdue.edu
norman> (Herman Rubin):

cik> A language is a set of macros to be interpreted by the compiler
cik> into machine procedures.

This is a bit crude -- less crude, but still not entirely satisfactory,
may be that a language is a set of macros for a virtual machine, and the
compiler must both expand the macros and map the virtual machine to the
real machine.

cik> There is no good reason why the user should not be allowed to add
cik> macros in convenient notation to this list, nor why many of the
cik> restrictions on the current macros need be there.

The concept of a supercompiler -- you would be pleased with Lisp/Scheme,
that do not have any such restrictions, and many Lisp/Scheme compilers,
which use a distributed compiler approach -- each relevant function is
tagged with two (or more, if you want) properties, that define its
behaviour with respect to 'COMPILE and 'INTERPRET.

	e.g. the symbol PLUS is associated, under the COMPILE property,
	with code that _generates_ "load op1, load op2, sum op1,op2,op3"
	while under the INTERPRET property it will execute the same
	sequence. A Smalltalk/Self style compiling interpreter is one
	that generates code incrementally and then passes control to the
	chunks of code so generated on the fly. Not difficult to do
	in Lisp/Scheme either.

The compiler and the interpreter are then just symbolic reduction
engines that fire the appropriate rules for each symbol they see in the
source. In one case the reducation produces code to calculate results,
in the other case directly results.  Actually if one is clever it is
possible to realize that first one wants to reduce things at compile
time as much as possible, then one wants to compile the rest.

	What you want to do is to interpret a program as much as you can,
	and then compile what remains, that will depend on free variables.

I think that Forth is similar here -- two (conceptual) dictionaries and
two distinct but similar reduction engines.

norman> This view explains why you're constantly at odds with the rest of 
norman> the netnews community.

Precisely, indeed so many in the netnews community cannot conceive of
anything different from the C or Fortran they are accustomed to use,
or indeed some others cannot see Rubin's motivation entirely, as follows.

norman> First, as anyone with a basic knowledge of languages can tell you,

I am somehow under the impression that Rubin understands languages
better than somebody that gives much importance to syntax. A recent book
on language implementation maps many disparate languages into a simple
lisp/like syntax, with no great loss.

norman> a language is a set of strings (of finite but arbitrary length)
norman> over some alphabet.

Well, that is the syntax of the language -- essentially irrelevant,
except for pragmatics. If this were literally true, yacc would be all we
need for writing compilers. But:

norman> In addition, computer languages are notations for expressing
norman> computations; they are not notations for expressing the machine
norman> instructions you want a compiler to generate.

Uhhhmmmm. Here we seem to be describing some branch of mathematics
instead -- a fairly common idea.  Computer languages exist for pragmatic
reasons. Otherwise we'd be using lambda calculus or Turing machines. I
used to think, erroneously I now understand, that computer languages are
not there to describe computations; they are there for supporting an
engineering like activity, in which expressing computations is a fairly
small part of the whole picture. Analogies are always inaccurate, but it
would be like saying that the reason for a jet engine is the
demonstration of one of Newton's laws, or of the effects of heating a
gas. Maybe civil engineering is only really about differential equations
as well.

norman> As a general rule, a computer language exists apart from any
norman> particular compiler or computer architecture, although issues of
norman> compilation and computation model may influence the design of a
norman> language.

I would dearly hope they do. Actually I would hope they are *prominent*.
I would venture as far as saying that the machine is the reason for
which the language exists. The idea that a language *definition* should
imply a virtual rather than a real machine is to aid portability,
hopefully without hurting its applicability to real machines too much,
and for languages for which portability is not important, a virtual
machine based definition is often a burden.

norman> Second, it is simply naive to describe what a compiler does as
norman> macro expansion.

Maybe you are thinking of macros as they are found in languages like C,
those Rubin is quite unhappy about.

I am quite sure that a compiler can be implemented in Lisp/Scheme
macros. I am using "macro" here as 'procedure that is evaluated at
compile time, and whose function is to transform a piece of program into
something else'.  It need not be a mere syntax macro, say like in cpp.
If you are familiar with Lisp/Scheme, just consider the source and
effects of some common 'loop' macros -- to my poor tired eyes they look
like pieces of a compiler.

cjk> If the machine can do something, the user should be able to invent
cjk> a notation to do it, if necessary.  For example, I find the general
cjk> vector operation on the CYBER 205, with its dozen optional fields,
cjk> easy to explain in a notation easy to read and write.

Maybe Rubin is a bit rough in expression, but I think that he is trying
to say that he would dearly love to have extensible compilers, i.e.
compilers where the set of compile time procedures can be extended by the
user, i.e. the symbolic reduction engine is programmable. The "if
necessary" above does not refer to power, I guess, but to cost.

Well, maybe he should seriously consider Lisp/Scheme. It is well known
that they are excellently suited to numerical computations, and they
provide unparalleled access to the underlying implementation. Maybe a
look a T? Forth is another nice choice. Note that I am not joking here
-- I am very serious. I am considering writing myself an OS kernel in
Scheme or something similar rather than in C/C++. Scheme can be viewed
as a fairly good SIL, even if most Scheme systems do not implement it as
one (especially inasmuch memory management is concerned -- you don't
have the option of doing manual memory reclamation really).

norman> This is written as if you believe the 'power of the computer' resides
norman> in its instruction set. I disagree with this idea.

Interesting disagreement. So Peano arithmetic (zero, successor, test
against zero) is enough and everything else is redundant? Why are we not
using Turing machines? They are as powerful as anything else, and have
a pretty small instruction set.

norman> In fact, the whole RISC movement is founded on the idea that to
norman> build a faster computer you must _remove_ instructions from the
norman> instruction set.

Uhmmm. _must_? I don't think they see it as a necessity -- my own,
probably seriously wrong idea of the subject, is that the RISC movement
is about improving price/performance, not *power* (once you have got
Peano, you have got it all), by observing that it is _often_ a bad
investment to allocate your silicon budget to seldom used, complicated
instructions, but instead it gives better price/performance to allocate
it to speeding up the simpler, most frequently executed ones.

I don't think that this excludes that a RISC machine can have
complicated instructions (vide floating point), if the payoff is
sufficient.  So far the best known payoff for doing matrix computing is
in vector instructions, ergo they are RISCy :-). Or maybe I am no longer
current on this subject and I should agree that:

norman> Likewise, adding an instruction to a modern computer will not
norman> increase its computational power.

Or maybe you should reconsider -- try to remove vector instructions from
a Cray, if they let you. Indeed its power will not be diminished, as
long as Peano instructions are left in, but its price/performance ratio
may be another story, I guess. Or maybe you should reread Hennessy's and
Patterson's book to get a better idea of what is the RISC idea about
(the title gives away almost the whole story).

norman> I believe the 'power of the computer' resides in its ability to be
norman> used as an abstraction device on which we can build higher and higher
norman> levels of reality.

Here we fully agree. The reasons for which computers are so important
are that they are general purpose automata (abstraction engines), and
that they can be cost effective too. Leaving out the second aspect
brings us back to Babbage, I am afraid.

norman> Personally, I chose to live in a reality where
norman> lambda calculus is the underlying computational model.

We couldn't have guessed! :-). Most of us out here are instead in a
reality where they must pay for their machines, and are keenly
interested in price/performance ratios.

Rubin too is unfortunately locked in this sad and regrettable reality,
and also in a segment of it where absolute prices are so huge that
price/performance ratio of a machine/language combination seems not
easily dismissable.

He is quite annoyed that he cannot get the benefits of high level
languages without forgoing those of special purpose hw facilities that
substantially enhance the cost effectiveness of his work, and that also
carried a fairly large price tag (only a few million dollars, I guess,
that's the difference between the price of a 205 and that of a mainframe
of equivalent scalar power). He is even more annoyed as he suspects that
the problem could be rectified with just a little more effort on the
part of language designers and implementors.

norman> But by living in this level of reality I gain the ability to
norman> write extremely clear and straight-forward programs that are 10,
norman> 20, and sometimes even 30 times _shorter_ than the equivalent
norman> programs written in a typical high-level language.

Are you sure that your "programs" are equivalent? A lot of people
(including regrettably Prof. Dijkstra and Prof. Hoare) seem to have lost
sight of the distinction between what is a program and what is an
algorithm written in a program-like notation. A sort program, e.g.  UNIX
sort(1), is quite a different thing from a sort algorithm, e.g.
qsort(3).

My probably warped view of the programming scene is that the best known
general purpose language technology, applied under favourable
circumstances, seems (hand waving very prominently here) no more than
2-3 times more productive than mainstream language technology (Fortran,
Cobol, C, PL/1); claims to the contrary make me a bit skeptical. Now I
admit that even 200-300% is a lot, in economic terms, but it pales by
comparison with the different productivity levels of *people*.
--
Piercarlo "Peter" Grandi           | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth        | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk