From: fish@cs.tu-berlin.de (Mario Suedholt)
Subject: Inquiery about work on skeletons - SUMMARY
Organization: Technical University of Berlin, Germany
Distribution: comp.compilers
Date: Mon, 21 Dec 1992 09:27:49 GMT


Hi, everybody!

Three weeks ago I posted a news requiring imformation about current
work on skeletons. Here I will give a summary about the responses I
got:

From jampel@cs.city.ac.uk Mon Dec  7 11:35:44 1992

I suggest you contact Professor John Darlington at Imperial College,
London.
Email is (probably) j.darlington@doc.ic.ac.uk
He has been working for quite a few years in 'Transformation
for Parallelism' using skeletons.
Michael Jampel


From zgma04@trc.amoco.com Mon Dec  7 11:36:25 1992

You should get in touch with Murray Cole at Edinburgh University.
I believe he did this or something similar as his PhD topic.
I don't know his e-mail address.
			Guy


From sheard@urubu.cse.ogi.edu Mon Dec  7 11:36:38 1992

In reference to your search for skeletons, you might want to look at
a new paper (submitted to a journal) entitled "Generating Programs by
Reflection". It is available as OGI tech report 92-015 it can be gotten
over the net by
   ftp cse.ogi.edu
   cd pub/tech-reports/1992
   get 92-015.ps.Z
