Computer Laboratory

Technical reports

Proving termination of normalization functions for conditional expressions

Lawrence C. Paulson

June 1985, 16 pages

Abstract

Boyer and Moore have discussed a recursive function that puts conditional expressions into normal form. It is difficult to prove that this function terminates on all inputs. Three termination proofs are compared: (1) using a measure function, (2) in domain theory using LCF, (3) showing that its “recursion relation”, defined by the pattern of recursive calls, is well-founded. The last two proofs are essentially the same though conducted in markedly different logical frameworks. An obviously total variant of the normalize function is presented as the ‘computational meaning’ of those two proofs.

A related function makes nested recursive calls. The three termination proofs become more complex: termination and correctness must be proved simultaneously. The recursion relation approach seems flexible enough to handle subtle termination proofs where previously domain theory seemed essential.

Full text

PDF (0.1 MB)
DVI (0.0 MB)

BibTeX record

@TechReport{UCAM-CL-TR-69,
  author =	 {Paulson, Lawrence C.},
  title = 	 {{Proving termination of normalization functions for
         	   conditional expressions}},
  year = 	 1985,
  month = 	 jun,
  url = 	 {http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-69.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  number = 	 {UCAM-CL-TR-69}
}