Lazy expressions

Python has a fairly strict eager evaluation order:

Expressions are evaluated such that
1. expressions within parentheses are evaluated first;
2. in the absence of parentheses, operators with a higher precedence are evaluated before operators with a lower precedence;
3. and otherwise from left to right.
Function calls are evaluated last, in the sense that the expression expr_0(expr_1, expr_2, ...) is evaluated left to right, where expr_0 needs to evaluate to a callable (i.e. a function). In particular, this function is called only after all its arguments expr_1, expr_2, …, have been evaluated. That is, the code in the function’s body is executed only after all the expressions have been evaluated.
A notable exception to evaluating all arguments first is the ternary if-else expression:
- expr_True if condition else expr_False
Here, condition is first evaluated, and depending on its outcome, only one of expr_True or expr_False is evaluated. This is an example of lazy evaluation (of expr_True and expr_False).
And this is also the case for short-circuit evaluation of some boolean expressions:
- In a and b, b is not evaluated when a is False.
- In a or b, b is not evaluated when a is True.

FuPy supports so-called lazy expressions with memoization (caching) through the class Lazy. Lazy expressions can be formed in the following ways:

Lazy(lambda: expr);
lazy(f) where f is a function; we have lazy(f) = Func(lambda a: Lazy(lambda: f(a))); thus, lazy(f)(a) = Lazy(lambda: f(a)).
lazy('expr'), which is roughly equivalent to Lazy(lambda: eval('expr')).

When such a lazy expression is constructed, the expression is not evaluated, but stored unevaluated in a so-called thunk. Lazy expressions behave in the following ways:

Evaluation of a Lazy expression can be forced by applying evaluate. (Note that evaluate can also be applied to non-Lazy values; it then does nothing.)
The function force (in FuPy.utils) will evaluate all embedded lazy expressions. Note that this may give rise to infinite behavior.
When a Lazy expression is called like a function, it is automatically evaluated before doing the call. (The lazy expression must then evaluate to a function.)
When a Lazy expression is indexed like a sequence (string, tuple, list), it is automatically evaluated before doing the indexing. (The lazy expression must then evaluate to a sequence.)
When +, -, *, ==, etc. are applied to a Lazy expression, the lazy expression is first evaluated.

Support for other operators may be added in the future.

We have tried to hide the explicit use of Lazy expressions and evaluate as much as possible. In particular, the following functions introduce lazy expressions, to avoid unnecessary infinite recursions:

Function combinators & (split), * (ftimes), + (fplus)
FuPy.fixpoints.fix()
FuPy.fixpoints.cata()
FuPy.fixpoints.ana()
FuPy.fixpoints.hylo()

The following functions use evaluate:

Function combinators | (case), + (fplus)
FuPy.basics.guard()
FuPy.basics.first()
FuPy.basics.second()
FuPy.fixpoints.out()
FuPy.prelude.strList()
FuPy.prelude.listList()

It can be necessary to apply force at the very end.

Examples

The following examples require

from FuPy.basics import *
from FuPy.laziness import *

_ = x_

Simple lazy expression

We define function f with two arguments a and b to return a * b * b, but where argument b can be an “expensive” expression, which we don’t want to have evaluated when a == 0:

@func
def f(a: int, b: Lazy[int]) -> int:
    """Return a if a == 0 else a * b * b."""
    return a if a == 0 else a * b * b

When f(0, Lazy(lambda: expr)) is called, argument b won’t be evaluated.
When f(2, Lazy(lambda: expr)) is called, argument b is evaluated once and the resulting value is used twice.

The first call can be checked by tracing the evaluation:

trace(lambda: f(0, lazy('1 + 2')), live=True)

which results in the output

Define:    λ : 1 + 2
Suspend:   (θ_0 : `1 + 2`)
Apply:     ┌ f.(0, (θ_0 : `1 + 2`))
Motivate:  =   { def. of f }
Return:    └ 0

Note that lazy expressions are printed as (θ_i : `expr`), where i is the thunk number. Here, the thunk is left unevaluated.

The second call can be checked by tracing the evaluation:

trace(lambda: f(2, lazy('1 + 2')), live=True)

which results in the output

Define:    λ : 1 + 2
Suspend:   (θ_1 : `1 + 2`)
Apply:     ┌ f.(2, (θ_1 : `1 + 2`))
Motivate:  =   { def. of f }
Evaluate:  │     (θ_1 : `1 + 2`)
Apply:     │     │     ┌ (λ : 1 + 2)._
Motivate:  │     │     =   { def. of λ }
Return:    │     │     └ 3
Get:       │     (θ_1 = 3)
Get:       │     (θ_1 = 3)
Return:    └ 18

Now, the thunk is evaluated once (in Step 4) and this value is used twice (in Steps 8 and 9). An evaluated thunk is printed as (θ_i = value).

Tail Recursion and Tail Call Elimination

Also see demo.py.

Lazy expressions can be used to do, what is known as, tail call elimination. In a (direct) recursive function definition, an occurrence of a recursive call in the return statement, is called a tail call. No further work is done after such a tail call. A recursive function definition is said to be tail recursive, when all recursive calls are tail calls. Hence, the recursion is linear, such as over the natural numbers or lists. The famous factorial function is recursive but not tail recursive:

@func
def fac(n: int) -> int:
    """Return n factorial."""
    return 1 if n == 0 else n * fac(n - 1)

After the recursive call fac(n - 1), a multiplication must still be done to complete the computation. By generalizing fac to gfac with

@func
def gfac(a: int, n: int) -> int:
    """Return a * fac(n).
    Note that fac(n) = gfac(1, n)."""
    return a if n == 0 else gfac(a * n, n - 1)

The definition of gfac is tail recursive. The call gfac(a, n) will use n levels of stack space. In Python, the default limit on the recursion depth is 1000 levels. Hence, gfac(1, 1000) will result in a RecursionError.

It is well-known that a tail-recursive function definition can be transformed into a loop, thereby eliminating the recursion. For gfac that would be

@func
def gfac_iter(a: int, n: int) -> int:
    """Return a * fac(n), iteratively."""
    while n != 0:
        a, n = a * n, n - 1
    return a

Function gfac_iter uses only one level of stack space.

Lazy can be used to let a tail-recursive function use the heap rather than the stack, as follows:

@func
def gfac_lazy(a: int, n: int) -> IterLazy[int]:
    """Return lazy expression for a * fac(n)."""
    return a if n == 0 else Lazy(lambda: gfac_lazy(a * n, n - 1))

Since the returned value is lazy (for n > 0), we must apply evaluate (which acts as a trampoline) to get the actual result:

gfac = evaluate @ gfac_lazy

Now, gfac(1, 1000) will succeed.

Notes

Python is mostly strict, except when laziness is requested, such as FuPy does in some function combinators and in fixpoints.
Haskell is mostly lazy, except when the programmer or compiler request strict evaluation.