aet@felix.ee.mu.OZ.AU (bert) (02/25/91)
Does anyone know how to write a compose function in C, without writing a Scheme interpreter to do it in. A call should look something like this: (compose(sqr,cube)) (2) which would evaluate to 64. "compose" is a one-liner in any functional language, but I suspect that it is, given the above constraint, impossible in C. (then again, I'm just an undergrad, so what would I know :-) Feel free to use pointers wherever they seem appropriate. (so the above call could look like: (*compose(&sqr,&cube)) (2) ) Many thanks for everyone's helpful comments! Bert Thompson.
sane@cs.uiuc.edu (Aamod Sane) (02/26/91)
aet@felix.ee.mu.OZ.AU (bert) writes: > Does anyone know how to write a compose function in C, >without writing a Scheme interpreter to do it in. >A call should look something like this: > (compose(sqr,cube)) (2) >which would evaluate to 64. > "compose" is a one-liner in any functional language, >but I suspect that it is, given the above constraint, impossible in C. >(then again, I'm just an undergrad, so what would I know :-) > Feel free to use pointers wherever they seem appropriate. > (so the above call could look like: > (*compose(&sqr,&cube)) (2) ) > Many thanks for everyone's helpful comments! > Bert Thompson. Write to comp.lang.misc. There was recently a major war on this.. -- sane@cs.uiuc.edu == / \ ----- == * \_/ -|||- ==
markh@csd4.csd.uwm.edu (Mark William Hopkins) (02/26/91)
In article <6873@munnari.oz.au> aet@felix.ee.mu.OZ.AU (bert) writes: > > Does anyone know how to write a compose function in C, >without writing a Scheme interpreter to do it in. > >A call should look something like this: > (compose(sqr,cube)) (2) >which would evaluate to 64. ... You could do it compile-time like this example for composing x^2 and 2*x: ------------------------------------------------------------ #include <stdio.h> int Compose(F, G, X) int (*F)(), (*G)(); int X; { return (*F)((*G)(X)); } static int Square(X) int X; { return X*X; } static int Double(X) int X; { return 2*X; } static int Square_Double(X) int X; { return Compose(Square, Double, X); } static int Double_Square(X) int X; { return Compose(Double, Square, X); } main() { printf("%d, %d", Square_Double(5), Double_Square(5)); } ------------------------------------------------------------ The declarations above for Square_Double, and Double_Square would be compile-time lambda abstractions (with X being the variable abstracted out), but C does not support run-time lambda abstraction. You'd have to be able to write something like: int (*Compose(int (*F)(), int (*G)()))() { int (*H)(int X) { return (*F)((*G)(X)); } return H; } with embedded run-time function declarations...
acha@CS.CMU.EDU (Anurag Acharya) (02/28/91)
In article <6873@munnari.oz.au> aet@felix.ee.mu.OZ.AU (bert) writes: > Does anyone know how to write a compose function in C, > without writing a Scheme interpreter to do it in. > A call should look something like this: > (compose(sqr,cube)) (2) which would evaluate to 64. > "compose" is a one-liner in any functional language, > but I suspect that it is, given the above constraint, impossible in C. Nope. it is possible. Example: #include <stdio.h> int compose (foo,bar,baz) int (*foo) (); int (*bar) (); int baz; { return ((*foo) ((*bar)(baz))); } int sqr(x) int x; { return x * x; } int cube(x) int x; { return x * x * x; } main() { printf("The value is %d\n",compose(sqr,cube,2) ); } try it out. it works. this version of compose will work for any pair of int->int functions. liberal use of casts will allow you to write a general compose as well. anurag
kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) (02/28/91)
In article <ACHA.91Feb28002548@DRAVIDO.CS.CMU.EDU> acha@CS.CMU.EDU (Anurag Acharya) writes: >In article <6873@munnari.oz.au> aet@felix.ee.mu.OZ.AU (bert) writes: >> Does anyone know how to write a compose function in C, >> without writing a Scheme interpreter to do it in. >Nope. it is possible. >int compose (foo,bar,baz) >int (*foo) (); >int (*bar) (); >int baz; >{ > return ((*foo) ((*bar)(baz))); > } I don't think anyone was saying your method was not valid, but functional composition returns a _function_ given two other functions. This enables you to, e.g., assign the said composition to another function variable. Can you write something like: int (*proc1)(int); int (*proc2)(int); int (*my_composition)(); my_composition = compose(proc1,proc2); so that later you can say: printf("%d\n",(*my_composition)(1)); There will be a problem (for a start) with the type for `compose()'. If you can handle that one there are a few more examples I have in mind (where the composed functions include local variables). -kym
acha@CS.CMU.EDU (Anurag Acharya) (03/01/91)
In article <ACHA.91Feb28002548@DRAVIDO.CS.CMU.EDU> acha@CS.CMU.EDU (Anurag Acharya) writes: > In article <6873@munnari.oz.au> aet@felix.ee.mu.OZ.AU (bert) writes: > > Does anyone know how to write a compose function in C, > > without writing a Scheme interpreter to do it in. > Nope. it is possible. As Brad White points out my solution used a compose function whose type was ((int->int) x (int->int) x int)->int whereas the original question asked for a compose function that had the type (int->int) x (int->int) -> (int->int) In this note contains two other solutions. The compose function in the first one looks and feels the same a compose functional in a functional language except that susbequent calls to compose may alter the behaviour of the function returned by compose. The second solution doesnot have this problem but requires an explicit "apply" operation. It pretty much does what functional languages do for composition -- create a closure at composition and use the info during application. The explicit apply operation is needed because unlike Scheme, SML etc., C's nested lexical scopes cannot contain function declarations. anurag ------------------------------------------------------------------------------ First Solution: #include <stdio.h> typedef int (*fptr)(); static int (*foo)(), (*bar)(); int compose1 (baz) int baz; { return ((*foo) ((*bar)(baz))); } fptr compose(f,g) fptr f; fptr g; { foo = f; bar = g; return compose1; } int sqr(x) int x; { return x * x; } int cube(x) int x; { return x * x * x; } main() { printf("The value is %d\n",compose(sqr,cube)(2) ); } ------------------------------------------------------------------------------- Second solution: #include <stdio.h> typedef int (*fptr)(); typedef struct CLOS { fptr foo; fptr bar; } closure; closure *compose(f,g) fptr f; fptr g; { closure *tmp; tmp = (closure *) malloc(sizeof(closure)); tmp->foo = f; tmp->bar = g; } int apply (clos,arg) closure *clos; int arg; { return((*(clos->foo))((*(clos->bar))(arg))); } int sqr(x) int x; { return x * x; } int cube(x) int x; { return x * x * x; } int quad(x) int x; { return x * x * x * x; } main() { closure *a, *b; a = compose(sqr,cube); b = compose(sqr,quad); printf("sqr(cube 2) is %d\n",apply(a,2) ); printf("sqr(quad 2) is %d\n",apply(b,2) ); printf("sqr(cube 3) is %d\n",apply(a,3) ); }
volpe@kirkwood.crd.ge.com (Christopher R Volpe) (03/01/91)
In article <ACHA.91Feb28002548@DRAVIDO.CS.CMU.EDU>, acha@CS.CMU.EDU (Anurag Acharya) writes: |>In article <6873@munnari.oz.au> aet@felix.ee.mu.OZ.AU (bert) writes: |>> Does anyone know how to write a compose function in C, |>> without writing a Scheme interpreter to do it in. |>> A call should look something like this: |>> (compose(sqr,cube)) (2) which would evaluate to 64. |>> "compose" is a one-liner in any functional language, |>> but I suspect that it is, given the above constraint, impossible in C. |> |>Nope. it is possible. |> |>Example: |> |>#include <stdio.h> |> |>int compose (foo,bar,baz) |>int (*foo) (); |>int (*bar) (); |>int baz; |>{ |> return ((*foo) ((*bar)(baz))); |> } This is not a compose function, because it does not take two functions are return a FUNCTION. Compose should behave as the original poster specified: (compose(sqr,cube))(2) == 64. Try something along the lines of the following: (Assume a stack of function pointers with push and pop functions) typedef int (*pfi)(int) /* pointer to funtion taking int and returning int */ void push(pfi); pfi pop(void); int compose_aux(int arg) { pfi f1,f2; f2 = pop(); f1 = pop(); return f1(f2(arg)); } pfi compose(pfi f1, pfi f2) { push(f1); push(f2); return compose_aux; } This is just the basic concept, I haven't tested it. ================== Chris Volpe G.E. Corporate R&D volpecr@crd.ge.com
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (03/01/91)
In article <ACHA.91Feb28002548@DRAVIDO.CS.CMU.EDU>, acha@CS.CMU.EDU (Anurag Acharya) writes: > In article <6873@munnari.oz.au> aet@felix.ee.mu.OZ.AU (bert) writes: > > Does anyone know how to write a compose function in C, > > without writing a Scheme interpreter to do it in. > > A call should look something like this: > > (compose(sqr,cube)) (2) which would evaluate to 64. > > "compose" is a one-liner in any functional language, > > but I suspect that it is, given the above constraint, impossible in C. > > Nope. it is possible. He then proceded to miss the point completely. The point was *not* to write a function which applies the composition of two functions to a given function, the equivalent of (define (apply-composition f g x) (f (g x))) but a function which returns a new function, which is the composition, the equivalent of (define (make-composition f g) (lambda (x) (f (g x)) )) C will let you return an *existing* function, but the standard contains no operations which can be used to create *NEW* functions at run time, and that is what was required here. The original poster wanted to be able to do things like typedef int intfn(int); intfn compose(intfn f, intfn g) { /* create a new function fg and return it */ } intfn a = compose(sqr, cube); intfn b = compose(a, a); intfn c = compose(b, iabs); On the machine I am using (an Encore Multimax) it was rather easy to implement compose() in C, but it involved -- filling a new block of memory with machine code -- casting function pointers to unsigned long -- casting (char *) to function pointer none of which operations is what you might call portable. The bottom line is that the operation *can* be implemented quite easily on many machines, without even leaving C for as much as an asm() statement, but that there is NO *portable* way of dynamically calculating a new *C* function in C. What's rather unsettling is the number of people who have completely misunderstood the question. -- The purpose of advertising is to destroy the freedom of the market.
lupienj@hpwadac.hp.com (John Lupien) (03/02/91)
In article <6316@rex.cs.tulane.edu> fs@caesar.cs.tulane.edu (Frank Silbermann) writes: >In article <6873@munnari.oz.au> aet@felix.ee.mu.OZ.AU (bert) writes: >> Does anyone know how to write a compose function in C, >> without writing a Scheme interpreter to do it in. >> A call should look something like this: >> (compose(sqr,cube)) (2) >> which would evaluate to 64. >Compose would input two functions, and return a _new_ function. >This is impossible to do _directly_ in C, >as all functions must created at compile time. >> Feel free to use pointers wherever they seem appropriate. >> (so the above call could look like: >> (*compose(&sqr,&cube)) (2) ) >I suggest you let `compose' take _three_ parameters, >the two functions and also the argument upon which the >result is to be applied, so the call would look like: >compose(&sqr,&cube, 2). This is OK, but the "compose" function should be able to take any number of function pointer arguments directly. >Alternatively, you could name a new _datatype_ `composition', >which is _implemented_ as a record of two function pointers >(comp.first and comp.second). To create compositions, >you could write a function `compose' that inputs two function pointers >and returns them embedded in a single record of type `composition'. >To apply compositions, you write a function `apply' that inputs >a composition X and an argument Y, and returns: *x.second(*x.first(Y)). This is the data-structure driven (and probably most portable) way to go about it. However, if you put the data argument first, any machine with a C compiler and library that supports "varargs(5)" (which is the "portable" variable number of arguments support package) can be used to write a "compose" function that takes a data value (of fixed type), iteratively apply each of a list of function pointers to it, and return the result. Here's an example for "double" data. The argument list must be terminated with a null pointer in this implementation, but an integer count of functions to be applied could be supplied as the second argument instead. /* start of file dbl_compose.c */ #include <varargs.h> #include <stdio.h> double dbl_compose(); double sqare(); double cub(); double halve(); void main() { double foo; foo = dbl_compose(2.0, sqare, cub, halve, (double (*)())NULL); printf("result is %f\n",foo); } double dbl_compose(va_alist) va_dcl /* note lack of semi-colon */ { va_list ap; /* arg list scanner */ double result; double (*func)(); /* function pointer */ va_start(ap); /* initialize the arglist scanner */ result = va_arg(ap,double); /* read off the data arg */ while(1) { func = (double (*)())(void *)va_arg(ap,char *); if (func == ((double (*)())NULL)) { break; } result = (*func)(result); } va_end(ap); return(result); } double sqare(foo) double foo; { return(foo * foo); } double cub(foo) double foo; { return(foo * foo * foo); } double halve(foo) double foo; { return(foo/2); } /* end of file dbl_compose.c */ --- John R. Lupien lupienj@hpwarq.hp.com