5.3.1 · Память в виде векторов

Пары как адреса в векторах car и cdr

Ячейки пар фиксированной емкости лежат в двух векторах, ссылки становятся явными указателями, а порядок списков, мутация и общие хвосты видны прямо.

Вопрос для размышления

Как car, cdr, мутация и разделение структуры могут сохраняться, когда пара представляется целочисленным адресом, а не парой хоста?

Представление указателя на пару отдельно от атомарных данных
Выделение соответствующих слотов в параллельных векторах car и cdr
Реализация car, cdr, set-car! и set-cdr! через индексы указателей
Построение и декодирование конечного списка в векторной памяти
Наблюдение двух выделенных пар, разделяющих один представленный хвост
Явное отображение исчерпания емкости вместо предположения о бесконечной памяти

Объект памяти содержит два вектора одинаковой длины и один индекс free. Представленная пара имеет вид (ptr index). Процедуры memory-car и memory-cdr используют этот индекс в параллельных векторах, а операция выделения записывает оба поля и сдвигает free вперед. Процедура list->memory сначала строит хвост, поэтому корнем списка (a b c) становится последняя из трех выделенных ячеек, хотя декодирование восстанавливает исходный порядок.

Пример разделения структуры выделяет один хвост и сохраняет указатель на него в двух разных внешних ячейках. Изменение поля car в хвосте через этот единственный указатель изменяет оба декодированных списка. Это тот же вопрос о структуре графа, что и при разделении пар хоста, но идентичность теперь задается явным адресом. Фиксированная емкость векторов и монотонно возрастающий указатель free остаются явными ограничениями до тех пор, пока менеджер памяти не освободит или не скопирует живые ячейки.

Код SICP2,879 из 1,048,576 байт UTF-8

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

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Выделение памяти для списка возвращает (3 (ptr 2) (a b c) a b c (c b a) (() (ptr 0) (ptr 1))). Запуск с разделением структуры возвращает (3 (left changed) (right changed) #t 0).

На что обратить внимание в трассе

Проследите за указателем free и обратите внимание, что c, b и a занимают индексы 0, 1 и 2, так как построение хвоста завершается первым. В запуске с разделением структуры убедитесь, что два внешних слота cdr содержат одно и то же значение (ptr 0) и изменяется только один слот в векторе car.

Попробуйте сами

Измените программу и сравните результат.

Реализуйте деструктивную операцию append для векторной памяти, изменяющую только последний представленный слот cdr. Затем создайте цикл и напишите декодер с бюджетом посещений, который сообщает о повторно посещенных индексах указателей.

Показать подсказку

Последней ячейкой является указатель, чей представленный cdr является пустым списком. Безопасный при наличии циклов обход должен запоминать индексы указателей перед переходом по любому из полей.

Завершить этот урок

В этой главе пройдено 0 из 23 урока0%