The reader of this paper is assumed to be familiar with Backus’s functional programming (FP) notation and the linear expansion theorem (LET). The LET states (loosely) that if a function f is defined recursively by an equation of the form f = p → q ; H f where p and q are fixed functions and H is a linear functional, then f has the non-recursive expansion f = p → q ; H t p → H q ; Ht2 p → H 2 q ;... where H t is a functional defined in terms of H, called its predicate transformer. If the sequence terminates, f has a nonrecursively computable solution, f x = ( H i q ) x.
The paper’s main result (Theorem 1) is an extension of the LET to the degenerate-bilinear-1 (DBL-1) class of nonlinear functionals. If H is DBL-1, it can be written as Here the G i are expansions of a bilinear functional G (see Williams [1]). The expansion of H has four branches: a, b, c, and d.
In the first formulation of Theorem 1, branch d is never allowed to occur, but this restriction is eased in some cases explored in the corollaries. The theorem shows that a functional H, defined as above, with certain restrictions on h 1 , H 2 , G , G 1, and g 2, can be computed in n + 1 nonrecursive steps for some n ≥ 0.
As an example, a quadratic functional,
