Dynamic typing and type-based program analysis

Academic Journals

P. Wadler, R. Findler. Well-typed programs cant be blamed. Programming Languages and Systems, pages 1-16, 2009.
J. Siek, R. Garcia, W. Taha. Exploring the design space of higher-order casts. Programming Languages and Systems, pages 17-31, 2009.
Jan Midtgaard, David van Horn. Subcubic Control Flow Analysis Algorithms. Higher-order and Symbolic Computation (HOSC), 2009.
P. Meunier, R.B. Findler, P. Steckler, M. Wand. Selectors make set-based analysis too hard. Higher-Order and Symbolic Computation, 18(3):245-269, 2005.
H.G. Mairson. Functional pearl: Linear lambda calculus and PTIME-completeness. Journal of Functional Programming, 14(6):623-633, 2004.
David McAllester. On the complexity analysis of static analyses. J. ACM, 49(4):512-537, 2002. download
Robert Bruce Findler, Matthias Felleisen. Contracts for higher-order functions. SIGPLAN Notices, 37(9):48-59, 2002.
Manuel F\"ahndrich, Jakob Rehof, Manuvir Das. Scalable context-sensitive flow analysis using instantiation constraints. SIGPLAN Not, 35(5):253-263, 2000. download
Laurent Mauborgne. An Incremental Unique Representation for Regular Trees. Nordic Journal of Computing, 7(4):290-311, 2000.
Fritz Henglein. Breaking Through the $n^3$ Barrier: Faster Object Type Inference. Theory and Practice of Object Systems (TAPOS), Invited paper selected from 4th Int'l Workshop on Foundations of Object-Oriented Languages (FOOL), January 1997, Paris, France, 5(1):57-72, 1999.
Christian Mossin. Higher-Order Value Flow Graphs. Nordic Journal of Computing, 5:214-234, 1998.
Dexter Kozen, Jens Palsberg, Michael Schwartzbach. Efficient Recursive Subtyping. Mathematical Structures in Computer Science (MSCS), Conference version presented at the 20th Annual ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages (POPL), 1993, 5(1), 1995.
Jens Palsberg. Efficient inference of object types. Information and Computation, 123(2):198-209, 1995.
Fritz Henglein. Dynamic Typing: Syntax and Proof Theory. Science of Computer Progamming (SCP), 22(3):197-230, 1994.
Jens Palsberg, Michael I. Schwartzbach Dexter Kozen. Efficient Inference of Partial Types. Journal of Computer and Systems Sciences, Also presented at IEEE Symp. on Foundations of Computer Science 1992, 49(2), 1994.
Anders Bondorf, Jesper J\orgensen. Efficient Analysis for Realistic Off-Line Partial Evaluation. Journal of Functional Programming (JFP), 3(3):315-346, 1993.
Jens Palsberg. Normal Forms have Partial Types. Information Processing Letters, 1992.
M. Abadi, L. Cardelli, B. Pierce, G. Plotkin. Dynamic Typing in a Statically Typed Language. ACM Transactions on Programming Languages and Systems (TOPLAS), Presented at POPL '89, 13(2):237-268, April 1991.
K. Ma, R. Kessler. TICL - A Type Inference System for Common Lisp. Software Practice & Experience, 1990.
J. Schwartz. Optimization of Very High Level Languages - I: Value Transmission and its Corollaries. J. Computer Languages, 1:161-194, 1975.
J. Schwartz. Optimization of Very High Level Languages - II: Deducing Relationships of Inclusion and Membership. J. Computer Languages, 1:197-218, 1975.

Book Chapters

Fritz Henglein, Henning Makholm, Henning Niss. Effect type systems and region-based memory management. In Advanced Topics in Types and Programming Languages, Benjamin Pierce (ed.), MIT Press, 2005.
O. Shivers. Data-Flow Analysis and Type Recovery in Scheme. In Topics in Advanced Language Implementation, P. Lee (ed.), Chap. 3, pp. 47-88, MIT Press, 1991.
P. Steenkiste. The Implementation of Tags and Run-Time Type Checking. In Topics in Advanced Language Implementation, P. Lee (ed.), Chap. 7, pp. 157-188, MIT Press, 1991.
D. Matthews. Static and Dynamic Type Checking. F. Bancilhon, P. Buneman (eds.), Chap. 4, pp. 67-73, Frontier Series, Addison-Wesley, ACM Press, 1990.
N. Jones. Flow Analysis of Lazy Higher-Order Functional Programs. S. Abramsky, C. Hankin (eds.), Chap. 5, pp. 103-122, John Wiley and Sons, 1987.
N. Jones, S. Muchnick. Flow Analysis and Optimization of LISP-like Structures. In Program Flow Analysis: Theory and Applications, Prentice-Hall, 1981.
N. Jones, S. Muchnick. Complexity of Flow Analysis, Inductive Assertion Synthesis and a Language Due to Dijkstra. S. Muchnick, N. Jones (eds.), Chap. 12, pp. 380-393, North-Holland, 1979.

