3.1 Base calculus

The base calculus ${\lambda_{\textrm{b}}}$ is a fine-grain call-by-value (Levy et al., Reference Levy, Power and Thielecke2003) variation of PCF (Plotkin, Reference Plotkin1977). Fine-grain call-by-value is similar to A-normal form (Flanagan et al., Reference Flanagan, Sabry, Duba and Felleisen1993) in that every intermediate computation is named, but unlike A-normal form is closed under reduction.

The syntax of ${\lambda_{\textrm{b}}}$ is as follows.

The ground types are Nat and Unit which classify natural number values and the unit value, respectively. The function type $A \to B$ classifies functions that map values of type A to values of type B. The binary product type $A \times B$ classifies pairs of values whose first and second components have types A and B, respectively. The sum type $A + B$ classifies tagged values of either type A or B. Type environments $\Gamma$ map term variables to their types. For hygiene, we require that the variables appearing in a type environment are distinct.

We let k range over natural numbers and c range over primitive operations on natural numbers ( $+, -, =$ ). We let x, y, z range over term variables. We also use f, g, h, q for variables of function type and i, j for variables of type Nat. The value terms are standard.

All elimination forms are computation terms. Abstraction is eliminated using application ( $V\,W$ ). The product eliminator $(\mathbf{let} \; {{{{{{\langle x,y \rangle}}}}}} = V \; \mathbf{in} \; N)$ splits a pair V into its constituents and binds them to x and y, respectively. Sums are eliminated by a case split ( $\mathbf{case}\; V\;\{\mathbf{inl}\; x \mapsto M; \mathbf{inr}\; y \mapsto N\}$ ). A trivial computation $(\mathbf{return}\;V)$ returns value V. The sequencing expression $(\mathbf{let} \; x {{{{{{\leftarrow}}}}}} M \; \mathbf{in} \; N)$ evaluates M and binds the result value to x in N.

The typing rules are those given in Figure 1, along with the familiar Exchange, Weakening and Contraction rules for environments. (Note that thanks to Weakening we are able to type terms such as $(\lambda x^A. (\lambda x^B.x))$ , even though environments are not permitted to contain duplicate variables.) We require two typing judgements: one for values and the other for computations. The judgement $\Gamma \vdash \square : A$ states that a $\square$ -term has type A under type environment $\Gamma$ , where $\square$ is either a value term (V) or a computation term (M). The constants have the following types.

Fig. 1. Typing rules for ${\lambda_{\textrm{b}}}$ .

We give a small-step operational semantics for

${\lambda _b}$

with evaluation contexts in the style of Felleisen (Reference Felleisen1987). The reduction relation ${{{{{{\leadsto}}}}}}$ is defined on computation terms via the rules given in Figure 2. The statement $M {{{{{{\leadsto}}}}}} N$ reads: term M reduces to term N in one step. We write $R^+$ for the transitive closure of relation R and $R^*$ for the reflexive, transitive closure of relation R.

Fig. 2. Contextual small-step operational semantics.

Most often, we are interested in ${{{{{{\leadsto}}}}}}$ as a relation on closed terms. However, we will sometimes consider it as a relation on terms involving free variables, with the stipulation that none of these free variables also occur as bound variables within the terms. Since we never perform reductions under a binder, this means that the notation $M[V/x]$ in our rules may be taken simply to mean M with V textually substituted for free occurrences of x (no variable capture is possible). We also take $\ulcorner c \urcorner$ to mean the usual interpretation of constant c as a meta-level function on closed values.

The type soundness of our system is easily verified. This is subsumed by the property we shall formally state for the richer language ${\lambda_{\textrm{h}}}$ in Theorem 1 below.

When dealing with reductions $N {{{{{{\leadsto}}}}}} N'$ , we shall often make use of the idea that certain subterm occurrences within N’ arise from corresponding identical subterms of N. For instance, in the case of a reduction $(\lambda x^A .M) V {{{{{{\leadsto}}}}}} M[V/x]$ , we shall say that any subterm occurrence P within any of the substituted copies of V on the right-hand side is a descendant of the corresponding subterm occurrence within the V on the left-hand side. (Descendants are called residuals e.g. in Barendregt, Reference Barendregt1984.) Similarly, any subterm occurrence Q of $M[V/x]$ not overlapping with any of these substituted copies of V is a descendant of the corresponding occurrence of an identical subterm within the M on the left. This notion extends to the other reduction rules in the evident way; we suppress the formal details. If P’ is a descendant of P, we also say that P is an ancestor of P’. By transitivity we extend these notions to the relations ${{{{{{\leadsto}}}}}}^+$ and ${{{{{{\leadsto}}}}}}^*$ . Note that if $N{{{{{{\leadsto}}}}}}^* N'$ then a subterm occurrence in N’ may have at most one ancestor in N but a subterm occurrence in N may have many descendants in N’.

Notation. We elide type annotations when clear from context. For convenience we often write code in direct-style assuming the standard left-to-right call-by-value elaboration into fine-grain call-by-value (Moggi, Reference Moggi1991; Flanagan et al., Reference Flanagan, Sabry, Duba and Felleisen1993). For example, the expression $f\,(h\,w) + g\,{\langle \rangle}$ is syntactic sugar for:

We define sequencing of computations in the standard way.

\[ M;N \mathrel{\overset{{\mbox{def}}}{=}} \mathbf{let}\;x {{{{{{\leftarrow}}}}}} M \;\mathbf{in}\;N, \quad \text{where $x \notin FV(N)$}\]

We make use of standard syntactic sugar for pattern matching. For instance, we write

\[ \lambda{{{{{{\langle . \rangle}}}}}}M \mathrel{\overset{{\mbox{def}}}{=}} \lambda x^{\mathrm{Unit}}.M, \quad \text{where $x \notin FV(M)$}\]

for suspended computations, and if the binder has a type other than Unit, we write:

\[ \lambda\_^A.M \mathrel{\overset{{\mbox{def}}}{=}} \lambda x^A.M, \quad \text{where $x \notin FV(M)$}\]

We use the standard encoding of booleans as a sum:

3.2 Handler calculus

We now define ${\lambda_{\textrm{h}}}$ as an extension of ${\lambda_{\textrm{b}}}$ .

We assume a fixed effect signature $\Sigma$ that associates types $\Sigma(\ell)$ to finitely many operation symbols $\ell$ . An operation type $A \to B$ classifies operations that take an argument of type A and return a result of type B. A handler type $C \Rightarrow D$ classifies effect handlers that transform computations of type C into computations of type D. Following Pretnar (Reference Pretnar2015), we assume a global signature for every program. Computations are extended with operation invocation ( $\mathbf{do}\;\ell\;V$ ) and effect handling ( $\mathbf{handle}\; M \;\mathbf{with}\; H$ ). Handlers are constructed from a single success clause $(\{\mathbf{val}\; x \mapsto M\})$ and an operation clause $(\{ \ell \; p \; r \mapsto N \})$ for each operation $\ell$ in $\Sigma$ ; here the x,p,r are considered as bound variables. Following Plotkin & Pretnar (Reference Plotkin and Pretnar2013), we adopt the convention that a handler with missing operation clauses (with respect to $\Sigma$ ) is syntactic sugar for one in which all missing clauses perform explicit forwarding:

\[ \{\ell \; p \; r \mapsto \mathbf{let}\; x {{{{{{\leftarrow}}}}}} \mathbf{do} \; \ell \, p \;\mathbf{in}\; r \, x\}\]

The typing rules for ${\lambda_{\textrm{h}}}$ are those of ${\lambda_{\textrm{b}}}$ (Figure 1) plus three additional rules for operations, handling, and handlers given in Figure 3. The T-Do rule ensures that an operation invocation is only well-typed if the operation $\ell$ appears in the effect signature $\Sigma$ and the argument type A matches the type of the provided argument V. The result type B determines the type of the invocation. The T-Handle rule types handler application. The T-Handler rule ensures that the bodies of the success clause and the operation clauses all have the output type D. The type of x in the success clause must match the input type C. The type of the parameter p ( $A_\ell$ ) and resumption r ( $B_\ell \to D$ ) in operation clause $H^{\ell}$ is determined by the type of $\ell$ ; the return type of r is D, as the body of the resumption will itself be handled by H. We write $H^{\ell}$ and $H^{\mathrm{val}}$ for projecting success and operation clauses.

We extend the operational semantics to ${\lambda_{\textrm{h}}}$ . Specifically, we add two new reduction rules: one for handling return values and another for handling operation invocations.

The first rule invokes the success clause. The second rule handles an operation via the corresponding operation clause.

Fig. 3. Additional typing rules for ${\lambda_{\textrm{h}}}$ .

To allow for the evaluation of subterms within $\mathbf{handle}$ expressions, we extend our earlier grammar for evaluation contexts to one for handler contexts:

We then replace the S-Lift rule with a corresponding rule for handler contexts.

However, it is critical that the rule S-Op is restricted to pure evaluation contexts ${{{{{{\mathcal{E}}}}}}}$ rather than handler contexts. This ensures that the $\mathbf{do}$ invocation is handled by the innermost handler (recalling our convention that all handlers handle all operations). If arbitrary handler contexts ${{{{{{\mathcal{H}}}}}}}$ were permitted in this rule, the semantics would become non-deterministic, as any handler in scope could be selected.

The ancestor-descendant relation for subterm occurrences extends to ${\lambda_{\textrm{h}}}$ in the obvious way.

We now characterise normal forms and state the standard type soundness property of ${\lambda_{\textrm{h}}}$ .

It is worth observing that our language does not prohibit ‘operation extrusion’: even if we begin with a term in which all $\mathbf{do}$ invocations fall within the scope of a handler, this property need not be preserved by reductions, since a $\mathbf{do}$ invocation may pass another $\mathbf{do}$ to the outermost handler. Such behaviour may be readily ruled out using a type-and-effect system, but this additional machinery is not necessary for our present purposes.

4.1 Base machine

We choose a CEK-style abstract machine semantics (Felleisen & Friedman, Reference Felleisen and Friedman1987) for ${\lambda _b}$ based on that of Hillerström et al. (Reference Hillerström, Lindley and Longley2020). The CEK machine operates on configurations which are triples of the form ${{{{{{\langle M \mid \gamma \mid \sigma \rangle}}}}}}$ . The first component contains the computation currently being evaluated. The second component contains the environment $\gamma$ which binds free variables. The third component contains the continuation which instructs the machine how to proceed once evaluation of the current computation is complete. The syntax of abstract machine states is as follows.

Values consist of function closures, constants, pairs, and left or right tagged values. We refer to continuations of the base machine as pure. A pure continuation is a stack of pure continuation frames. A pure continuation frame $(\gamma, x, N)$ closes a let-binding $\mathbf{let} \;x{{{{{{\leftarrow}}}}}} [~] \;\mathbf{in}\;N$ over environment $\gamma$ . We write ${{{{{{[]}}}}}}$ for an empty pure continuation and $\phi {{{{{{::}}}}}} \sigma$ for the result of pushing the frame $\phi$ onto $\sigma$ . We use pattern matching to deconstruct pure continuations.

The abstract machine semantics is given in Figure 4. The transition relation ( ${{{{{{\longrightarrow}}}}}}$ ) makes use of the value interpretation ( $[\![ - ]\!] $ ) from value terms to machine values. The machine is initialised by placing a term in a configuration alongside the empty environment ( $\emptyset$ ) and the identity pure continuation ( ${{{{{{[]}}}}}}$ ). The rules (M-App), (M-Rec), (M-Const), (M-Split), (M-CaseL), and (M-CaseR) eliminate values. The (M-Let) rule extends the current pure continuation with let bindings. The (M-RetCont) rule extends the environment in the top frame of the pure continuation with a returned value. Given an input of a well-typed closed computation term $ \vdash M : A$ , the machine will either diverge or return a value of type A. A final state is given by a configuration of the form ${{{{{{\langle \mathbf{return}\;V \mid \gamma \mid {{{{{{[]}}}}}} \rangle}}}}}}$ in which case the final return value is given by the denotation $[\![ V ]\!] \gamma$ of V under environment $\gamma$ .

