Use of a list processing language in programming simplification procedures

There are several reasons which make the use of a list processing type of computer programming language attractive for the coding of logical algorithms such as those which arise in truth function simplification. Among the most important programming advantages are ease of coding, improved use of computer storage, and a reduction of limitations on the number of variables which can be handled. Also of interest is the fact that the effectiveness of an algorithm implemented by means of a list processing system is much less dependent upon the characteristics of the particular computer used than is the case if instructions closer to basic machine language are employed. In combination with the ease of coding, this permits the evaluation of the relative effectiveness of several diverse algorithms or heuristic implementations of a single algorithm. This paper demonstrates the utility of the MIT 709 LISP I system in coding several procedures for determination of the prime implicants and irredundant forms of a truth function. The capabilities and limitations of these programs are discussed as is their application to evaluating the algorithms they represent.