New version of FUNCTION-TYPE-REST-LIST-ELEMENT proposal

[sandra%orion@cs.utah.edu (Sandra J Loosemore)]

Issue:         FUNCTION-TYPE-REST-LIST-ELEMENT
References:    CLtL p. 27, 47-48, 61
               "Artifical Intelligence Programming", Charniak et. al.
               X3J13/86-003 (A:>GLS>clarifications.text.4)
Category:      CLARIFICATION, ADDITION
Edit history:  Version 1, 23-Nov-1987 Sandra Loosemore
	       Version 2, 15-Jan-1988 Sandra Loosemore
	           (incorporate comments from Scott Fahlman & others)
Related issues: FUNCTION-TYPE-KEY-NAME


Problem description:

The FUNCTION type specifier list is provided to allow declaration of
function argument types and return value types.  This type specifier uses a
syntax similar to the usual lambda list syntax to specify which types go
with which lambda list variables.  However, this is actually of limited
usefulness in the context of a declaration, where one normally wants type
information about the actual arguments which can be passed to the function
rather than the lambda variables to which they are bound.

There is a particular problem with &REST lambda variables, which are always
bound to a value of type LIST.  For the sake of consistency, it would seem
that the corresponding type given in the FUNCTION declaration must also be
LIST, but since this provides no information about the actual arguments,
some users/implementors have instead adopted the convention of supplying
the type of the actual arguments which are gathered into the list.  

CLtL is vague on the issue, mentioning only that &REST may appear in the
type specifier without touching upon its interpretation.


Proposal (FUNCTION-TYPE-REST-LIST-ELEMENT:USE-ACTUAL-ARGUMENT-TYPE):

Clarify that, in the FUNCTION type specifier, the type specifier provided
with &REST is the type of each actual argument, not the type of the 
corresponding lambda variable.


Test Case:

The type of the function + would be specified as:

(FUNCTION (&REST NUMBER) NUMBER)


Rationale:

This is more useful than specifying that the type of a &REST parameter must
be LIST, since it provides information about the actual arguments.


Current practice:

There does not appear to be any concensus on this issue.  Many Common Lisp
implementations currently ignore FUNCTION type declarations.


Cost to Implementors:

Implementations that ignore the FUNCTION type specifier may continue to do
so.  Probably only a small amount of code would have to be written/changed
in implementations that currently think that the type of the &REST parameter
must be LIST.


Cost to Users:

Users who have been using the convention that the &REST type parameter must
be LIST will have to change their code.  However, because this issue is so
unclear, the FUNCTION type specifier is probably not used very much.


Cost of non-adoption:

If nothing is done, the FUNCTION type specifier will continue to be of
limited use for its intended purpose.


Benefits:

Adopting the proposal will clear up an area of confusion in the language
design.


Esthetics:

Ugly.  Since the argument type syntax used by the FUNCTION type specifier
mirrors normal lambda-list syntax, it is confusing to make the &REST type
to refer to the types of the actual arguments rather than the type of the
matching lambda variable.  


Discussion:


Proposal (FUNCTION-TYPE-REST-LIST-ELEMENT:EXTEND-LIST-TYPE):

(1) Clarify that, in the FUNCTION type specifier, the type specifier provided
with &REST refers to the type of the corresponding lambda variable and must
be LIST or a subtype of LIST.

(2) Introduce a list form of the LIST type specifier, (LIST <type>).  If
the type is specified, then it indicates that the list is a true list
(that is, finite and null-terminated), and that the value of each
successive CAR of the list is a member of type <type>.


Test Case:

The type of the function + would be specified as:

(FUNCTION (&REST (LIST NUMBER)) NUMBER)


Rationale:

(1) It is clear that a &REST lambda variable must be bound to a list.
Since the FUNCTION type syntax follows lambda-list syntax rather than
function call syntax, it is more consistent to make the type correspond to
the type of the lambda variable rather than that of the actual arguments.

(2) Introducing a list LIST type specifier would allow the FUNCTION type
specifier to be more useful for its intended purpose.  It would also be
useful on its own.  For example, a compiler may be able to optimize
calls to functions such as MAPCAR that operate on successive elements of
a list if information is available about the type of items in the list.

The motivation for making this part of the standard is that the syntax
of the LIST type cannot cannot be extended by user code.  The motivation
for making (LIST <type>) specify a true list is that leaving the issue
unresolved would probably introduce more problems than it solves; see
also the discussion under "esthetics" below.


Current practice:

There does not appear to be any concensus on this issue.  Many Common Lisp
implementations currently ignore FUNCTION type declarations.


Cost to Implementors:

Implementations that ignore the FUNCTION type specifier may continue to
do so.  It should be a fairly straightforward to implement the list 
form of the LIST type specifiers.


Cost to Users:

Users who have been using the convention that the &REST type parameter
specifies the type of the actual arguments will have to change their code.
However, because this issue is so unclear, the FUNCTION type specifier is
probably not used very much.

Since there is no list form of the LIST type specifier defined now, adding
it should not affect user code.  The semantics of the non-list form remain
unchanged.

Cost of non-adoption:

If nothing is done, the FUNCTION type specifier will continue to be of
limited use for its intended purpose.


Benefits:

Adopting the proposal will clear up an area of confusion in the language
design.


Esthetics:

Since the argument type syntax used by the FUNCTION type specifier mirrors
normal lambda-list syntax, it would be cleaner and less confusing to provide
the type of the lambda variable rather than the type of the actual arguments.

On the issue of why (LIST <type>) should imply a true list, the notion
of a list of <type> implies a certain bias or asymmetry in the list
structure: the CARs of each cons contain an element of type <type> and
the CDRs contain a link to the next cons.  Moreover, in most
applications of the extended form of the LIST type specifier, one would
almost certainly want to use it to specify a true list.  (For example,
CLtL routinely uses the term ``list'' to mean ``true list'', and states
that it is an error to pass a dotted list to a function where the
corresponding argument is described as a list.)

If there is a need to specify the component types of lists being used as
trees, it would probably make more sense to define a list form of the
CONS type specifier that allows the types of both the CAR and CDR to be
supplied.


Discussion:

-------