Blog › ICP guides

SASL developer on retainer: lazy evaluation, self-referential stream definitions, strict equality non-termination, and combinatory reduction on monthly retainer

September 30, 2026 · ~15 min read

A SASL developer was implementing a lazy functional evaluation engine for a programming languages research project, working with SASL — the St Andrews Static Language — one of the first purely functional languages with lazy evaluation, designed by David Turner at the University of St Andrews in 1972. The developer defined an infinite list of Fibonacci numbers using SASL’s self-referential definition: def fibs = 0 : 1 : zipWith (+) fibs (tl fibs). The supporting zipWith function applied a binary operator element-by-element across two lists: def zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys. Both definitions worked correctly under SASL’s lazy evaluation — hd fibs returned 0 immediately, hd (tl fibs) returned 1 immediately, and hd (tl (tl fibs)) returned 1 as expected. The developer then wrote a length-counting function to verify stream segments: def myLength xs = if xs = [] then 0 else 1 + myLength (tl xs). Calling myLength (take 10 fibs) caused non-termination: SASL’s = operator performs structural equality, forcing evaluation of the entire spine of its left argument to compare it with []. Even a finite list returned by take 10 fibs has a lazy tail thunk at each cons cell; xs = [] forced evaluation of that entire thunk chain, which re-entered zipWith applied to fibs, which re-entered the infinite self-referential definition. Non-termination: every call. The SASL developer on retainer identified the culprit as the = equality check against [] and replaced it with the null predicate: def myLength xs = if null xs then 0 else 1 + myLength (tl xs). The null predicate inspects only the outermost constructor of xs, requiring O(1) work regardless of the structure of the tail. Non-termination rate: 1/call → 0.

The work log entry read “replaced = [] equality check with null predicate in length function, 6h.” It names the result and the duration. It cannot explain why = causes non-termination in lazy functional languages: = on lists is structural equality; to determine whether two lists are equal, both spines must be evaluated until both reach a constructor that can be compared; xs = [] evaluates xs’s full spine by forcing every tail thunk in the chain until either a [] (empty list) or a discrepancy is found; if xs contains any lazy thunk that evaluates to a non-empty list (even transitively), = forces that thunk; in the Fibonacci case, take 10 fibs returns a finite list at the top level, but each cons cell’s tail was computed via zipWith applied to the infinite fibs stream — the = operator, attempting to traverse xs to its end, forced that tail chain link by link, re-entering the zipWith (+) fibs (tl fibs) computation at every step, which never terminates because the underlying fibs stream is infinite. It cannot explain why null xs is the correct substitute: null in SASL inspects only the outermost constructor of xs; if xs is a cons cell h:t, null xs returns False immediately without evaluating t at all; if xs is [], null xs returns True; this is O(1) work regardless of the structure of the tail because it examines only the tag of the outermost constructor, not its contents. It cannot explain the diagnosis cost: the developer initially suspected a bug in zipWith (was it failing to stop at the shorter list?) or in take (was it generating more than 10 elements?), not in myLength, because myLength looked correct by inspection — the conditional if xs = [] then 0 else 1 + myLength (tl xs) appears to be a standard length function that any programmer familiar with strict languages would write. The non-termination manifested as an infinite loop with no error message, no stack overflow, and no diagnostic output because SASL’s SKI combinator reduction mechanism simply continues reducing graph nodes indefinitely with no built-in termination detection. Tracing which reduction sequence caused the loop required understanding how SKI combinator reduction evaluates = on lists: the equality primitive, when applied to two combinator expressions representing list spines, forces graph reduction of both arguments to normal form before returning a Boolean, which means the full infinite fibs stream was being forced via the tail chain of the supposedly-finite result of take 10 fibs. The six hours of combinator reduction tracing, strictness analysis, and predicate substitution are invisible in a diff showing five characters replaced.

SASL lazy evaluation: normal-order reduction, self-referential definitions, infinite lists, and SKI combinatory reduction

Lazy evaluation in SASL is formally known as normal-order evaluation: an expression is evaluated only when its value is needed for the enclosing computation to proceed, and when it is evaluated, it is evaluated only as far as necessary. This contrasts with applicative-order evaluation (strict evaluation), used in languages like Standard ML and OCaml, where every argument to a function is fully evaluated before the function body begins executing. In SASL, when a function is applied to an argument, the argument expression is passed unevaluated as a thunk — a suspended computation — to the function body; if the function body never examines the argument, the thunk is never forced; if the function body does examine the argument, the thunk is forced to whatever level of evaluation is required (typically weak head normal form, meaning the outermost constructor is revealed but inner fields remain as thunks). This evaluation strategy is the foundation of every interesting SASL program design decision.