International Conferences

Sam Tobin-Hochstadt, Matthias Felleisen. Logical types for untyped languages. In Proceedings of the 15th ACM SIGPLAN international conference on Functional programming, ICFP '10, Pages 117-128, New York, NY, USA, 2010. download
Tobias Wrigstad, Francesco Zappa Nardelli, Sylvain Lebresne, Johan \"Ostlund, Jan Vitek. Integrating typed and untyped code in a scripting language. In POPL '10: Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, Pages 377-388, New York, NY, USA, 2010. download
Jeremy G. Siek, Philip Wadler. Threesomes, with and without blame. In POPL '10: Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, Pages 365-376, New York, NY, USA, 2010. download
Michael Greenberg, Benjamin C. Pierce, Stephanie Weirich. Contracts made manifest. In POPL '10: Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, Pages 353-364, New York, NY, USA, 2010. download
J.G. Siek, M. Vachharajani. Gradual typing with unification-based inference. In Proceedings of the 2008 symposium on Dynamic languages, Pages 1-12, 2008.
Sam Tobin-Hochstadt, Matthias Felleisen. The design and implementation of typed scheme. In Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL '08, Pages 395-406, New York, NY, USA, 2008. download
David Van Horn, Harry G. Mairson. Deciding kCFA is complete for EXPTIME. In ICFP '08: Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, Pages 275-282, New York, NY, USA, 2008. download
David Van Horn, Harry G. Mairson. Relating complexity and precision in control flow analysis. In ICFP '07: Proceedings of the 12th ACM SIGPLAN international conference on Functional programming, Pages 85-96, New York, NY, USA, 2007. download
Robert Bruce Findler, Matthias Blume. Contracts as Pairs of Projections. In FLOPS, Pages 226-241, 2006.
B. De Sutter, F. Tip, J. Dolby. Customization of Java library classes using type constraints and profile information. In ECOOP 2004-Object-Oriented Programming, Pages 584-608, 2004.
F. Tip, A. Kiezun, D. B�umer. Refactoring for generalization using type constraints. In Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, 2003.
Jakob Rehof, Manuel F�hndrich. Type-base flow analysis: from polymorphic subtyping to CFL-reachability. In POPL, Pages 54-66, 2001. download
Nevin Heintze, David McAllester. Linear time subtransitive control flow analysis. In Proc.\ ACM SIGPLAN Conf.\ on Programming Language Design and Implementation (PLDI), Pages 261-272, http://www.acm.org, 1997.
Nevin Heintze, David McAllester. On the Complexity of Set-Based Analysis. In Proc.\ Int'l Conf.\ on Functional Programming (ICFP), Amsterdam, The Netherlands, Pages 150-163, 1997.
Cormac Flanagan, Matthias Felleisen. Componential set-based analysis. In Proc.\ ACM SIGPLAN '97 Conference on Programming Language Design and Implementation (PLDI), June 1997.
Nevin Heintze, David McAllester. On the Cubic Bottleneck in Subtyping and Flow Analysis. In Proc. 22nd Annual IEEE Symp. on Logic in Computer Science (LICS), Warsaw, Poland, June 1997.
S. Marlow, P. Wadler. A practical subtyping system for Erlang. In Proc.\ 2nd International Conference on Functional Programming (ICFP), Amsterdam, The Netherlands, June 1997.
Fritz Henglein. Breaking through the $n^3$ barrier: Faster object type inference. In Proc.\ 4th Int'l Workshop on Foundations of Object-Oriented Languages (FOOL), Paris, France, Benjamin Pierce (ed.), Also DIKU TOPPS Report D-317, January 1997.
Manuel F\"ahndrich, Alex Aiken. Making set-constraint program analyses scale. In Proc. Workshop on Set Constraints, Cambridge, Massachussetts, 1996.
J. Michael Ashley. A Practical and Flexible Flow Analysis for Higher-Order Languages. In Proc.\ 23d Annual ACM Symposium on Principles of Programming Languages (POPL), St.\ Petersburg, Florida, Pages 184-193, January 1996.
Bjarne Steensgaard. Points-to Analysis in Almost Linear Time. In Proc. 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, St.\ Petersburg, Florida, January 1996.
Suresh Jagannathan, Stephen Weeks. A Unified Treatment of Flow Analysis in Higher-Order Languages. In POPL, Pages 393-407, 1995.
Nevin Heintze. Control-Flow Analysis and Type Systems. In Proc. Static Analysis Symposium (SAS), Glasgow, Scotland, Alan Mycroft (ed.), Lecture Notes in Computer Science (LNCS), Volume 983, Pages 189-206, 1995.
O. Agesen. The Cartesian Product Algorithm. In Proc. 9th European Conference on Object-Oriented Programming (ECOOP), Lecture Notes in Computer Science (LNCS), Pages 2-26, Aarhus, Denmark, August 1995.
Fritz Henglein, Jakob Rehof. Safe polymorphic type inference for a dynamically typed language: Translating Scheme to ML. In FPCA '95: Proceedings of the seventh international conference on Functional programming languages and computer architecture, Pages 192-203, New York, NY, USA, June 1995. download
Alex Aiken, Manuel F\"ahndrich. Dynamic typing and subtype inference. In Proc. ACM Conf.\ on Functional Programming Languages and Computer Architecture (FPCA), La Jolla, California, June 1995.
Jens Palsberg, Patrick O'Keefe. A Type System Equivalent to Flow Analysis. In Proc. 22nd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages (POPL), San Francisco, California, Pages 367-378, acmpubs@acm.org, January 1995.
Thomas Reps, Mooly Sagiv, Susan Horwitz. Precise Interprocedural Dataflow Analysis via Graph Reachability. In Proc. 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), San Francisco, California, Pages 49-61, January 1995.
Andrew K. Wright, Robert Cartwright. A Practical Soft Type System for Scheme. In Proc. ACM Symp. on LISP and Functional Programming (LFP), Orlando, Florida, 1994.
Jens Palsberg. Efficient type inference of object types. In Proc. 9th Annual IEEE Symp. on Logic in Computer Science (LICS), Paris, France, Pages 186-195, July 1994.
Nevin Heintze. Set Based Analysis of ML Programs. In Proc. ACM Conf. on LISP and Functional Programming (LFP), Orlando, Florida, Pages 306-317, June 1994.
Fritz Henglein, Christian Mossin. Polymorphic Binding-Time Analysis. In Proc. European Symposium on Programming (ESOP), Edinburgh, Scotland, Pages 287-301, April 1994.
Fritz Henglein, Jesper J\orgensen. Formally optimal boxing. In POPL '94: Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, Also DIKU Semantics Report D-179, Pages 213-226, New York, NY, USA, January 1994. download
Alexander Aiken, Edward L. Wimmers, T.K. Lakshman. Soft Typing with Conditional Types. In Proc. 21st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), Portland, Oregon, January 1994.
Dhananjay Dhamdhere, Uday Khedker. Complexity of Bi-Directional Data Flow Analysis. In Proc. 20th Annual ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, Pages 397-408, January 1993.
Dexter Kozen, Jens Palsberg, Michael Schwartzbach. Efficient Recursive Subtyping. In Proc. 20th Annual ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, Pages 419-428, January 1993.
Mario S� dholt, Ch. Steigner. On Interprocedural Data Flow Analysis for Object-Oriented Languages. In Proc. 4th Int'l Conf. on Compiler Construction (CC), Paderborn, Germany, U. Kastens, P. Pfahler (eds.), Lecture Notes in Computer Science, Vol. 641, Pages 156-162, October 1992.
Yan-Mei Tang, Pierre Jouvelot. Control-Flow Effects for Escape Analysis. In Proc. Workshop on Static Analysis (WSA), Bordeaux, France, Pages 313-321, September 1992.
Andrew Ayers. Efficient Closure Analysis with Reachability. In Proc. Workshop on Static Analysis (WSA), Bordeaux, France, Pages 126-134, September 1992.
Fritz Henglein. Global tagging optimization by type inference. In LFP '92: Proceedings of the 1992 ACM conference on LISP and functional programming, Also DIKU Semantics Report D-102, Pages 205-215, New York, NY, USA, June 1992. download
M. Abadi, L. Cardelli, B. Pierce, D. R�my. Dynamic Typing in Polymorphic Languages. In Proc. ACM SIGPLAN Workshop on ML and its Applications (ML), San Francisco, California, See also full journal version, JFP 1995, same name, Pages 92-103, June 1992.
Fritz Henglein. Dynamic Typing. In Proc. European Symp. on Programming (ESOP), Rennes, France, Pages 233-253, February 1992.
J. Palsberg, M. Schwartzbach. Object-Oriented Type Inference. In Proc. Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), Phoenix, Arizona, Pages 146-161, October 1991.
Fritz Henglein. Efficient Type Inference for Higher-Order Binding-Time Analysis. In Proc. Conf. on Functional Programming Languages and Computer Architecture (FPCA), Cambridge, Massachusetts, Pages 448-472, August 1991.
X. Leroy, M. Mauny. Dynamics in ML. In Proc. Conf. on Functional Programming Languages and Computer Architecture (FPCA), Cambridge, Massachusetts, Lecture Notes in Computer Science, Vol. 523, Pages 406-426, August 1991.
R. Cartwright, M. Fagan. Soft Typing. In Proc. ACM SIGPLAN '91 Conf. on Programming Language Design and Implementation, Toronto, Ontario, Pages 278-292, June 1991.
T. Freeman, F. Pfenning. Refinement types for ML (Extended Abstract). In Proc. ACM SIGPLAN '91 Conf. on Programming Language Design and Implementation, Toronto, Ontario, Pages 268-277, June 1991.
O. Shivers. The Semantics of Scheme Control-Flow Analysis. In Proc. Symp. on Partial Evaluation and Semantics-Based Program Manipulation (PEPM), New Haven, Connecticut, Pages 190-198, June 1991.
A. Aiken, B. Murphy. Static Type Inference in a Dynamically Typed Language. In Proc. 18th Annual ACM Symp. on Principles of Programming Languages, Orlando, Florida, Pages 279-290, January 1991.
J. Palsberg, M. Schwartzbach. Type Substitution for Object-Oriented Programming. In Proc. Conf. Object-Oriented Programming: Systems, Languages, and Applications and European Conf. on Object-Oriented Programming, N. Meyrowitz (ed.), Pages 151-160, Ottawa, Canada, October 1990.
C. Gomard. Partial Type Inference for Untyped Functional Programs (Extended Abstract). In Proc. LISP and Functional Programming (LFP), Nice, France, July 1990.
S. Thatte. Quasi-Static Typing. In Proc. ACM Symp. on Principles of Programming Languages, Pages 367-381, January 1990.
J. Graver, R. Johnson. A Type System for Smalltalk. In Proc. ACM Symp. on Principles of Programming Languages, January 1990.
M. Abadi, L. Cardelli, B. Pierce, G. Plotkin. Dynamic Typing in a Statically-Typed Language. In Proc. 16th Annual ACM Symp. on Principles of Programming Languages, Pages 213-227, January 1989.
S. Thatte. Type Inference with Partial Types. In Proc. Int'l Coll. on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, Pages 615-629, 1988.
David Callahan. The Program Summary Graph and Flow-sensitive Interprocedural Data Flow Analysis. In Proc. SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), Atlanta, Georgia, Pages 47-56, June 1988.
O. Shivers. Control Flow Analysis in Scheme. In Proc. SIGPLAN '88 Conf. on Programming Language Design and Implementation, Pages 164-174, June 1988.
M. Montenyohl. Correct Flow Analysis in Continuation Semantics. In Proc. 15th Annual ACM Symp. on Principles of Programming Languages (POPL), San Diego, California, Pages 204-218, January 1988.
P. Steenkiste, J. Hennessy. Tags and Type Checking in LISP: Hardware and Software Approaches. In Proc. 2nd Int'l Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), October 1987.
M. Wand. Finding the Source of Type Errors. In Proc. IEEE Symp. on Logic in Computer Science, Pages 38-43, June 1986.
N. Jones, A. Mycroft. Data Flow Analysis of Applicative Programs Using Minimal Function Graphs (Abridged Version). In Proc. 13th Annual ACM Symposium on Principles of Programming Languages, Pages 296-306, January 1986.
G. Johnson, J. Walz. A Maximum-Flow Approach to Anomaly Isolation in Unification-Based Incremental Type Inference. In Proc. 13th Annual ACM Symp. on Principles of Programming Languages, Pages 44-57, January 1986.
L. Meertens. Incremental Polymorphic Type Checking in B. In Proc. 10th ACM Symp. on Principles of Programming Languages (POPL), Pages 265-275, 1983.
N. Jones, S. Muchnick. A Flexible Approach to Interprocedural Data Flow Analysis and Programs with Recursive Data Structures. In Proc. ACM Symp. on Principles of Programming Languages, Pages 66-74, January 1982.
J. Reynolds. Automatic Computation of Data Set Definitions. In Proc. IFIP Congress 68, Edinburgh, Scotland, August 1968.

