Title

Array Notation

Authors

Aubrey Jaffer and Radey Shouman

Status

This SRFI is currently in ``draft'' status. To see an explanation of each status that a SRFI can hold, see here. It will remain in draft status until 2005/01/26, or as amended. To provide input on this SRFI, please mailto:srfi-58@srfi.schemers.org. See instructions here to subscribe to the list. You can access previous messages via the archive of the mailing list.

Received: 2004/11/26
Draft: 2004/11/26 - 2005/01/26

Abstract

SRFI-47 provides both uniform-typed and heterogeneous multidimensional arrays which subsume Scheme vectors. The notation presented here builds upon Common-Lisp array sytnax to represent heterogeneous and uniform-typed arrays.

Issues

Original Proposal
prototype procedure	exactness	element type	prefix (rank = n)
`vector`		any	`#nA`
`ac64`	inexact	IEEE 64.bit floating point complex	`#nAc64`
`ac32`	inexact	IEEE 32.bit floating point complex	`#nAc32`
`ar64`	inexact	IEEE 64.bit floating point real	`#nAr64`
`ar32`	inexact	IEEE 32.bit floating point real	`#nAr32`
`as64`	exact	64.bit integer	`#nAs64`
`as32`	exact	32.bit integer	`#nAs32`
`as16`	exact	16.bit integer	`#nAs16`
`as8`	exact	8.bit integer	`#nAs8`
`au64`	exact	64.bit nonnegative integer	`#nAu64`
`au32`	exact	32.bit nonnegative integer	`#nAu32`
`au16`	exact	16.bit nonnegative integer	`#nAu16`
`au8`	exact	8.bit nonnegative integer	`#nAu8`
`string`		char	`#nA\`
`at1`		boolean	`#nAt`

The original proposal allowed the "1" in the "#1A" prefix to be elided. That exception has been removed.
In discussions on the SRFI-58 mailing list, the abbreviations for the original uniform array types were criticized for being cryptic. Abbreviations for signed and unsigned were used, even though those terms are absent from R4RS and R5RS!
Type names from Scheme foreign-function and foreign-data interfaces were suggested; but these names are confusing or even misleading to those unfamiliar with C or Java.
The Scheme reports are amply descriptive using their succinct vocabulary; so I rewrote this SRFI to use only Scheme terminology. Several correspondents felt the resulting full names of the array types were too long:
```
  inexact-IEEE-64-bit-floating-point-complex-array
  inexact-IEEE-32-bit-floating-point-complex-array
  inexact-IEEE-64-bit-floating-point-real-array
  inexact-IEEE-32-bit-floating-point-real-array
  exact-64-bit-integer-array
  exact-32-bit-integer-array
  exact-16-bit-integer-array
  exact-8-bit-integer-array
  exact-64-bit-nonnegative-integer-array
  exact-32-bit-nonnegative-integer-array
  exact-16-bit-nonnegative-integer-array
  exact-8-bit-nonnegative-integer-array
  char-array
  boolean-array
  object-array
```
Per Bothner suggested that the Common-Lisp "#nA" prefix could be retained while eschewing further abbreviations by introducing ":" into the notation thus "#nA:typename".
The short typenames are those suggested by Taylor Campbell (with the un-Schemely "-U" and "-S" replaced by "+" and "-"). The results in Table-1 are compact, mnemonic, and do not reach outside of the Scheme language.
The use of SRFI-10 syntax for Arrays was discussed. The main arguments in favor of SRFI-10 were:

SRFI-10 is for Scheme extensions, and thus appropriate for SRFI-47 arrays if they are not incorporated into R6RS.

My efforts are directed toward making multidimensional arrays part of R6RS. Multidimensional arrays have been an integral part of computing since before electronic computers. A supposed general-purpose computer language without multidimensional arrays is an oxymoron.

Literal arrays would not be used often enough to warrant a "#" syntax.

