johng@cs.qmw.ac.uk (John Goodwin) (08/03/90)
Ages ago I sent a message asking if anyone had a bibliography
on abstract interpretation or any references. Anyway thank you
very much to all the people that replied, sorry the summary is so late.
-------------------------------
-From: Ken Mcdonald <mcdonald@cs.sfu.ca>
-
-The standard starting point for AI (no, not that other junk--the REAL
-stuff) is the book edited by Hankin and Abramsky, called something along
-the lines of, oh, "Abstract Interpretation." But you probably already know
-that.
- I don't know of a bibliography for this particular field, which is, after
-all, very underdeveloped. The most recent FPCA had some papers on
-various aspects of AI, and I suspect you best bet might be just to collect
-all of the recent proceeding, journals, etc. aimed specifically at
-functional language types and go through them.
-
-Hope this helped (though it probably didn't)
-Ken McDonald
-mcdonald@cs.sfu.ca
-------------------------------
-From: Tony Davie <ad@cs.st-and.ac.uk>
-
-I have a very long bibliography on functional programming as a whole
-which contains a good abstract interpretation subset (at least as applied
-to functional programming --- strictness analysis, path analysis etc.
-It's two linked
-Hypercard stacks, so if you send me enough Mac discs to put them on
-(288K and 488K at the last count) I can send them back.
-
-
-Tony Davie
-Department of Mathematical and Computational Sciences
-Computational Science Division
-North Haugh
-St. Andrews University
-St. Andrews
Refs. only found in this bibliography: (bet there are loads more I missed,
its a huge thing!)
Hudak,P
"A Set-theoretic characterization of function strictness in the lambda
calculus"
Yale University Technical Report YALEU/DCS/TR--391, 1985
Jones,D and Muchnick,S
"A Flexible Approach to Interprocedural Flow Analysis and Programs with Recursive Data"
Proc. 9th ACM Symp. on Principles of Programming Languages, Albuquerque, 1982
Maurer,D
"Strictness Computation Using Special Lambda-Expressions"
In Lecture Notes in Computer Science Vol. 217, Springer-Verlag, Ed. Harald Ganzinger and Neil Jones --- Proc. Workshop on Programs
-------------------------------
-From: jnino@cs.utexas.edu
-
-There is a collection of papers on the subject in the following book :
- Abstract Interpretation of declarative languages
- S. Abramsky, Hanking eds.
- Publisher Chichester, West Sussex, England. E. Horwood
- ISBN 07 45801099
-
-Would you please send me a copy of your summary to :
- jncs@uno.bitnet
-
-Thanks,
-
-Jaime Nino
-------------------------------
-From: Flemming Nielson <fn@daimi.dk>
-
-I published a bibliography some years ago in:
- - ACM Sigplan Notices vol. 21 no. 5 pp. 31-38, 1986
- - Bulletin of the EATCS vol. 28, 1986.
-
-Sincerely
-
-Flemming Nielson
-
-
------ Address: ---------------------------------------------------
-Computer Science Department, Aarhus University, Ny Munkegade 116,
-DK-8000 Aarhus C, DENMARK. --- Tlph: +45 86 12 71 88 ext. 5213.
-[Fax:+4586135725][E-mail:fnielson@daimi.dk][Telex:64767 aausci dk]
-------------------------------------------------------------------
-------------------------------
-From: Mizuhito OGAWA <@relay.cs.net:mizuhito@lucifer.ntt.jp>
-
-Dear Mr. Goodwin,
-
-There are many articles on abstract interpretation to follow original papers- :
-
-@inproceedings{Cousot77
-AUTHOR = "Cousot,P. and Cousot,R.",
-TITLE = "Abstract Interpretation : A Unified Lattice Model for Static
-Analysis of Programs by Construction or Approximation of Fixpoints",
-BOOKTITLE = "ACM Symposium on Principles of Programming Languages",
-YEAR = "1977", PAGES = "238--252",
-ORGANIZATION = "ACM"}
-
-@inproceedings{Mycroft80
-AUTHOR = "Mycroft,A.",
-TITLE = "The theory and practice of transforming call-by-need into
-call-by-value",
-BOOKTITLE = "International Symposium on Programming (LNCS)",
-YEAR = "1980", VOLUME = "83", PAGES = "269--281",
-PUBLISHER = "Springer-Verlag"}
-
-Those what published until around 1985 are resumed in
-
-[1]
-@techreport{Nielson
-AUTHOR = "Nielson,F.",
-TITLE = "A Bibliography on abstract interpretation",
-INSTITUTION = "ACM SIGPLAN Notices", YEAR = "1986",
-VOLUME = "21", NUMBER = "5",
-PAGES = "31--38"}
-
-Later in 1987, a collection of papers is published from Ellis Horwood Limite-d.
-
-[2]
-@incollection{Abramsky
-BOOKTITLE = "Abstract interpretation of declarative languages",
-PUBLISHER = "Ellis Horwood Limited",
-EDITOR = "Abramsky,S. and Hankin,C.",
-YEAR = "1987"}
-
-Follows are papers not included in [1] (but may duplicate with [2])
-after 1985 until 1988. Further recent papers (1988-1989) may be found
-in proceedings of POPL (ACM symposium on Principles of Programming Languages-),
-LFP (ACM conference on LISP and Functional Languages),
-FPCA (Functional Programming Languages and Computer Architecture), etc.
-
-
- Mizuhito Ogawa (NTT Software Laboratories)
- 3-9-11 Midori-cho Musashino-shi
- Tokyo, 180 Japan
- phone : +81-422-59-3048
- e.mail : mizuhito%lucifer.ntt.jp@relay.cs.net
-
------------------ Cut here (BibTEX format) ------------------------------------
% Bibliography
@techreport{Nielson
AUTHOR = "Nielson,F.",
TITLE = "A Bibliography on abstract interpretation",
INSTITUTION = "ACM SIGPLAN Notices", YEAR = "1986",
VOLUME = "21", NUMBER = "5",
PAGES = "31--38"}
@incollection{Abramsky
BOOKTITLE = "Abstract interpretation of declarative languages",
PUBLISHER = "Ellis Horwood Limited",
EDITOR = "Abramsky,S. and Hankin,C.",
YEAR = "1987"}
% Abstract interpretation
@inproceedings{Bloss87
AUTHOR = "Bloss,A., and Hudak,P.",
TITLE = "Path Semantics",
BOOKTITLE = "Mathematical Foundations of Programming Language Semantics
(LNCS)",
VOLUME = "298", YEAR = "1987", PAGES = "476--489",
PUBLISHER = "Springer-Verlag"}
@phdthesis{Burn87
AUTHOR = "Burn,G.L.",
TITLE = "Abstract Interpretation and the Parallel Evaluation of Functional
Languages",
SCHOOL = "Imperial Collage", YEAR = "1987"}
@inproceedings{Dybjer87
AUTHOR = "Dybjer,P.",
TITLE = "Inverse Image Analysis",
BOOKTITLE = "International Colloquium on Automata, Languages,
and Programming ({\sl LNCS\/})", YEAR = "1987",
VOLUME = "267", PAGES = "21--30",
PUBLISHER = "Springer-Verlag"}
@inproceedings{Hudak87
AUTHOR = "Hudak,P., Anderson,S.",
TITLE = "Pomset Interpretations of Parallel Functional Programs",
BOOKTITLE = "Functional Programming Languages and Computer Architecture
(LNCS)",
VOLUME = "274", YEAR = "1987", PAGES = "234--256",
PUBLISHER = "Springer-Verlag"}
@inproceedings{Hudak88
AUTHOR = "Hudak,P. and Young,J.",
TITLE = "A Collecting Interpretation of Expressions (Without Powerdomains)
-Preliminary Report-",
BOOKTITLE = "ACM SIGACT-SIGPLAN Symposium on Principles
of Programming Languages", YEAR = "1988", PAGES = "107--118",
ORGANIZATION = "ACM"}
@inproceedings{Hughes87
AUTHOR = "Hughes,J.",
TITLE = "Backwards Analysis of Functional Programs",
BOOKTITLE = "Partial Evaluation and Mixed Computation",
YEAR = "1987", PAGES = "1--29"}
@inproceedings{Mycroft85
AUTHOR = "Mycroft,A. and Jones,N.",
TITLE = "A relational framework for abstract interpretation",
BOOKTITLE = "Workshop on Programs as Data Objects (LNCS)",
VOLUME = "217", YEAR = "1985", PAGES = "156--171",
PUBLISHER = "Springer-Verlag"}
@inproceedings{Nielson87
AUTHOR = "Nielson,F.",
TITLE = "Strictness Analysis and Denotational Abstract Interpretation",
BOOKTITLE = "ACM Symposium on Principles of Programming Languages",
YEAR = "1987", PAGES = "120--131",
ORGANIZATION = "ACM"}
@article{Nielson88
AUTHOR = "Nielson,F.",
TITLE = "Strictness Analysis and Denotational Abstract Interpretation",
BOOKTITLE = "Information and Computation",
VOLUME = "76", YEAR = "1988", PAGES = "29--92"}
%
% Strictness analysis based on abstract interpretation
@inproceedings{Bloss86-SA
AUTHOR = "Bloss,B. and Hudak,P.",
TITLE = "Variations on strictness analysis",
BOOKTITLE = "ACM Conference on LISP and Functional Programming",
YEAR = "1986", PAGES = "132--142",
ORGANIZATION = "ACM"}
@inproceedings{Burn85-SA
AUTHOR = "Burn,G.L., Hankin,C.L., Abramsky,S.",
TITLE = "The Theory of Strictness Analysis for Higher Order Functions",
BOOKTITLE = "Workshop on Programs as Data Objects (LNCS)",
VOLUME = "217", YEAR = "1985", PAGES = "42--62",
PUBLISHER = "Springer-Verlag"}
@article{Burn86-SA
AUTHOR = "Burn,G.L., Hankin,C. and Abramsky,S.",
TITLE = "Strictness analysis for higher-order functions",
JOURNAL = "Science of Computer Programming",
YEAR = "1986",
VOLUME = "7", PAGES = "249--278",
PUBLISHER = "North-Holland"}
@inproceedings{Burn87-SA
AUTHOR = "Burn,G.L.",
TITLE = "Evaluation Transformers -- A Model for the Parallel Evaluation of
Functional Languages",
BOOKTITLE = "Functional Programming Languages and Computer Architecture
(LNCS)",
VOLUME = "274", YEAR = "1987", PAGES = "446--470",
PUBLISHER = "Springer-Verlag"}
@inproceedings{Hankin86-SA
AUTHOR = "Hankin,C.L.,Burn,G.L. and Peyton Jones,S.T.",
TITLE = "A Safe Approach to Parallel Combinator Reduction",
BOOKTITLE = "European Symposium on Programming (LNCS)",
VOLUME = "213", YEAR = "1986", PAGES = "99--110",
PUBLISHER = "Springer-Verlag"}
@article{Hankin88-SA
AUTHOR = "Hankin,C.L., Burn,G.L., and Peyton Jones,S.T.",
TITLE = "A Safe Approach to Parallel Combinator Reduction",
JOURNAL = "Theoretical Computer Science", YEAR = "1988",
VOLUME = "56", PAGES = "17--36",
PUBLISHER = "North-Holland"}
@inproceedings{Hudak86-SA
AUTHOR = "Hudak,P. and Young,R.",
TITLE = "Higher-order strictness analysis in untyped lambda calculus",
BOOKTITLE = "ACM SIGACT-SIGPLAN Symposium on Principles
of Programming Languages", YEAR = "1986", PAGES = "97--109",
ORGANIZATION = "ACM"}
@inproceedings{Hughes85-SA
AUTHOR = "Hughes,J.",
TITLE = "Strictness Detection in Non-Flat Domains",
BOOKTITLE = "Workshop on Programs as Data Objects (LNCS)",
YEAR = "1985", VOLUME = "217", PAGES = "112--135",
PUBLISHER = "Springer-Verlag"}
@inproceedings{Lindstrom86-SA
AUTHOR = "Lindstrom,G.",
TITLE = "Static Evaluation of Functional Programs",
BOOKTITLE = "ACM Symposium of Compiler Construction", YEAR = "1986",
VOLUME = "21", NUMBER = "7", ORGANIZATION = "ACM"}
@book{Peyton87-SA
AUTHOR = "Peyton Jones,S.T.",
TITLE = "The implementation of functional programming languages",
PUBLISHER = "Prentice-Hall", YEAR = "1987"}
@inproceedings{Wadler87-SA
AUTHOR = "Wadler,P., and Hughes,R.J.M.",
TITLE = "Projections for Strictness Analysis",
BOOKTITLE = "Functional Programming Languages and Computer Architecture
(LNCS)",
VOLUME = "274", YEAR = "1987", PAGES = "385--407",
PUBLISHER = "Springer-Verlag"}
%
% Side-effects analysis based on abstract interpretation
@inproceedings{Hudak85-side
AUTHOR = "Hudak,P.",
TITLE = "The Aggregate Update Problem in Functional Programming",
its Abstraction (Detailed Summary)",
BOOKTITLE = "ACM SIGACT-SIGPLAN Symposium on Principles
of Programming Languages",
YEAR = "1985", PAGES = "300--314",
ORGANIZATION = "ACM"}
@inproceedings{Hudak86-side
AUTHOR = "Hudak,P.",
TITLE = "A Semantic Model of Reference Counting and
its Abstraction (Detailed Summary)",
BOOKTITLE = "ACM Conference on LISP and Functional Programming",
YEAR = "1986", PAGES = "351--363",
ORGANIZATION = "ACM"}
%
% Theoretical foundation of abstract interpretation
@inproceedings{Martin87
AUTHOR = "Martin,C. and Hankin,C.",
TITLE = "Finding Fixed Points in Finite Lattices",
BOOKTITLE = "Functional Programming Languages and Computer
Architecture (LNCS)",
VOLUME = "274", YEAR = "1987", PAGES = "426--445",
PUBLISHER = "Springer-Verlag"}
@article{Smyth78
AUTHOR = "Smyth,M.B.",
TITLE = "Power Domains",
JOURNAL = "Journal of the Computer Systems and Science", YEAR = "1978",
VOLUME = "16", PAGES = "23--36"}
%
% Abstract Interpretation for Logic Programming
@inproceedings{Bruynooghe87
AUTHOR = "Bruynooghe,M., Demoen,B., Callebaut,A., and Janssens,G.",
TITLE = "Abstract interpretation : Towards the global optimization
of Prolog programs",
BOOKTITLE = "IEEE Symposium on Logic Programming",
YEAR = "1987",
ORGANIZATION = "IEEE"}
@article{Debray89
AUTHOR = "Debray,K.",
TITLE = "Static Inference of Modes and Data Dependencies in Logic Programs",
JOURNAL = "ACM Transactions on Programming Languages and Systems",
VOLUME = "11", NUMBER = "3", YEAR = "1989", PAGES = "418--450"
ORGANIZATION = "ACM"}
@inproceedings{Janssens88
AUTHOR = "Janssens,G., and Bruynooghe,M.",
TITLE = "An instance of abstract interpretation integrating type and
mode inferencing",
BOOKTITLE = "International Conference on Logic Programming",
YEAR = "1988", PAGES = "669--683"}
@inproceedings{Mellish86
AUTHOR = "Mellish,C.S.",
TITLE = "Abstract Interpretation on Prolog Programs",
BOOKTITLE = "Proc. of 3rd International Conference on Logic Programming
(LNCS)",
VOLUME = "225", YEAR = "1986", PAGES = "107--116",
PUBLISHER = "Springer-Verlag"}
@inproceedings{Sondergaard86
AUTHOR = "Sondergaard,H.",
TITLE = "An Application of Abstract Interpretation of Logic Programs :
Occur Check Reduction",
BOOKTITLE = "European Symposium on Programming (LNCS)",
VOLUME ="213", YEAR = "1986", PAGES = "327--338",
PUBLISHER = "Springer-Verlag"}
@inproceedings{Warren88
AUTHOR = "Warren,R., Hermenegildo,M., and Debray,S.K.",
TITLE = "On the practicality of global flow analysis of logic programs",
BOOKTITLE = "International Conference on Logic Programming",
YEAR = "1988"}
%
%Activity in Japan (Functional Programming)
@inproceedings{Katayama84
AUTHOR = "Katayama,T.",
TITLE = "Type Inference and Type Checking for Functional Programming
Languages --- A Reduced Computation Approach",
BOOKTITLE = "ACM Conference on LISP and Functional Programming",
YEAR = "1984", PAGES = "263--272"}
@techreport{Katayama
AUTHOR = "Katayama,T. and Luo,J.",
TITLE = "Type Inference of FP Programs on Heterogeneous Sequences",
INSTITUTION = "{\it Preprint}"}
@inproceedings{Ogawa88
AUTHOR = "Ogawa,M.~and Ono,S.",
TITLE = "Transformation of Strictness-Related Analyses based on
Abstract Interpretation",
BOOKTITLE = "International Conference on Fifth Generation Computer Systems
1988",
YEAR = "1988", PAGES = "430--438"}
@inproceedings{Ono86
AUTHOR = "Ono,S., Takahashi,N. and Amamiya,M.",
TITLE = "Optimized demand-driven evaluation of functional programs
on a dataflow machine",
BOOKTITLE = "ICPP", YEAR = "1986", PAGES = "421--428",
ORGANIZATION = "IEEE"}
@inproceedings{Ono87
AUTHOR = "Ono,S.",
TITLE = "Computation Path Analysis : Towards an Autonomous
Global Dataflow Analysis",
BOOKTITLE = "The Second France-Japan Aritificial Intelligence and
Computer Science Symposium ({\sl Sophia, France\/})",
YEAR = "1987"}
@techreport{Ono84
AUTHOR = "Ono,S., Takahashi,N.~and Amamiya,M.",
TITLE = "Non-strict partial computation with a dataflow machine",
INSTITUTION = "RIMS technical report, 6th RIMS Symposium
on mathematical methods in software science and engineering",
VOLUME = "547", PAGES = "196--229", YEAR = "1984"}
%Activity in Japan (Logic Programming)
@inproceedings{Horiuchi87
AUTHOR = "Horiuchi,K. and Kanamori,T.",
TITLE = "Polymorphic Type Inference in Prolog by Abstract Interpretation",
BOOKTITLE = "Proc. of The Logic Programming Conference",
YEAR = "1987", PAGES = "107--116",
ORGANIZATION = "ICOT, Japan"}
@techreport{Kawamori87
AUTHOR = "Kanamori,T. and Kawamura,T.",
TITLE = "Analyzing Success Patterns of Logic Programs by Abstract
Hybrid Interpretation"}
INSTITUTION = "ICOT Technical Report",
VOLUME = "TR-279", YEAR = "1987"}
%
% P.S. Articles appears in [1]
@inproceedings{Cousot77
AUTHOR = "Cousot,P. and Cousot,R.",
TITLE = "Abstract Interpretation : A Unified Lattice Model for Static
Analysis of Programs by Construction or Approximation of Fixpoints",
BOOKTITLE = "ACM Symposium on Principles of Programming Languages",
YEAR = "1977", PAGES = "238--252",
ORGANIZATION = "ACM"}
@inproceedings{Mycroft80
AUTHOR = "Mycroft,A.",
TITLE = "The theory and practice of transforming call-by-need into
call-by-value",
BOOKTITLE = "International Symposium on Programming (LNCS)",
YEAR = "1980", VOLUME = "83", PAGES = "269--281",
PUBLISHER = "Springer-Verlag"}
@inproceedings{Clack85
AUTHOR = "Clack,C. and Peyton Jones,S.L.",
TITLE = "Strictness analysis -- a practical approach",
BOOKTITLE = "Functional Programming Languages and Computer Architecture
(LNCS)",
VOLUME = "201", YEAR = "1985", PAGES = "35--49",
PUBLISHER = "Springer-Verlag"}
@inproceedings{Mishra84
AUTHOR = "Mishra,P. and Keller,A.M.",
TITLE = "Static Inference of Properties of Applicative Programs",
BOOKTITLE = "ACM SIGACT-SIGPLAN Symposium on Principles
of Programming Languages", YEAR = "1984",
PAGES = "235--244",
ORGANIZATION = "ACM"}
--------------------------------------------------------------
-From: Sebastian Hunt <lsh@doc.ic.ac.uk>
-
-Flemming Nielson has published an abstract interpretation bibliography.
-I haven't seen it, but it's bound to be pretty comprehensive. The
-reference is:
-
- Flemming Nielson,
- A bibliography on abstract interpretation,
- ACM SIGPLAN Notices 21 (1986) 31-38, and Bull. EATCS 28 (1986) 45-52.
-
-Incidentally, I took that reference from:
-
- Flemming Nielson,
- Two-level semantics and abstract interpretation,
- Theoretical Computer Science 69 (1989) 117-242,
- North Holland
-
-Hope that's of some help,
-
-Sebastian Hunt Tel: 071-589-5111 ext. 4993
-Department of Computing Janet: lsh@doc.ic.ac.uk
-Imperial College
-180 Queen's Gate
-London SW7 2BZ
-------------------------------
Other papers I found that looked abstract interpretation-like (havn't looked
in Lisp and FP 88, 90 or POPL 90 or other places so this is bound to be very
incomplete)
Abramsky,S
"Strictness analysis and polymorphic invariance"
Workshop on Programs as Data Objects 1985 (LNCS 217)
Jones,N and Mycroft,A
"Data flow analysis of applicative programs using minimal function graphs"
ACM Symposium on Principles of Programming Languages 1986
Goldberg,B
"Detecting sharing of partial applications in functional programs"
Functional Programming and Computer Architecture 1987 (LNCS 274)
Hudak,P and Goldberg,B
"Serial combinators: optimal grains of parallelism"
Functional Programming and Computer Architecture 1985 (LNCS 217)
Wadler,P
"Strictness analysis aids time analysis"
ACM Symposium on Principles of Programming Languages 1988
in ACM Symposium on Functional Programming and Computer Architecture 1989:
Kuo,T and Mishra,P
"Strictness analysis: a new perspective based on type inference"
Jones,S and Metayer,D
"Compile-time garbage collection by sharing analysis"
Bloss,A
"Update analysis and the efficient implementation of functional aggregates"
Sestoft,P
"Replacing function parameters by global variables"
Hunt,S
"Frontiers and open sets in abstract interpretation"
Lester,D
"Stacklessness: compiling recursion for a distributed architecture"
Bjerner,B and Homlstrom,S
"A compositional approach to the time analysis of first order lazy functional
languages"