Analysis of Functional Algorithms
Functional programs are evaluated by reducing expressions to values. So different reduction orders are important.
A reduction strategy is about choosing next expression to reduce. And proving it terminates, the produced result should be in normal form.
call-by-name, or lazy evaluation, is often implemented using a graph reductio mechanism:
- When a function application is reduced, a copy of its body is made with the formal parameters replaced by pointers to the graphs of the respective arguments.
- When an argument is evaluated, its graph is replaced by its value which is shared.
Strictness analysis: Determine the situations in which it is safe to evaluate an expression strictly because its value is needed in every execution.
Divergence could be a factor. If an argument can go divergent, then it might not be equivalently strict.
In a lazy language, algebraic type constructors are also lazy. For example, an application Cons a b
won't evaluate a
and b
until needed.
Step-counting analysis: Use the number of function applications as a measure.
Transformation
- expression $e$ has a cost $T(e)$
- function $f$ has a step-counting version $T_f$
{f a1 a2 ... an = e}
$\Rightarrow$ {Tf a1 a2 ... an = 1 + T(e)}
T(f a1 a2 ... an) = T(a1) + t(a2) + ... + T(an) + (Tf a1 a2 ... an)
Program Transformation
The Burstall-Darlington transformation system
- Unfolding
- Constant Evaluation
- Instantiation
- Definition
- Folding
- Abstraction: introduces local definitions
About TCO: In a lazy language, TCO only works if the parameters of the recursive call are strictly evaluated.
Exercises
3.1
- Only
a
:(f $! a) b
- Only
b
:(f a) $! b
a
andb
:(f $! a) $! b
3.2
- $T_{power, 0} = 2$
- $T_{power, k} = T_{if} + 1 + T_{if} + 2 + (T_{power, k / 2} + 1)$
It is a tail-call, plus k 'div' 2
, so space complexity should be $O(log(k))$
3.3
a) lazy list: length
- $O(n)$, head
- $O(m)$, sum
- $O(mn)$
b) strict tails: length
- $O(mn)$, head
- $O(m)$, sum
- $O(mn)$
c) all strict: length
- $O(mn)$, head
- $O(mn)$, sum
- $O(mn)$
3.4
a)
sum 0 ret = ret + 0
sum n ret = sum (n - 1) (ret + n)
prod 0 ret = ret * 1
prod n ret = prod (n - 1) (ret * n)
b)
prodsum n = x + y where (x, y) = g n
g n = (n * x, n + y) where (x, y) = g (n - 1)
g 0 = (1, 0)
c)
so
$$
prodsum(n) - \frac{n (n - 1) }{2} = n(prodsum(n - 1) - \frac{(n - 1)(n - 2)}{2}) \ g(n) = n g(n - 1) \ g(1) = prodsum(1) = 2\ prodsum(n) = g(n) + \frac{n(n-1)}{2}
$$