We have shown a systematic method that succeeds in designing efficient implementations for many problems in many application domains starting with clear specifications of these problems using high-level language constructs. The method is systematic by being based on the language constructs used in the specifications and being guided by the cost considerations taken from the application domains.

The method, even though consisting of Steps Iterate, Incrementalize, and Implement in order, is driven by the middle step—Step Incrementalize. Because efficient computations on nontrivial input must proceed repeatedly on incremented input, Step Incrementalize aims to make the computation on each incremented input efficient by storing and reusing values computed on the previous input. Steps Iterate and Implement are enabling mechanisms: to maximize reuse by Step Incrementalize, Step Iterate determines a minimum input increment to take repeatedly; to support efficient access of the stored values by Step Incrementalize, Step Implement designs a combination of linked and indexed data structures to hold the values.

We first take a deeper look at incrementalization, showing how to systematically exploit the previous result, intermediate results, and auxiliary values for incremental computation. This will use simple examples specified using recursive functions, followed by several different sorting programs as additional examples. We then discuss abstractions in general, focusing on the importance of and principles for not only building up, but also breaking through, abstractions. The latter may sound surprising at first, but it is natural when query functions are incrementalized with respect to updates.

Many complex computational problems are most clearly and easily specified using logic rules. Logic rules state that if certain hypotheses hold then certain conclusions hold. These rules can be used to infer new facts from given facts. Example applications include queries in databases, analysis of computer programs, and reasoning about security policies. Datalog, which stands for Database logic, is an important rule-based language for specifying how new facts can be inferred from existing facts. Its fixed-point semantics allows the computation of the set of all facts that can be inferred from a given set of facts. It is sufficiently powerful for expressing many practical analysis problems.

While a Datalog program can be easily implemented using a logic programming system, such as a Prolog system, evaluated using various evaluation methods, such as well-established tabling methods, or rewritten using transformation methods for more efficient evaluation, such as using the well-known magic-sets method, these implementations are typically for fast prototyping. The running times of Datalog programs implemented using these methods can vary dramatically depending on the order of rules and the order of hypotheses in a rule. Even less is known about the space usage. Developing and implementing efficient algorithms specialized for any given set of rules and with time and space guarantees is a nontrivial, recurring task.

We first look at computational problems programmed using loops over numbers and arrays. A loop is a command for repeating a sequence of operations. A number is an integer or a real number with an internal representation in a computer. An array is an arrangement of computer memory elements in one or more dimensions. Problems involving arithmetic on numbers were the first problems for which computing devices were built. Problems involving operations on arrays were at the center of many subsequent larger computer applications. Because nontrivial computations involve performing operations iteratively, loops are a most commonly used, most important construct in programming solutions to problems.

Clear and straightforward problem solutions tend to have expensive computations in loops, where the values that these computations depend on are updated slightly in each iteration. To improve efficiency, the results of these computations can be stored and incrementally maintained with respect to updates to the values that they depend on. The transformation of programs to achieve this is called incrementalization.

We will use a small example and several variations to explain the basic ideas of incrementalization. We then describe two larger examples: one in hardware design, to show additional loop optimizations enabled by incrementalization, and the other in image processing, to show handling of nested loops and arrays in incrementalization. We discuss the need for higher-level languages at the end.

Many combinatorics and optimization problems can be solved straightforwardly by combining solutions to subproblems, where the subproblems may overlap in complicated manners. Such ways of solving the problems can be easily specified using recursive functions—functions whose definitions involve calls to the functions themselves, called recursive calls. The recursive calls are used for solving subproblems. Applications include many kinds of data analysis and decision-making problems, such as the great many kinds of analysis and manipulations needed on sequences, be they sequences in biological computing, document processing, financial analysis, or sensor data analysis.

Straightforward evaluation of recursive functions may be inefficient, and may in fact be extremely inefficient when they are used to solve overlapping subproblems, because subproblems may share subsubproblems, and common subsubproblems may be solved repeatedly. An efficient algorithm solves every subsubproblem just once, saves the result appropriately, and reuses the result when the subsubproblem is encountered again. Such algorithms are called dynamic programming algorithms. To arrive at such efficient algorithms, we must determine how efficient computations should proceed, and how computed results should be saved and reused. These correspond to Steps Iterate and Incrementalize. Step Implement just determines a straightforward way of storing the saved results in appropriate data structures.

Design may refer to both the process of creating a plan, a scheme, or generally an organization of elements, for accomplishing a goal, and the result of that process. Wikipedia states that design is usually considered in the context of applied arts, engineering, architecture, and other creative endeavors, and normally requires considering aesthetic, functional, and many other aspects of an object or a process [319]. In the context of this book in the computing world, design refers to the creation of computer programs, including algorithmic steps and data representations, that satisfy given requirements.