Self-referential definitions in SASL work because the recursive reference in the definition is itself a thunk that is never forced until demanded. Consider def ones = 1 : ones: this creates a cons cell with head 1 and tail pointing (lazily) back to the same ones definition; hd ones forces the cons cell to reveal its head, returning 1; tl ones forces the cons cell to reveal its tail, returning ones (the same lazy definition, not a fully-evaluated infinite list); hd (tl ones) forces the tail to ones, then forces ones’s head, returning 1 again; the infinite list [1, 1, 1, ...] is never materialized in memory — only the cons cells that are explicitly demanded are ever created. The same principle applies to more complex self-referential definitions. def nats n = n : nats (n + 1) defines the infinite list of natural numbers starting at n: hd (nats 0) = 0; hd (tl (nats 0)) = 1; hd (tl (tl (nats 0))) = 2; each tl application forces the creation of the next cons cell by evaluating nats (n + 1) to weak head normal form, revealing the next cons cell without evaluating its tail.

The Fibonacci stream definition def fibs = 0 : 1 : zipWith (+) fibs (tl fibs) is the canonical demonstration of SASL’s lazy self-referential power. Here, zipWith f xs ys produces a new list by applying f to corresponding elements of xs and ys: def zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys. The fibs definition reads: the first element is 0, the second is 1, and every subsequent element is the sum of the corresponding elements of fibs (shifted by 0) and tl fibs (shifted by 1). To demand the third element, SASL forces zipWith (+) fibs (tl fibs) to reveal its head: it forces fibs to its head (0), forces tl fibs to the second cons cell and then its head (1), computes 0 + 1 = 1, and constructs a cons cell with head 1 and tail pointing to a thunk for zipWith (+) (tl fibs) (tl (tl fibs)). The fourth element is then the head of that thunk, which forces tl fibs to its head (1) and tl (tl fibs) to its head (1), computing 1 + 1 = 2. Each element of fibs is computed on demand by forcing exactly the thunks needed; elements already computed are shared (not recomputed), which is the graph reduction property of SASL’s implementation.

The take function bounds access to a potentially-infinite stream: a typical definition is def take n xs = if n = 0 then [] else hd xs : take (n - 1) (tl xs). take 10 fibs produces a finite list of ten elements by forcing exactly ten head-accesses and nine tail-accesses into fibs. The returned finite list has ten cons cells whose heads are fully evaluated integers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34), but the tail of the tenth cons cell is a thunk pointing back into the fibs stream. This is the subtle structure that xs = [] fails to handle: the list appears finite from the outside, but its tail thunk is connected to an infinite structure, and any operation that forces all tail thunks (as = does for structural equality) will follow that connection into non-termination.

The three fundamental list destructors in SASL are hd, tl, and null. hd (h:t) = h forces the argument to WHNF (revealing the outermost cons cell) and returns the head; hd [] is an error. tl (h:t) = t forces the argument to WHNF and returns the tail; tl [] is an error. null [] = True and null (h:t) = False: null forces the argument to WHNF to determine which constructor is present, but crucially, it does not force the contents of the constructor; for a cons cell h:t, null returns False without evaluating h or t; for the empty list [], null returns True. The cost of null is always O(1) regardless of the list structure beyond the outermost constructor.

SASL’s runtime evaluation mechanism is SKI combinator reduction, a technique due to David Turner’s implementation work. Programs in SASL are compiled to expressions over three primitive combinators: S (composition/substitution), K (constant/projection), and I (identity). The reduction rules are: K x y → x (discard the second argument); S f g x → f x (g x) (share the argument x between two functions and compose their results); I x → x (return the argument unchanged). Any lambda expression or function definition can be translated into a combinator expression using these rules, and the translation preserves sharing: when a thunk is forced and evaluated, the result is written back into the graph node so that subsequent references to the same thunk find the already-computed value rather than recomputing it. This sharing property is what makes lazy evaluation of self-referential definitions like fibs efficient: the second reference to fibs inside the zipWith (+) fibs (tl fibs) expression shares the already-partially-evaluated fibs graph rather than starting a new evaluation.

