Cons cell

Overview

In the ImpL imperative language, a cons cell is the fundamental two-field heap-allocated data structure from which linked lists and other pointer-based data structures are composed. Each cons cell has a head field and a tail field. Values held in these fields may be integers, the null reference nil, or pointers (ptr(r)) to other cons cells, which allows cons cells to be linked into nil-terminated or even cyclic lists (chunk 24a78dfe-f23e-4622-a271-5b5d41f78400; chunk 10f11341-f17f-440e-8eca-3070f887cf19).

Construction and access in ImpL

The grammar of ImpL provides three primitives that operate on cons cells (chunk 24a78dfe-f23e-4622-a271-5b5d41f78400):

• new cons(e1, e2) — allocate a fresh cons cell on the heap whose head and tail are initialized to the values of e1 and e2 respectively.
• e.head — read the head field of the cons cell referenced by e.
• e.tail — read the tail field of the cons cell referenced by e.

The corresponding assignment forms l.head := e and l.tail := e allow in-place updates of the two fields through left-hand-side paths.

Representation on the heap

A cons cell is represented on the heap as a mapping entry of the form r → cons(vh, vt), where r is a unique reference (the cell's address), vh is the value stored in the head field, and vt is the value stored in the tail field. Environments map program variables to either integers, nil, or ptr(r) references into the heap (chunk 10f11341-f17f-440e-8eca-3070f887cf19).

For example, executing the list program while (x.tail.head /= x.head) { x := x.tail }; x.tail := nil on the initial list [1,2,3,3,4] is represented on the heap as (chunk 10f11341-f17f-440e-8eca-3070f887cf19):

H : r₁ → cons(1, ptr(r₂))
    r₂ → cons(2, ptr(r₃))
    r₃ → cons(3, ptr(r₄))
    r₄ → cons(3, ptr(r₅))
    r₅ → cons(4, nil)

Operational semantics

The ImpL semantics uses cons cells as the unit of heap allocation and field access (chunk 10f11341-f17f-440e-8eca-3070f887cf19):

• (Cons) — evaluating new cons(e₁, e₂) evaluates e₁ and e₂, picks a fresh reference r, and returns ptr(r) while extending the heap with r → cons(v₁, v₂).
• (Head) / analogous (Tail) rule — evaluating e.head requires e to evaluate to a reference ptr(r) whose heap entry is of the form r → cons(vₕ, vₜ), after which the head (or tail) value vₕ (or vₜ) is returned.

The (Var) rule returns the value bound to a variable in the environment E, and (Nil) and (Int) rules model the nil pointer and integer literals (chunk 10f11341-f17f-440e-8eca-3070f887cf19).

Symbolic execution and test generation

Cons cells are the values that constraint-based test-input generation in ImpL must reason about symbolically. During symbolic execution, an unknown list value is represented by an unknown reference that points to a cons cell on a symbolically represented heap, and constraints over cons-cell contents are accumulated along an execution path (chunk 10f11341-f17f-440e-8eca-3070f887cf19).

Non-determinism in the search arises from the structure of cons cells themselves. For example, the program y := x.tail imposes the constraint (A → cons(Vₕ, Vₜ)) ∈ H₀, which admits infinitely many concrete test cases such as (chunk 3ad84e6a-8c5a-4f4a-a3c0-48ecb1d126c6):

E₀                              H₀
{x → ptr(a1), y → nil}         {a1 → cons(0, nil)}
{x → ptr(a1), y → nil}         {a1 → cons(0, a1)}
{x → ptr(a1), y → nil}         {a1 → cons(1, nil)}
{x → ptr(a1), y → ptr(a1)}     {a1 → cons(0, nil)}
{x → ptr(a1), y → nil}         {a1 → cons(0, ptr(a2)), a2 → cons(0, nil)}

Unknown reference values assigned to a cons-cell field are enumerated as (chunk 3ad84e6a-8c5a-4f4a-a3c0-48ecb1d126c6):

Vr = nil
  ∨ (∨_{r∈R} Vr = ptr(r))
  ∨ (Vr = ptr(r′) ∧ (r′ → cons(Vi′, Vr′)) ∈ H₀)

i.e., nil, any previously created reference, or a fresh reference whose cons cell carries fresh unknown head and tail values. Finite search strategies (e.g., depth-bounded search) are used in practice to enumerate solutions (chunk 3ad84e6a-8c5a-4f4a-a3c0-48ecb1d126c6).

Generalization to richer structures

ImpL's two-field cons cell is presented as the simplest case; the constraint-based approach generalizes to arbitrary struct-like data structures by adding new constructors with more fields (for example a binary tree tree(value, left, right)) and corresponding field selectors. The search process for unknown such values follows the same three-way pattern used for cons cells (chunk 3ad84e6a-8c5a-4f4a-a3c0-48ecb1d126c6).

Role in ImpL

The cons cell is the basic building block of ImpL's heap-allocated data structures. Its two fields give the language enough expressive power to model linked lists — including cyclic ones — and it serves as the template that the constraint-based test-generation machinery generalizes to richer record-like types.