A framework for call graph construction algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A framework for call graph construction algorithms

Full text

Pdf (1.36 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 23 , Issue 6 (November 2001) table of contents

Pages: 685 - 746

Year of Publication: 2001

ISSN:0164-0925

Authors

David Grove	IBM T.J. Watson Research Center, NY
Craig Chambers	University of Washington, Seattle, WA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 33, Downloads (12 Months): 225, Citation Count: 38

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/506315.506316 What is a DOI?

ABSTRACT

A large number of call graph construction algorithms for object-oriented and functional languages have been proposed, each embodying different tradeoffs between analysis cost and call graph precision. In this article we present a unifying framework for understanding call graph construction algorithms and an empirical comparison of a representative set of algorithms. We first present a general parameterized algorithm that encompasses many well-known and novel call graph construction algorithms. We have implemented this general algorithm in the Vortex compiler infrastructure, a mature, multilanguage, optimizing compiler. The Vortex implementation provides a "level playing field" for meaningful cross-algorithm performance comparisons. The costs and benefits of a number of call graph construction algorithms are empirically assessed by applying their Vortex implementation to a suite of sizeable (5,000 to 50,000 lines of code) Cecil and Java programs. For many of these applications, interprocedural analysis enabled substantial speed-ups over an already highly optimized baseline. Furthermore, a significant fraction of these speed-ups can be obtained through the use of a scalable, near-linear time call graph construction algorithm.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Agesen, O. 1994. Constraint-based type inference and parametric polymorphism. In Proceedings of the First International Static Analysis Symposium. LNCS 864, Springer, New York, NY, 78--100.
	2	Ole Agesen, The Cartesian Product Algorithm: Simple and Precise Type Inference Of Parametric Polymorphism, Proceedings of the 9th European Conference on Object-Oriented Programming, p.2-26, August 07-11, 1995
	3	Ole Agesen, Concrete type inference: delivering object-oriented applications, Stanford University, Stanford, CA, 1996
	4	Ole Agesen , Jens Palsberg , Michael I. Schwartzbach, Type Inference of SELF, Proceedings of the 7th European Conference on Object-Oriented Programming, p.247-267, July 26-30, 1993
	5	Alexander Aiken, Set Constraints: Results, Applications, and Future Directions, Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, p.326-335, May 02-04, 1994
	6	Martin Alt , Florian Martin, Generation of Efficient Interprocedural Analyzers with PAG, Proceedings of the Second International Symposium on Static Analysis, p.33-50, September 25-27, 1995
	7	J. Michael Ashley, A practical and flexible flow analysis for higher-order languages, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.184-194, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237773]
	8	J. Michael Ashley, The effectiveness of flow analysis for inlining, Proceedings of the second ACM SIGPLAN international conference on Functional programming, p.99-111, June 09-11, 1997, Amsterdam, The Netherlands
	9	David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
	10	Deepankar Bairagi , Dharma P. Agrawal , Sandeep Kumar, Precise Call Graph Construction for OO Programs in the Presence of Virtual Functions, Proceedings of the international Conference on Parallel Processing, p.412-416, August 11-15, 1997
	11	David Callahan , Alan Carle , Mary Wolcott Hall , Ken Kennedy, Constructing the Procedure Call Multigraph, IEEE Transactions on Software Engineering, v.16 n.4, p.483-487, April 1990 [doi>10.1109/32.54302]
	12	Chambers, C. 1993. The Cecil language: Specification and rationale. Tech. Rep. UW-CSE-93-03-05, Dept. Computer Science and Engineering. Univ. of Washington. Revised, March 1997.
	13	Chambers, C., Dean, J., and Grove, D. 1996. Whole-program optimization of object-oriented languages. Tech. Rep. UW-CSE-96-06-02, Dept. of Computer Science and Engineering. Univ. of Washington. June.
	14	C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
	15	Craig Chambers , David Ungar, Interactive type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.150-164, June 1990, White Plains, New York, United States
	16	Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
	17	Jeffrey Adgate Dean , Craig Chambers, Whole-program optimization of object-oriented languages, 1996
	18	Jeffrey Dean , Greg DeFouw , David Grove , Vassily Litvinov , Craig Chambers, Vortex: an optimizing compiler for object-oriented languages, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.83-100, October 06-10, 1996, San Jose, California, United States
	19	Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
	20	Greg DeFouw , David Grove , Craig Chambers, Fast interprocedural class analysis, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.222-236, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268965]
	21	L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
	22	Amer Diwan , J. Eliot B. Moss , Kathryn S. McKinley, Simple and effective analysis of statically-typed object-oriented programs, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.292-305, October 06-10, 1996, San Jose, California, United States
	23	Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
	24	Mary F. Fernández, Simple and effective link-time optimization of Modula-3 programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.103-115, June 18-21, 1995, La Jolla, California, United States
	25	James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
	26	David Grove, The impact of interprocedural class analysis on optimization, Proceedings of the 1995 conference of the Centre for Advanced Studies on Collaborative research, p.25, November 07-09, 1995, Toronto, Ontario, Canada
	27	David Paul Grove , Craig Chambers, Effective interprocedural optimization of object-oriented languages, 1998
	28	David Grove , Jeffrey Dean , Charles Garrett , Craig Chambers, Profile-guided receiver class prediction, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.108-123, October 15-19, 1995, Austin, Texas, United States
	29	David Grove , Greg DeFouw , Jeffrey Dean , Craig Chambers, Call graph construction in object-oriented languages, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.108-124, October 05-09, 1997, Atlanta, Georgia, United States
	30	Mary W. Hall , Ken Kennedy, Efficient call graph analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.227-242, Sept. 1992 [doi>10.1145/151640.151643]
	31	Nevin Heintze , David McAllester, Linear-time subtransitive control flow analysis, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.261-272, June 16-18, 1997, Las Vegas, Nevada, United States
	32	Fritz Henglein, Efficient type inference for higher-order binding-time analysis, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.448-472, June 1991, Cambridge, Massachusetts, United States
	33	Urs Hölzle , Ole Agesen, Dynamic versus static optimization techniques for object-oriented languages, Theory and Practice of Object Systems, v.1 n.3, p.167-188, Fall 1995
	34	Urs Hölzle , David Ungar, Optimizing dynamically-dispatched calls with run-time type feedback, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.326-336, June 20-24, 1994, Orlando, Florida, United States
	35	Suresh Jagannathan , Stephen Weeks, A unified treatment of flow analysis in higher-order languages, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.393-407, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199536]
	36	Ralph E. Johnson , Justin O. Graver , Laurance W. Zurawski, TS: an optimizing compiler for smalltalk, Conference proceedings on Object-oriented programming systems, languages and applications, p.18-26, September 25-30, 1988, San Diego, California, United States
	37	John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
	38	Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
	39	David Andrew Kranz , Paul Hudak, Orbit: an optimizing compiler for scheme, 1988
	40	Arun Lakhotia, Constructing call multigraphs using dependence graphs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.273-284, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158647]
	41	William Landi , Barbara G. Ryder, Pointer-induced aliasing: a problem taxonomy, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.93-103, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99599]
	42	Flemming Nielson , Hanne Riis Nielson, Infinitary control flow analysis: a collecting semantics for closure analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.332-345, January 15-17, 1997, Paris, France [doi>10.1145/263699.263745]
	43	Nicholas Oxhøj , Jens Palsberg , Michael I. Schwartzbach, Making Type Inference Practical, Proceedings of the European Conference on Object-Oriented Programming, p.329-349, June 29-July 03, 1992
	44	Jens Palsberg , Christina Pavlopoulou, From polyvariant flow information to intersection and union types, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.197-208, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268963]
	45	Jens Palsberg , Michael I. Schwartzbach, Object-oriented type inference, Conference proceedings on Object-oriented programming systems, languages, and applications, p.146-161, October 06-11, 1991, Phoenix, Arizona, United States
	46	Pande, H. D. and Ryder, B. G. 1994. Static type determination for C++. In Proceedings of Sixth USENIX C++ Technical Conference.
	47	Phillips, G. and Shepard, T. 1994. Static typing without explicit types. Unpublished report, Dept. of Electrical and Computer Engineering, Royal Military College of Canada, Kingston, Ont., Canada.
	48	John Bradley Plevyak , Andrew Chien, Optimization of object-oriented and concurrent programs, 1996
	49	John Plevyak , Andrew A. Chien, Precise concrete type inference for object-oriented languages, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.324-340, October 23-28, 1994, Portland, Oregon, United States
	50	Ryder, B. 1979. Constructing the call graph of a program. IEEE Trans. Softw. Eng. 5, 3, 216--225.
	51	Marc Shapiro , Susan Horwitz, Fast and accurate flow-insensitive points-to analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 15-17, 1997, Paris, France [doi>10.1145/263699.263703]
	52	Sharir, M. and Pnueli, A. 1981. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds. Prentice-Hall, Englewood Cliffs, NJ, Ch. 7, 189--233.
	53	O. Shivers, Control flow analysis in scheme, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.164-174, June 20-24, 1988, Atlanta, Georgia, United States
	54	Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
	55	Steensgaard, B. 1994. A polyvariant closure analysis with dynamic abstraction. Unpublished manuscript.
	56	Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
	57	Dan Stefanescu , Yuli Zhou, An equational framework for the flow analysis of higher order functional programs, Proceedings of the 1994 ACM conference on LISP and functional programming, p.318-327, June 27-29, 1994, Orlando, Florida, United States
	58	Vijay Sundaresan , Laurie Hendren , Chrislain Razafimahefa , Raja Vallée-Rai , Patrick Lam , Etienne Gagnon , Charles Godin, Practical virtual method call resolution for Java, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.264-280, October 2000, Minneapolis, Minnesota, United States
	59	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	60	Frank Tip , Jens Palsberg, Scalable propagation-based call graph construction algorithms, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.281-293, October 2000, Minneapolis, Minnesota, United States
	61	Jan Vitek , R. Nigel Horspool , James S. Uhl, Compile-Time Analysis of Object-Oriented Programs, Proceedings of the 4th International Conference on Compiler Construction, p.236-250, October 05-07, 1992
	62	Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States
	63	Andrew K. Wright , Suresh Jagannathan, Polymorphic splitting: an effective polyvariant flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.1, p.166-207, Jan. 1998 [doi>10.1145/271510.271523]

