First class data types [summary]

Here are some messages that have arrived over the past few weeks on the
first class data types discussion in a dialogue between Ken Dickey and
Thomas Breuel. Now the topic is really truly closed, so send your
comments to the individual authors, please.


Regards,
John Levine, comp.compilers moderator


--------------------


Date: Wed, 11 Mar 92 17:00:32 PST
From: kend@data.rain.com (Ken Dickey)


In comp.compilers you write:


>Closures are a very powerful and useful language feature. But Scheme's
>terminology wrt. "first class functions" is unnecessarily "cutesy".
>Functions themselves are no more first class in Scheme than they are in C.


I disagree. While it is true that a Scheme function with no free
variables can be treated roughly equivalently to a C function pointer,
C has no unnamed funcions (i.e. no equivalent of LAMBDA).


A language in which all numbers have to be named before use still has
numbers. However, the second class status does become a pain very
shortly.


def two = 2
def three = 3
...
    return ( two + three ) /* can't do (2 + 3) -- have to use *names* */


Having to name each function before use is likewise painful if one is
unused to the restriction.


-Ken


--------------------


From: tmb@ai.mit.edu (Thomas M. Breuel)
Date: Thu, 12 Mar 92 06:36:13 EST


|>Closures are a very powerful and useful language feature. But Scheme's
|>terminology wrt. "first class functions" is unnecessarily "cutesy".
|>Functions themselves are no more first class in Scheme than they are in C.
|
|I disagree. While it is true that a Scheme function with no free
|variables can be treated roughly equivalently to a C function pointer,
|C has no unnamed funcions (i.e. no equivalent of LAMBDA).
|
|A language in which all numbers have to be named before use still has
|numbers. However, the second class status does become a pain very
|shortly.


I think you are missing the point. I'm objecting to your terminology,
not claims about functionality. I assume everybody knows what features
Scheme and C, respectively, provide.


A "function" to me corresponds to code, not to a closure; neither R4RS
Scheme nor ANSI C let you create new functions (new code) at runtime,
(although both languages have commonly available extensions providing
this capability). But only Scheme, not C, lets you create lexical
closures with unlimited extent.


Now, as to being "first class", to see how vague this notion is note
that the original article claimed that (I paraphrase) "C only has first
class pointers to functions but not first class functions". By the same
logic, I could argue that Scheme only has first class pointers to
lists but not first class lists (you cannot pass a list around as a
value, only a pointer to it); is that terribly meaningful?


On the other hand, you seem to think that having to name an object of
some type in order to define it deprives the type of first-class
status. Now, C does not have a constructor for structures; do you want
to argue that C structures are not first class? Whichever way you
answer, your notion of "first class" is either going to be pretty
useless for evaluating the expressive power of some datatype (lack of a
constructor for closures in C is a minor syntactical nuisance, not a
major problem) or inconsistent.


So, altogether, rather than saying that "Scheme has first-class
functions", I think it is better to stick with stating that Scheme has
"lexical closures with unlimited extent" and "anonymous functions"
while C doesn't. As opposed to "first-class functions", there is
widespread agreement and understanding outside the Scheme community
about what those terms mean.


Thomas.


--------------------


Date: Thu, 12 Mar 92 13:29:43 PST
From: kend@data.rain.com (Ken Dickey)


Thomas,


> I assume everybody knows what features Scheme and C, respectively, provide.


I do not generally find this to be the case.


> A "function" to me corresponds to code, not to a closure


Then "the value of a function applied to an argument" has no semantics
for you. I can see where this definition leads to trouble,
particularly when code cannot refer to locations of free variables (as
they are part of the environment). Do you consider the environment as
an additional (display) parameter? I find *your* definition of
"function" confusing--it certainly makes more sense to me to speak of
"function pointer" or "code address" where you say "function".


> I could argue that Scheme only has first class pointers to
> lists but not first class lists (you cannot pass a list around as a
> value, only a pointer to it)


While this may be true in terms of implementation, the Scheme language
refers only to data objects, not having the concept of a pointer. So
I would say that in Scheme you can only denote a value which is (in
your example) a list.


> you seem to think that having to name an object of
> some type in order to define it deprives the type of first-class
> status.


Where one data type can be created, used, etc. without having a name
and another cannot, that other *is* second class. This is what I
think.


> Now, C does not have a constructor for structures


You mean that malloc() and a cast no longer work?


> do you want to argue that C structures are not first class?


This depends on what you mean by structs. I can refer to memory
without having to name it. I can pass this reference around. I can
store a reference in a data structure. Pointers are certainly first
class in C. C's "datatypes" are so weak (without casting or using
pointers) that there is not much to be said about them.


> lack of a constructor for closures in C is a minor syntactical
> nuisance, not a major problem


Lack of closures, higher order functions, etc, is what makes C (IMHO)
a high-level assembler, not a high-level language. There is *no*
problem, but there is a major difference in what I do in C and what I
do in (e.g.) Scheme. C deals primarily with representation and
storage issues. Scheme deals primarily with abstract values (which
happen to have representations). These are major differences in focus
and I tend to use Scheme and C in very different areas.


> So, altogether, rather than saying that "Scheme has first-class
> functions", I think it is better to stick with stating that Scheme has
> "lexical closures with unlimited extent" and "anonymous functions"
> while C doesn't. As opposed to "first-class functions", there is
> widespread agreement and understanding outside the Scheme community
> about what those terms mean.


I have not found anyone who knows of "lexical closures" but not of
"first-class functions". I don't think that Denotational Semantics is
unknown outside of the Scheme community. It is certainly widely used
in language design & research. I would perhaps argue that it is
desirable to widen the education of many "programmers" to include more
of the literature on programming language theory. Blame Stoy et al.


-Ken




--------------------


From: tmb@ai.mit.edu (Thomas M. Breuel)
Date: Sun, 15 Mar 92 07:03:36 EST


I don't really want to continue this battle of words in public,
but there is one bad typo in my last message:


|> lack of a constructor for closures in C is a minor syntactical
                                                          ^^^^^^^^
|> nuisance, not a major problem
|
|Lack of closures, higher order functions, etc, is what makes C (IMHO)
|a high-level assembler, not a high-level language.


This should have been "lack of a constructor for structures in C
                                                                                                  ^^^^^^^^^^
is a minor syntactical nuisance, not a major problem".


Thomas.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.