NDLI: Analysis of pointer rotation

Please wait, while we are loading the content...

Analysis of pointer rotation

Data types, parameters and type checking

A high-level approach to computer document formatting

Experience with an applicative string processing language

An overview of the SUMMER programming language

Analysis of simple programs over different sets of primitives

Synchronous schemes and their decision problems

Qualified data flow problems

Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables

Prime subprogram parsing of a program

On specifying verifiers

A case study in specifying the semantics of a programming language

Final data type specifications: a new data type specification method

Expressiveness of the operation set of a data abstraction

On proving inductive properties of abstract data types

On the temporal analysis of fairness

"Sometime" is sometimes "not never": on the temporal logic of programs

Propositional logics of programs: systems, models, and complexity

A dynamic logic of multiprocessing with incomplete information

Axiomatic definitions of programming languages: a theoretical assessment (preliminary report)

Efficient algorithms for structural similarity of grammars

Theoretical and empirical studies on using program mutation to test the functional correctness of programs

"Type-completeness" as a language principle

An indeterminate constructor for applicative programming

Formal specification as a design tool

Analysis of pointer rotation

Content Provider	ACM Digital Library
Author	Suzuki, Norihisa
Abstract	Pointer manipulation is one of the trickiest operations in programming and is a major source of programming errors. A great deal of research effort has been dedicated to making programs with pointers more reliable. In this paper we will present pointer operations which reduce conceptual difficulties when writing pointer programs, and increase reliability of programs. We will analyze theoretically as well as empirically why these operations are more convenient. Finally, we will define the safety of rotations, and show that it is decidable to check whether the rotation is safe and also show that it is a good measure of the correctness of programs. (That is, if the rotation is safe it is highly probable that the program is correct, and if it is unsafe it is highly probable that the program is incorrect.)Probably the most successful effort to eliminate difficulties associated with pointer manipulation is the invention of abstract data types and the use of implementation modules. Pointers are often used to implement complex data structures, which in turn represent abstract data types. We can textually localize relevant pointer manipulations using abstract data types. Thus, we can easily check correctness of pointer programs. This approach is successful when the structure of abstract data types is simple, or efficiency is not seriously required. However, programs like garbage collection, list marking and copying, and balanced tree manipulations have not been well specified by abstract types.The approach taken in this paper is complementary to abstract data types, and makes programs like list marking and copying more reliable and easy to write. The idea behind this approach is to introduce higher-level pointer manipulation primitives instead of pointer assignments. Since most pointer assignments do not appear isolated, we can group several assignments together and replace them by one of these new primitives. We also show some theoretical evidence why these operations are nicer.Two primitives are introduced in this paper. One is the n-way pointer rotation, which is defined as being equivalent to the following procedure:Rotate: procedure(var x1, x2, … , xn:T) = begin var w:T; w:=x1; x1:=x2; … ;xn:=w endwhere all the locations of arguments x1, x2, … , xn are distinct. The other operation is n-way pointer slide, which is as powerful as pointer assignment yet keeps the elegance of rotation.Section 2 of this paper reviews previous work related to this subject. We give definitions of pointer operations analyzed in this paper in section 3. Using these operations, Deutsch-Schorr-Waite algorithm is rewritten in section 4. In section 5 we analyze pointer rotations extensively and obtain several properties which are not attainable by ordinary pointer assignments. In section 6 we define the safety of pointer rotation when applied to linear list and trees. Then, we extend this definition to arbitrary pointer data structures and show a decision procedure to check safety. In section 7 we show two examples, list marking and list copying programs written using rotations and slides. We examine how we can directly code the algorithms using these operations and safety checking algorithms are useful.
Starting Page	1
Ending Page	11
Page Count	11
File Format	PDF
ISBN	0897910117
DOI	10.1145/567446.567447
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1980-01-28
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in