Terminating polymorphic type inference program analysis

Details Terminating polymorphic type inference program analysis Terminating polymorphic type inference program analysis

1997-06-26

2000-01-11

Voeltz, Emanuel Todd

395705, 395709, G06F 945

Patent

active

060145188

ABSTRACT:
A terminating polymorphic type inference program analysis helps to better optimize, understand, and/or browse computer programs. The analysis represents parameter values for each function call in the program with separate types and modifies the types to comply with typing constraints. The analysis also determines whether a potential non-terminating loop has been entered. If so, the analysis modifies the types such that the types comply with the typing constraints and such that the type inference analysis will terminate. In this manner, the analysis will generate a usable finite set of types for programs regardless of whether the principal typing for the program is infinite in size.

REFERENCES:
patent: 5361351 (1994-11-01), Lenkov et al.
patent: 5488727 (1996-01-01), Agrawal et al.
patent: 5748966 (1998-05-01), Sato
patent: 5790866 (1998-08-01), Robison
Agesen, Ole, Concrete Type Inference: Delivering Object-Oriented Applications, Ph.D. Thesis, Stanford University, Abstract and Table of Contents, pp. i-ii, and vi-viii (Dec. 1995).
Aho, Alfred V., et al., Compilers: Principles, Techniques, and Tools, Addison-Wesley Publishing Company, Contents and Chapter 6, pp. vii-x and 343-388 (1986).
Aiken, Alexander, et al., "Better Static Memory Management: Improving Region-Based Analysis of Higher-Order Languages," Sigplan '95 Conference on Programming Language Design and Implementation, La Jolla, California, pp. 174-185 (Jun. 1995).
Andersen, Lars Ole, Program Analysis and Specialization for the C Programming Language, Ph.D. Thesis, DIKU, University of Copenhagen, Denmark (May 1994).
Austin, Todd M., et al., "Efficient Detection of All Pointer and Array Access Errors," Sigplan '94 Conference on Programming Language Design and Implementation, Orlando, Florida, pp. 290-301 (Jun. 1994).
Birkedal, Lars, et al., "From Region Inference to von Neumann Machines via Region Representation Inference," Proceedings of the 23rd Sigplan-Sigact Symposium on Principles of Programming Languages, St. Petersburg, Florida, pp. 171-183 (Jan. 1996).
Burke, Michael, et al., "Flow-Insensitive Interprocedural Alias Analysis in the Presence of Pointers," Research Report RC 19546, IBM T.J. Watson Research Center, Yorktown Heights, New York, pp. 1-21 (Sep. 1994).
Chase, David R., et al., "Analysis of Pointers and Structures," Proceedings of the ACM Sigplan '90 Conference on Programming Language Design and Implementation, White Plains, New York, pp. 296-310 (Jun. 20-22, 1990).
Choi, Jong-Deok, et al., "Efficient Flow-Sensitive Interprocedural Computation of Pointer-Induced Aliases and Side Effects," Twentieth Annual ACM Sigplan-Sigact Symposium on Principles of Programming Languages, Charleston, South Carolina, pp. 232-245 (Jan. 10-13, 1993).
Choi, Jong-Deok, et al., "On the Efficient Engineering of Ambitious Program Analysis," IEEE Transactions on Software Engineering, vol. 20, No. 2, pp. 105-114 (Feb. 1994).
Cousot, Patrick, et al., "Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints," Proceedings of the Fourth Annual ACM Symposium on Principles of Programming Languages, pp. 238-252 (Jan. 1977).
Cytron, Ron, et al., "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph," ACM Transactions on Programming Languages and Systems, vol. 13, No. 4, pp. 451-490 (Oct. 1991).
Damas, Luis, et al., "Principal Type-Schemes for Functional Programs," Conference Record of the Ninth Annual ACM Symposium on Principles of Programming Languages, Albuquerque, New Mexico, pp. 207-212 (Jan. 1982).
Deutsch, Alain, "A Storeless Model of Aliasing and its Abstractions using Finite Representation of Right-Regular Equivalence Relations," Proceedings of the IEEE 1992 International Conference on Computer Languages, Oakland, California, pp. 2-13 (Apr. 1992).
Deutsch, Alain, "Interprocedural May-Alias Analysis for Pointers: Beyond k-limiting," Sigplan '94 Conference on Programming Language Design and Implementation, Orlando, Florida, pp. 230-241 (Jun. 1994).
Emami, Maryam, et al., "Context-Sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers," ACAPS Technical Memo 54, Advanced Compilers, Architectures and Parallel Systems Group, School of Computer Science, McGill University, Montreal, Canada, pp. 1-28 (Nov. 12, 1993).
Heintze, Nevin, Set Based Program Analysis, Ph.D. Thesis, Carnegie Mellon Univeristy, Abstract, Contents, and Chapter 1, pp. i-iv and 1-6 (1992).
Henglein, Fritz, "Efficient Type Inference for Higher-Order Binding-Time Analysis," Functional Programming Languages and Computer Architecture, 5th ACM Conference, Cambridge, Massachusetts, pp. 448-472 (Aug. 26-30, 1991).
Henglein, Fritz, "Type Inference with Polymorphic Recursion," ACM Transactions on Programming Languages and Systems, vol. 15, No. 2, pp. 253-289 (Apr. 1993).
Kahn, G. "Natural Semantics," Lecture Notes in Computer Science, vol. 457, Stacs 87 4th Annual Symposium on Theoretical Aspects of Computer Science, Passau, Federal Republic of Germany, pp. 22-39, (Feb. 19-21, 1987).
Landi, William, et al., "A Safe Approximate Algorithm for Interprocedural for Interprocedural Pointer Aliasing," Proceedings of the Sigplan '92 Conference on Programming Language Design and Implementation, pp. 235-248 (Jun. 1992).
Landi, William, et al., "Interprocedural Modification Side Effect Analysis With Pointer Aliasing," Proceedings of the Sigplan '93 Conference on Programming Language Design and Implementation, pp. 56-67 (Jun. 1993).
Mairson, Harry G., "Deciding ML Typability is Complete for Deterministic Exponential Time," Proceedings of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, pp. 382-401 (Jan. 1990).
Mycroft, Alan, "Polymorphic Type Schemes and Recursive Definitions," Lecture Notes in Computer Science, vol. 167, Proceedings of the International Symposium on Programming, 6th Colloquium, Toulouse, pp. 217-228 (Apr. 17-19, 1984).
O'Callahan, Robert, et al., "Detecting Shared Representations Using Type Inference," Technical Report CMU-CS-95-202, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, pp. 1-21 (Sep. 1995).
Ruf, Erik, "Context-Insensitive Alias Analysis Reconsidered," Sigplan '95 Conference on Programming Language Design and Implementation, La Jolla, California, pp. 13-22 (Jun. 1995).
Steensgaard, Bjarne, "Sparse Functional Stores for Imperative Programs," ACM Sigplan Workship on Intermediate Representations (IR' 95), San Francisco, California, pp. 62-70 (Jan. 22, 1995).
Steensgaard, Bjarne, "Points-to Analysis in Almost Linear Time," Technical Report MSR-TR-95-08, Microsoft Research, Redmond, Washington, pp. 1-12 (Mar. 1995).
Steensgaard, Bjarne, "Points-to Analysis in Almost Linear Time," Proceedings of the 23rd Sigplan/Sigact Symposium on Principles of Programming Languages, St. Petersburg, Florida, pp. 32-41 (Jan. 21-24, 1996).
Steensgaard, Bjarne, "Points-to Analysis by Type Inference of Programs with Structures and Unions," Lecture Notes on Computer Science, vol. 1060, Proceedings of the 1996 International Conference on Compiler Construction, Linkobing, Sweden, pp. 136-150 (Apr. 24-26, 1996).
Talpin, Jean-Pierre, et al., Syntactic Control of Type Polymorphism for Recursive Function Definitions, Technical Report ECRC-94-29, European Computer-Industry Research Centre GmbH, pp. I-III, 1-15, and i-xiv (Jul. 1994, Revised Feb. 1995).
Talpin, Jean-Pierre, et al., "Syntactic Type Polymorphism for Recursive Function Definitions," Workshop on Types for Program Analysis, pp. 80-94 (May 26-27, 1995).
Tarjan, Robert E., Data Structures and Network Algorithms, Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial and Applied Mathematics (SIAM), Table of Contents, pp. v-vi (1983).
Tofte, Mads, et al., "Implementation of the Typed Call-by-Value .lambda.-calculus using a Stack of Regions," Proceedings of the 21st ACM Sigplan-Sigact Symposium on Principles of Programming Languages, Portland, Oregon, pp. 188-201 (Jan. 17-21, 1994).
Weihl, William E., "Interprocedural Data

Affiliated with

Also associated with

Rating

Terminating polymorphic type inference program analysis does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Terminating polymorphic type inference program analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Terminating polymorphic type inference program analysis will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1468578