# Lazy expressions Python has a fairly strict _eager_ evaluation order: * Expressions are evaluated such that 1. expressions within _parentheses_ are evaluated first; 1. in the absence of parentheses, operators with a _higher precedence_ are evaluated before operators with a lower precedence; 1. 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) * {func}`FuPy.fixpoints.fix` * {func}`FuPy.fixpoints.cata` * {func}`FuPy.fixpoints.ana` * {func}`FuPy.fixpoints.hylo` The following functions use `evaluate`: * Function combinators `|` (case), `+` (fplus) * {func}`FuPy.basics.guard` * {func}`FuPy.basics.first` * {func}`FuPy.basics.second` * {func}`FuPy.fixpoints.out` * {func}`FuPy.prelude.strList` * {func}`FuPy.prelude.listList` It can be necessary to apply `force` at the very end. ## Examples The following examples require ```python 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`: ```python @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: ```python trace(lambda: f(0, lazy('1 + 2')), live=True) ``` which results in the output ``` 0 Define: λ : 1 + 2 1 Suspend: (θ_0 : `1 + 2`) 2 Apply: ┌ f.(0, (θ_0 : `1 + 2`)) 3 Motivate: = { def. of f } 4 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: ```python trace(lambda: f(2, lazy('1 + 2')), live=True) ``` which results in the output ``` 0 Define: λ : 1 + 2 1 Suspend: (θ_1 : `1 + 2`) 2 Apply: ┌ f.(2, (θ_1 : `1 + 2`)) 3 Motivate: = { def. of f } 4 Evaluate: │ (θ_1 : `1 + 2`) 5 Apply: │ │ ┌ (λ : 1 + 2)._ 6 Motivate: │ │ = { def. of λ } 7 Return: │ │ └ 3 8 Get: │ (θ_1 = 3) 9 Get: │ (θ_1 = 3) 10 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](../examples/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: ```python @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 ```python @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 ```python @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: ```python @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: ```python 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](fixpoints.md). * Haskell is mostly lazy, except when the programmer or compiler request strict evaluation.