Lazy Evaluation Technical Specification

Source: src/hql/lib/stdlib/js/internal/seq-protocol.js, src/hql/lib/stdlib/js/core.js, src/hql/lib/stdlib/stdlib.hql

Grammar

lazy-seq  ::= '(' 'lazy-seq' body ')'
cons      ::= '(' 'cons' head tail ')'
seq       ::= '(' 'seq' coll ')'
delay     ::= '(' 'delay' expr ')'
force     ::= '(' 'force' delayed ')'
realized  ::= '(' 'realized' delayed ')'

Overview

HQL implements Clojure-inspired lazy sequences built on a Symbol-based protocol system. Lazy sequences defer computation until values are needed, enable infinite data structures, and provide memory-efficient processing of large collections.

The SEQ Protocol

The sequence protocol is defined using JavaScript Symbols:

SEQ     = Symbol.for("hql.seq")      // ISeq: first(), rest(), seq()
COUNTED = Symbol.for("hql.counted")  // Counted: count() in O(1)
INDEXED = Symbol.for("hql.indexed")  // Indexed: nth(i) in O(1)

Any object implementing the SEQ protocol can participate in HQL's sequence operations. The protocol requires three methods:

Core Types

EMPTY

Singleton empty sequence (like Clojure's PersistentList.EMPTY):

• Implements all three protocols (SEQ, COUNTED, INDEXED)
• first() returns undefined
• rest() returns itself
• seq() returns null
• count() returns 0
• Frozen (immutable)

Cons

Immutable pair of (first, rest):

(cons 1 (cons 2 (cons 3 null)))
;; => (1 2 3)

Time complexity:

• first(): O(1)
• rest(): O(1)
• seq(): O(1)
• Iteration: O(n) with O(1) stack via trampolining

;; Prepend to a sequence
(cons 0 [1 2 3])       ;; => (0 1 2 3)

;; Build a list
(cons 1 (cons 2 null)) ;; => (1 2)

LazySeq

Lazy sequence that defers computation until first access:

(lazy-seq
  (cons (compute-head)
        (lazy-seq (compute-rest))))

Properties:

• Memoized: Body thunk is evaluated at most once; result is cached
• Trampolined: Handles deeply nested lazy sequences without stack overflow
• Nil-punning: seq() returns null for empty lazy sequences

Time complexity:

• first(): O(1) amortized (first call evaluates thunk)
• rest(): O(1)
• seq(): O(1) amortized

ArraySeq

Efficient sequence view over a JavaScript array:

(seq [1 2 3])  ;; => ArraySeq wrapping [1, 2, 3]

Properties:

• Implements COUNTED and INDEXED protocols
• count(): O(1)
• nth(i): O(1)
• Zero-copy: shares the underlying array

ChunkedCons / ArrayChunk / ChunkBuffer

Chunked sequences for batch optimization:

• ArrayChunk: Fixed-size chunk of pre-computed values
• ChunkBuffer: Mutable buffer for building chunks (default capacity: 32)
• ChunkedCons: Cons cell with a chunk as first and a lazy seq as rest

Chunked processing amortizes the overhead of lazy thunk evaluation across multiple elements.

The seq Function

Converts collections to lazy sequences with nil-punning:

(seq [1 2 3])    ;; => ArraySeq
(seq "hello")    ;; => seq over characters
(seq #{1 2 3})   ;; => seq over Set values
(seq {a: 1})     ;; => seq over [key, value] entries
(seq [])         ;; => null (nil-punning)
(seq null)       ;; => null

Supported input types:

• Arrays -> ArraySeq
• Strings -> ArraySeq over characters
• Sets -> ArraySeq from Array.from(set)
• Maps -> ArraySeq from Array.from(map)
• Objects -> ArraySeq from Object.entries()
• SEQ protocol objects -> delegates to .seq()
• Iterators/Iterables -> lazy sequence via thunk chain
• null/undefined -> null

Delay / Force / Realized

delay

Wraps an expression in a deferred computation:

(let d (delay (expensive-computation)))
;; computation not yet executed

force

Forces evaluation of a delayed value:

(force d)  ;; => evaluates and caches the result
(force d)  ;; => returns cached result (no recomputation)

realized

Checks if a delay has been forced:

(let d (delay 42))
(realized d)  ;; => false
(force d)     ;; => 42
(realized d)  ;; => true

Non-delay values always return true for realized.

Lazy Constructors

range

Generates a lazy sequence of numbers:

(range)         ;; => 0, 1, 2, 3, ... (infinite)
(range 5)       ;; => 0, 1, 2, 3, 4
(range 2 8)     ;; => 2, 3, 4, 5, 6, 7
(range 0 10 2)  ;; => 0, 2, 4, 6, 8

repeat

Creates an infinite lazy sequence of a single value:

(take 3 (repeat "x"))  ;; => ("x" "x" "x")

cycle

Creates an infinite lazy sequence by cycling through a collection:

(take 7 (cycle [1 2 3]))  ;; => (1 2 3 1 2 3 1)

iterate

Creates an infinite lazy sequence by repeatedly applying a function:

(take 5 (iterate inc 0))        ;; => (0 1 2 3 4)
(take 5 (iterate (fn [x] (* x 2)) 1))  ;; => (1 2 4 8 16)

Sequence Operations (Lazy)

These operations return lazy sequences:

Sequence Operations (Eager)

These operations force evaluation:

Invariants

1. Nil-punning -- Empty sequences return null from seq(), enabling (if (seq coll) ...) idiom
2. Immutability -- Cons cells and lazy sequences are immutable once created
3. Memoization -- LazySeq thunks are evaluated at most once; the result is cached
4. Trampolining -- Deeply nested lazy sequences use trampolining to avoid stack overflow
5. O(1) primitives -- first, rest, seq are O(1) for all sequence types
6. Protocol dispatch -- Any object implementing the SEQ symbol protocol can participate in sequence operations

Edge Cases

Infinite Sequences

Infinite sequences must be consumed with take, takeWhile, or similar bounded operations:

;; CORRECT: bounded consumption
(take 10 (range))

;; DANGER: infinite loop
;; (reduce + (range))  -- never terminates

Empty Sequence Handling

(first [])    ;; => undefined
(rest [])     ;; => EMPTY (not null)
(seq [])      ;; => null
(count [])    ;; => 0

Lazy Side Effects

Side effects in lazy sequences are deferred:

;; Side effects happen only when the sequence is consumed
(let logged (map (fn [x] (print x) x) [1 2 3]))
;; Nothing printed yet
(reduce + 0 logged)  ;; Prints 1, 2, 3, returns 6

Implementation Location

• Seq protocol: src/hql/lib/stdlib/js/internal/seq-protocol.js
• Core operations: src/hql/lib/stdlib/js/core.js
• Self-hosted operations: src/hql/lib/stdlib/stdlib.hql
• Transducers: src/hql/lib/stdlib/js/transducers.js
• Tests: tests/unit/stdlib.test.ts, tests/unit/lazy-seq.test.ts