Path: utzoo!mnetor!tmsoft!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!rpi!sci.ccny.cuny.edu!phri!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: On whether C has first-class composable functions
Message-ID: <17557:Jan219:22:3191@kramden.acf.nyu.edu>
Date: 2 Jan 91 19:22:31 GMT
References: <19418@yunexus.YorkU.CA> <23986:Dec2703:47:1390@kramden.acf.nyu.edu> <1990Dec29.110202.3862@mathrt0.math.chalmers.se>
Organization: IR
Lines: 114

In e-mail discussions Dave Gudeman has shown me what I was missing about
Lennart's original statement. Here goes.

Lennart started by saying that C does not have first-class functions. It
was reasonably clear that what he meant was that C does not have
first-class composable functions, and that's what I objected to.

I think we all agree on what ``first-class,'' ``composable,'' and
``function'' mean. A first-class object can be passed as arguments and
assigned to variables. A function is something for which there exists
one evaluation operator for each value of some type. A composable
function also supports a composition operation with the obvious
definition. This is all reasonably standard terminology.


The problem is what ``has'' means. There are at least three workable
definitions of ``C has first-class (composable) functions.'' The first,
which I call NP (nitpick): ``The things that C calls `functions' are
first-class objects (which are composable).''

The second, BI (builtin): ``C has some built-in objects which are
first-class (composable) functions.'' This is slightly ambiguous,
because it's not clear what a ``built-in object'' is. I will return to
this point below.

The third, POW (power): ``C supports certain language features
sufficiently well to implement objects which are first-class
(composable) functions.''


Now NP is obviously wrong, both with and without ``composable.'' The
things that C calls ``functions'' aren't even first-class.

POW is right, both with and without ``composable.'' One example of a
first-class function in C is ``pointer to function''; the evaluation
operation is ``dereference and then call as a function.'' One example of
a first-class composable function in C is ``pointer to structure
containing an integer and either one function pointer or two structure
pointers depending on the integer''; I described the evaluation and
composition operations on this type in detail in a previous article.

Whether BI is right depends on your definition of ``built in.'' I don't
see any reasonable definition other than ``atomic''---and by that
definition, pointers to functions are not ``built in'' any more than
pointers to structures containing blah are. This means that BI is wrong,
both with and without ``composable.'' (But see below.)


When I read Lennart's statement I automatically assumed he meant POW.
NP means that you're blindly accepting the language's terminology, and
can't see beyond ANSI C ``function'' when you think about functions in
C. I think BI also reflects a confusion between syntax and semantics:
how something is expressed in a language is irrelevant to the language's
raw power. So I responded by showing one way to construct first-class
composable functions in C.

Dave focused on Lennart's original statement, viz., that C doesn't have
first-class functions. He said that what C calls ``pointers to
functions'' really are first-class. Not only that, but they are
functions, because they can be evaluated. Just because C doesn't call
these things ``functions'' doesn't mean they aren't functions.

Dave was certainly not referring to NP. To me it was obvious that he
wasn't referring to BI, for the reasons outlined above, so he must have
meant POW.

Then people started attacking my response. ``You're misusing
terminology!'' Oh? What terminology was I misusing? I took the most
natural definition of ``has.'' I think it's a big mistake to confuse
syntax and semantics. ``Your solution is obvious!'' Yes, of course it
is---but Lennart and Dave kept saying that C didn't have composable
functions. This left me confused until Dave explained the missing step.


Lennart and Dave are taking BI as their definition. They're defining
``built in'' as ``having operations equivalent in syntax to builtins''
with the second ``builtin'' meaning ``atomic'' in my sense. For example:
Because (in common practice, and with the ANSI kludge) you use the same
syntax to call a function pointer as you use to call a function, a
function pointer is a builtin. Hence C ``has'' first-class functions in
this sense. In contrast, calling one of my struct funs does not have the
same syntax, so my struct funs are not builtins. Hence C does not
``have'' first-class composable functions in this sense.

I don't like this, for at least two reasons. First, it does not match
K&R C. There are many compilers where you must dereference a function
pointer before calling it. Does this change function pointers from
``built in'' to ``not built in''? Second, it takes a statement about
abstract language power like ``C has composable functions'' and turns it
into a statement combining both syntax and semantics. I think that's an
abuse of terminology---hiding cheap syntactic restrictions under an
innocent word like ``has.'' But at least this clears up the confusion.


As a programmer, I don't care about the syntax of a language as much as
I care about its efficiency---but neither one matters as much as
language power. 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.''

Only when we're sure about equal power can we consider other issues.
Efficiency is always a big concern. At some point BI becomes important:
``You can implement this with the built-in syntax.'' When all else is
equal, NP tips the scales: ``The basic language includes exactly the
feature you want with exactly this syntax.''

To sum up: ``C has first-class composable functions with reasonable
efficiency and without ridiculously complicated syntax'' is good enough
for me.

---Dan