This paper outlines a systematic way to generate skeletons of programs for
arbitrary types.  The referees have pointed out a bug in one
of the proofs (which hasn't been fixed yet) so please don't distribute
this version. I though you might want to take a look at it.
Tim Sheard
Department of Computer Science and Engineering
Oregon Graduate Institute of Science and Technology
19600 N.W. von Neuman Drive
Beaverton, OR 97006-1999
USA


From hilly@dcs.qmw.ac.uk Mon Dec  7 13:37:14 1992

	I'm replying to your message on news-net concerning the use of higher
order skeletons in the development of parallel functional programs. I'm 
working on a data parallel lazy functional language based upon Haskell,
in which parallel algorithms can be expressed. I've included part of a paper 
I've been writing that develops parallel versions of the higher order 
functions map, scan and fold. The aim of the notation I propose 
is that people write general higher order parallel functions, that can easily 
be re-used. 


From holger@zeus.informatik.rwth-aachen.de Mon Dec  7 14:36:41 1992

Ich habe gerade Dein Posting in den News gelesen und war aeusserst
interessiert. Grund: Ich arbeite zur Zeit hier in Aachen an der
selben Sache. Meine Zugrunde liegende Hardware ist ein Transputer-
System. Da ich im "Graduiertenkolleg Informatik&Technik" bezahlt werde,
ist meine Ausrichtung (in der Implementierung) wahrscheinlich ein
klein wenig praktischer ausgelegt... Meine Skelette muessen am Ende
dann "num_diff_skelett" und so heissen.

Stand der Dinge bei mir ist zur Zeit:
- eine abstrakte Maschine ist implementiert, die zur Zeit aber nur
  reinen funktionalen Code vertraegt.
- Ich habe angefangen, den Datentyp Array in C-Manier zu implementieren.
  Hier suche ich zur Zeit noch eine gute Theorie als Grundlage, die
  mir ein "single threading" ermoeglicht. (Peyton-Jones Monads sind
  nicht ausreichend, es soll da aber noch was von Hudak und von einem aus
  Nijmegen geben.)
- Insbesondere auf diesem Datentyp sollen dann Skelette - als higher-order
  Funktionen in C geschrieben - arbeiten. Neben dem gerade angesprochenen
  numerischen Differations Skelett sind Skelette wie divide&conquer,
  branch&bound, Pipe, ... ins Auge gefasst. Aber wie gesagt: bisher noch
  nicht implementiert (hoffentlich hab ich in ca. einem Monat erste Ergebnisse).
An Literatur fallen mir die folgenden Dinge ein:
Murray I. Cole: Algorithmic Skeletons: Structured Management of Parallel
                Computation, Pitman/MIT-Press 1989
    Das ist wohl seine PhD Thesis, inzwischen als Buch veroeffentlicht (?).
    Ich hab noch die Thesis - kam mal ueber Schriftenaustausch aus Edinburgh
    hier an. Die dortige Nummer ist: CST - 56 - 88, October 88
Darlington et al: Structured Parallel Functional Programming
    3. International Workshop on the Parallel Implementation of
    Functional Languages 1991.
    Zu dem Workshop gibt es auch nur einen internen Report aus Southampton.
Bratvold: Determining Useful Parallelism in Higher Order Functions
    4. Internationaler und so weiter. Diesmal in Aachen.
    Der Tagungsband ist f"ur 20,- DM zu haben bei uns, oder Du gehst
    via anonymous-ftp auf den Rechner ftp.informatik.rwth-aachen.de,
    Verzeichnis /pub/reports. Datei: 92-19-04.ps.Z.
holger@zeus.informatik.rwth-aachen.de
Holger Stoltze
Lehrstuhl fuer Informatik II
RWTH Aachen
Ahornstrasse 55
5100 Aachen


From tore@cee.heriot-watt.ac.uk Tue Dec  8 10:27:05 1992

There seems to be an increasing interest in skeletons these days. The 
major work (past & present) in the area that I'm aware of is: 
- Hewlett-Packard/University of Pisa
    The P4 project/P3 language 
- Imperial College, London
    Prof. Darlington's group
    Paul Kelly's Caliban
- University of British Colombia
    TOPS
- University of East Anglia
    ZAPP
- University of Edinburgh
    Murray Cole's work on Algorithmic Skeletons
    Edinburgh Parallel Computing Centre, skeletons in ML
Some interesting work has been carried out by John Reekie (University
of Technology, Sydney) and Fethi Rabhi (University of Hull). David
Skillicorn's ideas on architecture-independent parallel computation and
the Bird-Meertens formalism are also worth looking at.  
Here at Heriot-Watt (Edinburgh) we've done some work on exploiting parallelism
in HOFs for high-level image processing. I'm currently working on general
methods for extracting and exploiting parallelism from functional programs
based on skeletons, and there is also David Busvine's forthcoming thesis on
detecting parallel structures in functional programs.
Hope this helps. I would appreciate if you could share with me, alternatively
summarise to the net, other responses you get to your posting.
Tore


From mic@dcs.ed.ac.uk Tue Dec  8 10:28:40 1992

I have been interested in this area for a while. There is a lot of work in this
vein at Imperial College, London, in David Skillicorn's group at Queen's, Kingston, 
by Rabhi at Hull and others. Here are some refs, some of them more relevant than
others. I'd be very interested to  hear what else you discover!

Murray Cole.

@techreport{foster90,
    author = "I. Foster and R. Stevens",
    title = "{Parallel Programming with Algorithmic Motifs}",
    institution = "{\it Argonne National Laboratory}",
    type = "{\it Preprint}",
    number = "{\it MCS-P124-0190}",
    year = "1990"}
@techreport{axford91,
    author = "T. Axford",
    title = "{An Abstract Model for Parallel Programming}",
    institution = "{\it University of Birmingham}",
    type = "{\it Computer Science Research Report}",
    number = "{\it CSR-91-5}",
    year = "1991"}
@techreport{mckeown90,
    author = "G.P. McKeown and  V.J. Rayward Smith and H.J. Turpin",
    title = "{Branch-and-Bound as a Higher Order Function}",
    institution = "{\it University of East Anglia}",
    type = "{\it School of Information Systems Internal Report}",
    number = "{\it SYS-C90-03}",
    year = "1990"}
@techreport{danelutto91,
    author = "M. Danelutto and S. Pelagatti and M. Vanneschi",
    title = "{Parallel Programming with Algorithmic Motifs}",
    institution = "{\it Hewlett-Packard Pisa Science Center}",
    type = "{\it Report}",
    number = "{\it HPL-PSC-91-16}",
    year = "1991"              in the Linda Machine}",
    journal = "IEEE Transactions on Computers",
    year = "1988",
    volume = "37",
    number = "8",
    pages = "921--929"}
@article{bird89,
    author = "R.S. Bird",
    title = "{Algebraic Identities for Program Calculation}",
    journal = "Computer Journal",
    year = "1989",
    volume = "32",
    number = "2",
    pages = "122--126"}
