Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!sdd.hp.com!ucsd!ucbvax!bloom-beacon!eru!hagbard!sunic!news.funet.fi!hydra!cc.helsinki.fi!jpiitulainen
From: jpiitulainen@cc.helsinki.fi
Newsgroups: comp.lang.misc
Subject: Re: On whether C has first-class composable functions
Message-ID: <1991Jan9.225355.4465@cc.helsinki.fi>
Date: 9 Jan 91 22:53:55 GMT
References: <442@data.UUCP> <4408:Jan421:44:3391@kramden.acf.nyu.edu> <20021@yunexus.YorkU.CA> <24547:Jan822:05:4191@kramden.acf.nyu.edu>
Organization: University of Helsinki
Lines: 61

(On first-class procedures and whether they need be named.)

Here's a recent reference, from David Gelernter and Suresh Jagannathan:
Programming Linguistics, 1990, The MIT Press (ISBN 0-262-07127-4).  The
context is Algol60 and call-by-name.  The colons mark quoted text, a
sequence of three periods marks omitted text.  I've included much
context because I think it is needed in order for the definition to
be understood the way they intended it.  Note that what follows the
definition below is to be thought of as being entailed by the
definition.

:  Definition 3.2 The first-class objects within language L are the ones
:  that can be yielded as values by expressions within L.

The authors proceed to ask what the definition entails, answering that
first-class objects can be passed as parameters to subroutines, returned
as values of functions and assigned to variables.  Then they ask what it
is like to have first-class procedures:

:  Consider a hypothetical language that includes first-class
:  procedures: it includes expressions E such that E yields a procedure.
:  ... E(z) is a legal invocation, in particular an invocation of
:  whatever procedure is specified by expression E. ... we should be
:  able to write f := E ... we should be able to write h(E) ... we
:  should be able to return E ... If A is an array, we should be able to
:  write ... A[1] := E.

Finally on the issue of not having a name---remember that the authors
are explaining call-by-name here.

:  ... We can think of a call-by-name application in terms of a
:  call-by-value application in which each of the actuals are unnamed
:  procedure objects.
:
:  It's interesting that Algol60 also allows procedures (more accurately
:  procedure names) to be passed explicitly and directly as actual
:  parameters.  (Procedures are not allowed to be returned as results of
:  an application, however; a procedure definition is considered to be a
:  declaration, not a value-yielding expression).  This is another
:  partial approach to the freedom implicit in first-class procedures.
:  It allows procedures as arguments, but requires that they be defined
:  and be given a name first; they can't be made up on the spot.  This
:  isn't quite the same as the invocation h(E), where E is improvised
:  for the occasion and not defined anywhere else, much as in h(3+4),
:  3+4 is an arithmetic expression that is improvised on the spot.

The last paragraph is the key here: Gelernter and Jagannathan expect E
to be like arithmetic expressions.

By the way, the authors also call, in footnote, the term "first-class"
"the residue of an inept metaphor":

:  First-class objects are said to be "first-class citizens" of the
:  language, assuming that a programming language can somehow be
:  compared to a state whose citizens are its data objects---which it
:  cannot, or at any rate just barely.

Well, I hope that I have not quoted more than is fair.  The book is
well worth a read or two.

Jussi Piitulainen