Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!warwick!nott-cs!piaggio!anw
From: anw@maths.nott.ac.uk (Dr A. N. Walker)
Newsgroups: comp.lang.misc
Subject: Re: On whether C has first-class composable functions
Message-ID: <1991Jan8.184708.15822@maths.nott.ac.uk>
Date: 8 Jan 91 18:47:08 GMT
References: <1991Jan05.222639.6387@dirtydog.ima.isc.com> <1991Jan6.171234.27734@d.cs.okstate.edu> <1991Jan07.045733.13637@dirtydog.ima.isc.com>
Reply-To: anw@maths.nott.ac.uk (Dr A. N. Walker)
Organization: Maths Dept., Nott'm Univ., UK.
Lines: 88

In article <1991Jan07.045733.13637@dirtydog.ima.isc.com>
karl@ima.isc.com (Karl Heuer) writes, in response to Norman Graham,
>>names have scope--values do not.
>True.  I should have said "storage duration".

	Depends on the language!  (I realise that the thread is nominally
about C, but since we're trying to extend it, we have to drag in ideas
from elsewhere.)  I quote from MR93, the Algol 68 Draft Report [my copies
of the actual Report and Revised Report having gone walkabout], section
2.2.4.2.b:

	The scope of a plain value [eg, 7 -- ANW] is the program, ...,
	that of a routine ... denotation ... is the smallest range
	containing a defining ... occurrence of an identifier ...
	applied but not defined within that denotation, ... and
	that of a name is some range.

>It's not f and g that are being used beyond their storage duration, it's the
>anonymous function itself.

	In Algol, at least, it's "f" and "g" that are the problem.  The
occurrences of "f" and "g" within the procedure body restrict its scope
to the range defined by (the text of) "compose".  The following:

	BEGIN PROC compose = (PROC(REAL)REAL f, g) PROC(REAL)REAL:
		(REAL x) REAL: sin (cos (x));
	      print (compose (tan, sqrt) (0))
	END

compiles and prints 0.84..., ie it correctly composes sin and cos, but
if I replace sin and cos by f and g, the resulting program aborts with
a scope violation.  I suspect that if C added anonymous &/or nested
functions, they would look more like Algol than like applicative
languages, and that the same scope rules for closures would apply.

	The other way that has been mentioned is through partial
application -- Charles Lindsey has provided the following example in
a reasonably simple extension of Algol [which would surely also be
partially applicable to C]:

	PROC compose = (PROC(REAL)REAL f, g, REAL x) REAL: f(g(x));
	PROC(REAL)REAL sex = compose (sqrt, exp, );
		# note the missing third parameter #

The following is neat:

	OP ^ = (PROC(REAL)REAL a, INT b) PROC(REAL)REAL:
		((PROC(REAL)REAL a, INT b, REAL p) REAL:
			(REAL x := 1; TO b DO x *:= a(p) OD; x))(a, b, );
	REAL theta; ...;
	print ((cos^2)(theta) + (sin^2)(theta)) # had better print 1 ! #

>Of course, you can also consider a further extension in which functions are
>allocatable; ...

	There are, of course, different sorts of allocation.  In both C
and Algol, you can't generate lots of new functions *and export them to
other parts of the program*, but at least in Algol you can generate as
many new functions as you need through recursion.  I rediscovered the
following yesterday while searching some dusty decks for other reasons.
It's a program [due to Dick Grune] for parsing the grammar

		S -> aSS | a
		T -> Sb

As it stands, it just counts the number of parses, and is clearly a toy,
but it works.  Change the TAIL of "t" to do cleverer things, and change
the structure of "s" and "t" to change the grammar.

  BEGIN MODE TAIL = PROC VOID, RULE = PROC (TAIL) VOID;
	INT n := 0; STRING input;
	RULE a = (TAIL q) VOID: (n +:= 1; (input [n] = "a" | q); n -:= 1),
	     b = (TAIL q) VOID: (n +:= 1; (input [n] = "b" | q); n -:= 1),
	     s = (TAIL q) VOID: (a (VOID: s (VOID: s (q))); a (q)),
	     t = (TAIL q) VOID: s (VOID: b (q));
  # example of use: #
	FOR i TO 12 DO INT count := 0; input := "aaaaaaaaaaab" [i:];
		       t (VOID: count +:= 1); print ((count, newline))
		    OD
  END

Best of luck if you try to re-write this in C.  Pascal might be possible,
but I wouldn't like to try to understand the result, whereas the above is
perfectly clear [:-)], despite all the anonymous procedures.

-- 
Andy Walker, Maths Dept., Nott'm Univ., UK.
anw@maths.nott.ac.uk