Fig. 4. Abstract machine semantics for ${\lambda_{\textrm{b}}}$ .

Correctness. The base machine faithfully simulates the operational semantics for ${\lambda_{\textrm{b}}}$ ; most transitions correspond directly to $\beta$ -reductions, but M-Let performs an administrative step to bring the computation M into evaluation position. We formally state and prove the correspondence in Appendix A, relying on an inverse map $(|-|)$ from configurations to terms (Hillerström et al., Reference Hillerström, Lindley and Longley2020).

4.2 Handler machine

We now enrich the ${\lambda_{\textrm{b}}}$ machine to a ${\lambda_{\textrm{h}}}$ machine. We extend the syntax as follows.

The notion of configurations changes slightly in that the continuation component is replaced by a generalised continuation $\kappa \in \mathsf{Cont}$ (Hillerström et al., Reference Hillerström, Lindley and Longley2020); a continuation is now a list of resumptions. A resumption is a pair of a pure continuation (as in the base machine) and a handler closure ( $\chi$ ). A handler closure consists of an environment and a handler definition, where the former binds the free variables that occur in the latter. The machine is initialised by placing a term in a configuration alongside the empty environment ( $\emptyset$ ) and the identity continuation ( $\kappa_0$ ). The latter is a singleton list containing the identity resumption, which consists of the identity pure continuation paired with the identity handler closure:

\[\kappa_0 \mathrel{\overset{{\mbox{def}}}{=}} [({{{{{{[]}}}}}}, (\emptyset, \{\mathbf{val}\;x \mapsto \mathbf{return}~x\}))]\]

Machine values are augmented to include resumptions as an operation invocation causes the topmost frame of the machine continuation to be reified (and bound to the resumption parameter in the operation clause).

The handler machine adds transition rules for handlers and modifies $(\text{M-L<sc>et</sc>})$ and $(\text{M-RetCont})$ from the base machine to account for the richer continuation structure. Figure 5 depicts the new and modified rules. The $(\text{M-Handle})$ rule pushes a handler closure along with an empty pure continuation onto the continuation stack. The $(\text{M-RetHandler})$ rule transfers control to the success clause of the current handler once the pure continuation is empty. The $(\text{M-Handle-Op})$ rule transfers control to the matching operation clause on the topmost handler, and during the process it reifies the handler closure. Finally, the $(\text{M-Resume})$ rule applies a reified handler closure, by pushing it onto the continuation stack. The handler machine has two possible final states: either it yields a value or it gets stuck on an unhandled operation.

Fig. 5. Abstract machine semantics for ${\lambda_{\textrm{h}}}$ .

Correctness. The handler machine faithfully simulates the operational semantics of ${\lambda_{\textrm{h}}}$ . Extending the result for the base machine, we formally state and prove the correspondence in Appendix B.

4.3 Realisability and asymptotic complexity

As witnessed by the work of Hillerström & Lindley (Reference Hillerström and Lindley2016), the machine structures are readily realisable using standard persistent functional data structures. Pure continuations on the base machine and generalised continuations on the handler machine can be implemented using linked lists with a time complexity of ${{{{{{\mathcal{O}}}}}}}(1)$ for the extension operation $(\_{{{{{{::}}}}}}\_)$ . The topmost pure continuation on the handler machine may also be extended in time ${{{{{{\mathcal{O}}}}}}}(1)$ , as extending it only requires reaching under the topmost handler closure. Environments, $\gamma$ , can be realised using a map, with a time complexity of ${{{{{{\mathcal{O}}}}}}}(\log|\gamma|)$ for extension and lookup (Okasaki, Reference Okasaki1999). We can use the same technique to realise label lookup, $H^{\ell}$ , with time complexity ${{{{{{\mathcal{O}}}}}}}(\log|\Sigma|)$ . However, in Section 5.4, we shall work only with a single effect operation, so $|\Sigma| = 1$ , meaning that in our analysis we can practically treat label lookup as being a constant time operation.

The worst-case time complexity of a single machine transition is exhibited by rules which involves the value translation function, $[\![ - ]\!] \gamma$ , as it is defined structurally on values. Its worst-time complexity is exhibited by a nesting of pairs of variables $[\![ {{{{{{\langle x_1,{{{{{{\langle x_2,\cdots,{{{{{{\langle x_{n-1},x_n \rangle}}}}}}\cdots \rangle}}}}}} \rangle}}}}}} ]\!] \gamma$ which has complexity ${{{{{{\mathcal{O}}}}}}}(n\log|\gamma|)$ .

Continuation copying. On the handler machine the topmost continuation frame can be copied in constant time due to the persistent runtime and the layout of machine continuations. An alternative design would be to make the runtime non-persistent in which case copying a continuation frame $((\sigma, \chi) {{{{{{::}}}}}} \_)$ would be a ${{{{{{\mathcal{O}}}}}}}(|\sigma| + |\chi|)$ time operation, where $|\chi|$ is the size of the handler closure $\chi$ .

Primitive operations on naturals. Our model assumes that arithmetic operations on arbitrary natural numbers take ${{{{{{\mathcal{O}}}}}}}(1)$ time. This is common practice in the study of algorithms when the main interest lies elsewhere (Cormen et al., Reference Cormen, Leiserson, Rivest and Stein2009, Section 2.2). If desired, one could adopt a more refined cost model that accounted for the bit-level complexity of arithmetic operations; however, doing so would have the same impact on both of the situations we are wishing to compare, and thus would add nothing but noise to the overall analysis.

5.1 Examples of points, predicates and trees

Consider first the following terms of type Point:

(Here $\bot$ is the diverging term $(\mathbf{rec}\; f\,i.f\,i)\,{\langle \rangle}$ .) Then $\mathrm{q}_0$ represents $\langle{\mathrm{true},\dots,\mathrm{true}}\rangle \in {{{{{{\mathbb{B}}}}}}}^n$ for any n; $\mathrm{q}_1$ represents $\langle{\mathrm{true},\mathrm{false},\dots,\mathrm{false}}\rangle \in {{{{{{\mathbb{B}}}}}}}^n$ for any $n \geq 1$ ; and $\mathrm{q}_2$ represents $\langle{\mathrm{true},\mathrm{false}}\rangle \in {{{{{{\mathbb{B}}}}}}}^2$ .

Next some predicates. First, the following terms all represent the constant true predicate ${{{{{{\mathbb{B}}}}}}}^2 \to {{{{{{\mathbb{B}}}}}}}$ :

These illustrate that in the course of evaluating a predicate term P at a point q, for each $i<n$ the value of q at i may be inspected zero, one or many times.

Likewise, the following all represent the ‘identity’ predicate ${{{{{{\mathbb{B}}}}}}}^1 \to {{{{{{\mathbb{B}}}}}}}$ , in a sense to be made precise below (here $\&\&$ is shortcut ‘and’):

Slightly more interestingly, for each n we have the following program which determines whether a point contains an odd number of true components:

\[ \mathrm{Odd}_n \mathrel{\overset{{\mbox{def}}}{=}} \lambda q.\, \mathrm{fold}\otimes\mathrm{false}~(\mathrm{map}~q~[0,\dots,n-1])\]

Here fold and map are the standard combinators on lists, and $\otimes$ is exclusive-or. Applying $\mathrm{Odd}_2$ to $\mathrm{q}_0$ yields false; applying it to $\mathrm{q}_1$ or $\mathrm{q}_2$ yields true.

We can think of a predicate term P as participating in a ‘dialogue’ with a given point $Q : \mathrm{Point}_n$ . The predicate may query Q at some coordinate k; Q may respond with true or false and this returned value may influence the future course of the dialogue. After zero or more such query/response pairs, the predicate may return a final answer (true or false).

The set of possible dialogues with a given term P may be organised in an obvious way into an unrooted binary decision tree, in which each internal node is labelled with a query $\mathord{?} k$ (with $k<n$ ), and with left and right branches corresponding to the responses true, false respectively. Any point will thus determine a path through the tree, and each leaf is labelled with an answer $\mathord{!} \mathrm{true}$ or $\mathord{!} \mathrm{false}$ according to whether the corresponding point or points satisfy the predicate.

Decision trees for a sample of the above predicate terms are depicted in Figure 6; the relevant formal definitions are given in the next subsection. In the case of $\mathrm{I}_2$ , one of the $\mathord{!} \mathrm{false}$ leaves will be ‘unreachable’ if we are working in ${\lambda_{\textrm{b}}}$ (but reachable in a language supporting mutable state).

Fig. 6. Examples of decision trees.

We think of the edges in the tree as corresponding to portions of computation undertaken by P between queries, or before delivering the final answer. The tree is unrooted (i.e. starts with an edge rather than a node) because in the evaluation of $P\,Q$ there is potentially some ‘thinking’ done by P even before the first query or answer is reached. For the purpose of our runtime analysis, we will also consider timed variants of these decision trees, in which each edge is labelled with the number of computation steps involved.

It is possible that for a given P, the construction of a decision tree may hit trouble, because at some stage P either goes undefined or gets stuck at an unhandled operation. It is also possible that the decision tree is infinite because P can keep asking queries forever. However, we shall be restricting our attention to terms representing total predicates: those with finite decision trees in which every path leads to a leaf.

In order to present our complexity results in a simple and clear form, we will give special prominence to certain well-behaved decision trees. For $n \in {{{{{{\mathbb{N}}}}}}}$ , we shall say a tree is n-standard if it is total (i.e. every maximal path leads to a leaf labelled with an answer) and along any path to a leaf, each coordinate $k<n$ is queried once and only once. Thus, an n-standard decision tree is a complete binary tree of depth $n+1$ , with $2^n - 1$ internal nodes and $2^n$ leaves. However, there is no constraint on the order of the queries, which indeed may vary from one path to another. One pleasing property of this notion is that for a predicate term with an n-standard decision tree, the number of points in ${{{{{{\mathbb{B}}}}}}}^n$ satisfying the predicate is precisely the number of $\mathord{!} \mathrm{true}$ leaves in the tree.

Of the examples we have given, the tree for $\mathrm{T}_0$ is 0-standard; those for $\mathrm{I}_0$ and $\mathrm{I}_1$ are 1-standard; that for $\mathrm{Odd}_n$ is n-standard; and the rest are not n-standard for any n.

5.2 Formal definitions

We now formalise the above notions. We will present our definitions in the setting of ${\lambda_{\textrm{h}}}$ , but everything can clearly be relativised to ${\lambda_{\textrm{b}}}$ with no change to the meaning in the case of ${\lambda_{\textrm{b}}}$ terms. For the purpose of this subsection, we fix $n \in {{{{{{\mathbb{N}}}}}}}$ , set ${{{{{{\mathbb{N}}}}}}}_n \mathrel{\overset{{\mbox{def}}}{=}} \{0,\ldots,n-1\}$ , and use k to range over ${{{{{{\mathbb{N}}}}}}}_n$ . We write ${{{{{{\mathbb{B}}}}}}}$ for the set of booleans, which we shall identify with the (encoded) boolean values of ${\lambda_{\textrm{h}}}$ , and use b to range over ${{{{{{\mathbb{B}}}}}}}$ .

As suggested by the foregoing discussion, we will need to work with both syntax and semantics. For points, the relevant definitions are as follows.

Definition 2 (points). A closed value $Q : \mathrm{Point}$ is said to be a syntactic n-point if:

\[ \forall k \in {{{{{{\mathbb{N}}}}}}}_n.\,\exists b \in {{{{{{\mathbb{B}}}}}}}.~ Q~k {{{{{{\leadsto}}}}}}^\ast \mathbf{return}\;b \]

A semantic n-point $\pi$ is simply a mathematical function $\pi: {{{{{{\mathbb{N}}}}}}}_n \to {{{{{{\mathbb{B}}}}}}}$ . (We shall also write $\pi \in {{{{{{\mathbb{B}}}}}}}^n$ .) Any syntactic n-point Q is said to denote the semantic n-point $[\![ Q ]\!] $ given by

