This book is a revised edition of the monograph which appeared under the same title in the series Research Notes in Theoretical Computer Science, Pit man, in 1986. In addition to a general effort to improve typography, English, and presentation, the main novelty of this second edition is the integration of some new material. Part of it is mine (mostly jointly with coauthors). Here is brief guide to these additions. I have augmented the account of categorical combinatory logic with a description of the confluence properties of rewriting systems of categor ical combinators (Hardin, Yokouchi), and of the newly developed cal culi of explicit substitutions (Abadi, Cardelli, Curien, Hardin, Levy, and Rios), which are similar in spirit to the categorical combinatory logic, but are closer to the syntax of A-calculus (Section 1.2). The study of the full abstraction problem for PCF and extensions of it has been enriched with a new full abstraction result: the model of sequential algorithms is fully abstract with respect to an extension of PCF with a control operator (Cartwright, Felleisen, Curien). An order extensional model of error-sensitive sequential algorithms is also fully abstract for a corresponding extension of PCF with a control operator and errors (Sections 2.6 and 4.1). I suggest that sequential algorithms lend themselves to a decomposition of the function spaces that leads to models of linear logic (Lamarche, Curien), and that connects sequentiality with games (Joyal, Blass, Abramsky) (Sections 2.1 and 2.6).

Programming is hard. Building a large program is like constructing a steam locomotive through a hole the size of a postage stamp. An artefact that is the fruit of hundreds of person-years is only ever seen by anyone through a lOO-line window. In some ways it is astonishing that such large systems work at all. But parallel programming is much, much harder. There are so many more things to go wrong. Debugging is a nightmare. A bug that shows up on one run may never happen when you are looking for it - but unfailingly returns as soon as your attention moves elsewhere. A large fraction of the program's code can be made up of marshalling and coordination algorithms. The core application can easily be obscured by a maze of plumbing. Functional programming is a radical, elegant, high-level attack on the programming problem. Radical, because it dramatically eschews side-effects; elegant, because of its close connection with mathematics; high-level, be cause you can say a lot in one line. But functional programming is definitely not (yet) mainstream. That's the trouble with radical approaches: it's hard for them to break through and become mainstream. But that doesn't make functional programming any less fun, and it has turned out to be a won derful laboratory for rich type systems, automatic garbage collection, object models, and other stuff that has made the jump into the mainstream.

The Functional Programming Group at the University of Glasgow was started in 1986 by John Hughes and Mary Sheeran. Since then it has grown in size and strength, becoming one of the largest computing science research groups at Glasgow and earning an international reputation. The first Glasgow Functional Programming Workshop was organised in the summer of 1988. Its purpose was threefold: to provide a snapshot of all the research going on within the group, to share research ideas between Glaswegians and colleagues in the U.K. and abroad, and to introduce research students to the art of writing and presenting papers at a semi-formal (but still local and friendly) conference. The success of the first workshop has led to an annual series: Rothesay (1988), Fraserburgh (1989), Ullapool (1990). Portree (1991), Ayr (1992), and the workshop reported in these proceedings: Ayr (1993). Most participants wrote a paper that appeared in the draft proceedings (distributed at the workshop), and each draft paper was presented by one of the authors. The papers were all refereed by several other participants at the workshop, both internal and external, and the programme committee selected papers for these proceedings. Most papers have been revised twice, based firstly on feedback at the workshop, and secondly using the referee reports.