Design can be exciting because it is linked to problem solving, creation, accomplishments, and so on. It may also be frustrating because it is also linked to details, restrictions, retries, and the like. In the computing world, the creation of a computer program to accomplish a computation task clearly requires problem solving; the sense of excitement in it is easy to perceive by anyone who ever did it. At the same time, one needs to mind computation details and obey given restrictions in often repeated trials; the sense of frustration in the process is also hard to miss.

Systematic design refers to step-by-step processes to go from problem descriptions to desired results, in contrast to ad hoc techniques. For program design, it refers to step-wise procedures to go from specifications prescribing what to compute to implementations realizing how to compute. The systematic nature is important for reproducing, automating, and enhancing the creation or development processes. Clarity of the specifications is important for understanding, deploying, and evolving the programs. Efficiency of the implementations is important for their acceptance, usage, and survival.

Most computer applications must handle collections of data. A set is a collection of distinct elements. Operations on sets, such as union and difference of the elements of two sets, are higher-level than operations on arrays, which are assignment and access of elements at indexed positions. The largest class of computer applications that involve collections is database applications, which typically handle large collections of data and provide many kinds of queries and other functionalities. Because of their higher-level nature, sets and set operations can be used to express problem solutions more clearly and easily, and have been used increasingly in programming languages, though typically only in applications that are not performance critical.

Problem solutions programmed using high-level set operations typically have performance problems, because high-level set operations typically involve many elements and are often repeatedly performed as sets are updated. To improve performance of applications programmed using sets, expensive high-level operations on sets must be transformed into efficient incremental operations, and sets must be implemented using data structures that support efficient incremental operations. These correspond to Steps Incrementalize and Implement, respectively. Step Iterate just determines a simple way of iteration that adds one element at a time to a set.

Because graph problems are typically specified using sets, we first describe the method using the graph reachability problem as an example, showing how efficient graph algorithms can be derived systematically.

From clarity to efficiency: systematic program design

At the center of computer science, there are two major concerns of study: what to compute, and how to compute efficiently. Problem solving involves going from clear specifications for “what” to efficient implementations for “how”. Unfortunately, there is generally a conflict between clarity and efficiency, because clear specifications usually correspond to straightforward implementations, not at all efficient, whereas efficient implementations are usually sophisticated, not at all clear. What is needed is a general and systematic method to go from clear specifications to efficient implementations.

We give example problems from various application domains and discuss the challenges that lead to the need for a general and systematic method. The example problems are for database queries, hardware design, image processing, string processing, graph analysis, security policy frameworks, program analysis and verification, and mining semi-structured data. The challenges are to ensure correctness and efficiency of developed programs and to reduce costs of development and maintenance.

Example problems and application domains

Database queries. Database queries matter to our everyday life, because databases are used in many important day-to-day applications. Consider an example where data about professors, courses, books, and students are stored, and we want to find all professor-course pairs where the professor uses any of his own books as the textbook for the course and any of his own students as the teaching assistant for the course.

The efficiency of a program is measured in terms of its memory requirements and its running time. In this chapter we shall introduce the concepts stack and heap because a basic understanding of these concepts is necessary in order to understand the memory management of the system, including the garbage collection.

Furthermore, we shall study techniques that in many cases can be used to improve the efficiency of a given function, where the idea is to search for a more general function, whose declaration has a certain form called iterative or tail recursive. Two techniques for deriving tail-recursive functions will be presented: One is based on using accumulating parameters and the other is based on the concept of a continuation, that represents the rest of the computation. The continuation-based technique is generally applicable. The technique using accumulating parameters applies in certain cases only, but when applicable it usually gives the best results. We give examples showing the usefulness of these programming techniques.

We relate the notion of iterative function to while loops and provide examples showing that tail-recursive programs are in fact running faster than the corresponding programs using while loops.

The techniques for deriving tail-recursive functions are useful programming techniques that often can be used to obtain performance gains. The techniques do not replace a conscious choice of good algorithms and data structures. For a systematic study of efficient algorithms, we refer to textbooks on “Algorithms and Data Structures.”

The purpose of this book is to introduce a wide range of readers – from the professional programmer to the computer science student – to the rich world of functional programming using the F# programming language. The book is intended as the textbook in a course on functional programming and aims at showing the role of functional programming in a wide spectrum of applications ranging from computer science examples over database examples to systems that engage in a dialogue with a user.

Why functional programming u sing F#?

Functional programming languages have existed in academia for more than a quarter of a century, starting with the untyped Lisp language, followed by strongly typed languages like Haskell and Standard ML.

The penetration of functional languages to the software industry has, nevertheless, been surprisingly slow. The reason is probably lack of support of functional languages by commercial software development platforms, and software development managers are reluctant to base software development on languages living in a non-commercial environment.

