[comp.lang.c] function composition in C

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...

browns@iccgcc.decnet.ab.com (Stan Brown) (02/27/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.

Okay, this is so obvious that there must be a reason why you're _not_
doing it:
       sqr(cube(2));
I must not understand what question you're asking.

My opinions are mine:  I don't speak for any other person or company.
                                   email: browns@iccgcc.decnet.ab.com
Stan Brown, Oak Road Systems, Cleveland, Ohio, USA    +1 216 371 0043

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

gwyn@smoke.brl.mil (Doug Gwyn) (03/01/91)

In article <1991Feb28.072757.1904@bingvaxu.cc.binghamton.edu> kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) writes:
>I don't think anyone was saying your method was not valid, but functional
>composition returns a _function_ given two other functions.

Which makes this topic unsuitable for discussion in the C newsgroup.
In C, functions are always statically defined.

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.

REIDMP@MAINE.BITNET (Reid M. Pinchback) (03/02/91)

gwyn@smoke.brl.mil (Dough Gwyn) writes:
* >I don't think anyone was saying your method was not valid, but functional
* >composition returns a _function_ given two other functions.
 
* Which makes this topic unsuitable for discussion in the C newsgroup.
* In C, functions are always statically defined.
 
Isn't it a bit abrupt to forestall questions in this manner?  One of
the joys of reading newsgroups like this is to have the chance to
consider problems that we haven't thought of before; its not like the
original poster cross-posted to a large number of irrelevant groups.
 
Functions are statically defined in C, but we can consider ways to
circumvent this.  I can think of three ways we can attempt this:
 
   1. Use data abstraction techniques to pass around lists of pointers
      to functions and 'compose' them on the fly;
   2. Generate compiled code for the compositions at run time and
      have the OS change the relevant data 'segment' into code.
   3. For reasonable mathematical functions, describe the function
      as lists of operators and variables.  Compositions could be
      as simple as changing one item in the appropriate data structure.
      Evaluation would consist of a list traversal.  This need not be
      as involved as something like implementing scheme in C.
 
Still sounds like C to me.
 
 

robert@Neon.Stanford.EDU (James R. Kennedy) (03/03/91)

In article <9754@uwm.edu> markh@csd4.csd.uwm.edu (Mark William Hopkins) 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.
> ...
> 
> You could do it compile-time like this example for composing x^2 and
> 2*x:
> [... code deleted ...]

Everyone seems to have ignored an important issue that harks back to
yet another major war on the structure of C, namely the "typeof()"
debate. I don't want to restart it here, but I do want to point out
that the solution proposed in the parent to this article as well as
the solution proposed by the person who suggested storing compositions
as structs and using an "apply" function work only for one type. I had
the impression that the author of the original article was looking for
a type-independent way to do function composition in C, since to my
mind, THAT is the main thing allowed by the obvious Scheme construct
but utterly unavailable in C.

Robert Kennedy
Department of Computer Science
Stanford University

louk@tslwat.UUCP (Lou Kates) (03/06/91)

In article <91060.132635REIDMP@MAINE.BITNET> REIDMP@MAINE.BITNET (Reid M. Pinchback) writes:
>gwyn@smoke.brl.mil (Dough Gwyn) writes:
>* >I don't think anyone was saying your method was not valid, but functional
>* >composition returns a _function_ given two other functions.
> 
>* Which makes this topic unsuitable for discussion in the C newsgroup.
>* In C, functions are always statically defined.
> 
>Isn't it a bit abrupt to forestall questions in this manner?  One of
>the joys of reading newsgroups like this is to have the chance to
>consider problems that we haven't thought of before; 

Perhaps we need  to consider  what you   need to add to C to  get
this with the minimal change to C.

You should be able to do function composition in OO extensions to
C. In particular, consider the class C, each of whose objects has
the publicly settable function pointers fp  and gp and the method
c(x) which   returns  f(g(x))  where f  and g  are the  functions
pointed at by fp and gp.

Then the composition of f and g  can be constructed by creating a
new object  of class C, setting the function pointers to point to
f and g and returning a function pointer to c.

