% Time-stamp: % $Id: SFP.bib,v 1.1 2005/01/24 16:48:13 hwloidl Exp $ % % This Bibtex file contains references of all papers published in the % Scottish Functional Programming Workshop (SFP) series. % SFP is a successor to the Glasgow Functional Programming Workshop (GlaFp). % For bib entries of GlaFp from 1988-1998 see GlaFp.bib. % --------------------------------------------------------------------------- % This should be the official web page of the SFP Workshops @Misc{WWW-SFP, key = {SFP Web Page}, title = {{SFP Web Page}}, howpublished = {WWW page}, year = 2000, month = jun, annote = {date field means ``created at''}, url = {http://www.macs.hw.ac.uk/~dsg/sfp/}, } % --------------------------------------------------------------------------- % The whole SFP'99 Proceedings. @Proceedings{SFP99, title = {{Trends in Functional Programming}}, booktitle = {{1st Scottish Functional Programming Workshop}}, volume = {1}, year = 1999, editor = {P. W. Trinder and G. Michaelson and H-W. Loidl}, address = {Stirling, Scotland}, month = sep, publisher = {Intellect}, note = {ISBN 1-84150-024-0}, url = {http://www.macs.hw.ac.uk/~dsg/sfp/sfp99-contents.html}, } % The papers @InProceedings{klusik_sfp99, author = {Ulrike Klusik and Ricardo Pe{\~n}a and Clara Segura}, title = {{Bypassing of Channels in Eden}}, pages = {2--11}, crossref = {SFP99}, abstract = "In this chapter, Ulrike Klusik, Ricardo Pe{\~n}a and Clara Segura discuss {\it automatic bypassing}, an optimisation of Eden's implementation to reduce the number of messages and/or threads at runtime. Eden extends the lazy functional language Haskell with a set of {\em coordination} features, aimed to express parallel algorithms. These include {\it process abstractions} (or process schemes) and {\it process instantiations} (or applications of a process scheme to actual inputs). When a new process is instantiated, its input and output channels are connected to its parent process. This implies that, in principle, only tree-like process topologies can be created. But the aimed topology may not be tree-like (e.g.\ pipelines, grids, etc). It is desirable to be able to connect every producer to its actual consumer, trying to avoid the intermediate processes frequently used only to set up the topology. The strategy consists of a combination of compile time analysis and runtime support. Both are explained in detail. Also, the savings expected with the proposed strategy are commented upon." } @InProceedings{hernandez_sfp99, author = {F{\'e}lix Hernandez and Ricardo Pe{\~n}a and Fernando Rubio}, title = {{From GranSim to Paradise}}, pages = {11--20}, crossref = {SFP99}, abstract = "Complementing the first Chapter, F\'elix Hernandez, Ricardo Pe\~na and Fernando Rubio describe PARADISE (PARAllel DIstribution Simulator for Eden), a simulator developed to profile the execution of programs written in Eden. Paradise is a substantial modification of GranSim, a simulator used to study the dynamic behaviour of GpH (Glasgow Parallel Haskell) programs. The reason for reusing GranSim is that, in addition to being an accurate and flexible simulator, both GpH and Eden are based on the Glasgow Haskell Compiler. The differences between both GpH and Eden, and between GranSim and Paradise are described. The new facilities required for the simulator and the current status of the implementation are presented. The most relevant new features of Paradise are the speculation graphics and the mark system to relate profiles with the source code. Examples of actual and foreseen graphics are given in the text." } @InProceedings{hayashi_sfp99, author = {Yasushi Hayashi and Murray Cole}, title = {{BSP-based Cost Analysis of Skeletal Programs}}, pages = {20--29}, crossref = {SFP99}, abstract = "Next, Yasushi Hayashi and Murray Cole present an automatic cost-analysis system for an implicitly parallel skeletal programming language. Tractability of the analysis is facilitated by language restrictions based on the principles of shape analysis. This builds on earlier work in the area by quantifying communication as well as computation costs, with the former being derived for the Bulk Synchronous Parallel (BSP) model. The analysis has been implemented and its cost predictions for a simple example program are discussed." } @InProceedings{ballereau_sfp99, author = {Olivier Ballereau and Fr{\'e}d{\'e}ric Loulergue and Ga{\'e}tan Hains}, title = {{High Level BSP Programming: BSML and BS$\lambda $}}, pages = {29--41}, crossref = {SFP99}, abstract = "In a contrasting approach, Olivier Ballereau, Fr\'ed\'eric Loulergue and Ga\'etan Hains present a functional data-parallel language called BSML, for programming BSP algorithms in so-called direct mode. Its aim is to combine the generality of languages like NESL with the predictable performance of direct-mode BSP algorithms. The BSML operations are motivated and described. Experiments with a library implementation of BSML show the possibilities and limitations of parallel performance prediction in this framework." } @InProceedings{gilmore_sfp99, author = {Stephen Gilmore}, title = {{Deep Type Inference for Mobile Functions}}, pages = {41--50}, crossref = {SFP99}, abstract = "Stephen Gilmore considers the problem of assessing the trustworthiness of mobile code. The idea of \emph{deep type inference} on compiled object code is introduced and its usefulness is explained as a method of deciding the level of security management that a unit of mobile code will require." } @InProceedings{mcadam_sfp99, author = {Bruce J. McAdam}, title = {{Generalising Techniques for Type Debugging}}, pages = {50--59}, crossref = {SFP99}, abstract = "Several authors have presented algorithms to help programmers understand the types in their programs and to help debug type errors in languages with Hindley-Milner type systems. Each of these has supplied a different form of information to the programmer: the types of unbound identifiers and suggestions of where in programs mistakes may lie are examples of such information. Here, Bruce J.~McAdam introduces a new means of representing type information as graphs. From this a range of different facts about the types in programs can be extracted. The graph representation is presented, and is used to simulate some of the schemes proposed by other authors. Such graphs generalise a number of previously disjoint pieces of work." } @InProceedings{yang_sfp99, author = {Jun Yang}, title = {{Explaining Type Errors by Finding the Source of a Type Conflict}}, pages = {59--68}, crossref = {SFP99}, abstract = "Both complementing and contrasting with the previous Chapter, Jun Yang discusses better methods of explaining type conflicts. Typically a type error is reported when unification fails, even though the programmer's actual error may have occurred much earlier in the program. The W and M inference algorithms report the site where a type conflict is detected, but the error message is isolated information: it is not clear what the relationship is between the site where error is reported and the context in which the subexpression was typed. As a result, the error message may give little help to locate the source of the error. The aim here is to find a method that may be effective even when the user has little knowledge of type checking. The philosophy of the approach taken is to find sources of type errors by reporting which parts of the program conflict, rather than isolated error sites. Two new inference algorithms are implemented with this philosophy: the Unification of Assumption Environments (UAE) and the Incremented Error Inference (INC)." } @InProceedings{widera_sfp99, author = {Manfred Widera and Christoph Beierle}, title = {{How to Combine the Benefits of Strict and Soft Typing}}, pages = {68--79}, crossref = {SFP99}, abstract = "Manfred Widera and Christoph Beierle discuss the properties of strictly typed languages and soft typing, and identify the disadvantages of these approaches to type checking in the context of powerful type languages. To overcome the problems an approach is developed that combines ideas of both strict and soft typing. The approach is based on the concept of complete typing that is guaranteed to accept every well-typed program. The main component of a complete type checker is defined." } @InProceedings{green_sfp99, author = {Mark Green and Ali E. Abdallah}, title = {{Interfacing Java with Haskell}}, pages = {79--89}, crossref = {SFP99}, abstract = "Mark Green and Ali E. Abdallah present an approach for interfacing Java and Haskell. In their approach, a program is divided into two parts: one part, expressed in Haskell, implements the functionality of the system; the other part, written in Java, provides the user interface and calls the Haskell code. This approach combines the strength of the problem-solving features of functional programming with the strength of the user interfacing and platform independence features of Java. Several case studies are presented to demonstrate the usefulness of this approach." } @InProceedings{walton_sfp99, author = {Christopher D. Walton}, title = {{An Abstract Machine for Memory Management}}, pages = {89--98}, crossref = {SFP99}, abstract = "In composing the Definition of Standard~ML, the authors chose not to give an account of the operation of memory management. This was the right decision when focusing upon the abstract description of a sophisticated high-level language. However, the issues associated with memory management cannot be ignored by the compiler writer who must make decisions which have a great impact on the performance of the compiled code. Here, Christopher D. Walton presents an abstract machine formalism of a tag-free garbage-collector which exposes many important memory management details such as the heap, stack, and environment. The model provides an implementor with an unambiguous and precise description of a memory management strategy for Standard~ML." } @InProceedings{morazan_sfp99, author = {Marco T. Moraz{\'a}n and Douglas R. Troeger}, title = {{The MT Architecture and Allocation Algorithm}}, pages = {98--106}, crossref = {SFP99}, abstract = "Marco T. Moraz\'an and Douglas R. Troeger present the MT architecture and some experiments involving the MT allocation algorithm. The MT architecture suggests the use of a distributed virtual memory (DVM) to enhance performance by reducing the number of page faults at the evaluator node. The DVM is both based on and, fine--tuned to, the needs of the language. The allocation algorithm is simple and fair. It attempts to foster intra--list locality without the intervention of a garbage collector. Properties of the layout of lists are presented for the allocation algorithm." } @InProceedings{woo_sfp99, author = {Gyun Woo and Taisook Han}, title = {{ZG-machine: a Space-Efficient G-machine}}, pages = {106--116}, crossref = {SFP99}, abstract = "Gyun Woo and Taisook Han discuss the ZG-machine, a space-efficient G-machine, which exploits a simple encoding method, called tag-forwarding, to compress the heap structure of graphs. Experiments on the ZG-machine without garbage collection show that the ZG-machine saves 30\% of heap space and the run-time overhead is no more than 6\% than the standard G-machine. Experiments on the ZG-machine with garbage collection show that, compared to the G-machine, heap-residency decreases by 34\% on average although run-time increases by 34\%. The high run-time overhead of the ZG-machine is due to the garbage collector. However, with large heap sizes, e.g.\ 7 times greater than heap-residency, the run-time overhead is no more than 12\% compared to the G-machine. Having reduced heap-residency, the ZG-machine may be useful in memory-restricted environments such as embedded systems. Also, with the development of a more efficient garbage collector, run-time is expected to decrease significantly." } @InProceedings{rabhi_sfp99, author = {Fethi A. Rabhi and Guy Lapalme and Albert Y. Zomaya}, title = {{A Functional Design Framework for Genetic Algorithms}}, pages = {116--126}, crossref = {SFP99}, abstract = "One advantage of functional languages is the ability to use higher-order functions to guide the design of certain classes of algorithms. Fethi A. Rabhi, Guy Lapalme and Albert Y. Zomaya consider genetic algorithms (GAs) and their application to the solution of the single row routing (SRR) problem which is an important problem in the design of multilayer printed circuit boards (MPCBs). The paper presents a framework which allows high-level modelling of a GA solution as well as providing an executable specification which can be used to refine the parameters of the GA search. This is a first step towards ``intelligent'' GA design interfaces and efficient implementations possibly based on parallel evaluation." } @InProceedings{baker_sfp99, author = {Paul Baker and Clive Jervis and David J. King}, title = {{An Industrial use of FP: A Tool for Generating Test Scripts from System Specifications}}, pages = {126--135}, crossref = {SFP99}, abstract = "With the scale and complexity of telecommunication systems, the telecoms industry has had to adapt and embrace more formal techniques in order to develop reliable software and systems more rapidly. Formal specification languages are now used throughout the development process from requirements specification through to code generation. By using these formal techniques it is possible to automate many parts of the engineering process. To this end, Paul Baker, Clive Jervis and David J. King from Motorola Lab's Software Research Group in the UK, have contributed to the development of a toolset that formally verifies and validates system and software specifications. In order to develop these tools rapidly, many techniques have been deployed that are more commonly found in academia, namely, the process algebra CSP, a tactical term rewriting engine, and the functional language Standard ML. These techniques are described, and the reduced development time, and improved the maintainability of the \emph{ptk} tool are considered." } @InProceedings{dosch_sfp99, author = {Walter Dosch and Bernd Wiedemann}, title = {{List Homomorphisms with Accumulation and Indexing}}, pages = {135--144}, crossref = {SFP99}, abstract = "Walter Dosch and Bernd Wiedemann propose a new class of list homomorphisms as functional skeletons for data parallel programming. Accumulating list homomorphisms generalise genuine list homomorphisms by introducing an accumulation parameter into the definition scheme. Data parallel implementations that are structured in several stages are derived, where the number of implementation stages depends on the algebraic properties of the accumulation function. Several case studies illustrate the wide class of list functions that can be parallelised with accumulating homomorphisms." } @InProceedings{lammel_sfp99, author = {Ralf L{\"a}mmel}, title = {{Reuse by Program Transformation}}, pages = {144--154}, crossref = {SFP99}, abstract = "Ralf Lämmel discusses how certain adaptations that are usually performed manually by functional programmers may be formalised by program transformation. The focus is on on adaptations to obtain a more reusable version of a program or a version needed for a special use case, for example, propagation of additional parameters, introduction of monadic style, and symbolic rewriting. The corresponding transformations are specified by inference rules in the style of natural semantics. Preservation properties such as type and semantics preservation are discussed. The overall thesis is that suitable operator suites for automated adaptations and a corresponding transformational programming style can eventually be combined with other programming styles, such as polymorphic programming, modular programming, or the monadic style, in order to improve reusability of functional programs." } @InProceedings{baker-finch_sfp99, author = {Clem Baker-Finch}, title = {{An Abstract Machine for Parallel Lazy Evaluation}}, pages = {154--161}, crossref = {SFP99}, abstract = "Clem Baker-Finch describes a simple abstract machine for parallel lazy evaluation. The starting point is Sestoft's abstract machine for sequential lazy evaluation and the development is influenced by an existing operational semantics for parallel lazy evaluation. The general structure of the machine is flexible enough to describe a variety of parallel constructs. This claim is illustrated by considering fully speculative evaluation, {\bf par} and {\bf seq} combinators and limited processing resources." } % --------------------------------------------------------------------------- % The whole SFP'00 Proceedings. @Proceedings{SFP00, title = {{Trends in Functional Programming}}, booktitle = {{2nd Scottish Functional Programming Workshop}}, volume = {2}, year = 2000, editor = {Stephen Gilmore}, address = {St. Andrews, Scotland}, month = jul, publisher = {Intellect}, url = {http://www.macs.hw.ac.uk/~dsg/sfp/sfp00-contents.html}, note = {ISBN 1-84150-058-5} } % The papers @InProceedings{faxen_sfp00, author = {Karl-Filip Fax{\'e}n}, title = {{The costs and benefits of cloning in a lazy functional language}}, pages = {1--12}, crossref = {SFP00}, url = {http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Faxen/main.ps} } @InProceedings{pareja_sfp00, author = {Crist{\'o}bal Pareja and Ricardo Pe{\~n}a and Fernando Rubio and Clara Segura}, title = {{Optimising Eden by transformation}}, pages = {13--26}, crossref = {SFP00}, url = {http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Segura/cameraready.ps}, } @InProceedings{brown_sfp00, author = {Deryck F. Brown and A. Beatriz Garmendia-Doval and John A.W. McCall}, title = {{A functional framework for the implementation of genetic algorithms: Comparing Haskell and Standard ML}}, pages = {27--38}, crossref = {SFP00}, url = {http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Garmendia-Doval/cameraready.ps}, } @InProceedings{loidl_sfp00, author = {Hans-Wolfgang Loidl and Ulrike Klusik and Kevin Hammond and Rita Loogen and Phil Trinder}, title = {{GpH and Eden: Comparing two parallel functional languages on a Beowulf cluster}}, pages = {39--52}, crossref = {SFP00}, url = {http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Loidl/main.ps}, } @InProceedings{klusik_sfp00, author = {Ulrike Klusik and Rita Loogen and Steffen Priebe}, title = {{Controlling parallelism and data distribution in Eden}}, pages = {53--64}, crossref = {SFP00}, url = {http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Loogen/main.ps}, } @InProceedings{cope_sfp00, author = {Michelle Cope and Ian Gent and Kevin Hammond}, title = {{Parallel heuristic search in Haskell}}, pages = {65--76}, crossref = {SFP00}, url = {http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Cope/cbj-sfp.ps}, } @InProceedings{loulergue_sfp00, author = {Fr{\'e}d{\'e}ric Loulergue}, title = {{Parallel composition and bulk synchronous parallel functional programming}}, pages = {77--88}, crossref = {SFP00}, url = {http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Loulergue/Frederic.Loulergue.ps}, } @InProceedings{hidalgo_sfp00, author = {Mercedes Hidalgo-Herrero and Yolanda Ortega-Mall{\'e}n}, title = {{A distributed operational semantics for a parallel functional language}}, pages = {89--102}, crossref = {SFP00}, url = {http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Hidalgo/sfpiicrp.ps}, } @InProceedings{trinder_sfp00, author = {Phil Trinder and Robert Pointon and Hans-Wolfgang Loidl}, title = {{Runtime system level fault tolerance for a distributed functional language}}, pages = {103--114}, crossref = {SFP00}, url = {http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Trinder/paper.ps}, } @InProceedings{bakewell_sfp00, author = {Adam Bakewell and Colin Runciman}, title = {{The space usage problem: An evaluation kit for graph reduction semantics}}, pages = {115--128}, crossref = {SFP00}, url = {http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Bakewell/sfp.ps}, } @InProceedings{serot_sfp00, author = {Jocelyn S{\'e}rot}, title = {{CAMLFLOW: a CAML to data-flow graph translator}}, pages = {129--144}, crossref = {SFP00}, url = {http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Serot/cameraready.ps}, } @InProceedings{curtis_sfp00, author = {Sharon Curtis}, title = {{An application of functional programming: quilting}}, pages = {145--158}, crossref = {SFP00}, url = {http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Curtis/cameraready.ps}, } @InProceedings{mcadam_sfp00, author = {Bruce McAdam and Andrew Kennedy and Nick Benton}, title = {{Type inference for MLj}}, pages = {159--172}, crossref = {SFP00}, url = {http://www.dcs.ed.ac.uk/home/stg/sfpw/book/McAdam/cameraready.ps}, } @InProceedings{widera_sfp00, author = {Manfred Widera and Christoph Beierle}, title = {{Detecting common elements of types}}, pages = {173--184}, crossref = {SFP00}, url = {http://www.dcs.ed.ac.uk/home/stg/sfpw/book/Widera/sfp2000.ps}, } % --------------------------------------------------------------------------- % The whole SFP'00 Proceedings. @Proceedings{SFP01, title = {{Trends in Functional Programming}}, booktitle = {{3rd Scottish Functional Programming Workshop}}, volume = {3}, year = 2001, editor = {Kevin Hammond and Sharon Curtis}, address = {Stirling, Scotland}, month = aug, publisher = {Intellect}, url = {http://www.macs.hw.ac.uk/~dsg/sfp/sfp01-contents.html}, note = {ISBN 1-8410-070-4} } % The papers @InProceedings{russel_sfp01, author = {Dan Russell and Dominic Steinitz and Chris Reade}, title = {{Haskell: Language for Business Systems}}, pages = {1--12}, crossref = {SFP01}, } @InProceedings{stoughton_sfp01, author = {Allen Stoughton}, title = {{Infinite Pretty-printing in eXene}}, pages = {13--24}, crossref = {SFP01}, } @InProceedings{hamilton_sfp01, author = {Geoffrey W. Hamilton}, title = {{Extending Higher-Order Deforestation: Transforming Programs to Eliminate Even More Trees}}, pages = {25--36}, crossref = {SFP01}, } @InProceedings{miller_sfp01, author = {Quentin Miller}, title = {{BSP in a Lazy Functional Context}}, pages = {37--50}, crossref = {SFP01}, } @InProceedings{pena_sfp01, author = {Ricardo Pe{\~n}a and Fernando Rubio and Clara Segura}, title = {{Deriving Non-Hierarchical Process Topologies}}, pages = {51--62}, crossref = {SFP01}, } @InProceedings{loidl_sfp01, author = {Hans-Wolfgang Loidl}, title = {{Load Balancing in a Parallel Graph Reducer}}, pages = {63--74}, crossref = {SFP01}, } @InProceedings{morazan_sfp01, author = {Marco T. Morazan and Douglas R. Troeger and Myles Nash}, title = {{Paging in a Distributed Virtual Memory}}, pages = {75--86}, crossref = {SFP01}, } @InProceedings{mcadam_sfp01, author = {Bruce J. McAdam}, title = {{How to Repair Type Errors Automatically}}, pages = {87--98}, crossref = {SFP01}, } @InProceedings{uustalu_sfp01, author = {Tarmo Uustalu and Varmo Vene}, title = {{The Dual of Substitution is Redecoration}}, pages = {99--110}, crossref = {SFP01}, } @InProceedings{widera_sfp01, author = {Manfred Widera and Christoph Beierle }, title = {{Function Types in Complete Type Inference}}, pages = {111--122}, crossref = {SFP01}, }