This state of affairs has been changed completely by the appearance of F#, an open-source, full-blown functional language integrated in the Visual Studio development platform and with access to all features in the .NET program library.

Processing text files containing structured data is a common problem in programming – you may just think of analysing any kind of textual data generated by electronic equipment or retrieved data from the web.

In this chapter we show how such programs can be made in a systematic and elegant way using F# and the .NET library. Data are extracted from text files using functions from the RegularExpressions library. The data processing of the extracted data is done with a systematic use of F# collections types list <′a>, Map <′a,′b> and Set<′a>. Easy access from F# programs to the extensive text processing features of the .NET library is given in a special TextProcessing library that can be copied from the home page of the book. The chapter centers on a real-world example illustrating the techniques.

Time performance of programs is always a problem, even with todays very fast computers. Poor performance of text processing programs is often caused by operations on very long strings. The method in this chapter uses three strategies to avoid using very long strings:

1. 1. Text input is in most cases read and processed in small pieces (one or a few lines).

2. 2. Text is generated and written in small pieces.

3. 3. Large amounts of internal program data are stored in many small pieces in F# collections like list, set or map.

Throughout the book we have used programs from the F# core library and from the .NET library, and we have seen that programs from these libraries are reused in many different applications. In this chapter we show how the user can make own libraries by means of modules consisting of signature and implementation files. The implementation file contains the declarations of the entities in the library while the signature file specifies the user's interface to the library.

Overloaded operators are defined by adding augmentations to type definitions. Type augmentations can also be used to customize the equality and comparison operators and the string conversion function. Libraries with polymorphic types are obtained by using signatures containing type variables.

These features of the module system are illustrated by small examples: plane geometric vectors and queues of values with arbitrary type. The last part of the chapter illustrates the module system by a larger example of piecewise linear plane curves. The curve library is used to describe the recursively defined family of Hilbert curves, and these curves are shown in a window using the .NET library. The theme of an exercise is a picture library used to describe families of recursively defined pictures like Escher's fishes.

This chapter is about programs where the dynamic allocation of computer resources like processor time and memory becomes an issue. We consider two different kinds of programs together with programming constructs to obtain the wanted management of computer resources:

1. 1. Asynchronous, reactive programs spending most of the wall-clock time awaiting a request or a response from an external agent. A crucial problem for such a program is to minimize the resource demand while the program is waiting.

2. 2. Parallel programs exploiting the multi-core processor of the computer by performing different parts of the computation concurrently on different cores.

The construction of asynchronous and parallel programs is based on the hardware features in the computer and software features in system software as described in Sections 13.1 and 13.2. Section 13.3 addresses common challenges and pitfalls in parallel programming. Section 13.4 describes the async computation expression and illustrates its use by some simple examples. Section 13.5 describes how asynchronous computations can be used to make reactive, asynchronous programs with a very low resource demand. Section 13.6 describes some of the library functions for parallel programming and their use in achieving computations executing concurrently on several cores.

A computation expression of F# provides the means to express a specific kind of computations in a way where low-level details are hidden and only visible through the use of special syntactic constructs like yield, let!, return, etc. These constructs are not part of the normal F# syntax and are only allowed inside computation expressions. Each kind of computation expression is defined by a computation builder object that contains the meaning of the special constructs.

A computation expression ce belonging to the builder object comp appears in the F# program in a construct of the form:

comp {ce}

This construct is an expression that evaluates to a value called a computation.

We have already seen examples of computation expressions in the form of sequence expressions with builder object seq (cf. Table 11.2) and query expressions with builder object query (cf. Section 11.8). The sequence computation expressions allow us to define computations on sequences without having to bother about the laziness and other implementation details, and the query expressions allow you to make database queries. In Chapter 13 we introduce asynchronous computation expressions with builder object async where you can define asynchronous computations without having to bother about low-level details in the current state of the system. The seq, query and async computation expressions are parts of F#.

In this chapter we will introduce some of the main concepts of functional programming languages. In particular we will introduce the concepts of value, expression, declaration, recursive function and type. Furthermore, to explain the meaning of programs we will introduce the notions: binding, environment and evaluation of expressions.

The purpose of the chapter is to acquaint the reader with these concepts, in order to address interesting problems from the very beginning. The reader will obtain a thorough knowledge of these concepts and skills in applying them as we elaborate on them through-out this book.

There is support of both compilation of F# programs to executable code and the execution of programs in an interactive mode. The programs in this book are usually illustrated by the use of the interactive mode.

The interface of the interactive F# compiler is very advanced as, for example, structured values like tuples, lists, trees and functions can be communicated directly between the user and the system without any conversions. Thus, it is very easy to experiment with programs and program designs and this allows us to focus on the main structures of programs and program designs, that is, the core of programming, as input and output of structured values can be handled by the F# system.