Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!chalmers.se!mathrt0.math.chalmers.se!augustss
From: augustss@cs.chalmers.se (Lennart Augustsson)
Newsgroups: comp.lang.misc
Subject: Re: On whether C has first-class composable functions
Message-ID: <1991Jan5.182428.615@mathrt0.math.chalmers.se>
Date: 5 Jan 91 18:24:28 GMT
References: <1990Dec29.110202.3862@mathrt0.math.chalmers.se> <17557:Jan219:22:3191@kramden.acf.nyu.edu> <442@data.UUCP> <4408:Jan421:44:3391@kramden.acf.nyu.edu>
Sender: news@mathrt0.math.chalmers.se (Evald Nyhetsson)
Organization: Dept. of CS, Chalmers, Sweden
Lines: 102

In article <4408:Jan421:44:3391@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>In article <442@data.UUCP> kend@data.UUCP (Ken Dickey) writes:
>> [ ... ]
>> There is an important property of "first-class" objects missing here.
>> A first-class object does not have to be named.  
>
>Do you have a reference? As always, I'm doing my best to use standard
>terminology; I just haven't seen any references that demand a syntactic
>restriction like that.
>
I wouldn't call the ability to have unnamned functions just a syntactic
extension, it has big semantic consequences.  Here's why:

(Since most people seems to think it OK to blur the distinction between
C-functions (I will write C-functions when I mean the builtin function type
in C to avoid confusion) and C-functions pointers I will do that.
Nitpicks can insert "pointer to" where appropriate.)

First, what do we mean by a semantic difference.  I quote from one of Dan's
articles:
> ... In C I get a machine with an unbounded (though not
> infinite) amount of memory; in Fortran I have to decide memory bounds in
> advance, and certain programs using a lot of dynamic allocation are
> simply impossible to write. *That* is a big difference, and I wish we
> could reserve ``has'' for situations like this. ``C has memory
>allocation power that Fortran doesn't.''
I assume that this counts as a semantic difference.  It can be summed up as:
The amount of memory available to a C program is not bounded by the
program itself (only by the implementation you run the program in).

I think that both Dan and I agree on this point.


Second, the number of C-functions in a C program is bounded.  This is
quite natural since every C-function has to be given a name and there can
only be a bounded number of named things in a program of bounded size.
This means that C-functions does not enjoy the same status as objects
of other types in C, where it is possible to get an unbounded number of
them.  The bounded number of C-functions is the real reason why a 
C-function compose (for C-functions) cannot be written in C.  Since
composition can give you an unbounded number of different C-functions,
but there is only a bounded number of them available it has to fail.
(This is why Kristoffer Eriksson "solution" cannot be made to work
in the general case.)
To paraphrase: ... and certain programs using a lot of composed C-functions are
simply impossible to write. 
So, C-functions are not composable and I think that both Dan and I 
agree on this point.


Third,
I will now extend C by unnamed C-functions.  If we take an ordinary
C-function declaration and replace the C-function name with ANONYMOUS
we will get an expression which has C-function type (what an abominable
syntax!).
So for example the declaration
	int succ(int x) { return x+1; }
can now be written (analogous to "int five = 5;")
	int (*succ)(int) = int ANONYMOUS(int x) { return x+1; };
and either of them used by "succ(5)".
The expression "(int ANONYMOUS(int x) { return x*2; })(21)" will 
evaluate to 42.

The unnamed C-functions should behave as ordinary C-function definitions
when it comes to scoping, i.e. all variables in a C-function should
be either arguments, local variables, or defined in an outer scope.
The C-function expression should also behave as a normal C expression,
i.e. it can be sent as an argument, returned etc.


Finally, I can now write a compose C-function^:
typedef int (*intintfun)(int);
intintfun compose(intintfun f, intintfun g)
{
	return (int ANONYMOUS(int x) { return f(g(x)) };
}
Since I am now able to write a C-function that according to my second
point was impossible to write in standard C this must mean that I
have changed the semantic power (according to the definition
of semantic power in the first point) of C-functions.

A change in a language that changes the semantic power of a type
in the language in this way is not what I would call a just syntactic
change.

(You could argue, quite correctly, that it is not the unnamed functions as
such that gives you the power, but rather the ability to return a locally
defined function.  But the point is that you cannot add unnamed functions
in a natural way without getting the additional semantic power.)



^ Footnote:
The careful reader will see than my compose C-function has a different
type than it has had in my previous examples.  All my previous prototypes
have been subtly wrong, but since nobody has complained about this I don't
think this has confused anyone.



	-- Lennart Augustsson
[This signature is intentionally left blank.]