More Web Proxy on the site http://driver.im/

Article

Free access

The program understanding problem: analysis and a heuristic approach

Authors:

Qiang YangAuthors Info & Claims

ICSE '96: Proceedings of the 18th international conference on Software engineering

Pages 6 - 15

Published: 01 May 1996 Publication History

PDF eReader Publisher Site

Abstract

Program understanding is the process of making sense of a complex source code. This process has been considered as computationally difficult and conceptually complex. So far no formal complexity results have been presented, and conceptual models differ from one researcher to the next. We formally prove that program understanding is NP hard. Furthermore, we show that even a much simpler subproblem remains NP hard. However we do not despair by this result, but rather offer an attractive problem solving model for the program understanding problem. Our model is built on a framework for solving constraint satisfaction problems, or CSPs, which are known to have interesting heuristic solutions. Specifically, we can represent and heuristically address previous and new heuristic approaches to the program understanding problem with both existing and specially designed constraint propagation and search algorithms.

References

[1]

Sandra Carberry. Modeling the user's plans and goals. Computational Linguistics, 14(3):23-37, 1988.

Digital Library

[2]

Prem Devanbu and Laura Eaves. Gen++ -an analyzer generator for c++ programs. Technical report, AT& T Bell Labs, New Jersey, 1994.

[3]

Michael R. Garey and David S. Johnson. Computers and Intractability: A guide to the theory of NP- Completeness. W. H. Freeman and Company, Bell Laboratories, Murray Hill, New Jersey, 1979.

Digital Library

[4]

Henry Kautz and James Allen. Generalized plan recognition. In Proceedings of the Fijth National Conference on Art@cial Intelligence, pages 32-37, Philadelphia, Pennsylvania, 1986.

[5]

Wojtek Kozaczynski and Jim Q. Ning. Automated program understanding by concept recognition. Automated SofWare Engineering, 1:61-78, 1994.

[6]

Vipin Kumar. Algorithms for constraint-satisfaction problems. AI Magazine, pages 32-44, Spring 1992.

Digital Library

[7]

A.K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99-1 18, 1977.

Digital Library

[8]

H. Muller, K. Wong, and S.R. Tilley. Understanding software systems using reverse engineering technology. In Proceedings of the Colloquim on Object Orientation in Databases and SofWare Enginenng, pages 88-98, December 1994.

[9]

Alex Quilici. A memory-based approach to recognizing programming plans. Communications of the ACM, 37(5):84-93, May 1994.

Digital Library

[10]

Alex Quilici and David Chin. DECODE: A cooperative environment for reverse-engineering legacy software. In Proceedings of the Second Working Conference on Reverse-Engineering, pages 156-165. IEEE Computer Society Press, July 1995.

Digital Library

[11]

C. Rich and R.C. Waters. The programmer's apprentice. Addison-Wesley, Reading, Mass., 1990.

[12]

P. Van Hentenryck, Y. Deville, and C-M. Teng. A generic arc-consistency algorithm and its specializations. Artificial Intelligence, 57:291-321, 1992.

Digital Library

[13]

L. M. Wills. Automated program recognition: A feasibility demonstration. Artificial Intelligence, 45(2): 113-172, February 1990.

Digital Library

[14]

L. M. Wills. Automated program recognition by Graph Parsing. PhD thesis, MIT, July 1992.

Digital Library

[15]

Steven Woods and Alex Quilici. Representing memory-based program understanding as constraint satisfaction. Technical report, University of Water- 100, Department of Computer Science, 1995.

[16]

Steven Woods, Alex Quilici, and Qiang Yang. Program understanding and plan recognition: reasoning under different assumptions. Technical report, University of Waterloo, Department of Computer Science, 1995.

[17]

Steven Woods and Qiang Yang. Constraintbased plan recognition in legacy code. Working Notes of the Third Workshop on AI and Software Engineering : Breaking the Toy Mold (ALSE), August 1995.

[18]

Steven Woods and Qiang Yang. Program understanding as constraint satisfaction. In Proceedings of the IEEE Seventh International Workshop on Computer- Aided Software Engineering (CASE), pages 3 18-327, July 1995.

Digital Library

[19]

Steven Woods and Qiang Yang. Program understanding as constraint satisfaction: Representation and reasoning techniques. Technical report, University of Waterloo, Department of Computer Science, 1995.

Cited By

Taherkhani AMalmi LKorhonen AMalmi LPears A(2008)Algorithm recognition by static analysis and its application in students' submissions assessmentProceedings of the 8th International Conference on Computing Education Research10.1145/1595356.1595372(88-91)Online publication date: 13-Nov-2008
https://dl.acm.org/doi/10.1145/1595356.1595372
Vinz BEtzkorn L(2008)Improving program comprehension by combining code understanding with comment understandingKnowledge-Based Systems10.1016/j.knosys.2008.03.03321:8(813-825)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1016/j.knosys.2008.03.033
Johnson TEigenmann RSchwartzbach MBall T(2006)Context-sensitive domain-independent algorithm composition and selectionProceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/1133981.1134003(181-192)Online publication date: 11-Jun-2006
https://dl.acm.org/doi/10.1145/1133981.1134003
Show More Cited By

