Cons cell

Concept

A cons cell is a two-field heap-allocated data structure used in the ImpL imperative language to build linked lists and other pointer-based structures; it has a head field and a tail field, and is created and accessed by the new cons, head, and tail operations within ImpL programs.

First seen 7/11/2026

Last seen 7/11/2026

Evidence 3 chunks

Wiki v1

WIKI

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

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

2 connections

heap-allocated data structures part of → 90% 2e

Heap-allocated data structures in ImpL are composed of cons cells.

ImpL imperative language part of → 90% 1e

ImpL includes cons cells as data structure elements.

LINKED ENTITIES

2 links

ImpL imperative language PART_OF Extracted graph relationship

heap-allocated data structures PART_OF Extracted graph relationship

CITATIONS

7 sources

7 citations — click to expand

[1] In the ImpL language, cons cells are two-field heap-allocated data structures with head and tail fields used to build linked lists. Generating Test Inputs for a Small Imperative Language Using Constraint Programming

[2] ImpL provides the expressions new cons(e1, e2), e.head, and e.tail to allocate and access cons cells, and l.head / l.tail left-hand sides to update them. Generating Test Inputs for a Small Imperative Language Using Constraint Programming

[3] A heap is a finite mapping from references r to cons cells of the form cons(vh, vt); environments map variables to integers, nil, or ptr(r) references into the heap. Generating Test Inputs for a Small Imperative Language Using Constraint Programming

[4] The ImpL operational semantics rules (Cons) and (Head) show that new cons(e1, e2) allocates a fresh reference r and adds r → cons(v1, v2) to the heap, while e.head returns the head value of the cons cell referenced by e. Generating Test Inputs for a Small Imperative Language Using Constraint Programming

[5] A single execution path over cons cells, such as y := x.tail, yields infinitely many concrete test cases because the heap entry (A → cons(Vh, Vt)) ∈ H0 is under-constrained. Generating Test Inputs for a Small Imperative Language Using Constraint Programming

[6] Unknown reference values filling a cons-cell field are assigned either nil, an existing reference, or a fresh reference whose cons cell carries fresh unknown head and tail values; in practice a finite search strategy enumerates solutions. Generating Test Inputs for a Small Imperative Language Using Constraint Programming

[7] The constraint-based test-generation approach extends beyond simple two-field cons cells to arbitrary struct-like data structures (e.g., binary trees) by adding new constructors and corresponding field selectors. Generating Test Inputs for a Small Imperative Language Using Constraint Programming