CITED BY 39

	Craig Chambers, Staged compilation, ACM SIGPLAN Notices, v.37 n.3, March 2002
	Atanas Rountev , Ana Milanova , Barbara G. Ryder, Fragment class analysis for testing of polymorphism in Java software, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
	Gleb Naumovich, A conservative algorithm for computing the flow of permissions in Java programs, ACM SIGSOFT Software Engineering Notes, v.27 n.4, July 2002
	Frank Tip , Peter F. Sweeney , Chris Laffra, Extracting library-based Java applications, Communications of the ACM, v.46 n.8, August 2003
	Atanas Rountev , Scott Kagan , Michael Gibas, Static and dynamic analysis of call chains in java, ACM SIGSOFT Software Engineering Notes, v.29 n.4, July 2004
	Larry Koved , Marco Pistoia , Aaron Kershenbaum, Access rights analysis for Java, ACM SIGPLAN Notices, v.37 n.11, November 2002
	Chen Fu , Ana Milanova , Barbara Gershon Ryder , David G. Wonnacott, Robustness Testing of Java Server Applications, IEEE Transactions on Software Engineering, v.31 n.4, p.292-311, April 2005
	William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural pointer aliasing, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Atanas Rountev , Scott Kagan , Michael Gibas, Evaluating the imprecision of static analysis, Proceedings of the ACM-SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08, 2004, Washington DC, USA
	Chen Fu , Barbara G. Ryder , Ana Milanova , David Wonnacott, Testing of java web services for robustness, ACM SIGSOFT Software Engineering Notes, v.29 n.4, July 2004
	Sorin Lerner , Todd Millstein , Erika Rice , Craig Chambers, Automated soundness proofs for dataflow analyses and transformations via local rules, ACM SIGPLAN Notices, v.40 n.1, p.364-377, January 2005
	Baowen Xu , Ju Qian , Xiaofang Zhang , Zhongqiang Wu , Lin Chen, A brief survey of program slicing, ACM SIGSOFT Software Engineering Notes, v.30 n.2, March 2005
	Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to analysis for Java, ACM Transactions on Software Engineering and Methodology (TOSEM), v.14 n.1, p.1-41, January 2005
	Craig Chambers , David Ungar, A retrospective on: "customization: optimizing compiler technology for self, a dynamically-typed object-oriented programming language", ACM SIGPLAN Notices, v.39 n.4, April 2004
	Fragment Class Analysis for Testing of Polymorphism in Java Software, IEEE Transactions on Software Engineering, v.30 n.6, p.372-387, June 2004
	Mariana Sharp , Jason Sawin , Atanas Rountev, Building a whole-program type analysis in Eclipse, Proceedings of the 2005 OOPSLA workshop on Eclipse technology eXchange, p.6-10, October 16-17, 2005, San Diego, California
	Jean Privat , Roland Ducournau, Link-time static analysis for efficient separate compilation of object-oriented languages, ACM SIGSOFT Software Engineering Notes, v.31 n.1, January 2006
	Alan Donovan , Adam Kiežun , Matthew S. Tschantz , Michael D. Ernst, Converting java programs to use generic libraries, ACM SIGPLAN Notices, v.39 n.10, October 2004
	Daniel Spoonhower , Joshua Auerbach , David F. Bacon , Perry Cheng , David Grove, Eventrons: a safe programming construct for high-frequency hard real-time applications, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Jinlin Yang , David Evans , Deepali Bhardwaj , Thirumalesh Bhat , Manuvir Das, Perracotta: mining temporal API rules from imperfect traces, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China
	Vugranam C. Sreedhar, Data-centric security: role analysis and role typestates, Proceedings of the eleventh ACM symposium on Access control models and technologies, June 07-09, 2006, Lake Tahoe, California, USA
	Stephen J. Fink , Eran Yahav , Nurit Dor , G. Ramalingam , Emmanuel Geay, Effective typestate verification in the presence of aliasing, ACM Transactions on Software Engineering and Methodology (TOSEM), v.17 n.2, p.1-34, April 2008
	Manu Sridharan , Rastislav Bodík, Refinement-based context-sensitive points-to analysis for Java, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Paolina Centonze , Gleb Naumovich , Stephen J. Fink , Marco Pistoia, Role-Based access control consistency validation, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA
	Weilei Zhang , Barbara G. Ryder, Discovering accurate interclass test dependences, Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.55-62, June 13-14, 2007, San Diego, California, USA
	Rajeev Kumar , Soham S. Chakraborty, Precise static type analysis for object oriented programs, ACM SIGPLAN Notices, v.42 n.2, p.17-26, February 2007
	Bruno Dufour , Barbara G. Ryder , Gary Sevitsky, Blended analysis for performance understanding of framework-based applications, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom
	Guoqing Xu , Atanas Rountev, AJANA: a general framework for source-code-level interprocedural dataflow analysis of AspectJ software, Proceedings of the 7th international conference on Aspect-oriented software development, March 31-April 04, 2008, Brussels, Belgium
	Patricia M. Hill , Fausto Spoto, Deriving escape analysis by abstract interpretation, Higher-Order and Symbolic Computation, v.19 n.4, p.415-463, December 2006
	Ond∨rej Lhoták, Comparing call graphs, Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.37-42, June 13-14, 2007, San Diego, California, USA
	Marco Pistoia , Stephen J. Fink , Robert J. Flynn , Eran Yahav, When Role Models Have Flaws: Static Validation of Enterprise Security Policies, Proceedings of the 29th International Conference on Software Engineering, p.478-488, May 20-26, 2007
	Ana Milanova, Composition inference for UML class diagrams, Automated Software Engineering, v.14 n.2, p.179-213, June 2007
	Guoqing Xu , Atanas Rountev, Merging equivalent contexts for scalable heap-cloning-based context-sensitive points-to analysis, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA
	Roland Ducournau, Perfect hashing as an almost perfect subtype test, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.6, p.1-56, October 2008
	Mariana Sharp , Atanas Rountev, Static Analysis of Object References in RMI-Based Java Software, IEEE Transactions on Software Engineering, v.32 n.9, p.664-681, September 2006
	Ondřej Lhoták , Laurie Hendren, Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation, ACM Transactions on Software Engineering and Methodology (TOSEM), v.18 n.1, p.1-53, September 2008
	Satish Chandra , Stephen J. Fink , Manu Sridharan, Snugglebug: a powerful approach to weakest preconditions, ACM SIGPLAN Notices, v.44 n.6, June 2009
	Emmanuel Geay , Marco Pistoia , Takaaki Tateishi , Barbara G. Ryder , Julian Dolby, Modular string-sensitive permission analysis with demand-driven precision, Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, p.177-187, May 16-24, 2009
	Weilei Zhang , Barbara G. Ryder, Automatic construction of accurate application call graph with library call abstraction for Java: Research Articles, Journal of Software Maintenance and Evolution: Research and Practice, v.19 n.4, p.231-252, July 2007