Path: utzoo!attcan!uunet!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: <1991Feb7.150537.9257@spool.cs.wisc.edu>
Date: 7 Feb 91 15:05:37 GMT
References: <1234:Feb520:27:2391@kramden.acf.nyu.edu> <1991Feb6.161639.18311@spool.cs.wisc.edu> <12547:Feb621:05:4491@kramden.acf.nyu.edu>
Sender: news@spool.cs.wisc.edu (The News)
Organization: U of Wisconsin CS Dept
Lines: 65

In article <12547:Feb621:05:4491@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>
>You are making Jim Giles' mistake of confusing syntax and semantics.
>Just because the C standard calls certain language objects ``functions''
>doesn't mean that it's impossible to implement functions that don't have
>the same restrictions as those objects. As a matter of fact, it's not
>only possible, it's trivial.
>

Unfortunately, this doesn't solve the problem.  Your `functions' are not
functions.  What happens when I pass a Bernstein `function' to twalk(3c)??

The question was NEVER, "Can C _implement_ dynamically allocable functions?"

I can implement a Turing machine simulator in practically any language,
but it's not very interesting or useful.

Does C _have_ dynamically allocable functions?

No.

A short session in SML (which does have first-class functions):

- fun square i : int = i * i;
val square = fn : int -> int
- (square o square) 2;
val it = 16 : int
- ((square o square) o square) 2;
val it = 256 : int
- (square o (square o square)) 2;
val it = 256 : int

The last is a nested call to the builtin compose operator, o,
whose definition is:

- infix o;
- fun f o g = fn x => f (g x);
val o = fn : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b

Compose has a simple mathematical definition, and since Dan is so proud
of his math, he surely knows that (f o g) o h = f o (g o h).
(Strangely he expressed confusion over a nested call to compose in a
posting made by someone else some time ago, but this is really quite
elementary.)

Let's see Bernstein's compose function do that.  (On a related note,
he also claimed that it is just as easy to prove program correctness in
C as it is in a functional language.  Since his implementation of compose
in C doesn't obey one of the most trivial identities for that function,
I wonder how he reaches that bizarre conclusion.)

Given Dan's pride in his math I'm tempted to call "First-class functions,
or Why You Can't Write compose in C" the pons asinorum of the study of
computer programming languages.

P.S. Dan, read _The_Structure_and_Interpretation_of_Programming_Languages_,
     by Abelson, Sussman and Sussman.  Jim Giles said he didn't learn
     anything useful from that book, but I certainly did and you might too.
     At the very least it will show you what you can do with first-class
     functions.  (A short preview:  blocks, delayed evaluation,
     call-by-name, own variables, coroutines, non-local exits and
     objects for OOP.)

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