\[ \forall k \in {{{{{{\mathbb{N}}}}}}}_n,\, b \in {{{{{{\mathbb{B}}}}}}}.~ [\![ Q ]\!] (k) = b \,\Leftrightarrow\, Q~k {{{{{{\leadsto}}}}}}^\ast \mathbf{return}\;b \]

Any two syntactic n-points Q and Q’ are said to be distinct if $[\![ Q ]\!] \neq [\![ Q' ]\!] $ .

By default, the unqualified term n-point will from now on refer to syntactic n-points.

Likewise, we wish to work with predicates both syntactically and semantically. By a semantic n-predicate, we shall mean simply a mathematical function $\Pi: {{{{{{\mathbb{B}}}}}}}^n \to {{{{{{\mathbb{B}}}}}}}$ . One slick way to define syntactic n-predicates would be as closed terms $P:\mathrm{Predicate}$ such that for every n-point Q, $P\,Q$ evaluates to either $\mathbf{return}\;\mathrm{true}$ or $\mathbf{return}\;\mathrm{false}$ . For our purposes, however, we shall favour an approach to n-predicates via decision trees, which will yield more information on their behaviour.

We will model decision trees as certain partial functions from addresses to labels. An address will specify the position of a node in the tree via the path that leads to it, while a label will represent the information present at a node. Formally:

1. (i) The address set $\mathsf{Addr}$ is simply the set ${{{{{{\mathbb{B}}}}}}}^\ast$ of finite lists of booleans. If $bs,bs' \in \mathsf{Addr}$ , we write $bs \sqsubseteq bs'$ (resp. $bs \sqsubset bs'$ ) to mean that bs is a prefix (resp. proper prefix) of bs’.

2. (ii) The label set $\mathsf{Lab}$ consists of queries parameterised by a natural number and answers parameterised by a boolean:

   \[ \mathsf{Lab} \mathrel{\overset{{\mbox{def}}}{=}} \{\mathord{?} k \mid k \in {{{{{{\mathbb{N}}}}}}} \} \cup \{\mathord{!} b \mid b \in {{{{{{\mathbb{B}}}}}}} \} \]

3. (iii) An (untimed) decision tree is a partial function $\tau : \mathsf{Addr}\rightharpoonup \mathsf{Lab}$ such that:

   • The domain of $\tau$ (written $dom(\tau)$ ) is prefix closed.

   • Answer nodes are always leaves: if $\tau(bs) = \mathord{!} b$ then $\tau(bs')$ is undefined whenever $bs \sqsubset bs'$ .

As our goal is to reason about the time complexity of generic count programs and their predicates, it is also helpful to decorate decision trees with timing data that records the number of machine steps taken for each piece of computation performed by a predicate:

Here we think of $\mathsf{steps}(\tau)(bs)$ as the computation time associated with the edge whose target is the node addressed by bs.

We now come to the method for associating a specific tree with a given term P. One may think of this as a kind of denotational semantics, but here we shall extract a tree from a term by purely operational means using our abstract machine model. The key idea is to try applying P to a distinguished free variable $q: \mathrm{Point}$ , which we think of as an ‘abstract point’. Whenever P wants to interrogate its argument at some index i, the computation will get stuck at some term $q\,i$ : this both flags up the presence of a query node in the decision tree, and allows us to explore the subsequent behaviour under both possible responses to this query.

Our definition captures this idea using abstract machine configurations. We write ${\mathrm{Conf}}_q$ for the set of $\lambda_h$ configurations possibly involving q (but no other free variables). We write $a \simeq b$ for Kleene equality: either both a and b are undefined or both are defined and $a = b$ .

It is convenient to define the timed tree and then extract the untimed one from it:

If the execution of a configuration $\mathcal{C}$ runs forever or gets stuck at an unhandled operation, then $\mathcal{T}(\mathcal{C})(bs)$ will be undefined for all bs. Although this is admitted by our definition of decision tree, we wish to exclude such behaviours for the terms we accept as valid predicates. Specifically, we frame the following definition:

• For every query $\mathord{?} k$ appearing in $\tau$ , we have $k \in {{{{{{\mathbb{N}}}}}}}_n$ .

• Every query node has both children present:

  \[ \forall bs \in \mathsf{Addr},\, k \in {{{{{{\mathbb{N}}}}}}}_n,\, b \in {{{{{{\mathbb{B}}}}}}}.~ \tau(bs) = \mathord{?} k \Rightarrow {{{{{{bs \mathbin{+\!\!+} [b]}}}}}} \in dom(\tau) \]

• All paths in $\tau$ are finite (so every maximal path terminates in an answer node).

A closed term $P: \mathrm{Predicate}$ is a (syntactic) n-predicate if $\mathcal{U}(P)$ is an n-predicate tree.

If $\tau$ is an n-predicate tree, clearly any semantic n-point $\pi$ gives rise to a path $b_0 b_1 \dots $ through $\tau$ , given inductively by

\[ \forall j.~ \mbox{if~} \tau(b_0\dots b_{j-1}) = \mathord{?} k_j \mbox{~then~} b_j = \pi(k_j) \]

This path will terminate at some answer node $b_0 b_1 \dots b_{r-1}$ of $\tau$ , and we may write $\tau \bullet \pi \in {{{{{{\mathbb{B}}}}}}}$ for the answer at this leaf.

Proof By interleaving the computation for the relevant path through $\mathcal{U}(P)$ with computations for queries to Q, and appealing to the correspondence between the small-step reduction and abstract machine semantics. We omit the routine details.

It is thus natural to define the denotation of an n-predicate P to be the semantic n-predicate $[\![ P ]\!] $ given by $[\![ P ]\!] (\pi) = \mathcal{U}(P) \bullet \pi$ .

As mentioned earlier, we shall also be interested in a more constrained class of trees and predicates:

• The domain of $\tau$ is precisely $\mathsf{Addr}_n$ , the set of bit vectors of length $\leq n$ .

• There are no repeated queries along any path in $\tau$ :

  \[ \forall bs, bs' \in dom(\tau),\, k \in {{{{{{\mathbb{N}}}}}}}_n.~ bs \sqsubseteq bs' \wedge \tau(bs)=\tau(bs')=\mathord{?} k \Rightarrow bs=bs' \]

A timed decision tree $\tau$ is n-standard if its underlying untimed decision tree $\mathsf{labs}(\tau)$ is too. An n-predicate P is n-standard if $\mathcal{U}(P)$ is n-standard.

Clearly, in an n-standard tree, each of the n queries $\mathord{?} 0,\dots, \mathord{?}(n-1)$ appears exactly once on the path to any leaf, and there are $2^n$ leaves, all of them answer nodes.

It is also clear how for any n-standard tree $\tau$ we may construct a predicate P that denotes it, simply by mirroring the structure of $\tau$ with nested $\mathbf{if}$ expressions:

We then define

\[ P(\tau) ~=~ \lambda q.\; T_q(\tau,[]) \]

(so that clearly $\mathcal{U}(P(\tau)) = \tau$ ), and call $P(\tau)$ the canonical n-standard predicate for $\tau$ .

In practice, we will omit the subscript q from uses of T.

Note that the use of lists here is entirely at the meta-level, and none of the terms $T(\tau,bs)$ themselves involve list data. Because of their simple, standardised form, canonical n-standard predicates will play a useful role in our lower bound analysis in Section 8.

5.3 Specification of counting programs

We can now specify what it means for a program $K : \mathrm{Predicate} \to \mathrm{Nat}$ to implement counting.

This definition gives us the flexibility to talk about counting programs that operate on various classes of predicates, allowing us to state our results in their strongest natural form. On the positive side, we shall shortly see that there is a single ‘efficient’ program in ${\lambda_{\textrm{h}}}$ that correctly counts all n-standard $\lambda_h$ predicates for every n; in Section 6.1 we improve this to one that correctly counts all n-predicates of $\lambda_h$ . On the negative side, we shall show that an n-indexed family of counting programs written in ${\lambda_{\textrm{b}}}$ , even if only required to work correctly on canonical n-standard $\lambda_b$ predicates, can never compete with our ${\lambda_{\textrm{h}}}$ program for asymptotic efficiency even in the most favourable cases.

5.4 Efficient generic count with effects

We now present the simplest version of our effectful implementation of counting: one that works on n-standard predicates.

Our program uses a variation of the handler for nondeterministic computation that we gave in Section 2. The main idea is to implement points as ‘nondeterministic computations’ using the Branch operation such that the handler may respond to every query twice, by invoking the provided resumption with true and subsequently false. The key insight is that the resumption restarts computation at the invocation site of Branch, meaning that prior computation performed by the predicate need not be repeated. In other words, the resumption ensures that common portions of computations prior to any query are shared between both branches.

We assert that $\mathrm{Branch} : \mathrm{Unit} \to \mathrm{Bool} \in \Sigma$ is a distinguished operation that may not be handled in the definition of any input predicate (it has to be forwarded according to the default convention). The algorithm is then as follows.

The handler applies predicate pred to a single ‘generic point’ defined using Branch. The boolean return value is interpreted as a single solution, whilst Branch is interpreted by alternately supplying true and false to the resumption and summing the results. The sharing enabled by the use of the resumption is exactly the ‘magic’ we need to make it possible to implement generic count more efficiently in ${\lambda_{\textrm{h}}}$ than in ${\lambda_{\textrm{b}}}$ . A curious feature of effcount is that it works for all n-standard predicates without having to know the value of n.

We may now articulate the crucial correctness and efficiency properties of effcount.

1. 1. effcount correctly counts P.

2. 2. The number of machine steps required to evaluate $\mathrm{effcount}~P$ is

   \[ \left( \displaystyle\sum_{bs \in \mathsf{Addr}_n} \mathsf{steps}(\mathcal{T}(P))(bs) \right) ~+~ {{{{{{\mathcal{O}}}}}}}(2^n) \]

Proof [Outline.] Suppose $bs \in \mathsf{Addr}_n$ , with length j. From the construction of $\mathcal{T}(P)$ , one may easily read off a configuration $\mathcal{C}_{bs}$ whose execution is expected to compute the count for the subtree below node bs, and we can explicitly describe the form $\mathcal{C}_{bs}$ will have. We write $\mathrm{Hyp}(bs)$ for the claim that $\mathcal{C}_{bs}$ correctly counts this subtree and does so within the following number of steps:

\[ \left( \displaystyle\sum_{bs' \in \mathsf{Addr}_n,\; bs' \sqsupset bs} \mathsf{steps}(\mathcal{T}(P))(bs') \right) ~+~ 9 * (2^{n-j} - 1) + 2*2^{n-j} \]

The $9*(2^{n-j}-1)$ expression is the number of machine steps contributed by the Branch-case inside the handler, whilst the $2*2^{n-j}$ expression is the number of machine steps contributed by the $\mathbf{val}$ -case. We prove $\mathrm{Hyp}(bs)$ by a laborious but entirely routine downwards induction on the length of bs. The proof combines counting of explicit machine steps with ‘oracular’ appeals to the assumed behaviour of P as modelled by $\mathcal{T}(P)$ . Once $\mathrm{Hyp}({{{{{{[]}}}}}})$ is established, both halves of the theorem follow easily. Full details are given in Appendix C of Hillerström et al. (Reference Hillerström, Lindley and Longley2020).

The above formula can clearly be simplified for certain reasonable classes of predicates. For instance, suppose we fix some constant $c \in {{{{{{\mathbb{N}}}}}}}$ , and let $\mathcal{P}_{n,c}$ be the class of all n-standard predicates P for which all the edge times $\mathsf{steps}(\mathcal{T}(P))(bs)$ are bounded by c. (Many reasonable predicates will belong to $\mathcal{P}_{n,c}$ for some modest value of c: for instance, the membership test for some regular language $\mathcal{L} \subseteq \{0,1\}^*$ , or even for many languages defined by deterministic pushdown automata if cons-lists be added to our language.) Since the number of sequences bs in question is less than $2^{n+1}$ , we may read off from the above formula that for predicates in $\mathcal{P}_{n,c}$ , the runtime of effcount is ${{{{{{\mathcal{O}}}}}}}(c2^n)$ .

Alternatively, should we wish to use the finer-grained cost model that assigns an $O(\log |\gamma|)$ runtime to each abstract machine step (see Section 4.3), we may note that any environment $\gamma$ arising in the computation contains at most n entries introduced by the let-bindings in effcount, and (if $P \in\mathcal{P}_{n,c}$ ) at most ${{{{{{\mathcal{O}}}}}}}(cn)$ entries introduced by P. Thus, the time for each step in the computation remains ${{{{{{\mathcal{O}}}}}}}(\log c+ \log n)$ , and the total runtime for effcount is ${{{{{{\mathcal{O}}}}}}}(c 2^n (\log c + \log n))$ .

One might also ask about the execution time for an implementation of ${\lambda_{\textrm{h}}}$ that performs genuine copying of continuations, as in systems such as MLton (2020). As MLton copies the entire continuation (stack), whose size is ${{{{{{\mathcal{O}}}}}}}(n)$ , at each of the $2^n$ branches, continuation copying alone takes time ${{{{{{\mathcal{O}}}}}}}(n2^n)$ and the effectful implementation offers no performance benefit. More refined implementations (Farvardin & Reppy, Reference Farvardin and Reppy2020; Flatt & Dybvig, Reference Flatt and Dybvig2020) that are able to take advantage of delimited control operators or sharing in copies of the stack can bring the complexity of continuation copying back down to ${{{{{{\mathcal{O}}}}}}}(2^n)$ .

Finally, one might consider another dimension of cost, namely, the space used by effcount. Consider a class $\mathcal{Q}_{n,c,d}$ of n-standard predicates P for which the edge times in $\mathcal{T}(P)$ never exceed c and the sizes of pure continuations never exceed d. If we consider any $P \in \mathcal{Q}_{n,c,d}$ then the total number of environment entries is bounded by cn, taking up space ${{{{{{\mathcal{O}}}}}}}(cn(\log cn))$ . We must also account for the pure continuations. There are n of these, each taking at most d space. Thus, the total space is ${{{{{{\mathcal{O}}}}}}}(n(d + c(\log c + \log n)))$ .

6.1 Beyond n-standard predicates

The n-standardness restriction on predicates serves to make the efficiency phenomenon stand out as clearly as possible. However, we can relax the restriction by tweaking effcount to handle repeated queries and missing queries. The trade-off is that the analysis of effcount becomes more involved. The key to relaxing the n-standardness restriction is the use of state to keep track of which queries have been computed. We can give stateful implementations of effcount without changing its type signature by using parameter-passing (Kammar et al., Reference Kammar, Lindley and Oury2013; Pretnar, Reference Pretnar2015) to internalise state within a handler. Parameter-passing abstracts every handler clause such that the current state is supplied before the evaluation of a clause continues and the state is threaded through resumptions: a resumption becomes a two-argument curried function $r : B \to S \to D$ , where the first argument of type B is the return type of the operation and the second argument is the updated state of type S.

Repeated queries. We can generalise effcount to handle repeated queries by memoising previous answers. First, we generalise the type of Branch to carry an index of a query.

\[ \mathrm{Branch} : \mathrm{Nat} \to \mathrm{Bool}\]

For fixed n, we assume a type of natural number to boolean maps, $\mathrm{Map}_n$ , with the following interface.

Invoking $\mathrm{lookup}~i~map$ returns $\mathbf{inl}~{\langle \rangle}$ if i is not present in map, and $\mathbf{inr}~ans$ if i is associated by map with the value $ans : \mathrm{Bool}$ . Allowing ourselves a few extra constant-time arithmetic operations, we can realise suitable maps in ${\lambda_{\textrm{b}}}$ such that the time complexity of $\mathrm{add}_n$ and $\mathrm{lookup}_n$ is ${{{{{{\mathcal{O}}}}}}}(\log n)$ (Okasaki, Reference Okasaki1999). We can then use parameter-passing to support repeated queries as follows.

The state parameter s memoises query results, thus avoiding double-counting and enabling $\mathrm{effcount}'_n$ to work correctly for predicates performing the same query multiple times.

Missing queries. Similarly, we can use parameter-passing to support missing queries.

The parameter d tracks the depth and the returned result is scaled by $2^{n-d}$ accounting for the unexplored part of the current subtree. This enables $\mathrm{effcount}''_n$ to operate correctly on predicates that inspect n points at most once. We leave it as an exercise for the reader to combine $\mathrm{effcount}'_n$ and $\mathrm{effcount}''_n$ to handle both repeated queries and missing queries.

6.2 From generic count to generic search

We can generalise the problem of generic counting to generic searching. The key difference is that a generic search procedure must materialise a list of solutions, thus its type is

\[ \mathrm{search}_{n} : ((\mathrm{Nat}_n \to \mathrm{Bool}) \to \mathrm{Bool}) \to \mathrm{List}_{\mathrm{Nat}_n \to \mathrm{Bool}}\]

where $\mathrm{List}_A$ is the type of cons-lists whose elements have type A. We modify effcount to return a list of solutions rather than the number of solutions by lifting each result into a singleton list and using list concatenation instead of addition to combine partial results $xs_\mathrm{true}$ and $xs_\mathrm{false}$ as follows.

The Branch operation is now parameterised by an index i. The handler is now parameterised by the current path as a point q, which is output at a leaf if it is in the predicate. A little care is required to ensure that $\text{effSearch}_\textit{n}$ has runtime ${{{{{{\mathcal{O}}}}}}}(2^n)$ ; naïve use of cons-list concatenation would result in ${{{{{{\mathcal{O}}}}}}}(n2^n)$ runtime, as cons-list concatenation is linear in its first operand. In place of cons-lists, we use Hughes lists (Hughes, Reference Hughes1986), which admit constant time concatenation: $\text{HList}_A \mathrel{\overset{{\mbox{def}}}{=}} \mathrm{List}_A \to \mathrm{List}_A$ . The empty Hughes list $\mathrm{nil} : \text{HList}_A$ is defined as the identity function: $\mathrm{nil} \mathrel{\overset{{\mbox{def}}}{=}} \lambda xs. xs$ .

We use the function $\text{toConsList}$ to convert the final Hughes list to a standard cons-list. This conversion has linear time complexity (it just conses all of the elements of the list together).

6.3 Type-and-effect system

Many practical implementations of effect handlers come equipped with rich type systems that track which effectful operations any function may perform (Bauer & Pretnar, Reference Bauer and Pretnar2014; Hillerström & Lindley, Reference Hillerström and Lindley2016; Leijen, Reference Leijen2017; Biernacki et al., Reference Biernacki, Piróg, Polesiuk and Sieczkowski2019; Brachthäuser et al., Reference Brachthäuser, Schuster and Ostermann2020). One may wonder whether our result transfers to such a system as we make crucial use of the ability to inject an effectful operation into a computation, which a first glance might seem to require a change of (effect) types.

However, as we shall briefly outline, with sufficient polymorphism we need not change the effect types. Our generic count program does not perform any externally visible effects. Therefore, if we equip our simple type system with some form of rank-2 effect polymorphism, then we do not morally require a change of types even in the presence of the richer types provided by effect tracking.

Suppose we track the effects on function types, e.g. $A \to B !\varepsilon$ denotes a function that accepts a value of type A as input and produces some value of type B as output using effects $\varepsilon$ . Here $\varepsilon$ is intended to be an effect variable which may be instantiated to name concrete effectful operations that the function may perform such as $\mathrm{Branch} : \mathrm{Unit} \to \mathrm{Bool}$ . We shall not concern ourselves with a particular effect type formalism here, but rather just note that there are many approaches to realising such an effect system, e.g. using row types (Hillerström & Lindley, Reference Hillerström and Lindley2016; Leijen, Reference Leijen2017), subtyping (Bauer & Pretnar, Reference Bauer and Pretnar2014), intersection types (Brachthäuser et al., Reference Brachthäuser, Schuster and Ostermann2020), etc.

We can give a fully effect-parametric signature to generic count using rank-2 effect polymorphism.

\[ \mathrm{Count} : (\forall \varepsilon. (\mathrm{Nat} \to \mathrm{Bool} ! \varepsilon) \to \mathrm{Bool} ! \varepsilon) \to \mathrm{Nat} ! \emptyset\]

Here $\emptyset$ denotes that an application of Count does not perform any externally visible effects. The parameter type of Count is a rank-2 effect type. It effectively hides the implementation detail of the provided point from the predicate. Thus, the implementation of Count is allowed to supply a point that performs any effectful operation granted that the implementation guarantees to handle any such operation. This idea of using rank-2 polymorphism is an old idea which dates back at least to McCracken (Reference McCracken1984); it has been used in practice in Haskell as the primary means for state encapsulation since Launchbury & Jones (Reference Launchbury and Jones1994).

7.1 Naïve count

The naïve approach, of course, is simply to apply the given predicate P to all $2^n$ possible n-points in turn, keeping a count of those on which P yields true. Of course, this approach could be readily implemented in ${\lambda_{\textrm{b}}}$ ; but it is also clear how it could be effected in an even weaker language, in which the recursion construct of ${\lambda_{\textrm{b}}}$ is replaced by a weaker iteration construct. (For a comparison of the power of iteration and recursion, see Longley, Reference Longley2019.) For instance, the following operator (definable in ${\lambda_{\textrm{b}}}$ ) allows one to achieve the effect of while-loops manipulating data of type A:

Let us write ${{{{{{\lambda_{\textrm{i}}}}}}}}$ for the sublanguage of ${\lambda_{\textrm{b}}}$ allowing $\mathrm{while}_A$ for each type A, but disallowing all uses of $\mathbf{rec}$ elsewhere. Then it is a straightforward coding exercise to write a ${{{{{{\lambda_{\textrm{i}}}}}}}}$ program

\[ {\mathrm{naivecount}}_n ~: ((\mathrm{Nat}_n \to \mathrm{Bool}) \to \mathrm{Bool}) \to \mathrm{Nat} \]

that implements generic counting using the naïve strategy.

The evaluation of an n-standard predicate on an individual n-point must clearly take time $\Omega(n)$ . It is therefore clear that in whatever way the naïve count strategy is implemented, the runtime on any n-standard predicate P must be $\Omega(n2^n)$ . If P is not n-standard, the $\Omega(n)$ bound on each point application need not apply, but we may still say that a naïve count for any predicate P (at level n) must take time $\Omega(2^n)$ .

One might at first suppose that these properties are inevitable for any implementation of generic count within ${\lambda_{\textrm{b}}}$ , or indeed any purely functional language: surely, the only way to learn something about the behaviour of P on every possible n-point is to apply P to each of these points in turn? It turns out, however, that the $\Omega(2^n)$ lower bound can sometimes be circumvented by implementations that cleverly exploit nesting of calls to P. In the next section, we illustrate the germ of this idea, and in Section 7.3, we show how it gives rise to a practically superior counting program within ${\lambda_{\textrm{b}}}$ .

7.2 The nesting trick

The germ of the idea may be illustrated even within ${{{{{{\lambda_{\textrm{i}}}}}}}}$ . Suppose that we first construct some program

\[ {\mathrm{bestshot}}_n ~: ((\mathrm{Nat}_n \to \mathrm{Bool}) \to \mathrm{Bool}) \to (\mathrm{Nat}_n \to \mathrm{Bool})\]

which, given a predicate P, returns some n-point Q such that $P~Q$ evaluates to true, if such a point exists, and any point at all if no such point exists. (In other words, ${\mathrm{bestshot}}_n$ embodies Hilbert’s choice operator $\varepsilon$ on predicates.) It is once again routine to construct such a program by naïve means, and we may moreover assume that for any P, the evaluation of ${\mathrm{bestshot}}_n\;P$ takes only constant time, all the real work being deferred until the argument of type $\mathrm{Nat}_n$ is supplied.

Now consider the following program:

Here the term $pred~({\mathrm{bestshot}}_n~pred)$ serves to test whether there exists an n-point satisfying pred: if there is not, our count program may return 0 straightaway. It is thus clear that ${\mathrm{lazycount}}_n$ is a correct implementation of generic count, and also that if pred is the predicate $\lambda q.\mathrm{false}$ then ${\mathrm{lazycount}}_n\;pred$ returns 0 within ${{{{{{\mathcal{O}}}}}}}(1)$ time, thus violating the $\Omega(2^n)$ lower bound suggested above.

This might seem like a footling point, as ${\mathrm{lazycount}}_n$ offers this efficiency gain only on (certain implementations of) the constantly false predicate. However, it turns out that by a recursive application of this nesting trick, we may arrive at a generic count program in ${\lambda_{\textrm{b}}}$ that spectacularly defies the $\Omega(2^n)$ lower bound for an interesting class of (non-n-standard) predicates, and indeed proves quite viable for counting solutions to ‘n-queens’ and similar problems. In contrast to the naïve strategy, however, this approach relies crucially on the use of recursion and cannot be implemented in a language such as ${{{{{{\lambda_{\textrm{i}}}}}}}}$ with mere iteration.

We shall refer to this ${\lambda_{\textrm{b}}}$ program as ${\mathrm{Bergercount}}$ , as it is modelled largely on Berger’s PCF implementation of the so-called fan functional (Berger, Reference Berger1990; Longley & Normann, Reference Longley and Normann2015). We give an implementation of ${\mathrm{Bergercount}}$ in the next section.

7.3 Berger count

Berger’s original program (Berger, Reference Berger1990) introduced a remarkable search operator for predicates on infinite streams of booleans and has played an important role in higher-order computability theory (Longley & Normann, Reference Longley and Normann2015). What we wish to highlight here is that if one applies the algorithm to predicates on finite boolean vectors, the resulting program, though no longer interesting from a computability perspective, still holds some interest from a complexity standpoint: indeed, it yields what seems to be the best known implementation of generic count within a PCF-style ‘functional’ language (provided one accepts the use of a primitive for call-by-need evaluation).

We give the gist of an adaptation of Berger’s search algorithm on finite spaces. The key ingredient of Berger’s search algorithm is the ${\mathrm{bestshot}}_n$ function, which given any n-standard predicate P returns a point satisfying P if one exists, or the dummy point $\lambda i.\mathrm{false}$ if not. Figure 7 depicts the implementation of this function. It is implemented by via two mutually recursive auxiliary functions whose workings are admittedly hard to elucidate in a few words. The function ${\mathrm{bestshot}}'_n$ is a generalisation of ${\mathrm{bestshot}}_n$ that makes a best shot at finding a point $\pi$ satisfying given predicate and matching some specified list start in some initial segment of its components $[\pi(0),\dots,\pi(i-1)]$ . Here we use two customary operations on lists: we write $|-|$ for the list length function and nth for the function which projects the nth element of a list. The ${\mathrm{bestshot}}'_n$ function works ‘lazily’, drawing its values from start wherever possible, and performing an actual search only when required. This actual search is undertaken by ${\mathrm{bestshot}}''_n$ , which proceeds by first searching for a solution that extends the specified list with true (using the standard list append function); but if no such solution is forthcoming, it settles for false as the next component of the point being constructed. The whole procedure relies on a subtle combination of laziness, recursion and implicit nesting of calls to the provided predicate which means that the search is self-pruning in regions of the binary tree where the predicate only demands some initial segment $q~0$ , $q~(i-1)$ of its argument q.

Fig. 7. An implementation of ${\mathrm{bestshot}}$ in ${\lambda_{\textrm{b}}}$ with memoisation.

The above program makes use of an operation

\[ \mathrm{memoise} : (\mathrm{Unit} \to \mathrm{List}~\mathrm{Bool}) \to (\mathrm{Unit} \to \mathrm{List}~\mathrm{Bool})\]

which transforms a given thunk into an equivalent ‘memoised’ version, i.e. one that caches its value after its first invocation and immediately returns this value on all subsequent invocations. Such an operation may readily be implemented with the help of local state, or alternatively may simply be added as a primitive in its own right. The latter has the advantage that it preserves the purely ‘functional’ character of the language, in the sense that every program is observationally equivalent to a ${\lambda_{\textrm{b}}}$ program, namely the one obtained by replacing memoise by the identity.

Figure 8 depicts an implementation that exploits the above idea to yield a generic count program (this development appears to be new). Again, ${\mathrm{Bergercount}}_n$ is implemented by means of two mutually recursive auxiliary functions. The function $\mathrm{count}'_n$ counts the solutions to the provided predicate pred that start with the specified list of booleans, adding their number to a previously accumulated total given by acc. The function $\mathrm{count}''_n$ does the same thing, but exploiting the knowledge that a best shot at the ‘leftmost’ solution to P within this subtree has already been computed. (We are visualising n-points as forming a binary tree with true to the left of false at each fork.) Thus, $\mathrm{count}''_n$ will not re-examine the portion of the subtree to the left of this candidate solution, but rather will start at this solution and work rightward.

Fig. 8. An implementation of Berger count in ${\lambda_{\textrm{b}}}$ .

This gives rise to an n-count program that can work efficiently on predicates that tend to ‘fail fast’: more specifically, predicates P that inspect the components of their argument q in order $q~0$ , $q~1$ , $q~2$ , and which are frequently able to return false after inspecting just a small number of these components. Generalising our program from binary to k-ary branching trees, we see that the n-queens problem provides a typical example: most points in the space can be seen not to be solutions by inspecting just the first few components. Our experimental results in Section 11 attest to the viability of this approach and its overwhelming superiority over the naïve functional method.

By contrast, the above program is not able to exploit parts of the tree where our predicate ‘succeeds fast’, i.e. returns true after seeing just a few components. Unlike the effectful count program of Section 5.4, which may sometimes add $2^{n-d}$ to the count in a single step, the Berger approach can only count solutions one at a time. Thus, for an n-standard predicate P, the evaluation of ${\mathrm{Bergercount}}_n~P$ that returns a natural number k must take time $\Omega(k)$ .

7.4 Pruned count

To do better than ${\mathrm{Bergercount}}$ , it seems that we must ascend to a more powerful language. We now briefly outline another approach, using ideas from Longley (Reference Longley1999), which yields a more efficient form of pruned search in an extension of $\lambda_b$ with local state of ground type. Since local state can certainly be encoded using affine effect handlers with no essential loss of efficiency, this approach falls within the ambit of what can be achieved within the language ${{{{{{\lambda_{\textrm{a}}}}}}}}$ to be introduced in Section 9.

The key idea is that each time we apply a predicate to a point, we may use local state to detect which components of the point are actually inspected by the predicate. We do this using a third-order function Modulus, which encloses the point in a wrapper that logs all calls to the point, then passes this wrapped point to the predicate:

This is somewhat different from the modulus functional considered in Longley (Reference Longley1999), which returns a sorted list of the arguments to which the point is applied. The latter has the theoretically pleasant consequence that the modulus is an example of a sequentially realisable functional – its externally observable behaviour is purely functional (i.e. extensional) although the function it implements cannot be realised in pure $\lambda_b$ . However, this property is purchased at the cost of the extra work needed to return a sorted list and is of little relevance to our present concerns.

The essential point is that if $\mathrm{Modulus}~pred~point$ returns ${{{{{{\langle b,ilist \rangle}}}}}}$ , then we know immediately that $pred~point'$ would also return the value b for every point’ that agrees with point at the components listed in ilist. This property can be used as the basis of a program

\[ {\mathrm{prunedcount}}_n ~: ((\mathrm{Nat}_n \to \mathrm{Bool}) \to \mathrm{Bool}) \to \mathrm{Nat} \]

that takes care, at each stage, to apply the predicate to some ‘new’ point at which the value is not already known on the basis of previous calls, and which then increments the accumulator by either 0 (if the predicate returns false) or the appropriate $2^{n-d}$ (if it returns true). In contrast to ${\mathrm{Bergercount}}$ , this has the effect of pruning the search space both where the predicate fails fast and where it succeeds fast.

Of course, the ability to prune in the ‘true’ case makes no difference for search problems such as n-queens, where the predicate never returns true without inspecting all components. Even for searches of this kind, however, ${\mathrm{prunedcount}}$ performs significantly better in practice than ${\mathrm{Bergercount}}$ , which achieves its pruning of ‘false’ subtrees by much more convoluted means. (The difference is clearly manifested by the experimental results reported in Section 11.) Indeed, in the absence of advanced control features, we are not aware of any approach to generic counting that essentially does better than ${\mathrm{prunedcount}}$ .

It is clear, however, that in the case of n-standard predicates, which always inspect all n components of their points, no pruning at all is possible, and neither ${\mathrm{Bergercount}}$ nor ${\mathrm{prunedcount}}$ improves on the $\Omega(n2^n)$ runtime of ${\mathrm{naivecount}}$ .

9.1 ${{{{{{\lambda_{\textrm{a}}}}}}}}$ as a dual intuitionistic-affine calculus

We present the type system of ${{{{{{\lambda_{\textrm{a}}}}}}}}$ in terms of dual-context judgements $\Delta; \Gamma \vdash \square : A$ , stating that a term $\square$ (which may be a value term V or a computation term M) has type A under intuitionistic type environment $\Delta$ and affine type environment $\Gamma$ . Informally, variables in the intuitionistic environment may be used zero, one or many times within $\square$ , while those in the affine environment may be used at most once.

As before, environments are lists assigning types to variables. For hygiene, we suppose we have disjoint lexical categories of intuitionistic and affine variables (each ranged over by metavariables x,y), and the variables within each of the environments $\Delta,\Gamma$ are required to be distinct.

The syntax of ${{{{{{\lambda_{\textrm{a}}}}}}}}$ is as follows:

The type constructors $\multimap$ , $\otimes$ , $\oplus$ , and $!$ are borrowed from linear logic. Here we informally understand Nat, Unit, $A \multimap B$ , $A \times B$ , and $A \oplus B$ as types of values that may be used at most once, and $!A$ as a type of values of type A that may be used as many times as desired. (The way DILL manifests the latter is to allow a value of $!A$ to be used at most once by binding it to an intuitionistic variable of type A which can subsequently be used as many times as desired. Thus, technically $!A$ is affine just like all other types, but it provides access to an unlimited source of identical affine values of type A.)

The typing rules those shown in Figure 9, along with Exchange, Weakening and Contraction for the intuitionistic environment, and Exchange and Weakening (but not Contraction) for the affine one. To understand the workings of this type system, it is helpful to think of the affine arrow $\multimap$ and the affine environment $\Gamma$ as playing the primary role: for instance, lambda abstraction is supported for affine variables but not intuitionistic ones. The sole purpose of the intuitionistic environment is to allow for multiple uses of values of $!$ -type: the rule TL-LetBang allows such a value to be bound to an intuitionistic variable. Note too that values of $!$ -type are formed via the TL-Bang rule, which allows a value $W : A$ to be ‘promoted’ to a reusable value $!W: !A$ if all free variables that went into the making of W are themselves reusable (we here write $!\Gamma$ to mean that every type in $\Gamma$ is of the form $!A$ for some A). Similarly, TL-BangComp allows promotion of computations. This latter form introduces some minor complications and is not strictly speaking necessary, but we include it nonetheless in order to admit a straightforward translation of let-binding in the inclusion ${{{{{{\lambda_{\textrm{b}}}}}}}}\hookrightarrow {{{{{{\lambda_{\textrm{a}}}}}}}}$ outlined at the end of this section.

Fig. 9. Typing Rules for ${{{{{{\lambda_{\textrm{a}}}}}}}}$

The crucial restrictions in the rule for handlers are that the operation argument p and the resumption variable r are now affine. Notice that the success clause may involve affine variables as it will be invoked at most once (this idea will be substantiated in Section 10 below). By contrast, the operation clauses cannot involve affine variables as they may be invoked multiple times.

There is also a small subtlety with $\mathbf{rec}$ . The function argument f is bound in the intuitionistic type environment, allowing f to be used many times within M. The operational intention is that f can be unfolded to $\lambda x.M$ as often as necessary; for this reason, it is required that M involves no affine variables other than x.

All of the above syntactic forms are shared with ${\lambda_{\textrm{h}}}$ , with the exception of $!W$ , $!M$ , and $\mathbf{let} !\;x=V\;\mathbf{in}\;N$ . To give a small-step operational semantics for ${{{{{{\lambda_{\textrm{a}}}}}}}}$ , we may therefore take all the operational rules for ${\lambda_{\textrm{h}}}$ as given in Section 3 (along with the machinery of evaluation contexts and handler contexts), together with the new rules

and additional evaluation and handler contexts for promoted computations:

As usual, we take ${{{{{{\leadsto}}}}}}^*$ to be the transitive closure of ${{{{{{\leadsto}}}}}}$ , and define the notions of ancestor and descendant in the evident way. This completes our definition of ${{{{{{\lambda_{\textrm{a}}}}}}}}$ .

The notion of normal form may now be defined just as in Definition 1. Once again, the following is straightforward to verify:

9.2 Relationship to ${\lambda_{\textrm{h}}}$ and ${\lambda_{\textrm{b}}}$

We now outline how we intend to view ${{{{{{\lambda_{\textrm{a}}}}}}}}$ as a sublanguage of ${\lambda_{\textrm{h}}}$ , and ${\lambda_{\textrm{b}}}$ as a sublanguage of ${{{{{{\lambda_{\textrm{a}}}}}}}}$ . A brief sketch will suffice here, as these translations will only play a minor role in what follows and are mentioned here mainly for the sake of orientation.

For the inclusion ${{{{{{\lambda_{\textrm{a}}}}}}}} \hookrightarrow {{{{{{\lambda_{\textrm{h}}}}}}}}$ , the broad idea is simply that any well-typed term of ${{{{{{\lambda_{\textrm{a}}}}}}}}$ will certainly remain well-typed if all affineness restrictions on variables are waived. Formally, we may define a translation that erases the intuitionistic/affine distinction completely. The translation on types may be defined by

The translation on terms is given in the obvious way for the syntactic forms common to ${{{{{{\lambda_{\textrm{a}}}}}}}}$ and ${\lambda_{\textrm{h}}}$ , the three new forms being treated by

A typing judgement $\Delta;\Gamma \vdash \square:A$ of ${{{{{{\lambda_{\textrm{a}}}}}}}}$ then becomes a judgement , where $\Delta,\Gamma$ is the result of rolling $\Delta$ and $\Gamma$ into a single environment, and is the result of applying to the types of all its variables.

Under this translation, it is easy to check that every derivable typing judgement in ${{{{{{\lambda_{\textrm{a}}}}}}}}$ yields one in ${\lambda_{\textrm{h}}}$ , and also that if $M {{{{{{\leadsto}}}}}} M'$ in ${{{{{{\lambda_{\textrm{a}}}}}}}}$ then in ${\lambda_{\textrm{h}}}$ .

For the inclusion ${{{{{{\lambda_{\textrm{b}}}}}}}} \hookrightarrow {{{{{{\lambda_{\textrm{a}}}}}}}}$ , we give a translation $(-)^\star$ inspired by the familiar Girard translation from intuitionistic types to linear ones, wrapping each subformula of a type by a ‘ $!$ ’ except for the return types of functions. The translation on types is as follows.

A type environment $\Gamma$ of ${\lambda_{\textrm{b}}}$ translated to the environment $\Gamma^\star ; \cdot$ of ${{{{{{\lambda_{\textrm{a}}}}}}}}$ : that is, all variables are treated as intuitionistic. The translation of value and computation terms therefore needs to eliminate ‘ $!$ ’ types at bindings in favour of intuitionistic variables. We give here a selection of the clauses for the translation on terms; for all syntactic forms not covered here, the translation is defined homomorphically on term structure in the obvious way.

Once again, it is routine to check that every derivable typing judgement in ${\lambda_{\textrm{b}}}$ yields one in ${{{{{{\lambda_{\textrm{a}}}}}}}}$ , and that if $M{{{{{{\leadsto}}}}}} M'$ in ${\lambda_{\textrm{b}}}$ then $M^\star {{{{{{\leadsto}}}}}}^\ast {M'}^\star$ in ${{{{{{\lambda_{\textrm{a}}}}}}}}$ .

10.1 Tracking of resumptions

To make the role of resumptions more explicit, it will be convenient to recast the small-step operational semantics for ${{{{{{\lambda_{\textrm{a}}}}}}}}$ slightly, presenting it as a reduction system for pairs ${{{{{{\langle M \mid \Xi \rangle}}}}}}$ , where M is a term and $\Xi$ is a resumption environment, mapping finitely many resumption variables $\hat{r}$ to terms of the form $\lambda y.\,\mathbf{handle} \; {{{{{{\mathcal{E}}}}}}}[\mathbf{return} \; y] \; \mathbf{with} \; H$ . Note that these terms may themselves involve other resumption variables.

The only reduction rules in which $\Xi$ plays an active role are the following. We write $\Xi \backslash \hat{r}$ for $\Xi$ with the entry for $\hat{r}$ deleted.

All other reduction rules are carried over from the original semantics in the obvious way: for each reduction rule $M {{{{{{\leadsto}}}}}} M'$ except for S-Op, we now have a rule ${{{{{{\langle M \mid \Xi \rangle}}}}}} {{{{{{\leadsto}}}}}}{{{{{{\langle M' \mid \Xi \rangle}}}}}}$ . To initiate a reduction sequence for a closed term M, we start from the configuration ${{{{{{\langle M \mid \emptyset \rangle}}}}}}$ .

The main purpose of this semantics is to make explicit the points at which resumptions are invoked (as the points at which S-Res is applied). In the original semantics, such steps appear simply as $\beta$ -reductions, which may not be distinguishable, on the face of it, from other $\beta$ -reductions that occur.

It is intuitively clear that the reduction of ${{{{{{\langle M \mid \emptyset \rangle}}}}}}$ under the new semantics proceeds in lockstep with the reduction of M under the original semantics. One half of this is formalised by the following proposition (we write ${{{{{{\leadsto}}}}}}^m$ for reduction in exactly m steps).

The converse to the above proposition — that if $M {{{{{{\leadsto}}}}}}^m M''$ then ${{{{{{\langle M \mid \emptyset \rangle}}}}}} {{{{{{\leadsto}}}}}}^m {{{{{{\langle M' \mid \Xi \rangle}}}}}}$ for some $M',\Xi$ — is not quite clear at this point, because of the worry that an application of S-Res might be blocked because the relevant $\hat{r}$ is not present in $dom\,\Xi$ , having been deleted by an earlier application of S-Res. We shall see shortly, however, that such blocking never happens, so that our two semantics do indeed work perfectly in lockstep.

Let us say a configuration ${{{{{{\langle M' \mid \Xi \rangle}}}}}}$ is naturally arising if it appears in the course of reduction of ${{{{{{\langle M \mid \emptyset \rangle}}}}}}$ for some closed M.

In the typing rules for ${{{{{{\lambda_{\textrm{a}}}}}}}}$ , the critical typing restriction is that in the handler clauses $\ell\,p\;r \mapsto N_\ell$ , the variable r is used affinely within $N_\ell$ . This does not mean that r can occur at most once within $N_\ell$ (in view of the TL-Case rule); and even if it does, the variable r may subsequently be copied in the course of a $\beta$ -reduction (again because of TL-Case). However, the affineness restriction does buy us the following crucial property:

We first claim that in this situation, $M,\Xi$ satisfy the following two conditions, writing $\hat{r}_0,\ldots,\hat{r}_{k-1}$ for the elements of $dom(\Xi)$ .

1. 1. $\hat{r}$ appears in at most one of the $k+1$ terms $M,\Xi(\hat{r}_0),\ldots,\Xi(\hat{r}_{k-1})$ .

2. 2. If N is one of these terms and $\hat{r}$ appears in N, then no two occurrences of $\hat{r}$ within N share the same set of enclosing $\mathbf{case}$ clauses. (A $\mathbf{case}$ clause is a subphrase $\mathbf{inl}\;x \mapsto P$ or $\mathbf{inr}\;y \mapsto Q$ within a $\mathbf{case}$ expression.)

Condition 1 holds because $\hat{r}$ is fresh and so does not appear in any of the $\Xi(\hat{r}_i)$ . Condition 2 is a general property of occurrences of affine variables within terms: an inspection of the typing rules shows that the TL-Case rule is the only possible source of multiple occurrences of $\hat{r}$ , and it is clear that if we know the set of enclosing $\mathbf{case}$ clauses then the occurrence is uniquely determined.

Next, we claim that Conditions 1 and 2 above are maintained as invariants by all the reduction rules of our new semantics. Since Condition 2 is a general property of affine variables, and our reduction rules are easily seen to respect the type system, the preservation of this condition is automatic, so it will suffice to show that Condition 1 is preserved. We reason by cases on the possible forms for a reduction ${{{{{{\langle M \mid \Xi \rangle}}}}}} {{{{{{\leadsto}}}}}} {{{{{{\langle M' \mid \Xi' \rangle}}}}}}$ .

• For $\text{{S-Op}}'$ (applied within some handler context ${{{{{{\mathcal{H}}}}}}}$ and introducing a fresh $\hat{r}'$ ): Suppose $\hat{r}$ appears within the relevant subterm $\mathbf{handle} \; {{{{{{\mathcal{E}}}}}}}[\mathbf{do} \; \ell \, V] \; \mathbf{with} \; H$ (the situation for occurrences of $\hat{r}$ elsewhere is straightforward). Since this subterm is in evaluation position, it is not within a $\mathbf{case}$ clause, so by Conditions 1 and 2 for ${{{{{{\langle M \mid \Xi \rangle}}}}}}$ , there are no other occurrences of $\hat{r}$ elsewhere, and all occurrences are within just one of ${{{{{{\mathcal{E}}}}}}}[~], V, H$ . If they are within V, then because of the affineness of p within N, $\hat{r}$ may appear within the resulting term $N[V/p, \hat{r}'/r]$ , but will not appear in the new $\Xi'(\hat{r}')$ or elsewhere. If within ${{{{{{\mathcal{E}}}}}}}[~]$ or H, the occurrences of $\hat{r}$ will all be moved to $\Xi'(\hat{r}')$ , and there will be none elsewhere.

• For S-Res (applied to some subterm $\hat{r}'W$ within some ${{{{{{\mathcal{H}}}}}}}$ ): If $\hat{r}$ occurs within W, it may appear within the resulting $R[W/y]$ , but not elsewhere. If $\hat{r}$ occurs within $\Xi(\hat{r}')$ (i.e. within R), then it does not appear elsewhere in ${{{{{{\langle M \mid \Xi \rangle}}}}}}$ . So after the application of S-Res and the deletion of $\hat{r}'$ from $\Xi$ , $\hat{r}$ may appear in $R[W/y]$ but nowhere else.

• For the rules carried over from the original semantics (applied within some ${{{{{{\mathcal{H}}}}}}}$ ), the preservation of Condition 1 is immediate, since $\Xi$ is unchanged.

To complete the proof, suppose that within the reduction sequence from some naturally arising ${{{{{{\langle M \mid \Xi \rangle}}}}}}$ we have an application of S-Res for a given variable $\hat{r}$ : that is, we have some configuration ${{{{{{\langle {{{{{{\mathcal{H}}}}}}}[\hat{r}W] \mid \Xi' \rangle}}}}}}$ . Since this satisfies Conditions 1 and 2, we see that the highlighted occurrence of $\hat{r}$ is its only appearance within ${{{{{{\mathcal{H}}}}}}}[\hat{r}W]$ or the range of $\Xi'$ , and it follows that $\hat{r}$ does not appear at all within the resulting configuration ${{{{{{\langle {{{{{{\mathcal{H}}}}}}}[R[W/y]] \mid \Xi' \backslash \hat{r} \rangle}}}}}}$ . There is therefore no danger of a later instance of S-Res for $\hat{r}$ .

We can now lay to rest the worry mentioned earlier:

Lemma 2 is the crucial property of ${{{{{{\lambda_{\textrm{a}}}}}}}}$ on which our whole argument hinges. This property is flagrantly violated by ${\lambda_{\textrm{h}}}$ , as illustrated by effcount with its essential use of multi-shot resumptions. Our next task is to show how, in view of Lemma 2, the evaluation of a given subterm may be tracked in a sequential way through a reduction sequence.

10.2 Tracking of active subterms

We shall say a subterm S of M is active if it occurs in an evaluation position, i.e. $M = {{{{{{\mathcal{H}}}}}}}[S]$ for some handler context ${{{{{{\mathcal{H}}}}}}}$ . We introduce the following concepts for tracking the evaluation of S through the reduction of M with respect to some resumption context $\Xi$ .

Clearly, if ${{{{{{\langle M \mid \Xi \rangle}}}}}}$ is naturally arising and $M = {{{{{{\mathcal{H}}}}}}}[S]$ , any reduction sequence ${{{{{{\langle S \mid \Xi \rangle}}}}}} {{{{{{\leadsto}}}}}}^\ast {{{{{{\langle S' \mid \Xi' \rangle}}}}}}$ will yield a reduction sequence

\[ {{{{{{\langle M \mid \Xi \rangle}}}}}} ~\equiv~ {{{{{{\langle {{{{{{\mathcal{H}}}}}}}[S] \mid \Xi \rangle}}}}}} ~{{{{{{\leadsto}}}}}}^\ast~ {{{{{{\langle {{{{{{\mathcal{H}}}}}}}[S'] \mid \Xi' \rangle}}}}}} \]

We then say the occurrence of S’ highlighted by ${{{{{{\mathcal{H}}}}}}}[S']$ is an active reduct of the original occurrence of S highlighted by ${{{{{{\mathcal{H}}}}}}}[S]$ .

In this situation, there are four possibilities:

1. 1. The reduction of ${{{{{{\langle S \mid \Xi \rangle}}}}}}$ may continue forever.

2. 2. The reduction may terminate in some ${{{{{{\langle \mathbf{return}\;V \mid \Xi' \rangle}}}}}}$ where V is a value.

3. 3. The reduction of ${{{{{{\langle S \mid \Xi \rangle}}}}}}$ may get stuck at some configuration ${{{{{{\langle {{{{{{\mathcal{E}}}}}}}[\mathbf{do}\;\ell\,V] \mid \Xi' \rangle}}}}}}$ where the $\mathbf{do}\;\ell\,V$ is not handled anywhere within ${{{{{{\mathcal{H}}}}}}}[{{{{{{\mathcal{E}}}}}}}[\mathbf{do}\;\ell\,V]]$ — in this situation, we say the entire computation is absolutely blocked.

4. 4. The reduction may get stuck at some ${{{{{{\langle {{{{{{\mathcal{E}}}}}}}[\mathbf{do}\;\ell\,V] \mid \Xi' \rangle}}}}}}$ , where the $\mathbf{do}\;\ell\,V$ is not handled within ${{{{{{\mathcal{E}}}}}}}[\mathbf{do}\;\ell\,V]$ itself, but is handled further out within ${{{{{{\mathcal{H}}}}}}}[-]$ .

In case 4, ${{{{{{\mathcal{H}}}}}}}[-]$ will have the form ${{{{{{\mathcal{H}}}}}}}'[\mathbf{handle} \; {{{{{{\mathcal{F}}}}}}}[-] \; \mathbf{with} \; H]$ where ${{{{{{\mathcal{F}}}}}}}$ is an evaluation context, and the $\text{{S-Op}}'$ rule will then apply to ${{{{{{\langle \mathbf{handle} \; {{{{{{\mathcal{F}}}}}}}[{{{{{{\mathcal{E}}}}}}}[\mathbf{do}\;\ell\,V]] \;\mathbf{with}\; H \mid \Xi' \rangle}}}}}}$ . This will result in a new resumption environment entry

\[ \hat{r} ~\mapsto ~ \lambda y.\; \mathbf{handle} \; {{{{{{\mathcal{F}}}}}}}[{{{{{{\mathcal{E}}}}}}}[\mathbf{return} \; y]] \;\mathbf{with}\; H \]

and we may call the subterm ${{{{{{\mathcal{E}}}}}}}[\mathbf{return} \; y]$ here a dormant reduct of the original S.

As the reduction of the original ${{{{{{\langle M \mid \Xi \rangle}}}}}}$ continues, this environment entry will remain unaffected until, if ever, $\hat{r}$ is activated by S-Res (and by Lemma 2, this will happen at most once). This activation step will have the form

\[ {{{{{{\langle {{{{{{\mathcal{H}}}}}}}_1' [\hat{r}W] \mid \Xi_1 \rangle}}}}}} ~{{{{{{\leadsto}}}}}}~ {{{{{{\langle {{{{{{\mathcal{H}}}}}}}_1'[\mathbf{handle}\;{{{{{{\mathcal{F}}}}}}}[{{{{{{\mathcal{E}}}}}}}[\mathbf{return}\;W]]\;\mathbf{with}\;H] \mid \Xi_1 \rangle}}}}}} \]

where ${{{{{{\mathcal{H}}}}}}}_1'[\mathbf{handle}\;{{{{{{\mathcal{F}}}}}}}[-]\;\mathbf{with}\;H]$ is itself a handler context, which we shall write as ${{{{{{\mathcal{H}}}}}}}_1[-]$ for compatibility with our earlier convention. So writing $S_1$ for ${{{{{{\mathcal{E}}}}}}}[\mathbf{return}\;W]$ , we have arrived at

\[ {{{{{{\langle M \mid \Xi \rangle}}}}}} ~{{{{{{\leadsto}}}}}}^\ast~ {{{{{{\langle {{{{{{\mathcal{H}}}}}}}_1[S_1] \mid \Xi_1 \rangle}}}}}}, \]

and we shall again designate this occurrence of $S_1$ as an active reduct of the original S.

For the purpose of tracking the fate of the original subterm S, it will also be convenient to say that ${{{{{{\langle S \mid \Xi \rangle}}}}}}$ gives rise in this context to a pseudo-reduction sequence

\[ {{{{{{\langle S \mid \Xi \rangle}}}}}} ~{{{{{{\leadsto}}}}}}^\ast~ {{{{{{\langle {{{{{{\mathcal{E}}}}}}}[\mathbf{do}\;\ell\,V] \mid \Xi' \rangle}}}}}} ~{{{{{{\leadsto}}}}}}^!~ {{{{{{\langle S_1 \mid \Xi_1 \rangle}}}}}} \]

in which all steps but the last are genuine reductions, but the step flagged by ${{{{{{\leadsto}}}}}}^!$ is considered as a ‘pseudo-reduction’ (note that this step has a seemingly ‘non-deterministic’ character in that it depends crucially on information from outside ${{{{{{\langle {{{{{{\mathcal{E}}}}}}}[\mathbf{do}\;\ell\,V] \mid \Xi' \rangle}}}}}}$ ). The point is simply to have a way of saying how the evaluation of ${{{{{{\mathcal{E}}}}}}}[\mathbf{do}\;\ell\,V]$ continues after being temporarily suspended by a switch to another thread of control.

We may now repeat exactly the same procedure starting from ${{{{{{\langle {{{{{{\mathcal{H}}}}}}}_1[S_1] \mid \Xi_1 \rangle}}}}}}$ , potentially yielding further (active and dormant) reducts of the original S:

\[ {{{{{{\langle S \mid \Xi \rangle}}}}}} ~{{{{{{\leadsto}}}}}}^\ast~ {{{{{{\langle {{{{{{\mathcal{E}}}}}}}[\mathbf{do}\;\ell\,V] \mid \Xi' \rangle}}}}}} ~{{{{{{\leadsto}}}}}}^!~ {{{{{{\langle S_1 \mid \Xi_1 \rangle}}}}}} ~{{{{{{\leadsto}}}}}}^\ast~ {{{{{{\langle {{{{{{\mathcal{E}}}}}}}_1[\mathbf{do}\;\ell_1\,V_1] \mid \Xi'_1 \rangle}}}}}} ~{{{{{{\leadsto}}}}}}^!~ {{{{{{\langle S_2 \mid \Xi_2 \rangle}}}}}} ~{{{{{{\leadsto}}}}}}^\ast~ \cdots \]

In this way, we obtain an extended pseudo-reduction sequence for S, consisting of ordinary reduction sequences interspersed with pseudo-reductions of the above kind, jumping straight from some ${{{{{{\langle {{{{{{\mathcal{E}}}}}}}_i[\mathbf{do}\;\ell_i\,V_i] \mid \Xi_i \rangle}}}}}}$ to the corresponding ${{{{{{\langle {{{{{{\mathcal{E}}}}}}}_i[\mathbf{return}\;W_i] \mid \Xi_{i+1} \rangle}}}}}}$ .

This pseudo-reduction sequence may continue forever, or it may be absolutely blocked, or it may end with a dormant reduct in a resumption environment entry that is never subsequently activated, or it may terminate in some ${{{{{{\langle \mathbf{return}\;V \mid \Xi'_i \rangle}}}}}}$ where V is a value. In the last case, we say the evaluation of the original S completes (in the context of ${{{{{{\langle {{{{{{\mathcal{H}}}}}}}[S] \mid \Xi \rangle}}}}}}$ ).

It is thanks to Lemma 2 that the evaluation behaviour of S may be represented in this way by a single linear reduction sequence rather than by a branching tree. The notion of pseudo-reduction sequence thus allows us to reason about subterm evaluations much as in the familiar setting, rendering the thread-switching machinery largely transparent, its only trace being in the ‘non-deterministic’ character of the pseudo-reduction steps.

It is also clear that the notions of ancestor and descendant make sense for subterms appearing within pseudo-reduction sequences, providing one considers configurations ${{{{{{\langle S \mid \Xi \rangle}}}}}}$ as a whole: a subterm within the main term may have descendants within the resumption environment, and vice versa. For a pseudo-reduction step ${{{{{{\langle S \mid \Xi \rangle}}}}}} {{{{{{\leadsto}}}}}}^! {{{{{{\langle S' \mid \Xi' \rangle}}}}}}$ , we say a subterm of the right-hand side is a descendant of one on the left iff it is a descendant with respect to the genuine reduction sequence that witnesses this pseudo-step.

10.3 Application to generic count

We now apply the above notions to the analysis of generic counting in ${{{{{{\lambda_{\textrm{a}}}}}}}}$ , obtaining a lower bound analogous to that of Theorem 3 for ${\lambda_{\textrm{b}}}$ . Proceeding as in Section 8, we fix $n \in {{{{{{\mathbb{N}}}}}}}$ , and suppose that K is some program of ${{{{{{\lambda_{\textrm{a}}}}}}}}$ that correctly counts all canonical n-standard predicates P (noting that all such predicates are actually terms from our base language ${\lambda_{\textrm{b}}}$ ). Once again, focusing on this restricted class of predicates will greatly simplify our task, while still giving all we need for a worst-case lower bound.

We recall here that we are thinking of ${\lambda_{\textrm{b}}}$ as included in ${{{{{{\lambda_{\textrm{a}}}}}}}}$ via the intuitionistic encoding $(-)^\star$ defined in Section 9. Since our intention is that our lower bound for ${{{{{{\lambda_{\textrm{a}}}}}}}}$ should generalise the one for ${\lambda_{\textrm{b}}}$ , this means that the types Point and Predicate appear within ${{{{{{\lambda_{\textrm{a}}}}}}}}$ as

Formally, then, we will be considering the reduction behaviour of ${{{{{{\langle K\,(!P) \mid \emptyset \rangle}}}}}}$ , where $P:\mathrm{Predicate}$ is the $\star$ -translation of a canonical n-standard predicate, K is a generic count program of ${{{{{{\lambda_{\textrm{a}}}}}}}}$ assumed to count all such predicates correctly. (We may assume without loss of generality that K is a closed term.) By hypothesis, this reduction will terminate in some ${{{{{{\langle \mathbf{return}\;k \mid \Xi_{end} \rangle}}}}}}$ where k is a numeral.

By an application of P, we shall mean an occurrence of a term $P\,Q$ in evaluation position in some reduct of ${{{{{{\langle K\,(!P) \mid \emptyset \rangle}}}}}}$ (so that ${{{{{{\langle K\,(!P) \mid \emptyset \rangle}}}}}} {{{{{{\leadsto}}}}}}^\ast {{{{{{\langle {{{{{{\mathcal{H}}}}}}}[P\,Q] \mid \Xi_0 \rangle}}}}}}$ for some handler context ${{{{{{\mathcal{H}}}}}}}$ ), where we require that the P in $P\,Q$ is a descendant of the original P. As a significant consequence of our typing of P, the argument Q here will be of type $!\mathrm{Point}$ , meaning that no resumption variable $\hat{r}$ may appear in Q (recall that resumption variables are not of $!$ -type). However, such terms Q may well exhibit effectful behaviour in other ways: they may contain $\mathbf{do}$ invocations to be handled elsewhere within K, and they may contain their own $\mathbf{handle}$ expressions.

For any such application of P, we may consider the pseudo-reduction sequence for $P\,Q$ arising from the reduction of ${{{{{{\langle {{{{{{\mathcal{H}}}}}}}[P\,Q] \mid \Xi_0 \rangle}}}}}}$ . In view of the special form of the canonical predicate P (see Definition 8), it is clear that this pseudo-reduction sequence will have the following form, or some initial portion thereof:

\[ \begin{array}{rclcl}{{{{{{\langle P\,Q \mid \Xi_0 \rangle}}}}}} & {{{{{{\leadsto}}}}}}^\ast & {{{{{{\langle {{{{{{\mathcal{E}}}}}}}_0[Q\,k_0] \mid \Xi_0 \rangle}}}}}} & {{{{{{\leadsto}}}}}}^{\ast,!} & {{{{{{\langle {{{{{{\mathcal{E}}}}}}}_0[b_0] \mid \Xi_1 \rangle}}}}}} \\ & {{{{{{\leadsto}}}}}}^\ast & {{{{{{\langle {{{{{{\mathcal{E}}}}}}}_1[Q\,k_1] \mid \Xi_1 \rangle}}}}}} & {{{{{{\leadsto}}}}}}^{\ast,!} & {{{{{{\langle {{{{{{\mathcal{E}}}}}}}_1[b_1] \mid \Xi_2 \rangle}}}}}} \\ & \cdots \\ & {{{{{{\leadsto}}}}}}^\ast & {{{{{{\langle {{{{{{\mathcal{E}}}}}}}_{n-1}[Q\,k_{n-1}] \mid \Xi_{n-1} \rangle}}}}}} & {{{{{{\leadsto}}}}}}^{\ast,!} & {{{{{{\langle {{{{{{\mathcal{E}}}}}}}_{n-1}[b_{n-1}] \mid \Xi_n \rangle}}}}}} \\ & {{{{{{\leadsto}}}}}}^\ast & {{{{{{\langle \mathbf{return}\;b \mid \Xi_n \rangle}}}}}}\end{array} \]

Here each ${{{{{{\mathcal{E}}}}}}}_i[-]$ has its unique hole occurrence at the head of an $\mathbf{if}$ -expression corresponding to one of the nested $\mathbf{if}$ -expressions within P itself.

We think of the above pseudo-reduction as a sequence of ‘P-phases’ alternating with ‘Q-phases’. The former are the portions designated by ${{{{{{\leadsto}}}}}}^\ast$ : these are short sequences of genuine reductions concerned with the evaluation of the canonical n-standard predicate P in this instance. The latter are the portions designated by ${{{{{{\leadsto}}}}}}^{\ast,!}$ , which may mix genuine reduction steps with pseudo ones. Clearly, no Q-phase can run forever, since the whole computation ${{{{{{\langle K\,(!P) \mid \emptyset \rangle}}}}}} {{{{{{\leadsto}}}}}}^\ast {{{{{{\langle \mathbf{return}\;k \mid \Xi_{end} \rangle}}}}}}$ is finite. Likewise, the pseudo-reduction for $P\,Q$ can never block absolutely, as this too would prevent the whole computation from completing. Nonetheless, it is quite possible that a computation for $P\,Q$ may hang because one of the Q-phases is suspended by a $\mathbf{do}$ operation and never thereafter resumed. We say an application of P is successful if it evaluates all the way to some boolean b as indicated above.

In the case of a successful application, we see that the P-phases consist of precisely the reductions that feature in the definition of the tree $\mathcal{U}(P)$ : in the notation of the above reduction scheme, the computation is tracing out the path $b_0 \ldots b_{n-1}$ through this tree. Bearing in mind that P is assured to be n-standard, we may conclude that $\{ k_0,\ldots,k_{n-1} \} = \{ 0,\ldots,n-1 \}$ and that $\mathcal{U}(P)(b_0 \ldots b_{n-1}) = !b$ .

We may now, ‘with hindsight’, identify the semantic n-point to which P was in effect applied: namely, the point $\pi$ given by $\pi(k_i)=b_i$ for each i. Notice that in the setting of ${\lambda_{\textrm{b}}}$ , this semantic point could be read off at the point of application simply as $[\![ Q ]\!] $ ; however, this is not possible here, since the behaviour of $\mathbf{do}$ operations within Q need not be determined by Q itself, and indeed may vary according to the context in which Q appears. Nonetheless, in the above situation, it is convenient to refer to our $P\,Q$ as an application of P to $\pi$ . Since, as we have seen, the point $\pi$ may be read off from the pseudo-reduction sequence for $P\,Q$ , we have shown:

The crucial claim is now the following:

We now consider the reduction sequence from ${{{{{{\langle K\,(!(\lambda q.\,C[-])) \mid \emptyset \rangle}}}}}}$ , carrying the hole ‘ $-$ ’ through the computation. Just as in Lemma 1, we argue that this hole must at some point reach the head of a $\mathbf{case}$ expression in evaluation position, and by looking at the last ancestor of this hole occurrence that does not appear within a descendant of the original $\lambda q.\,C[-]$ , we see that at this point we have a configuration ${{{{{{\langle {{{{{{\mathcal{H}}}}}}}[(\lambda q.\,C[-])Q] \mid \Xi \rangle}}}}}}$ with Q a closed term of type Point. This reduces in the next step to ${{{{{{\langle {{{{{{\mathcal{H}}}}}}}[E[-]] \mid \Xi \rangle}}}}}}$ , where $E[-] \equiv C[-][Q/q]$ . (Note that we are here considering the entire top-level computation and are tracking subterms through genuine reductions, not pseudo-reductions.)

In the present setting, we cannot conclude that $[\![ Q ]\!] = \pi$ — indeed, $[\![ Q ]\!] $ as defined in Definition 2 has no clear meaning if Q invokes operations that it cannot handle. Nevertheless, it is again the case that $E[-]$ is a complex of nested $\mathbf{if}$ expressions with various branch conditions $Q\,k$ , and with the unique hole at the leaf at position l. The idea now is that the only way for the hole to become later exposed at the head of an active $\mathbf{case}$ expression is for these enclosing $\mathbf{if}$ expressions to be successively stripped away until the hole is exposed, and this can only happen if each of the relevant conditions $Q\,k$ evaluates (by pseudo-reduction) to the corresponding $\pi(k)$ .

More formally, we have that $E[-]$ has the form $\mathbf{if}\;Q\,k_0\,\cdots$ , which desugars to $\mathbf{let}\;z {{{{{{\leftarrow}}}}}} Q\,k_0\;\mathbf{in}\; \mathbf{case}\,z\,\{\cdots\}$ . Now consider the pseudo-reduction sequence for $Q\,k_0$ . This cannot continue for ever or be absolutely blocked, for then the same would happen with true substituted for ‘ $-$ ’ and the computation of $P(!Q)$ would not complete. We also claim that it cannot end with a dormant reduct that is never reactivated. To see this, we first note that the pseudo-reduction sequence for $\mathbf{let}\;z {{{{{{\leftarrow}}}}}} Q\,k_0\;\mathbf{in}\;\cdots$ exactly tracks the one for $Q\,k_0$ for as far as this latter pseudo-reduction extends (this is easy to check, since no handler intervenes between these terms). So if the sequence for $Q\,k_0$ ended in a dormant reduct, the same would be true for $\mathbf{let}\;z {{{{{{\leftarrow}}}}}} Q\,k_0\;\mathbf{in}\;\cdots$ , whose pseudo-reduction sequence carries with it the critical hole occurrence. Thus, this hole occurrence would remain forever dormant in the resumption environment and so would never become exposed.

We conclude that the pseudo-reduction of $Q\,k_0$ must complete with some boolean value b, so that the enclosing $\mathbf{let}$ expression reduces to $\mathbf{case}\,b\,\{\cdots\}$ . Furthermore, this value b must be $b_0 = \pi(k_0)$ if the hole is not to be eliminated at the next step. After applying one of the S-Case rules, we are now left with one of the $\mathbf{if}$ expressions from the second level of the original $E[-]$ , say with branch condition $Q\,k_1$ , and the same argument now shows that this must pseudo-reduce to the boolean value $b_1 = \pi(k_1)$ . Continuing in this way, we arrive at a pseudo-reduction of ${{{{{{\langle (\lambda q.\,C[-])Q \mid \Xi \rangle}}}}}}$ to $\mathbf{return}\;-$ , and under specialisation of ‘ $-$ ’ to true, we obtain precisely a successful pseudo-reduction of ${{{{{{\langle P\,Q \mid \Xi \rangle}}}}}}$ to true. Moreover, since our computation has traced the path $b_0 \ldots b_{n-1}$ through the term structure of P, we have here an application of P to $\pi$ in the sense introduced above.

Suppose, then, that within the evaluation of $K\,(!P)$ we are given such a reduction step, reducing a subterm $\mathbf{case}\;b_i\;\{\mathbf{inl}\,{{{{{{\langle \mapsto \rangle}}}}}} R; \mathbf{inr}\,{{{{{{\langle \mapsto \rangle}}}}}} R'\}$ to R or R’ as appropriate. Note that this subterm does not appear within a $\lambda$ expression, since we never reduce under a $\lambda$ . Moreover, if this reduction step indeed features in the pseudo-reduction for some $P\,Q$ as displayed above, then R and R’ are themselves descendants of subterms within $C[\mathrm{true}][Q/q]$ , and indeed are either boolean literals or expressions $\mathbf{if}\;Q\,k'\;\cdots$ .

Let us now trace the ancestors of R (say) back as far as possible through the entire computation of $K\,(!P)$ . There are two cases. If R is a boolean $\mathbf{return}\;b$ , this will have an ancestor within P itself in the application $P\,Q$ , and it is clear from the displayed form of the pseudo-reduction that this will be the latest ancestor that occurs under a $\lambda$ (within the main term as opposed to the resumption environment); and this property serves to pinpoint the application $P\,Q$ . If $R \equiv \mathbf{if}\;Q\,k'\;\cdots$ , then its earliest ancestor will be within the term $C[\mathrm{true}][Q/q]$ to which $P\,Q$ contracts, when R came into existence as the result of the substitution $[Q/q]$ . Once again, this information suffices to pinpoint $P\,Q$ . Thus, it is uniquely determined with which successful application the given S-Case step is associated.

As with Theorem 3, one may also obtain a variant of this theorem with both occurrences of ‘canonical’ omitted, at the cost of significant extra complication in the proof.

Taken together, Theorems 5 and 2 highlight the efficiency gap between ${{{{{{\lambda_{\textrm{a}}}}}}}}$ and ${\lambda_{\textrm{h}}}$ .