Technical Reports

Cormac Flanagan, Matthias Felleisen. Modular and Polymorphic Set-Based Analysis: Theory and Practice. Research Report Department of Computer Science, Rice University, No 0, November 1996.
Andrew K. Wright, Robert Cartwright. A Practical Soft Type System for Scheme. Research Report Rice University, No 0, December 1993.
Fritz Henglein. Dynamic Typing: Syntax and Proof Theory. TOPPS Report D-163 Department of Computer Science, University of Copenhagen (DIKU), March 1993.
Hans Lei\ss. Combining Recursive and Dynamic Types. Research Report CIS, Universit\"at M\"unchen, No 92, October 1992.
Dexter Kozen, Jens Palsberg, Michael Schwartzbach. Efficient Recursive Subtyping. Research Report DAIMI, Aarhus University, No 0, July 1992.
Dexter Kozen, Jens Palsberg, Michael Schwartzbach. Efficient Inference of Partial Types. Research Report DAIMI, Aarhus University, No 0, April 1992.
Fritz Henglein. Simple Closure Analysis. TOPPS Report D-193 Department of Computer Science, University of Copenhagen (DIKU), March 1992.
J. Palsberg, M. Schwartzbach. Safety Analysis versus Type Inference. Research Report DAIMI, Aarhus University, No 0, March 1992.
J. Palsberg, M. Schwartzbach. Polyvariant Analysis of the Untyped Lambda Calculus. Research Report DAIMI, Aarhus University, No 0, February 1992.
Fritz Henglein. Global Tagging Optimization by Type Inference. TOPPS Report D-102 Department of Computer Science, University of Copenhagen (DIKU), November 1991.
J. Palsberg, M. Schwartzbach. Object-Oriented Type Inference. Research Report DAIMI, Aarhus University, No 0, March 1991.
J. Palsberg, M. Schwartzbach. Object-Oriented Type Inference. Research Report DAIMI, Aarhus University, No 0, March 1991.
Fritz Henglein. Dynamic Typing. TOPPS Report D-90 Department of Computer Science, University of Copenhagen (DIKU), March 1991. download
O. Shivers. Data-Flow Analysis and Type Recovery in Scheme. Research Report Carnegie Mellon University, No 0, March 1990.
K. Walker. A Type Inference System for Icon. Research Report University of Arizona, No 88, July 1988.
N. Jones. Flow Analysis of Lambda Expressions. Research Report Aarhus University, No 0, January 1981.
W. Tsui. A Reformulation of Value-Flow Analysis. SETL Newsletter New York University, No 181, March 1977.

Miscellaneous

Christian Mossin. Exact Flow Analysis. Manuscript, 1997.
Anindya Banerjee. A Modular, Polyvariant and Type-based Closure Analysis. Manuscript, November 1996.

Dissertations

Christian Mossin. Flow Analysis of Typed Higher-Order Programs. PhD Thesis DIKU, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen, Denmark, 1997.
Andrew Wright. Practical Soft Typing. PhD Thesis Rice University, 1994.
C. Gomard. Program Analysis Matters. PhD Thesis University of Copenhagen, Dept. of Computer Science (DIKU), December 1991.
Olin Grigsby Shivers. Control-Flow Analysis of Higher-Order Languages or Taming Lambda. PhD Thesis Carnige-Mellon Univeristy, May 1991.
Mike Fagan. Soft Typing: An Approach to Type Checking for Dynamically Typed Languages. PhD Thesis Rice University, 1990.

Master's thesis

Gordon Gran. A Type-Theoretic Approach to Conditional Types. Master's theses DIKU, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen, Denmark, August 1998.
Jakob Rehof. Polymorphic Dynamic Typing - Aspects of Proof Theory and Inference. Master's theses DIKU, University of Copenhagen, March 1995.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.