Functional C

Preface

This book is the course material to teach a second paradigm: imperative programming, using C as the programming language. The book has been written so that it builds on the knowledge that the students have acquired during their first course on functional programming, using SML. The prerequisite of this book is that the principles of programming are already understood; this book does not specifically aim to teach `problem solving' or `programming'. This book aims to:

• Familiarise the reader with imperative programming as another way of implementing programs. The aim is to preserve the programming style, that is, the programmer thinks functionally while implementing an imperative program.
• Provide understanding of the differences between functional and imperative programming. Functional programming is a high level activity. The ordering of computations and the allocation of storage are automatic. Imperative programming, particularly in C, is a low level activity where the programmer controls both the ordering of computations and the allocation of storage. This makes imperative programming more difficult, but it offers the imperative programmer opportunities for optimisations that are not available to the functional programmer.
• Familiarise the reader with the syntax and semantics of ISO-C, especially the power of the language (at the same time stressing that power can kill). We visit all dark alleys of C, from void * to pointer arithmetic and assignments in expressions. On occasions, we use other languages (like C++ and Pascal) to illustrate concepts of imperative languages that are not present in C. C has been chosen because it is a de facto standard for imperative programming, and because its low level nature nicely contrasts with SML. Those who want to learn, for example, Modula-2 or Ada-95 afterwards should not find many difficulties.
• Reinforce the principles of programming and problem solving. This is facilitated by the use of three different languages (mathematics, a functional language, and an imperative language). The fact that these widely differing languages have common aspects makes the idea that programming principles exist and that they are useful quite natural.
• Reinforce the principle of abstraction. Throughout the book we encourage the student to look for more abstract solutions, for example, by viewing the signature of a function as an abstraction of its purpose, by using procedural abstractions (in particular higher order functions) early on, and by using data abstraction.
• Guide the student from specification and mathematics to implementation and software engineering. In the first chapters the emphasis is on writing correct functions and as we make progress the emphasis gradually shifts to transforming correct functions into efficient and reusable functions. Clean interfaces are of paramount importance, and are sacrificed for better efficiency only as a last resort.

• A specification of the problem is made.
• An appropriate algorithm is found to deliver solutions that satisfy the specification.
• The algorithm is implemented as efficiently as possible. Throughout the book, the emphasis is on this third step.

The appropriate algorithm is given in SML. SML is freely available for a range of platforms (PC's, UNIX work stations, Apple), and is therefore popular as a teaching language. As many functional languages are not too different from SML, an appendix gives a brief review of SML for those familiar with any of the other main stream functional languages, such as Miranda, Haskell, Clean, or Scheme.

As the target language to implement solutions in an imperative style we have chosen C. The choice to use C and not C++ was a difficult one. Both languages are mainstream languages, and would therefore be suitable as the target language. We have chosen C because it more clearly exposes the low level programming. To illustrate this consider the mechanisms that the languages provide for call by reference. In C, arguments must be explicitly passed as a pointer. The caller must pass the address, the callee must dereference the pointer. This in contrast with the call by reference mechanism of C++ (and Pascal and Modula-2). This explicit call by reference is a didactical asset as it clearly exposes the model behind call by reference, and its dangers (in the form of unwanted aliases).

As this book is intended to be used in a first year course, only few assumptions were made about prior knowledge of the students. Reasoning about the correctness of programs requires proof skills, which students might not have acquired at this stage. Therefore we have confined all proofs to specially marked exercises. To distinguish the programming exercises from the exercises requiring a proof, we have marked the latter with an asterisk. We are confident that the book can be used without making a single proof. However we would recommend the students to go through the proofs on a second reading. The answers to one third of the exercises are provided in Appendix A.

The student should have an understanding of the basic principles of computing. This would include base 2 arithmetic and the principles of operation of the von Neumann machine. A computer appreciation course would be most appropriate to cover this material. The book contains examples from other areas of computer science, including data bases, computer graphics, the theory of programming languages, and computer architecture. These examples can be understood without prior knowledge of these areas.