lists, strings, and vectors
Author Message
lists, strings, and vectors

R4RS has a clear attempt to provide symmetry between lists, strings, and
vectors.

LENGTH   STRING-LENGTH VECTOR-LENGTH
APPEND
REVERSE
LIST-REF STRING-REF    VECTOR-REF
STRING-SET!   VECTOR-SET!
STRING-FILL!  VECTOR-FILL!
STRING-COPY

But annoyingly,

1. a number of entries are missing from the above orthogonal table, and
2. LENGTH, APPEND, and REVERSE don't follow the naming convention (presumably
for historical reasons).

Can I suggest a remedy to this situation? I propose that a future RnRS provide
only the seven generic procedures LENGTH, APPEND, REVERSE, REF, REF!, FILL!,
and COPY and define these to work on lists, strings, and vectors.
(Unfortunately one can't genericize LIST/STRING/VECTOR-SET! to SET! as would
be desired for symetry, hence the creation of REF!.)

--

Tue, 04 Feb 1997 15:05:13 GMT
lists, strings, and vectors

Can I suggest a remedy to this situation? I propose that a future
RnRS provide only the seven generic procedures LENGTH, APPEND,
REVERSE, REF, REF!, FILL!, and COPY and define these to work on
lists, strings, and vectors.  (Unfortunately one can't genericize
LIST/STRING/VECTOR-SET! to SET! as would be desired for symetry,
hence the creation of REF!.)

I think you forgot "substring": subvector, sublist.

What should be the result type of append, reverse, copy etc?

You'd also have to generalize the conversion functions:
to
from    list            vector          string
list    -               list->vector list->string
vector  vector->list -               -
string  string->list -               -

See? There's no string->vector etc.

And: why do for-each and map only work on lists? They could work on
vectors and strings, too. E.g.:
(string-map char-upcase "hallo") => "HALLO"

I believe Common-Lisp allows those functions to operate on all kinds
of sequences. Is that the reason why Scheme doesn't?

I can see a few problems with these polymorphic functions:

- too much abstraction. REF on lists and the vector types has very
different complexity - O(1) on vectors, O(n) on lists. Programs may
need to make a vector copy of a list for efficiency.

- needs runtime type dispatch

But these could be interpreted as advantages when taking a more
object oriented view.  Or is this supposed to be the monomorphic
foundation? After all, Jeff could simply write his own REF:
(define (REF x n)
(cond ((vector? x) (vector-ref x n))
((string? x) (string-ref x n))
((list? x)   (list-ref x n))

Another vague posting by...
--

"If I have not seen as far as others, then that's |  Axel Wienberg
because giants were standing on my shoulders"    |  Hinzeweg 9
Hal Abelson               |  21075 Hamburg

Tue, 04 Feb 1997 22:40:58 GMT
lists, strings, and vectors

It seems to me that the reason for the asymmetry is that the types are
different from each other!  The whole reason both lists and vectors
exist is that some things are more expensive with one than with the
other.

Yes, but lists and vectors both conceptually have a length. That is why the
Scheme standard includes the procedures LENGTH and VECTOR-LENGTH. The only
difference between the two names is that the latter includes the type of the
argument in the name. Why shouldn't there be a generic procedure LENGTH that
takes arguments of all builtin Scheme types that can reasonably said to have a
length. Scheme already has generic procedures. For instance, it has +, <, and
WRITE. One doesn't write EXACT-INTEGER-+ vs. INEXACT-REAL-+ one simply writes
+. There are performance differences (and even semantic differences) between
EXACT-INTEGER-+ and INEXACT-REAL-+ yet we still genericize them because of the
conceptual similarity. Why shouldn't we genericize LENGTH (which has no
semantic differences) (and the other procedures under discussion)?

--

Fri, 07 Feb 1997 12:32:11 GMT
lists, strings, and vectors

Quote:
> conceptual similarity. Why shouldn't we genericize LENGTH (which has no
> semantic differences) (and the other procedures under discussion)?

