Konferensartikel

Assertions for Dynamic Shape Analysis of List Data Structures

Mikhail Auguston
Computer Science Department, New Mexico State University, USA

Miu Har Hon
Computer Science Department, New Mexico State University, USA

Ladda ner artikelhttp://www.ep.liu.se/ecp_article/index.en.aspx?issue=001;article=004

Ingår i: Proceedings of the 3rd International Workshop on Automatic Debugging; 1997 (AADEBUG-97)

Linköping Electronic Conference Proceedings 1:4, s. 37-42

Linköping Electronic Articles in Computer and Information Science 009:4, s. 37-42

Visa mer +

Publicerad: 1997-09-10

ISBN:

ISSN: 1650-3686 (tryckt), 1650-3740 (online)

Abstract

We introduce an assertion language for run-time checking of linked list data structure shapes. The assertion language is expressive enough to define characteristic predicates for data structures created with the use of pointers and dynamic memory allocation. Examples of such data structures include singly linked list; binary tree; doubly linked list; and cyclic list. These characteristic predicates may be used for automatic run-time detection of data constraint violations. Some results of experiments with a prototype assertion checker implementation for the PASCAL programming language are presented.

Nyckelord

Inga nyckelord är tillgängliga

Referenser

[Auguston 90] M.Auguston; “Programming language RIGAL as a compiler writing tool”; ACM SIGPLAN Notices; Vol. 25; December 1990; pp.61-69.

[Auguston 94] M.Auguston; “A Language for Debugging Automation”; in the Proceedings of the 6th International Conference on Software Engineering and Knowledge Engineering SEKE’94; Knowledge Systems Institute; 1994; pp.108-115.

[Fradet; Le Metayer 97]P.Fradet; D. Le Metayer; “Shape Types”; in the Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages POPL’97; ACM Press; 1997; pp.27-37.

[Ghiya; Hendren 96]R.Ghiya; L.Hendren; “Is it a Tree; a DAG; or a Cyclic Graph? A Shape Analysis for Heap-Directed Pointers in C”; in the Proceedings of the 23rd ACM SIGPLANSIGACT Symposium on Principles of Programming Languages POPL’96; ACM Press; 1996; pp.1-15.

[Landi 92] W.Landi; “Undecidabilty of static analysis”; ACM Letters on Programming Languages and Systems; Vol 1; No 4; 1992.

[Luckham 90] D.Luckham; “Programming with Specifications”; Springer Verlag; 1990.

[Miu Har Hon 95]Miu Har Hon; “Assertions for List Data Structures”; M.S. Project; Department of Computer Science; New Mexico State University; November 1995.

[Pande et al. 94]H.Pande; W. Landi; B. Ryder; “Interprocedural Def-Use Associations for C Systems with Single Level Pointers”; IEEE TSE; Vol. 20; No 5; May 1994; pp.385-403

[Sagiv; Reps 96]M.Sagiv; T.Reps; “Solving Shape-Analysis Problems in Languages with Destructive Updating”; in the Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages POPL’96; ACM Press; 1996; pp.16-31.

Citeringar i Crossref