Embed Size px x x x x Email for orders and customer service enquiries : cs-books wiley. No part of this publication may be reproduced, stored in a retrievalsystem or transmitted in any form or by any means, electronic, mechanical, photocopying,recording, scanning or otherwise, except under the terms of the Copyright, Designs andPatents Act or under the terms of a licence issued by the Copyright Licensing AgencyLtd, 90 Tottenham Court Road, London WIT 4LP, UK, without the permission in writing ofthe Publisher, with the exception of any material supplied specifically for the purpose ofbeing entered and executed on a computer system, for exclusive use by the purchaser of thepublication.
The authors and publisher expressly disclaim all implied warranties, includingmerchantability or fitness for any particular purpose. There will be no duty on the authorsor publisher to correct any errors or defects in the software. Designations used by companies to distinguish their products are often claimed as trade-marks. Readers, however, should contact the appropriatecompanies for more complete information regarding trademarks and registration.
This publication is designed to provide accurate and authoritative information in regardto the subject matter covered. It is sold on the understanding that the Publisher is notengaged in rendering professional services. If professional advice or other expert assis-tance is required, the services of a competent professional should be sought.
Wiley also publishes its books in a variety of electronic formats. Some content that appearsin print may not be available in electronic books. This book is printed on acid-free paper responsibly manufactured from sustainableforestry in which at least two trees are planted for each one used for paper production. Inductive Proofs and Constructions Remainder Computation PrefaceProgramming is a highly skilled activity, and good programmers are few and farbetween.
Many programmers are able towrite programs that 'work' in most circumstances; few programmers know thebasic principles of program specification, let alone how to construct programsthat guarantee to meet their specifications in all circumstances. It is no wonder. Many texts have been written that explain how to encode compu-tational processes in some specific programming language C, Java, Visual Basic,or whatever , but few tackle the much harder problem of presenting the problem-solving skills that are needed to formulate programming problems precisely andconcisely, and to convert those formulations into elegant implementations.
This book is about programming per se. It is about the most elementary princi-ples of program constructionproblem decomposition, invariant properties, andguarantees of progress. It is intended to appeal to both novice programmers, whowish to start on the right track, and to experienced programmers who wish toproperly master their craft. Although the subject matter of the book is 'elementary', in the sense of foun-dational, it is not 'easy'. Programming is challenging, and it is wrong to skirt theissues or to wrap it up in a way that makes it seem otherwise.
I have lecturedon this material for many years, mostly to undergraduates on computing sciencedegrees, and, occasionally, to professional programmers. Inevitably, it is the expe-rienced programmers who appreciate its value the most. Novice programmershave the additional hurdle of learning how to write codetoo often in a highlycomplex programming language.
For them, the problem is the programming lan-guage, whereas, of course, the programming language should not be a problem,but part of the solution. In order to present the real challenges of programming without obfuscation,the book uses a very simple programming language, with just four programmingconstructsassignment, sequential composition, conditionals and loops. I haveomitted variable declarations, so that the focus of the book remains clear. Expertswill recognize the language as the Guarded Command Language, a simple, elegantlanguage designed by Dijkstra specifically for this purpose.
The book is a major revision of my earlier book Program Construction and Ver-ification, published in Some sections remain the same, but there is muchthat is different. The main difference is reflected in the omission of 'verification'in the title. The primary goal of the book is to show how programs are constructedto meet their specifications, by means of simple, mathematical calculations. Theemphasis on construction is crucial; the fact that the calculations can be formallyverified is also important, but much less so. Unfortunately, however, the empha-sis in many related texts is the reverse; the fundamental principles of programconstruction are introduced as a mechanism for performing a post hoc validationof the program's correctness, and their integral role in the activity of developingprograms is neglected.
Even worse, automatic verification is often given as the pri-mary justification for their use. I have no doubt that this misplaced emphasis onverification rather than construction has, for long, stood in the way of the accep-tance and active use of the principles by practising programmers. A metamorphism is the opposite composition, an unfold after a fold; typically, it will convert from one data representation to another.
In general, metamorphisms are less interesting than hylomorphisms: there is no automatic fusion to deforest the intermediate virtual data structure. However, under certain conditions fusion is possible: some of the work of the unfold can be done before all of the work of the fold is complete.
This permits streaming metamorphisms , and among other things allows conversion of infinite data representations. We present the theory of metamorphisms and outline some examples.
Cross-trial query system for cancer clinical trials. CancerGrid, a consortium of clinicians, cancer researchers, computational biologists and software engineers from leading UK institutions, is developing open-standards cancer informatics addressing this challenge. The CancerGrid solution involves the representation of a widely accepted clinical trials model in controlled vocabulary and common data elements CDEs as the enabling factor for cancer data sharing. This paper describes a cancer data query system that supports data sharing across CancerGrid-compliant clinical trial boundaries.
The formal specification of the query system allows the model-driven development of a flexible, web-based interface that cancer researchers with limited IT experience can use to identify and query common data across multiple clinical trials. Design patterns as higher-order datatype-generic programs.
- See a Problem?;
- Program construction : calculating implementations from specifications.
- Rectal Cancer: New Frontiers in Diagnosis, Treatment and Rehabilitation!
However, using current programming languages, these elements can only be expressed extra-linguistically: as prose, pictures, and prototypes. We believe that this is not inherent in the patterns themselves, but evidence of a lack of expressivity in the languages of today.
We expect that, in the languages of the future, the code part of design patterns will be expressible as reusable library components. Indeed, we claim that the languages of tomorrow will suffice; the future is not far away. The necessary features are higher-order and datatype-generic constructs; these features are already or nearly available now. We argue the case by presenting higher-order datatype-generic programs capturing Origami, a small suite of patterns for recursive data structures. Superseded by [ iterator ].
Various functional iterations model one or other of these, but not both simultaneously. We argue that McBride and Paterson's idioms, and in particular the corresponding traverse operator, do exactly this, and therefore capture the essence of the Iterator pattern. We present some axioms for traversal, and illustrate with a simple example, the repmin problem.
Fission for program comprehension. Fission is the same transformation, in reverse: creating structure, ex nihilo. We explore the use of fission for program comprehension, that is, for reconstructing the design of a program from its implementation. We illustrate through rational reconstructions of the designs for three different C programs that count the words in a text file. Fast and loose reasoning is morally correct. In Principles of Programming Languages , pages , January Two languages are defined, one total and one partial, with identical syntax.
The semantics of the partial language includes partial and infinite values and lifted types, including lifted function spaces. A partial equivalence relation is then defined, the domain of which is the total subset of the partial language. It is proved that if two closed terms have the same semantics in the total language, then they have related semantics in the partial language.
It is also shown that the partial equivalence relation gives rise to a bicartesian closed category, which can be used to reason about values in the domain of the relation. American Mathematical Monthly , 4 , One of the algorithms described in this paper won a prize for most useful submission at the Succ Zeroth International Obfuscated Haskell Code Contest!
A spigot algorithm yields its outputs incrementally, and does not reuse them after producing them. Their algorithm is inherently bounded ; it requires a commitment in advance to the number of digits to be computed, and in fact might still produce an incorrect last few digits. Enumerating the rationals. Journal of Functional Programming , 16 4 , A revision of [ hodgp-ecoop ]. In particular, the thesis is that whereas design patterns must be expressed extra-linguistically as prose, diagrams, examples in object-oriented languages, they may be captured directly as abstractions using higher-order operators in functional programming languages.
Therefore, they may be reasoned about, type-checked, applied and reused, just as any other abstractions may be. We argue this case by developing the idea of higher-order operators, specifically for capturing patterns of computation in programs. We then build on this to show how the intentions behind a number of the Gang of Four patterns-such as Composite, Visitor, Iterator, and Builder-have higher-order operators as their analogues in functional languages.
Specifically, the structure of these patterns is determined essentially by the structure of the data involved, and they can be captured as generic programs parametrized by that datatype. The aim is to give greater insight into and understanding of already-familiar patterns. Later version appears as [ hodgp-oopsla ].
Second Hand Books & Games for sale in Johannesburg CBD
We then bring this around to show how the intentions behind a number of the Gang of Four patterns-such as Composite, Visitor, Iterator, and Builder-have higher-order operators as their analogues in functional languages. Proof methods for corecursive programs. The dual technique of corecursion is less well-known, but is increasingly proving to be just as useful. This article is a tutorial on the four main methods for proving properties of corecursive programs: fixpoint induction, the approximation or take lemma, coinduction, and fusion.
TypeCase: A design pattern for type-indexed functions. In Daan Leijen, editor, Haskell Workshop , Haskell's type class mechanism provides collections of open type-indexed functions , in which the indexing family can be extended by defining a new type class instance but the collection of functions is fixed. The purpose of this paper is to present TypeCase : a design pattern that allows the definition of closed type-indexed functions , in which the index family is fixed but the collection of functions is extensible.
It is inspired by Cheney and Hinze's work on lightweight approaches to generic programming. We generalise their techniques as a design pattern. Furthermore, we show that type-indexed functions with type-indexed types , and consequently generic functions with generic types , can also be encoded in a lightweight manner, thereby overcoming one of the main limitations of the lightweight approaches.
Streaming representation-changers. Superseded by [ metamorphisms-scp ]. Disciplined, efficient, generalised folds for nested datatypes. Formal Aspects of Computing , 16 1 , Their folds are restricted in power due to type constraints. Bird and Paterson introduced generalised folds for extra power, but at the cost of a loss of efficiency: folds may take more than linear time to evaluate.
Hinze introduced efficient generalised folds to counter this inefficiency, but did so in a pragmatic way, at the cost of a loss of reasoning power: without categorical or equivalent underpinnings, there are no universal properties for manipulating folds. We combine the efficiency of Hinze's construction with the powerful reasoning tools of Bird and Paterson's. Patterns in datatype-generic programming. Datatype-generic programming is another instance, in which the parameters take the form of datatypes.
We argue that datatype-generic programming is sufficient to express essentially all the genericity found in the Standard Template Library. This paper describes work in progress. Arithmetic coding with folds and unfolds. It produces a theoretically optimal compression under much weaker assumptions than Huffman and Shannon-Fano, and can compress within one bit of the limit imposed by Shannon's Noiseless Coding Theorem.
Earlier presentations provided little in the way of proof of why the various steps in the encoding process were correct, particularly when it came to the specification of precisely what problem the implementation solved, and the details of why the inverse operation of decoding was correct. Our aim in these lectures is to provide a formal derivation of basic algorithms for coding and decoding.
Our development makes heavy use of the algebraic laws of folds and unfolds. One novel result concerns a new pattern of computation, which we call streaming , whereby elements of an output list are produced as soon as they are determined and which has nothing to do with lazy evaluation. This volume is about a novel form of genericity in programs, based on parameterizing programs by the structure of the data they manipulate. The material is based on lectures presented at a summer school on Generic Programming held at the University of Oxford in August Origami programming. Such equations are easy to explain, and adequate for any computational purpose, but hard to use well as programs get bigger and more complicated.
As computer scientists discovered in the s with structured programming, it is better to identify common patterns of use of such too-powerful tools, and capture these patterns as new constructions and abstractions. In functional programming, in contrast to imperative programming, we can often express the new constructions as higher-order operations within the language, whereas the move from unstructured to structured programming entailed the development of new languages. In this chapter we will look at folds and unfolds as abstractions.
In a precise technical sense, folds and unfolds are the natural patterns of computation over recursive datatypes; unfolds generate data structures and folds consume them. Functional programmers are very familiar with the foldr function on lists, and its directional dual foldl ; they are gradually coming to terms with the generalisation to folds on other datatypes.
The computational duals, unfolds, are still rather unfamiliar; we hope to show here that they are no more complicated than, and just as useful as, folds, and to promote a style of programming based on these and similar recursion patterns. The Fun of Programming. Cornerstones in Computing. Palgrave, Ideas that were first developed in the laboratory environment of functional programming have proved their values in wider settings, such as generic Java and XML.
The time is ripe, therefore, to teach a second course on functional programming, delving deeper into the subject. This book is the text for such a course. The emphasis is on the fun of programming in a modern, well designed programming language such as Haskell. There are chapters that focus on applications, in particular pretty printing, musical composition, hardware description, and graphical design.
These applications are interspersed with chapters on techniques, such as the design of efficient data structures, interpreters for other languages, program testing and optimisation. These topics are of interest to every aspiring programmer, not just to those who choose to work in a functional language. Haskell just happens to be a very convenient vehicle for expressing the ideas, and the theme of functional programming as a lingua franca to communicate ideas runs throughout the book. On the supervision and assessment of part-time postgraduate software engineering projects.
In International Conference on Software Engineering , It considers this aspect of the learning experience, and the educational issues raised, in the context of existing literature-much of which is focussed upon the experience of full-time, undergraduate students. The importance of these issues will increase with the popularity of part-time study at a postgraduate level; the paper presents a set of guidelines for project supervision and assessment. Generic Programming. Kluwer Academic Publishers, This book contains revised versions of the papers that were presented at the conference.
Towards a colimit-based semantics for visual programming. They encourage the study of connectors as first-class entities, and superposition of connectors onto components as a paradigm for component-oriented programming. We demonstrate that this is a good model for what visual programming tools like IBM's VisualAge actually do.
Moreover, Fiadeiro and Maibaum's categorical semantics of parallel programs is applicable to this model, so we can make progress towards a formal semantics of visual programming. Calculating functional programs. In particular, one can use this style of reasoning to calculate programs, in the same way that one calculates numeric values in arithmetic. Many useful theorems for such reasoning derive from an algebraic view of programs, built around datatypes and their operations.
Traditional algebraic methods concentrate on initial algebras, constructors, and values; dual co-algebraic methods concentrate on final co-algebras, destructors, and processes.
Both methods are elegant and powerful; they deserve to be combined. Algebraic methods for optimization problems. To support this argument, we present an extended case study for a class of optimization problems, deriving efficient functional programs from concise relational specifications. Doing so in a way that guarantees correctness is an undertaking requiring deep understanding of the languages and tools being used, as well as of the application domain.
Recent research aimed at improving the process of program construction exploits insights from abstract algebraic tools such as lattice theory, fixpoint calculus, universal algebra, category theory and allegory theory. This book provides an introduction to these mathematical theories and how they are applied to practical problems. On the semantics of nested datatypes. Information Processing Letters , 80 5 , December The standard semantic definition of recursively defined datatypes is as initial algebras in the category Set of sets and total functions.
Bird and Meertens have shown that this theory is inadequate to describe nested datatypes. Instead, one solution proposed there was to define them as initial algebras in the functor category Nat Set , with objects all endofunctors on Set and arrows all natural transformations between them. We show here that initial algebras are not guaranteed to exist in the functor category itself, but that they do exist in one of its subcategories: the category of all cocontinuous endofunctors and natural transformations.
This category is then a suitable semantic domain for nested datatypes, both first order and higher-order. The generic approximation lemma. Information Processing Letters , 79 4 , August We show how the approximation lemma, unlike the take lemma, can naturally be generalised from lists to a large class of datatypes, and present a generic approximation lemma that is parametric in the datatype to which it applies. As a useful by-product, we find that generalising the approximation lemma in this way also simplifies its proof.
When is a function a fold or an unfold?
Jeremy Gibbons' Publications
Proceedings of Coalgebraic Methods in Computer Science. The conditions are simple, practically useful, and generic in the underlying datatype. Pointwise relational programming. However, when it comes to specific applications, the calculus can be rather awkward to use: some things are more clearly and simply expressed using variables. The combination of variables and relational combinators such as converse and choice yields a kind of nondeterministic functional programming language.
We give a semantics for such a language, and illustrate with an example application. Program optimisation, naturally.
Davies, A. Roscoe, and J. Woodcock, editors, Millenial Perspectives in Computer Science. Such laws are part and parcel of the basic toolkit for improving the efficiency of functional programs. More rarely, some polymorphic functions also possess a higher-order naturality property. One example is the operation unzip that takes lists of pairs to pairs of lists. Surprisingly, this property can be invoked to improve the asymptotic efficiency of some divide-and-conquer algorithms from O n log n to O n.
The improved algorithms make use of polymorphic recursion, and can be expressed neatly using nested datatypes, so they also serve as evidence of the practical utility of these two concepts. Generic downwards accumulations. The concept was originally introduced in an ad hoc way for just a couple of kinds of tree. We generalize the concept to an arbitrary regular datatype; the resulting definition is co-inductive. Bridging the algorithm gap: A linear-time functional program for paragraph formatting. Science of Computer Programming , 35 1 , In the algorithm design community, on the other hand, it may be well known that the textbook solution to a problem is not the most efficient possible.
Books & Games in Johannesburg CBD | Gumtree Classifieds Johannesburg CBD
However, in presenting the more efficient solution, the algorithm designer will usually omit some of the implementation details, thus creating an algorithm gap between the abstract algorithm and its concrete implementation. This is in contrast to the formal development, which usually proceeds all the way to the complete concrete implementation of the less efficient solution.
We claim that the algorithm designer is forced to omit some of the details by the relative expressive poverty of the Pascal-like languages typically used to present the solution. The greater expressiveness provided by a functional language would allow the whole story to be told in a reasonable amount of space. In this paper we use a functional language to present the development of a sophisticated algorithm all the way to the final code.
We hope to bridge the algorithm gap between abstract and concrete implementations, and thereby facilitate communication between the constructive programming and algorithm design communities. A pointless derivation of radixsort. Journal of Functional Programming , 9 3 , We address this topic with the help of an example, namely calculating the radix-sort algorithm from a more obvious specification of sorting.
The message that we hope to send is that point-free calculations are sometimes surprisingly simpler than the corresponding point-wise calculations. The under-appreciated unfold. Their dual, unfolds , are not new, but they are not nearly as well appreciated. We believe they deserve better. To illustrate, we present indeed, we calculate a number of algorithms for computing the breadth-first traversal of a tree. We specify breadth-first traversal in terms of level-order traversal , which we characterize first as a fold.
The presentation as a fold is simple, but it is inefficient, and removing the inefficiency makes it no longer a fold. We calculate a characterization as an unfold from the characterization as a fold; this unfold is equally clear, but more efficient. Polytypic downwards accumulations. We generalize the concept to an arbitrary polynomial datatype; our generalization proceeds via the notion of a path in such a datatype. Structured programming in Java.