Pattern matching in SASL forces the matched argument to WHNF to determine which pattern applies: def f (h:t) = ... forces the argument to reveal either a cons cell (matching the (h:t) pattern) or the empty list (causing a match failure or falling through to the next equation); def f [] = ... matches the empty list. The forcing depth for pattern matching is exactly WHNF — enough to see the outermost constructor — not full normal form. This is why pattern matching on lists is safe in lazy languages even when the list is infinite: matching (h:t) reveals that the list is non-empty and binds h to the head thunk and t to the tail thunk without forcing either h or t beyond their own outermost constructors. where clauses in SASL allow local definitions scoped to a function: def f x = expr where helper y = ...; these are also evaluated lazily, so a where-bound definition is not computed unless the function body demands its value. SASL is the direct predecessor of KRC (the Kent Recursive Calculator, also designed by Turner in 1981), which in turn led to Miranda (1985), and Miranda’s design significantly influenced Haskell (1990). David Turner’s work on lazy evaluation and combinator reduction is one of the foundational threads of modern purely functional programming.

SASL strictness: the = operator, pattern matching evaluation, and when lazy thunks are forced

Understanding which operations force thunk evaluation, and to what depth, is the central skill of SASL retainer work. There are four categories of forcing in SASL, each with a different forcing depth and a different set of implications for lazy stream programming.

The first category is the hd and tl destructors and pattern matching: these force the argument to weak head normal form (WHNF). WHNF means the outermost constructor is revealed: for a list, this means forcing enough to determine whether the list is [] (the empty list constructor) or h:t (a cons cell constructor with head h and tail t). Critically, WHNF does not require evaluating h or t; they remain as thunks. This is why def f (h:t) = something with h and t is safe even if the list is generated lazily: the pattern match forces only the outermost constructor, creating bindings for h (a thunk for the head) and t (a thunk for the tail), and then the function body proceeds; h is forced only if the body uses it in a context requiring its value, and t is forced only if the body recursively destructures it. The null predicate is also WHNF-forcing: null xs forces xs to reveal its outermost constructor (either [] or _:_) and returns a Boolean based on which constructor it finds, without ever forcing the head or tail of a cons cell.

The second category is arithmetic operators. +, -, *, /, and comparison operators like <, >, <=, >= all force both of their operands to fully-evaluated numeric values before performing the computation. This is expected and correct: arithmetic on partially-evaluated expressions is not meaningful, so the primitive arithmetic operations in SASL’s combinator reduction engine force their arguments to integers or floats before proceeding. This means that any function that performs arithmetic on list elements will force those elements, but only those elements — the spine of the list and the other elements remain lazy.

The third category, and the most dangerous for lazy stream programming, is the = operator. In SASL, = performs structural equality comparison: it forces both of its arguments to full normal form (NF), not just WHNF, before determining whether they are equal. Full normal form means every substructure at every depth is evaluated to a primitive value or constructor. For atomic values (integers, booleans), = is equivalent to WHNF-forcing since integers and booleans have no substructure. For lists, however, = must traverse the entire spine of both arguments to determine equality: it forces the first cons cell of each list (WHNF), compares the heads (forcing both to NF), then recursively compares the tails (forcing each tail thunk, revealing the next cons cell or empty list, and continuing). The comparison terminates only when both lists have reached their [] terminator or a structural difference is found. This traversal is necessarily O(n) in the length of the shorter list, and for infinite lists it does not terminate.

The consequence for the myLength example is now precise: xs = [] forces xs to full NF to compare it with []; even though xs is the result of take 10 fibs and represents a conceptually-finite ten-element list, each cons cell in that list has a tail thunk that is part of the zipWith (+) fibs (tl fibs) computation; forcing each tail thunk reveals the next cons cell, which has another tail thunk connected to the same infinite fibs stream; = forces all ten tail thunks in the process of traversing the spine, each of which re-enters the zipWith computation over fibs; the tenth tail thunk is particularly expensive: it is a thunk for zipWith (+) (drop 10 fibs) (drop 10 (tl fibs)), which is itself an infinite lazy stream; = attempts to force this to NF, which requires forcing the entire infinite stream, which never completes.

