Supporting displaced vectors & arrays in Racket

Common Lisp has a nice feature for creating displaced arrays (or views, or slices, or ...) as exemplified in this interaction:

CL-USER 29 > (setq my-array (make-array '(2 2) :initial-contents '((a11 a12) (a13 a23))))
#2A((A11 A12) (A13 A23))

CL-USER 30 > (setq view-array (make-array '(1 2) :displaced-to my-array))
#2A((A11 A12))

CL-USER 31 > (setf (aref view-array 0 1) 'b12)
B12

CL-USER 32 > my-array
#2A((A11 B12) (A13 A23))

It doesn't seem Racket vectors have an analogous feature. I also don't know to build my own without rewriting most of the vector API. I read through the Racket Reference on the racket/generics module, the object system, and structure properties, but none of them are fit for introducing an abstraction over existing vectors.

Maybe a structure that wraps a vector and dereferences to it when passed to the vector API somehow? I don't want to involve macros but don't know how it would be done without them.

1 Like

It's a bit unusual, but you can achieve something like this with impersonate-vector:

$ racket
Welcome to Racket v8.11.1 [cs].
> (define (vector-view vec [start 0] [end (vector-length vec)])
    (impersonate-vector                                        
     (make-vector (- end start))
     (λ (placeholder pos zero)
       (vector-ref vec (+ start pos)))
     (λ (placeholder pos new)
       (vector-set! vec (+ start pos) new)
       0)))
> (define base           
    (vector 'a 'b 'c 'd))
> (define view             
    (vector-view base 1 3))
> view
'#(b c)
> (vector-set! view 0 'X)
> view
'#(X c)
> base
'#(a X c d)

An "impersonator" can interpose on certain operations—for vectors, vector-ref and vector-set!, with all other operations derived from those—and add arbitrary behavior. (Impersonators can only interpose arbitrarily where mutation is already allowed: immutable values/fields can only have chaperones, where interposition is limited to raising an exception or returning the value the base operation would have returned, possibly wrapped in a further chaperone.) The most prominent use of impersonators is to implement contracts, but impersonators are a lower-level and more general mechanism. For background on impersonators beyond The Racket Reference, I recommend “Chaperones and Impersonators: Run-time Support for Reasonable Interposition”.

In this example, the impersonator is wrapping a new placeholder vector that has the size of the “vector view”: the contents of the placeholder vector are completely unused. Instead, the interposition procedure for vector-ref accesses the target of the view. Likewise, the interposition procedure for vector-set! mutates the target vector: it returns 0 to be installed into the placeholder vector on the grounds that 0 is already there.

2 Likes

Jens Axel Søgaard implemented a great deal of SRFI 231, Intervals and Generalized Arrays, for Racket here:

(It says SRFI 179, but it contains many extensions from SRFI 231.) This has views, slices, shared arrays, etc., however you want to look at it:

https://srfi.schemers.org/srfi-231/srfi-231.html

3 Likes

For arrays, you might also consider math/array (and math/matrix if you want to do linear algebra to them), which supports views and lazy arrays.

1 Like