Index Terms

The program understanding problem: analysis and a heuristic approach
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation

Recommendations

Program understanding as constraint satisfaction
WCRE '95: Proceedings of the Second Working Conference on Reverse Engineering

The process of understanding a source code in a high-level programming language involves complex computation. Given a piece of legacy code and a library of program plan templates, understanding the code corresponds to building mappings from parts of the ...
Constraint satisfaction tractability from semi-lattice operations on infinite sets

A famous result by Jeavons, Cohen, and Gyssens shows that every Constraint Satisfaction Problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. This is one of the basic facts for the so-called ...
Constructing NP-intermediate problems by blowing holes with parameters of various properties

The search for natural NP-intermediate problems is one of the holy grails within computational complexity. Ladner's original diagonalization technique for generating NP-intermediate problems, blowing holes, has a serious shortcoming: it creates problems ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICSE '96: Proceedings of the 18th international conference on Software engineering

May 1996

590 pages

ISBN:0818672463

Chairman:
H. Dieter Rombach
Univ. of Kaiserslautern, Germany

Copyright © Copyright (c) 1996 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Sponsors

German Comp Soc: GI - Gesellshaft for Informatik
SIGSOFT: ACM Special Interest Group on Software Engineering
IEEE-CS\TCSE: TC on Software Engineering

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 May 1996

Check for updates

Author Tags

Qualifiers

Article

Conference

ICSE96

Sponsor:

German Comp Soc
SIGSOFT
IEEE-CS\TCSE

ICSE96: 18th International Conference on Software Engineering

March 25 - 29, 1996

Berlin, Germany

Acceptance Rates

Overall Acceptance Rate 276 of 1,856 submissions, 15%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
625
Total Downloads

Downloads (Last 12 months)49
Downloads (Last 6 weeks)6

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Taherkhani AMalmi LKorhonen AMalmi LPears A(2008)Algorithm recognition by static analysis and its application in students' submissions assessmentProceedings of the 8th International Conference on Computing Education Research10.1145/1595356.1595372(88-91)Online publication date: 13-Nov-2008
https://dl.acm.org/doi/10.1145/1595356.1595372
Vinz BEtzkorn L(2008)Improving program comprehension by combining code understanding with comment understandingKnowledge-Based Systems10.1016/j.knosys.2008.03.03321:8(813-825)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1016/j.knosys.2008.03.033
Johnson TEigenmann RSchwartzbach MBall T(2006)Context-sensitive domain-independent algorithm composition and selectionProceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/1133981.1134003(181-192)Online publication date: 11-Jun-2006
https://dl.acm.org/doi/10.1145/1133981.1134003
Johnson TEigenmann R(2006)Context-sensitive domain-independent algorithm composition and selectionACM SIGPLAN Notices10.1145/1133255.113400341:6(181-192)Online publication date: 11-Jun-2006
https://dl.acm.org/doi/10.1145/1133255.1134003
Yang JHendrix TChang KUmphress DGuimaraes M(2005)An empirical validation of complexity profile graphProceedings of the 43rd annual ACM Southeast Conference - Volume 110.1145/1167350.1167395(143-149)Online publication date: 18-Mar-2005
https://dl.acm.org/doi/10.1145/1167350.1167395
Mendonça NKramer J(2001)An Approach for Recovering Distributed System ArchitecturesAutomated Software Engineering10.1023/A:10112177208608:3-4(311-354)Online publication date: 1-Aug-2001
https://dl.acm.org/doi/10.1023/A%3A1011217720860
Burnstein ISaner FLimpiyakorn Y(1999)Using an Artificial Intelligence Approach to Build an Automated Program Understanding/Fault Localization ToolProceedings of the 11th IEEE International Conference on Tools with Artificial Intelligence10.5555/850950.853651Online publication date: 8-Nov-1999
https://dl.acm.org/doi/10.5555/850950.853651
Woods SYang Q(1998)Program Understanding as Constraint SatisfactionAutomated Software Engineering10.1023/A:10086552307365:2(147-181)Online publication date: 1-Apr-1998
https://dl.acm.org/doi/10.1023/A%3A1008655230736
Quilici AYang QWoods S(1998)Applying Plan Recognition Algorithms To Program UnderstandingAutomated Software Engineering10.1023/A:10086088253905:3(347-372)Online publication date: 1-Jul-1998
https://dl.acm.org/doi/10.1023/A%3A1008608825390
Kunz TSeuren M(1997)Fast detection of communication patterns in distributed executionsProceedings of the 1997 conference of the Centre for Advanced Studies on Collaborative research10.5555/782010.782022Online publication date: 10-Nov-1997
https://dl.acm.org/doi/10.5555/782010.782022
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten