oz@yunexus.yorku.ca (Ozan Yigit) (12/27/90)
In article <21126:Dec2614:38:2890@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >A few people have said that I'm cheating in some sense, though they >can't explain exactly how. Let me draw an analogy. You are not cheating. You are confusing the intrinsic expressiveness of a language with that which is programmable in it. The original question had the former in mind, as I tried to illustrate in my scheme example. oz --- Where the stream runneth smoothest, | Internet: oz@nexus.yorku.ca the water is deepest. - John Lyly | UUCP: utzoo/utai!yunexus!oz
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (12/27/90)
In article <19418@yunexus.YorkU.CA> oz@yunexus.yorku.ca (Ozan Yigit) writes: > You are confusing the intrinsic expressiveness > of a language with that which is programmable in it. No fair to ignore my examples to the contrary. I think you're confusing language syntax with language semantics. Or can you define ``intrinsic expressiveness'' in terms of anything but syntax? Are composable functions part of the ``intrinsic expressiveness'' of Q? I'd also like to point out that real-world programmers really don't care whether a solution is part of ``the intrisic expressiveness'' of a language as long as it is ``programmable in it.'' Okay, okay, so I shouldn't bring up real-world programming issues in a computer science discussion. Sorry. ---Dan
barmar@think.com (Barry Margolin) (12/27/90)
In article <23986:Dec2703:47:1390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >I'd also like to point out that real-world programmers really don't care >whether a solution is part of ``the intrisic expressiveness'' of a >language as long as it is ``programmable in it.'' You mean real-world programmers would be happy if we replaced Fortran, Pascal, C, and Lisp with raw Turing Machines? Any solution is programmable in a TM, but we prefer higher-level languages because it is easier to express most solutions in them. -- Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
augustss@cs.chalmers.se (Lennart Augustsson) (12/29/90)
In article <23986:Dec2703:47:1390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <19418@yunexus.YorkU.CA> oz@yunexus.yorku.ca (Ozan Yigit) writes: >> You are confusing the intrinsic expressiveness >> of a language with that which is programmable in it. > >No fair to ignore my examples to the contrary. I think you're confusing >language syntax with language semantics. Or can you define ``intrinsic >expressiveness'' in terms of anything but syntax? Are composable >functions part of the ``intrinsic expressiveness'' of Q? > >I'd also like to point out that real-world programmers really don't care >whether a solution is part of ``the intrisic expressiveness'' of a >language as long as it is ``programmable in it.'' Okay, okay, so I >shouldn't bring up real-world programming issues in a computer science >discussion. Sorry. > >---Dan I didn't want to post on this subject again, but since Dan seems to think that those opposing his view of things cannot express clearly what their objection is I'll make just one more try (to explain what I mean, at least). I apologize to those who find this trivial and think it's just a waste of time and space. Since Dan seems to hate computer science (or is it just computer scientists? Btw. what do you consider yourself to be Dan?) I will try to refrain from using computer science arguments. First a short recap of the argument so far, to the right I've put a similar but completely fictitious argument (the analogy is not perfect). Initial claim: Initial claim: C has first class functions. C has integers. My claim: Claim: In C you cannot write a function In C you cannot write a function int (*compose)(int (*f)(int), int factorial(int n); int (*g)(int)); with the proprety with the property (*compose(f,g))(x) == f(g(x)) factorial(n)/1/2/ ... /(n-1)/n == 1 Dan's counterclaim: Counterclaim: Yes, you can. You just define Yes, you can. You just define typedef ... func; typedef ... bignum; func cf_to_func(int (*f)(int)) bignum int_to_bignum(int) ... bignum mul(bignum, bignum) ... ... and now you can define and now you can define func compose(func f, func g) { bignum factorial(bignum n) { ... ... } } The problem with the counterclaim is that it talks about a completely different, newly defined type called func (integer), but the original claim was about another builtin type. Dan claims that there is no practical difference, but I think there is a very big one. If I have tons of code that uses functions (ints) I would have to make massive changes to be able to use that code with these new type func (bignum). Even worse, I may not have the source code for all the things I use, e.g. a library function like qsort (abs) would fail horribly if passed an object of the new type insteaad of the original. It is true that if I have the source the changes are massive, but trivial so they could be automated. Unfortunately in the real world you don't always have the source. (You cannot write a total function that converts func to C functions any more than you write a total function that converts bignum to int. The function has to fail (or give a "wrong" result) for some arguments.) To state my argument concisely: If a predefined type X (function, int) does not have property P it does not matter if it possible to define another type that has property P, X still does not have it. Furthermore, C is such that predefined types have special syntax and the compiler handles code generation for then in a special way. This is what makes it into a practical problem. If a program uses a *defined* type X in C it would probably be easy (a minimal number of or perhaps no changes) to change it so that it uses Y instead. It would still be true that if X does not have property P, then it hasn't. But then I would agree with Dan: the practical implications of the whole thing would be inconsequential. Since Dan's description of Q was rather short I cannot say anything about Q. Is it the case that you can change anything without syntactical changes? Without recompilation? :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) We break here for a short message from our sponsor. This is a excerpt from a thread in comp.lang.nonsense: Anonymous voice says: FORTRAN is a subset of C. August Lennartsson says: No, here's a counterexample DO 10 I = 1,10 10 J = J + I END Ben Darnstein says: Yes it is! Just make the following trivial change main() { fortran_interpreter(" DO 10 I = 1,10 10 J = J + I END "); } and this simple definition fortran_interpreter(char *s) { ... } There you are! FORTRAN is a subset of C! ----- And now back to our main program. :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) A way of changing C to allow the definition of (my) compose would be to allow nested function defintions and the possibility to return an inner function. You would the do int (*compose)(int (*f)(int), int (*g)(int)) { int r(int x) { return f(g(x)); } return r; } An implementation of this would of course have to do something along the lines of what Dan suggested, i.e. you cannot just return a pointer to the code for a function, you have to return a closure with a code pointer and an environment with the free variables (f and g in the example). If this was added to C you would almost certainly also want garbage collection since the closures would probably be heap allocated and adding explicit freeing of them would be weird since then the programmer has to free object that has been allocated by the runtime system. Enough of this ranting. Exhausted and convinced that Dan wants the last word on this I leave this group you Dan! -- Lennart Augustsson [This signature is intentionally left blank.]
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/03/91)
In article <1990Dec27.043209.7131@Think.COM> barmar@think.com (Barry Margolin) writes: > In article <23986:Dec2703:47:1390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >I'd also like to point out that real-world programmers really don't care > >whether a solution is part of ``the intrisic expressiveness'' of a > >language as long as it is ``programmable in it.'' > You mean real-world programmers would be happy if we replaced Fortran, > Pascal, C, and Lisp with raw Turing Machines? I sure wouldn't mind a Turing Machine on my desk for some of those big-memory computations. :-) Seriously: No, because once you have equal power you start paying attention to efficiency. If the hardware is crippled then things won't run at a reasonable speed. ---Dan
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/03/91)
In article <1990Dec29.110202.3862@mathrt0.math.chalmers.se> augustss@cs.chalmers.se (Lennart Augustsson) writes: > I apologize to those who find this trivial and think it's just > a waste of time and space. Ditto. > Since Dan seems to hate computer science (or is it just computer > scientists? Btw. what do you consider yourself to be Dan?) I will > try to refrain from using computer science arguments. I don't hate computer science or computer scientists, and I don't have anything against ``computer science arguments'' (whatever those are). I consider myself a mathematician, since you ask. [ analogy between functions and integers ] [ analogy between composable functions and arbitrary-precision integers ] I agree that your analogy is reasonably close. For reasons outlined in a previous article, I would say ``C supports arbitrary-precision arithmetic'' just as strongly as ``C supports composable functions.'' (I am using ``supports'' to dodge the ambiguity of ``has.'') However, there is one important failure of the analogy. Integers really are an atomic type in C. Function pointers are not. C has first-class arithmetic built in to the language. It does not have first-class functions built in. Of course, these statements about language power ignore issues of efficiency and syntax. > The problem with the counterclaim is that it talks about a completely > different, newly defined type called func (integer), but the original > claim was about another builtin type. In this case, C does *not* have built-in first-class functions, unless you abuse terminology and take ``has'' as something syntactic. So what do you care about? If you care about what's built in, then you can go nitpick with the ANSI word-mangling committee. If you care about programming, you will solve the problem at hand and not worry about what's built in and what takes a few lines of code to implement. > Dan claims that there is no practical difference, but I think there > is a very big one. If I have tons of code that uses functions (ints) > I would have to make massive changes to be able to use that code with > these new type func (bignum). The fact that function pointers are supported more strongly than struct fun pointers is merely a matter of convention and history. Neither type is built in to the language per se. (I am referring to K&R and common C.) If I understand your argument correctly, you are saying that C ``has'' a type if and only if you can find a big enough box of library functions that depend on that type. This is insupportable. Please don't misinterpret my statements here. I do agree that there is a practical reason to use whatever code is available when it does the job. But you started by saying that C doesn't have first-class (rather, first-class composable) functions, and that's a theoretical statement with a theoretical meaning. > (You cannot write a total function that converts func to C functions any more > than you write a total function that converts bignum to int. The function > has to fail (or give a "wrong" result) for some arguments.) Actually, another poster illustrated a technique for doing exactly this, with no failures. It's a rather nice solution, though it does require ANSI C. > To state my argument concisely: If a predefined type X (function, int) > does not have property P it does not matter if it possible to define > another type that has property P, X still does not have it. C does not predefine any type which is a first-class function! Why do you keep saying it does? Either you say that C has composable functions, or you say that C doesn't have first-class functions (in the usual sense) at all. There's no way out without an appeal to syntax. I understand that you and Dave really are taking that way out, and I think we are on common ground wrt what we mean. I just don't like mixing syntax into a discussion of semantics. Next time I'll try to stay away from phrases like ``C has X.'' > Since Dan's description of Q was rather short I cannot say anything > about Q. Is it the case that you can change anything without > syntactical changes? Without recompilation? Without changes to the program text per se, always. Without recompilation, of course not. For the purposes of this discussion, C++ works the same way. > Anonymous voice says: > FORTRAN is a subset of C. This statement refers to much more than language power. In particular, C cannot deal with certain features of Fortran syntax. Therefore Fortran is not a subset of C. Why are you being facetious? ---Dan
barmar@think.com (Barry Margolin) (01/03/91)
In article <18463:Jan219:52:0391@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <1990Dec27.043209.7131@Think.COM> barmar@think.com (Barry Margolin) writes: >> You mean real-world programmers would be happy if we replaced Fortran, >> Pascal, C, and Lisp with raw Turing Machines? >Seriously: No, because once you have equal power you start paying >attention to efficiency. If the hardware is crippled then things won't >run at a reasonable speed. I guess I haven't learned that you require everything spelled out precisely. First of all, a Turing Machine is an abstract device, so it doesn't make sense (to me) to refer to the efficiency of the hardware -- there is no hardware. Since I was talking about replacing programming languages, my sentence wouldn't have made sense if I were suggesting replacing them with hardware. What I was actually referring to was the Turing Machine programming model, which is basically an infinite state automaton. On finite computers this can be approximated by a finite state automaton with a large enough number of states (i.e. a large address space). So, I guess I meant was: you mean real-world programmers would be happy if we replaced their high-level languages with low-level FSA interpreters/compilers, assuming they produce similarly efficient code. I believe the TM model of programming is even more low-level than most assembly languages. And it's well-known that good assembly programmers can produce more efficient programs than high-level language programmers (given the state of most compilers). Yet most people prefer to program in high-level languages. Anyone who prefers high-level languages over assembly is not likely to want a TM. Basically, it is well-known that most general-purpose programming languages are computationally equivalent to each other. Expressive power refers to the *ease* with which they can be used, not to their fundamental computational power. If two languages are identical except that one has a built-in exponentiation operator, the one with is more expressive than the one without, even though exponentiation can be programmed in the one without. (Note that I use "built-in" to include "available in a standard library", since the distinction I am making refers to whether the user of the language is forced to write or obtain the operator versus being able to assume its existence.) -- Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
new@ee.udel.edu (Darren New) (01/04/91)
In article <19717:Jan220:38:5491@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >> Anonymous voice says: >> FORTRAN is a subset of C. > >This statement refers to much more than language power. In particular, C >cannot deal with certain features of Fortran syntax. Therefore Fortran >is not a subset of C. Why are you being facetious? > >---Dan Well, if you write a FORTRAN interpreter in C, I don't see how you can say that FORTRAN is not a subset of C. Precisely which "features of Fortran syntax" is C incapable of handling? Or have I missed the point? -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, Formal Description Techniques (esp. Estelle), Coffee, Amigas ----- =+=+=+ Let GROPE be an N-tuple where ... +=+=+=
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/04/91)
In article <40569@nigel.ee.udel.edu> new@ee.udel.edu (Darren New) writes: > In article <19717:Jan220:38:5491@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >> Anonymous voice says: > >> FORTRAN is a subset of C. > >This statement refers to much more than language power. In particular, C > >cannot deal with certain features of Fortran syntax. Therefore Fortran > >is not a subset of C. Why are you being facetious? > Well, if you write a FORTRAN interpreter in C, I don't see how you can > say that FORTRAN is not a subset of C. Gee. I wrote a Forth interpreter in 8088 assembler. Does that make Forth a subset of 8088 assembler? > Precisely which "features of > Fortran syntax" is C incapable of handling? A parser for C cannot parse Fortran's spacing conventions. Finis. ---Dan
new@ee.udel.edu (Darren New) (01/05/91)
In article <3340:Jan322:21:4791@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >Gee. I wrote a Forth interpreter in 8088 assembler. Does that make Forth >a subset of 8088 assembler? No, and that was the point that the original poster made. Just because you can code composable functions in C does not mean that composable functions are part of C. >> Precisely which "features of >> Fortran syntax" is C incapable of handling? > >A parser for C cannot parse Fortran's spacing conventions. Finis. But the original code fragment passed a string to a function. Hence, you are not talking about a parser for C, but rather a parser written in C. Hence, again, the original poster's argument makes the point. -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, Formal Description Techniques (esp. Estelle), Coffee, Amigas ----- =+=+=+ Let GROPE be an N-tuple where ... +=+=+=
new@ee.udel.edu (Darren New) (01/05/91)
In article <GESSEL.91Jan4105720@masada.cs.swarthmore.edu> gessel@masada.cs.swarthmore.edu (Daniel Mark Gessel) writes: >>Well, if you write a FORTRAN interpreter in C, I don't see how you can >>say that FORTRAN is not a subset of C. > -- Darren >You have missed the point completely. If you can write a FORTRAN >interpreter in C, C is as powerful or more than FORTRAN. Actually, I hadn't missed the point. I was asking an Aristotelian/rhetorical question of Dan to show where I though he had missed the point. The first statement was "Here is how to do FORTRAN in C, does that make it a subset?" and Dan said (essentially) "No, because there is FORTRAN syntax that C can't handle." and I responded "Name some." I got the point, and Dan probably got the point but seems to me to have brought up a specious argument that intentionally missed the point in order to continue the argument. Maybe this was not intended, but it seemed that way to me. >A language without any form of dynamic allocation is going to be weak, >(is FORTRAN like this?). Actually, most assembler languages don't have dynamic allocation. I would think you could handle it in FORTRAN the same as in assembler. Hmmm... on second thought, that doesn't answer the question, does it :-) (Disclaimer: I have not looked at FORTRAN in ~7 years. Maybe it has dynamic allocation by now.) -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, Formal Description Techniques (esp. Estelle), Coffee, Amigas ----- =+=+=+ Let GROPE be an N-tuple where ... +=+=+=
gessel@masada.cs.swarthmore.edu (Daniel Mark Gessel) (01/05/91)
>Well, if you write a FORTRAN interpreter in C, I don't see how you can >say that FORTRAN is not a subset of C. Precisely which "features of >Fortran syntax" is C incapable of handling? Or have I missed the >point? -- Darren You have missed the point completely. If you can write a FORTRAN interpreter in C, C is as powerful or more than FORTRAN. If you can write a C interpreter in FORTRAN as well, they are equally powerful. But that does not make FORTRAN a subset of C, (nor C a subset of FORTRAN). If FORTRAN were a subset of C, any legal program in FORTRAN would be a legal program in C. Not only that, they should have the same semantics, although that becomes a difficult question when function libraries are considered. From a purely syntactic point of view, I'm pretty sure (although I don't know FORTRAN) that there are constructions in FORTRAN that C's syntax could not generate. Nonetheless, it has nothing to do with being able to write an interpreter for one language in another. Most languages are equally powerful. That is, any program you can write in one language you can write in another, (even though it could be really difficult). A language without any form of dynamic allocation is going to be weak, (is FORTRAN like this?). Dan -- Daniel Mark Gessel Independent Software Consultant Internet: gessel@cs.swarthmore.edu and Developer I do not represent Swarthmore College (thank God).
dc@sci.UUCP (D. C. Sessions) (01/05/91)
In article <40569@nigel.ee.udel.edu> new@ee.udel.edu (Darren New) writes: # In article <19717:Jan220:38:5491@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: # >> Anonymous voice says: # >> FORTRAN is a subset of C. # > # >This statement refers to much more than language power. In particular, C # >cannot deal with certain features of Fortran syntax. Therefore Fortran # >is not a subset of C. Why are you being facetious? # > # >---Dan # # Well, if you write a FORTRAN interpreter in C, I don't see how you can # say that FORTRAN is not a subset of C. Precisely which "features of # Fortran syntax" is C incapable of handling? Or have I missed the # point? -- Darren # -- # --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- Hmmm... by the same token, you can write a C interpreter in BASIC, and a BASIC interpreter in FORTRAN. If I recall my set theory correctly, this means that FORTRAN, BASIC, and C are all equivalent. (Note that I am *not* advocating writing these *****s. For that sort of thing, look in alt.masochism) What we have just rediscovered, children, is the rather well-known (gasp! dare I say the dreaded words?) computer science theorem that any system capable of general recursion is of equivalent power. Of course, if raw power were the only consideration we'd still all be punching decks of absolute code. With sewing needles. -- | The above opinions may not be original, but they are mine and mine alone. | | "While it may not be for you to complete the task, | | neither are you free to refrain from it." | +-=-=- (I wish this _was_ original!) D. C. Sessions -=-=-+
kinnersley@kuhub.cc.ukans.edu (Bill Kinnersley) (01/05/91)
In article <40693@nigel.ee.udel.edu>, new@ee.udel.edu (Darren New) writes:
:
: (Disclaimer: I have not looked at FORTRAN in ~7 years. Maybe it has
: dynamic allocation by now.)
:
Not yet but soon, patience. The proposed Fortran 8x has structures,
pointers, and a heap. For example you'll be able to build linked lists
by doing something like this:
TYPE ITEM
REAL VALUE
TYPE(ITEM),POINTER :: NEXTITEM
END TYPE ITEM
TYPE(ITEM),POINTER :: STACK, NEWITEM
NULLIFY(STACK)
ALLOCATE(NEWITEM)
NEWITEM = ITEM(3.7,STACK)
STACK => NEWITEM
(I can't help it, they send me this stuff in the mail.)
--
--Bill Kinnersleybrnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/05/91)
In article <40690@nigel.ee.udel.edu> new@ee.udel.edu (Darren New) writes: > In article <3340:Jan322:21:4791@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >Gee. I wrote a Forth interpreter in 8088 assembler. Does that make Forth > >a subset of 8088 assembler? > No, and that was the point that the original poster made. Just because you > can code composable functions in C does not mean that composable functions > are part of C. I never said they were. C's functions are not first-class. C's function pointers are not composable. But C does have first-class composable functions. > >A parser for C cannot parse Fortran's spacing conventions. Finis. > But the original code fragment passed a string to a function. Which has to do neither with the statement ``Fortran is a subset of C,'' nor with the statement ``C has first-class functions,'' nor with anything else remotely related to this discussion. ---Dan
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/05/91)
In article <27699.27849b1b@kuhub.cc.ukans.edu> kinnersley@kuhub.cc.ukans.edu (Bill Kinnersley) writes: > The proposed Fortran 8x 9x now. The progression 66-77-88 would have been nice---among other things, it would have shown that the Fortran programming community could accept the moderate evolution occurring in the language. But ANSI X3J3 went out of its way to invent (and copy from Modula-2, Ada, et al.) rather than codify current practice. So there is no Fortran 88. ---Dan Ban X3J3.
kinnersley@kuhub.cc.ukans.edu (Bill Kinnersley) (01/06/91)
In article <11770:Jan502:09:2091@kramden.acf.nyu.edu>, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: : In article <27699.27849b1b@kuhub.cc.ukans.edu> kinnersley@kuhub.cc.ukans.edu (Bill Kinnersley) writes: : :> The proposed Fortran 8x : : 9x now. : The way I hear it, it's still Fortran 8x, but x has now become a hexadecimal digit. -- --Bill Kinnersley