Proceedings

Symbolic Evaluation of LISP Functions with Side Effects for Verification

Download BibTeX Cite

Proceedings of the Seventh International Joint Conference on Artificial Intelligence. Theorem Proving. Pages 519-523.

© 1981 International Joint Conferences on Artificial Intelligence

Abstract

In this paper we present a symbolic evaluator of LISP functions. It can handle data-altering functions of the RPLACA type, i.e. functions that change one datastructure by replacing parts of it by other structures that will themselves not be changed further, at least not permanently. The state description language uses first-order predicate calculus. It is argued that symbolic evaluation in terms of this language, although theoretically adequate, is not feasible in general, since it may require extremely complicated specifications for real-life functions with side effects. Examples are given of the specifications needed to verify several versions of SUBSTAD, a non-copying SUBST.

  1. eqa(,nw) & {onichain(ex,nw) --> lb2at5(vs1,lat,ex,l3,ol,nw))
  2. & {-onichain(ex,nw) --> [{atom(car(ol)) --> [{car(ol)=lat --> car(nw):vs1} & {-(car(ol):lat) --> car(nw):car(ol)}]}
  3. & {-atom(car(ol)) --> lb2at3(vs1,lat,ex,l3,car(ol),car(nw))} & {atom(cdr(ol)) --> [{cdr(ol)=lat --> cdr(nw):vs1} & {-(cdr(ol):lat) --> cdr(nw):cdr(ol))]} & {-atom(cdr(ol)) --> lb2at3(vs1,lat,ex,l3,cdr(ol),cdr(nw)))]}}. This predicate already visited mainly looks whether nw -which is is residing on the inverted pointer chain, which may be caused by structure sharing. If so the predicate lb2at5 will describe the situation. (vs1)(lat)(ex)(l3)(ol)(nw) { lb2at5(vs1,lat,ex,l3,ol,nw) <--> [eqa(ol,nw) & {ex:nw --> [ {markb(nw) --> [replacedd(vs1,lat,car(ol),l3) & {atom(cdr(ol)) --> [{cdr(ol):lat --> cdr(nw):vs1} & {-(cdr(ol):lat) --> cdr(nw):cdr(ol)}])
  4. & {-atom(cdr(ol)) --> replacedd(vs1,lat,cdr(ol),cdr(nw))}}
  5. & {-markb(nw) --> {atom(car(ol)) --> [{car(ol):lat --> car(nw):vs1) & {-(car(ol)=lat) --> car(nw):car(ol)})} & {-atom(car(ol)) --> replacedd(vs1,lat,car(ol),car(nw))}
  6. & replacedd(vs1,lat,cdr(ol),l3)])}
  7. & {-(ex:nw) --> [{markb(nw) --> [{atom(cdr(ol)) --> [{cdr(ol)=lat --> cdr(nw):vs1} & {-(cdr(ol):lat) --> cdr(nw):cdr(ol)}])
  8. & {-atom(cdr(ol)) --> lb2at3(vs1,lat,ex,l3,cdr(ol),cdr(nw))}
  9. & E icel){onichain(ex,icel) & lb2at5(vs1,lat,ex,l3,car(ol),icel) & [markb(icel) --> car(icel):nw] & [-markb(icel) --> cdr(icel):nw])])
  10. & {-markb(nw) --> [{atom(car(ol)) --> [{car(ol):lat --> car(nw):vs1} & {-(car(ol):lat) --> car(nw):car(ol))]) & {-atom(car(ol)) --> lb2at3(vs1,lat,ex,l3,car(ol),car(nw))}
  11. & (E icel){onichain(ex,icel) & lb2at5(vs1,lat,ex,l3,cdr(ol),icel) & [markb(icel) --> car(icel):nw] & [-markb(icel) --> cdr(icel):nw)}))])]).
  12. CHAMPEAUX, D. de, SUBSTAD: For Fast Substitution in LISP, with an Application on Unification, Information Processing Letters, vol 7, no 1, January 1978, pp 58-62.
  13. CHAMPEAUX, D. de, Algorithms in AI, forthcoming thesis, Economische Faculteit, Universiteit van Amsterdam, 1981.
  14. DARRINGER, J.A. & J.C. KING, Applications of Symbolic Execution to Program Testing, IBM Report RC 6965, January 1977.
  15. DE MILLO R.A. et al, Social Processes and Proofs of Theorems and Programs, CACM, vol 22, no 5, May 1979, pp 271-280.
  16. HAREL, D., Proving the Correctness of Regular Deterministic Programs: A Unifying Survey Using Dynamic Logic, IBM Report 7557, March 1979.
  17. KING, J.C., Symbolic Testing, CACM, vol 385-394. Execution and Program 19, no 7, July 1976, pp
  18. McCARTHY, J. & P.J. HAYES, Some Philosophical Problems from the Standpoint of Artificial Intelligence, in B. Meltzer & D. Michie (Ed), Machine Intelligence 4, Elsevier NY, 1969, pp 463-502.
  19. TOPOR, R.W., The correctness of the Schorr-Waite List Marking Algorithm, Acta Informatica, vol 11, pp 211-221, 1979.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards