home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / lang / function / 1074 < prev    next >
Encoding:
Internet Message Format  |  1992-09-08  |  7.5 KB
  1. Path: sparky!uunet!pmafire!news.dell.com!natinst.com!cs.utexas.edu!rutgers!uwvax!natasha.cs.wisc.edu!lorenz
  2. From: lorenz@natasha.cs.wisc.edu (Lorenz Huelsbergen)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: Abstractly Interpreting Lists
  5. Message-ID: <1992Sep7.201252.12560@cs.wisc.edu>
  6. Date: 7 Sep 92 20:12:52 GMT
  7. Sender: news@cs.wisc.edu (The News)
  8. Organization: University of Wisconsin, Madison -- Computer Sciences Dept.
  9. Lines: 233
  10.  
  11. Below is a summary of the responses I received in reply to my query for 
  12. abstract interpretation over non-flat domains.  Thanks to all who
  13. responded.  Note that I did not remove duplicates from the summary.
  14.  
  15. Lorenz Huelsbergen
  16.  
  17. ------------------------------------------------------------------------------
  18. From Geoffrey L Burn (glb@doc.imperial.ac.uk):
  19.  
  20.     @phdthesis{HUNT91b,
  21.     author = "L.S. Hunt",
  22.     title = "Abstract Interpretation of Functional Languages: From
  23.              Theory to Practice",
  24.     school = "Department of Computing, Imperial College of Science,
  25.           Technology and Medicine, University of London",
  26.     year = 1991
  27.     }
  28.  
  29.     (available ftp theory.doc.ic.ac.uk)
  30.  
  31.     @inproceedings{WADLER87a,
  32.     author = "P. Wadler and R. J. M. Hughes",
  33.     title = "Projections for Strictness Analysis",
  34.     pages = "385--407",
  35.     booktitle = "Proceedings of the Functional Programming Languages
  36.              and Computer Architecture Conference",
  37.     editor = "G. Kahn",
  38.     publisher = "Springer-Verlag LNCS 274",
  39.     month = sep,
  40.     year = 1987
  41.     }
  42.  
  43.     @incollection{WADLER87b,
  44.     author = "Wadler, P.L.",
  45.     title = "Strictness Analysis on Non-flat Domains (by Abstract
  46.          Interpretation over Finite Domains)",
  47.     booktitle = "Abstract Interpretation of Declarative Languages",
  48.     publisher = "Ellis Horwood Ltd.",
  49.     year = 1987,
  50.     editor = "Abramsky, S. and Hankin, C.L.",
  51.     chapter = 12,
  52.     pages = "266--275",
  53.     address = "Chichester, West Sussex, England",
  54.     isbn = "ISBN 0-7458-0109-9"
  55.     }
  56.  
  57.     Also Nielson and Nielson have done some work, as has
  58.     Thomas Jensen (tpj@doc.ic.ac.uk).
  59.  
  60.  
  61. Simon Hughes (tcssph@aie.lreg.co.uk):
  62.  
  63.     I guess someone must have told you about Wadler's original
  64.     paper.  I can add to that my own PhD thesis
  65.  
  66.     S.P. Hughes
  67.     Static Analysis of Store Use in Functional Programs
  68.     University of London
  69.     October 1991
  70.  
  71.     I don't actually formally (i.e. give abstraction and concretisation
  72.     maps) express my static analyses as abstract interpretations and, in
  73.     fact, it's quite fiddly and complex to do it but it's conceptually
  74.     quite easy.
  75.  
  76. From Hanne Riis Nielson (hrn@daimi.aau.dk):
  77.  
  78.     I had a paper (jointly with F.Nielson) at ESOP92:
  79.  
  80.        "The tensor product in Wadler's analysis of lists"
  81.     See Springer LNCS vol. 582. It generalises Phil Wadler's
  82.     construction from 1987 (reference 17 of the paper).
  83.  
  84. From Benjamin Goldberg (goldberg@GOLDBERG.CS.NYU.EDU):
  85.  
  86.     Tyng-Ruey Chuang and I have a paper on using symbolic
  87.     manipulation to find fixed points of abstract functions
  88.     (such as those generated by abstract interpretation). 
  89.     A section of it discusses abstract interpretation for
  90.     non-flat domains.
  91.  
  92.         Chuang, T-R and Goldberg, B. "A syntactic approach to finding
  93.           fixpoints on finite domains". Proc. 1992ACM Symposium on LISP 
  94.         and Functional Programming, June 1992.
  95.  
  96. From John Farrell (farrell@coral.cs.jcu.edu.au):
  97.  
  98.     "Abstract Interpretation and the Parallel Evaluation of 
  99.     Functional Languages" Geoffrey Burn, Ph.D. thesis, 
  100.     Imperial College London, March 1987.
  101.  
  102.     I have done some work on *backwards* analysis myself:
  103.  
  104.     "Context Approximation for Functional Languages"
  105.     John Farrell, Ph.D. thesis submitted to the University of Queensland, 
  106.     June 1992.
  107.  
  108. From Guido Hogen (ghogen@zeus.informatik.rwth-aachen.de):
  109.  
  110.     here are two references:
  111.  
  112.     Phil Wadler:
  113.     Strictness analysis on non-flat domains (by Abstract
  114.     interpretation over finite domains),
  115.     in: S.Abramsky, C.Hankin (eds.):
  116.     Abstract Interpretation of Declarative Languages,
  117.     Ellis Horwood Limited~1987.
  118.  
  119.     G.Burn: 
  120.     Evaluation Transformers --- A Model for the
  121.     Parallel Evaluation of Functional Languages, 
  122.     Conf. on Functional Progr.\ Lang.\ and
  123.     Computer Architecture, LNCS~274, Springer Verlag~1987.
  124.  
  125. From Yamine Ait Ameur (yamine@tls-cs.cert.fr):
  126.  
  127.     Abstract interpretation of declarative languages.
  128.        edited by Samson Abramsky and Chris Hankin at Ellis Horwood 1987
  129.     ISBN 0-7458-0109-9
  130.  
  131. From Pieter H. Hartel (pieter@fwi.uva.nl):
  132.  
  133.     @inproceedings{Gla90,
  134.         author = {H. W. Glaser and P. H. Hartel and J. M. Wild},
  135.         title = {A pragmatic approach to the analysis and compilation
  136.             of lazy functional languages},
  137.         booktitle = {2nd Parallel and distributed processing},
  138.         editor = {K. Boyanov},
  139.         publisher = {North Holland},
  140.         pages = {169-184},
  141.         address = {Sofia, Bulgaria},
  142.         month = {Mar},
  143.         year = 1990,
  144.         annote = {refs}}
  145.  
  146.     @techreport{Har91,
  147.         author = {P. H. Hartel and H. W. Glaser and J. M. Wild},
  148.         title = {Compilation of functional languages using 
  149.              flow graph analysis},
  150.         institution = {Dept. of Electr. and Comp. Sci, 
  151.                    Univ. of Southampton, UK},
  152.         type = {Technical report},
  153.         number = {CSTR 91-03},
  154.         month = {Jan},
  155.         year = 1991,
  156.         annote = {refs}}
  157.  
  158.  
  159.     @inproceedings{Har91b,
  160.         author = {P. H. Hartel and H. W. Glaser and J. M. Wild},
  161.         title = {On the benefits of different analyses in the 
  162.              compilation of functional languages},
  163.         booktitle = {Implementation of functional languages on parallel
  164.             architectures},
  165.         editor = {H. W. Glaser and P. H. Hartel},
  166.         publisher = {CSTR 91-07, Dept. of Electr. and Comp. Sci,
  167.             Univ. of Southampton, UK},
  168.         pages = {123-145},
  169.         address = {Southampton, UK},
  170.         month = {Jun},
  171.         year = 1991,
  172.         annote = {refs}}
  173.  
  174. From Tony Davie (ajtd@st-andrews.ac.uk):
  175.  
  176.     S. Abramsky, C. Hankin
  177.     Abstract Interpretation of Declarative Languages
  178.     Ellis Horwood Ltd., 1987
  179.     
  180.     Geoffrey L. Burn, Chris L. Hankin, S. Abramsky
  181.     The Theory and Practice of Strictness Analysis for 
  182.         Higher Order Functions
  183.     In LNCS 217, also Imperial College research report 85/6
  184.     
  185.     Geoffrey L. Burn, Chris L. Hankin, S. Abramsky
  186.     Strictness Analysis for Higher Order Functions
  187.     Science of Computer Programming, 7 pp249-278
  188.     
  189.     G.L. Burn
  190.     Abstract Interpretation and the Parallel Evaluation of 
  191.         Functional Languages
  192.     ESPRIT Project 415 Report, Dept. Computing, Imperial College, 
  193.         Ph.D. thesis, 1987
  194.     
  195.     G.L. Burn
  196.     Lazy Functional Languages: Abstract Interpretation and Compilation
  197.     Pitman in association with MIT press, 
  198.         ISBN 0-273-08832-7, 0-262-52160-1, 1991
  199.     
  200.     G.L. Burn
  201.     The Evaluation Transformer Model of Reduction and its Correctness
  202.     TAPSOFT '91, LNCS 494, pp458-482
  203.     
  204.     C. Consel
  205.     Binding Time Analysis for Higher Order Untyped Functional Languages
  206.     In ACM Proceedings of the 1990 ACM Conference on LISP and 
  207.         Functional Programming
  208.     Nice, pp264-272
  209.     
  210.     C.A. Gunter, E.L. Gunter, D.B. MacQueen
  211.     An Abstract Interpretation for ML Equality Types
  212.     LNCS 526, pp112-130
  213.     
  214.     C. Hall
  215.     Using Lazy Evaluation to Find Fixpoints in Infinite Domains
  216.     Glasgow University Report?
  217.     
  218.     C.L. Hankin, G.L. Burn, S.L. Peyton Jones
  219.     A Safe Approach to Parallel Combinator Redfuction
  220.     ESOP 86, LNCS 213, pp99-109, 
  221.     Also Theoretical Computer Science, 56:17-36, 1988
  222.     
  223.     C. Hankin
  224.     Abstract Interpretation of term Graph Rewriting Systems
  225.     In S.L. Peyton Jones, G. Hutton, C.K. Holst, Eds.
  226.     Functional Programming, Glasgow 1990
  227.     Springer Verlag, London, 1991, ISBN 3 540 19667 6, pp54-65
  228.     
  229.     P.L. Wadler
  230.     Strictness Analysis on Non-Flat Domains by 
  231.         Abstract Interpretation over Finite Domains
  232.     Prog.In S. Abramsky, C. Hankin
  233.     Abstract Interpretation of Declarative Languages
  234.     Ellis Horwood Ltd. 1987
  235.  
  236. -- 
  237.  
  238. Lorenz Huelsbergen (lorenz@cs.wisc.edu)
  239.  
  240. Computer Sciences Department
  241. University of Wisconsin
  242. 1210 W. Dayton Street
  243. Madison, WI  53706  (USA)
  244.