Details of Grant 

EPSRC Reference:	GR/R72440/01
Title:	Safe Pointers by Graph Transformation
Principal Investigator:	Plump, Dr D
Other Investigators:	Runciman, Professor C
Researcher Co-Investigators:
Project Partners:
Department:	Computer Science
Organisation:	University of York
Scheme:	Fast Stream
Starts:	01 January 2002	Ends:	31 May 2003	Value (£):	51,705
EPSRC Research Topic Classifications:	Fundamentals of Computing
EPSRC Industrial Sector Classifications:	Information Technologies
Related Grants:
Panel History:
Summary on Grant Application Form
Pointers in imperative programming languages are indispensable for the efficient implementation of many algorithms, and are ubiquitous in software at both applications and systems level. However, manipulating pointers is an error-prone activity, while the type systems of current programming languages are incapable of detecting most pointer errors. The problem is that a programmer has no means to specify the intended shape of a pointer stucture, be it a list, a circular list or a tree, so the type system cannot check whether pointer manipulations in a program will always preserve the intended shape. Mathematically pointer structures are graphs, so it is natural to describe classes of pointer structures by collections of graph transformation rules which reduce all intended structures to an accepting graph. Graph transformation rules can also specify arbitrary operations on pointer structures. Our aim is to use graph transformation rules to uniformly describe pointer-based data structures, and operations upon them, in such a way that the safety of the operations can be checked automatically. We use graph reduction systems rather than logic because they can specify important structures, like balanced binary trees, that cannot be expressed in any other shape description formalism proposed in the literature. We also intend to define an extension of the C programming language for graph transformation rules. The extension will enable programmers to specify pointer structures and operations upon them, and will be translated to ordinary C by a pre-processor which also checks the safety of the specified operations.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.york.ac.uk