I'd vote for a vector-map, vector-for-each, string-map, and
string-for-each as well, whether genericized under "map" and
"for-each" or not.  (Nobody tell me I can use vector->list then map
over it!).  A Scheme compiler can produce better code much more easily
for iteration over a vector or string using for-each than it can if I
use explicit indexing.

I'd like to see Scheme support this, and user-defined types (records,
structs, etc), and lots of other things that I know won't happen
anytime soon.  Even R5RS seems to have withered on the vine.

I guess I'll just wait for Dylan.

-- Robert

Sat, 08 Feb 1997 02:41:34 GMT
lists, strings, and vectors
Date: 19 Aug 94 07:05:13 GMT

Organization: /local/share/news/organization

R4RS has a clear attempt to provide symmetry between lists, strings, and
vectors.

LENGTH   STRING-LENGTH VECTOR-LENGTH
APPEND
REVERSE
LIST-REF STRING-REF    VECTOR-REF
STRING-SET!   VECTOR-SET!
STRING-FILL!  VECTOR-FILL!
STRING-COPY

But annoyingly,

1. a number of entries are missing from the above orthogonal table, and
2. LENGTH, APPEND, and REVERSE don't follow the naming convention (presumably
for historical reasons).

Can I suggest a remedy to this situation? I propose that a future RnRS provide
only the seven generic procedures LENGTH, APPEND, REVERSE, REF, REF!, FILL!,
and COPY and define these to work on lists, strings, and vectors.
(Unfortunately one can't genericize LIST/STRING/VECTOR-SET! to SET! as would
be desired for symetry, hence the creation of REF!.)

--

A similar proposal was made at one of the Scheme authors meetings.
Based on that proposal, I drafted a set of formal changes for
inclusion in the next RnRS report.  These changes were later voted
down by the RnRS authors.  For a complete recap of the arguements for
and against, please see the RRRS-authors mailing list archives which
include a report from the RnRS meetings at which these changes were
discussed.
--------------------
Morry Katz

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

Sat, 08 Feb 1997 07:53:09 GMT
lists, strings, and vectors
| For a complete recap of the arguements for
| and against, please see the RRRS-authors mailing list archives which
| include a report from the RnRS meetings at which these changes were
| discussed.

Can you tell me where to find that?  Thanks in advance.

-- Scott

Sat, 08 Feb 1997 11:53:32 GMT
lists, strings, and vectors
Date: 22 Aug 94 04:32:11 GMT

Organization: /local/share/news/organization

It seems to me that the reason for the asymmetry is that the types are
different from each other!  The whole reason both lists and vectors
exist is that some things are more expensive with one than with the
other.

Yes, but lists and vectors both conceptually have a length. That is
why the Scheme standard includes the procedures LENGTH and
VECTOR-LENGTH. The only difference between the two names is that
the latter includes the type of the argument in the name. Why
shouldn't there be a generic procedure LENGTH that takes arguments
of all builtin Scheme types that can reasonably said to have a
length. Scheme already has generic procedures. For instance, it has
+, <, and WRITE. One doesn't write EXACT-INTEGER-+ vs.
INEXACT-REAL-+ one simply writes +. There are performance
differences (and even semantic differences) between EXACT-INTEGER-+
and INEXACT-REAL-+ yet we still genericize them because of the
conceptual similarity. Why shouldn't we genericize LENGTH (which
has no semantic differences) (and the other procedures under
discussion)?

Just quickly, one argument given at the RnRS meeting for not going to
the generic operator form is that performance can be much poorer for
some of the generic operators because of an inability at compile time
to select the correct varient of the operator.  It was pointed out
that this is particularly costly when the operator could be inlined
and further optimized when the variant is specified by the programmer,
but not when used as a generic.  Of course, we all know that a good
compiler can often discern the correct form of the operator at compile
time, that there are runtime mechanisms for overcoming some of the
costs of generic operators, etc.; but, there remained a concern
amongst a siginificant numbre of authors that the costs would be
excessive particularly for fairly simple, light-weight implementations
of scheme.  As a futher argument, they stated that the generic
operators could always be built upon the primitives already given in
the languages, but not visa versa.

