LISP - Adjustable Arrays

Lisp - Adjustable Arrays and Fill Pointers

Standard Lisp arrays have a fixed size. However, many real-world problems require a collection that can grow or shrink as the program runs. For this, Common Lisp provides adjustable arrays and fill pointers, a powerful combination for creating dynamic collections like stacks or buffers.

Key Concepts

• Adjustable Array: An array created with the :adjustable t flag. Its underlying memory allocation can be resized using the adjust-array function. Resizing can be an expensive operation, as it may involve allocating new memory and copying all existing elements.
• Fill Pointer: A special index associated with a vector that tracks the number of active elements. Think of it as a bookmark indicating how much of the array is currently in use. The capacity of the array can be larger than the number of active elements. This allows you to add new elements efficiently without immediately resizing the array, as long as there is spare capacity.

Creating an Adjustable Vector

To create a dynamic vector, you must specify both :adjustable and :fill-pointer when calling make-array.

(make-array <initial-capacity>
            :adjustable t
            :fill-pointer 0) ; Or `t` which defaults to 0

Here, <initial-capacity> is the physical size allocated, and the fill pointer is set to 0, indicating the vector is initially empty.

Example: Manual Manipulation

;; Create a dynamic vector with a capacity of 8, but initially empty.
(defparameter *dynamic-vec* (make-array 8 :adjustable t :fill-pointer 0))

(format t "Initial Vector: ~a~%" *dynamic-vec*)
(format t "Initial Fill Pointer: ~a~%" (fill-pointer *dynamic-vec*))
(format t "Initial Capacity (Total Size): ~a~%~%" (array-total-size *dynamic-vec*))

;; Add an element manually. This requires two steps:
;; 1. Place the element at the fill-pointer index.
(setf (aref *dynamic-vec* (fill-pointer *dynamic-vec*)) 'A)
;; 2. Increment the fill-pointer.
(incf (fill-pointer *dynamic-vec*))

(setf (aref *dynamic-vec* (fill-pointer *dynamic-vec*)) 'B)
(incf (fill-pointer *dynamic-vec*))

(format t "Vector after adding elements: ~a~%" *dynamic-vec*)
(format t "New Fill Pointer: ~a~%" (fill-pointer *dynamic-vec*))

Output

Initial Vector: #()
Initial Fill Pointer: 0
Initial Capacity (Total Size): 8

Vector after adding elements: #(A B)
New Fill Pointer: 2

The Modern Approach: vector-push-extend

Manually managing the fill pointer is tedious and error-prone. The modern and idiomatic way to add elements to a dynamic vector is with vector-push-extend. This function automatically handles adding the element, incrementing the fill pointer, and even resizing the array if it runs out of capacity.

Example: Dynamic Growth with vector-push-extend

This example starts with a small vector and adds more elements than its initial capacity. vector-push-extend will automatically double the array size when needed.

;; Start with a small capacity of 4.
(defparameter *buffer* (make-array 4 :adjustable t :fill-pointer 0))

(format t "Initial capacity: ~a~%" (array-total-size *buffer*))

;; Add 10 items to the buffer.
(loop for i from 1 to 10
      do (vector-push-extend i *buffer*)
      (format t "Added ~a. Current buffer: ~a. Current capacity: ~a~%"
              i *buffer* (array-total-size *buffer*)))

Output

Initial capacity: 4
Added 1. Current buffer: #(1). Current capacity: 4
Added 2. Current buffer: #(1 2). Current capacity: 4
Added 3. Current buffer: #(1 2 3). Current capacity: 4
Added 4. Current buffer: #(1 2 3 4). Current capacity: 4
Added 5. Current buffer: #(1 2 3 4 5). Current capacity: 8
Added 6. Current buffer: #(1 2 3 4 5 6). Current capacity: 8
Added 7. Current buffer: #(1 2 3 4 5 6 7). Current capacity: 8
Added 8. Current buffer: #(1 2 3 4 5 6 7 8). Current capacity: 8
Added 9. Current buffer: #(1 2 3 4 5 6 7 8 9). Current capacity: 16
Added 10. Current buffer: #(1 2 3 4 5 6 7 8 9 10). Current capacity: 16

Other Useful Functions

• vector-push: Like vector-push-extend, but it only adds the element if there is space. It returns the index where the element was placed, or nil if the vector is full.
• vector-pop: Removes and returns the last active element by decrementing the fill pointer. An error is signaled if the vector is empty.

When to Use Adjustable Arrays

Adjustable arrays with fill pointers are the go-to data structure when:

• You need an ordered collection whose final size is unknown at compile time.
• You need to implement a stack data structure (vector-push-extend is push, vector-pop is pop).
• You are reading data from a stream or file and need a buffer that can grow dynamically.
• Performance matters. While resizing can be slow, the strategy of doubling the capacity ensures that adding an element is, on average (amortized), a very fast operation.