5.3.1 · Memory as vectors

A pair can be an address into parallel car and cdr vectors.

Allocate fixed-capacity pair cells in two vectors, represent references as explicit pointers, and observe list order, mutation, and shared tails.

Guiding question

How can car, cdr, mutation, and sharing survive when a pair is represented by an integer address rather than a host pair?

Represent a pair pointer separately from an atomic datum
Allocate matching slots in parallel car and cdr vectors
Implement car, cdr, set-car!, and set-cdr! through pointer indexes
Construct and decode a finite list in vector memory
Observe two allocated pairs sharing one represented tail
Keep capacity exhaustion visible rather than assuming infinite memory

The memory object contains two equal-length vectors and one free index. A represented pair is (ptr index). memory-car and memory-cdr use that index in the parallel vectors; allocation writes both fields and advances free. list->memory builds the tail first, so the root of (a b c) is the last of three allocated cells even though decoding restores the source order.

The sharing example allocates one tail and stores its pointer in two different outer cells. Changing the tail car through that one pointer changes both decoded lists. This is the same graph question as host-pair sharing, but the identity is now an explicit address. The fixed vector capacity and monotonically advancing free pointer remain visible limitations until a storage manager reclaims or copies live cells.

SICP code2,879 of 1,048,576 UTF-8 bytes

(begin
  (define (tagged-list? value tag)
    (and (pair? value) (eq? (car value) tag)))
  (define (make-vector-memory capacity)
    (list '*vector-memory*
          (make-vector capacity '*unused*)
          (make-vector capacity '*unused*)
          (cons 'free 0)))
  (define (memory-cars memory) (list-ref memory 1))
  (define (memory-cdrs memory) (list-ref memory 2))
  (define (memory-free-cell memory) (list-ref memory 3))
  (define (memory-free memory) (cdr (memory-free-cell memory)))
  (define (set-memory-free! memory value)
    (set-cdr! (memory-free-cell memory) value))

  (define (pair-pointer? value) (tagged-list? value 'ptr))
  (define (make-pointer index) (list 'ptr index))
  (define (pointer-index pointer) (cadr pointer))

  (define (allocate-pair! memory car-value cdr-value)
    (let ((index (memory-free memory)))
      (if (>= index (vector-length (memory-cars memory)))
          (error "vector memory exhausted" index)
          (begin
            (vector-set! (memory-cars memory) index car-value)
            (vector-set! (memory-cdrs memory) index cdr-value)
            (set-memory-free! memory (+ index 1))
            (make-pointer index)))))
  (define (memory-car memory pointer)
    (vector-ref (memory-cars memory) (pointer-index pointer)))
  (define (memory-cdr memory pointer)
    (vector-ref (memory-cdrs memory) (pointer-index pointer)))
  (define (set-memory-car! memory pointer value)
    (vector-set! (memory-cars memory)
                 (pointer-index pointer)
                 value))
  (define (set-memory-cdr! memory pointer value)
    (vector-set! (memory-cdrs memory)
                 (pointer-index pointer)
                 value))

  (define (list->memory values memory)
    (if (null? values)
        '()
        (let ((tail (list->memory (cdr values) memory)))
          (allocate-pair! memory (car values) tail))))
  (define (memory->list pointer memory)
    (if (null? pointer)
        '()
        (cons (memory-car memory pointer)
              (memory->list (memory-cdr memory pointer)
                            memory))))
  (define (used-vector-prefix values count)
    (define (loop index result)
      (if (= index count)
          (reverse result)
          (loop (+ index 1)
                (cons (vector-ref values index) result))))
    (loop 0 '()))
  (define memory (make-vector-memory 8))
  (define root (list->memory '(a b c) memory))
  (list (memory-free memory)
        root
        (memory->list root memory)
        (memory-car memory root)
        (memory-car memory (memory-cdr memory root))
        (memory-car memory
                    (memory-cdr memory
                                (memory-cdr memory root)))
        (used-vector-prefix
          (memory-cars memory)
          (memory-free memory))
        (used-vector-prefix
          (memory-cdrs memory)
          (memory-free memory)))
)

(begin
  (define (tagged-list? value tag)
    (and (pair? value) (eq? (car value) tag)))
  (define (make-vector-memory capacity)
    (list '*vector-memory*
          (make-vector capacity '*unused*)
          (make-vector capacity '*unused*)
          (cons 'free 0)))
  (define (memory-cars memory) (list-ref memory 1))
  (define (memory-cdrs memory) (list-ref memory 2))
  (define (memory-free-cell memory) (list-ref memory 3))
  (define (memory-free memory) (cdr (memory-free-cell memory)))
  (define (set-memory-free! memory value)
    (set-cdr! (memory-free-cell memory) value))

(define (pair-pointer? value) (tagged-list? value 'ptr))
  (define (make-pointer index) (list 'ptr index))
  (define (pointer-index pointer) (cadr pointer))

(define (allocate-pair! memory car-value cdr-value)
    (let ((index (memory-free memory)))
      (if (>= index (vector-length (memory-cars memory)))
          (error "vector memory exhausted" index)
          (begin
            (vector-set! (memory-cars memory) index car-value)
            (vector-set! (memory-cdrs memory) index cdr-value)
            (set-memory-free! memory (+ index 1))
            (make-pointer index)))))
  (define (memory-car memory pointer)
    (vector-ref (memory-cars memory) (pointer-index pointer)))
  (define (memory-cdr memory pointer)
    (vector-ref (memory-cdrs memory) (pointer-index pointer)))
  (define (set-memory-car! memory pointer value)
    (vector-set! (memory-cars memory)
                 (pointer-index pointer)
                 value))
  (define (set-memory-cdr! memory pointer value)
    (vector-set! (memory-cdrs memory)
                 (pointer-index pointer)
                 value))

(define (list->memory values memory)
    (if (null? values)
        '()
        (let ((tail (list->memory (cdr values) memory)))
          (allocate-pair! memory (car values) tail))))
  (define (memory->list pointer memory)
    (if (null? pointer)
        '()
        (cons (memory-car memory pointer)
              (memory->list (memory-cdr memory pointer)
                            memory))))
  (define (used-vector-prefix values count)
    (define (loop index result)
      (if (= index count)
          (reverse result)
          (loop (+ index 1)
                (cons (vector-ref values index) result))))
    (loop 0 '()))
  (define memory (make-vector-memory 8))
  (define root (list->memory '(a b c) memory))
  (list (memory-free memory)
        root
        (memory->list root memory)
        (memory-car memory root)
        (memory-car memory (memory-cdr memory root))
        (memory-car memory
                    (memory-cdr memory
                                (memory-cdr memory root)))
        (used-vector-prefix
          (memory-cars memory)
          (memory-free memory))
        (used-vector-prefix
          (memory-cdrs memory)
          (memory-free memory)))
)

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The list allocation returns (3 (ptr 2) (a b c) a b c (c b a) (() (ptr 0) (ptr 1))). The sharing run returns (3 (left changed) (right changed) #t 0).

Trace focus

Follow the free pointer and note that c, b, and a occupy indexes 0, 1, and 2 because tail construction finishes first. In the sharing run, verify that the two outer cdr slots contain the same (ptr 0) value and that only one car-vector slot changes.

Try it yourself

Change the program and compare the result.

Implement a destructive vector-memory append that changes only the final represented cdr slot. Then create a cycle and write a decoder with a visit budget that reports revisited pointer indexes.

Show hint

The final cell is the pointer whose represented cdr is the empty list. A cycle-safe traversal must remember pointer indexes before following either field.

Complete this lesson

0 of 23 lessons complete in this chapter0%