For more details, please see the archives.
------------------------------------------------------
Morry Katz
Rockwell Science Center

(415)723-9427 (office)
(415)694-9121 (beeper)
------------------------------------------------------

Sun, 09 Feb 1997 00:46:25 GMT
lists, strings, and vectors
Just quickly, one argument given at the RnRS meeting for not going to
the generic operator form is that performance can be much poorer for
some of the generic operators because of an inability at compile time
to select the correct varient of the operator.  ...
...  As a futher argument, they stated that the generic
operators could always be built upon the primitives already given in
the languages, but not visa versa.

Whilst I don't have any problem with this argument, I do find it
anomalous given that generic mathematical operators are in the
language.  Was there some reason given for allowing generic arithmetic
but not generic sequences?

... For more details, please see the archives.

Which are stored where?

Sun, 09 Feb 1997 16:28:14 GMT
lists, strings, and vectors

... For more details, please see the archives.

Which are stored where?

altdorf.ai.mit.edu:archive/scheme-mail/
================================================================
This directory contains archives of the Scheme mailing lists.  The
archives are compressed files of mail messages.  Most of the mail
messages are in unix mail format, except the early issues of "scheme"
which are in ITS mail format, and the early issues of "rrrs-authors"
which are in Babyl format.

Messages sent to the "scheme" mailing list:

scheme.mail01.Z  20-OCT-85  11-JUL-86
scheme.mail02.Z  11-JUL-86  22-SEP-87
scheme.mail03.Z  24-SEP-87  15-JAN-88
scheme.mail04.Z  19-JAN-88  26-MAY-88
scheme.mail05.Z  26-MAY-88  16-NOV-88
scheme.mail06.Z  16-NOV-88  21-APR-89
scheme.mail07.Z   8-AUG-89  26-JUN-90
scheme.mail08.Z  27-JUN-90  18-MAR-91
scheme.mail09.Z  19-MAR-91  22-APR-91
scheme.mail10.Z  24-APR-91   1-JUN-91
scheme.mail11.Z   2-JUN-91  22-JUL-91
scheme.mail12.Z  23-JUL-91   3-DEC-91
scheme.mail13.Z   4-DEC-91  29-DEC-91
scheme.mail14.Z   1-JAN-92  31-MAR-92
scheme.mail15.Z   1-APR-92  30-JUN-92
scheme.mail16.Z   1-JUL-92  31-JUL-92
scheme.mail17.Z   1-AUG-92  17-SEP-92
scheme.mail18.Z  17-SEP-92  18-MAR-93

Messages sent to the "rrrs-authors" mailing list:

rrrs.mail01.Z  24-SEP-84  12-MAR-85
rrrs.mail02.Z  14-MAR-85  23-APR-85
rrrs.mail03.Z  24-APR-85  17-SEP-85
rrrs.mail04.Z   7-NOV-85  19-MAR-86
rrrs.mail05.Z  19-MAR-86   7-APR-86
rrrs.mail06.Z  17-APR-86  11-JUL-86
rrrs.mail07.Z  12-JUL-86   5-FEB-87
rrrs.mail08.Z  10-MAR-87  27-APR-87
rrrs.mail09.Z  18-MAY-87   6-JAN-88
rrrs.mail10.Z  23-JAN-88  28-MAR-88
rrrs.mail11.Z   6-APR-88  11-JUL-88
rrrs.mail12.Z  13-JUL-88   9-FEB-89
rrrs.mail13.Z  18-FEB-89   8-JUN-89
rrrs.mail14.Z   6-AUG-89  30-APR-90
rrrs.mail15.Z  13-JUL-90  19-DEC-91
rrrs.mail16.Z  13-FEB-92  31-MAY-92
rrrs.mail17.Z  31-MAY-92  18-MAR-93
rrrs.mail18.Z  19-MAR-93  10-JUL-94

