🚀 go-pugleaf

From article <PCG.90Sep23181145@teachc.cs.aber.ac.uk>:

Here are the players:
pcg>     Piercarlo Grandi  <pcg@cs.aber.ac.uk>
cik>     Herman Rubin      <cik@l.cc.purdue.edu>
norman>  Norman Graham     <norman@d.cs.okstate.edu>

norman> First, as anyone with a basic knowledge of languages can tell you,
 
pcg> I am somehow under the impression that Rubin understands languages
pcg> better than somebody that gives much importance to syntax. A recent book
pcg> on language implementation maps many disparate languages into a simple
pcg> lisp/like syntax, with no great loss.

This sounds like denotational semantics to me. So programs written in
one language can be translated into another language; what's you point?
 
norman> a language is a set of strings (of finite but arbitrary length)
norman> over some alphabet.
 
pcg> Well, that is the syntax of the language -- essentially irrelevant,
pcg> except for pragmatics. If this were literally true, yacc would be all we
pcg> need for writing compilers. But:

While syntax is certainly arbitrary (for the most part), it certainly
is not irrelevant: Syntax defines what strings of symbols are valid
programs (i.e. syntax defines the language and the language is a set
of strings of symbols). Without a syntatic definition, how can our
comptilers know the difference between a correct program and an errant
one? [Aside. I'm sure you're aware that Yacc can't handle the syntax
of many programming languages.]

On the other hand, I agree that syntactic issues are, as a rule, boring.
And, of course, syntax says nothing about what a program means.
 
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.
 
pcg> Uhhhmmmm. Here we seem to be describing some branch of mathematics
pcg> instead -- a fairly common idea.  Computer languages exist for pragmatic
pcg> reasons. Otherwise we'd be using lambda calculus or Turing machines. I
pcg> used to think, erroneously I now understand, that computer languages are
pcg> not there to describe computations; they are there for supporting an
pcg> engineering like activity, in which expressing computations is a fairly
pcg> small part of the whole picture. [ ... ]

Well, you've confused me here: Do you agree or disagree with me.
I believe you meant to disagree, but an extra 'not' got in the way. :-)

I will not disagree with your assertion that computer language exist
for pragmatic reasons. However, I will stand by my original statement:
Programs are abstract specifications of computation--not abstract
specifications of sequences of machine instructions. [Here, I'm 
writing of the general case, not of special or assembly languages.]

Of course, describing computations is only a small part of what a
programmer/software engineer does, but this is beside the point.
 
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.
 
pcg> I would dearly hope they do. Actually I would hope they are *prominent*.
pcg> I would venture as far as saying that the machine is the reason for
pcg> which the language exists. [ ... ]

I'm afraid you mistook my intent here. I was speaking of the way
the von Neumann machine influences the imperative languages, or the
way the lambda calculus influences the functional languages, etc. 
The underlying computational model influences language design and 
thus programming style. [And yes, there is some hope that novel
languages will influence machine design.]

If we had to rely solely on the physical machine for our ideas of
language design, I'm afraid we would be stuck with increasingly 
baroque or specialized languages.
 
norman> Second, it is simply naive to describe what a compiler does as
norman> macro expansion.

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

Actually, I had forgotten about Lisp/Scheme macros. Yes you can
implement a translator from a (user defined) language to Lisp/Scheme
with macros. But this does not mean that compilers, in general,
are macro expanders, which was Rubin's original assertion.
Certainly languages are not collections of macros, as Rubin 
also asserted. [But, of course, a translator may be a collection
of macros.]
 
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.
 
pcg> Maybe Rubin is a bit rough in expression, but I think that he is trying
pcg> to say that he would dearly love to have extensible compilers, i.e.
pcg> compilers where the set of compile time procedures can be extended by the
pcg> user, i.e. the symbolic reduction engine is programmable. The "if
pcg> necessary" above does not refer to power, I guess, but to cost.
pcg> 
pcg> Well, maybe he should seriously consider Lisp/Scheme. It is well known
pcg> that they are excellently suited to numerical computations, and they
pcg> provide unparalleled access to the underlying implementation. Maybe a
pcg> look a T? Forth is another nice choice. Note that I am not joking here
pcg> -- I am very serious. I am considering writing myself an OS kernel in
pcg> Scheme or something similar rather than in C/C++. Scheme can be viewed
pcg> as a fairly good SIL, even if most Scheme systems do not implement it as
pcg> one (especially inasmuch memory management is concerned -- you don't
pcg> have the option of doing manual memory reclamation really).

So, what you're saying is that Ruben should invent his own language
and write translators for that language in Lisp/Scheme macros. Yes
this is possible--I've heard of a macro package for Common Lisp
that implements an Algol-like language.
 
norman> This is written as if you believe the 'power of the computer' resides
norman> in its instruction set. I disagree with this idea.
 
pcg> Interesting disagreement. So Peano arithmetic (zero, successor, test
pcg> against zero) is enough and everything else is redundant? Why are we not
pcg> using Turing machines? They are as powerful as anything else, and have
pcg> a pretty small instruction set.

Well, I'm sure you know we can't build Turing machines. :-)

Let me clarify my position here: While the 'power' of the computer
does not reside in its instruction set, the efficiency and practicality
of the computer does.
 
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.
 
pcg> Uhmmm. _must_? I don't think they see it as a necessity -- my own,
pcg> probably seriously wrong idea of the subject, is that the RISC movement
pcg> is about improving price/performance, not *power* (once you have got
pcg> Peano, you have got it all), by observing that it is _often_ a bad
pcg> investment to allocate your silicon budget to seldom used, complicated
pcg> instructions, but instead it gives better price/performance to allocate
pcg> it to speeding up the simpler, most frequently executed ones.
pcg> 
pcg> I don't think that this excludes that a RISC machine can have
pcg> complicated instructions (vide floating point), if the payoff is
pcg> sufficient.  So far the best known payoff for doing matrix computing is
pcg> in vector instructions, ergo they are RISCy :-). [ ... ]

Quite correct. I didn't mean to imply otherwise.

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.
 
pcg> Here we fully agree. The reasons for which computers are so important
pcg> are that they are general purpose automata (abstraction engines), and
pcg> that they can be cost effective too. Leaving out the second aspect
pcg> 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.

pcg> We couldn't have guessed! :-).

Oops, my rhetoric gave me away :-)

pcg> Most of us out here are instead in a
pcg> reality where they must pay for their machines, and are keenly
pcg> interested in price/performance ratios.
pcg> 
pcg> Rubin too is unfortunately locked in this sad and regrettable reality,
pcg> and also in a segment of it where absolute prices are so huge that
pcg> price/performance ratio of a machine/language combination seems not
pcg> easily dismissable.
pcg> 
pcg> He is quite annoyed that he cannot get the benefits of high level
pcg> languages without forgoing those of special purpose hw facilities that
pcg> substantially enhance the cost effectiveness of his work, and that also
pcg> carried a fairly large price tag (only a few million dollars, I guess,
pcg> that's the difference between the price of a 205 and that of a mainframe
pcg> of equivalent scalar power). He is even more annoyed as he suspects that
pcg> the problem could be rectified with just a little more effort on the
pcg> part of language designers and implementors.

And I can emphathise with his plight.

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.
 
pcg> Are you sure that your "programs" are equivalent? [...]

Right. I should have written "comperable" or "similar" rather than
"equivalent".
-- 
Norman Graham   <norman@a.cs.okstate.edu>   {cbosgd,rutgers}!okstate!norman
The opinions expressed herein do not necessarily reflect the views of
the state of Oklahoma, Oklahoma State University, OSU's Department of
Computer Science, or of the writer himself.