[comp.lang.misc] composition of functions

kkenny@wind.nrtc.northrop.com (Kevin B. Kenny KE9TV) (02/13/91)

Reading all the flamage about composable functions, I am forced to
note that everyone appears to agree:
	(1) Functions are not first-class objects in C
	(2) Composition is a difficult notion to express in C.
The disagreements are on the subject of whether this problem is a
major failing in the language.

With the advent of C++, the question is (almost) moot, as compositions
*are* trivial in the latter language.  The trick is to represent
functions explicitly and use operator() as the means of evaluating
them.  Will all of the arguing parties agree that the following short
program (almost) does the right thing?

[NOTE: The (almost) above is included because I can't define new
operators that act on the existing basic types.  Which is the reason
for the #ifdef NEVER, and the kludge of composing everything with the
`id' function.

It's also somewhat awkward that you can't extract a
`pointer-to-function' out of a Function, but it should be obvious why
not.  A `pointer-to-Function' is ALMOST as useful.]

Anyone for working these into an existing class library? A
Smalltalk-flavored one like NIHCL would be a better choice, since the
functionals could work with the type Object (&) (const Object &const),
and the Function class wuldn't have to be replicated for each
combination of parameter type and return type.  Templates would be
ALMOST as suitable.

Kevin Kenny, KE9TV
   cur           w        d      dis     and p
a     sed f iend  rought   eath     ease      ain.
  bles     r     b       br     and         ag

// -*- C++ -*-

#include <stream.h>

// Base class of composable function

class Function {
public:
  virtual int operator () (int) = 0;
};

// The ordinary composable function: construct around a
// reference-to-function-returning-int.


class OrdinaryFunction : public Function {
private:
  int (&f) (int);
public:
  OrdinaryFunction (int (&fn) (int)) : f (fn) {}
  virtual int operator () (int x) { return f (x); }
};

// A composition (functional form) -- construct around two composable functions

class Composition : public Function {
private:
  Function& first;
  Function& second;
public:
  Composition (Function& two, Function& one) 
    : first (one), second (two) {}
  virtual operator () (int x) { return second (first (x)); }
};

#ifdef NEVER
// I'd like to do this....
Function& operator * (int (&two) (int), int (&one) (int))
{
  return *new Composition (*new OrdinaryFunction (two),
			   *new OrdinaryFunction (one));
}
#endif

// The identity function

static int idem (int x) { return x; }

OrdinaryFunction id (idem);

// Syntactic sugar for compositions

Function& operator * (Function& two, int (&one) (int))
{
  return *new Composition (two, *new OrdinaryFunction (one));
}

Function& operator * (int (&two) (int), Function& one)
{
  return *new Composition (*new OrdinaryFunction (two), one);
}

Function& operator * (Function& two,
				Function& one)
{
  return *new Composition (two, one);
}

// The square function

int square (int x)
{
  return x * x;
}

// Let's test some things out.

int main (int, char **)
{
  // Make some compositions

  Function& sqsq = id * square * square;
  Function& sqsqsq = id * square * square * square;

  // Try functions and compositions

  cout << "square (2) = " << square (2) << "\n";
  cout << "sqsq (2)   = " << sqsq (2)   << "\n";
  cout << "sqsqsq (2) = " << sqsqsq (2) << "\n";

  // Try creating a composition on the fly.

  cout << "(square * square) (3) = " << (id * square * square) (3) << "\n";
  return 0;
}

bliss@sp64.csrd.uiuc.edu (Brian Bliss) (02/16/91)

>the question was:  how do I write a function
	typedef int i2ifn(int);
	i2ifn compose(i2ifn f, i2ifn g) { /* fill this in */ }
>so that compose(f,g)(x) == f(g(x)).


you say

int (*f1)(), (*f2)();

int retval (x) { (*f1)((*f2)(x));}

int (*compose (f, g))()
   int (*f)(), (*g)();
   {
      f1 = f;
      f2 = g;
      return (retval);
   }



if you don't like using global variables, then you have to
say

struct CLOSURE {
   int (*func)();
   struct LOCALS *locals;
}
with the understanding that applying a closure is to say
(*func)(locals, args...),
and that any (would-be)local variables that the called function 
uses are found in the struct LOCALS.

this is plain, portable C.

bb

ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (02/20/91)

In article <1991Feb15.230112.2902@csrd.uiuc.edu>, bliss@sp64.csrd.uiuc.edu (Brian Bliss) writes:
> >the question was:  how do I write a function
> 	typedef int i2ifn(int);
> 	i2ifn compose(i2ifn f, i2ifn g) { /* fill this in */ }
> >so that compose(f,g)(x) == f(g(x)).

> you say

> int (*f1)(), (*f2)();

> int retval (x) { (*f1)((*f2)(x));}

> int (*compose (f, g))()
>    int (*f)(), (*g)();
>    { f1 = f; f2 = g; return retval; }

Spare me days!  This completely (almost definitively) misses the
point.  If I do
	fg = compose(f, g);
	hk = compose(h, k);
the later call to compose() should not invalidate the earlier result!
This atrociously buggy pseudo-implementation *guarantees* that
	compose(compose(f,g),h)(x)
will not work, which it would in a language with first-class functions.
 
-- 
Professional programming is paranoid programming