Vector constants were thought useful enough that the "#(" syntax was appointed them. Many of the extant literal vectors (especially nested vectors) could be better expressed as arrays. Some literal nested lists would also be better suited to arrays. Bear@sonic.net gives some examples uses for literal arrays:
Data tables for character properties. color palettes. Graphic sprites. Coordinate transformation matrices. cellular automata substructures. Default Window coordinate lists. Map data. Integrated-circuit diagrams. Alias tables for character names. Parallel Records. Tuple aggregates. Multi-Character tokens for protocol drivers. Image data. Compiler transition tables. Tax rate tables. Icons. Lists of countries, states, counties, and municipalities. Bus routes. Airline schedules. Cellular coverage areas. And the list goes on... Programs need to be able to dump this information to file in S-expressions and read it back.

The proposed "#nA" syntax consumes too much of the precious "#" name-space.

The claim is that SRFI-58 would consume ten characters (the ten decimal digits), far more than the single "(" used for vectors.
But this accounting is disingenuous. It is highly unlikely that a one digit "#" code, say "#5" would be registered without including the other digits. If we consider "#" followed by digits to be a numeric argument to the character following, then only one letter, "A", worth of name-space has been allocated. "#nnn" followed by the letters B-Z and punctuation are all available.

A choice must be made between SRFI-10 syntax and "#nA" syntax. I felt the reasons in support of the "#nA" syntax given in the Rationale were more compelling.
Common Lisp has a compact notation for rank 1 boolean arrays: "#*" followed by a sequence of ones and zeros; "1" for "#t", "0" for "#f". Common-Lisp's bit-array accessor functions return "1" and "0"; but SRFI-47's "array-ref" returns "#t" or "#f". I don't think that difference invalidates this notation for Scheme, but others may.

Rationale

Vectors, which are rank 1 arrays, have a notation allowing them to be read and written by the procedures read and write. Vectors which are written, then read are EQUAL? to the originals.
A write-read invariant notation for other arrays would allow them to be easily saved and restored by programs.
A read notation for arrays would allow literal arrays to be coded directly in programs.
The syntax for heterogeneous array constants, "#nA" followed by the list-decomposition of the array, is the same as the Common-Lisp read-syntax for arrays.
Why Common-Lisp array syntax? Per Bothner answers:
- It's terse.
- It's stylistically consistent with vector notation:
  "#(a b c)" can be viewed as short-hand for "#1a(a b c)".
- It doesn't require me to write an extra noise keyword.
- It's prior art.

SRFI-47, "Array", incorporates all the uniform vector types from SFRI-4 "Homogeneous numeric vector datatypes", and adds a boolean array type and array types of complex numbers composed of two IEEE 32.bit or two IEEE 64.bit floating-point numbers. Multi-dimensional arrays subsume homogeneous vectors as the one-dimensional case, obviating the need for SRFI-4.

Implementations are required to accept all of the type denotations. Those which the platform supports will have platform-dependent representations; the others will be represented as the next larger uniform-type implemented; defaulting to vector if there are none.

Aliases for the array-prototype-procedures of SRFI-47 are defined whose identifiers are the #nA:typename prefix sans the #n. Having the array-prototype-procedure names match the array prefixes reduces the memory load for users.

This arrangement has platforms supporting uniform array types using them, with less capable platforms using vectors; both from the same source code.

Specification

Syntax

The syntax for arrays is a prefix according to the type and rank of the array followed by the list-decomposition of an array. The prefix must be immediately followed by a delimiter. Upper and lower case forms of a letter are not distinguished in the prefix characters.

By list-decomposition is meant rank nestings of lists of the elements where the most nested list has length equal to the last dimension of the array and at top level has length equal to the first dimension of the array.

Rank 0 arrays have one element; that element appears after the prefix (perhaps with intervening whitespace) with no additional parenthesis.

Rank 1 heterogeneous arrays which are not subarrays write and display as Scheme vectors.

prototype
procedure exactness element type prefix
(rank = n)
vector any #nA
A:complex-64 inexact IEEE 64.bit floating point complex #nA:complex-64
A:complex-32 inexact IEEE 32.bit floating point complex #nA:complex-32
A:real-64 inexact IEEE 64.bit floating point real #nA:real-64
A:real-32 inexact IEEE 32.bit floating point real #nA:real-32
A:integer-64 exact 64.bit integer #nA:integer-64
A:integer-32 exact 32.bit integer #nA:integer-32
A:integer-16 exact 16.bit integer #nA:integer-16
A:integer-8 exact 8.bit integer #nA:integer-8
A:integer+64 exact 64.bit nonnegative integer #nA:integer+64
A:integer+32 exact 32.bit nonnegative integer #nA:integer+32
A:integer+16 exact 16.bit nonnegative integer #nA:integer+16
A:integer+8 exact 8.bit nonnegative integer #nA:integer+8
A:boolean boolean #nA:boolean

