Array Notation

Aubrey Jaffer

Status

This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-58 @nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Abstract

SRFI-47 and its successor SRFI-63 provide both homogeneous numeric and heterogeneous multidimensional arrays which subsume Scheme vectors. The notation presented here builds upon Common-Lisp array syntax to represent heterogeneous arrays; and introduces a new Scheme-based notation for denoting homogeneous numeric arrays.

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.

• In Common Lisp, #n(v1 v2 ... vk) creates a vector of size N, with the final value, vk, repeated (N - K) times. It's an error if (K > N) or if (K = 0 and N > 0). Examples:
#5(1 2) ==> #(1 2 2 2 2)
#2(1 2) ==> #(1 2)
#0()    ==> #()
#1(1 2) ==> error: too many values
#5()    ==> error: no values for non-empty array

• PLT Scheme adds two extensions: If (K = 0), the vector is filled with 0, and if (K > N) the reader raises a specific exception.

The rank and dimension of the literal array can be specified several ways.

• the rank as a integer between # and A;
• the dimensions as integers joined with * after A; or
• the dimensions as integers joined with * after #.

Both rank and dimensions can be supplied on opposite sides of A.

Homogeneous Numeric Arrays

SRFI-63 introduces homogeneous arrays. This SRFI introduces denotations for homogeneous arrays following the rank and/or dimensions; and separated from them by a colon (:).

The names of the array-prototype-procedures of SRFI-63 and aliases for the array-prototype-procedures of SRFI-47 match these type denotations with A prepended. Having the array-prototype-procedure names match the array type denotations reduces the memory load for users.

All implementations must accept all the type denotations, but need not implement all the homogeneous array types. Those homogeneous types which an implementation doesn't support it stores in next best homogeneous array type, defaulting to heterogeneous arrays in the worst case. The rules for casting unsupported types are given in SRFI-63.

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. Vectors may substitute for lists at any nesting depth.

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

Rank 1 character arrays which are not subarrays are writen as Scheme strings; display treats rank 1 character arrays which are not subarrays identically with strings.

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

The prefix syntax is:

array-prefix :: rank `A' [ dimensions ] [ `:' type-specifier ] |
[ `A' ] dimensions [ `:' type-specifier ]

dimensions :: dimension | dimensions `*' dimension

dimension :: nonnegative-integer

rank :: nonnegative-integer

type-specifier :: `flo' { `C' | `R' } flowidth `b' |
`fix' { `Z' | `N' } fixwidth `b' |
`flo' `Q' decwidth `d'

flowidth :: `16' | `32' | `64' | `128'

