Article | Proceedings of the 3rd International Workshop on Automatic Debugging; 1997 (AADEBUG-97) | Assertions for Dynamic Shape Analysis of List Data Structures

Title:
Assertions for Dynamic Shape Analysis of List Data Structures
Author:
Mikhail Auguston: Computer Science Department, New Mexico State University, USA Miu Har Hon: Computer Science Department, New Mexico State University, USA
Download:
Full text (pdf) Full text (ps)
Year:
1997
Conference:
Proceedings of the 3rd International Workshop on Automatic Debugging; 1997 (AADEBUG-97)
Issue:
001
Article no.:
004
Pages:
37-42
No. of pages:
6
Publication type:
Abstract and Fulltext
Published:
1997-09-10
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Series:
Linköping Electronic Articles in Computer and Information Science
ISSN (online):
1401-9841
Publisher:
Linköping University Electronic Press; Linköpings universitet


Export in BibTex, RIS or text

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.

Proceedings of the 3rd International Workshop on Automatic Debugging; 1997 (AADEBUG-97)

Author:
Mikhail Auguston, Miu Har Hon
Title:
Assertions for Dynamic Shape Analysis of List Data Structures
References:

[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.

Proceedings of the 3rd International Workshop on Automatic Debugging; 1997 (AADEBUG-97)

Author:
Mikhail Auguston, Miu Har Hon
Title:
Assertions for Dynamic Shape Analysis of List Data Structures
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment