Fifth Annual IEEE Symposium on

Logic in Computer Science (LICS 1990)

Paper: Programming in equational logic: beyond strong sequentiality (at LICS 1990)

Authors: Sekar, R.C. Ramakrishnan, I.V.


The authors consider whether it is possible to devise a complete normalization algorithm that minimizes (rather than eliminates) the wasteful reductions for the entire class of regular systems. A solution is proposed to this problem using the concept of a necessary set of redexes. In such a set, at least one of the redexes must be reduced to normalize a term. An algorithm is devised to compute a necessary set for any term not in normal form, and it is shown that a strategy that repeatedly reduces all redexes in such a set is complete for regular programs. It is also shown that the algorithm is optimal among all normalization algorithms that are based on left-hand sides alone. This means that the algorithm is lazy (like Huet-Levy's) on strongly sequential parts of a program, relaxes laziness minimally to handle the other parts, and thus does not sacrifice generality for the sake of efficiency


    author = 	 {Sekar, R.C. and Ramakrishnan, I.V.},
    title = 	 {Programming in equational logic: beyond strong sequentiality},
    booktitle =  {Proceedings of the Fifth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1990},
    year =	 1990,
    editor =	 {John Mitchell},
    month =	 {June}, 
    pages =      {230--241},
    location =   {Philadelphia, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}