From: lorenz@natasha.cs.wisc.edu (Lorenz Huelsbergen)
Newsgroups: comp.lang.functional
Subject: Re: Abstractly Interpreting Lists
Date: 7 Sep 92 20:12:52 GMT
Organization: University of Wisconsin, Madison -- Computer Sciences Dept.

Below is a summary of the responses I received in reply to my query for 
abstract interpretation over non-flat domains.  Thanks to all who
responded.  Note that I did not remove duplicates from the summary.

Lorenz Huelsbergen

------------------------------------------------------------------------------
From Geoffrey L Burn (glb@doc.imperial.ac.uk):

	@phdthesis{HUNT91b,
	author = "L.S. Hunt",
	title = "Abstract Interpretation of Functional Languages: From
	         Theory to Practice",
	school = "Department of Computing, Imperial College of Science,
		  Technology and Medicine, University of London",
	year = 1991
	}

	(available ftp theory.doc.ic.ac.uk)

	@inproceedings{WADLER87a,
	author = "P. Wadler and R. J. M. Hughes",
	title = "Projections for Strictness Analysis",
	pages = "385--407",
	booktitle = "Proceedings of the Functional Programming Languages
		     and Computer Architecture Conference",
	editor = "G. Kahn",
	publisher = "Springer-Verlag LNCS 274",
	month = sep,
	year = 1987
	}

	@incollection{WADLER87b,
	author = "Wadler, P.L.",
	title = "Strictness Analysis on Non-flat Domains (by Abstract
		 Interpretation over Finite Domains)",
	booktitle = "Abstract Interpretation of Declarative Languages",
	publisher = "Ellis Horwood Ltd.",
	year = 1987,
	editor = "Abramsky, S. and Hankin, C.L.",
	chapter = 12,
	pages = "266--275",
	address = "Chichester, West Sussex, England",
	isbn = "ISBN 0-7458-0109-9"
	}

	Also Nielson and Nielson have done some work, as has
	Thomas Jensen (tpj@doc.ic.ac.uk).


Simon Hughes (tcssph@aie.lreg.co.uk):

	I guess someone must have told you about Wadler's original
	paper.  I can add to that my own PhD thesis

	S.P. Hughes
	Static Analysis of Store Use in Functional Programs
	University of London
	October 1991

	I don't actually formally (i.e. give abstraction and concretisation
	maps) express my static analyses as abstract interpretations and, in
	fact, it's quite fiddly and complex to do it but it's conceptually
	quite easy.

From Hanne Riis Nielson (hrn@daimi.aau.dk):

	I had a paper (jointly with F.Nielson) at ESOP92:

   	"The tensor product in Wadler's analysis of lists"
	See Springer LNCS vol. 582. It generalises Phil Wadler's
	construction from 1987 (reference 17 of the paper).

From Benjamin Goldberg (goldberg@GOLDBERG.CS.NYU.EDU):

	Tyng-Ruey Chuang and I have a paper on using symbolic
	manipulation to find fixed points of abstract functions
	(such as those generated by abstract interpretation). 
	A section of it discusses abstract interpretation for
	non-flat domains.

	    Chuang, T-R and Goldberg, B. "A syntactic approach to finding
  	    fixpoints on finite domains". Proc. 1992ACM Symposium on LISP 
	    and Functional Programming, June 1992.

From John Farrell (farrell@coral.cs.jcu.edu.au):

	"Abstract Interpretation and the Parallel Evaluation of 
	Functional Languages" Geoffrey Burn, Ph.D. thesis, 
	Imperial College London, March 1987.

	I have done some work on *backwards* analysis myself:

	"Context Approximation for Functional Languages"
	John Farrell, Ph.D. thesis submitted to the University of Queensland, 
	June 1992.

From Guido Hogen (ghogen@zeus.informatik.rwth-aachen.de):

	here are two references:

	Phil Wadler:
	Strictness analysis on non-flat domains (by Abstract
	interpretation over finite domains),
	in: S.Abramsky, C.Hankin (eds.):
	Abstract Interpretation of Declarative Languages,
	Ellis Horwood Limited~1987.

	G.Burn: 
	Evaluation Transformers --- A Model for the
	Parallel Evaluation of Functional Languages, 
	Conf. on Functional Progr.\ Lang.\ and
	Computer Architecture, LNCS~274, Springer Verlag~1987.

