Path: utzoo!attcan!uunet!samsung!sol.ctr.columbia.edu!caen!uwm.edu!uwvax!picard.cs.wisc.edu!quale
From: quale@picard.cs.wisc.edu (Douglas E. Quale)
Newsgroups: comp.lang.misc
Subject: Re: On whether C has first-class composable functions
Summary: using the correct tool
Message-ID: <1991Jan13.045906.6210@spool.cs.wisc.edu>
Date: 13 Jan 91 04:59:06 GMT
References: <4408:Jan421:44:3391@kramden.acf.nyu.edu> <1991Jan5.182428.615@mathrt0.math.chalmers.se> <4762@pkmab.se>
Sender: quale@picard.cs.wisc.edu
Organization: U of Wisconsin CS Dept
Lines: 85

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