The correct idiom for empty-list detection in SASL is always null xs, not xs = []. The corrected myLength: def myLength xs = if null xs then 0 else 1 + myLength (tl xs). Here, null xs forces xs only to WHNF; if xs is a cons cell (non-empty list), null xs returns False immediately without touching the head or tail; the else branch then forces tl xs to WHNF to get the tail, and recursively calls myLength on the tail; each recursive call forces exactly one cons cell and no more; after ten recursive calls on a ten-element list, the eleventh call receives the empty list [], null [] returns True, and the base case returns 0; the accumulated additions compute the result as the call stack unwinds. The take 10 fibs tail thunk that previously caused non-termination is never forced at all by this version of myLength because null stops at the outermost constructor.

An important consequence of this strictness profile is that length xs = 0 is also dangerous for lazy lists: length must traverse the entire spine to count, and then the arithmetic comparison forces the count to an integer; for an infinite list, length itself does not terminate; even for finite lists derived from infinite streams, length-based checks are O(n) when null would be O(1). The correct rule for SASL stream programming is: use null for empty-list detection; use hd and tl for element access; use pattern matching (which forces to WHNF) for structural dispatch; avoid = for list comparison unless both lists are known to be finite and fully evaluated; never use = or length on any list that might be connected to a lazy infinite stream.

The if-then-else construct in SASL is itself lazy in its branches: the condition is always evaluated (it must be, to determine which branch to take), but only the selected branch is evaluated, and only as far as the enclosing context requires. This is the standard lazy conditional and it interacts well with infinite streams: if null xs then [] else hd xs : someTransform (tl xs) evaluates null xs eagerly (forcing xs to WHNF), then evaluates only the selected branch; if xs is non-empty, it constructs a new cons cell with a lazy thunk for someTransform (tl xs) without evaluating that thunk.

Accumulator-style function definitions in SASL provide an important tool for controlling evaluation order in recursive functions over lists. Consider a sum function: the naive version def sum (h:t) = h + sum t | sum [] = 0 builds up a chain of deferred additions before evaluating any of them — on a list of length n, this creates n pending addition thunks before any arithmetic is done, which in SASL’s combinator reduction model means n graph nodes to reduce before producing the result. An accumulator-style version: def sum xs = sumAcc xs 0 where sumAcc (h:t) acc = sumAcc t (acc + h) | sumAcc [] acc = acc. Here, acc + h is evaluated at each step before the recursive call, so the accumulator is always a fully-evaluated integer, and each recursive call forces only the next cons cell to WHNF. The accumulator version is correct and efficient under SASL’s lazy evaluation because the + operator forces h (the head) to a numeric value at each step, but the (h:t) pattern match has already provided t as a lazy thunk; the recursive call on t does not force t’s contents until the next iteration, which is exactly the behavior needed. SASL has no explicit strictness annotations analogous to Haskell’s seq function or bang patterns (!); all forcing in SASL is implicit, mediated by the primitives, pattern matching, and arithmetic operations described above. This means that Haskell developers transitioning to SASL work cannot rely on seq or ! to fix space leaks or force evaluation at strategic points; instead, they must structure computations so that the right primitives are applied at the right positions to achieve the desired forcing depth.

The connection between SASL’s strictness model and Miranda is direct: Miranda is SASL’s descendant (via KRC), and Miranda’s lazy evaluation semantics are substantially the same as SASL’s; Miranda’s = operator is also structural and strict, and Miranda’s equivalent of null is the built-in function null :: [*] -> bool (same name, same semantics); Miranda adds a type system that can sometimes catch strictness mismatches at compile time through its type inference, but the fundamental laziness model is inherited from SASL’s design. Haskell, which drew heavily from Miranda’s design, added seq (a function that forces its first argument to WHNF before returning its second argument) and later bang patterns to give programmers explicit control over strictness; SASL had neither, relying entirely on the structural strictness of its primitive operations.

How HourTab tracks SASL developer retainer hours

SASL retainer work carries the invisible-hours problem in its most concentrated form: the question “which operations in this function are strict, and how deep do they force?” requires reasoning about SASL’s evaluation order for every primitive, every pattern match, and every operator in every function that touches a lazy stream. The non-termination described above — xs = [] in a length function — appears trivial in retrospect: replace with null. But the diagnosis cost was the bulk of the work. The developer initially suspected a bug in zipWith or take, not in myLength, because myLength appeared syntactically correct and was indeed correct for any finite list that was not derived from a lazy stream. The non-termination gave no error message or stack trace (combinator reduction just continues reducing graph nodes indefinitely; there is no “infinite loop detected” primitive in SKI graph reduction), no memory exhaustion (graph reduction with sharing uses bounded memory for many self-referential definitions), and no partial output (the non-termination occurred before any result was produced). The only observable symptom was that the process ran without producing output.

