Path: utzoo!mnetor!tmsoft!torsqnt!lethe!yunexus!ists!helios.physics.utoronto.ca!news-server.csri.toronto.edu!cs.utexas.edu!uunet!samsung!spool.mu.edu!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
Message-ID: <1991Feb8.201117.7515@spool.cs.wisc.edu>
Date: 8 Feb 91 20:11:17 GMT
References: <12547:Feb621:05:4491@kramden.acf.nyu.edu> <1991Feb7.150537.9257@spool.cs.wisc.edu> <25199:Feb801:33:1191@kramden.acf.nyu.edu>
Sender: news@spool.cs.wisc.edu (The News)
Organization: U of Wisconsin CS Dept
Lines: 93

In article <25199:Feb801:33:1191@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>In article <1991Feb7.150537.9257@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes:
>> Unfortunately, this doesn't solve the problem.  Your `functions' are not
>> functions.  What happens when I pass a Bernstein `function' to twalk(3c)??
>
>``Unfortunately, your bignum package doesn't solve the problem. Your
>`bignums' are not numbers. What happens when I pass a DECWRL bignum to
>getcwd()??''
>
>The mistake here is the second statement. Bignums are numbers; they just
>aren't the same as C's integers. Similarly, anything supporting certain
>operations is a function; it doesn't have to be the same as C's
>functions.
>

Number, bignum and integer are not C types.  int is a C type.  I expect
to be able to apply the integer operators in C to ints.  I don't expect
C's built in operators to apply to bignums.  (Of course in C++ we can manage
this.  Some languages do support overloading and/or polymorphism.)

Compose is a binary function taking two unary functions as arguments
producing a unary function.  In the trivial case where we have int->int
for everything, we have something that is indeed a valid C type:

int (*compose)(int (*f)(int), int (*g)(int))

I expect to be able to use the result of compose as a pointer to a function
from ints to ints.

We have a valid C type for compose, why can't we use it?

"Anything supporting certain operations etc." gives you two incompatible
classes of ``functions.''  Applied to C I must admit that I cannot find
this passage in the first or second edition of K&R.  Dan, do you have the
page number handy?  In any case, why is this crap necessary?  Why can't the
output of one invocation of compose be used an argument to another compose?
Are we going to write two composes as well?

This thread began when someone said "C doesn't have first-class functions
because it can't handle compose."  Dan objected, saying compose was trivial
in C and C does too have first-class functions and then gave a compose
implementation that returned a struct, not a function pointer.  Unwittingly
Dan proved the original poster to be correct:  If C had first-class
functions compose could return a function rather than a structure.

  A) Dynamic allocation is a source of expressive power in a language.

Dan said this once and I agree.  We are together at point A.

  B) First-class status requires that dynamic allocation be possible.

I think I probably lose Dan between point A and point B.  But what really
puzzles me is

  C) C functions are not dynamically allocable.

Dan has repeatedly denied C.  The only proof he can offer is to redefine
function.  Actually I am getting used to Dan redefining terms in the CS
lexicon whenever his opponent gets the upper hand in an argument.  It
must be a sign of desparation that Dan now tries redefine common English
words such as ``has''.  To me, "C functions are not dynamically allocable"
and "C doesn't have dynamically allocable functions" have identical
meaning, but to hear Dan tell one of those statements has "to be able to
implement X in L" mixed up in it (don't ask me which one).

	"Aber nein!  [Herr Bernstein] is capable of making the
	 finest distinctions!"  -- David Hilbert

(An obscure reference to a bon mot of Hilbert's.  Dan is a math genius
who can't learn anything a mere book, but for anyone else I recommend
_Hilbert_ by Constance Reid.  And I still highly recommend _The_Structure_
and_Interpretation_of_Computer_Programs_.  Only small minds are afraid
of ideas that may be new to them.)

A great advantage of languages with first-class functions over languages
like C is that it is unnecessary to use Newspeak and call struct bletch
a function.

Actually, most C programmers don't feel the need to act like Big Brother
Dan.  They would simply say, "Yes, this isn't a strong point of C.  The
best work-around is inconvenient, but it is usable in some cases.
Generally I use C for tasks that don't require much functional composition."

For some reason, Dan is insanely protective of C, like a mother for her
child.  C is 20 years old, and the state of the art in programming
languages has improved somewhat since then.  Dan should learn a non-Algol
language before proclaiming himself an expert on programming languages.
He could start with SML, since he seems to be completely ignorant of it.
Otherwise Hope or Miranda or Scheme or any of a whole slew of other languages
would do him good.

-- Doug Quale
quale@picard.cs.wisc.edu