Can this be  done  in C++? Objective  C? other OO extension to C?
Assuming that this works, code this in  an OO extension to C that
operates as a preprocessor to C and look at the generated C code.
What is that has been added that allows this to work?

Lou Kates, Teleride Sage Ltd., louk%tslwat@watmath.waterloo.edu

torek@elf.ee.lbl.gov (Chris Torek) (03/06/91)

In article <347@tslwat.UUCP> louk@tslwat.UUCP (Lou Kates) writes:
>Perhaps we need to consider what you need to add to C to get
>this with the minimal change to C.

Probably such consideration belongs in alt.lang.cfutures, but since
alt.* groups have weaker propagations...:

>You should be able to do function composition in OO extensions to C.
In particular, consider the class C, each of whose objects has the
>publicly settable function pointers fp and gp and the method c(x)
>which returns f(g(x)) where f and g are the functions pointed at
>by fp and gp.

This only works for a single return type.  Since the type system in
any C-like language is infinitely extensible (each new `struct' is a new
type, for instance), either the composition function must be polymorphic
(choose your favourite other word here for `accepts arbitrary types')
or else you must resort to trickery, e.g., `the machine internally has
only this many types'.

The problem continues (only more so) for binding of arguments, e.g.,
there is no good way to define a function:

	; compose takes a function f of $k$ arguments, a function g of
	; one argument, and arguments $x_1 .. x_k$, and produces a new
	; function of one argument which is equivalent to
	;	(f (g arg) x1 x2 ... xk).

You might as well give in and use Scheme. :-)
-- 
In-Real-Life: Chris Torek, Lawrence Berkeley Lab EE div (+1 415 486 5427)
Berkeley, CA		Domain:	torek@ee.lbl.gov

peter@ficc.ferranti.com (Peter da Silva) (03/07/91)

See my recent article in comp.lang.misc. In general you can't compose normal
functions in any language that doesn't have an interpreter stage, such
as lisp or an object-oriented language like SmallTalk. But you can
implement objects in C: this is what C-preprocessors like CO2 and C++
do. They basically write a micro-interpreter for function calls using a
jump-table, and convert calls to these objects into calls to an application
function and an indirection through this jump-table. You can do the same
thing on a smaller scale to get the effect of first-class functions: but
these first-class functions are *not* C functions.
-- 
Peter da Silva.  `-_-'  peter@ferranti.com
+1 713 274 5180.  'U`  "Have you hugged your wolf today?"

broome@smoke.brl.mil (Paul Broome) (03/08/91)

In article <347@tslwat.UUCP> louk@tslwat.UUCP (Lou Kates) writes:
:
:In article <91060.132635REIDMP@MAINE.BITNET> REIDMP@MAINE.BITNET (Reid M. Pinchback) writes:
:>gwyn@smoke.brl.mil (Dough Gwyn) writes:
    >someone else wrote:
:>* >I don't think anyone was saying your method was not valid, but functional
:>* >composition returns a _function_ given two other functions.
:> 
:>* Which makes this topic unsuitable for discussion in the C newsgroup.
:>* In C, functions are always statically defined.
:> 
:>Isn't it a bit abrupt to forestall questions in this manner?  One of
:>the joys of reading newsgroups like this is to have the chance to
:>consider problems that we haven't thought of before; 
:
:Perhaps we need  to consider  what you   need to add to C to  get
:this with the minimal change to C.
:
:You should be able to do function composition in OO extensions to C...

True function composition is associative.  That is,
compose(f,compose(g,h)) = compose(compose(f,g),h).  A proposal for such 
extensions should consider whether this property will hold true.

Function composition is a very powerful concept as it's a good way to control
complexity.  But to be useful for programming in C you'd have to preclude
side effects.  This would completely change the character of the language.
Doug is right.  The topic is not appropriate (although it is interesting!).

One place to read more about it is in a recent book on Functional Programming
by Richard Bird and Phil Wadler or in the group comp.lang.functional.

-Paul
<broome@brl.mil>