From Yamine Ait Ameur (yamine@tls-cs.cert.fr):

	Abstract interpretation of declarative languages.
   	edited by Samson Abramsky and Chris Hankin at Ellis Horwood 1987
	ISBN 0-7458-0109-9

From Pieter H. Hartel (pieter@fwi.uva.nl):

	@inproceedings{Gla90,
		author = {H. W. Glaser and P. H. Hartel and J. M. Wild},
		title = {A pragmatic approach to the analysis and compilation
			of lazy functional languages},
		booktitle = {2nd Parallel and distributed processing},
		editor = {K. Boyanov},
		publisher = {North Holland},
		pages = {169-184},
		address = {Sofia, Bulgaria},
		month = {Mar},
		year = 1990,
		annote = {refs}}

	@techreport{Har91,
		author = {P. H. Hartel and H. W. Glaser and J. M. Wild},
		title = {Compilation of functional languages using 
			 flow graph analysis},
		institution = {Dept. of Electr. and Comp. Sci, 
			       Univ. of Southampton, UK},
		type = {Technical report},
		number = {CSTR 91-03},
		month = {Jan},
		year = 1991,
		annote = {refs}}


	@inproceedings{Har91b,
		author = {P. H. Hartel and H. W. Glaser and J. M. Wild},
		title = {On the benefits of different analyses in the 
			 compilation of functional languages},
		booktitle = {Implementation of functional languages on parallel
			architectures},
		editor = {H. W. Glaser and P. H. Hartel},
		publisher = {CSTR 91-07, Dept. of Electr. and Comp. Sci,
			Univ. of Southampton, UK},
		pages = {123-145},
		address = {Southampton, UK},
		month = {Jun},
		year = 1991,
		annote = {refs}}

From Tony Davie (ajtd@st-andrews.ac.uk):

	S. Abramsky, C. Hankin
	Abstract Interpretation of Declarative Languages
	Ellis Horwood Ltd., 1987
	
	Geoffrey L. Burn, Chris L. Hankin, S. Abramsky
	The Theory and Practice of Strictness Analysis for 
		Higher Order Functions
	In LNCS 217, also Imperial College research report 85/6
	
	Geoffrey L. Burn, Chris L. Hankin, S. Abramsky
	Strictness Analysis for Higher Order Functions
	Science of Computer Programming, 7 pp249-278
	
	G.L. Burn
	Abstract Interpretation and the Parallel Evaluation of 
		Functional Languages
	ESPRIT Project 415 Report, Dept. Computing, Imperial College, 
		Ph.D. thesis, 1987
	
	G.L. Burn
	Lazy Functional Languages: Abstract Interpretation and Compilation
	Pitman in association with MIT press, 
		ISBN 0-273-08832-7, 0-262-52160-1, 1991
	
	G.L. Burn
	The Evaluation Transformer Model of Reduction and its Correctness
	TAPSOFT '91, LNCS 494, pp458-482
	
	C. Consel
	Binding Time Analysis for Higher Order Untyped Functional Languages
	In ACM Proceedings of the 1990 ACM Conference on LISP and 
		Functional Programming
	Nice, pp264-272
	
	C.A. Gunter, E.L. Gunter, D.B. MacQueen
	An Abstract Interpretation for ML Equality Types
	LNCS 526, pp112-130
	
	C. Hall
	Using Lazy Evaluation to Find Fixpoints in Infinite Domains
	Glasgow University Report?
	
	C.L. Hankin, G.L. Burn, S.L. Peyton Jones
	A Safe Approach to Parallel Combinator Redfuction
	ESOP 86, LNCS 213, pp99-109, 
	Also Theoretical Computer Science, 56:17-36, 1988
	
	C. Hankin
	Abstract Interpretation of term Graph Rewriting Systems
	In S.L. Peyton Jones, G. Hutton, C.K. Holst, Eds.
	Functional Programming, Glasgow 1990
	Springer Verlag, London, 1991, ISBN 3 540 19667 6, pp54-65
	
	P.L. Wadler
	Strictness Analysis on Non-Flat Domains by 
		Abstract Interpretation over Finite Domains
	Prog.In S. Abramsky, C. Hankin
	Abstract Interpretation of Declarative Languages
	Ellis Horwood Ltd. 1987

-- 

Lorenz Huelsbergen (lorenz@cs.wisc.edu)

Computer Sciences Department
University of Wisconsin
1210 W. Dayton Street
Madison, WI  53706  (USA)