Blog › ICP guides

Curry developer on retainer: functional-logic programming, free variable unification, encapsulated search with allValues, and pakcs/kics2 programs on monthly retainer

September 30, 2026 · ~15 min read

A Curry developer was building a constraint-solving library for scheduling problems. The developer implemented a solver using Curry’s functional-logic approach: free variables introduced with let x free in ... represented unbound schedule slots, equational constraints (x =:= v) bound them by unification, and overlapping function rules introduced non-determinism to enumerate candidate solutions. The developer called the solver directly at the top level — main = print (solve constraints) — expecting the runtime to enumerate and print all valid schedules. Under PAKCS’s default depth-first search, calling a non-deterministic function directly produces the first solution found (or enters an infinite loop if the search space is unbounded) and does not automatically collect all solutions into a list. The developer’s output showed exactly one schedule when multiple valid solutions existed: the PAKCS Prolog backend found the first value along the depth-first traversal of the non-determinism tree and returned it as the result of the expression; subsequent branches were never explored because the computation had already produced a value and terminated. Solutions collected: 1 → N (all valid schedules) after wrapping in allValues (solve constraints) in KiCS2 or getAllValues (solve constraints) in PAKCS.

The work log entry read “wrapped solver in allValues to collect all solutions, 7h.” It names the result and duration. It cannot explain why calling non-deterministic functions directly does not enumerate all solutions in Curry — unlike Prolog, where a query at the interactive top level naturally backtracks through all solutions as the user presses semicolon, Curry under PAKCS’s depth-first strategy is a compiled functional-logic language where a non-deterministic expression at the top level of a main function produces one value and the program exits; to collect all solutions the developer must switch to encapsulated search, which runs the non-deterministic expression in a captured context that explores all branches and accumulates their results into a list before returning. It cannot explain why the one solution found was actually a correct solution and not a wrong one — the PAKCS Prolog backend’s DFS traversal does find a genuine solution that satisfies all constraints; the question is whether the developer intended one valid schedule (in which case the original code was correct and the requirements were satisfied) or all valid schedules (in which case the single-solution output was a completeness failure, not a correctness failure), and that distinction is a requirements analysis question that required reviewing the scheduling problem’s specification with the client before any code was changed. It cannot explain the performance implications of switching to encapsulated search — allValues must explore the entire search tree, evaluating every branch to collect every solution; for a scheduling problem with N slots and K valid assignments per slot, the search tree can be exponentially large; the developer had to estimate the expected number of valid schedules, determine whether the full enumeration fit in available memory, and decide whether the caller actually needed all solutions simultaneously or could process them lazily. It cannot explain the downstream restructuring — every caller of solve constraints that used the result as a scalar Schedule value had to be updated to receive and iterate over [Schedule], which touched module boundaries, type signatures, and rendering logic. The 7 hours of search strategy analysis, encapsulated search scoping, solution space estimation, and caller restructuring are invisible in a diff that shows allValues ( added around one expression.

Curry functional-logic programming: free variables, equational constraints, functional patterns, and non-deterministic choice

Curry is a declarative programming language that unifies the functional paradigm (as embodied by Haskell) with the logic paradigm (as embodied by Prolog), designed by Michael Hanus, Herbert Kuchen, Juan José Moreno-Navarro, and colleagues at Kiel University and RWTH Aachen beginning in the 1990s. The language uses Haskell’s type system, syntax, and higher-order functions while adding Prolog-style free variables, unification, and non-deterministic computation as first-class language features. The result is a language where a single function can both compute (returning a value given inputs) and constrain (narrowing a free variable to a value by satisfying a predicate), and where the same syntax expresses functional programs, logic programs, and programs that combine both styles.

Free variables are introduced with the let x free in ... construct: let slot free in slot =:= Morning && validSchedule slot introduces slot as an unbound logical variable, applies the equational constraint slot =:= Morning to bind it to Morning, and then checks the binding against validSchedule. The =:= operator performs strict equational constraint: it evaluates its right-hand side argument to normal form (fully reducing all function applications) before attempting unification with the left-hand side. This differs from Prolog’s = operator, which performs syntactic unification without evaluation — in Prolog, X = 1 + 1 binds X to the term 1+1 without evaluating it to 2; in Curry, x =:= 1 + 1 evaluates 1 + 1 to 2 and then binds x to 2. This strictness has significant implications: if the right-hand side is a complex expression, it must successfully reduce to normal form before unification proceeds; if reduction fails (throws an error, diverges, or produces a non-deterministic value itself), the constraint fails or introduces additional non-determinism.

Non-determinism in Curry arises from two sources: overlapping function rules and the ? operator. Overlapping rules occur when multiple rules for the same function can match the same argument. For example, a function that generates candidate schedule slots might have two rules: candidate Morning = True and candidate Afternoon = True. When called as candidate slot where slot is a free variable, Curry’s narrowing mechanism considers both rules simultaneously, non-deterministically binding slot to Morning in one branch and Afternoon in another. The ? operator expresses explicit non-deterministic choice: a ? b evaluates to either a or b non-deterministically, with each evaluation of the expression potentially selecting a different branch. Both mechanisms create a tree of possible computations that the search strategy explores.

Functional patterns extend Curry’s pattern matching with logic-style matching. A functional pattern in the left-hand side of a rule is an expression that contains free variables, and it is matched against a concrete value by running the expression in reverse via unification rather than by structural decomposition. For example, a function extract (append xs (y:ys)) = y uses append xs (y:ys) as a functional pattern in the LHS: given a concrete list, Curry determines the free variables xs, y, and ys such that append xs (y:ys) unifies with the given list, effectively decomposing the list at any split point non-deterministically. This is more expressive than Haskell’s structural patterns but requires that the function used in the pattern (here append) has a known inverse that Curry can compute via narrowing.

The two main Curry implementations differ in their search strategies and compilation backends. PAKCS (Portland Aachen Kiel Curry System) compiles Curry source to Prolog and executes it using SICStus Prolog or SWI-Prolog as the backend; its default search strategy is Prolog’s depth-first search, which explores the non-determinism tree left branch first, finds the first solution, and returns it. KiCS2 (Kiel Curry System 2) compiles Curry source to Haskell and executes it via GHC; it uses “needed search,” a lazy demand-driven strategy that evaluates non-deterministic expressions only as far as needed to produce the requested result, and handles non-determinism by threading it through the Haskell runtime as a monad-like structure. The REPL in both systems accepts :load Module to load a module file, :eval expr to evaluate an expression, and :type expr to query the type of an expression without evaluating it. Both systems support the standard Curry module system and can import standard library modules such as Data.List, Control.Search.SetFunctions, and Control.Search.AllValues.

Curry retainer work sits at the intersection of functional and logic programming, making its retainer neighbors worth noting. Haskell developer retainers cover the functional subset: type classes, monads, lazy evaluation, GHC extensions — but Haskell is deterministic, has no free variables, no =:=, and no allValues; a Haskell developer on retainer who has never worked with Curry will not know why let x free in x =:= v differs from let x = v in x (the former performs unification-based constraint solving that can be used in non-deterministic contexts; the latter is a simple let-binding that always evaluates v immediately). Prolog developer retainers cover the logic subset: unification, backtracking, cut — but Prolog is untyped, has no type classes, and no higher-order typed functions; a Prolog developer on retainer who has never worked with Curry will be familiar with free variable binding but unfamiliar with how Curry’s type system constrains what free variables can be unified with, and will expect interactive top-level backtracking that Curry does not provide by default. The Eff developer retainer is a different paradigm (algebraic effects with continuation-based handlers) and the Effekt developer retainer addresses lexical capability-based effects — both differ fundamentally from Curry’s functional-logic unification model.

Curry encapsulated search: allValues, set functions, getAllValues, and KiCS2 search modes

Encapsulated search is the mechanism in Curry for collecting all solutions to a non-deterministic computation into a deterministic data structure. The key insight is that at the top level of a Curry program, a non-deterministic expression produces one value under PAKCS (the first value found by DFS) or is handled by the Haskell runtime under KiCS2 in a way that depends on how the result is consumed. To deliberately enumerate all solutions into a list, the developer must wrap the non-deterministic expression in an encapsulated search function that creates an isolated context, explores all branches, and accumulates the results.

In KiCS2, the primary encapsulated search function is allValues :: a -> IO [a] from the Control.Search.AllValues module. It takes a non-deterministic expression of type a and returns an IO [a] action that, when executed, explores all non-deterministic branches of the expression and collects their results into a list. The ordering of results in the list follows the search strategy used by KiCS2’s needed search. Usage in a do-block: schedules <- allValues (solve constraints) binds the full list of solutions to schedules; the developer can then process, filter, or display all of them. In PAKCS, the equivalent function is getAllValues :: a -> IO [a] from the Control.Search.AllValues module; its semantics follow PAKCS’s DFS traversal order, so results are ordered depth-first left-to-right through the non-determinism tree.

Set functions provide a different interface to encapsulated search that does not require IO. The Control.Search.SetFunctions module provides set0 :: a -> Values a for wrapping 0-ary (nullary) non-deterministic expressions, set1 :: (a -> b) -> a -> Values b for wrapping 1-ary functions, set2 :: (a -> b -> c) -> a -> b -> Values c for 2-ary functions, and so on. The Values a type is an abstract type representing a multiset of values; it is not in IO, which means set functions can be used in pure (non-IO) code and composed with other pure functions. From a Values a, the developer can extract results with toList :: Values a -> [a] (converts to an ordinary list), check emptiness with isEmpty :: Values a -> Bool (returns True if no solutions exist), and test membership with valueOf :: a -> Values a -> Bool (returns True if a specific value is in the solution set). Set functions are the preferred choice when the encapsulated search result needs to be used in pure code — for example, when computing whether any valid schedule exists as part of a larger pure computation, not (isEmpty (set0 (solve constraints))) is cleaner than wrapping in IO.

The distinction between collecting all solutions into memory at once versus processing them lazily matters for large search spaces. allValues and toList (set0 ...) both evaluate the entire search tree and construct the full solution list before returning; if the scheduling problem has thousands of valid schedules, this means all of them are held in memory simultaneously. For large solution spaces, KiCS2’s findFirst :: a -> Maybe a retrieves only the first solution and terminates immediately after, without exploring the remaining branches — this is O(depth of first solution in the search tree) rather than O(all branches). The developer working on the scheduling library had to determine whether the client genuinely needed all valid schedules presented simultaneously, or whether an iterative approach — present the first solution, allow the user to request the next, and explore the tree on demand — would serve the use case with far less memory pressure.

Understanding the search tree structure is essential for predicting the behavior of encapsulated search. Each overlapping pair of function rules for a function f creates a binary branch in the non-determinism tree: one branch for each rule. The ? operator also creates a binary branch. When a function has three overlapping rules, it creates a ternary branch (or equivalently, a nested binary tree). The total number of leaves in the search tree is the product of the branching factors at each non-deterministic choice point encountered along any path from root to leaf. Under PAKCS’s DFS, the leftmost leaf (first rule, first choice at each point) is found first. Under KiCS2’s needed search, the order depends on which branches are “needed” to produce the output requested by the encapsulated search call. For the scheduling problem, the developer had to trace the non-determinism tree manually — identifying each overlapping rule pair, each ? application, and each free variable narrowing point — to estimate the total search space before deciding whether allValues was practical or whether a more targeted constraint was needed to prune branches before encapsulated search was invoked.

PAKCS’s compilation to Prolog means that the DFS behavior is inherited directly from the Prolog backend’s depth-first unification procedure. When PAKCS compiles an overlapping rule pair, it emits two Prolog clauses; Prolog’s resolution mechanism tries the first clause and, on backtracking, tries the second. The PAKCS getAllValues implementation uses Prolog’s findall/3 to collect all backtracked results, wrapping the computation in a context that drives backtracking to exhaustion. This is why PAKCS’s getAllValues can enter an infinite loop on search spaces with infinite branches — Prolog’s findall/3 backtracks until all choices are exhausted, which never terminates for infinite non-determinism trees. KiCS2’s needed search, implemented through Haskell’s lazy evaluation and a non-determinism monad, handles some infinite search spaces more gracefully by only evaluating branches as they are demanded; but for allValues, which demands all solutions, both KiCS2 and PAKCS will diverge on infinite search spaces. The developer’s responsibility in encapsulated search design is to ensure the search space is finite, or to use findFirst or lazy enumeration patterns that allow termination before the full tree is explored.

The idet :: a -> a function (identity in deterministic mode) available in some Curry configurations asserts to the compiler that a function is guaranteed to be deterministic — that it has no overlapping rules and introduces no non-determinism. This assertion allows the compiler to skip the overhead of non-determinism tracking for those functions, improving performance. Using idet on a function that is actually non-deterministic is a type-unsafe operation that can produce incorrect results; the developer must verify the determinism guarantee before applying it. In practice, idet is used on helper functions that perform purely functional computation within a larger non-deterministic program, marking them as safe to call without the non-determinism machinery.

How HourTab tracks Curry developer retainer hours

Curry retainer work carries the invisible-hours problem specific to functional-logic systems: the question “why does this solver produce one solution instead of all solutions?” requires understanding the interaction between Curry’s non-determinism semantics, the search strategy of the chosen backend, and the distinction between calling a non-deterministic expression directly versus wrapping it in encapsulated search. The encapsulated search restructuring described above — where the developer added allValues ( around one expression — appears in the diff as a two-character change to a function call. The hours before that change were: identifying that the behavior was a completeness failure rather than a correctness failure (the one solution found was valid; the problem was that others were not found); reviewing the scheduling problem specification to confirm all valid schedules were required; determining that the search space was finite under all valid constraint combinations; estimating the maximum number of valid schedules to bound the memory footprint of allValues; choosing between PAKCS and KiCS2 based on the search space characteristics (KiCS2’s needed search handles the specific non-determinism patterns in the constraint solver more efficiently); updating all callers from Schedule to [Schedule]; and verifying that the full solution set, when enumerated, included exactly the schedules that the client expected.

The formula for logging Curry retainer hours should name the mechanism precisely. For search strategy work: name the encapsulation form used (direct call, allValues, getAllValues, set0/set1, findFirst), the result count before and after (1 solution → N solutions), the backend used (PAKCS with SWI-Prolog, KiCS2 with GHC), and the reason for the choice. For free variable and constraint work: name the variable (slot), the constraint (slot =:= Morning), whether the strict evaluation in =:= affected the solution space, and which unification result was expected versus observed. For functional pattern work: name the function used in the LHS pattern, which rule was expected to match, and whether overlapping rules introduced unintended non-determinism. For set function work: name the arity (set0, set1), the result of toList (how many solutions), and whether isEmpty checks or valueOf membership tests were used as preconditions.

Comparing Curry retainers to adjacent language retainers clarifies what is and is not covered. Haskell developer retainers cover the functional subset of Curry: type classes, monads, lazy evaluation, GHC performance optimization, Data.Map and Data.Set data structures, STM for concurrency. But Haskell developer retainers do not cover free variables, equational constraints, non-deterministic function rules, or encapsulated search — these are Curry-specific mechanisms that have no direct Haskell equivalents. A Haskell developer hired on a Curry retainer will know GHC (which KiCS2 uses as its backend) but will not know Curry’s narrowing semantics, will not understand why let x free in x =:= v is different from monadic binding, and will not know how to structure set1 for pure-code search or when to prefer findFirst over allValues. Prolog developer retainers cover the logic subset: unification, backtracking, cut, assert/retract, definite clause grammars. But Prolog developer retainers do not cover Curry’s type system, type classes, higher-order typed functions, functional patterns, or the interaction between Haskell-style type inference and Prolog-style constraint solving. A Prolog developer hired on a Curry retainer will understand free variable binding but will not know how Curry’s type system constrains which values a free variable can unify with, will not understand functional patterns (which have no Prolog equivalent), and will expect interactive backtracking at the top level that Curry’s compiled execution model does not provide.

HourTab gives Curry developers a public retainer-hours URL they send to clients — typically academic researchers prototyping constraint-solving algorithms (schedulers, type checkers, program analysis tools) using Curry’s functional-logic synthesis; Prolog users migrating to Curry to gain a type system while retaining their logic-programming intuition; and backend engineers exploring functional-logic programming for configuration DSLs where both functional computation over configuration values and constraint-based validation of configuration consistency are needed in the same language. For Curry retainers, each work log entry should name the mechanism: search category (which encapsulation form, how many solutions before and after, which backend, why that backend); free variable category (variable name, =:= target, whether strict evaluation changed the result); functional pattern category (function in LHS, which rule matched, whether overlap was intentional); set function category (arity, toList count, isEmpty or valueOf usage). Curry’s invisible hours come from the gap between the two-character diff of adding allValues ( and the seven hours of search space analysis, backend selection, solution estimation, and caller restructuring that made that change safe to deploy. HourTab’s work log closes that gap, turning the technical reasoning into client-visible evidence of why retainer work on a functional-logic language takes the time it does.

FAQ: Curry developer retainers