Messages sent to the "scheme-standard" mailing list:

standard.mail01.Z  13-OCT-88   3-APR-90

Mon, 10 Feb 1997 10:05:51 GMT
lists, strings, and vectors
Date: 24 Aug 1994 08:28:14 GMT

...
Whilst I don't have any problem with this argument, I do find it
anomalous given that generic mathematical operators are in the
language.  Was there some reason given for allowing generic arithmetic
but not generic sequences?

What Lisp has traditionally called "generic arithmetic" really
shouldn't be confused with the modern CLOS/Dylan/this-week's-hot-
new-language usage of the word "generic" [1].

Look at it this way: Scheme really has only one numeric type: the type
`number'.  Sure, there are predicates that test -attributes- of numbers,
such as `rational?', `integer?', `positive?' and `odd?', but those
predicates do not correspond to "types" in any ordinary programming
language sense of the word [2].  You don't have to use a special version of
`+' to add numbers that satisfy the predicate `integer?', just as you don't
have to use a special version of `+' to add numbers that satisfy the
predicate `odd?'.

If you peek behind the curtain at the way a Scheme implementation typically
-implements- the type `number', you may find a patchwork of representations
(traditionally "fixnums", "flonums", "bignums", "ratnums", etc.) stitched
together using a operator dispatch mechanism that looks like a generic
procedure dispatch.  But that's just an implementation technique, it is
completely hidden from the user.

There is really -nothing- in Scheme that could properly be called "generic"
except perhaps for `write', `display' and `equal?' [3].

-- Footnotes

[1] I used to have a piece of electronic mail somewhere from Dave Moon
where he explains the historical origins of this confusion -- but I can't
seem to locate it at the moment.

[2] Actually, R4RS does use the word "type" to refer to some of these
subsets of the numbers -- but R4RS is full of places where the numbers are

[3] In R5RS, add `eval' to this list.

Mon, 10 Feb 1997 16:31:26 GMT
lists, strings, and vectors
Date: 24 Aug 1994 08:28:14 GMT

Organization: Department of Computer Science; University of Manchester

Just quickly, one argument given at the RnRS meeting for not going to
the generic operator form is that performance can be much poorer for
some of the generic operators because of an inability at compile time
to select the correct varient of the operator.  ...
...  As a futher argument, they stated that the generic
operators could always be built upon the primitives already given in
the languages, but not visa versa.

Whilst I don't have any problem with this argument, I do find it
anomalous given that generic mathematical operators are in the
language.  Was there some reason given for allowing generic arithmetic
but not generic sequences?

I do not remember the entire discussion (it was almost 2 years ago).

... For more details, please see the archives.

Which are stored where?

I do not know the current location.  I am sure that the FAQ for
comp.lang.scheme gives this info.  They userd to be on
zurich.ai.mit.edu many years ago, but that may have changed.
--------------------
Morry Katz

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

Tue, 11 Feb 1997 02:33:35 GMT
lists, strings, and vectors
Date: 24 Aug 1994 08:28:14 GMT

...
Whilst I don't have any problem with this argument, I do find it
anomalous given that generic mathematical operators are in the
language.  Was there some reason given for allowing generic arithmetic
but not generic sequences?

What Lisp has traditionally called "generic arithmetic" really
shouldn't be confused with the modern CLOS/Dylan/this-week's-hot-
new-language usage of the word "generic" [1].

[ rest deleted ]

All of which clearly shows that I had an incorrect view of Scheme numerics,
and hence my question was nonsensical.  I've since found that the
issue of a "generic" length ... etc. has been discussed off and on for
almost 10 years on the rrrs-authors mailing list so I plan to study
the arguments there before (and probably instead of :-) wading in with
any more of my own.

Any chance of adding the location of the rrrs archives to the FAQ?

Tue, 11 Feb 1997 15:21:29 GMT

 Page 1 of 1 [ 12 post ]

Relevant Pages