Available in Paperback Available in eBook editions (PDF format) Institution: Syracuse University (Syracuse, NY, USA) Advisor(s): Prof. Klaus J. Berkling Degree: Ph.D. in Computer and Information Science Year: 1993 Book Information: 248 pages Publisher: Dissertation.com ISBN-10: 1612337570 ISBN-13: 9781612337579 View First 25 pages: (free download) Abstract The operational aspects of Lambda Calculus are studied as a fundamental basis for high-order functional computation. We consider systems having full reduction semantics, i.e., equivalence-preserving transformations of functions. The historic lineage from Eval-Apply to SECD to RTNF/RTLF culminates in the techniques of normal-order graph Head Order Reduction (HOR). By using a scalar mechanism to artificially bind relatively free variables, HOR makes it relatively effortless to reduce expressions beyond weak normal form and to allow expression-level results while exhibiting a well-behaved linear self-modifying code structure. Several variations of HOR are presented and compared to other efficient reducers, with and without sharing, including a conservative breadth-first one which mechanically takes advantage of the inherent, fine-grained parallelism of the head normal form. We include abstract machine and concrete implementations of all the reducers in pure functional code. Benchmarking comparisons are made through a combined time-space efficiency metric. The original results indicate that circa 2010 reduction rates of 10-100 million reductions per second can be achieved in software interpreters and a billion reductions per second can be achieved by a state-of-the art custom VLSI implementation.

This volume constitutes the refereed proceedings of the 1995 Asian Computing Science Conference, ACSC 95, held in Pathumthani, Thailand in December 1995. The 29 fully revised papers presented were selected from a total of 102 submissions; clearly the majority of the participating researchers come from South-East Asian countries, but there is also a strong international component. The volume reflects research activities, particularly by Asian computer science researchers, in different areas. Special attention is paid to algorithms, knowledge representation, programming and specification languages, verification, concurrency, networking and distributed systems, and databases.

Basic Category Theory for Computer Scientists provides a straightforward presentation of the basic constructions and terminology of category theory, including limits, functors, natural transformations, adjoints, and cartesian closed categories. Category theory is a branch of pure mathematics that is becoming an increasingly important tool in theoretical computer science, especially in programming language semantics, domain theory, and concurrency, where it is already a standard language of discourse. Assuming a minimum of mathematical preparation, Basic Category Theory for Computer Scientists provides a straightforward presentation of the basic constructions and terminology of category theory, including limits, functors, natural transformations, adjoints, and cartesian closed categories. Four case studies illustrate applications of category theory to programming language design, semantics, and the solution of recursive domain equations. A brief literature survey offers suggestions for further study in more advanced texts. Contents Tutorial • Applications • Further Reading

Parallel processing offers a solution to the problem of providing the processing power necessary to help understand and master the complexity of natural phenomena and engineering structures. By taking several basic processing devices and connecting them together the potential exists of achieving a performance many times that of an individual device. However, building parallel application programs is today recognized as a highly complex activity requiring specialist skills and in-depth knowledge. PARLE is an international, European based conference which focuses on the parallel processing subdomain of informatics and information technology. It is intended to become THE European forum for interchange between experts in the parallel processing domain and to attract both industrial and academic participants with a technical programme designedto provide a balance between theory and practice. This volume contains the proceedings of PARLE '93. The PARLE conference came into existence in 1987 as an initiative from the ESPRIT I programme and the format was revised in 1991/92. PARLE '93 is the second conference with the new format and was held in Munich.

This book offers a comprehensive view of the best and the latest work in functional programming. It is the proceedings of a major international conference and contains 30 papers selected from 126 submitted. A number of themes emerge. One is a growing interest in types: powerful type systems or type checkers supporting overloading, coercion, dynamic types, and incremental inference; linear types to optimize storage, and polymorphic types to optimize semantic analysis. The hot topic of partial evaluation is well represented: techniques for higher-order binding-time analysis, assuring termination of partial evaluation, and improving the residual programs a partial evaluator generates. The thorny problem of manipulating state in functional languages is addressed: one paper even argues that parallel programs with side-effects can be "more declarative" than purely functional ones. Theoretical work covers a new model of types based on projections, parametricity, a connection between strictness analysis and logic, and a discussion of efficient implementations of the lambda-calculus. The connection with computer architecture and a variety of other topics are also addressed.

The second part of this Handbook presents a choice of material on the theory of automata and rewriting systems, the foundations of modern programming languages, logics for program specification and verification, and some chapters on the theoretic modelling of advanced information processing.