Kleene’s predecessor function and the iterative factorial function on Church numerals as presented in Section 2.2 consist of (i) construction of an initial pair of numerals, (ii) bounded iteration of an auxiliary function over the pair, and (iii) extraction of the final answer from the resulting pair. In a functional setting the functions operate, via bounded iteration, on a pair in a store-like manner. The iterative nature is carried out by letting the iterated function con-sume and produce a pair.5 Kleene’s predecessor function and the iterative factorial function hence follow a general pattern known as dynamic programming [37, Section 12.3]:
5The pair of numerals is threaded.
(i) Define the structure of configurations and construct an initial configuration.
(ii) Specify the next configuration as a function of the current configuration in a bounded number of iterations.
(iii) Extract the result from the final configuration.
This approach to define algorithms is usually applied in connection with optimization prob-lems, where a naive solution is slow (relative to a solution with optimal time complexity).
Usually, to be useful, dynamic programming requires that an optimal solution can be de-scribed in terms of optimal solutions for subproblems, and that the same subproblems occur more times in different parts of the solution. This description also matches the predeces-sor function and the factorial function except that subproblems do not occur more times in different part of the solution. The solutions to subproblems are ‘optimal’ per definition:
sub1(n) =
0, ifn=0, 1 1+sub1(n−1) ifn≥2 fac(n) =
1, ifn=0 n×fac(n−1) ifn≥1
In the function mapping natural numbers to the corresponding Fibonacci-number subprob-lems do occur more times in the solution:
fib(n) =
1, ifn=1, 2 fib(n−1) +fib(n−2), ifn≥3
In fact, we encounter an exponential blowup in the number of subproblems to solve in a naive implementation of such a specification. In the following, a more realistic problem is presented.
2.3.1 A longest common subsequence
The problem of finding a longest common subsequence (not subsegment!) LCS of two se-quencesa andbfits perfectly into the problem area of dynamic programming. LCS is an optimization problem where the result can be defined as a combination of optimal solutions to subproblems. Also subproblems occur in more parts of the solution. It is a standard exercise to give an efficient algorithm by use of dynamic programming:
With sequencesa= [a1, . . . , an]andb= [b1, . . . , bn0]the base structure of configurations is a matrixM(n+1)×(n0+1). EntryMi,jrepresents the length of a longest common subsequence of[a1, . . . , ai]and[b1, . . . , bj]. The length of a longest common subsequence using the empty prefix ofawill always be0. That is, all entries in the first row is0. Analogously with use of the empty prefix ofball entries in the first column is0.
A relation between solutions indicates that each entry can be defined in terms of optimal solutions to subproblems, and that subproblems occur more times when unfolding:
|LCS([a1, . . . , ai],[b1, . . . , bj])| =
1+|LCS([a1, . . . , ai−1],[b1, . . . , bj−1])| ifai=bj
max{|LCS([a1, . . . , ai−1],[b1, . . . , bj])|,
|LCS([a1, . . . , ai],[b1, . . . , bj−1])|} ifai6=bj
That is, each entryMi,jcan be found directly from the entriesMi−1,j−1,Mi−1,j, andMi,j−1. The complete definition of all entries hence reads:
Mi,j =
0 ifi=0
0 ifj=0
1+Mi−1,j−1 ifai=bj,i, j≥1 max{Mi−1,j, Mi,j−1} ifai6=bj,i, j≥1
Obviously, the matrix can be filled out, e.g., row by row, starting in entryM1,1. The length of a longest common subsequence ofaandbisMn,n0, and one actual common subsequence of this length can be found by a ‘backwards traversal’ in the matrix starting in entryMn,n0.
The problem nicely fits the pattern of dynamic programming: (1) Defining the base struc-ture matrixMand constructing the initial configuration by filling out first row and first col-umn with0, (2) iteratively filling out the rest of the matrix, and finally (3) constructing the result by a traversal in the completely filled out matrix together constitute a solution to the problem.
2.3.2 Length of a longest common subsequence
To simplify the definitions in this section we restrict the problem to only find the length of a longest common subsequence LLCS.
Base structure and initial configuration A simple observation from the above analysis is that filling out rowi does not depend on other rows than rowi and row i− 1. Because we only consider finding the length and not an actual longest common subsequence the maintained structure is simplified such that only the last row and not the complete matrix is maintained when building the current row. In addition, (parts of) the sequencesaandb are also maintained because they are consumed in each iteration. Accordingly, we represent configuration by a list of length4:
[last row, current row, asuffix, bsuffix]a
For readability we define four ‘projections’:
rowlast := λc.pnthqap0qcc rowcur := λc.pnthqap1qcc suffixa := λc.pnthqap2qcc suffixb := λc.pnthqap3qcc
The initial configuration is constructed by the following abstraction when applied to the first sequenceaand the lengthn0of the second sequence:
confstart := λa.λn0.[pnilqa, padd1qcn0(pconsqap0qc)pnilqa, pconsqa(λx.x)a, pnilqa]a
Here the term for the current row represents a list ofn0+1zeros. Dummies are used in the other three components of the initial configuration because we perform a reconfiguration before each row is handled.
Reconfiguration before each new row Reconfiguration is done before calculating each row: Current row becomes last row, and we reverse that new last row to prepare it for a left to right traversal. The new current row is just the list[p0qc]awhich is the base case for a row. Finally, we progress one step in the sequenceaand reinstallb. We define reconfigura-tion as an abstracreconfigura-tion over the configurareconfigura-tionc, and the sequenceb:
reconf := λc.λb.[prevqa(rowcurc), [p0qc]a, ptlqa(suffixac), b]a
Calculating one entry According to the definition in Section 2.3.1 we need to define a func-tion yielding the maximum of two Church numerals. We define the maximum funcfunc-tion pmaxqcon numerals viapsubqc:
pmaxqc := λn.λn0.psubqcn n0(λx.n)n0
Ifpsubqcn n0 6=β p0qc, nis the maximum of the two numerals and the result isnbecause λx.nis applied at least once. Otherwisen0is the result.
We construct the function that yieldsMi,jgiven the three neighbors (left, diagonal, up) and the two elementsaiandbj:
calcentry := λl.λd.λu.λai.λbj.p=qcaibj(padd1qcd) (pmaxqcl u)
The inner iterated function The inner iterated function it maps from the current config-uration to the next configconfig-uration. it computes the next entry via an application of calcentry and makes progress in the last row and in thebsuffix:
it := λc.[ptlqa(rowlastc),
pconsqa(calcentry(phdqa(rowcurc)) (phdqa(rowlastc)) (phdqa(ptlqa(rowlastc))) (phdqa(suffixac)) (phdqa(suffixbc))) (rowcurc),
suffixac,
ptlqa(suffixbc)]a
To fill the entries of one row it is iterated the length ofbtimes.
Extracting the result The length of a longest common subsequence is the last computed entry in the current row of the final configuration:
extract := λc.phdqa(rowcurc)
Assembling the representation ofLLCS With the above auxiliary definitions a function computes the length of a longest common subsequence of two sequencesa = [a1, . . . , an]a
andb= [b1, . . . , bn0]aby (1) constructing the initial configuration via confstart, (2) iteratively ntimes filling a row (vian0 times applying it) and reconfiguring, and finally (3) extracting the result via extract from the final configuration:
pLLCSqa := λa.λb.extract(plenqaa(λc.plenqabit(reconfc b)) (confstarta(plenqab))) With the configuration representing the ‘state’ of the computation the above representation of LLCS realize a nested for-loop. Via bounded iterationpLLCSqaworks for pair-represented lists augmented with its length. Exchanging the operations to those of Church lists we im-mediately have pLLCSqc which operate on Church lists. A definition of pLLCSqp would abstract over the lengths of prefixes ofaandbto consider.