A two-by-three array of nonnegative 16.bit integers is written:

#2A:integer+16((0 1 2) (3 5 4))

Note that this is the external representation of an array, not an expression evaluating to a array. Like vector constants, array constants must be quoted:

'#2a:INTEGER+16((0 1 2) (3 5 4))
               ==> #2A:integer+16((0 1 2) (3 5 4))

Rank 0 arrays:

#0a sym
#0A:real-32 237.0

Semantics

(array-dimensions '#2A:integer+16((0 1 2) (3 5 4))) ==> (2 3)

An equivalent array could have been created by

(define ra (make-array (A:integer+16) 2 3))
(array-set! ra 0 0 0)
(array-set! ra 1 0 1)
(array-set! ra 2 0 2)
(array-set! ra 3 1 0)
(array-set! ra 5 1 1)
(array-set! ra 4 1 2)

Literal array constants are immutable objects. It is an error to attempt to store a new value into a location that is denoted by an immutable object.

The following equivalences will be defined to alias SRFI-47 names to the new ones. SRFI-47 should be amended or replaced to make these be the array-prototype-procedures:

(define A:complex-64 ac64)
(define A:complex-32 ac32)
(define A:real-64    ar64)
(define A:real-32    ar32)
(define A:integer-64 as64)
(define A:integer-32 as32)
(define A:integer-16 as16)
(define A:integer-8  as8)
(define A:integer+64 au64)
(define A:integer+32 au32)
(define A:integer+16 au16)
(define A:integer+8  au8)
(define A:boolean    at1)

Implementation

The following code from the SCM implementation ("Init5d9.scm") implements array read-syntax. read:sharp is called from read when a #\# is read. Its first argument is the character after #\#; the second argument is the input port; the third argument is the procedure to call for recursive reading.

list->uniform-array converts the list-decomposition returned by read into the uniform array of the specified type (or the next larger compatible type).

(define (read:sharp c port read)
  (case c
    ((#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9)
     (let* ((num (read:try-number port c))
            (c (peek-char port)))
       (cond ((memv c '(#\a #\A))
              (read-char port)
              (read:array num port read))
             (else (error "syntax? #" num c)))))
    (else (error "unknown # object" c))))

(define (read:try-number port . ic)
  (define chr0 (char->integer #\0))
  (let loop ((arg (and (not (null? ic))
                       (- (char->integer (car ic)) chr0))))
    (let ((c (peek-char port)))
      (cond ((eof-object? c) #f)
            ((char-numeric? c)
             (loop (+ (* 10 (or arg 0))
                      (- (char->integer (read-char port)) chr0))))
            (else arg)))))

(define (read:array rank port reader)   ;ignore reader
  (define (bomb pc wid)
    (error (string-append "array syntax? #"
                          (number->string rank)
                          "A" (string pc)
                          (if wid (number->string wid) ""))))
  (list->uniform-array
   rank
   (case (char-downcase (peek-char port))
     ((#\:)
      (read-char port)
      (let ((typ (read port)))
        (case typ
          ((complex-64) +64.0i)
          ((complex-32) +32.0i)
          ((real-64)     64.0)
          ((real-32)     32.0)
          ((integer-64) -64)
          ((integer-32) -32)
          ((integer-16) -16)
          ((integer-8)   -8)
          ((integer+64)  64)
          ((integer+32)  32)
          ((integer+16)  16)
          ((integer+8)    8)
          ((boolean)     #t))))
     (else #f))
   (read port)))

Copyright

This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Scheme Request For Implementation process or editors, except as needed for the purpose of developing SRFIs in which case the procedures for copyrights defined in the SRFI process must be followed, or as required to translate it into languages other than English.

The limited permissions granted above are perpetual and will not be revoked by the authors or their successors or assigns.

This document and the information contained herein is provided on an "AS IS" basis and THE AUTHOR AND THE SRFI EDITORS DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Editor: David Van Horn

Last modified: Wed Jan 5 11:47:26 EST 2005