brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/03/91)
In e-mail discussions Dave Gudeman has shown me what I was missing about Lennart's original statement. Here goes. Lennart started by saying that C does not have first-class functions. It was reasonably clear that what he meant was that C does not have first-class composable functions, and that's what I objected to. I think we all agree on what ``first-class,'' ``composable,'' and ``function'' mean. A first-class object can be passed as arguments and assigned to variables. A function is something for which there exists one evaluation operator for each value of some type. A composable function also supports a composition operation with the obvious definition. This is all reasonably standard terminology. The problem is what ``has'' means. There are at least three workable definitions of ``C has first-class (composable) functions.'' The first, which I call NP (nitpick): ``The things that C calls `functions' are first-class objects (which are composable).'' The second, BI (builtin): ``C has some built-in objects which are first-class (composable) functions.'' This is slightly ambiguous, because it's not clear what a ``built-in object'' is. I will return to this point below. The third, POW (power): ``C supports certain language features sufficiently well to implement objects which are first-class (composable) functions.'' Now NP is obviously wrong, both with and without ``composable.'' The things that C calls ``functions'' aren't even first-class. POW is right, both with and without ``composable.'' One example of a first-class function in C is ``pointer to function''; the evaluation operation is ``dereference and then call as a function.'' One example of a first-class composable function in C is ``pointer to structure containing an integer and either one function pointer or two structure pointers depending on the integer''; I described the evaluation and composition operations on this type in detail in a previous article. Whether BI is right depends on your definition of ``built in.'' I don't see any reasonable definition other than ``atomic''---and by that definition, pointers to functions are not ``built in'' any more than pointers to structures containing blah are. This means that BI is wrong, both with and without ``composable.'' (But see below.) When I read Lennart's statement I automatically assumed he meant POW. NP means that you're blindly accepting the language's terminology, and can't see beyond ANSI C ``function'' when you think about functions in C. I think BI also reflects a confusion between syntax and semantics: how something is expressed in a language is irrelevant to the language's raw power. So I responded by showing one way to construct first-class composable functions in C. Dave focused on Lennart's original statement, viz., that C doesn't have first-class functions. He said that what C calls ``pointers to functions'' really are first-class. Not only that, but they are functions, because they can be evaluated. Just because C doesn't call these things ``functions'' doesn't mean they aren't functions. Dave was certainly not referring to NP. To me it was obvious that he wasn't referring to BI, for the reasons outlined above, so he must have meant POW. Then people started attacking my response. ``You're misusing terminology!'' Oh? What terminology was I misusing? I took the most natural definition of ``has.'' I think it's a big mistake to confuse syntax and semantics. ``Your solution is obvious!'' Yes, of course it is---but Lennart and Dave kept saying that C didn't have composable functions. This left me confused until Dave explained the missing step. Lennart and Dave are taking BI as their definition. They're defining ``built in'' as ``having operations equivalent in syntax to builtins'' with the second ``builtin'' meaning ``atomic'' in my sense. For example: Because (in common practice, and with the ANSI kludge) you use the same syntax to call a function pointer as you use to call a function, a function pointer is a builtin. Hence C ``has'' first-class functions in this sense. In contrast, calling one of my struct funs does not have the same syntax, so my struct funs are not builtins. Hence C does not ``have'' first-class composable functions in this sense. I don't like this, for at least two reasons. First, it does not match K&R C. There are many compilers where you must dereference a function pointer before calling it. Does this change function pointers from ``built in'' to ``not built in''? Second, it takes a statement about abstract language power like ``C has composable functions'' and turns it into a statement combining both syntax and semantics. I think that's an abuse of terminology---hiding cheap syntactic restrictions under an innocent word like ``has.'' But at least this clears up the confusion. As a programmer, I don't care about the syntax of a language as much as I care about its efficiency---but neither one matters as much as language power. In C I get a machine with an unbounded (though not infinite) amount of memory; in Fortran I have to decide memory bounds in advance, and certain programs using a lot of dynamic allocation are simply impossible to write. *That* is a big difference, and I wish we could reserve ``has'' for situations like this. ``C has memory allocation power that Fortran doesn't.'' Only when we're sure about equal power can we consider other issues. Efficiency is always a big concern. At some point BI becomes important: ``You can implement this with the built-in syntax.'' When all else is equal, NP tips the scales: ``The basic language includes exactly the feature you want with exactly this syntax.'' To sum up: ``C has first-class composable functions with reasonable efficiency and without ridiculously complicated syntax'' is good enough for me. ---Dan
kend@data.UUCP (Ken Dickey) (01/04/91)
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >I think we all agree on what ``first-class,'' ``composable,'' and >``function'' mean. A first-class object can be passed as arguments and >assigned to variables. A function is something for which there exists >one evaluation operator for each value of some type. A composable >function also supports a composition operation with the obvious >definition. This is all reasonably standard terminology. There is an important property of "first-class" objects missing here. A first-class object does not have to be named. >To sum up: ``C has first-class composable functions with reasonable >efficiency and without ridiculously complicated syntax'' is good enough >for me. >---Dan Strike "first-class". C functions do not have the status of numbers because they must be named before use. By the way, what function would "apply(compose(compose,f),x);" return in C? Strike "composable"? -Ken Dickey kend@data.uucp
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/05/91)
In article <442@data.UUCP> kend@data.UUCP (Ken Dickey) writes: > brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >I think we all agree on what ``first-class,'' ``composable,'' and > >``function'' mean. A first-class object can be passed as arguments and > >assigned to variables. [ ... ] > There is an important property of "first-class" objects missing here. > A first-class object does not have to be named. Do you have a reference? As always, I'm doing my best to use standard terminology; I just haven't seen any references that demand a syntactic restriction like that. > >To sum up: ``C has first-class composable functions with reasonable > >efficiency and without ridiculously complicated syntax'' is good enough > >for me. [ ... ] > By the way, what function would "apply(compose(compose,f),x);" return in C? > Strike "composable"? What are you talking about? It doesn't make sense to compose a function that takes two arguments, at least not without a more general notation. I can't make heads or tails of your example. ---Dan
augustss@cs.chalmers.se (Lennart Augustsson) (01/06/91)
In article <4408:Jan421:44:3391@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <442@data.UUCP> kend@data.UUCP (Ken Dickey) writes: >> [ ... ] >> There is an important property of "first-class" objects missing here. >> A first-class object does not have to be named. > >Do you have a reference? As always, I'm doing my best to use standard >terminology; I just haven't seen any references that demand a syntactic >restriction like that. > I wouldn't call the ability to have unnamned functions just a syntactic extension, it has big semantic consequences. Here's why: (Since most people seems to think it OK to blur the distinction between C-functions (I will write C-functions when I mean the builtin function type in C to avoid confusion) and C-functions pointers I will do that. Nitpicks can insert "pointer to" where appropriate.) First, what do we mean by a semantic difference. I quote from one of Dan's articles: > ... In C I get a machine with an unbounded (though not > infinite) amount of memory; in Fortran I have to decide memory bounds in > advance, and certain programs using a lot of dynamic allocation are > simply impossible to write. *That* is a big difference, and I wish we > could reserve ``has'' for situations like this. ``C has memory >allocation power that Fortran doesn't.'' I assume that this counts as a semantic difference. It can be summed up as: The amount of memory available to a C program is not bounded by the program itself (only by the implementation you run the program in). I think that both Dan and I agree on this point. Second, the number of C-functions in a C program is bounded. This is quite natural since every C-function has to be given a name and there can only be a bounded number of named things in a program of bounded size. This means that C-functions does not enjoy the same status as objects of other types in C, where it is possible to get an unbounded number of them. The bounded number of C-functions is the real reason why a C-function compose (for C-functions) cannot be written in C. Since composition can give you an unbounded number of different C-functions, but there is only a bounded number of them available it has to fail. (This is why Kristoffer Eriksson "solution" cannot be made to work in the general case.) To paraphrase: ... and certain programs using a lot of composed C-functions are simply impossible to write. So, C-functions are not composable and I think that both Dan and I agree on this point. Third, I will now extend C by unnamed C-functions. If we take an ordinary C-function declaration and replace the C-function name with ANONYMOUS we will get an expression which has C-function type (what an abominable syntax!). So for example the declaration int succ(int x) { return x+1; } can now be written (analogous to "int five = 5;") int (*succ)(int) = int ANONYMOUS(int x) { return x+1; }; and either of them used by "succ(5)". The expression "(int ANONYMOUS(int x) { return x*2; })(21)" will evaluate to 42. The unnamed C-functions should behave as ordinary C-function definitions when it comes to scoping, i.e. all variables in a C-function should be either arguments, local variables, or defined in an outer scope. The C-function expression should also behave as a normal C expression, i.e. it can be sent as an argument, returned etc. Finally, I can now write a compose C-function^: typedef int (*intintfun)(int); intintfun compose(intintfun f, intintfun g) { return (int ANONYMOUS(int x) { return f(g(x)) }; } Since I am now able to write a C-function that according to my second point was impossible to write in standard C this must mean that I have changed the semantic power (according to the definition of semantic power in the first point) of C-functions. A change in a language that changes the semantic power of a type in the language in this way is not what I would call a just syntactic change. (You could argue, quite correctly, that it is not the unnamed functions as such that gives you the power, but rather the ability to return a locally defined function. But the point is that you cannot add unnamed functions in a natural way without getting the additional semantic power.) ^ Footnote: The careful reader will see than my compose C-function has a different type than it has had in my previous examples. All my previous prototypes have been subtly wrong, but since nobody has complained about this I don't think this has confused anyone. -- Lennart Augustsson [This signature is intentionally left blank.]
karl@ima.isc.com (Karl Heuer) (01/06/91)
In article <1991Jan5.182428.615@mathrt0.math.chalmers.se> augustss@cs.chalmers.se (Lennart Augustsson) writes: >[In C extended with anonymous functions, we could write compose():] > typedef int (*intintfun)(int); > intintfun compose(intintfun f, intintfun g) { > return (int ANONYMOUS(int x) { return f(g(x))) }; > } >...the point is that you cannot add unnamed functions in a natural way >without getting the additional semantic power. I disagree. Since the return value of the function references objects that go out of scope before the value would be used, I would expect this to analogous to int *h(int i) { return &i; } , which is undefined. Karl W. Z. Heuer (karl@ima.isc.com or uunet!ima!karl), The Walking Lint
norman@d.cs.okstate.edu (Norman Graham) (01/07/91)
From article <1991Jan05.222639.6387@dirtydog.ima.isc.com>, by karl@ima.isc.com (Karl Heuer): > In article <1991Jan5.182428.615@mathrt0.math.chalmers.se> augustss@cs.chalmers.se (Lennart Augustsson) writes: >>[In C extended with anonymous functions, we could write compose():] >> typedef int (*intintfun)(int); >> intintfun compose(intintfun f, intintfun g) { >> return (int ANONYMOUS(int x) { return f(g(x))) }; >> } >>...the point is that you cannot add unnamed functions in a natural way >>without getting the additional semantic power. > > I disagree. Since the return value of the function references objects that go > out of scope before the value would be used, I would expect this to analogous > to int *h(int i) { return &i; } , which is undefined. The example is correct. The construct int ANONYMOUS(int x) { return f(g(x)) } [1] creates a new function value that has the _values_ of f and g bound up in its definition. Since the _values_ of f and g are used, scope plays no part in the value created by [1]. Remember, names have scope-- values do not. Here is an example that might help: int foo (int a, int b) { return a + b; } Do you say 'The return value of foo() references objects that go out of scope before the value is used.'? Of course not. The expression a + b creates a new value; this new value has no reference to a or b. In the same way, the expression [1] creates a new value; this new value has no reference to f or g. (Of course, the _values_ of f and g are used to create the _new_ value.) This is really much easier to think about in a functional language-- especially one that allows curried functions and partial application. -- Norman Graham <norman@a.cs.okstate.edu> Standard Disclaimer Applies {cbosgd,rutgers}!okstate!norman
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/07/91)
Summary: I implied that the ability of an object to be unnamed was a syntactic feature. Here Lennart tries to prove the opposite, by what reduces to the following argument: C functions are not allocatable. If C is extended with functions without names, then it gains power. Therefore unnamed functions are a semantic feature. The mistake in this argument is the second step. As Karl points out in another article, C does not gain power when you add unnamed functions. *Allocatable* functions are indeed semantic, and when you add them you do indeed get some power. In article <1991Jan5.182428.615@mathrt0.math.chalmers.se> augustss@cs.chalmers.se (Lennart Augustsson) writes: > In article <4408:Jan421:44:3391@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > > In article <442@data.UUCP> kend@data.UUCP (Ken Dickey) writes: > > > A first-class object does not have to be named. > > Do you have a reference? As always, I'm doing my best to use standard > > terminology; I just haven't seen any references that demand a syntactic > > restriction like that. > I wouldn't call the ability to have unnamned functions just a syntactic > extension, it has big semantic consequences. Here's why: Wait a minute. This still doesn't answer my question, which is whether anyone defines ``first-class'' to include the restriction ``can be defined without a name.'' You're talking about the side issue of whether this ``unnamability'' is a syntactic restriction or a semantic restriction. Let's analyze your argument, step by step: 1. ``The number of C-functions in a C program is bounded.'' True. 2. ``C-functions do not enjoy the same status as objects of other types in C, where it is possible to get an unbounded number of them.'' This is true. The property that the other objects have is ``allocatability.'' 3. ``The bounded number of C-functions is the real reason why a C-function compose (for C-functions) cannot be written in C.'' Although I agree with what you're trying to say, you're not saying it right. What you have observed is that C-functions are not allocatable. But this property is independent of ``first-class'' and ``composable.'' Eriksson's solution does show how to compose C-functions. You are entirely correct that a new C-function cannot be generated dynamically, but this is an independent problem. > So, C-functions are not composable and I think that both Dan and I > agree on this point. Not at all. Please stop changing your terms in the middle of the discussion. First-class is not the same as composable, or unnamable, or allocatable. It's a very specific adjective that refers to what you can do with old data. 4. ``Certain programs using a lot of composed C-functions are simply impossible to write.'' More precisely, programs cannot dynamically allocate C-functions. This is true. You then extend C with ``unnamed C-functions.'' As Karl points out in another article, your extension is simply flawed. What's the flaw? You don't allocate space for your new functions, so you can't return them. Can't you see that the problem is just like the problem of char *foo() { char s[100]; ... return s; } ? What makes char *'s and C-functions different is that char *'s are *allocatable*. You can *allocate* a new string to pass back to your caller. You can't *allocate* a new function. Unnamability is entirely independent of allocability. The former is a syntactic restriction. The latter is a semantic restriction. Your argument confuses the two and hence falls apart. 5. ``Since I am now able to write a C-function that according to my second point was impossible to write in standard C this must mean that I have changed the semantic power (according to the definition of semantic power in the first point) of C-functions.'' Nice try, but no cigar. What you have managed to prove is that *allocatability* is a semantic feature. > A change in a language that changes the semantic power of a type > in the language in this way is not what I would call a just syntactic > change. Agreed. However, your change does not affect semantics. > (You could argue, quite correctly, that it is not the unnamed functions as > such that gives you the power, but rather the ability to return a locally > defined function. But the point is that you cannot add unnamed functions > in a natural way without getting the additional semantic power.) That point is simply wrong. ---Dan
augustss@cs.chalmers.se (Lennart Augustsson) (01/07/91)
In article <1991Jan05.222639.6387@dirtydog.ima.isc.com> karl@ima.isc.com (Karl Heuer) writes: >In article <1991Jan5.182428.615@mathrt0.math.chalmers.se> augustss@cs.chalmers.se (Lennart Augustsson) writes: >>[In C extended with anonymous functions, we could write compose():] >> typedef int (*intintfun)(int); >> intintfun compose(intintfun f, intintfun g) { >> return (int ANONYMOUS(int x) { return f(g(x))) }; >> } >>...the point is that you cannot add unnamed functions in a natural way >>without getting the additional semantic power. > >I disagree. Since the return value of the function references objects that go >out of scope before the value would be used, I would expect this to analogous >to int *h(int i) { return &i; } , which is undefined. > Do you think that int f(int x, int y) { return x+y; } is illegal just because the return statement contains variables that goes out of scope when you return? Returning an unnamed function is analogous (but I can imagine that an implementer would like to make exactly your restriction since that would make it much easier to implement). -- Lennart Augustsson [This signature is intentionally left blank.]
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/07/91)
In article <1991Jan6.205005.4579@mathrt0.math.chalmers.se> augustss@cs.chalmers.se (Lennart Augustsson) writes: > In article <1991Jan05.222639.6387@dirtydog.ima.isc.com> karl@ima.isc.com (Karl Heuer) writes: > >In article <1991Jan5.182428.615@mathrt0.math.chalmers.se> augustss@cs.chalmers.se (Lennart Augustsson) writes: > >>[In C extended with anonymous functions, we could write compose():] > >> typedef int (*intintfun)(int); > >> intintfun compose(intintfun f, intintfun g) { > >> return (int ANONYMOUS(int x) { return f(g(x))) }; > >> } Your definition of unnamed functions did not magically turn them into function pointers. Either you are trying to return a function by value, which is impossible in C without a *semantic* extension; or you are returning a pointer to that function, in which case, as Karl said, the pointer is useless after the return. ---Dan
karl@ima.isc.com (Karl Heuer) (01/07/91)
In article <1991Jan6.171234.27734@d.cs.okstate.edu> norman@d.cs.okstate.edu (Norman Graham) writes: >From article <1991Jan05.222639.6387@dirtydog.ima.isc.com>, by karl@ima.isc.com (Karl Heuer): >>I disagree. Since the return value of the function references objects that >>go out of scope before the value would be used, I would expect this to >>analogous to int *h(int i) { return &i; } , which is undefined. >names have scope--values do not. True. I should have said "storage duration". >[The example should work, since it uses the *values* of f and g.] It's not f and g that are being used beyond their storage duration, it's the anonymous function itself. If C had Pascal-like nested functions, like int beta(int x) { int alpha(void) { return x; } return alpha(); } I would consider "alpha" to be an object of type function that has automatic storage duration, and hence becomes invalid when it goes out of scope. So int (*gamma(int x))(void) { int alpha(void) { return x; } return α } is illegal for the same reason as my earlier example. Making alpha an anonymous function does not change the situation. Of course, you can also consider a further extension in which functions are allocatable; but I was rebutting the statement "you cannot add unnamed functions in a natural way without getting the additional semantic power". Karl W. Z. Heuer (karl@ima.isc.com or uunet!ima!karl), The Walking Lint
norman@d.cs.okstate.edu (Norman Graham) (01/07/91)
From article <1991Jan07.045733.13637@dirtydog.ima.isc.com>, by karl@ima.isc.com (Karl Heuer): > In article <1991Jan6.171234.27734@d.cs.okstate.edu> norman@d.cs.okstate.edu (N orman Graham) writes: > >>[The example should work, since it uses the *values* of f and g.] > > It's not f and g that are being used beyond their storage duration, it's the > anonymous function itself. I see. You assumed Lennart did not add function values to the language when he added anonymous functions; I assumed he did (after all, that _is_ the most natural assumption :-). > If C had Pascal-like nested functions, like > int beta(int x) { > int alpha(void) { return x; } > return alpha(); > } > I would consider "alpha" to be an object of type function that has automatic > storage duration, and hence becomes invalid when it goes out of scope. So > int (*gamma(int x))(void) { > int alpha(void) { return x; } > return α > } > is illegal for the same reason as my earlier example. Making alpha an > anonymous function does not change the situation. If functions are not first-class values in this new language, then you are correct. However, if functions (not function pointers) are first- class values in this new language, then your first example works and your second example is incorrect (as you have already noted). > Of course, you can also consider a further extension in which functions are > allocatable; but I was rebutting the statement "you cannot add unnamed > functions in a natural way without getting the additional semantic power". Now we've returned to the original point in the thread: C does not have first-class functions--It has first-class function pointers. It appears that you believe Lennart added anonymous function pointers to the language rather than anonymous functions. Anonymous function pointers are not as useful as anonymous functions (for example, see the failures of anonymous function pointers in the above examples). I believe Lennart was using the example of anonymous functions to hammer home the fact that first-class function pointers are not as useful or as general as first-class functions. -- Norman Graham <norman@a.cs.okstate.edu> Standard Disclaimer Applies {cbosgd,rutgers}!okstate!norman
oz@yunexus.yorku.ca (Ozan Yigit) (01/09/91)
In article <4408:Jan421:44:3391@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <442@data.UUCP> kend@data.UUCP (Ken Dickey) writes: >> There is an important property of "first-class" objects missing here. >> A first-class object does not have to be named. >Do you have a reference? As always, I'm doing my best to use standard >terminology; I just haven't seen any references that demand a syntactic >restriction like that. There may be many references, though I am not sure if that will that make any difference whatsoever. It appears that you would prefer to argue than to look them up. Here is one: William Clinger, Semantics of Scheme, February. 1988, BYTE, pp. 221-227 [Will Clinger is an author of MacScheme, one of the nicest [I think] implementations of this language.] First-Class Objects All Scheme objects are endowed with certain inalienable rights: o Objects have the right to remain anonymous. o Objects have an identity that is independent of any names by which they may be known o Objects can be stored in variables and in data structures without losing their identity o Objects may be returned as a result of a procedure call o Objects never die. All scheme objects are first-class citizens of the language. In most programming languages, the only first-class objecst are those that can easily fit into a machine register, like numbers, booleans, and pointers. While numbers may be used without being given names, procedures may not; while characters and pointers may be stored, strings may not; while booleans live forever, vectors may die when the procedure that created them returns. Thus, Scheme is very unusual in this respect. In fact, Scheme is the most widely used procedural language in which all objects are first class. Though objects never die, they may become inaccessible and therefore useless. Implementations of Scheme and other advanced languages may in fact reclaim the storage occupied by an object, provided they can prove that the object will never again be used. Algorithms for performing these proofs are known as garbage-collection algorithms. ... next !! oz --- who pays any attention to the syntax | Internet: oz@nexus.yorku.ca of things will never wholly kiss you... | Uucp: utai/utzoo!yunexus!oz -- e. e. cummings | P:1+ (416) 736 5257 x 33976
anw@maths.nott.ac.uk (Dr A. N. Walker) (01/09/91)
In article <1991Jan07.045733.13637@dirtydog.ima.isc.com> karl@ima.isc.com (Karl Heuer) writes, in response to Norman Graham, >>names have scope--values do not. >True. I should have said "storage duration". Depends on the language! (I realise that the thread is nominally about C, but since we're trying to extend it, we have to drag in ideas from elsewhere.) I quote from MR93, the Algol 68 Draft Report [my copies of the actual Report and Revised Report having gone walkabout], section 2.2.4.2.b: The scope of a plain value [eg, 7 -- ANW] is the program, ..., that of a routine ... denotation ... is the smallest range containing a defining ... occurrence of an identifier ... applied but not defined within that denotation, ... and that of a name is some range. >It's not f and g that are being used beyond their storage duration, it's the >anonymous function itself. In Algol, at least, it's "f" and "g" that are the problem. The occurrences of "f" and "g" within the procedure body restrict its scope to the range defined by (the text of) "compose". The following: BEGIN PROC compose = (PROC(REAL)REAL f, g) PROC(REAL)REAL: (REAL x) REAL: sin (cos (x)); print (compose (tan, sqrt) (0)) END compiles and prints 0.84..., ie it correctly composes sin and cos, but if I replace sin and cos by f and g, the resulting program aborts with a scope violation. I suspect that if C added anonymous &/or nested functions, they would look more like Algol than like applicative languages, and that the same scope rules for closures would apply. The other way that has been mentioned is through partial application -- Charles Lindsey has provided the following example in a reasonably simple extension of Algol [which would surely also be partially applicable to C]: PROC compose = (PROC(REAL)REAL f, g, REAL x) REAL: f(g(x)); PROC(REAL)REAL sex = compose (sqrt, exp, ); # note the missing third parameter # The following is neat: OP ^ = (PROC(REAL)REAL a, INT b) PROC(REAL)REAL: ((PROC(REAL)REAL a, INT b, REAL p) REAL: (REAL x := 1; TO b DO x *:= a(p) OD; x))(a, b, ); REAL theta; ...; print ((cos^2)(theta) + (sin^2)(theta)) # had better print 1 ! # >Of course, you can also consider a further extension in which functions are >allocatable; ... There are, of course, different sorts of allocation. In both C and Algol, you can't generate lots of new functions *and export them to other parts of the program*, but at least in Algol you can generate as many new functions as you need through recursion. I rediscovered the following yesterday while searching some dusty decks for other reasons. It's a program [due to Dick Grune] for parsing the grammar S -> aSS | a T -> Sb As it stands, it just counts the number of parses, and is clearly a toy, but it works. Change the TAIL of "t" to do cleverer things, and change the structure of "s" and "t" to change the grammar. BEGIN MODE TAIL = PROC VOID, RULE = PROC (TAIL) VOID; INT n := 0; STRING input; RULE a = (TAIL q) VOID: (n +:= 1; (input [n] = "a" | q); n -:= 1), b = (TAIL q) VOID: (n +:= 1; (input [n] = "b" | q); n -:= 1), s = (TAIL q) VOID: (a (VOID: s (VOID: s (q))); a (q)), t = (TAIL q) VOID: s (VOID: b (q)); # example of use: # FOR i TO 12 DO INT count := 0; input := "aaaaaaaaaaab" [i:]; t (VOID: count +:= 1); print ((count, newline)) OD END Best of luck if you try to re-write this in C. Pascal might be possible, but I wouldn't like to try to understand the result, whereas the above is perfectly clear [:-)], despite all the anonymous procedures. -- Andy Walker, Maths Dept., Nott'm Univ., UK. anw@maths.nott.ac.uk
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/09/91)
In article <20021@yunexus.YorkU.CA> oz@yunexus.yorku.ca (Ozan Yigit) writes: > In article <4408:Jan421:44:3391@kramden.acf.nyu.edu> > brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >In article <442@data.UUCP> kend@data.UUCP (Ken Dickey) writes: > >> There is an important property of "first-class" objects missing here. > >> A first-class object does not have to be named. > >Do you have a reference? As always, I'm doing my best to use standard > >terminology; I just haven't seen any references that demand a syntactic > >restriction like that. > There may be many references, though I am not sure if that will that make > any difference whatsoever. It appears that you would prefer to argue than > to look them up. On the contrary. Every reference I've found either (1) doesn't define first-class; (2) makes ``first-class'' so restrictive that nothing in C or Ada can possibly be first-class; or (3) defines ``first-class'' as ``can be passed as an argument and [when there are variables] assigned to variables.'' Note that Dave Gudeman posted a definition equivalent to #3. > Here is one: William Clinger, Semantics of Scheme, February. 1988, BYTE, > pp. 221-227 You have this habit of posting long definitions without verifying that they have anything to do with your point. I asked for a reference that *defines* first-class in any way other than #3. The only statement in what you posted that could possibly be a definition is this one: > All scheme objects are first-class citizens of the language. But the text also gives scheme objects the following ``inalienable right'': > o Objects never die. Question 1: When you posted that definition, did you believe that it defined ``first-class''? (If not, you are not contributing to the discussion.) Question 2: Do you realize that if the properties you posted are taken to define ``first-class,'' then nothing in Ada is ``first-class''? I conjecture that Scheme advertisers have tried to corrupt the meaning of ``first-class,'' by adding properties that make Scheme objects into ``first-class'' objects while making objects in other languages into non-``first-class'' objects. Ozan is drawing upon the Scheme literature alone, but ``first-class'' wasn't invented with Scheme. ---Dan
sw@smds.UUCP (Stephen E. Witham) (01/09/91)
To me, the "power" of a language has to do with what concepts you can express
DIRECTLY. Or, it's the inverse of the amount of twisting you have to do
to express something you are conceiving of in a certain way. Having to include
a compiler or interpreter for another language is "too" indirect. The syntax
and symantics have to support what you're doing...well, "directly". But I'm
not too strict about what I mean by that.
For example, here's a way to compose functions that I think is not too
twisted, either syntactically or in terms of the overhead of things I have
to define in the beginning. What do you all think?
With this method, functions are annonymous, but function
TYPES are not. "Types" meaning, things you have to define with C code.
I think even that restriction could be overcome with macros in a way that
somebody in this thread (who? sorry.) described earlier, but that might
involve more twisting than it's worth. Here's the simplest version:
---------------------------- Code version 1 follows ------------------------
/* compose.c -- experiment in "second-class, composable, anonymous functions"
Steve Witham
Jan. 8, 1991
*/
#include <stdio.h>
void *malloc();
/* Basic definitions for "functions" */
typedef struct
{
int (*c)(); /* code */
void *d; /* data */
}
Func;
#define APPLY(f,arg) ((f)->c)( (f)->d, arg )
int
apply( f, arg ) /* Use apply, not APPLY, if f or arg is non-trivial. */
Func *f;
int arg;
{
return APPLY( f, arg );
}
/* --- A --- */
/* Definitions for "adder" function type... */
int
adderBody ( d, arg )
int *d;
int arg;
{
return *d + arg;
}
Func *
adder ( i ) /* Create an Func that adds a constant to its argument. */
int i;
{
Func *result;
result = (Func *) malloc( sizeof( Func ) );
result->c = adderBody;
result->d = (void *) malloc( sizeof( int ) );
*( (int *) result->d ) = i;
return result;
}
/* Definitions for composing functions... */
typedef struct
{
Func *f, *g;
}
FuncPair;
int
composeBody ( d, arg )
FuncPair *d;
int arg;
{
APPLY( d->f, APPLY( d->g, arg ) );
}
Func *
compose ( f, g )
Func *f, *g;
{
Func *result;
result = (Func *) malloc( sizeof( Func ) );
result->c = composeBody;
result->d = (void *) malloc( sizeof( FuncPair ) );
((FuncPair *) result->d) ->f = f;
((FuncPair *) result->d) ->g = g;
return result;
}
/* --- B --- */
/* Here's a macro to print the text of an expression with its value... */
#define ANNOUNCE(expr) printf( "expr = %d\n", expr );
/* And finally... */
main ( )
{
ANNOUNCE( apply( adder(1), 2 ) );
ANNOUNCE( apply( adder(3), apply( adder(4), 5 ) ) );
ANNOUNCE( apply( compose( adder(5), adder(6) ), 7 ) );
}
------------------------- End of version 1 ------------------------
Here is a variation to ponder. Replace the section between /* --- A --- */
and /* --- B --- */ with the following:
-------------------------- Start of replacement code --------------------
/* Now a macro for defining new function-creating functions... */
#define FUNCMAKER(funcmaker,argdecls,setupcode,bodyname,bodycode) \
int bodyname( d, arg )\
struct{argdecls} *d; \
int arg; \
{ bodycode; } \
Func *funcmaker \
argdecls \
{ \
Func *result; \
struct{argdecls} *d; \
\
result = (Func *) malloc( sizeof( Func ) ); \
result->c = bodyname; \
*((void **) &d) = malloc( sizeof( struct{argdecls} ) ); \
result->d = (void *) d; \
setupcode; \
return result; \
}
/* Definitions for "adder" function type... */
FUNCMAKER(adder(i), int i;, d->i = i,
adderBody, return d->i + arg)
/* Definitions for composing functions... */
FUNCMAKER(compose(f,g), Func *f; Func *g;, { d->f = f; d->g = g; },
composeBody, return apply( d->f, apply( d->g, arg ) ) )
------------------------- End of replacement ---------------------
This is totally unpolished, but both versions above work on my machine.
The question I'm interested in is, given that you hide the right stuff in
include files and subroutine libraries, how TWISTED is this method to use
in the places where you'd want "first class, composable, anonymous functions?"
This is actually something I want to do sometimes (for instance, passing an
option to a compare function that I'm passing to a sort routine), so I'm
really interested in y'all's oppinions.
--Steve Witham, The Squeaky Wheel
Not-the-fault-of: SMDS, Inc.
If-All-Else-Fails: (508)369-7398jwb@cepmax.ncsu.edu (John W. Baugh Jr.) (01/09/91)
Apparently Strachey coined the term "first class" (according to Harland in Polymorphic Programming Languages). The reference is: C. Strachey, Fundamental Concepts of Programming Languages, Oxford University Programming Research Group (1967). Can anyone get their hands on this? John Baugh jwb@cepmax.ncsu.edu
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/09/91)
In article <289@smds.UUCP> sw@smds.UUCP (Stephen E. Witham) writes: > To me, the "power" of a language has to do with what concepts you can express > DIRECTLY. But what's direct? Why are pointers to functions direct, if pointers to structures containing blah blah blah are indirect? I think this gives you the same problem as trying to qualify ``has.'' I prefer to keep ``power'' an objective term, and to qualify it with further objective terms: memory use, run time, code complexity (by any sensible measure), etc. Words describing syntax can be objective too, though I prefer to keep them well separated from the syntactic terms. [ function composition routines ] > The question I'm interested in is, given that you hide the right stuff in > include files and subroutine libraries, how TWISTED is this method to use > in the places where you'd want "first class, composable, anonymous functions?" Looks like it works to me, and it's not sufficiently twisted that I wouldn't use it. ---Dan
augustss@cs.chalmers.se (Lennart Augustsson) (01/10/91)
My unnamed C-functions seems to have caused some misunderstandings
and controversy so here is an explanation. (I now promise that
this is my last posting on this subject, no matter how badly it will
be misunderstood.)
When I explained unnamed C-functions in C i said:
The C-function expression should also behave as a normal C expression,
i.e. it can be sent as an argument, returned etc.
This clearly states that returning an unnamed function is ok.
This means that my compose example works. (If we play a game and I define
the rules and then follow them, you cannot accuse me of cheating,
but you *can* complain about the rules). It may be unreasonable to
require anonymous C-functions to be returnable, but that's another
matter. To forestall a discussion of this I'll give a few of the
objections to having unnamed returnable C-functions:
- It's unimplementable.
This is clearly wrong since many languages have them.
- It's to hard to implement.
I think not, but that's a matter of opinion.
- It goes against the "spirit" of C.
This is an argument I could buy, an implementation of them
would be somewhat alien in C, but not more than some of the things
in C++.
Since the unnamed functions caused some confusion I'll present some
interpretations on what they could mean. I must now return to my
nitpick mode and distinguish between C-functions and pointers to
C-functions. (I should never have stopped nitpicking.)
What does "return int ANONYMOUS(int x) { return x+1; };" mean?
1. C has "first class" (whatever that is) pointers to functions,
but not functions (i.e. functions cannot be sent, returned etc.)
1a. "int ANONYMOUS(int x) { return x+1; };" represents a C-function value.
This means that the return statement has a type error (you can only
return pointers to functions), so this cannot be the intended meaning.
1b. "int ANONYMOUS(int x) { return x+1; };" follows the C rule that
a function automatically gets the "&" (address-of) operator inserted
to get a pointer.
This would also be an error if "int ANONYMOUS(int x) { return x+1; };"
is a function value. It would be like saying "return &5;", since
you cannot apply & to a value, only to an lvalue.
1c. The value "int ANONYMOUS(int x) { return x+1; };" is automagically
somehow turned into an lvalue (by allocating space for it and
storing it and then giving this address as the result).
This makes unnamed C-functions into a special case, but if you want them
to work this is the way to go. Memory can be allocated on the stack or in
the heap (or more generally: somewhere that is automatically deallocated
when leaving the function or where the extent is unlimited). Memory
cannot be allocated on the stack since this would make it impossible to
return the pointer to it. This seems to be the version that Dan and
Karl thought I meant. Memory can also be alloacted in the heap so that
the address is valid after returning, this is a solution that works.
(If C has no heap then returnable pointers to unnamed C-functions
cannot be implemented.)
Notice that I agree entirely with Dan(!!) that allocatablity is the crucial
point here (but also see 2). The point I'm trying to make is that if
you add unnamed C-functions that can be returned (I don't think this
is unreasonable since you can return unnamed ints), this implies
allocatability (or whatever you like to call it).
2. C has "first class" C-functions (not just pointers to them).
This means that function values are now all right and need not be
turned into pointers to be returned etc. This is the status that
structs have in C (but you cannot have unnamed struct).
The meaning of returning a C-function is now simply that you return
the value of it.
A small example may illustrate the point
/* mkaddc takes an int and returns a function that adds this */
typedef int intintfun(int);
intintfun mkaddc(int c) {
return intintfun ANONYMOUS(int x) { return x+c; }
}
compare this with a function returning a struct
typedef struct { int z; } intstruct;
intstruct makec(int c) {
intstruct s;
s.z = c;
return s;
}
(in GCC which allows unnamed structs you can write
typedef struct { int z; } intstruct;
intstruct makec(int c) {
return (intstruct){ c };
}
)
Notice that the struct example is very much like the functions example:
- the returned value contains the value of an argument.
- the returned value is not a pointer.
In solution 2 there is no need to add special rules that converts
function values to pointers, the values themselfes can be returned.
I think Dan (maybe) misunderstood my posting that said that unnamed
C-functions would add semantic power. First, I was speaking about
unnamed C-functions specifically, unnamed structs would add no power.
Second, I did not want to imply that unnamed functions could be
added without further implications, i.e. if you choose 1 you have
to make them automatically allocated, if you choose 2 you have to
introduce C-functions (not pointers) as first class objects.
In my article that said that unnamed functions would give extra power
I think I said (I've lost the article) that they should be added in a
reasonable way, without explaining what I meant by reasonable. What I
meant was that unnamed C-functions should not be inferiour to other
unnamed values in C, e.g. they should be returnable. This has, as we
can see, rather big implications. Since a (working) extension of C
would entail so big changes you might have objections to making it.
-- Lennart Augustsson
[This signature is intentionally left blank.]jpiitulainen@cc.helsinki.fi (01/10/91)
(On first-class procedures and whether they need be named.) Here's a recent reference, from David Gelernter and Suresh Jagannathan: Programming Linguistics, 1990, The MIT Press (ISBN 0-262-07127-4). The context is Algol60 and call-by-name. The colons mark quoted text, a sequence of three periods marks omitted text. I've included much context because I think it is needed in order for the definition to be understood the way they intended it. Note that what follows the definition below is to be thought of as being entailed by the definition. : Definition 3.2 The first-class objects within language L are the ones : that can be yielded as values by expressions within L. The authors proceed to ask what the definition entails, answering that first-class objects can be passed as parameters to subroutines, returned as values of functions and assigned to variables. Then they ask what it is like to have first-class procedures: : Consider a hypothetical language that includes first-class : procedures: it includes expressions E such that E yields a procedure. : ... E(z) is a legal invocation, in particular an invocation of : whatever procedure is specified by expression E. ... we should be : able to write f := E ... we should be able to write h(E) ... we : should be able to return E ... If A is an array, we should be able to : write ... A[1] := E. Finally on the issue of not having a name---remember that the authors are explaining call-by-name here. : ... We can think of a call-by-name application in terms of a : call-by-value application in which each of the actuals are unnamed : procedure objects. : : It's interesting that Algol60 also allows procedures (more accurately : procedure names) to be passed explicitly and directly as actual : parameters. (Procedures are not allowed to be returned as results of : an application, however; a procedure definition is considered to be a : declaration, not a value-yielding expression). This is another : partial approach to the freedom implicit in first-class procedures. : It allows procedures as arguments, but requires that they be defined : and be given a name first; they can't be made up on the spot. This : isn't quite the same as the invocation h(E), where E is improvised : for the occasion and not defined anywhere else, much as in h(3+4), : 3+4 is an arithmetic expression that is improvised on the spot. The last paragraph is the key here: Gelernter and Jagannathan expect E to be like arithmetic expressions. By the way, the authors also call, in footnote, the term "first-class" "the residue of an inept metaphor": : First-class objects are said to be "first-class citizens" of the : language, assuming that a programming language can somehow be : compared to a state whose citizens are its data objects---which it : cannot, or at any rate just barely. Well, I hope that I have not quoted more than is fair. The book is well worth a read or two. Jussi Piitulainen
ske@pkmab.se (Kristoffer Eriksson) (01/12/91)
In article <1990Dec29.110202.3862@mathrt0.math.chalmers.se>, augustss@cs.chalmers.se (Lennart Augustsson) wrote: >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. > > 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. Actually, the situation is not quite that bad. For the purpose of passing one of Dan's structure-emulated pseudo functions to an existing function that only knows about normal C functions, all you have to do is write a third (normal) function that knows how to call one of Dan's functions, and pass this third function to the library function (or whatever function it was). As long as you don't need to keep an unlimited number of such functions alive at one and the same time, this method works well. You only need these intermediate functions during the call to the library function, even if you have lots of Dan's pseudo functions around, so they can be ordinary statically allocated C functions, and a practical trick is to make them reconfigurable and set up each just prior to each use. For examples like qsort(), you would only need one of these intermediate functions. There would be a problem if you were using many library functions that needed to be passed multiple functions and possibly store some of them for later use, but there aren't many such functions in the ordinary C libraries, and if you're writing your own function library, you don't need this method since you can easily make them accept Dan's pseudo-functions directly. Thus, I would say that using Dan's method (lacking real first-class functions) is not such a disaster as you make it out, except if you have very special needs. (Maybe that wasn't such an important point in your argument, but you did make a point out of it.) In article <1991Jan5.182428.615@mathrt0.math.chalmers.se>, augustss@cs.chalmers.se (Lennart Augustsson) wrote: > The bounded number of C-functions is the real reason why a >C-function compose (for C-functions) cannot be written in C. Since >composition can give you an unbounded number of different C-functions, >but there is only a bounded number of them available it has to fail. >(This is why Kristoffer Eriksson "solution" cannot be made to work >in the general case.) The supply of memory is bounded, too, yet we seem to manage. Thus I gather that for many purposes a fixed, but dynamically allocatable, supply of functions is sufficient. Since Lennart challenged me by mail to prove that I could write such a function (whether or not this is the variety that he refers to as the "general" case above), and I think this function may be of more general interest, I will append it at the end of this posting. Still, I do grant that this method may not be sufficient or may be impractical for applications consuming big numbers of dynamic functions. After all, the practicall limit on the number of functions is a lot lower than for the supply of memory. We have so far concentrated solely on completely portable implementations of composed functions. But looking at how many other features available in the C programming environment are implemented, we see that many of them are of a kind that can not be expressed solely by C "builtin" features. Many are in fact implemented as assembler routines or system dependant nonportable C functions or operating system calls, for instance malloc, another function for dynamic allocation of resources. The C libraries are a means of providing C extensions, and they need not necessarily be portable. The portable inter- face is in the function call interface of the libraries. Therefore I will also append one implementation of _unlimited_ dynamic composed function creation. This maybe doesn't touch the subject of first class functions in C unless you take the library interface argument seriously, but I think the routines in themselves are interesting and maybe even useful to somebody. The implementation is obviously not portable, but is on the other hand not overly complicated either. It works on my 68000 Unix system, and I also give a modification for MSC on MSDOS. I don't know whether it is possible to make it work on PC-Unixes, but then Intel processors have always been special. I didn't get it to work on SCO Xenix, since the operating system wouldn't allow me to read the code section, but I would regard that as mostly a deficiency (also called "feature") in the operating system rather than in the general idea of the implementation. The implementation depends on there not being too strict boundaries between the code and data sections in the execution model. My impression is that many processors can accept that, although not all. Firstly, my portable but bounded compose() implementation. This requires ANSI C, unless you want to type a lot. To reconfigure the supply of allocatable functions, set NUM_FUN to the new number of functions, add or remove decl_fun()'s to the desired number of functions, and add function names to the initialization of funarray. One could probably make the preprocessor help with parts of this, but I don't want to overdo this, and besides, the preprocessor might overflow. /* composed.c: */ /* -------- Dynamic composition package begins ----- */ /* By Kristoffer Eriksson, ske@pkmab.se, 1991. */ #define decl_fun(num) \ int composed_ ## num(int x) \ { return(descrarray [num].f1( descrarray [num].f2(x) )); } #define NUM_FUN 5 struct fun_descr { int (*f1)(), (*f2)(); }; typedef int (*funptr)(int); static next_fun = 0; struct fun_descr descrarray [NUM_FUN]; /* Create a supply of to-be composed functions to allocate from. */ decl_fun(0); decl_fun(1); decl_fun(2); decl_fun(3); decl_fun(4); /* Array for referencing the functions. */ funptr funarray [] = { composed_0,composed_1,composed_2,composed_3,composed_4 }; funptr compose(funptr fun1, funptr fun2) { if (next_fun >= NUM_FUN) return 0; descrarray [next_fun].f1 = fun1; descrarray [next_fun].f2 = fun2; return(funarray [next_fun++]); } /* Matching function destruction function omitted. The allocation/deallocation * could of course be more sofisticated too, but this is just a demonstration. */ /* -------- Dynamic composition package ends ------- */ Next, my unbounded (except by memory) but non-portable compose() implementation. This does not require ANSI C, except for the fact that I used ANSI-style function declarations. A replacement for one of the functions for use on MSDOS is at the end. This package should port without too much difficulty to systems that satisfy the assumptions that are made about the execution model. Other system are out of luck. In this implementation you deallocate composed functions simply by calling the ordinary free() on them. /* composeu.c: */ /* -------- Unlimited dynamic composition package begins ----- */ /* By Kristoffer Eriksson, ske@pkmab.se, 1991. */ #include <memory.h> #include <malloc.h> typedef int (*funptr)(int); #define PLACE_HOLDER 12345678 /* Change this to a 16-bit value if 16-bit pointers are used. */ /* This value may have to be adjusted in order not to match any instruction sequence in the function template(). */ /* Template function that is copied to make new functions. The place holder * makes it possible to locate the place of the values that the local function * pointers are initialized to in the binary image of the function, in most * ordinary computer architectures. A more serious obstacle may be systems * that refuse to execute out of the data segment or copy from the text segment. * * Sometimes there are special system calls that can be used to turn a memory * area into an executable segment (e.g. execseg() in SCO Xenix), or special * calls to allocate new executable memory, or both. They should be put to use * by compose() in that case. There may also be operating system deficiencies * that make the whole approach impossible. In SCO Xenix, for instance, copying * from the code segment seems to be disallowed, which propably means that to * implement this on Xenix you'ld have to define template() as an array initia- * lized with suitable machine code (you could copy it from the assembly output * of the compiler for the original C version of the function), or you'ld have * to compile template() in a segment of it's own and somehow link it in as a * data segment. I don't know about the other i386 Unix versions. */ int template(int x) { funptr f1 = (funptr)PLACE_HOLDER, f2 = (funptr)PLACE_HOLDER; return(f1(f2(x))); } int after_template(void) {} char *memfind(char *mainstr, char *substr, int mainlen, int sublen) { int i; /* Find a substring in another string. */ if (mainlen <= 0) return(0); if (sublen <= 0) return(mainstr); mainlen -= sublen; while (mainlen-- >= 0) { if (*mainstr == *substr) for (i = 0; mainstr[i] == substr[i]; ) if (++i >= sublen) return(mainstr); ++mainstr; } return(0); } char *insert_funptr(char *area, int len, funptr fun) { funptr search_pattern = (funptr)PLACE_HOLDER; char *where; /* Find the place holder in a copy of the template function, and * insert the desired function pointer there in stead. */ where = memfind(area, (char*)&search_pattern, len, sizeof(search_pattern)); if (where == 0) write(2, "Compose() does not currently work on this machine\n", 50); else memcpy(where, (char *)&fun, sizeof(search_pattern)); return(where); } funptr compose(funptr fun1, funptr fun2) { char *res; char *where; int funsize = (char *)after_template - (char *)template; /* Allocate a fresh copy of the template function. */ if ((res = malloc(funsize)) == 0) return(0); memcpy(res, (char *)template, funsize); /* Insert the two function pointers in the right places. */ where = insert_funptr(res, funsize, fun1); if (where == 0) return(0); where = insert_funptr(where + sizeof(fun1), funsize - (where - res) - sizeof(fun1), fun2); if (where == 0) return(0); return((funptr)res); } /* -------- Unlimited dynamic composition package ends ------- */ /* -------- Replacement insert_funptr() for MSDOS ------------ */ /* Under MSDOS, the vanilla version may work if compiled to a .COM file, * with the same segment used for both code and data. To make an .EXE file, * you have to use the "large" memory model in order for the system to look * in the right segment for the allocated functions, and then you need the * following replacement for insert_funptr, since the function pointer values * are being assigned in 16 bits chunks. (This works for v5.1 at least.) * * With Microsoft C, use for instance the command CL -AL on all modules. */ #ifdef MSDOS char *insert_funptr(char *area, int len, funptr fun) { funptr search_pattern = (funptr)PLACE_HOLDER; char *where; where = memfind(area, (char*)&search_pattern, len, 2); if (where == 0) write(2, "Compose() does not currently work on this machine 1\n", 52); else memcpy(where, (char *)&fun, 2); where = memfind(area, (char*)&search_pattern + 2, len, 2); if (where == 0) write(2, "Compose() does not currently work on this machine 2\n", 52); else memcpy(where, (char *)&fun + 2, 2); return(where); } #endif /* -------- Replacement Insert_funptr() ends ----------------- */ Lastly, I give the test program I got from Lennart (it does what it should, so it would be pointless for me to write one myself). You can compile the test program and the composition packages as separate files that you link together if you like. Set MAXFUNC to the number of composed functions you want to test (the same or less than NUM_FUN if it is the bounded version you test). The program first composes a number of functions and stores them in an array, and then calls them to check the results. /* comptest.c: */ /* -------- Test program begins ------------------------------ */ #include <stdio.h> typedef int (*intintfun)(int); intintfun compose(intintfun, intintfun); #define MAXFUNC 5 #define TESTDATA 42 int id(int x) { return x; } int suc(int x) { return x+1; } main(int argc, char **argv) { intintfun adders[MAXFUNC+1]; int i; adders[0] = id; for(i = 1; i <= MAXFUNC; i++) { adders[i] = compose(adders[i-1], suc); if (adders[i] == 0) { printf("Sorry, ran out of functions at %d\n", i); exit(1); } } for(i = 0; i <= MAXFUNC; i++) if ((*adders[i])(TESTDATA) != TESTDATA+i) { printf("Sorry, adder %d failed\n", i); exit(1); } printf("You may have a working compose!\n"); exit(0); } /* -------- Test program ends -------------------------------- */ I'd still use my original macro implementation whenever it satisfies my needs, though, since it is both portable and needs no reconfiguration. -- Kristoffer Eriksson, Peridot Konsult AB, Hagagatan 6, S-703 40 Oerebro, Sweden Phone: +46 19-13 03 60 ! e-mail: ske@pkmab.se Fax: +46 19-11 51 03 ! or ...!{uunet,mcsun}!sunic.sunet.se!kullmar!pkmab!ske
bbc@rice.edu (Benjamin Chase) (01/13/91)
There is an unfortunate limitation of Kristoffer Eriksson's code, and
of other purported+ implementations of a composition function for C
functions. These implementations of function composition have not
been for C functions, but rather for monadic C functions that map
"int"s to "int"s.
+("purported" is perhaps too strong a word; they didn't claim, but
seemed to have merely overlooked)
Can a (reasonably efficient and portable) compose function for (all) C
functions be written in C?* I'm still waiting for that existence
proof... :-) I believe that it cannot be done. Actually, I'm not
really waiting for the existence proof. I don't really care to see
such code.
(Note that "reasonably efficient" is an important and subjective
restriction here. I will let Dan Bernstein be the arbiter for
"reasonably efficient and portable.")
*(Note that this is not the same question as: "Does C have composable
functions?")
--
Ben Chase <bbc@rice.edu>, Rice University, Houston, Texasquale@picard.cs.wisc.edu (Douglas E. Quale) (01/13/91)
In article <4762@pkmab.se> ske@pkmab.se (Kristoffer Eriksson) writes: >As long as you don't need to keep an unlimited number of such functions >alive at one and the same time, this method works well.... > >The supply of memory is bounded, too, yet we seem to manage. Thus I gather >that for many purposes a fixed, but dynamically allocatable, supply of >functions is sufficient. It's an unfortunate fact of life that all machines are finite. No language can give you an infinite number of *anything* on a finite machine. The question is are you satisfied with a language that forces you to accept an arbitrarily predetermined and limited number. This implementation which would undoubtedly be perfectly acceptable to Dan Bernstein *compiles* in a limit on the number of composed functions arbitrarily. This makes a decision at compile time that should be made at run time. It is one of the greatest sources of power of a language like Scheme that these decisions are delayed as long as possible. If Kristoffer adds more memory to his computer, he is rewarded by the privilege of recompiling every C program he has written to take advantage of the extra space. It's bad enough if Kristoffer decides that I will never need more than 1000 composed functions at once. Suppose I use only 1 composable function -- 999 of the preallocated functions and array slots sit unused. Useless. Fixed size tables DON'T save space, they waste it. C encourages programs with built in arbitrary limits. The AT with 512K gets just as many composable functions as the YMP with 512MW. A perfect example is the typical C compiler that can trace its proud lineage back to the original PCC (pessimizing C compiler). The compiler internal table sizes are fixed. Anyone compiling a large program is almost certain to get a turgid error message. Upon recompiling after adding some random flag as -Wc,a20000 a *different* internal table overflows and the compilation has to be restarted after adding another random flag. (I get pissed and use gcc instead, but this brings other problems.) (As a side note, I should add that the creators of Unix have given a rational reason for the decision to use fixed size tables in the Unix kernel and in pcc, both of which were developed on machines with an extremely cramped address space.) > >We have so far concentrated solely on completely portable implementations >of composed functions.... One of the most important tests of a language is how it can solve a problem in a portable way. If you are going to admit that C can't handle something as simple as function composition portably, then you've already thrown in the towel. > ... One could probably make the >preprocessor help with parts of this, but I don't want to overdo this, >and besides, the preprocessor might overflow. Wonderful. The preprocessor has fixed table sizes too. (It must have been written in C.) To paraphrase a well known computer curmudgeon, I expect the *computer* to do the bean counting! That's what they're for! To sum up the C composable function implementation -- - limited to a compile-time fixed number of functions - destructor must be explicitly called and most importantly, as astutely pointed out by another netter, - the solution _doesn't_ solve the problem. Who cares about functions from ints to ints. I want a polymorphic compose function, and C can't do it (hence C++). While you're chewing on that one, how about an function to return the fixed point (the Y combinator). C fans, the ball is in your court. All the C implementations of 'composable' functions have just lead me to believe that some people will use a hammer for anything, even driving screws. I hate to think what they do when they try to cut with it. -- Doug Quale quale@picard.cs.wisc.edu
ske@pkmab.se (Kristoffer Eriksson) (01/13/91)
In article <BBC.91Jan12160209@sicilia.rice.edu> Benjamin Chase <bbc@rice.edu> writes: >There is an unfortunate limitation of Kristoffer Eriksson's code, and >of other purported+ implementations of a composition function for C >functions. These implementations of function composition have not >been for C functions, but rather for monadic C functions that map >"int"s to "int"s. > >+("purported" is perhaps too strong a word; they didn't claim, but >seemed to have merely overlooked) For myself I can tell you that I haven't overlooked it. I acknowledge that my routines have that limitation, it just didn't seem worth mentioning it, since nobody ever talked about anything else. From the very first beginning, it has all been about int-to-int-mapping functions. Whether it should have been so or not is another question, at least from my position. >Can a (reasonably efficient and portable) compose function for (all) C >functions be written in C?* That depends on your goals (for instance, ease of use of the composed funcions and how complete you need it to be). I agree that it would be harder, and for certain (rather obvious) combinations of goals impossible. Treating the composed functions as ordinary C functions would make it hard to legally declare the compose function, for instance, so you would always have to cast the results returned by it. It could probably be added as a non-portable library function, this time written in assembler not C, though. I still want to point out that there are two ways of extending C. One way is to change it's syntax and semantics, which requires changing the compiler. The other way is to add library functions, sometimes (but not always, which may be considerd one of the strengths of C) written in other languages. The latter method does not require changing the compiler, and so is obviously much easier to do for most of us. At least this means there is seldom a total stop-gap to extending the language, if there is something you really desire. I also want to point out that I am still not making any claims regarding the original question about first-classnes of C functions or function pointers, although I hope some of it may add to the total picture. -- Kristoffer Eriksson, Peridot Konsult AB, Hagagatan 6, S-703 40 Oerebro, Sweden Phone: +46 19-13 03 60 ! e-mail: ske@pkmab.se Fax: +46 19-11 51 03 ! or ...!{uunet,mcsun}!sunic.sunet.se!kullmar!pkmab!ske
sw@smds.UUCP (Stephen E. Witham) (01/18/91)
In article <BBC.91Jan12160209@sicilia.rice.edu>, bbc@rice.edu (Benjamin Chase) writes: > Can a (reasonably efficient and portable) compose function for (all) C > functions be written in C?* I'm still waiting for that existence > proof... :-) I believe that it cannot be done. Actually, I'm not > really waiting for the existence proof. I don't really care to see > such code. Well, since you don't want to see it, I won't burdon you :-). Actually, I did think about it in my "purported" implementation of compose. At first glance, you're asking for something against the way C works with data types: a function that works even though you feed it arguments of different types at different times. For comparison, try writing a function that adds two numbers and returns a long--only the arguments may be chars, unsigned chars, shorts, unsigned shorts, ints, unsigneds or longs, or a combination. The original question was about "first-class" composable functions. I'm one of those who thinks that "first-class" is relative to what you can do with other things in the same language, so I think you're changing the rules here. But... Probably the most efficient way to do what you want would be to write different compose functions for different types of functions. On the other hand, since we're faking functions with structures, we might as well put declaration information into the structures. This might slow down the creation and composing of functions, but not their application. --Steve Witham Not-the-fault-of: SMDS, Concord, MA
quale@picard.cs.wisc.edu (Douglas E. Quale) (01/20/91)
In article <301@smds.UUCP> sw@smds.UUCP (Stephen E. Witham) writes: >In article <1991Jan13.045906.6210@spool.cs.wisc.edu>, >quale@picard.cs.wisc.edu (Douglas E. Quale) is ostensibly writing about the >various simulations of composable functions that have been posted here. >He talks about: > 1) The evils of fixed-size tables, as in Kristoffer Eriksson's posting. > 2) The evils of non-portability (Mr. Eriksson mentioned doing something > non-portable). > 3) The problem that if you allocate something, you have to explicitly > free it in C. > 4) That the "compose" functions seen so far only work on one type of > function. They are not polymorphic. >Finally, he complains that... > 5) "Some people will use a hammer for anything, even driving screws." > >Numbers 1 and 2 have to do with Mr. Ericsson's posting, and not, as Mr. >Quale seems to think, the C language or composable functions. If you know a portable method implementation in C that removes the restriction to fixed size tables, post it. Mr. Eriksson said he *didn't* know a portable way to fix this problem in C, so it *is* a C language problem. > >Number 5 is nasty. First of all, it's not all that clumsy, although >it's not Scheme. But mainly, this is something we were specifically >challenged to do. Now you're making fun of us for trying?? Also, given >one language at a time to work with, if I'm driving more nails than screws, >I'll use the hammer language instead of the screw language. > Not all that clumsy is a value judgement that you are entitled to make, and I suppose then that I'm entitled to chuckle as well. (The C code is somewhat larger than (define (compose f g) (lambda (x) (f (g x)))), and I'd really like to see you prove that the C code works, and the C implementation does have 69 different arbitrary limits built in that don't exist in a lisp solution, but it's your call.) If you have to drive nails and screws, I'd use a language that provides a full toolkit instead of just a hammer. -- Doug Quale quale@picard.cs.wisc.edu
new@ee.udel.edu (Darren New) (01/22/91)
In article <BBC.91Jan21120817@sicilia.rice.edu> you write: >When I think of "function composition", I usually think of it in a >mathematical sense. For such a function "compose(f,g)", the >requirements on the two parameters that come to mind are that the >domain of "f" matches the range of "g", that the domain of >"compose(f,g)" matches the domain of "g", and that the range of >"compose(f,g)" matches the range of "f". (The definitions of >"matches" in the previous sentence is left as an exercise to the >reader.) On this mathematical bent, it also seems reasonable to >require that the functions "f" and "g" are pure functions, though I >doubt this additional restriction will make my challenge any easier. Hmmm... I don't know that I've ever seen a mathematical system where the functions are not pure, since I've always seen functions described as a set of <domain-element, range-element>. I've also always seen compositions, as well as "apply" and other functions that take functions, either defined only to work on integer|->integer functions with the assumption that both the input and output integers are unlimited in range and may be coding something else (like a program or a pair of integers), or as being a class of functions all with the same (or no) name (somewhat like overloaded functions), or functions that map functions onto other functions of the same type (as in type theory). (I'm rusty on the type theory, so no flames, please.) Since C has neither unlimited integers nor general overloaded functions, I don't know that "the definition of matches" (left to the reader) should not exclude certain restrictions. For example, you say "the range of compose(f,g) matches the range of f". If I take "matches" to mean "assignment compatible in C" then it becomes trivial to show that for each f with a different return type you will need a different compose. Similarly with the range of g. Hence, the "matches" is why restricting compose to work only on integer identity functions won't work, as there are many f's and g's which take one integer and return one integer (i.e., with the same ranges and domains), and assumedly any compose which works on one should work on the others. However, the fact that you cannot change the range of f and still have the range of compose "match" it does not seem to be saying that functional composition is impossible in C. (Maybe it isn't, but I would not consider this to be the reason.) >>I'm one of those who thinks that "first-class" is relative to what >>you can do with other things in the same language, so I think you're >>changing the rules here. > >What rules have I changing in issuing my challenge? >That all challenges must have trivial solutions? No, that first-class functions must be able to accept and return arbitrary types, whereas first-class variables need not. -- 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 ... +=+=+=
karl@ima.isc.com (Karl Heuer) (01/23/91)
In article <BBC.91Jan21120817@sicilia.rice.edu> Benjamin Chase <bbc@rice.edu> writes: >[defend the idea that compose() should be polymorphic] Well, if you put it that way, then C doesn't even have a way to write a function% to add two numbers together, since you have to decide at compile-time what the domain and range will be. Karl W. Z. Heuer (karl@ima.isc.com or uunet!ima!karl), The Walking Lint ________ % To avoid trivial macro solutions: I want to be able to take the address of the resulting function. No fair converting everything to double, either; I may have a machine where some large integers can't be represented as floats.
eerke@cs.kun.nl (Eerke Boiten) (01/23/91)
OK everyone, it's time to start the polymorphism vs. overloading war again! In article <1991Jan22.200615.4518@dirtydog.ima.isc.com> karl@ima.isc.com (Karl Heuer) writes: >In article <BBC.91Jan21120817@sicilia.rice.edu> Benjamin Chase <bbc@rice.edu> writes: >>[defend the idea that compose() should be polymorphic] >Well, if you put it that way, then C doesn't even have a way to write a >function% to add two numbers together, since you have to decide at compile-time >what the domain and range will be. Addition is *not* polymorphic. There is no obvious meaningful interpretation of the addition of two characters, for instance (I suppose C has one anyway :-)). Addition is (in languages with various "types" of "numbers") an *overloaded* term for a number of operations that implement in some cases the abstract addition operation on numbers, plus some odd things at the borderline of the type range or precision. -- Eerke Boiten Department of Informatics (STOP Project), K.U.Nijmegen Toernooiveld, 6525 ED Nijmegen, The Netherlands Tel. +31-80-652236. Email: eerke@cs.kun.nl
sw@smds.UUCP (Stephen E. Witham) (01/26/91)
In article <BBC.91Jan21120817@sicilia.rice.edu>, bbc@rice.edu (Benjamin Chase) writes: > Long ago, I challenged: > > >> Can a (reasonably efficient and portable) compose function for (all) C > >> functions be written in C? ... I believe that it cannot be done. ... I'm omitting most of his posting (about a response of mine to his challenge) here... > I admit that my challenge for an implementation of function > composition suited _my_ tastes of what would constitute a useful > implementation of "function composition", and may bear no relation to > anyone else's. If that is what you mean by "changing the rules", then > certainly I am guilty. Nevertheless, my challenge remains unanswered. Ben, it's true that your challenge hasn't been answered, at least by me, and I want to explain my view of what HAS been going on in this thread. First of all, note the "Subject" line, "Whether C has first-class" blah, blah. I remember someone asking that question LONG, long ago. The way I took that original question (based on the phrase "first-class," which to me is relative to how things are done in the rest of the language) was, "Can C compose functions as well as it can do other things?" And the eventual answer was, "Well, almost as well." Then you came in and said, "This doesn't answer the original question because it's not polymorphic." (paraphrase). That's what I meant by "changing the rules." It seemed to me that the ORIGINAL challenge HAD been answered, but you were walking into the middle of a discussion with a harder challenge, and then berating us for having not having answered it already. Maybe what happened was, you were the original poster on this thread, but your question got watered down (even in the Subject line) before I joined in. If so, I'm sorry, but I wish you had explained that. Now to your challenge. I think you COULD whip up something, using variable-argument functions, structures with type information in them, a garbage collector, etc., that would meet the letter of your challenge. It would be kind of painful, which I think is sort of your point. BUT. Composing functions is something really neat that you might actually want to do in the context of a C program (I know because I've needed to myself), and it's actually reasonable to do. The sensible, less painful way is not to try to imitate Lisp in every detail, but to do it the way you do other things in C. Meaning, partly, that functions have fixed numbers of fixed-type arguments, functions with different numbers or types of arguments are in turn of different types, and when you want to do the same operation on two incompatible data types, then you write two different functions. Also, complex entities that are created at run time go into dynamically-allocated structures that have to be freed if you want the space back. This is terrible? I mean, Why pick on C? Why talk about doing something in C if you don't like the way things have to be done there? --Steve Witham Not-the-fault-of: SMDS, Concord, MA
quale@picard.cs.wisc.edu (Douglas E. Quale) (01/26/91)
In article <305@smds.UUCP> sw@smds.UUCP (Stephen E. Witham) writes: > >Now to your challenge. I think you COULD whip up something, >using variable-argument functions, structures with type information in them, >a garbage collector, etc., that would meet the letter of your challenge. >It would be kind of painful, which I think is sort of your point. > We'll forget polymorphism. With C it's hopeless. (Hence C++). > >two incompatible data types, then you write two different functions. Also, >complex entities that are created at run time go into dynamically-allocated >structures that have to be freed if you want the space back. This is terrible? > Show me an implementation that doesn't have a fixed limit on the number of functions that can be composed. The only portable C implementation demonstrated so far has an arbitrary limit compiled in. How do I dynamically allocate function objects in C?? -- Doug Quale quale@picard.cs.wisc.edu
quale@picard.cs.wisc.edu (Douglas E. Quale) (01/27/91)
In article <3576:Jan2622:55:2991@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <1991Jan26.132913.11358@spool.cs.wisc.edu> quale@picard.cs.wisc.edu writes: >> Show me an implementation that doesn't have a fixed limit on the number of >> functions that can be composed. The only portable C implementation >> demonstrated so far has an arbitrary limit compiled in. > >No. There have been at least seven implementations presented in this >ongoing discussion, of which the first (mine) was a portable C >implementation of first-class, dynamically allocated, composable >functions. > My apologies Dan, I didn't save your code when it came by. If you (or anyone else, for that matter) still has a copy I would appreciate having it emailed to me. It's nonobvious to me how C can provide first-class dynamically allocated functions. First-class dynamically allocated composed functions should look like function pointers because the functions that use them shouldn't have to know that they were dynamically allocated. And they especially shouldn't have to know that they are composed. Suppose I want to curry or uncurry functions, or for instance provide a fun C f x y = f y x ? If every use of a function parameter in the program has to know how the function was created, this would seem to be a rather marginal definition of first class. -- Doug Quale quale@picard.cs.wisc.edu
freek@fwi.uva.nl (Freek Wiedijk) (01/28/91)
quale@picard.cs.wisc.edu (Douglas E. Quale) writes: > How do I >dynamically allocate function objects in C?? Huh? How do you dynamically allocate NON-function objects in C?? Answer: you use a library routine called malloc. So, all you need is a routine called "falloc" in your library... While the implementation of falloc clearly can't be portable, the same holds for malloc. Freek "the Pistol Major" Wiedijk E-mail: freek@fwi.uva.nl #P:+/ = #+/P?*+/ = i<<*+/P?*+/ = +/i<<**P?*+/ = +/(i<<*P?)*+/ = +/+/(i<<*P?)**
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/28/91)
In article <21245@yunexus.YorkU.CA> oz@yunexus.yorku.ca (Ozan Yigit) writes: > Yes, you were able to write an interpreter that contained said > functionality, minus the scoping details. > Amazing. 'Twas hardly amazing. What amazes me is that there are *still* people posting to this newsgroup asking questions like ``Ya know, I haven't seen any portable first-class composable function implementations that don't have arbitrary limits. Is this because they are impossible, or is there some sneaky way?'' Then again, I was also surprised that there are people who don't know how to sort machine integers in linear time... ---Da
sw@smds.UUCP (Stephen E. Witham) (01/29/91)
In article <1991Jan26.132913.11358@spool.cs.wisc.edu>, quale@picard.cs.wisc.edu (Douglas E. Quale) writes: > > We'll forget polymorphism. With C it's hopeless. (Hence C++). Yeah. The impossible part is composing functions that RETURN different types. You could make all your functions deal with some "universal" type, like a pointer to a void, which you would cast to a pointer to a structure full of whatever, but that's pretty awful. By the way, C++ is sometimes implemented as a translator-into-C, so if you want to do something C++ does, but in C, ALL YOU HAVE TO DO :-} is make sure you're as thorough and methodical as a C++ compiler, and put up with some horrible syntax! > Show me an implementation that doesn't have a fixed limit on the number of > functions that can be composed. The only portable C implementation > demonstrated so far has an arbitrary limit compiled in. How do I > dynamically allocate function objects in C?? I guess you missed my earlier posting. Since it dealt with functions from ints to ints (and would require different compose functions to deal with functions that returned different types), I guess you don't want the details. The main idea, though, is that you invent a structure... struct Func { int (*f)( void *, int ); void *instanceVariables; }; ...and an "apply" function (it's dangerous as a macro): int apply ( f, arg ) struct Func *f; int arg; { return (f)->f ( (f)->instanceVariables, arg ); } The struct Funcs can be alloc'ed as you like. Mail me if you want the details. Or, if anybody wants, I'll repost it. --Steve Witham Not-the-fault-of: SMDS, Inc., Concord, MA
sw@smds.UUCP (Stephen E. Witham) (01/29/91)
In article <1991Jan27.035619.24981@spool.cs.wisc.edu>, quale@picard.cs.wisc.edu (Douglas E. Quale) writes: > > If every use of a function parameter in the program has to know how the > function was created, this would seem to be a rather marginal definition > of first class. > I agree. But you could make a function (or functions, yargh!) to convert real C function pointers to functionoid structs, then always assume you're dealing with functionoids... --Steve Witham Not-the-fault-of: SMDS, Concord, MA
chased@rbbb.Eng.Sun.COM (David Chase) (01/29/91)
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <21245@yunexus.YorkU.CA> oz@yunexus.yorku.ca (Ozan Yigit) writes: >> Yes, you were able to write an interpreter that contained said >> functionality, minus the scoping details. >> Amazing. >'Twas hardly amazing. What amazes me is that there are *still* people >posting to this newsgroup asking questions like ``Ya know, I haven't >seen any portable first-class composable function implementations that >don't have arbitrary limits. Is this because they are impossible, or is >there some sneaky way?'' ... Dan, you obviously missed the point. Most of the questioners assumed that you weren't going to write an interpreter. Of course it works if you write an interpreter. Nobody is surprised, or thinks it is particularly interesting, if you solve the problem by writing an interpreter. By that standard, C has first-class functions, closures, partial application, garbage collection, and threads -- I'll just write an interpreter. No doubt you'll claim that your answer is different, because the text of your program is input to a C compiler, not an interpreter. Bogus distinction, that -- consider the innards of the emacs lisp interpreter, or the innards of the x-lisp interpreter. One just makes calls from C to manipulate the appropriate data structures, and away you go. Your code might look something like: DEFUN ("directory-files", Fdirectory_files, Sdirectory_files, 1, 3, 0, "Return a list of names of files ...") (dirname, full, match) Lisp_Object dirname, full, match; { DIR *d; char slashfilename[MAXNAMLEN+2]; char *filename = slashfilename; int length; Lisp_Object list, name; ... (above was an excerpt from GNU Emacs) OR, perhaps /* xread - read an expression */ NODE *xread(args) NODE *args; { NODE ***oldstk,*fptr,*eof,*rflag,*val; /* create a new stack frame */ oldstk = xlsave(&fptr,&eof,(NODE **)NULL); ... /* restore the previous stack frame */ xlstack = oldstk; /* return the expression */ return (val); } (above was an excerpt from Xlisp) See? "Functions" in these interpreters work because they obey some protocol (just like your "functions"), and as long as that protocol is obeyed, the "functions" have all the power of "functions" in the language being interpreted. That's why your answer is boring; it's obvious. By the way Dan, how is it that growing arrays by reallocation has quadratic cost? I must have missed your answer. David Chase Sun
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/29/91)
In article <6800@exodus.Eng.Sun.COM> chased@rbbb.Eng.Sun.COM (David Chase) writes: > brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >'Twas hardly amazing. What amazes me is that there are *still* people > >posting to this newsgroup asking questions like ``Ya know, I haven't > >seen any portable first-class composable function implementations that > >don't have arbitrary limits. Is this because they are impossible, or is > >there some sneaky way?'' ... > Dan, you obviously missed the point. [ blah, blah, blah ] Let me rephrase the above paragraph, since Dave obviously didn't read it before following up. First sentence: From the start of this discussion I have considered the programming involved to be entirely trivial. I think everyone involved agrees with me. The arguments over terminology have turned out to be a lot more interesting; I've learned to take a much broader view of ``first-class'' because of this thread. Second sentence, and pseudo-quote: Why tf are people posting articles that show they refuse to think through the issues for themselves? It is trivial to implement portable, dynamically allocated, first-class, composable functions in C, and I'm amazed that people are asking whether it's possible. Now Dave spends sixty lines saying that the programming involved is trivial. I thought I had just said the same thing. So, Dave, exactly what point did I miss? [ Ching say, wise man implement interpreter in compiled language ] > No doubt you'll claim that your answer is different, Don't put words into my mouth. > That's why your answer is boring; it's > obvious. Dave, notably lacking from your USENET education is this tidbit of advice: If you follow up to an article, say that the author missed the point, and then make the same points he did, don't bother following up. > By the way Dan, how is it that growing arrays by reallocation has > quadratic cost? I must have missed your answer. Wtf does that have to do with comp.lang.misc? Go read comp.lang.c. ---Dan
quale@picard.cs.wisc.edu (Douglas E. Quale) (01/29/91)
My question: >> Show me an implementation that doesn't have a fixed limit on the number of >> functions that can be composed. The only portable C implementation >> demonstrated so far has an arbitrary limit compiled in. How do I >> dynamically allocate function objects in C?? > And the answer: >details. The main idea, though, is that you invent a structure... > > struct Func { int (*f)( void *, int ); void *instanceVariables; }; > >...and an "apply" function (it's dangerous as a macro): > > int apply ( f, arg ) > struct Func *f; > int arg; > { > return (f)->f ( (f)->instanceVariables, arg ); > } > >The struct Funcs can be alloc'ed as you like. Mail me if you want the >details. Or, if anybody wants, I'll repost it. Sorry, this doesn't work because compose returns a structure, not a function. Suppose I want to use the library function twalk(3c). It takes a function as an argument. Will it accept the output of your compose, or do I have to rewrite every library function that takes functional parameters to provide two versions? Note: The interpreter hack fails here as well. -- Doug Quale quale@picard.cs.wisc.edu
bbc@rice.edu (Benjamin Chase) (01/30/91)
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > It is trivial to implement portable, dynamically allocated, > first-class, composable functions in C, and I'm amazed that people are > asking whether it's possible. Dan, If you feel that such an implementation is trivial, how do you feel about implementing the version that I described in an earlier post? Probably you can just take one of the many "composition of integer function" implementations that's been posted here, hack it up a bit to gain a small bit of added functionality, and run it through the ol' compiler for us? On the edge of my seat, Ben -- Ben Chase <bbc@rice.edu>, Rice University, Houston, Texas
sw@smds.UUCP (Stephen E. Witham) (01/31/91)
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <21245@yunexus.YorkU.CA> oz@yunexus.yorku.ca (Ozan Yigit) writes: >> Yes, you were able to write an interpreter that contained said >> functionality, minus the scoping details. >> Amazing. >'Twas hardly amazing. What amazes me is that there are *still* people >posting to this newsgroup asking questions like ``Ya know, I haven't >seen any portable first-class composable function implementations that >don't have arbitrary limits. Is this because they are impossible, or is >there some sneaky way?'' ... At least we have the extremes of the opinion spectrum covered. The things I've seen (and posted) here are neither "interpreters" nor "first-class" (nor "obvious," as someone said, and Dan agreed). "Interpreter" implies a big mechanism that you have to write, that uses a different internal representation, requires a different kind of thinking to use, runs slowly, and is hard to interface to routines in the "host" language. The functionoids we've been talking about, on the other hand, are not that different from things people regularly do in C. The syntax of using them is, well, close to the syntax of using regular C functions. They deal in regular C data types. They run with compiled code, and not a lot of overhead, either. And there's no big mechanism that has to be implemented or added to your program. "First-class," in my favorite interpretation (i.e., relative to the rest of the language), also doesn't apply to these functionoids. In C, all variable- sized data are second-class compared to the simple, fixed-sized data types. They can't be put in "automatic" variables or be intermediate values in expressions, so you have to take care of allocating and freeing their space. Also, these functionoids can't be used interchangeably with regular C function pointers. I don't think that's a big practical limitation, but it is something function pointers can do that functionoid pointers can't. Calling this stuff obvious is an insult. Great, so you guys already knew the answer. I remember the time when I didn't, and the time when I first started using this stuff in a real C program (and it ran faster than the assembly- language program it replaced). Objects and lexical closures are standard stuff in computer science now, but for some of us lowly coders, the fact that you can get the same effects relatively painlessly in C is a nifty, non-obvious idea. --Steve Witham Not-the-fault-of: SMDS, Inc., Concord, MA
sw@smds.UUCP (Stephen E. Witham) (01/31/91)
In article <1991Jan29.153549.19220@spool.cs.wisc.edu>, quale@picard.cs.wisc.edu (Douglas E. Quale) writes about a response of mine to a challenge of his: > > Sorry, this doesn't work because compose returns a structure, not a function. > > Suppose I want to use the library function twalk(3c). > It takes a function as an argument. Will it accept the output of your > compose, or do I have to rewrite every library function that takes functional > parameters to provide two versions? First of all, I concede! Like I said, why pick on C? The poor thing has been knocked to the ground, she's out for the count, and you're still beating on her! C does not have first-class composable functions! We've established that, and I think people realize that it can be a real limitation. But it can do second-class functionoids that do a lot, if not everything. For instance, to answer your question, struct Func *globalFuncPtr; <return type> globalFuncInterface ( <args> ) <arg declarations>; { return apply( globalFuncPtr, <args> ); } ... globalFuncPtr = compose( ... ); twalk( ...globalFuncInterface, ... ); Yes, this is kind of messy. (For one thing, it's not recursive: the functionoid in globalFuncPtr had better not try the same trick.) If you're trying to hand composed functions to library functions in every other line of your code, it's going to be very messy. I'm just saying there's a large area of application of these functionoids that doesn't run into the kind of problems you've been pointing out, or does rarely enough that you can patch your way through. --Steve Witham Not-the-fault-of: SMDS, Inc., Concord, MA
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (01/31/91)
In article <BBC.91Jan29105852@sicilia.rice.edu> Benjamin Chase <bbc@rice.edu> writes: > If you feel that such an implementation is trivial, how do you feel > about implementing the version that I described in an earlier post? Ben, you're confusing two issues. One is the ease of implementing composable functions in C. The other is the difficulty of implementing polymorphic functions in C. Once you realize you're confusing the two issues, you should realize that your complaints have nothing to do with the subject at hand. (To answer the question, though: AT&T's cfront is a quite usable implementation of what yuckies these days call ``objects,'' including the sort of polymorphism you're looking for. It does take a bit of work to implement objects; my shortest respectable C macro set for the job is a few hundred lines. There, now you know how I feel about implementing what you described in an earlier post.) ---Dan
quale@picard.cs.wisc.edu (Douglas E. Quale) (02/02/91)
In article <3576:Jan2622:55:2991@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >There were two other portable C implementations (by Kris, I believe); >they allowed the usual C syntax for function calls, and because C >functions are statically allocated, the compositions had to be >statically allocated. Only one of those implementations had a fixed >(``arbitrary'') limit. I don't understand the last 2 sentences. They are mutually contradictory. The functions are statically allocated, and this ISN'T an arbitrary limit? Explanation, please. [ An additional note: I suffered from some braindamage in the C prototype I posted earlier. It should read int (*compose)(int (*f)(int), int (*g)(int)) but you folks probably spotted that right off. ] -- Doug Quale
quale@picard.cs.wisc.edu (Douglas E. Quale) (02/05/91)
In article <14484:Feb206:54:1191@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <1991Feb2.012304.2425@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes: >> The functions are statically allocated, and this ISN'T an arbitrary limit? > >Correct. There is no fixed or arbitrary limit on the size of a C program >or on the number of functions it contains. > Dan, sometimes I think we don't speak the same language. The number of functions in a C program is limited to EXACTLY the number of functions that are provided at compile time. This number cannot be altered (most crucially, increased) at run time. How do you know, at compile time, EXACTLY how many composed functions I want??????????????????????????????????????????????????????????????????????? -- Doug Quale quale@picard.cs.wisc.edu
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (02/05/91)
In article <1991Feb4.160639.2766@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes: > Dan, sometimes I think we don't speak the same language. Look, static allocation is not an ``arbitrary limit,'' and when you say ``fixed, arbitrary limit'' people will assume that the programmer used some fixed number, say 1000, as a limit. That's not true here. Are you going to claim that Fortran has ``arbitrary limits'' because doesn't have dynamic allocation? That's a restriction upon power: it's something the language can't do. It's not a fixed limit, and it's not an arbitrary limit. If you go around claiming that just because language designer X didn't provide for your pet feature Y, language Z must have ``arbitrary limits,'' then you're the one misusing words. > The number of functions in a C program is limited to EXACTLY the number of > functions that are provided at compile time. This number cannot be altered > (most crucially, increased) at run time. Fine, so call it a limit if you're desperate. It's not a fixed limit, and it's not an arbitrary limit. Translation: It's not something that a real-world programmer will consider a limit. > How do you know, at compile time, EXACTLY how many composed functions > I want? I don't. You're the one writing the program. ---Dan
larus@primost.cs.wisc.edu (James Larus) (02/05/91)
At the risk of jumping into the middle of an inane argument, let me point out that C does have first-class function. All you need to do is write your favorite Lisp system in C and presto, you can have all the first-class functions that you need. A bit heavy-handed perhaps. /Jim
quale@picard.cs.wisc.edu (Douglas E. Quale) (02/05/91)
In article <29224:Feb419:06:0191@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <1991Feb4.160639.2766@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes: >> Dan, sometimes I think we don't speak the same language. > >Look, static allocation is not an ``arbitrary limit,'' and when you say >``fixed, arbitrary limit'' people will assume that the programmer used >some fixed number, say 1000, as a limit. That's not true here. > Dan, static allocation of functions is an arbitrary limit. The *only* portable implementation of compose in C statically allocated the composed functions. If you compile the program with 50 statically allocated functions and then try to compose 51 functions, you're screwed. If you compile the program with 500 statically allocated functions and try to compose 501 functions, you're screwed again. Etc. If YOU have a portable implementation of compose in C that returns a function pointer and doesn't limit the number of composes to some compile time fixed number, then post it or mail it to me. This IS an arbitrary limit. -- Doug Quale
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (02/06/91)
In article <1991Feb5.144815.23239@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes: > In article <29224:Feb419:06:0191@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >In article <1991Feb4.160639.2766@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes: > >> Dan, sometimes I think we don't speak the same language. > >Look, static allocation is not an ``arbitrary limit,'' and when you say > >``fixed, arbitrary limit'' people will assume that the programmer used > >some fixed number, say 1000, as a limit. That's not true here. > Dan, static allocation of functions is an arbitrary limit. Arbitrary, adj. 1. Not fixed by rules but left to one's judgment or choice; discretionary. 2. Based on one's preference, notion, whim, etc.; capricious. 3. Absolute; despotic. You say that there is some arbitrary limit. Do you mean that the programmer used his judgment to choose some limit? Really? What is that limit? 500? 1000? 7? I don't see it. The only limit is the that the number of functions is limited to the number of functions statically declared, and that's a rule imposed by the language. Is someone choosing a limit capriciously, based on his preference or whim? No. The limit isn't consciously chosen by any particular person; it's forced by the rule of static allocation. You might argue that the rule is arbitrary, though this seems to be a further misuse of the language. In any case, there is no arbitrary limit involved. Who's not speaking the same language here? > The *only* portable implementation of compose in C statically allocated the > composed functions. As I said at the beginning of this discussion, you're wrong. The very first implementation posted (mine) dynamically allocated the composed, first-class functions. > If YOU have a portable implementation of compose in C that returns a > function pointer and doesn't limit the number of composes to some compile > time fixed number, then post it or mail it to me. I did post it. I question your use of ``compile-time fixed number'' to refer to static allocation. Again, do you say that Fortran is full of arbitrary or fixed limits because it doesn't have dynamic allocation? Of course not. Who's being arbitrary? Who's fixing the limit? The number of statements in a Fortran program is static, but it's not limited to any fixed or arbitrary number. Similarly for any other static language feature. Here's a real example of an arbitrary limit: The UNIX kernel typically only looks at the first 32 characters in a #! script. 32 is a fixed number which was chosen pretty much arbitrarily. ---Dan
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (02/06/91)
In article <29224:Feb419:06:0191@kramden.acf.nyu.edu>, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > In article <1991Feb4.160639.2766@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes: > > Dan, sometimes I think we don't speak the same language. > > Look, static allocation is not an ``arbitrary limit,'' and when you say > ``fixed, arbitrary limit'' people will assume that the programmer used > some fixed number, say 1000, as a limit. That's not true here. If there is static allocation, then the number of distinct compositions which can be "live" at any time has a FIXED LIMIT. That's what static allocation means, after all. > Are you going to claim that Fortran has ``arbitrary limits'' because > doesn't have dynamic allocation? *Fortran* didn't have arbitrary limits on array sizes, but Fortran *PROGRAMS* did. (Fortran Extended -- was F8X -- is much better.) > That's a restriction upon power: it's > something the language can't do. It's not a fixed limit, and it's not an > arbitrary limit. But the size of any one array in old Fortran WAS a fixed limit, and in general those limits were never satisfactory. In the same way, an implementation of function composition which uses static allocation does involve each program instance running with a fixed (hence often unsatisfactory) limit. It would be fair to say that Fortran did not have first-class arrays. (I think it would be possible to argue that 8X has.) > > The number of functions in a C program is limited to EXACTLY the number of > > functions that are provided at compile time. This number cannot be altered > > (most crucially, increased) at run time. > > Fine, so call it a limit if you're desperate. It's not a fixed limit, But it IS a fixed limit. If program P contains N function definitions, then when processes execute P, they will have N functions, no more, no less. N is a fixed limit for that program, even though it isn't a fixed limit for the *language*, and even though the limit can be set otherwise for a variant P' of P. > > How do you know, at compile time, EXACTLY how many composed functions > > I want? > I don't. You're the one writing the program. The point is that NOBODY knows. It's not all that rare for the execution of a program written in a language with first-class functions to create tens of millions of derived functions, just as C programs may perform milliards of arithmetic operations. -- The Marxists have merely _interpreted_ Marxism in various ways; the point, however, is to _change_ it. -- R. Hochhuth.
quale@picard.cs.wisc.edu (Douglas E. Quale) (02/07/91)
In article <1234:Feb520:27:2391@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >As I said at the beginning of this discussion, you're wrong. The very >first implementation posted (mine) dynamically allocated the composed, >first-class functions. I'm quite certain that you are completely, absolutely and undisputedly wrong. Functions cannot be dynamically allocated in C. C does not have first-class functions. If arrays and structures couldn't be dynamically allocated in C, would you call C arrays and structs first class? The comparison between C arrays and functions is interesting: If C arrays were limited to the same allocations permitted to functions, all arrays would be global static variables and no more arrays could be created at runtime. I have serious doubts about whether you would know what to do with dynamically allocated functions if you had them. -- Doug Quale quale@picard.cs.wisc.edu
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (02/07/91)
In article <1991Feb6.161639.18311@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes: > In article <1234:Feb520:27:2391@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >As I said at the beginning of this discussion, you're wrong. The very > >first implementation posted (mine) dynamically allocated the composed, > >first-class functions. > I'm quite certain that you are completely, absolutely and undisputedly wrong. > Functions cannot be dynamically allocated in C. > C does not have first-class functions. You are making Jim Giles' mistake of confusing syntax and semantics. Just because the C standard calls certain language objects ``functions'' doesn't mean that it's impossible to implement functions that don't have the same restrictions as those objects. As a matter of fact, it's not only possible, it's trivial. The things that my implementation produced were not C functions, but they were full-fledged functions in all respects. We've hashed all this out before. (Everyone agrees with the above points when I say ``implement''; the problem before was that some people didn't like how I said ``C has first-class composable functions'' to mean ``first-class functions can be implemented in C.'') May I suggest that you review the beginning of a discussion before jumping into the end of it and throwing out ``you're wrong, wrong, wrong'' left and right? May I also suggest that you learn to distinguish the syntax of a language feature from its semantics? > I have serious doubts about whether you would know what to do with > dynamically allocated functions if you had them. I've written a noticeable amount of Forth code, and I once found it useful to implement dynamically allocated functions (in Pascal) for an intepreter. Other than that I've never seen much use for the things. ---Dan
quale@picard.cs.wisc.edu (Douglas E. Quale) (02/07/91)
In article <12547:Feb621:05:4491@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >You are making Jim Giles' mistake of confusing syntax and semantics. >Just because the C standard calls certain language objects ``functions'' >doesn't mean that it's impossible to implement functions that don't have >the same restrictions as those objects. As a matter of fact, it's not >only possible, it's trivial. > Unfortunately, this doesn't solve the problem. Your `functions' are not functions. What happens when I pass a Bernstein `function' to twalk(3c)?? The question was NEVER, "Can C _implement_ dynamically allocable functions?" I can implement a Turing machine simulator in practically any language, but it's not very interesting or useful. Does C _have_ dynamically allocable functions? No. A short session in SML (which does have first-class functions): - fun square i : int = i * i; val square = fn : int -> int - (square o square) 2; val it = 16 : int - ((square o square) o square) 2; val it = 256 : int - (square o (square o square)) 2; val it = 256 : int The last is a nested call to the builtin compose operator, o, whose definition is: - infix o; - fun f o g = fn x => f (g x); val o = fn : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b Compose has a simple mathematical definition, and since Dan is so proud of his math, he surely knows that (f o g) o h = f o (g o h). (Strangely he expressed confusion over a nested call to compose in a posting made by someone else some time ago, but this is really quite elementary.) Let's see Bernstein's compose function do that. (On a related note, he also claimed that it is just as easy to prove program correctness in C as it is in a functional language. Since his implementation of compose in C doesn't obey one of the most trivial identities for that function, I wonder how he reaches that bizarre conclusion.) Given Dan's pride in his math I'm tempted to call "First-class functions, or Why You Can't Write compose in C" the pons asinorum of the study of computer programming languages. P.S. Dan, read _The_Structure_and_Interpretation_of_Programming_Languages_, by Abelson, Sussman and Sussman. Jim Giles said he didn't learn anything useful from that book, but I certainly did and you might too. At the very least it will show you what you can do with first-class functions. (A short preview: blocks, delayed evaluation, call-by-name, own variables, coroutines, non-local exits and objects for OOP.) -- Doug Quale quale@picard.cs.wisc.edu
throop@aurs01.UUCP (Wayne Throop) (02/08/91)
> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) >> quale@picard.cs.wisc.edu (Douglas E. Quale) >> Functions cannot be dynamically allocated in C. > You are making Jim Giles' mistake of confusing syntax and semantics. > Just because the C standard calls certain language objects ``functions'' > doesn't mean that it's impossible to implement functions that don't have > the same restrictions as those objects. As a matter of fact, it's not > only possible, it's trivial. As a newcomer to this discussion, I'm puzzled. Let me see if I understand the point Dan is making. Is the point that one can code in C dynamically allocated entities which can be invoked or interpreted? If so, is it fair to say that C also "has" 1) garbage collection 2) associative arrays 3) generators 4) inheritance (or hey, go all the way) multiple inheritance in this sense? If not, why not? These seem to be much the same thing. ( To be honest, it seems much like Dan is answering the question "How many legs does a dog have if you call the tail a leg?" with "four", while Douglas answers "five". The disagreement in the case of the dog is what is meant by "calling" one object another. The disagreement in the case of composable functions is what is meant by a language "having" a feature. Further, the principle of least astonishment in use of language would make me answer "five" to the question about the dog, and "no" to the question about C having dynamically allocatable functions, because most people take the "calling" to affect what the term "leg" in the question references, and most people take "to have" to mean something closer to "available as a language primitive" rather than "can be composed in the language". ) Wayne Throop ...!mcnc!aurgate!throop
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (02/08/91)
In article <1991Feb7.150537.9257@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes: > Unfortunately, this doesn't solve the problem. Your `functions' are not > functions. What happens when I pass a Bernstein `function' to twalk(3c)?? ``Unfortunately, your bignum package doesn't solve the problem. Your `bignums' are not numbers. What happens when I pass a DECWRL bignum to getcwd()??'' The mistake here is the second statement. Bignums are numbers; they just aren't the same as C's integers. Similarly, anything supporting certain operations is a function; it doesn't have to be the same as C's functions. Your ``problem'' of passing a non-C-function to twalk() has been quite thoroughly addressed in other postings. Just because twalk() only accepts C functions doesn't mean that other functions aren't functions, either in theory or in practice. This has all been discussed to death before in this newsgroup. If you're trying to contribute something, make an effort to see what's already been contributed. > The question was NEVER, "Can C _implement_ dynamically allocable functions?" I chose the subject line (I choose most subject lines in comp.lang.misc these days) and I was using ``L has X'' to mean ``X can be implemented in L'' where L is a language and X is a semantic feature. Apparently people can't stand this usage, although nobody's been able to come up with any other sensible definition of ``has'' in this context; so I've stopped using ``has'' in this way. Nevertheless, that's what it means in the subject line. This has also been discussed to death before in this newsgroup. If you're trying to contribute something, make an effort to see what's already been contributed. > I can implement a Turing machine simulator in practically any language, > but it's not very interesting or useful. (Not in Fortran.) The reason that a Turing machine simulator isn't useful is that once you get down from theory to practice, you care about issues like efficiency. However, usefulness is not the same thing as power. Would you say that the original Forth doesn't have I/O facilities just because its I/O facilities aren't very useful? No. > Does C _have_ dynamically allocable functions? > No. What's your definition of ``has'' for a semantic feature? I'll bet that your definition will either be (1) syntactic, in which case you're confusing syntax and semantics; or (2) so ambiguous as to be useless; or (3) in agreement with mine. > Compose has a simple mathematical definition, and since Dan is so proud > of his math, he surely knows that (f o g) o h = f o (g o h). > (Strangely he expressed confusion over a nested call to compose in a > posting made by someone else some time ago, but this is really quite > elementary.) That call was improperly formed and nonsensical as both a mathematical expression and a C language expression. [ composing three functions in a row ] > Let's see Bernstein's compose function do that. Are you shooting from the hip, or are you simply confused? It is trivial to compose() twice in a row. > (On a related note, > he also claimed that it is just as easy to prove program correctness in > C as it is in a functional language. Well, no, that's not really what I claimed, but I'll let this slide. > Since his implementation of compose > in C doesn't obey one of the most trivial identities for that function, > I wonder how he reaches that bizarre conclusion.) You are simply confused. > P.S. Dan, read _The_Structure_and_Interpretation_of_Programming_Languages_, > by Abelson, Sussman and Sussman. Jim Giles said he didn't learn > anything useful from that book, but I certainly did and you might too. I second Jim's opinion. > At the very least it will show you what you can do with first-class > functions. (A short preview: blocks, delayed evaluation, > call-by-name, own variables, coroutines, non-local exits and > objects for OOP.) Ah! Finally you come down out of the fluff and get to some real issues. As I noted in the previous article, I have found very little use for first-class functions in real-world problems. All of the applications you mention can easily be handled in C---and some of them, such as coroutines and so-called ``objects,'' simply don't gain anything from first-class functions. ---Dan
quale@picard.cs.wisc.edu (Douglas E. Quale) (02/09/91)
"Sophistry, thy name is Bernstein." -- Anon I think I am truly beginning to fathom the meaning of that old saying. "In France, they have a different word for EVERYTHING!" -- Steve Martin In article <25199:Feb801:33:1191@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >I chose the subject line (I choose most subject lines in comp.lang.misc >these days) and I was using ``L has X'' to mean ``X can be implemented >in L'' where L is a language and X is a semantic feature. Apparently This is not the meaning of ``has''. X can be implemented in L is a meaningless statement for any languages that are Turing equivalent. Meaningless terminology is not useful, and quite frankly Dan, I challenge you to give me evidence that _anyone_ uses ``has'' in the sense(lessness) that you do. To Dan, C ``has'' multiple inheritance because C++ does and C++ can be implemented in C. I don't think I can say anything more about this. "You can teach nothing to a stone." -- John McCarthy > >That call was improperly formed and nonsensical as both a mathematical >expression and a C language expression. > Dan, wtf are you talking about?? square o square o square is perfectly sensible as a mathematical expression. The parens can be omitted because functional composition is associative, but most programming languages would prefer that you write (square o square) o square or square o (square o square) In languages that don't give you the ability to make compose an infix operator, either compose(compose(square,square),square) or compose(square,compose(square,square)) is perfectly sensible (C would require some address-of operators due to its confused handling of functions and functional values). In order to save Dan hours of strenous calculation, I'll add that they are eighth power functions, ready to be applied to a integer (assuming square is an int->int function). For instance, print (((square o square) o square) 2) should print 256. And yes, Dan, I specifically request you to try explain what is nonsensical about those expressions. I will be willing to let you off with simply "I was having a bad day." Instead of continually saying it's trivial, post your compose code in C and then we'll see how it stacks up. Remember, it doesn't have to be polymorphic. I'll be suprised if you can handle even the simple case (int->int)*(int->int)->(int->int). -- Doug Quale quale@picard.cs.wisc.edu
quale@picard.cs.wisc.edu (Douglas E. Quale) (02/09/91)
In article <25199:Feb801:33:1191@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <1991Feb7.150537.9257@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes: >> Unfortunately, this doesn't solve the problem. Your `functions' are not >> functions. What happens when I pass a Bernstein `function' to twalk(3c)?? > >``Unfortunately, your bignum package doesn't solve the problem. Your >`bignums' are not numbers. What happens when I pass a DECWRL bignum to >getcwd()??'' > >The mistake here is the second statement. Bignums are numbers; they just >aren't the same as C's integers. Similarly, anything supporting certain >operations is a function; it doesn't have to be the same as C's >functions. > Number, bignum and integer are not C types. int is a C type. I expect to be able to apply the integer operators in C to ints. I don't expect C's built in operators to apply to bignums. (Of course in C++ we can manage this. Some languages do support overloading and/or polymorphism.) Compose is a binary function taking two unary functions as arguments producing a unary function. In the trivial case where we have int->int for everything, we have something that is indeed a valid C type: int (*compose)(int (*f)(int), int (*g)(int)) I expect to be able to use the result of compose as a pointer to a function from ints to ints. We have a valid C type for compose, why can't we use it? "Anything supporting certain operations etc." gives you two incompatible classes of ``functions.'' Applied to C I must admit that I cannot find this passage in the first or second edition of K&R. Dan, do you have the page number handy? In any case, why is this crap necessary? Why can't the output of one invocation of compose be used an argument to another compose? Are we going to write two composes as well? This thread began when someone said "C doesn't have first-class functions because it can't handle compose." Dan objected, saying compose was trivial in C and C does too have first-class functions and then gave a compose implementation that returned a struct, not a function pointer. Unwittingly Dan proved the original poster to be correct: If C had first-class functions compose could return a function rather than a structure. A) Dynamic allocation is a source of expressive power in a language. Dan said this once and I agree. We are together at point A. B) First-class status requires that dynamic allocation be possible. I think I probably lose Dan between point A and point B. But what really puzzles me is C) C functions are not dynamically allocable. Dan has repeatedly denied C. The only proof he can offer is to redefine function. Actually I am getting used to Dan redefining terms in the CS lexicon whenever his opponent gets the upper hand in an argument. It must be a sign of desparation that Dan now tries redefine common English words such as ``has''. To me, "C functions are not dynamically allocable" and "C doesn't have dynamically allocable functions" have identical meaning, but to hear Dan tell one of those statements has "to be able to implement X in L" mixed up in it (don't ask me which one). "Aber nein! [Herr Bernstein] is capable of making the finest distinctions!" -- David Hilbert (An obscure reference to a bon mot of Hilbert's. Dan is a math genius who can't learn anything a mere book, but for anyone else I recommend _Hilbert_ by Constance Reid. And I still highly recommend _The_Structure_ and_Interpretation_of_Computer_Programs_. Only small minds are afraid of ideas that may be new to them.) A great advantage of languages with first-class functions over languages like C is that it is unnecessary to use Newspeak and call struct bletch a function. Actually, most C programmers don't feel the need to act like Big Brother Dan. They would simply say, "Yes, this isn't a strong point of C. The best work-around is inconvenient, but it is usable in some cases. Generally I use C for tasks that don't require much functional composition." For some reason, Dan is insanely protective of C, like a mother for her child. C is 20 years old, and the state of the art in programming languages has improved somewhat since then. Dan should learn a non-Algol language before proclaiming himself an expert on programming languages. He could start with SML, since he seems to be completely ignorant of it. Otherwise Hope or Miranda or Scheme or any of a whole slew of other languages would do him good. -- Doug Quale quale@picard.cs.wisc.edu
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (02/09/91)
In article <1991Feb8.191014.6430@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes: > In article <25199:Feb801:33:1191@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >I chose the subject line (I choose most subject lines in comp.lang.misc > >these days) and I was using ``L has X'' to mean ``X can be implemented > >in L'' where L is a language and X is a semantic feature. Apparently > This is not the meaning of ``has''. X can be implemented in L is a > meaningless statement for any languages that are Turing equivalent. First of all, most real languages are not equivalent to Turing machines. People commonly use one of two models for programs. The first says, roughly, that a program is valid if its memory use is bounded by a fixed amount over all possible inputs. (This is for people who don't worry about running out of memory.) The second says, roughly, that a program is valid if its memory use is between N and N+K for all inputs, where N depends on the program and K does not. (This is for when you are worrying about running out of memory.) Both models suffice for real languages. Neither model allows a Turing machine. That's why ``has'' does distinguish languages that have, e.g., dynamic allocation from languages that don't. Second, you didn't respond to my challenge to provide a useful definition of ``L has X'' for L a language and X a semantic feature. I claim that my definition is (1) unambiguous and (2) useful. Why do I say it's useful? Because ``has'' is a helper word. Sure, the statement ``C has first-class functions'' (meaning ``first-class functions can be implemented in C'') doesn't say much. But you can qualify it! You can say ``C has efficient first-class functions'' (``first class functions can be implemented efficiently in C'') or ``C has easy-to-use first-class functions'' or ``C has easy-to-implement first-class functions.'' > Meaningless terminology is not useful, Nevertheless, it has been defined for the purposes of this discussion, so it is no longer meaningless in context. > and quite frankly Dan, I challenge > you to give me evidence that _anyone_ uses ``has'' in the sense(lessness) > that you do. Webster's, definition 5c(b): ``exercise.'' Their example: ``have mercy on us.'' ``Mercy'' is a trait---a semantic feature. ``Doug Quale has mercy on us'' means that you stop rehashing every little bit of a dead discussion---uh, I mean, that Doug Quale exercises mercy, i.e., Doug combines his primitive operations to implement mercy. ``Doug has mercy upon you'' doesn't mean that mercy is one of Doug's *basic* traits, or that mercy is defined as part of Dougginess, or that Doug *always* exercises mercy, or that Doug can show mercy without outside help; similarly for ``C has dynamically allocatable functions.'' And, before you post some irrelevant quibble, let me point out that this definition of ``has'' can be applied to impersonal, inactive objects: ``inetd.conf has control over your connections.'' > I don't think I can say anything more about this. Then don't. > >That call was improperly formed and nonsensical as both a mathematical > >expression and a C language expression. > Dan, wtf are you talking about?? You referred to the time when I expressed confusion over the supposed meaning of somebody's nested compose() call. In case you don't remember, the call in question tried to compose the compose function with an integer function. Once again, that call was improperly formed and nonsensical as both a mathematical expression and a C language expression. > square o square o square > is perfectly sensible as a mathematical expression. Yes. [ about the square examples again ] > And yes, Dan, I specifically request you to try explain what is nonsensical > about those expressions. I never said that those expressions were nonsensical. Your implication is a lie, plain and simple. I doubt you have the integrity to review the articles and apologize, but I'll give you one chance to do so before I start quoting things in public. > Instead of continually saying it's trivial, post your compose code in C and > then we'll see how it stacks up. I did. Since you apparently would rather flame than think, here's the three-way composition that you claim to be so difficult. I've written it out step-by-step and put in comments just for you. compose(square,square,sqsq) /* put square o square in sqsq */ compose(square,sqsq,sqsqsq) /* put square o sqsq in sqsqsq */ printf("%d\n",apply(sqsqsq,2)); /* apply sqsqsq to 2 and print it */ Exercise: write the missing struct fun definitions and initializations. ---Dan
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (02/09/91)
In article <1991Feb8.201117.7515@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes: > In article <25199:Feb801:33:1191@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >In article <1991Feb7.150537.9257@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes: > >> Unfortunately, this doesn't solve the problem. Your `functions' are not > >> functions. What happens when I pass a Bernstein `function' to twalk(3c)?? > >``Unfortunately, your bignum package doesn't solve the problem. Your > >`bignums' are not numbers. What happens when I pass a DECWRL bignum to > >getcwd()??'' [ etc. ] > Number, bignum and integer are not C types. int is a C type. Quite right. My struct funs are not C types. ``foo (*)()'' is a C type. Nevertheless, bignums are perfectly valid integral types, just as struct funs are perfectly valid function types. You seem to be confusing normal definitions (and common sense) with words that a few people decided to use in a language definition. They also defined these things called ``phases of translation''; will you no longer be able to use that phrase outside an ANSI C context? You'll be in real trouble when you read two standards that use the same words in different ways. > int (*compose)(int (*f)(int), int (*g)(int)) > We have a valid C type for compose, why can't we use it? ``unsigned char jn(unsigned char c)'' ``We have a valid C type for Bessel functions, why can't we use it?'' > "Anything supporting certain operations etc." gives you two incompatible > classes of ``functions.'' Boo hoo. long and short are two incompatible classes of ``integral types.'' > In any case, why is this crap necessary? Why can't the > output of one invocation of compose be used an argument to another compose? Wtf are you talking about? All seven working implementations I've seen here allow nested composition. [ the same old arguments ] Doug, WE HAVE FINISHED DISCUSSING THIS. You are the only person who publicly claims to have been listening since the beginning of this discussion and who doesn't understand the issues at this point. > A) Dynamic allocation is a source of expressive power in a language. > Dan said this once and I agree. We are together at point A. No, I have never said that. Dynamic allocation is a source of *semantic* power, not necessarily syntactic power. You are confused. > B) First-class status requires that dynamic allocation be possible. > I think I probably lose Dan between point A and point B. Yes. First-class (as traditionally defined) does not imply dynamically allocatable. > C) C functions are not dynamically allocable. > Dan has repeatedly denied C. No, I have never denied that statement. You are lying. > The only proof he can offer is to redefine > function. You are lying. > Actually I am getting used to Dan redefining terms in the CS > lexicon whenever his opponent gets the upper hand in an argument. Oh? What terms have I redefined? I define terms now and then when I cannot find any established terms with the right definition. But I have never redefined words already used in the same context. You are confused. > To me, "C functions are not dynamically allocable" > and "C doesn't have dynamically allocable functions" have identical > meaning, Then you don't know how to use the English language. (But we've established that already.) Hint: What does the first statement have in common with ``Have you stopped beating your wife?'' > Dan is a math genius Doubtful. > who can't learn anything a mere book, I can't parse that phrase. > A great advantage of languages with first-class functions over languages > like C is that it is unnecessary to use Newspeak and call struct bletch > a function. Oh, gee, this matters sooooo much to real programmers! > For some reason, Dan is insanely protective of C, like a mother for her > child. C is 20 years old, and the state of the art in programming > languages has improved somewhat since then. Dan should learn a non-Algol > language before proclaiming himself an expert on programming languages. I have never proclaimed myself an expert on programming languages. I have written nontrivial programs in several languages not derived from Fortran. I have even told you that I know one of those languages. All we can conclude is that you intend to be insulting. Doug, you are contributing absolutely nothing to the discussion. All you're doing is throwing out random insults. (If someone other than Doug can see any point he's brought up that hasn't been thoroughly discussed before in these threads, please let me know.) Go away. ---Dan
gudeman@cs.arizona.edu (David Gudeman) (02/10/91)
In article <6828:Feb906:14:3491@kramden.acf.nyu.edu> Dan Bernstein writes:
]
]Second, you didn't respond to my challenge to provide a useful
]definition of ``L has X'' for L a language and X a semantic feature.
One of the reasons people are unwilling to provide such a definition
is that "has" is intended to be something of a subjective judgement.
Even so, I think using "has" to mean "can implement" is peculiar. I
can't say it's wrong since the term is subjective, but it is at an
extreme end of the scale of meanings people apply to the term.
Another problem with giving a definition of "L has semantic feature X"
is that we first have to know what a "semantic feature" is. Until
that term is well-defined the term "has" must remain a bit flexible.
Having said that, here is a posible definition for the term, punting
on the issue of what a "semantic feature" is.
Definition of ``L has X'' for a language L and a semantic feature X:
View L as a many-sorted algebra where the operations consist of all
the primitive operations of the language and the sorts consist of all
the types acted on by built-in operations. I include standard
libraries as part of the standard language. A language "has" a type
if that type is one of the sorts of the algebra. A language "has" an
operation if that operation is in the algebra.
Then C "has":
(1) ints and floats -- obvious
(2) pointers to every type -- because C has built-in operations on
pointers. This is the reason I defined sorts based on operations --
it doesn't matter that syntactically (int *) is a non-atomic type, the
type is supported by built-in operations in the language, so it is
part of the language.
(3) strings -- string literals are 0-ary operations
(4) string concatenation -- the library function strcat()
(5) function construction -- just define the function
(6) first-class functions -- because function pointers are first-class
objects and function pointers (C terminology) are actually functions
(general terminology). The reason I say that C function pointers are
functions is because there is a built-in apply operation on them. The
statement "C functions are first-class" on the other hand is not true
because the phrase "C function" seems to require C terminology.
C does not have composable functions because there is no operation
in the algebra that composes functions. When you implement such
things in C, you have created a new language, an extension of C that
has composable functions. But standard C does not have them.
One problem with this definition is that C requires declarations, and
you can say that the code implementing composable functions is just an
extended declaration. In the case of C, there is a difference between
a "declaration" and a "definition", so I'm tempted to say that
declarations are permitted in the language that defines the algebra
but that definitions are not. But I'm not sure that this works for
all languages.
Practically, however, I would say that there is an obvious difference
between a declaration like "#include <string.h>" or "int *ip" and a
declaration that takes 300 lines of code.
--
David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudemanbrnstnd@kramden.acf.nyu.edu (Dan Bernstein) (02/10/91)
In article <21642@yunexus.YorkU.CA> oz@yunexus.yorku.ca (Ozan Yigit) writes: > No, they were not C functions, therefore unlike other attempts, they were > [and still are] irrelevant to the discussion. Ah. Someone with a name you might recognize posted a C++ solution near the beginning of this discussion. His composable functions were not C functions, so you are saying that his solution was irrelevant. > We have noted that by that amusing re-definition, > C ``has'' Fortran. Fortran is not a semantic feature. It is a computer language. Your notes have been exceedingly repetitious, largely incorrect, and insulting to (among other people) the man who designed C++. I don't think that anyone wants to associate himself with your royal ``we.'' I want this group to be a useful source of technical information, not boring arguments. But I haven't seen a new observation in this discussion for more than a week. So I'm giving up on this thread, and I suggest that others do likewise. It's not my problem if Ozan wants to continue tossing insults at Bell Labs language designers. ---Dan
rh@smds.UUCP (Richard Harter) (02/11/91)
In article <RANG.91Feb10140506@nexus.cs.wisc.edu>, rang@cs.wisc.edu (Anton Rang) writes: > In article <6828:Feb906:14:3491@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >First of all, most real languages are not equivalent to Turing machines. > Why not? > I claim that, given any Turing machine, I can write a Pascal or C > program which will perform exactly the computation that machine would > perform on a given input. (You can't do it in FORTRAN, because you > don't have dynamic memory allocation.) > Similarly, I claim that given any Pascal or C program, I can write a > description of it suitable for running on a universal Turing machine. Sorry, Dan is right on this one, and it is actually important to understand that he is right and why he is right. Turing machines do not exist in the real world -- they require as part of the definition infinite memory. The statement "real languages are not equivalent to Turing machines" isn't exact (it mixes languages and machines which are two different concepts) but the intent is clear. Real computers are finite state machine with absurdly large numbers of states. Programs which execute on real computers are not equivalent to Turing machine programs in general. In real computers there is only a finite amount of memory available (including memory of all types). As a direct consequence there are only a finite number of programs that can be executed on a real computer (the number is, however, very large) whereas a universal Turing machine can execute an infinite number of distinct programs. The distinction is important. There are many statements that are true for Turing machines that are not true for real computers. Etc. Incidentally there are some problems with your assumption that since C and Pascal have dynamic storage allocation and Fortran does not you can do Turing machine emulation in C and Pascal and not in Fortran. I will leave them as an exercise for the reader. -- Richard Harter, Software Maintenance and Development Systems, Inc. Net address: jjmhome!smds!rh Phone: 508-369-7398 US Mail: SMDS Inc., PO Box 555, Concord MA 01742 This sentence no verb. This sentence short. This signature done.
quale@picard.cs.wisc.edu (Douglas E. Quale) (02/12/91)
In article <6828:Feb906:14:3491@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >I never said that those expressions were nonsensical. Your implication >is a lie, plain and simple. I doubt you have the integrity to review the >articles and apologize, but I'll give you one chance to do so before I >start quoting things in public. > Quote away, Dan. I'm not afraid of the truth. >> Instead of continually saying it's trivial, post your compose code in C and >> then we'll see how it stacks up. > >I did. Since you apparently would rather flame than think, here's the >three-way composition that you claim to be so difficult. I've written it >out step-by-step and put in comments just for you. > > compose(square,square,sqsq) /* put square o square in sqsq */ > compose(square,sqsq,sqsqsq) /* put square o sqsq in sqsqsq */ > printf("%d\n",apply(sqsqsq,2)); /* apply sqsqsq to 2 and print it */ > >Exercise: write the missing struct fun definitions and initializations. > >---Dan Dan, this is your job, not mine. I say it can't be done. int square(int x) { return (x*x) } is easy enough, but I can't get the rest to work. How about helping me out? -- Doug Quale
quale@picard.cs.wisc.edu (Douglas E. Quale) (02/12/91)
In article <6828:Feb906:14:3491@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >I never said that those expressions were nonsensical. Your implication >is a lie, plain and simple. I doubt you have the integrity to review the >articles and apologize, but I'll give you one chance to do so before I >start quoting things in public. > Quote away, Dan. I'm not afraid of the truth. >> Instead of continually saying it's trivial, post your compose code in C and >> then we'll see how it stacks up. > >I did. Since you apparently would rather flame than think, here's the >three-way composition that you claim to be so difficult. I've written it >out step-by-step and put in comments just for you. > > compose(square,square,sqsq) /* put square o square in sqsq */ > compose(square,sqsq,sqsqsq) /* put square o sqsq in sqsqsq */ > printf("%d\n",apply(sqsqsq,2)); /* apply sqsqsq to 2 and print it */ > >Exercise: write the missing struct fun definitions and initializations. > >---Dan Dan, this is your job, not mine. I say it can't be done. int square(int i) { return i*i; } is easy enough, but I can't get the rest to work. I keep getting a type clash in the second call to compose, since your compose takes function pointers as arguments (I used &compose instead) and returns a structure. How about helping me out? -- Doug Quale
quale@picard.cs.wisc.edu (Douglas E. Quale) (02/12/91)
In article <6828:Feb906:14:3491@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >I never said that those expressions were nonsensical. Your implication >is a lie, plain and simple. I doubt you have the integrity to review the >articles and apologize, but I'll give you one chance to do so before I >start quoting things in public. > Quote away, Dan. I'm not afraid of the truth. >> Instead of continually saying it's trivial, post your compose code in C and >> then we'll see how it stacks up. > >I did. Since you apparently would rather flame than think, here's the >three-way composition that you claim to be so difficult. I've written it >out step-by-step and put in comments just for you. > > compose(square,square,sqsq) /* put square o square in sqsq */ > compose(square,sqsq,sqsqsq) /* put square o sqsq in sqsqsq */ > printf("%d\n",apply(sqsqsq,2)); /* apply sqsqsq to 2 and print it */ > >Exercise: write the missing struct fun definitions and initializations. > >---Dan Dan, this is your job, not mine. I say it can't be done. int square(int i) { return i*i; } is easy enough, but I can't get the rest to work. I keep getting a type clash in the second call to compose, since your compose takes function pointers as arguments (I used &square) and returns a structure. Unfortunately square and sqsq don't have the same types (both should be functions). How about helping me out? -- Doug Quale
rang@cs.wisc.edu (Anton Rang) (02/12/91)
In article <319@smds.UUCP> rh@smds.UUCP (Richard Harter) writes: >[I wrote:] >> I claim that, given any Turing machine, I can write a Pascal or C >> program which will perform exactly the computation that machine would >> perform on a given input. (You can't do it in FORTRAN, because you >> don't have dynamic memory allocation.) > >Sorry, Dan is right on this one, and it is actually important to understand >that he is right and why he is right. Turing machines do not exist in >the real world -- they require as part of the definition infinite memory. Turing machines don't exist in the real world. However, it is reasonable (IMHO) to assume that because many computer languages do not place restrictions on the operations used (such as "allocate memory" or "perform a procedure call"), the *language* assumes an infinite model for such resources as stack and dynamic memory. If I write a procedure in Pascal: procedure forever; begin forever end; and call it, the *language* semantics (which can be formally defined) probably say that this will never terminate. (It is possible to define the semantics in such a way that a procedure call can lead to an error at random, of course.) On a real machine, this may run forever, or it may abort with a stack overflow error. The *implementation* of the language places restrictions on what legal programs can be run. >The statement "real languages are not equivalent to Turing machines" >isn't exact (it mixes languages and machines which are two different >concepts) but the intent is clear. It's not really clear to me. "Real languages" and "real machines" are radically different, in my mind (with the exception of, e.g., an assembly language which defines a fixed data store size etc.). >Programs which execute on real computers are not equivalent to Turing >machine programs in general. Yes, but "programs which execute on real computers" is a strictly smaller set than "programs which are expressible in real programming languages," I believe. >The distinction is important. There are many statements that are true >for Turing machines that are not true for real computers. Etc. Very true (this is why the "halting problem" is defined for Turing machines, and is meaningless for an implementation on a FSM). There are also many statements that are true for programming languages which may not be true of a particular implementation. Anton +---------------------------+------------------+-------------+ | Anton Rang (grad student) | rang@cs.wisc.edu | UW--Madison | +---------------------------+------------------+-------------+
alanm@cognos.UUCP (Alan Myrvold) (02/13/91)
In article <7027:Feb906:42:0991@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > All seven working implementations I've seen here allow nested composition. Instead of all of the flamage, how about someone posting these 7 implementations for comment? ------------------------ int main() { if (main == &main) puts("C does not have first class functions"); } ------------------------ Obligatory compose implementation : ------------------------ #include <stdio.h> typedef struct { int (*a)(),(*b)(),(*c)(); } c_f; c_f compose(a,b) int (*a)(),(*b)(); { c_f cf; cf.a = NULL; cf.b = a; cf.c = b; return cf; } int apply(cf,x) c_f *cf; int x; { if (!cf->a) { return apply(cf->b,apply(cf->c,x)); } else { return ((int (*)()) cf)(x); } } int square(x) int x; { return x*x; } int main() { c_f sqsq,sqsqsq; sqsq = compose(square,square); /* put square o square in sqsq */ sqsqsq = compose(square,&sqsq); /* put square o sqsq in sqsqsq */ printf("%d\n",apply(&sqsqsq,2)); /* apply sqsqsq to 2 and print it */ return 0; } ------------------------ Alan Myrvold 3755 Riverside Dr. uunet!mitel!cunews!cognos!alanm Cognos Incorporated P.O. Box 9707 alanm%cognos.uucp@ccs.carleton.ca (613) 738-1440 x5530 Ottawa, Ontario CANADA K1G 3Z4
sw@smds.UUCP (Stephen E. Witham) (02/15/91)
In article <319@smds.UUCP> rh@smds.UUCP (Richard Harter) writes:
...about real machines not being Turing equivalent, in response to
Dan Bernstein's saying something about "real languages."
Richard, Richard. Dan, Dan. A language is a description of an abstract
machine.
Description Limited implementation Abstract machine
------------------ ------------------------ ------------------------
C standard Real Von Neuman machine Infinite "C machine"
Turing's real "Turing machine" with Abstract Turing machine
description of his finite tape
imaginary machine
(Hmm. But does C require that pointers have a finite number of bits?
How about longs? If so, how can you address infinite memory? What about
Pascal?)
--Steve Witham
Back-to-work-for: SMDS, Inc., Concord, MA