Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!spool.mu.edu!sdd.hp.com!elroy.jpl.nasa.gov!ncar!noao!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: On whether C has first-class composable functions
Message-ID: <501@coatimundi.cs.arizona.edu>
Date: 9 Feb 91 20:46:17 GMT
Sender: news@cs.arizona.edu
Lines: 64

In article  <6828:Feb906:14:3491@kramden.acf.nyu.edu> Dan Bernstein writes:
]
]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.

One of the reasons people are unwilling to provide such a definition
is that "has" is intended to be something of a subjective judgement.
Even so, I think using "has" to mean "can implement" is peculiar.  I
can't say it's wrong since the term is subjective, but it is at an
extreme end of the scale of meanings people apply to the term.

Another problem with giving a definition of "L has semantic feature X"
is that we first have to know what a "semantic feature" is.  Until
that term is well-defined the term "has" must remain a bit flexible.

Having said that, here is a posible definition for the term, punting
on the issue of what a "semantic feature" is.

Definition of ``L has X'' for a language L and a semantic feature X:

View L as a many-sorted algebra where the operations consist of all
the primitive operations of the language and the sorts consist of all
the types acted on by built-in operations.  I include standard
libraries as part of the standard language.  A language "has" a type
if that type is one of the sorts of the algebra.  A language "has" an
operation if that operation is in the algebra.

Then C "has":
(1) ints and floats -- obvious
(2) pointers to every type -- because C has built-in operations on
pointers.  This is the reason I defined sorts based on operations --
it doesn't matter that syntactically (int *) is a non-atomic type, the
type is supported by built-in operations in the language, so it is
part of the language.
(3) strings -- string literals are 0-ary operations
(4) string concatenation -- the library function strcat()
(5) function construction -- just define the function
(6) first-class functions -- because function pointers are first-class
objects and function pointers (C terminology) are actually functions
(general terminology).  The reason I say that C function pointers are
functions is because there is a built-in apply operation on them.  The
statement "C functions are first-class" on the other hand is not true
because the phrase "C function" seems to require C terminology.

C does not have composable functions because there is no operation
in the algebra that composes functions.  When you implement such
things in C, you have created a new language, an extension of C that
has composable functions.  But standard C does not have them.

One problem with this definition is that C requires declarations, and
you can say that the code implementing composable functions is just an
extended declaration.  In the case of C, there is a difference between
a "declaration" and a "definition", so I'm tempted to say that
declarations are permitted in the language that defines the algebra
but that definitions are not.  But I'm not sure that this works for
all languages.

Practically, however, I would say that there is an obvious difference
between a declaration like "#include <string.h>" or "int *ip" and a
declaration that takes 300 lines of code.
--
					David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudeman