cik@l.cc.purdue.edu (Herman Rubin) (07/26/90)
In article <1990Jul26.024449.1777@esegue.segue.boston.ma.us>, johnl@esegue.segue.boston.ma.us (John R. Levine) writes: > In article <58091@lanl.gov> jlg@lanl.gov (Jim Giles) writes: > >Well yes, ALGOL _has_ had an enormous _negative_ impact on language > >design (that still continues today). Features like 'call-by-name' are > >now recognized as bad by nearly everyone. > > Alan Perlis, who was on the Algol committee, once told me that when they > defined call-by-name, they thought they were defining call-by-reference > more elegantly. When Jensen invented his now-notorious device and they > realized what they had created, they were as surprised as anyone. Oops. > > >In fact, only two features, that I can find, are original to ALGOL and > >have a continuing positive influence on language design: if-then-else > >and while(). > > How about nested scopes and recursion? I find them handy from time to time. Nested scopes of DO loops are present in Fortran. Mathematicians have used recursion for ages, and the problems with implementing recursion in the architecture of the time were horrendous. Frankly, some of them still are. What language allows carrying globals in registers across recursion? One of the things which should be noted was that, at the time, registers were few and transfer and memory access were relatively fast compared with computation. Nobody would have considered the above question of any importance. Self-modifying code was a necessity, and even a decade later, the return jump (subroutine call) automatically did so. > I'd also be interested to hear what about compound statements (by which I > presume you mean BEGIN ... END blocks) is bad, and whether the Algol 68 > approach in which every control structure has its own closing word, obviating > begin and end, is any better. I do not see IF and FI as any better than BEGIN and END. Better would be to have labels (including temporary labels not going into the symbol table) and end statements which would carry the label. The END statement, even without a BEGIN statement, was in common use at the time; All processors need to know when to stop. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (Internet, bitnet) {purdue,pur-ee}!l.cc!cik(UUCP)
art@cs.bu.edu (Al Thompson) (07/27/90)
In article <2406@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: |In article <1990Jul26.024449.1777@esegue.segue.boston.ma.us>, johnl@esegue.segue.boston.ma.us (John R. Levine) writes: |> In article <58091@lanl.gov> jlg@lanl.gov (Jim Giles) writes: [...] |> |> How about nested scopes and recursion? I find them handy from time to time. | |Nested scopes of DO loops are present in Fortran. Scope, as in the sense of variables visible only from within the loop? Is this what you meant? Algol had a feature in which local data could be declared local to any begin end pair. Thus the compound statement in Algol would resemble a procedure except it had no parameters and could not be called elsewhere. Mathematicians have used |recursion for ages, and the problems with implementing recursion in the |architecture of the time were horrendous. Frankly, some of them still are. |What language allows carrying globals in registers across recursion? How is carrying globals in registers across recursion a language issue? It's an implementation issue. Whether you can do it or not is a function of the cleverness of the compiler writer and the architecture upon which it is implemented. | |One of the things which should be noted was that, at the time, registers |were few and transfer and memory access were relatively fast compared with |computation. The world's first commercial Algol machine (the Burroghs B5000 and derivatives) didn't have any registers, at least none visible to the user.
philip@pescadero.Stanford.EDU (Philip Machanick) (07/27/90)
In article <2406@l.cc.purdue.edu>, cik@l.cc.purdue.edu (Herman Rubin) writes: > In article <1990Jul26.024449.1777@esegue.segue.boston.ma.us>, johnl@esegue.segue.boston.ma.us (John R. Levine) writes: > > How about nested scopes and recursion? I find them handy from time to time. > > Nested scopes of DO loops are present in Fortran. Mathematicians have used > recursion for ages, and the problems with implementing recursion in the > architecture of the time were horrendous. Frankly, some of them still are. > What language allows carrying globals in registers across recursion? "Nested scopes" refers to the ability to define local names within one compilation unit. DO loops do not introduce "scope". Recursion is a problem if an architecture doesn't have a built in stack - not an issue on modern architectures. Why? Because language design required an efficient stack. Other more esoteric mechanisms like hardware displays to access non-local variables haven't paid off as much, and so are not in common use. "globals in registers across recursion"? How many _compilers_ manage registers across _any_ procedure calls? (Just asking.) Philip Machanick philip@pescadero.stanford.edu
preston@erato.rice.edu (Preston Briggs) (07/27/90)
In article <1990Jul26.171822.7193@Neon.Stanford.EDU> philip@pescadero.stanford.edu writes: >"globals in registers across recursion"? How many _compilers_ manage >registers across _any_ procedure calls? (Just asking.) Well, the MIPS compilers do some interprocedural register allocation. HP has also done experiments with a system to keep globals in registers across calls. The HP work is described in the most recent Proceedings of the Conference on Programming Language Design and Implementation. These tricks are all pretty difficult in the presence of seperate compilation, and the successful solutions will have to solve the problem. -- Preston Briggs looking for the great leap forward preston@titan.rice.edu
bengtl@maths.lth.se (Bengt Larsson) (07/27/90)
In article <2406@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: >In article <1990Jul26.024449.1777@esegue.segue.boston.ma.us>, johnl@esegue.segue.boston.ma.us (John R. Levine) writes: >> How about nested scopes and recursion? I find them handy from time to time. > >Nested scopes of DO loops are present in Fortran. Mathematicians have used Really, Mr Rubin. If you think that nested DO loops in Fortran have anything to do with the nested scopes of (for example Algol, Pascal, Ada), you apparantly don't know what you are talking about. (It is the _block structure_ that is important (several levels of declarations in different scopes). A nested DO loop is, as far as I can see, exactly equivalent to a nested loop in assembler. A nested scope in an Algol-like language is something completely different.) >recursion for ages, and the problems with implementing recursion in the >architecture of the time were horrendous. Frankly, some of them still are. Yes, of course some architectures made (make??) it somewhat difficult to have recursive procedures (the ones that stored the return adress in the first word of the subroutine comes to mind). You can write recursive programs in standard Fortran, but you will have to manage the activation stack yourself. This will certainly not be pretty (compare this with the ease of doing recursive procedures in Algol) >What language allows carrying globals in registers across recursion? I think you are over-concerned about keeping everything in registers. This is a very low-level view, and has almost nothing to do with the advantages/disadvantages (from a software engineering standpoint) of nested scopes as introduced by Algol. >One of the things which should be noted was that, at the time, registers >were few and transfer and memory access were relatively fast compared with >computation. Nobody would have considered the above question of any >importance. Self-modifying code was a necessity, and even a decade later, >the return jump (subroutine call) automatically did so. > >> I'd also be interested to hear what about compound statements (by which I >> presume you mean BEGIN ... END blocks) is bad, and whether the Algol 68 >> approach in which every control structure has its own closing word, obviating >> begin and end, is any better. > >I do not see IF and FI as any better than BEGIN and END. Better would be >to have labels (including temporary labels not going into the symbol table) >and end statements which would carry the label. The END statement, even >without a BEGIN statement, was in common use at the time; All processors >need to know when to stop. It seems you haven't heard about Ada. In Ada, different constructs (loops and blocks come to mind) may have labels. Like: MAIN_LOOP: loop -- stuff SUB_LOOP: loop -- more stuff exit MAIN_LOOP; -- exit 2 levels of loop end loop SUB_LOOP; end loop MAIN_LOOP; If a loop is started by a label and a ":", the same label must be repeated after "end loop". The "exit" statement by default exits one level of loops, it may also exit to a named level, as in the example. All constructs have their own (two word) delimiter, like: if A < B then -- something end if; case MYVAR is when 1 => DO_1; when others => null; end case; select -- end select; Even if Ada isn't best at everything, I think they got the syntax right. I like "if then else end if" better than "if then begin end else begin end". -- Bengt Larsson - Dep. of Math. Statistics, Lund University, Sweden Internet: bengtl@maths.lth.se SUNET: TYCHE::BENGT_L
carroll@udel.edu (Mark Carroll <MC>) (07/27/90)
In article <2406@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: ]> ]> How about nested scopes and recursion? I find them handy from time to time. ] ]Nested scopes of DO loops are present in Fortran. Mathematicians have used ]recursion for ages, and the problems with implementing recursion in the ]architecture of the time were horrendous. Frankly, some of them still are. ]What language allows carrying globals in registers across recursion? ] I'm sure that everyone and his brother is going to jump on you for this, but I'll join the bandwagon. This post is SO full of blatant proofs that you know very little about language design. I don't mean to turn this into a personal attack - but I really think that perhaps, as a statistician, you should realize that you aren't an expert on computer language design. Anyway, the really big error in the above quoted paragraph is the statement "Nested scopes of DO loops are present in Fortran." I don't think you understand what we mean by nested scopes. A scope is the region across which a variable declaration or binding is valid. In Fortran code, within the main program, a variable is either declared or not, for the entire body of the main program, that is, the scope of any variable in the main program is the entire main program. Now, to show you a nested scope, I'll jump into C: { int i=<expr>; int j=<expr>; ..code section 1.. while (i<j) { int k; ..code section 2.. } ..code section 3.. } This code fragment contains two scopes: the outer scope where i and j are declared, and an inner scope, where k is declared. The scope of variables i and j are code sections 1,2, and 3. The scope of k is only section 2. The scope of section 2 is a nested scope. Why do we consider this useful? Since k is only used inside of the body of the while loop, we'd like to have it only defined there, so that it can't be accessed outside of the loop. (Things can get better in C++ and Ada, where loop indexes can be scoped only for the body of the loop, so that the programmer can't use the (unpredictable) post-exit value of the loop index.) The other major problem in the quoted section in your remark about the fact that recursion was hard to implement. The purpose of programming languages is to allow you to simply express operations that would be extremely difficult to express on the real architecture. A technique like recursion is incredibly useful - to disallow using it in a supposedly general programming language would be foolish. My personal problem with this whole discussion is that I think we want different things from a programming language. What you're looking for in a language is a fancy macro assembler. Personally, I have no interest in that. What I look for in languages is a way to express my algorithm in a model of computation that is different from the underlying architecture of my machine. If it less efficient than it would be in assembler, I don't particularly care. I'm not looking for speed - I'm looking for the best way to express my algorithm in a natural way. I like object-oriented programming languages for certain jobs, because they let me express the relationships between the objects that I am manipulating in a natural way. For other jobs, I like a language like C, which is almost a portable assembly language. For yet other jobs, I like a functional language, because they provide me with a clean way of expressing certain kinds of mathematical relationships. A language provides with a clean expressive mechanism that is independant of my underlying architecture. That's not always what I want - sometimes I need to be close to the architecture. But the fact that I'm not close to the architecture is NOT a flaw in the language I'm using - it's a feature of the language! Finally, on the comment about compilers including global variables in registers accross recursions - I could recommend some good papers about interprocedural register allocation that talk about compilers that can do exactly that - and more. <MC> -- |Mark Craig Carroll: <MC> |"We the people want it straight for a change; |Soon-to-be Grad Student at| cos we the people are getting tired of your games; |University of Delaware | If you insult us with cheap propaganda; |carroll@dewey.udel.edu | We'll elect a precedent to a state of mind" -Fish
ergo@netcom.UUCP (Isaac Rabinovitch) (07/27/90)
In <2406@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: >In article <1990Jul26.024449.1777@esegue.segue.boston.ma.us>, johnl@esegue.segue.boston.ma.us (John R. Levine) writes: >> In article <58091@lanl.gov> jlg@lanl.gov (Jim Giles) writes: >> >> >In fact, only two features, that I can find, are original to ALGOL and >> >have a continuing positive influence on language design: if-then-else >> >and while(). >> >> How about nested scopes and recursion? I find them handy from time to time. >Nested scopes of DO loops are present in Fortran... I think maybe John was talking about lexical scope of symbols. If he wasn't, he should have been. I'd hate to program in a language that requires *every* variable in a program to be lexically distinct! If you're gonna be that primitive, you might as well give up on symbols and go back to machine language! Then again, LISP might've had this sort of thing before ALGOL. But the way LISP defines such things is to computing as mathematical logic is to "1+1=2"! You have to get away from all the great abstract theories before an idea can be useful in the real world. >I do not see IF and FI as any better than BEGIN and END. Better would be >to have labels (including temporary labels not going into the symbol table) >and end statements which would carry the label. The END statement, even >without a BEGIN statement, was in common use at the time; All processors >need to know when to stop. Again, you seem to be responding to a point that wasn't made. If the only purpose of END was to terminate a program, then it became obsolete as soon as OSs came up with a standard End-of-File indicator! BEGIN and END are for *grouping* statements *within* a program. It's been a long time since I programmed in FORTRAN, but I'm quite sure it had nothing of the kind, under that or any other name. >-- >Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 >Phone: (317)494-6054 >hrubin@l.cc.purdue.edu (Internet, bitnet) {purdue,pur-ee}!l.cc!cik(UUCP) -- ergo@netcom.uucp Isaac Rabinovitch atina!pyramid!apple!netcom!ergo Silicon Valley, CA uunet!mimsy!ames!claris!netcom!ergo "I hate quotations. Tell me what you know!" -- Ralph Waldo Emerson
preston@titan.rice.edu (Preston Briggs) (07/27/90)
In article <11052@netcom.UUCP> ergo@netcom.UUCP (Isaac Rabinovitch) writes: (about nested scopes...) >Then again, LISP might've had this sort of thing before ALGOL. My first reaction was "Nah...", but then I checked a little. I looked in a book called "History of Programming Languages", edited by Wexelblat. It's the proceedings of the ACM SIGPLAN History of Programming Languages Conference, 1978. It's a very cool book. Basically they invited a couple of people who participated in the early development of particular languages (I mean "2 people per language") to submit papers and give talks on what really happened and who did what. The book collects the papers, transcriptions of the talks, questions and replies, plus pictures. Anyway... In McCarthy's paper about Lisp, he says the 1st interpreter appeared sometime in late 1958 or early 1959. The 1st paper was in CACM, in 1960. Titled "Recursive functions of symbolic expressions and their computation by machine, part 1" (there is no part 2). Algol 58 apparently did not have nested scopes, though they did have compound statements (begin-end blocks). Algol 60 had both. Of course, this is all complicated because McCarthy was also on the Algol Committee. He was apparently fairly disgusted with the whole thing, suggesting that the meatings deteriorated into "we'll put your good idea in, if you'll put my good idea in". McCarthy's ideas included conditional expressions and recursion. (I'm not saying he invented recusion! He proposed that they be included in Algol 60.) In Naur's paper, he lists specific dates and author's for all the different proposals leading from Algol 58 to Algol 60. The relevant ideas seem to spring from prosals made by Ehrling (Sept. 15, 1959), Samelson (Oct. 1959), and Wijngaarden and Dijkstra (October 1959). In November 1959, in Paris, a subcommittee meeting (Dijkstra, Landin, Naur) recommened that these ideas be seriously considered. In December, in Mainz, a general meeting of the European representatives produced a proposal that included the modern form of compound statement, with nested declarations. Apparently, reaction in the US to Algol 58 was more concerned with I/O than with control of scoping and such. The Algol section is one of the most interesting in the book. It's interesting (to me) how much bad blood exists today because of the Algol 60 committee. Letters reprinted in various appendices made it clear that many of the committee members were seriously unhappy with the language. So, I dunno about Lisp vs. Algol. We can settle and say that Church invented nested scopes as part of the lambda calculus. Read the book! It's a blast. Languages covered: Algol, Apl, Apt, Basic, Cobol, Fortran, Gpss, Joss, Jovial, Lisp, PL/1 (or is it PL/I? Read!) Simula, and Snobol. -- Preston Briggs looking for the great leap forward preston@titan.rice.edu
peter@ficc.ferranti.com (Peter da Silva) (07/27/90)
In article <2406@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: > What language allows carrying globals in registers across recursion? Any language. All that is required is a good inter-procedural optimiser. That's an implementation detail, not a language feature. -- Peter da Silva. `-_-' +1 713 274 5180. 'U` <peter@ficc.ferranti.com>
irv@happym.wa.com (Irving Wolfe) (07/29/90)
In <10284@brazos.Rice.edu> preston@titan.rice.edu (Preston Briggs) writes: >I looked in a book called "History of Programming Languages", >edited by Wexelblat. It's the proceedings of the ACM SIGPLAN >History of Programming Languages Conference, 1978. >It's a very cool book. These talks are available on tape, and almost all of them are great. I got them years ago, and don't remember the ordering details, but ACM sells the tapes as a set. They are _much_ better than the Turing Award tapes, some of which are absolutely awful (50% plugs for the speaker's and his friends' latest books, 50% beyond comprehension except to the handful of scholars in his field). Apparently, the IQ, public-spiritedness, and delightful spirit of language originators far exceed those of the "typical" top-notch computer scientist. Anyway, these HOPL tapes are great, and well worth the money. The only one I've heard recently was Ralph Griswold's SNOBOL tape, which enlivened one of my recent ferry trips to the mainland, but I remember almost all of them fondly. -- Irving Wolfe Happy Man Corp. irv@happym.wa.com 206/463-9399 ext.101 4410 SW Point Robinson Road, Vashon Island, WA 98070-7399 SOLID VALUE, the investment letter for Benj. Graham's intelligent investors Information (not sample) free: email patty@happym.wa.com with US mail addr.
seanf@sco.COM (Sean Fagan) (07/29/90)
In article <1990Jul27.010930.12560@lth.se> bengtl@maths.lth.se (Bengt Larsson) writes: >Yes, of course some architectures made (make??) it somewhat difficult >to have recursive procedures (the ones that stored the return adress in >the first word of the subroutine comes to mind). "somewhat more difficult." That's *all*. The CDC Cyber 170 machines (of which most people know I am a big fan 8-)) have no stack, and, on a subroutine call, write an instruction into the first word of the subroutine ("jump <retaddr>," basicly). Yet: Pascal was developed on this machine (literally! Wirth used a Cyber for the first implementation of Pascal). Algol and Simula run quite well on it. So does PL/I (although the compiler eats up all of memory 8-)). There are even a couple of C compilers out there, I've been told. No, it's not as fast. The only reason you don't really want to do it on a Cyber is memory space: stacks can eat up *lots* of memory, and 170's only have 128Kwords of memory. On most "modern" machines, this is less a problem (but, then, most of them have a stack). Incidently: Crays stuff the return address into a register, which your routine can then save if it wants to (leaf routines, of course, don't need to save it). -- Sean Eric Fagan | "let's face it, finding yourself dead is one seanf@sco.COM | of life's more difficult moments." uunet!sco!seanf | -- Mark Leeper, reviewing _Ghost_ (408) 458-1422 | Any opinions expressed are my own, not my employers'.
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (07/29/90)
In article <1990Jul27.010930.12560@lth.se> bengtl@maths.lth.se (Bengt Larsson) writes: > In article <2406@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: > >I do not see IF and FI as any better than BEGIN and END. Better would be > >to have labels (including temporary labels not going into the symbol table) > >and end statements which would carry the label. The END statement, even > >without a BEGIN statement, was in common use at the time; All processors > >need to know when to stop. > It seems you haven't heard about Ada. [ surveys the Ada control structures ] Q does the job better. The syntax and semantics of control structures are actually rather complex, and I'm still putting together a series of four articles to describe them, but here are several syntactic features: The basic form for control structure foo is foo <some statements> end. The end can be specified, as in endfoo. The foo and end can be labelled, as in foo:main ... end:main. fi is a standard abbreviation for endif. Actually, control structures may include additional words: the form of an if statement, for example, is if(C) D [anyway] E fi. Here anyway is a keyword, which may have labels like if and fi; it is a once-at-most keyword, with default position just before the fi. A nonexistent label is taken as the empty label, or the label of the previous word in the same structure if that is applicable. else is a standard abbreviation for ``break anyway''; here break is the simplest example of an even more flexible syntax for exiting a control structure. This is just one example of how redundant control structures are replaced by macros. > In Ada, different constructs (loops and blocks come to mind) may have labels. > Like: > > MAIN_LOOP: loop > -- stuff > SUB_LOOP: loop > -- more stuff > exit MAIN_LOOP; -- exit 2 levels of loop > end loop SUB_LOOP; > end loop MAIN_LOOP; loop:MAIN /// stuff loop:SUB /// more stuff break^2; /// or breakloop:MAIN, or breakloop^2, or break:MAIN, or ... end; /// or endloop, or end:SUB, or pool, or endloop:SUB, or ... end; I find the Q version much more readable. (Okay, the semicolons aren't necessary. Shame on me.) > If a loop is started by a label and a ":", the same label must be repeated > after "end loop". Which is bad. The programmer shouldn't be forced into this style. Q does require that the labels match, but as explained above it will assume the loop label if the end label isn't provided. > The "exit" statement by default exits one level of loops, > it may also exit to a named level, as in the example. Q's breaking is nicer. (Note that Q's break doesn't distinguish between if, loop, switch, or any other structures. This greatly simplifies the semantics, and of course would have prevented the AT&T crash a few months back. [grin]) > All constructs have their own (two word) delimiter, like: > if A < B then > -- something > end if; Which is another annoyance. The programmer should be allowed to type just end. > Even if Ada isn't best at everything, I think they got the syntax right. Ada is best at nothing. Syntax is no exception. > I like "if then else end if" better than "if then begin end else begin end". Yes. There are many studies showing that explicitly terminated blocks are easier to write, reduce errors, are easier to read, etc. ---Dan
cik@l.cc.purdue.edu (Herman Rubin) (07/29/90)
In article <25767@nigel.udel.EDU>, carroll@udel.edu (Mark Carroll <MC>) writes: > In article <2406@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: > ]> > ]> How about nested scopes and recursion? I find them handy from time to time. ........................ > I'm sure that everyone and his brother is going to jump on you for this, > but I'll join the bandwagon. This post is SO full of blatant proofs that > you know very little about language design. I certainly misunderstood what was said. As for nested scopes, I have used them when available, and I have no difficulty with the concept or the implementation. I find it somewhat annoying that assemblers do not make better use of it. As I said, I misunderstood the terminology. As for language design, I am certainly not an expert. But I do not object when those consulting me ask for something the standard statistical procedures cannot deliver. The statistical packages are as limited as the HLLs. ...................... > The other major problem in the quoted section in your remark about the fact > that recursion was hard to implement. The purpose of programming languages > is to allow you to simply express operations that would be extremely difficult > to express on the real architecture. A technique like recursion is incredibly > useful - to disallow using it in a supposedly general programming language > would be foolish. Recursion still is hard to implement. There are situations where plopping everything on the stack is a good way, and situations in which this is horrible, and managing memory blocks is a better idea. Without guidance from the programmer, the compiler will not know which. However, I do not believe that recursion, nor anything else, should be left out of the language. If you look at my complaints, they are not that things are in the language, but that things are not in the language ! My personal problem with this whole discussion is that I think we want different ! things from a programming language. What you're looking for in a language ! is a fancy macro assembler. Personally, I have no interest in that. What I ! look for in languages is a way to express my algorithm in a model of ! computation that is different from the underlying architecture of my machine. ! If it less efficient than it would be in assembler, I don't particularly care. ! I'm not looking for speed - I'm looking for the best way to express my ! algorithm in a natural way. I like object-oriented programming languages ! for certain jobs, because they let me express the relationships between the ! objects that I am manipulating in a natural way. For other jobs, I like a ! language like C, which is almost a portable assembly language. For yet ! other jobs, I like a functional language, because they provide me with ! a clean way of expressing certain kinds of mathematical relationships. ! A language provides with a clean expressive mechanism that is independant ! of my underlying architecture. That's not always what I want - sometimes ! I need to be close to the architecture. But the fact that I'm not close ! to the architecture is NOT a flaw in the language I'm using - it's a ! feature of the language! I have never stated that languages must insist on efficiency, but that they are capable of it. If you do not wish to use a feature of the language, and you can get along without it, by all means I do not intend to force you. You say you sometimes want this, and sometimes that, and sometimes the other. I want all of this, and more, at the same time. If, for example, C does a good job of expressing the structural considerations in an algorithm, an optimizing C compiler may do well. But if it does not consider relevant aspects, it will not do well. And I do use programming constructs which are very clumsy in the HLLs I have seen, but simple from a mathematical point of view. You like an object-oriented language, and you like a functional language. Why not combine everything? It is not so much a problem for the language designer as for the compiler writer. In addition, I find the architectures simpler than the HLLs. It is not true that Algol has all the primitive operators for numerical calculation in its list of operators. It is true that it has enough that one can define any other, but this is like saying that the way that multiplication should be perforemed is by squaring the sum and the difference, subtracting, and shifting right two bits. The compiler may very well miss what I see, and vice versa. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (Internet, bitnet) {purdue,pur-ee}!l.cc!cik(UUCP)
gillett@ceomax..dec.com (Christopher Gillett) (07/30/90)
In article <1990Jul28.185054.2595@sco.COM> seanf@sco.COM (Sean Fagan) writes: >In article <1990Jul27.010930.12560@lth.se> bengtl@maths.lth.se (Bengt Larsson) writes: >>Yes, of course some architectures made (make??) it somewhat difficult >>to have recursive procedures (the ones that stored the return adress in >>the first word of the subroutine comes to mind). > >"somewhat more difficult." That's *all*. > >The CDC Cyber 170 machines (of which most people know I am a big fan 8-)) >have no stack, and, on a subroutine call, write an instruction into the >first word of the subroutine ("jump <retaddr>," basicly). > >Yet: Pascal was developed on this machine (literally! Wirth used a Cyber >for the first implementation of Pascal). Algol and Simula run quite well on >it. So does PL/I (although the compiler eats up all of memory 8-)). There >are even a couple of C compilers out there, I've been told. Hmmm. The Cyber 170's were *soooo* cool. Personal bias: I learned tons 'o stuff hacking on a 170/730D running NOS2.1 whilst in school. The systems guys who looked after the machine really taught me a lot. Anyways, I've seen the Pascal compiler (ETH Zurich) in source for this machine. It's an interesting read. My big question though: who does C compilers for this machine? Are they produced by CDC, or through a 3rd party. Putting a C compiler on one of those suckers had to have been a *really* nasty job, especially since NOS (at least back then) tended to regard users who wanted to use real upper/lower case ASCII as 2nd class citizens. I disagree with you about PL/I for these machines. PL/I was an intolerable pain, terribly slow, and not even a good subset G implementation. Pascal was done very well though. Semi-serious question: Does anybody know where you can buy these old machines? My alma mater sold theres for scrap for around $5,000. We were all bummed out, because we nearly bid for it, but figured that it would go for 10-20K. Anyways, if I found one selling at junk prices..... Of course, the 440 Volt 3 phase power requirements (not to mention the water cooling) would make it difficult to operate. :-) Oops, sorry. I'm off the subject. Maybe we should direct followups to comp.dinosaurs :-). Talk of Cybers makes my little techo-heart go pitter-pat (or is that "blip-blip" :-) ). >Sean Eric Fagan | "let's face it, finding yourself dead is one /Chris --- Christopher Gillett gillett@ceomax.dec.com Digital Equipment Corporation {decwrl,decpa}!ceomax.dec.com!gillett Hudson, Taxachusetts (508) 568-7172
jack@cs.glasgow.ac.uk (Jack Campin) (07/30/90)
preston@titan.rice.edu (Preston Briggs) wrote: > So, I dunno about Lisp vs. Algol. We can settle and say that > Church invented nested scopes as part of the lambda calculus. You get them in the predicate calculus too. So they must date back to Frege's "Begriffschrift" of around 1879. Maybe a bit of digging could unearth a similar analysis of names in mediaeval Arabic or Scholastic logic. In fact the nearest thing visually to an Algol block-structured program is a Fitch natural deduction proof for predicate logic (the "flags" introduced on subproofs for E-elimination or A-introduction are local variables with lexical scoping). These were presented in Fitch's elementary logic textbook of the early 50s; he must have invented the notation over ten years before that. In fact the similarity to Algol is so close I can't believe the Algol committee thought the idea up independently. -- -- Jack Campin Computing Science Department, Glasgow University, 17 Lilybank Gardens, Glasgow G12 8QQ, Scotland 041 339 8855 x6044 work 041 556 1878 home JANET: jack@cs.glasgow.ac.uk BANG!net: via mcsun and ukc FAX: 041 330 4913 INTERNET: via nsfnet-relay.ac.uk BITNET: via UKACRL UUCP: jack@glasgow.uucp
carroll@udel.edu (Mark Carroll <MC>) (07/30/90)
In article <2417@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: ]In article <25767@nigel.udel.EDU>, carroll@udel.edu (Mark Carroll <MC>) writes: ] ]As for language design, I am certainly not an expert. But I do not object ]when those consulting me ask for something the standard statistical procedures ]cannot deliver. The statistical packages are as limited as the HLLs. ] But you would object if people asked you for something which didn't really make sense in the context of statistics. "Hey, Herman, your stats package doesn't provide a recurrence relation solver - could you hack one up for me?" - what would you think of a person who asked you that? ] ]Recursion still is hard to implement. There are situations where plopping ]everything on the stack is a good way, and situations in which this is ]horrible, and managing memory blocks is a better idea. Without guidance ]from the programmer, the compiler will not know which. ] Can't it? I believe that I know some folks who would strongly disagree with you. Static compile-time analysis is improving every day, and there is nothing about recursion that is so horribly difficult. An intelligent compiler that tracks dataflow can certainly decide which way to implement a recursion. ]You say you sometimes want this, and sometimes that, and sometimes the other. ]I want all of this, and more, at the same time. If, for example, C does a ]good job of expressing the structural considerations in an algorithm, an ]optimizing C compiler may do well. But if it does not consider relevant ]aspects, it will not do well. And I do use programming constructs which ]are very clumsy in the HLLs I have seen, but simple from a mathematical ]point of view. ] ]You like an object-oriented language, and you like a functional language. ]Why not combine everything? It is not so much a problem for the language ]designer as for the compiler writer. ] What you're asking for doesn't even make good sense. Yes, I like oo languages. And I like functional languages. But combine them? It doesn't make good sense. A program in any language is a description of a machine. The language that you use determines what kind of machine your program is describing. In an Algol like language, you're basically modelling a vonNeumann machine. In Smalltalk or Self, you're modeling a message-passing machine. In Haskell, you're modeling a machine that does lambda calculus expansion. The models don't necessarily mix. If I mix the message-pass model of Smalltalk, and the functional model of Haskell, I end up with a monstrosity that destroys that attractive features of both! In a big way, the thing that makes Smalltalk so good at solving certain problems is its idea of object identity, where the object contains its own state. The primary advantage of a language like Haskell is the total lack of mutable state. How can I combine those two? It makes no sense, because the underlying machine models of the two languages are so radically different. ]In addition, I find the architectures simpler than the HLLs. It is not ]true that Algol has all the primitive operators for numerical calculation ]in its list of operators. It is true that it has enough that one can ]define any other, but this is like saying that the way that multiplication ]should be perforemed is by squaring the sum and the difference, subtracting, ]and shifting right two bits. The compiler may very well miss what I see, and ]vice versa. ] The underlying architecture of the real machine may be vastly simpler than the model underlying the language that is chosen to solve a problem. But that doesn't really matter. (A RISC machine has the simplest architecture of any of todays computers, but that doesn't mean that I want to write all my programs in RISC assembly!) The important thing is how clearly the language models the solution. The code written by a hotshot hack in assembly may be "better" in an efficiency sense than the code output by an SML compiler - but if the machine language does not clearly model the solution, and the SML program does, the SML is the better choice. <MC> -- |Mark Craig Carroll: <MC> |"We the people want it straight for a change; |Soon-to-be Grad Student at| cos we the people are getting tired of your games; |University of Delaware | If you insult us with cheap propaganda; |carroll@dewey.udel.edu | We'll elect a precedent to a state of mind" -Fish
bruce@mks.com (Bruce Payette) (07/31/90)
In article <26058@nigel.udel.EDU> carroll@udel.edu (Mark Carroll <MC>) writes: >In article <2417@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: >] >]You like an object-oriented language, and you like a functional language. >]Why not combine everything? It is not so much a problem for the language >]designer as for the compiler writer. >] > >What you're asking for doesn't even make good sense. Yes, I like oo >languages. And I like functional languages. But combine them? It doesn't >make good sense. > >A program in any language is a description of a machine. The language >that you use determines what kind of machine your program is >describing. In an Algol like language, you're basically modelling a >vonNeumann machine. In Smalltalk or Self, you're modeling a >message-passing machine. In Haskell, you're modeling a machine that >does lambda calculus expansion. The models don't necessarily mix. If I >mix the message-pass model of Smalltalk, and the functional model of >Haskell, I end up with a monstrosity that destroys that attractive >features of both! In a big way, the thing that makes Smalltalk so good >at solving certain problems is its idea of object identity, where the >object contains its own state. The primary advantage of a language >like Haskell is the total lack of mutable state. How can I combine >those two? It makes no sense, because the underlying machine models of >the two languages are so radically different. > > <MC> >-- >|Mark Craig Carroll: <MC> |"We the people want it straight for a change; >|Soon-to-be Grad Student at| cos we the people are getting tired of your games; >|University of Delaware | If you insult us with cheap propaganda; >|carroll@dewey.udel.edu | We'll elect a precedent to a state of mind" -Fish Actually some work has been done on combining the oo and functional paradigms. The Cosmos project at Newcastle-on-Tyne(?) has proposed a system (operating- system not a language) based on a mix of the two approaches. Objects are immutable - they can only be created. "Methods" (or whatever you choose to call them) are associated with objects but can only create a new object which is a modified COPY of the old one. No object is ever changed. This fulfills the principle of immutability required by the functional programming paradigm but also allows you to use oo. (Actually the notation looks more like parametric polymorphism than OOPS, a minor(?) religious point). Another approach to "combining" the various paradigms is in a multi-paradigm programming system. The various facilities are available, but aren't really merged. The Xerox Interlisp/LOOPS system is one of the best examples of this. It allows you to combine functional, procedural, object-oriented, rule-based and God knows what else all in the same program. The POPLOG system also has similar features. -- --Bruce Payette, Mortice Kern Systems Inc., 35 King Street N., Waterloo, Ont. Internet: bruce@mks.com UUCP: ..!uunet!watmath!mks!bruce
mantei@casca.cs.uiuc.edu (Jeff Mantei) (08/01/90)
seanf@sco.COM (Sean Fagan) writes: >The CDC Cyber 170 machines (of which most people know I am a big fan 8-)) >have no stack, and, on a subroutine call, write an instruction into the >first word of the subroutine ("jump <retaddr>," basicly). There is a problem with this is if you want shareable text -- which has to be immutable. >Incidently: Crays stuff the return address into a register, which your >routine can then save if it wants to (leaf routines, of course, don't need >to save it). Also, the new HP Precision Architecture RISC processor machines use a similar convention. Jeff Mantei mantei@cs.uiuc.edu
brianm@jomby.cs.wisc.edu (Brian Miller) (08/02/90)
In article <CEY4QND@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes: >In article <2406@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: >> What language allows carrying globals in registers across recursion? >Any language. All that is required is a good inter-procedural optimiser. >That's an implementation detail, not a language feature. And as someone pointed out, a cpu with register windows will handle inter-procedural globals *and* parameters without compiler support. Example: Berkley RISC I + II.
preston@titan.rice.edu (Preston Briggs) (08/02/90)
In article <10942@spool.cs.wisc.edu> brianm@jomby.cs.wisc.edu (Brian Miller) writes: >In article <CEY4QND@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes: >>In article <2406@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: >>> What language allows carrying globals in registers across recursion? > >>Any language. All that is required is a good inter-procedural optimiser. >>That's an implementation detail, not a language feature. > > And as someone pointed out, a cpu with register windows will >handle inter-procedural globals *and* parameters without compiler >support. Example: Berkley RISC I + II. This isn't true. You can do very little without compiler support. You certainly can't allocate globals to registers without interprocedural analysis. Every procedure will need to know where to find the global and we must be sure it isn't aliased. Register windows can't help with either problem. Parameters have some of the same problems. In C or Fortran, we can pass parameters in registers, but Pascal and others require more care since parameters may be referenced from nested procedures and should therefore be in memory, in a known locatation. The nesting also leads to the same sort of aliasing problems mentioned earlier. Peter da Silva distinguishes between the language and the implementation, which is of course important. However, many (most?) languages are not very amenable to interprocedural optimization. One reason is that the optimizer needs to construct a call multi-graph. (We say "multi-graph", since one procedure might contain several calls to another, and the individual call-sites should be distinguished.) Currently, there are efficient methods for languages that have only statically declared procedures (no procedure variables or parameters, like people imagine when they wave their hands about interprocedural optimization). There are also versions that can handle procedure parameters (like Fortran). Handling procedure-valued variables is very difficult and isn't done well or efficiently. This include languages like C, Oberon, Scheme, ... -- Preston Briggs looking for the great leap forward preston@titan.rice.edu
gudeman@cs.arizona.edu (David Gudeman) (08/03/90)
In article <1990Aug2.165229.28079@rice.edu> preston@titan.rice.edu (Preston Briggs) writes:
]... many (most?) languages are
]not very amenable to interprocedural optimization...
]Currently, there are efficient methods for languages that have only
]statically declared procedures (no procedure variables or parameters,
]like people imagine when they wave their hands about interprocedural
]optimization). There are also versions that can handle procedure parameters
](like Fortran). Handling procedure-valued variables is very difficult
]and isn't done well or efficiently.
This is a little deceptive. It is not a problem to do interprocedural
optimization in a language that _allows_ procedure-valued variables,
only for particular programs that _use_ such variables. A C program
that uses no procedure-valued variables can easily be detected (at
link-time) and optimized as though such variables were not allowed.
Furthermore, a program that does use such variables doesn't have to
suffer a huge performance hit unless the procedure variables are used
all over the place and the procedures that are assigned to variables
change a lot of global variables. If the uses are fairly isolated, or
the assigned procedures are well-behaved, then most of the program
can be optimized as thought they weren't there.
The only real problem with procedure-valued variables (and
interprocedural optimization in general) in C is that you have to do
it at link time, over the whole program at once. This problem could
be reduced if C allowed more informative declarations. Prototypes are
a good start, but it would also be useful to allow extra declarations
to specfy things like what globals are used and modified.
Of course, these sorts of declarations can't be verified by the
compiler because they depend on what procedures a given procedure
calls. So there is still some work for the linker to do.
--
David Gudeman
Department of Computer Science
The University of Arizona gudeman@cs.arizona.edu
Tucson, AZ 85721 noao!arizona!gudemanpreston@titan.rice.edu (Preston Briggs) (08/03/90)
In article <23822@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: >In article <1990Aug2.165229.28079@rice.edu> preston@titan.rice.edu (Preston Briggs) writes: >]... many (most?) languages are >]not very amenable to interprocedural optimization... >]Currently, there are efficient methods for languages that have only >]statically declared procedures (no procedure variables or parameters, >]like people imagine when they wave their hands about interprocedural >]optimization). There are also versions that can handle procedure parameters >](like Fortran). Handling procedure-valued variables is very difficult >]and isn't done well or efficiently. >This is a little deceptive. It is not a problem to do interprocedural >optimization in a language that _allows_ procedure-valued variables, >only for particular programs that _use_ such variables. A C program >that uses no procedure-valued variables can easily be detected (at >link-time) and optimized as though such variables were not allowed. Well, for research purposes, maybe. Link-time optimization means waiting 'til you have the entire program in one place so you can optimize over the whole thing (think expensive). Remember that every change means re-optimizing the entire program (as you noted), including all the libraries you normally link in. >Furthermore, a program that does use such variables doesn't have to >suffer a huge performance hit unless the procedure variables are used >all over the place and the procedures that are assigned to variables >change a lot of global variables. If the uses are fairly isolated, or >the assigned procedures are well-behaved, then most of the program >can be optimized as thought they weren't there. In my sample languages (C, Oberon, Scheme), I tried to be fair and take into account normal usage. C is perhaps a counter-example, and it's only included because it's relevant to most readers. >The only real problem with procedure-valued variables (and >interprocedural optimization in general) in C is that you have to do >it at link time, over the whole program at once. This problem could >be reduced if C allowed more informative declarations. Prototypes are >a good start, but it would also be useful to allow extra declarations >to specfy things like what globals are used and modified. Even at link-time, procedure-valued variables are difficult. If present, they can blow big holes in your call graph. >Of course, these sorts of declarations can't be verified by the >compiler because they depend on what procedures a given procedure >calls. So there is still some work for the linker to do. Interprocedural analysis need not be done at link time. At Rice, people have spent some years studying the problem and building systems that do interprocedural analysis. Basically, we do things in 3 phases. 1) Local analysis of each routine. 2) Global (interprocedural) analysis, using only the local summary information (that is, not looking at any program text). 3) Optimization of individual procedures. (1) is only done when a file is changed. We actually do it in our editor. (2) is repeated whenever any local info has changed (almost always). As part of (2), we notice which procedures need to be re-compiled because their interprocedural info has changed (their text hasn't, but they reference an interprocedural fact that has). Interprocedural analysis typically finds facts like what variables are referenced or changed across a call site, what parameters are constant at a procedure entry, and what parameters might be aliased (to each other or to a global). I don't believe the interprocedural register allocation problem has been solved satisfactorily. None seem to acknowledge the recompilation problem for large programs. -- Preston Briggs looking for the great leap forward preston@titan.rice.edu
gudeman@cs.arizona.edu (David Gudeman) (08/04/90)
In article <1990Aug2.224828.2867@rice.edu> preston@titan.rice.edu (Preston Briggs) writes: > >Well, for research purposes, maybe. Link-time optimization >means waiting 'til you have the entire program in one place >so you can optimize over the whole thing (think expensive). >Remember that every change means re-optimizing the entire >program (as you noted), including all the libraries you normally link in. My model of optimization is that it is something that is done after you have done all your testing and are producing a production version of the program. In this model, it doesn't matter if it takes a hundred times longer to compile. (Just because I know someone else is going to say it if I don't: Yes, you should run your test cases again on the optimized code.) >In my sample languages (C, Oberon, Scheme), I tried to be fair and take >into account normal usage. C is perhaps a counter-example, and it's >only included because it's relevant to most readers. I don't know much about Oberon, but I know it is easy to write a lot of Scheme code without resorting to procedure-valued variables. Of course, they do tend to crop up a lot more than in C... -- David Gudeman Department of Computer Science The University of Arizona gudeman@cs.arizona.edu Tucson, AZ 85721 noao!arizona!gudeman
phipps@garth.UUCP (Clay Phipps) (08/09/90)
[I missed the beginning of this thread; I hope I have unpeeled the onion of nested attributions correctly:] In article <58091@lanl.gov> jlg@lanl.gov (Jim Giles) writes: > >Well yes, ALGOL _has_ had an enormous _negative_ impact >on language design (that still continues today). >In fact, only two features, that I can find, are original to ALGOL >and have a continuing positive influence on language design: >if-then-else and while(). ^^^^^^^ In Algol-60, "while" was relegated to being one of the 3 forms of for-list-elements, i.e.: a clause of its "for" statement. The first appearance (that I can find) of a "while" statement as in Pascal was in Wirth's Algol-W [Wirth & Hoare: "A Contribution to the Development of ALGOL", CACM, v. 9, n. 6 (June 1966)]. -- [The foregoing may or may not represent the position, if any, of my employer, ] [ who is identified solely to allow the reader to account for personal biases.] Clay Phipps Intergraph APD: 2400#4 Geng Road, Palo Alto, CA 94303; 415/852-2327 UseNet (Intergraph internal): ingr!apd!phipps UseNet (external): {apple,pyramid,sri-unix}!garth!phipps EcoNet: cphipps ^^^^^^ Our site is once again experiencing 2-week delays in receiving net-news.
phipps@garth.UUCP (Clay Phipps) (08/11/90)
In article <2417@l.cc.purdue.edu>, cik@l.cc.purdue.edu (Herman Rubin) wrote: > >[...] I find the architectures simpler than the HLLs. >It is not true that Algol has all the primitive operators >for numerical calculation in its list of operators. Here's your opportunity to enlighten those of us more concerned with generating fast code for a large percentage of our customers than with providing a complete set of primitive operators for numerical calculation. What are those primitives, and what characteristics must they have ? >It is true that it has enough that one can define any other, >but this is like saying that the way that multiplication should >be perforemed is by squaring the sum and the difference, subtracting, >and shifting right two bits. You mean repeated addition isn't adequate ? :-) Sometimes it is *faster*. -- [The foregoing may or may not represent the position, if any, of my employer, ] [ who is identified solely to allow the reader to account for personal biases.] [Besides, this was written and posted while waiting for a test run to finish.] Clay Phipps Intergraph APD: 2400#4 Geng Road, Palo Alto, CA 94303; 415/852-2327 UseNet (Intergraph internal): ingr!apd!phipps UseNet (external): {apple,pyramid,sri-unix}!garth!phipps EcoNet: cphipps ^^^^^^ Our site is once again experiencing 2-week delays in receiving net-news.