Identifying the culprit required: first, recognizing that non-termination was occurring at all (rather than slowness due to an O(n²) algorithm, for instance); second, isolating the non-termination to myLength specifically by testing hd fibs, take 10 fibs, and other operations on fibs in isolation, confirming that fibs itself and take were not the problem; third, understanding why myLength (take 10 fibs) could fail when take 10 fibs succeeded — this required knowing that take 10 fibs returns a list that is finite at the top level but whose tail thunks are connected to the infinite fibs stream; fourth, tracing through the evaluation of myLength (take 10 fibs) to find which specific operation triggered the non-termination — this required understanding SKI combinator reduction order well enough to see that xs = [] forces xs to full NF, which forces the tail thunk of the tenth cons cell, which is a thunk for an infinite tail of fibs; fifth, confirming that null avoids this forcing (by verifying that null is defined to force only to WHNF in SASL’s primitive semantics, not to full NF); and sixth, verifying the fix by testing myLength (take 10 fibs) with the corrected definition and confirming that it returns 10 correctly. Steps three through five together constitute the strictness analysis and combinator reduction tracing that consumed the bulk of the six hours.

HourTab gives SASL developers a public retainer-hours URL they send to clients — typically programming languages researchers working with historical lazy functional programming systems, academics studying combinator reduction as both a theoretical model and a practical implementation technique, and engineers implementing SASL interpreters or SKI-reduction evaluators for language research projects. For SASL retainers, each work log entry should name the mechanism at the level of the strictness analysis: which operator was forcing evaluation (= operator vs null vs hd vs tl vs arithmetic), which argument was being forced (which xs, which stream), what the forcing depth was (WHNF sufficient, or full NF required), and whether the forcing caused non-termination. Comparative context for scope discussions: SASL retainer work is related to but distinct from Eff developer retainers (Eff focuses on algebraic effects and handlers, not lazy evaluation; Eff has no infinite streams or lazy thunks) and Effekt developer retainers (Effekt uses second-class capabilities and lexical effect scoping; also not a lazy language); Miranda developer retainers would be the closest related engagement (Miranda is SASL’s direct descendant via KRC; Miranda has the same lazy evaluation model, the same null predicate, and a similar = strictness profile, but adds a static type system, modules, and a richer standard library; a SASL retainer engaging with historical lazy FP research may overlap with Miranda work in the SASL-KRC-Miranda lineage). Haskell’s explicit strictness annotations (seq, !, BangPatterns extension, Data.List.isNull) are equivalent in purpose to SASL’s null predicate, but SASL’s model is simpler: there are no strictness annotations because all forcing is implicit, and the discipline of using the right predicate (null vs =) is the entire strictness programming model for list processing.

HourTab’s work log format for SASL retainers makes the strictness analysis, stream tracing, and combinator reduction debugging visible to clients who would otherwise see only the symptom — a process that runs forever without producing output — and not understand why the fix required: tracing all operations in myLength to identify which one forces thunks beyond WHNF, confirming that = is the structural equality primitive and not an identity comparison, verifying that the lazy tail of take 10 fibs is connected to the infinite fibs stream and is therefore non-terminating under full NF forcing, understanding the difference between WHNF and NF in SASL’s combinator reduction engine, selecting null as the O(1) WHNF-forcing predicate that replaces the structural equality check, and validating the fix against the original test case. The log entry “replaced = [] with null, 6h” is correct and complete as a time record; it is incomplete as a value record. HourTab’s categorized log format — strictness category (operator: =; forcing depth: full NF; caused non-termination: yes; fix: null; forcing depth: WHNF; non-termination: eliminated), stream category (stream: fibs; definition: self-referential via zipWith; access via take 10; tail thunks connected to infinite stream), combinator category (reduction sequence traced: = applied to result of take; graph node forced: tail thunk of 10th cons cell; reduction step that re-entered fibs: forcing of zipWith (+) (drop 10 fibs) (drop 10 (tl fibs))) — makes the diagnostic path visible and gives clients who funded the work a record of what was actually investigated and why six hours was a reasonable duration for a five-character change.

FAQ: SASL developer retainers