Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!clyde.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!hsdndev!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: On whether C has first-class composable functions
Message-ID: <23732:Jan619:29:4491@kramden.acf.nyu.edu>
Date: 6 Jan 91 19:29:44 GMT
References: <442@data.UUCP> <4408:Jan421:44:3391@kramden.acf.nyu.edu> <1991Jan5.182428.615@mathrt0.math.chalmers.se>
Organization: IR
Lines: 92

Summary: I implied that the ability of an object to be unnamed was a
syntactic feature. Here Lennart tries to prove the opposite, by what
reduces to the following argument: C functions are not allocatable. If C
is extended with functions without names, then it gains power. Therefore
unnamed functions are a semantic feature.

The mistake in this argument is the second step. As Karl points out in
another article, C does not gain power when you add unnamed functions.
*Allocatable* functions are indeed semantic, and when you add them you
do indeed get some power.

In article <1991Jan5.182428.615@mathrt0.math.chalmers.se> augustss@cs.chalmers.se (Lennart Augustsson) writes:
> 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:
> > > 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:

Wait a minute. This still doesn't answer my question, which is whether
anyone defines ``first-class'' to include the restriction ``can be
defined without a name.''

You're talking about the side issue of whether this ``unnamability'' is
a syntactic restriction or a semantic restriction. Let's analyze your
argument, step by step:

1. ``The number of C-functions in a C program is bounded.'' True.

2. ``C-functions do not enjoy the same status as objects of other types
in C, where it is possible to get an unbounded number of them.'' This is
true. The property that the other objects have is ``allocatability.''

3. ``The bounded number of C-functions is the real reason why a
C-function compose (for C-functions) cannot be written in C.'' Although
I agree with what you're trying to say, you're not saying it right. What
you have observed is that C-functions are not allocatable. But this
property is independent of ``first-class'' and ``composable.'' 

Eriksson's solution does show how to compose C-functions. You are
entirely correct that a new C-function cannot be generated dynamically,
but this is an independent problem.

> So, C-functions are not composable and I think that both Dan and I 
> agree on this point.

Not at all. Please stop changing your terms in the middle of the
discussion. First-class is not the same as composable, or unnamable, or
allocatable. It's a very specific adjective that refers to what you can
do with old data.

4. ``Certain programs using a lot of composed C-functions are simply
impossible to write.'' More precisely, programs cannot dynamically
allocate C-functions. This is true.

You then extend C with ``unnamed C-functions.'' As Karl points out in
another article, your extension is simply flawed. What's the flaw? You
don't allocate space for your new functions, so you can't return them.
Can't you see that the problem is just like the problem of char *foo()
{ char s[100]; ... return s; } ?

What makes char *'s and C-functions different is that char *'s are
*allocatable*. You can *allocate* a new string to pass back to your
caller. You can't *allocate* a new function.

Unnamability is entirely independent of allocability. The former is a
syntactic restriction. The latter is a semantic restriction. Your
argument confuses the two and hence falls apart.

5. ``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.'' Nice try, but no cigar. What
you have managed to prove is that *allocatability* is a semantic
feature.

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

Agreed. However, your change does not affect semantics.

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

That point is simply wrong.

---Dan