@book{book,
    author = "M.I. Cole",
    title = "Algorithmic Skeletons: Structured Management of Parallel 
             Computation",
    publisher = "Pitman",
    year = "1989"}
@inproceedings{darlin89b,
    author = "J. Darlington and M. Reeve and S. Wright",
    title = "{Programming Parallel Computer Systems using Functional
              Languages and Program Transformation}",
    booktitle = "Parallel Computing 89",
    publisher = "Elsevier Science Publishers (North Holland)",
    year = "1990"}
@article{skillicorn90,
    author = "D.B. Skillicorn",
    title = "{Architecture-Independent Parallel Computation}",
    journal = "Computer",
    year = "1990",
    volume = "23",
    number = "12",
    pages = "38--51"}
@techreport{skillicorn91,
    author = "D.B. Skillicorn",
    title = "{Deriving Parallel Programs from Specifications Using
              Cost Information}",
    institution = "{Department of Computing and Information Science, 
                    Queen's University, Kingston}",
    type = "{\it TR}",
    number = "{\it 91-316}",
    year = "1991"}
@techreport{skillicorn92a,
    author = "D.B. Skillicorn and W. Cai",
    title = "{A Cost Calculus for Parallel Functional Programming}",
    institution = "{Department of Computing and Information Science, 
                    Queen's University, Kingston}",
    type = "{\it TR}",
    number = "{\it 92-329}",
    year = "1992"}
@unpublished{skillicorn92b,
    author = "D.B. Skillicorn",
    title  = "{Parallelism and the Bird-Meertens Formalism}",
    year="1992",
    note="{Unpublished}"}
@unpublished{rabhi92
    author = "F.A. Rabhi",
    title  = "{Parallel Programming Paradigms: a Functional Approach}",
    year="1992",
    note="{Unpublished}"}
@unpublished{skillicorn92c,
    author = "W. Cai and D.B. Skillicorn",
    title  = "{Calculating Recurrences Using the Bird-Meertens Formalism}",
    year="1992",
    note="Unpublished"}@
@techreport{sharp92a,
    author = "D.W.N. Sharp and P.G. Harrison and J. Darlington",
    title = "{A Synthesis of a Dynamic Message Passing Algorithm
              for Quicksort}",
    institution = "{Department of Computer Science, 
                    Imperial College}",
    type = "{\it Technical Report}",
    number = "{\it 91-19}",
    year = "1991"}
@inproceedings{sharp92b,
    author = "D.W.N. Sharp and A.J. Field and H. Khoshnevisan",
    title = "{An Exercise in the Synthesis of Parallel Functional
              Programs for Message Passing Architectures}",
    booktitle = "Parallel Computing: From Theory to Sound Practice. Proceedings
                 of EWPC92",
    editor  = "W. Joosen and E. Milgrom",
    publisher = "IOS Press",
    year = "1992",
    pages = "452-463"}


From jeremy@cs.aukuni.ac.nz Wed Dec  9 09:20:05 1992

My thesis ("Algebras for Tree Algorithms", PRG, Oxford, 1991, available as
technical monograph PRG-94) is about accumulations on trees, a particular
kind of higher-order operation on trees. I've just written one and a half
papers on implementing these accumulations efficiently on PRAM machines.

David Skillicorn <skill@qucis.queensu.ca> believes that the data-parallel
style induced by higher-order operators makes a good
architecture-independent parallel programming language. I can send you refs
if you want.

I would be interested in seeing anything you have written so far, and in
your thesis when it is completed. Please send me a summary of the replies
you receive, too!

Cheers,

Jeremy

---
Jeremy Gibbons <jeremy@cs.aukuni.ac.nz>         tel: +64 9 373 7599
   Department of Computer Science,              fax: +64 9 373 7453
   University of Auckland, Private Bag 92019, Auckland, New Zealand.





















-- 

-----------------------------------------------------------------------
Mario Suedholt, TU Berlin, Sekr.: FR 5-13, Franklinstrasse 28/29,
                1000 Berlin 10, FRG;             Tel.: +49 30 314 73182
Newsgroups: comp.lang.functional