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!.)

    Jeff (home page http://www.*-*-*.com/ )
--

    Jeff (home page http://www.*-*-*.com/ )



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))
        (else (error "bad boy!"))))

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)?

    Jeff (home page http://www.cdf.toronto.edu/DCS/Personal/Siskind.html)
--

    Jeff (home page http://www.cdf.toronto.edu/DCS/Personal/Siskind.html)



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!.)

       Jeff (home page http://www.cdf.toronto.edu/DCS/Personal/Siskind.html)
   --

       Jeff (home page http://www.cdf.toronto.edu/DCS/Personal/Siskind.html)

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/
Here is the README:
================================================================
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
badly explained.

[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  
 
 [ 12 post ] 

 Relevant Pages 

1. Pymacs - tuples/lists .vs. proper-lists/vectors

2. no vector = vector*vector in BLAS?

3. MIT scheme: string->list on long strings

4. question about symbol->string, string->list

5. String and list of strings concatenation

6. Convert string of words to list of strings

7. string->list->string

8. List of list to string and back

9. Convert String to Vector

10. Creating a vector of strings using read-char...???

11. converting vectors to strings

12. Vector syntax for a string?

 

 
Powered by phpBB® Forum Software