Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!clyde.concordia.ca!nstn.ns.ca!news.cs.indiana.edu!att!linac!uwm.edu!zaphod.mps.ohio-state.edu!rpi!uupsi!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: <6828:Feb906:14:3491@kramden.acf.nyu.edu>
Date: 9 Feb 91 06:14:34 GMT
References: <1991Feb7.150537.9257@spool.cs.wisc.edu> <25199:Feb801:33:1191@kramden.acf.nyu.edu> <1991Feb8.191014.6430@spool.cs.wisc.edu>
Organization: IR
Lines: 96

In article <1991Feb8.191014.6430@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes:
> In article <25199:Feb801:33:1191@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
> >I chose the subject line (I choose most subject lines in comp.lang.misc
> >these days) and I was using ``L has X'' to mean ``X can be implemented
> >in L'' where L is a language and X is a semantic feature. Apparently
> This is not the meaning of ``has''.  X can be implemented in L is a
> meaningless statement for any languages that are Turing equivalent.

First of all, most real languages are not equivalent to Turing machines.
People commonly use one of two models for programs. The first says,
roughly, that a program is valid if its memory use is bounded by a fixed
amount over all possible inputs. (This is for people who don't worry
about running out of memory.) The second says, roughly, that a program
is valid if its memory use is between N and N+K for all inputs, where N
depends on the program and K does not. (This is for when you are
worrying about running out of memory.) Both models suffice for real
languages. Neither model allows a Turing machine. That's why ``has''
does distinguish languages that have, e.g., dynamic allocation from
languages that don't.

Second, you didn't respond to my challenge to provide a useful
definition of ``L has X'' for L a language and X a semantic feature. I
claim that my definition is (1) unambiguous and (2) useful. Why do I say
it's useful? Because ``has'' is a helper word. Sure, the statement ``C
has first-class functions'' (meaning ``first-class functions can be
implemented in C'') doesn't say much. But you can qualify it! You can
say ``C has efficient first-class functions'' (``first class functions
can be implemented efficiently in C'') or ``C has easy-to-use
first-class functions'' or ``C has easy-to-implement first-class
functions.''

> Meaningless terminology is not useful,

Nevertheless, it has been defined for the purposes of this discussion,
so it is no longer meaningless in context.

> and quite frankly Dan, I challenge
> you to give me evidence that _anyone_ uses ``has'' in the sense(lessness)
> that you do.

Webster's, definition 5c(b): ``exercise.'' Their example: ``have mercy
on us.'' ``Mercy'' is a trait---a semantic feature. ``Doug Quale has
mercy on us'' means that you stop rehashing every little bit of a dead
discussion---uh, I mean, that Doug Quale exercises mercy, i.e., Doug
combines his primitive operations to implement mercy. ``Doug has mercy
upon you'' doesn't mean that mercy is one of Doug's *basic* traits, or
that mercy is defined as part of Dougginess, or that Doug *always*
exercises mercy, or that Doug can show mercy without outside help;
similarly for ``C has dynamically allocatable functions.'' And, before
you post some irrelevant quibble, let me point out that this definition
of ``has'' can be applied to impersonal, inactive objects: ``inetd.conf
has control over your connections.''

> I don't think I can say anything more about this.

Then don't.

> >That call was improperly formed and nonsensical as both a mathematical
> >expression and a C language expression.
> Dan, wtf are you talking about??

You referred to the time when I expressed confusion over the supposed
meaning of somebody's nested compose() call. In case you don't remember,
the call in question tried to compose the compose function with an
integer function. Once again, that call was improperly formed and
nonsensical as both a mathematical expression and a C language
expression.

> 	square o square o square
> is perfectly sensible as a mathematical expression.

Yes.

  [ about the square examples again ]
> And yes, Dan, I specifically request you to try explain what is nonsensical
> about those expressions.

I never said that those expressions were nonsensical. Your implication
is a lie, plain and simple. I doubt you have the integrity to review the
articles and apologize, but I'll give you one chance to do so before I
start quoting things in public.

> Instead of continually saying it's trivial, post your compose code in C and
> then we'll see how it stacks up.

I did. Since you apparently would rather flame than think, here's the
three-way composition that you claim to be so difficult. I've written it
out step-by-step and put in comments just for you.

  compose(square,square,sqsq) /* put square o square in sqsq */
  compose(square,sqsq,sqsqsq) /* put square o sqsq in sqsqsq */
  printf("%d\n",apply(sqsqsq,2)); /* apply sqsqsq to 2 and print it */

Exercise: write the missing struct fun definitions and initializations.

---Dan