[PL-sem-jr] 9/29 seminar: solving recursive equations

[Dale Vaillancourt]

Here is a short abstract of what we will discuss during Thursday's
seminar.
-Dale

Recursive equations are a compact formalism for specifying entities such
as functions, data types, and semantic domains.  We are all (more or less)
familiar with equations such as these:

(1) f = (lambda (x) (if (zero? x) 1 (* x (f (- x 1)))))
(2) L = nil + cons(int, L)
(3) D = [D -> D]

Despite that each equation specifies a different kind of structure (a
function, a set, and a partially-ordered set), there are common structures
lurking that explain both the existence of solutions and how to calculate
them.  These common structures are called complete partial-orders (cpos).
We will review cpos and how to use them to solve equations like (1) and
(2).  And more interestingly, we will see that we can actually use cpos to
solve equations like (3) which *itself* specifies a cpo!