home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / function / 1479 next >
Encoding:
Text File  |  1992-12-21  |  11.7 KB  |  320 lines
  1. Newsgroups: comp.lang.functional
  2. Path: sparky!uunet!spool.mu.edu!umn.edu!math.fu-berlin.de!mailgzrz.TU-Berlin.DE!cs.tu-berlin.de!kreusa!fish
  3. From: fish@cs.tu-berlin.de (Mario Suedholt)
  4. Subject: Inquiery about work on skeletons - SUMMARY
  5. Message-ID: <FISH.92Dec21102739@kreusa.cs.tu-berlin.de>
  6. Sender: news@cs.tu-berlin.de
  7. Organization: Technical University of Berlin, Germany
  8. Distribution: comp.compilers
  9. Date: Mon, 21 Dec 1992 09:27:49 GMT
  10. Lines: 308
  11.  
  12.  
  13. Hi, everybody!
  14.  
  15. Three weeks ago I posted a news requiring imformation about current
  16. work on skeletons. Here I will give a summary about the responses I
  17. got:
  18.  
  19. From jampel@cs.city.ac.uk Mon Dec  7 11:35:44 1992
  20.  
  21. I suggest you contact Professor John Darlington at Imperial College,
  22. London.
  23. Email is (probably) j.darlington@doc.ic.ac.uk
  24. He has been working for quite a few years in 'Transformation
  25. for Parallelism' using skeletons.
  26. Michael Jampel
  27.  
  28.  
  29. From zgma04@trc.amoco.com Mon Dec  7 11:36:25 1992
  30.  
  31. You should get in touch with Murray Cole at Edinburgh University.
  32. I believe he did this or something similar as his PhD topic.
  33. I don't know his e-mail address.
  34.             Guy
  35.  
  36.  
  37. From sheard@urubu.cse.ogi.edu Mon Dec  7 11:36:38 1992
  38.  
  39. In reference to your search for skeletons, you might want to look at
  40. a new paper (submitted to a journal) entitled "Generating Programs by
  41. Reflection". It is available as OGI tech report 92-015 it can be gotten
  42. over the net by
  43.    ftp cse.ogi.edu
  44.    cd pub/tech-reports/1992
  45.    get 92-015.ps.Z
  46. This paper outlines a systematic way to generate skeletons of programs for
  47. arbitrary types.  The referees have pointed out a bug in one
  48. of the proofs (which hasn't been fixed yet) so please don't distribute
  49. this version. I though you might want to take a look at it.
  50. Tim Sheard
  51. Department of Computer Science and Engineering
  52. Oregon Graduate Institute of Science and Technology
  53. 19600 N.W. von Neuman Drive
  54. Beaverton, OR 97006-1999
  55. USA
  56.  
  57.  
  58. From hilly@dcs.qmw.ac.uk Mon Dec  7 13:37:14 1992
  59.  
  60.     I'm replying to your message on news-net concerning the use of higher
  61. order skeletons in the development of parallel functional programs. I'm 
  62. working on a data parallel lazy functional language based upon Haskell,
  63. in which parallel algorithms can be expressed. I've included part of a paper 
  64. I've been writing that develops parallel versions of the higher order 
  65. functions map, scan and fold. The aim of the notation I propose 
  66. is that people write general higher order parallel functions, that can easily 
  67. be re-used. 
  68.  
  69.  
  70. From holger@zeus.informatik.rwth-aachen.de Mon Dec  7 14:36:41 1992
  71.  
  72. Ich habe gerade Dein Posting in den News gelesen und war aeusserst
  73. interessiert. Grund: Ich arbeite zur Zeit hier in Aachen an der
  74. selben Sache. Meine Zugrunde liegende Hardware ist ein Transputer-
  75. System. Da ich im "Graduiertenkolleg Informatik&Technik" bezahlt werde,
  76. ist meine Ausrichtung (in der Implementierung) wahrscheinlich ein
  77. klein wenig praktischer ausgelegt... Meine Skelette muessen am Ende
  78. dann "num_diff_skelett" und so heissen.
  79.  
  80. Stand der Dinge bei mir ist zur Zeit:
  81. - eine abstrakte Maschine ist implementiert, die zur Zeit aber nur
  82.   reinen funktionalen Code vertraegt.
  83. - Ich habe angefangen, den Datentyp Array in C-Manier zu implementieren.
  84.   Hier suche ich zur Zeit noch eine gute Theorie als Grundlage, die
  85.   mir ein "single threading" ermoeglicht. (Peyton-Jones Monads sind
  86.   nicht ausreichend, es soll da aber noch was von Hudak und von einem aus
  87.   Nijmegen geben.)
  88. - Insbesondere auf diesem Datentyp sollen dann Skelette - als higher-order
  89.   Funktionen in C geschrieben - arbeiten. Neben dem gerade angesprochenen
  90.   numerischen Differations Skelett sind Skelette wie divide&conquer,
  91.   branch&bound, Pipe, ... ins Auge gefasst. Aber wie gesagt: bisher noch
  92.   nicht implementiert (hoffentlich hab ich in ca. einem Monat erste Ergebnisse).
  93. An Literatur fallen mir die folgenden Dinge ein:
  94. Murray I. Cole: Algorithmic Skeletons: Structured Management of Parallel
  95.                 Computation, Pitman/MIT-Press 1989
  96.     Das ist wohl seine PhD Thesis, inzwischen als Buch veroeffentlicht (?).
  97.     Ich hab noch die Thesis - kam mal ueber Schriftenaustausch aus Edinburgh
  98.     hier an. Die dortige Nummer ist: CST - 56 - 88, October 88
  99. Darlington et al: Structured Parallel Functional Programming
  100.     3. International Workshop on the Parallel Implementation of
  101.     Functional Languages 1991.
  102.     Zu dem Workshop gibt es auch nur einen internen Report aus Southampton.
  103. Bratvold: Determining Useful Parallelism in Higher Order Functions
  104.     4. Internationaler und so weiter. Diesmal in Aachen.
  105.     Der Tagungsband ist f"ur 20,- DM zu haben bei uns, oder Du gehst
  106.     via anonymous-ftp auf den Rechner ftp.informatik.rwth-aachen.de,
  107.     Verzeichnis /pub/reports. Datei: 92-19-04.ps.Z.
  108. holger@zeus.informatik.rwth-aachen.de
  109. Holger Stoltze
  110. Lehrstuhl fuer Informatik II
  111. RWTH Aachen
  112. Ahornstrasse 55
  113. 5100 Aachen
  114.  
  115.  
  116. From tore@cee.heriot-watt.ac.uk Tue Dec  8 10:27:05 1992
  117.  
  118. There seems to be an increasing interest in skeletons these days. The 
  119. major work (past & present) in the area that I'm aware of is: 
  120. - Hewlett-Packard/University of Pisa
  121.     The P4 project/P3 language 
  122. - Imperial College, London
  123.     Prof. Darlington's group
  124.     Paul Kelly's Caliban
  125. - University of British Colombia
  126.     TOPS
  127. - University of East Anglia
  128.     ZAPP
  129. - University of Edinburgh
  130.     Murray Cole's work on Algorithmic Skeletons
  131.     Edinburgh Parallel Computing Centre, skeletons in ML
  132. Some interesting work has been carried out by John Reekie (University
  133. of Technology, Sydney) and Fethi Rabhi (University of Hull). David
  134. Skillicorn's ideas on architecture-independent parallel computation and
  135. the Bird-Meertens formalism are also worth looking at.  
  136. Here at Heriot-Watt (Edinburgh) we've done some work on exploiting parallelism
  137. in HOFs for high-level image processing. I'm currently working on general
  138. methods for extracting and exploiting parallelism from functional programs
  139. based on skeletons, and there is also David Busvine's forthcoming thesis on
  140. detecting parallel structures in functional programs.
  141. Hope this helps. I would appreciate if you could share with me, alternatively
  142. summarise to the net, other responses you get to your posting.
  143. Tore
  144.  
  145.  
  146. From mic@dcs.ed.ac.uk Tue Dec  8 10:28:40 1992
  147.  
  148. I have been interested in this area for a while. There is a lot of work in this
  149. vein at Imperial College, London, in David Skillicorn's group at Queen's, Kingston, 
  150. by Rabhi at Hull and others. Here are some refs, some of them more relevant than
  151. others. I'd be very interested to  hear what else you discover!
  152.  
  153. Murray Cole.
  154.  
  155. @techreport{foster90,
  156.     author = "I. Foster and R. Stevens",
  157.     title = "{Parallel Programming with Algorithmic Motifs}",
  158.     institution = "{\it Argonne National Laboratory}",
  159.     type = "{\it Preprint}",
  160.     number = "{\it MCS-P124-0190}",
  161.     year = "1990"}
  162. @techreport{axford91,
  163.     author = "T. Axford",
  164.     title = "{An Abstract Model for Parallel Programming}",
  165.     institution = "{\it University of Birmingham}",
  166.     type = "{\it Computer Science Research Report}",
  167.     number = "{\it CSR-91-5}",
  168.     year = "1991"}
  169. @techreport{mckeown90,
  170.     author = "G.P. McKeown and  V.J. Rayward Smith and H.J. Turpin",
  171.     title = "{Branch-and-Bound as a Higher Order Function}",
  172.     institution = "{\it University of East Anglia}",
  173.     type = "{\it School of Information Systems Internal Report}",
  174.     number = "{\it SYS-C90-03}",
  175.     year = "1990"}
  176. @techreport{danelutto91,
  177.     author = "M. Danelutto and S. Pelagatti and M. Vanneschi",
  178.     title = "{Parallel Programming with Algorithmic Motifs}",
  179.     institution = "{\it Hewlett-Packard Pisa Science Center}",
  180.     type = "{\it Report}",
  181.     number = "{\it HPL-PSC-91-16}",
  182.     year = "1991"              in the Linda Machine}",
  183.     journal = "IEEE Transactions on Computers",
  184.     year = "1988",
  185.     volume = "37",
  186.     number = "8",
  187.     pages = "921--929"}
  188. @article{bird89,
  189.     author = "R.S. Bird",
  190.     title = "{Algebraic Identities for Program Calculation}",
  191.     journal = "Computer Journal",
  192.     year = "1989",
  193.     volume = "32",
  194.     number = "2",
  195.     pages = "122--126"}
  196. @book{book,
  197.     author = "M.I. Cole",
  198.     title = "Algorithmic Skeletons: Structured Management of Parallel 
  199.              Computation",
  200.     publisher = "Pitman",
  201.     year = "1989"}
  202. @inproceedings{darlin89b,
  203.     author = "J. Darlington and M. Reeve and S. Wright",
  204.     title = "{Programming Parallel Computer Systems using Functional
  205.               Languages and Program Transformation}",
  206.     booktitle = "Parallel Computing 89",
  207.     publisher = "Elsevier Science Publishers (North Holland)",
  208.     year = "1990"}
  209. @article{skillicorn90,
  210.     author = "D.B. Skillicorn",
  211.     title = "{Architecture-Independent Parallel Computation}",
  212.     journal = "Computer",
  213.     year = "1990",
  214.     volume = "23",
  215.     number = "12",
  216.     pages = "38--51"}
  217. @techreport{skillicorn91,
  218.     author = "D.B. Skillicorn",
  219.     title = "{Deriving Parallel Programs from Specifications Using
  220.               Cost Information}",
  221.     institution = "{Department of Computing and Information Science, 
  222.                     Queen's University, Kingston}",
  223.     type = "{\it TR}",
  224.     number = "{\it 91-316}",
  225.     year = "1991"}
  226. @techreport{skillicorn92a,
  227.     author = "D.B. Skillicorn and W. Cai",
  228.     title = "{A Cost Calculus for Parallel Functional Programming}",
  229.     institution = "{Department of Computing and Information Science, 
  230.                     Queen's University, Kingston}",
  231.     type = "{\it TR}",
  232.     number = "{\it 92-329}",
  233.     year = "1992"}
  234. @unpublished{skillicorn92b,
  235.     author = "D.B. Skillicorn",
  236.     title  = "{Parallelism and the Bird-Meertens Formalism}",
  237.     year="1992",
  238.     note="{Unpublished}"}
  239. @unpublished{rabhi92
  240.     author = "F.A. Rabhi",
  241.     title  = "{Parallel Programming Paradigms: a Functional Approach}",
  242.     year="1992",
  243.     note="{Unpublished}"}
  244. @unpublished{skillicorn92c,
  245.     author = "W. Cai and D.B. Skillicorn",
  246.     title  = "{Calculating Recurrences Using the Bird-Meertens Formalism}",
  247.     year="1992",
  248.     note="Unpublished"}@
  249. @techreport{sharp92a,
  250.     author = "D.W.N. Sharp and P.G. Harrison and J. Darlington",
  251.     title = "{A Synthesis of a Dynamic Message Passing Algorithm
  252.               for Quicksort}",
  253.     institution = "{Department of Computer Science, 
  254.                     Imperial College}",
  255.     type = "{\it Technical Report}",
  256.     number = "{\it 91-19}",
  257.     year = "1991"}
  258. @inproceedings{sharp92b,
  259.     author = "D.W.N. Sharp and A.J. Field and H. Khoshnevisan",
  260.     title = "{An Exercise in the Synthesis of Parallel Functional
  261.               Programs for Message Passing Architectures}",
  262.     booktitle = "Parallel Computing: From Theory to Sound Practice. Proceedings
  263.                  of EWPC92",
  264.     editor  = "W. Joosen and E. Milgrom",
  265.     publisher = "IOS Press",
  266.     year = "1992",
  267.     pages = "452-463"}
  268.  
  269.  
  270. From jeremy@cs.aukuni.ac.nz Wed Dec  9 09:20:05 1992
  271.  
  272. My thesis ("Algebras for Tree Algorithms", PRG, Oxford, 1991, available as
  273. technical monograph PRG-94) is about accumulations on trees, a particular
  274. kind of higher-order operation on trees. I've just written one and a half
  275. papers on implementing these accumulations efficiently on PRAM machines.
  276.  
  277. David Skillicorn <skill@qucis.queensu.ca> believes that the data-parallel
  278. style induced by higher-order operators makes a good
  279. architecture-independent parallel programming language. I can send you refs
  280. if you want.
  281.  
  282. I would be interested in seeing anything you have written so far, and in
  283. your thesis when it is completed. Please send me a summary of the replies
  284. you receive, too!
  285.  
  286. Cheers,
  287.  
  288. Jeremy
  289.  
  290. ---
  291. Jeremy Gibbons <jeremy@cs.aukuni.ac.nz>         tel: +64 9 373 7599
  292.    Department of Computer Science,              fax: +64 9 373 7453
  293.    University of Auckland, Private Bag 92019, Auckland, New Zealand.
  294.  
  295.  
  296.  
  297.  
  298.  
  299.  
  300.  
  301.  
  302.  
  303.  
  304.  
  305.  
  306.  
  307.  
  308.  
  309.  
  310.  
  311.  
  312.  
  313.  
  314.  
  315. -- 
  316.  
  317. -----------------------------------------------------------------------
  318. Mario Suedholt, TU Berlin, Sekr.: FR 5-13, Franklinstrasse 28/29,
  319.                 1000 Berlin 10, FRG;             Tel.: +49 30 314 73182
  320.