brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (12/21/90)
In article <1990Dec19.222059.6878@mathrt0.math.chalmers.se> augustss@cs.chalmers.se (Lennart Augustsson) writes: > To see the difference just try to write a function > that does function composition. Okay. (What follows isn't tested but you'll get the idea.) We'll work with a function descriptor type: struct basicfun { int (*f)(); } ; struct twofun { struct fun *first; struct fun *second; } struct fun { int type; union { struct basicfun b; struct twofun t; } u; } ; #define BASICTYPE 1 #define TWOTYPE 2 To convert a C function pointer into one of these things, given storage space: struct fun *cftofun(c,f) int (*c)(); struct fun *f; { f->type = BASICTYPE; f->u.b.f = c; return f; } To call one of these things, given the argument: int callfun(f,x) struct fun *f; int x; { switch(f->type) { case BASICTYPE: return f->u.b.f(x); case TWOTYPE: return callfun(f->u.t.second, callfun(f->u.t.first,x)); } } Finally, to answer the question: struct fun *compose(second,first,f) struct fun *second; struct fun *first; struct fun *f; { f->type = TWOTYPE; f->u.t.first = first; f->u.t.second = second; return f; } Of course, a more complete implementation would manage struct fun storage, possibly with garbage collection. A different strategy is to store basic functions as just pointers, and composed functions as a pointer to a special function, followed by the first and second pointers; then pointers to these ``objects'' would be passed in as arguments. Back to Lennart: > I claim that this is impossible to do in a portable way. You were saying? ---Dan
dolf@idca.tds.PHILIPS.nl (Dolf Grunbauer) (12/21/90)
In article <19468:Dec2100:23:0790@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >X-Original-Subject: Re: Complexity of syntax > >In article <1990Dec19.222059.6878@mathrt0.math.chalmers.se> augustss@cs.chalmers.se (Lennart Augustsson) writes: >> To see the difference just try to write a function >> that does function composition. >> I claim that this is impossible to do in a portable way. > >Okay. (What follows isn't tested but you'll get the idea.) > >[ idea, which probably will work, deleted ] > I think this is not what Lennart wanted. He wanted something like: extern int f(), g(); int (*fg)(); ... fg = f; (*fg)(x); /* executes f(x) */ fg = compose (f,g); (*fg)(x); /* should execute f(g(x)) */ That is: he just wants to use the result of compose just like any other pointer to function, so one needs not to known whether it is a real function or a composed one. In Dan's code one must made this disctinction. By the way when reading Lennarts article, he gave me more or less the idea that this compising is possible in ALGOL68, but I am affraid it isn't. -- _ _ / U | Dolf Grunbauer Tel: +31 55 433233 Internet dolf@idca.tds.philips.nl /__'< Philips Information Systems UUCP ...!mcsun!philapd!dolf 88 |_\ If you are granted one wish do you know what to wish for right now ?
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (12/22/90)
In article <553@ssp9.idca.tds.philips.nl> dolf@idca.tds.philips.nl (Dolf Grunbauer) writes: > That is: he just wants to use the result of compose just like any other > pointer to function, so one needs not to known whether it is a real function > or a composed one. In Dan's code one must made this disctinction. No, not at all! You just use all functions as struct fun's. It's perfectly consistent. You can make struct fun's from (1) static functions declared in your program and passed around as C function pointers; (2) function composition; (3) whatever extensions you want to add. And you call struct fun's in a single, absolutely consistent way. What's the problem? ---Dan
chased@rbbb.Eng.Sun.COM (David Chase) (12/22/90)
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >augustss@cs.chalmers.se (Lennart Augustsson) writes: >> To see the difference just try to write a function >> that does function composition. > >Okay. (What follows isn't tested but you'll get the idea.) > >We'll work with a function descriptor type: > > struct basicfun { int (*f)(); } ; > struct twofun { struct fun *first; struct fun *second; } > struct fun { int type; > union { struct basicfun b; struct twofun t; } u; > } ; Ah, but that is not a C "function", but something else (a struct). You have to call it in a different way than ordinary C functions or pointers to functions. You have not contradicted Lennart's assertion, which is that functions in C are not first class objects. Try to pass one of your "struct twofun" functions as a comparison function to qsort, for example. And no, you don't get to redefine "function", or rewrite qsort (much as it deserves it). Ugh. Please read and think before posting, ok? It says here that your message cost the net hundreds if not thousands of dollars to send everywhere. David Chase Sun Microsystems
augustss@cs.chalmers.se (Lennart Augustsson) (12/22/90)
In article <19468:Dec2100:23:0790@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >X-Original-Subject: Re: Complexity of syntax > >In article <1990Dec19.222059.6878@mathrt0.math.chalmers.se> augustss@cs.chalmers.se (Lennart Augustsson) writes: >> To see the difference just try to write a function >> that does function composition. > >Okay. (What follows isn't tested but you'll get the idea.) > >We'll work with a function descriptor type: > [code for handling function stuff deleted] > >Of course, a more complete implementation would manage struct fun >storage, possibly with garbage collection. > >A different strategy is to store basic functions as just pointers, and >composed functions as a pointer to a special function, followed by the >first and second pointers; then pointers to these ``objects'' would be >passed in as arguments. > >Back to Lennart: > >> I claim that this is impossible to do in a portable way. > >You were saying? > I repeat what I was saying, you cannot write a function int (*compose)(f, g) int (*f)(); int (*g)(); so that it can be used by (*compose(ff, gg))(x) I did not claim that you cannot represent functions with some suitable datastructures (which you have shown). Of course you can do what ever computable thing you want in C, but sometimes you have to add a some extra stuff to represent what you want. There is nothing strange about that since a language cannot contain everything. The second way you propose would be a way to solve the problem, but how would you do it in a portable way? I still make my old claim! -- Lennart Augustsson Email: augustss@cs.chalmers.se
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (12/22/90)
In article <4978@exodus.Eng.Sun.COM> chased@rbbb.Eng.Sun.COM (David Chase) writes: > Ah, but that is not a C "function", but something else (a struct). So what? Are we talking about real-world programming, or are we talking about computer science? > You have not contradicted Lennart's assertion, > which is that functions in C are not first class objects. Dave Gudeman already contradicted it. Functions (which the C language calls ``function pointers'') are first-class objects by the usual definition, because they can be passed as arguments and assigned to variables. > Ugh. Please read and think before posting, ok? It says here that > your message cost the net hundreds if not thousands of dollars to send > everywhere. I don't see what you contributed to the discussion. Are you paid to write code, or to do computer science? ---Dan
bs@alice.att.com (Bjarne Stroustrup) (12/23/90)
augustss@cs.chalmers.se (Lennart Augustsson @ Dept. of CS, Chalmers, Sweden) writes > I repeat what I was saying, you cannot write a function > int (*compose)(f, g) > int (*f)(); > int (*g)(); > > so that it can be used by > > (*compose(ff, gg))(x) > > I did not claim that you cannot represent functions with some > suitable datastructures (which you have shown). Of course you > can do what ever computable thing you want in C, but sometimes > you have to add a some extra stuff to represent what you want. > There is nothing strange about that since a language cannot > contain everything. > I still make my old claim! I know that C++ isn't (just) C and I know that trickery with an auxuilerary type is necessary, but 'tis is the season for some silliness so here is a solution in C++; First the main function showing the programming style that can be achieved: main() { int i1 = g(1); // g writes "Merry " // (and triples its argument) int i2 = f(i1); // f writes "Christmas\n" // (and doubles its argument) int i3 = (f+g)(1); fct h = f+g; int i4 = h(1); cout << i1 << '\n' << i2 << '\n' << i3 << '\n' << i4 << '\n'; } and the output Merry Christmas Merry Christmas Merry Christmas 3 6 6 6 Now the scaffolding: typedef int (*PFI)(int); class fct { // if f is a fct f() calls all functions in f // and (f+g)(i) means f(g(i)) PFI* p; int sz; // size of allocation int n; // number of contained functions public: fct& operator+=(const fct&); fct& operator+=(PFI); friend fct operator+(const fct&,const fct&); friend fct operator+(const fct&,PFI); friend fct operator+(PFI,const fct&); int operator()(int); fct(PFI f) : sz(10), n(1), p(new PFI[10]) { p[0] = f; p[1] = 0; } fct(const fct&); fct& operator=(const fct&); ~fct() { delete p; } }; int fct::operator()(int a) // application operator { int t = a; for (int i = n-1; i>=0; i--) t = p[i](t); return t; } fct& fct::operator+=(const fct& a) // add to list of contained functions { int nn = n+a.n; if (nn>=sz) { // not enough space, double allocation PFI* pp = new PFI[sz=sz+a.sz]; for (int i = 0; i<n; i++) pp[i] = p[i]; delete p; p = pp; } for (int i = n; i<=nn; i++) p[i] = a.p[i-n]; // copy cc n = nn; return *this; } fct::fct(const fct& a) // make a copy { sz = a.sz; n = a.n; p = new PFI[sz]; for (int i = 0; i<=n; i++) p[i] = a.p[i]; } fct operator+(const fct& c1, const fct& c2) { fct cc(c1); return cc+=c2; } #include<stream.h> int _f(int i) { cout<<"Christmas\n"; return i+i; } int _g(int i) { cout<<"Merry "; return i+i+i; } fct f(_f); fct g(_g); and the ``main program'' repeated in case you have forgotten it: main() { int i1 = g(1); int i2 = f(i1); int i3 = (f+g)(1); fct h = f+g; int i4 = h(1); cout << i1 << '\n' << i2 << '\n' << i3 << '\n' << i4 << '\n'; } This example has not been extensively tested. I just wrote it, compiled it and ran it.
oz@yunexus.yorku.ca (Ozan Yigit) (12/25/90)
In article <19468:Dec2100:23:0790@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >Of course, a more complete implementation would manage struct fun >storage, possibly with garbage collection. Yep. A more complete implementation would effectively be an interpreter that can handle arbitrary-depth function composition. This must be what you mean when you talk about real-world programming. Sigh. I believe the original question had something like scheme in mind, when referring to first-class-functions and composition. In scheme, we write (define compose (lambda (f g) (lambda (x) (f (g x))))) this looks uninteresting, except that the innermost (composing) closure preserves its scope information (environment) as a part of this composition as well. [Jeff Dalton elequently addressed this issue which has partly to do with the definition of the term. Jeff??] >You were saying? Hmm. oz --- Where the stream runneth smoothest, | Internet: oz@nexus.yorku.ca the water is deepest. - John Lyly | UUCP: utzoo/utai!yunexus!oz
jnemeth@cue.bc.ca (John Nemeth) (12/25/90)
Has anybody else tried to ruu the C++ version? I couldn't get it to run under Turbo C++. Does it use the C++ 2.0 or 2.1 version of stream.h (I tried both). I'm just learning C++, so I couldn't take a crack at debugging it.
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (12/26/90)
In article <19390@yunexus.YorkU.CA> oz@yunexus.yorku.ca (Ozan Yigit) writes: > In article <19468:Dec2100:23:0790@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu > (Dan Bernstein) writes: > >Of course, a more complete implementation would manage struct fun > >storage, possibly with garbage collection. > Yep. A more complete implementation would effectively be an interpreter > that can handle arbitrary-depth function composition. The version I posted can handle arbitrary-depth function composition with the same syntax and reasonable efficiency. It just requires the user to keep storage for the functions. > This must be what > you mean when you talk about real-world programming. Sigh. Yes. If I ever need to compose functions in a real-world program, I will use a solution along the lines that I posted. What are you complaining about? A few people have said that I'm cheating in some sense, though they can't explain exactly how. Let me draw an analogy. In my growing Q language, every syntactic construct eventually gets converted into what looks like a function call. A function declaration, for example, is converted into fundecl(fun,result,args), with the appropriate types filled in. fundecl is by default defined as defaultfundecl, which has a fixed meaning---but it can be redefined as something else. You can turn every function declaration into one of those struct funs if you want. It's all done syntactically, and it's completely invisible to the rest of the program. Now answer this: Does Q have composable functions? Just as in C, the ``functions'' as defined by the language cannot be composed. But you can change the syntax so that, just as in C++, a previously normal function turns into something you can compose. I think there's a big difference between the semantics---the power---of a language and the syntax. Behind its syntactic veil, C++ does have composable functions. So does Q. And so does C. ---Dan
ske@pkmab.se (Kristoffer Eriksson) (12/29/90)
In article <553@ssp9.idca.tds.philips.nl> dolf@idca.tds.philips.nl (Dolf Grunbauer) writes: >In article <19468:Dec2100:23:0790@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >> >>In article <1990Dec19.222059.6878@mathrt0.math.chalmers.se> augustss@cs.chalmers.se (Lennart Augustsson) writes: >>> To see the difference just try to write a function that does function >>> composition. I claim that this is impossible to do in a portable way. ... >I think this is not what Lennart wanted. He wanted something like: > > extern int f(), g(); > int (*fg)(); > ... > fg = f; > (*fg)(x); /* executes f(x) */ > fg = compose (f,g); > (*fg)(x); /* should execute f(g(x)) */ Just for the fun of it, I'll give you _exactly_ that: /* -------- Composition package begins ---------- */ int null_fn(int x) { return x; } struct fun_descr { int (*f1)(), (*f2)(); }; #define decl_composed_fun(name) \ struct fun_descr name ## _data = { null_fn, null_fn }; \ int name(int x) \ { return(name ## _data.f1( name ## _data.f2(x) )); } #define compose(name, fun1, fun2) \ name ## _data.f1 = fun1; \ name ## _data.f2 = fun2 /* --------- Composition package ends ----------- */ /* --------- Usage example begins --------------- */ int f(int x) { return(x+x); } /* extern int f(); */ int g(int x) { return(x+1); } /* extern int g(); */ decl_composed_fun(fg); /* int (*fg)(); */ main() { compose(fg, f, null_fn); /* fg = f; */ printf("%d\n", fg(5)); /* (*fg)(x); */ compose(fg, f, g); /* fg = compose(f,g) */ printf("%d\n", fg(5)); /* (*fg)(x); */ } /* --------- Example ends ----------------------- */ I've used an ANSI compiler. >That is: he just wants to use the result of compose just like any other >pointer to function, so one needs not to known whether it is a real function >or a composed one. I made the result of compose just a function in stead of a pointer to a function, since that gave the shortest implementation, but there's no problem taking the address of this function. Either way, the composed function is used just like any other function. If I wanted to get rid even of the special declaration of composed functions and allocate composed functions dynamically and make compose() itself a function in stead of a macro, I could set up a pool of pre- declared composed functions and have compose() allocate out of that pool. (I won't mention all the even more powerful and fairly easy non-portable and mostly-portable solutions that come to mind.) -- 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
smryan@garth.UUCP (Steven Ryan) (01/08/91)
Well, just to throw another bucket muck in the sewer, >> You have not contradicted Lennart's assertion, >> which is that functions in C are not first class objects. > >Dave Gudeman already contradicted it. Functions (which the C language >calls ``function pointers'') are first-class objects by the usual >definition, because they can be passed as arguments and assigned to >variables. and only because they cannot be nested so that their closure only consists of static variables. I'd like to see you be so casual about calling procedures first class objects when their closures include local variables. -- ...!uunet!ingr!apd!smryan Steven Ryan ...!{apple|pyramid}!garth!smryan 2400 Geng Road, Palo Alto, CA
cunniff@hpfcso.HP.COM (Ross Cunniff) (01/25/91)
In article <553@ssp9.idca.tds.philips.nl> dolf@idca.tds.PHILIPS.nl (Dolf Grunbauer) writes: >>In article <1990Dec19.222059.6878@mathrt0.math.chalmers.se> augustss@cs.chalmers.se (Lennart Augustsson) writes: >>> To see the difference just try to write a function >>> that does function composition. >>> I claim that this is impossible to do in a portable way. >> >>Okay. (What follows isn't tested but you'll get the idea.) >> >>[ idea, which probably will work, deleted ] >> >I think this is not what Lennart wanted. He wanted something like: > extern int f(), g(); > int (*fg)(); > ... > fg = f; > (*fg)(x); /* executes f(x) */ > fg = compose (f,g); > (*fg)(x); /* should execute f(g(x)) */ >That is: he just wants to use the result of compose just like any other >pointer to function, so one needs not to known whether it is a real function >or a composed one. In Dan's code one must made this disctinction. And now for something completely perverse. Of course, this violates the 'portability' constraint, but the function is short enought that it wouldn't be terribly hard to rewrite it for your target machine. Here goes: /* Assembly code we'll generate: * mov.l 4(%sp),-(%sp) * jsr b * mov.l %d0,(%sp) * jsr a * addq.w %4,%sp * rts */ /* Instructions used */ #define INSTR_GETX1 0x2f2f /* mov.l 4(%sp),-(%sp) */ #define INSTR_GETX2 0x0004 #define INSTR_JSR 0x4eb9 /* jsr ... */ #define INSTR_GETB 0x2e80 /* mov.l %d0,(%sp) */ #define INSTR_RET1 0x584f /* addq.w %4,%sp */ #define INSTR_RET2 0x4e75 /* rts */ #define COMPOSE_SIZE 22 /* Bytes */ typedef int (*func)( int ); /* Build a function that returns a(b(x)) */ func compose( func a, func b ) { unsigned short *Res, *Abits, *Bbits; void *malloc( unsigned ); Res = malloc( COMPOSE_SIZE ); if( !Res ) { return 0; } /* Get addresses */ Abits = (unsigned short *)&a; Bbits = (unsigned short *)&b; /* Call b */ Res[0] = INSTR_GETX1; Res[1] = INSTR_GETX2; Res[2] = INSTR_JSR; Res[3] = Bbits[0]; Res[4] = Bbits[1]; /* Call a, leaving result in d0 */ Res[5] = INSTR_GETB; Res[6] = INSTR_JSR; Res[7] = Abits[0]; Res[8] = Abits[1]; /* Pop args off stack and return */ Res[9] = INSTR_RET1; Res[10] = INSTR_RET2; /* Flush caches - this is very system specific, but necessary */ /* since separate I and D caches won't know about each other. */ flush_cache( Res, COMPOSE_SIZE ); /* Return result */ return (func)Res; } int a( int x ) { return x + 2; } int b( int x ) { return x * 2; } main( int argc, char **argv ) { int x, atoi( char * ); func f; x = atoi( argv[1] ); printf( "a(%d) = %d\n", x, a(x) ); printf( "b(%d) = %d\n", x, b(x) ); printf( "a(b(%d)) = %d\n", x, a(b(x)) ); f = compose( a, b ); printf( "f(%d) = %d\n", x, (*f)(x) ); return 0; } This printed: a(5) = 7 b(5) = 10 a(b(5)) = 12 f(5) = 12 on an HP9000 Series 300 workstation. How fun! Ross Cunniff Hewlett-Packard Colorado Language Lab cunniff@hpfcla.HP.COM