fixwidth :: `8' | `16' | `32' | `64'

decwidth :: `32' | `64' | `128'

prototype
procedure
exactness element type type
specifier
vector any
A:floC128binexact128.bit binary flonum complexfloC128b
A:floC64b inexact64.bit binary flonum complex floC64b
A:floC32b inexact32.bit binary flonum complex floC32b
A:floC16b inexact16.bit binary flonum complex floC16b
A:floR128binexact128.bit binary flonum real floR128b
A:floR64b inexact64.bit binary flonum real floR64b
A:floR32b inexact32.bit binary flonum real floR32b
A:floR16b inexact16.bit binary flonum real floR16b
A:floQ128dexact128.bit decimal flonum rationalfloQ128d
A:floQ64d exact64.bit decimal flonum rational floQ64d
A:floQ32d exact32.bit decimal flonum rational floQ32d
A:fixZ64bexact64.bit binary fixnum fixZ64b
A:fixZ32bexact32.bit binary fixnum fixZ32b
A:fixZ16bexact16.bit binary fixnum fixZ16b
A:fixZ8b exact8.bit binary fixnum fixZ8b
A:fixN64bexact64.bit nonnegative binary fixnumfixN64b
A:fixN32bexact32.bit nonnegative binary fixnumfixN32b
A:fixN16bexact16.bit nonnegative binary fixnumfixN16b
A:fixN8b exact8.bit nonnegative binary fixnumfixN8b
A:bool boolean bool
string char char

A two-by-three array of nonnegative 16.bit integers can be written several ways:

#2A:fixN16b((0 1 2) (3 5 4))
#2A2*3:fixN16b((0 1 2) (3 5 4))
#A2*3:fixN16b((0 1 2) (3 5 4))
#2*3:fixN16b((0 1 2) (3 5 4))

Note that these are external representations of an array, not expressions evaluating to arrays. Like vector constants, array constants should be quoted:

'#2a:FIXN16b((0 1 2) (3 5 4))
==> #2A:fixN16b((0 1 2) (3 5 4))

Rank 0 arrays:

#0a sym
#0A:floR32b 237.0

Empty arrays:

#A0*2()
#A2*0(() ())
#A2*0*3(() ())
#A2*3*0((() () ()) (() () ()))

Semantics

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

An equivalent array could have been created by

(define ra (make-array (A:fixN16b) 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)
ra             ==> #2A:fixN32b((0 1 2) (3 5 4))

In this example, the uniform type returned is wider than requested due to implementation restrictions.

It is an error for the rank specified in array syntax to be different from the number of dimensions when they are explicitly given.

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-63, which supersedes SRFI-47, already defines these array-prototype-procedures.

;; flonums
(define A:floC128b ac64)
(define A:floC64b ac64)
(define A:floC32b ac32)
(define A:floC16b ac32)
(define A:floR128b ar64)
(define A:floR64b ar64)
(define A:floR32b ar32)
(define A:floR16b ar32)
;; decimal flonums
(define A:floQ128d ar64)
(define A:floQ64d ar64)
(define A:floQ32d ar32)
;; fixnums
(define A:fixZ64b as64)
(define A:fixZ32b as32)
(define A:fixZ16b as16)
(define A:fixZ8b  as8)
(define A:fixN64b au64)
(define A:fixN32b au32)
(define A:fixN16b au16)
(define A:fixN8b  au8)
(define A:bool    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).

;;; Read integer up to first non-digit
(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))
(else arg)))))

(define (bomb pc wid)
(error 'array 'syntax? (symbol-append "#" rank "A" pc wid)))
(case (char-downcase (peek-char port))
(let ((typ (let loop ((arg '()))
(if (= 4 (length arg))
(string->symbol (list->string (reverse arg)))
(and (not (eof-object? c))
(loop (cons (char-downcase c) arg))))))))
(define wid (and typ (not (eq? 'bool typ)) (read:try-number port)))
(define (check-suffix chrs)
(if (and (char? chr) (not (memv (char-downcase chr) chrs)))
(error 'array-type? (symbol-append ":" typ wid chr))))
(define prot (assq typ '((floC (128 . +64.0i)
(64  . +64.0i)
(32  . +32.0i)
(16  . +32.0i))
(floR (128 . 64.0)
(64  . 64.0)
(32  . 32.0)
(16  . 32.0))
(fixZ (64 . -64)
(32 . -32)
(16 . -16)
(8  . -8))
(fixN (64 . 64)
(32 . 32)
(16 . 16)
(8  . 8))
(char . #\a)
(bool . #t))))
(if prot (set! prot (cdr prot)))
(cond ((pair? prot)
(set! prot (assv wid (cdr prot)))
(if (pair? prot) (set! prot (cdr prot)))
(if wid (check-suffix (if (and (inexact? prot) (real? prot))
'(#\b #\d)
'(#\b)))))
(prot)
(else (check-suffix '())))
prot))
(else #f)))

;;; We come into read:array with number or #f for RANK.
(let loop ((dims dims))
(if dim
(loop (cons dim dims))
(case (peek-char port)
((#\:)
(list->uniform-array (or rank (length dims)) typ (read port))))
(else
(list->uniform-array (or rank (length dims)) #f (read port)))))))

(case c
((#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9)
(chr (peek-char port)))
(case chr
(else
(else (error "unknown # object" c))))