Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!wuarchive!julius.cs.uiuc.edu!apple!uokmax!d.cs.okstate.edu!norman From: norman@d.cs.okstate.edu (Norman Graham) Newsgroups: comp.lang.misc Subject: Re: Multi-compilers Message-ID: <1990Sep23.221951.21697@d.cs.okstate.edu> Date: 23 Sep 90 22:19:51 GMT References: Organization: Oklahoma State University Lines: 210 From article : Here are the players: pcg> Piercarlo Grandi cik> Herman Rubin norman> Norman Graham 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 {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.