LISP - Fill Pointers in Arrays

Modern Lisp: Dynamic Arrays with Fill Pointers

In Common Lisp, arrays are typically fixed-size. However, many applications require a collection that can grow dynamically, like a C++ std::vector or a Python list. Lisp provides a highly efficient mechanism for this: adjustable arrays with fill pointers.

A fill pointer acts as a logical “end” marker for an array, allowing you to manage a smaller, active portion within a larger, pre-allocated memory block. This is a key technique for performance-critical tasks like parsing, I/O buffering, and building data collections without the overhead of list manipulation.

Core Concept: What is a Fill Pointer?

Imagine you have a bookshelf that can hold 100 books. This is the array’s total size or capacity. If you’ve only placed 5 books on it so far, you might put a bookmark after the 5th book. This bookmark is the fill pointer.

• The fill pointer is an integer that indicates how many elements of the array are currently “active” or in use.
• The active length of the array, as returned by the length function, is equal to its fill pointer, not its total allocated size.
• The fill pointer must always be less than or equal to the array’s total size.

Creating and Using Dynamic Arrays

1. Creating an Array with a Fill Pointer

To create a dynamic array, you use make-array with two key arguments: :adjustable t and :fill-pointer. Setting :fill-pointer to an integer initializes the active length to that value. Setting it to t initializes the fill pointer to the array’s total size.

;; Create a vector that can hold 10 elements, but is initially empty.
(defvar *dynamic-vector*
  (make-array 10 :adjustable t :fill-pointer 0))

;; Check its properties
(print (array-total-size *dynamic-vector*)) ;=> 10
(print (length *dynamic-vector*))           ;=> 0 (because fill-pointer is 0)

2. Idiomatic Usage: vector-push and vector-push-extend

While you can manually set the fill pointer, the idiomatic way to add elements to a dynamic array is with vector-push and vector-push-extend. These functions automatically manage the fill pointer for you.

• vector-push: Adds an element to the end of the vector if there is space. It increments the fill pointer and returns the new index.
• vector-push-extend: Does the same, but if the array is full, it automatically resizes it to make more room before adding the element. This makes the array truly dynamic.

;; Let's create a small, extensible vector
(defvar *buffer* (make-array 3 :adjustable t :fill-pointer 0))

;; Add some elements
(vector-push-extend 'a *buffer*) ;=> 0
(vector-push-extend 'b *buffer*) ;=> 1
(vector-push-extend 'c *buffer*) ;=> 2

(print *buffer*) ;=> #(A B C)
(print (length *buffer*)) ;=> 3

;; Now, add one more element. The array will automatically grow.
(vector-push-extend 'd *buffer*) ;=> 3

(print *buffer*) ;=> #(A B C D)
(print (length *buffer*)) ;=> 4
(print (array-total-size *buffer*)) ;=> (implementation-dependent, but > 3, e.g., 6)

3. Manual Fill Pointer Management

You can also read and write the fill pointer directly. This is useful for tasks like clearing a buffer without reallocating memory.

;; Let's use the buffer from the previous example: #(A B C D)
(print (fill-pointer *buffer*)) ;=> 4

;; Reset the buffer by setting the fill-pointer to 0.
;; The data is still there, but logically the array is empty.
(setf (fill-pointer *buffer*) 0)

(print (length *buffer*)) ;=> 0
(print *buffer*) ;=> #()

;; You can add new elements, which will overwrite the old ones.
(vector-push-extend 'x *buffer*)
(print *buffer*) ;=> #(X)

Practical Application: A Mini-Project

Let’s build a simple function that reads all lines from a string stream into a dynamic vector. This simulates reading a file line-by-line.

(defun read-lines-to-vector (text-stream)
  "Reads all lines from a stream into a dynamic vector."
  (let ((lines (make-array 10 :adjustable t :fill-pointer 0)))
    (loop for line = (read-line text-stream nil nil) ; Read one line
          while line ; Continue as long as a line was read
          do (vector-push-extend line lines))
    lines))

;; --- Test it ---
(let* ((sample-text "Hello Lisp\nModern Development\nEnd of File")
       (text-stream (make-string-input-stream sample-text))
       (result-vector (read-lines-to-vector text-stream)))

  (print result-vector))

;; --- Output ---
; #("Hello Lisp" "Modern Development" "End of File")

Best Practices and Common Pitfalls

• Prefer vector-push-extend: For most dynamic growth scenarios, vector-push-extend is the safest and most convenient choice.
• When to use fill pointers: Use them over lists when you need random access (aref) or when you’re working with a large number of elements and want to avoid the memory allocation overhead (consing) of lists.
• Common Error: Trying to set the fill pointer to a value greater than the array-total-size. This will signal an error.
• Performance Tip: When you know roughly how many elements you’ll need, initialize the array with a larger size to reduce the number of times it needs to be resized by vector-push-extend.