1
Introduction

Chapter Summary

The importance of representation and abstraction. The role of programming languages in computer science and the difference between computer science and software engineering. The need for metalanguages to study programming languages. Also, a short comparison of the three major programming paradigms.

Computer science studies the phenomenon of computation, where computation can be defined as the systematic transformation of representations for the purpose of solving a problem.

Let's consider as a motivating example the problem of determining a valid meeting time for a group of people on a particular day. The first step is to gather from each participant information about their availability, which raises the question of how to describe each participant's available times, that is, what representation do we chose for this information?

One possibility is to use a set of time intervals, which raises the further question of how to represent time points and at what granularity. Let's assume for simplicity that we are planning a one-hour meeting and that the available hours are numbered from 8 a.m. to 5 p.m. Using this representation, Alice may have the times 8-10, 12-1, and 2-3 available; Bob can offer 9-10 and 1-5; Carol is available from 9-10, 11-12, 1-3, and 4-5; and Daniel can make it 9-12 and 1-3. Typically, in this representation an interval a-b means the availability of the hours a through b - 1.

The next step is to find a method for extracting from this set of interval sets a (maximal) set of intervals that are covered by, or contained in, them. While this is not a very difficult task in principle, it can be quite tedious, in particular, if we have to do it without tool support.

An alternative representation that lends itself to a computation that can be easily performed by humans is to use a simple array of available hours in which unavailable hours are shown as "-". After aligning all availability arrays vertically, the potential meeting times are immediately visible as complete columns of hour numbers.

Alice 8 9 - - 12 - 2 - - Bob - 9 10 - - 1 2 3 4 Carol - 9 - 11 - 1 2 - 4 Daniel - 9 10 11 - 1 2 - -

The two possible meeting times 9-10 and 2-3 immediately stand out in this representation (as does the third-best option 1-2, which works only for three of the participants).

This example illustrates that the choice of representation can have a significant impact on its effectiveness for solving a problem, and thus awareness of representational variety is an important skill for computer scientists - or problem solvers more generally.

As it happens, the question of representation has also played a significant role in writing this book, namely: how to represent programming languages to facilitate the explanation of their fundamental concepts. In the remainder of this introduction I will discuss this aspect and lay out the contents of the book.

1.1 The Role of Programming Languages in Computer Science

One driving force of computer science is the goal of automating computations by letting machines perform them. To that end, a programming language is an interface between humans and machines that enables the description of algorithms in a form that can be understood and executed by machines. Programming languages are thus one of the most important tools for computer scientists.

Computing technology evolves rapidly with new application domains challenging programming languages to provide new or different features. Consequently, the field of programming languages constantly evolves in many different directions. Estimates of the number of programming languages range between 700 and 9000, which is evidence of the fluidity of the field. This fact has direct implications on how to study programming and programming languages. In particular, it is impossible master all or even a large subset of these languages. Therefore, to keep pace with the development, it seems more effective to study general principles of programming languages that apply to a wide range of languages instead of trying to learn individual languages one by one.

Table 1.1 Programming language abstraction hierarchy. The level of abstraction ofcomputer science concepts that are especially relevant to the study of programming languages.

Abstraction level Example 5 Meta Regular expressions, grammars, rule systems 4 Feature Syntax, semantics (scope, types, parameter passing schemas) 3 Model/Paradigm Lambda Calculus, Turing Machine, Predicate Calculus 2 Language Elm, Haskell, Lisp, C, Java, Python, Prolog 1 Program fac n = if n==1 then 1 else n*fac (n-1) 0 Computation fac 3 =? 3*fac 2 =? 3*2*fac 1 =? 3*2*1 =? 6

In addition to being indispensable as a tool for automated problem solving, programming languages play a central role in computer science as a substrate for abstraction. Computer science is suffused with abstractions. For example, an algorithm is an abstraction of computation: one algorithm describes many different computations by using parameters, and a specific computation is obtained by executing the algorithm with arguments substituted for the parameters. Turing machines, pushdown automata, and finite state machines are abstractions of physical computing machines: the exact physical details of machines are ignored, and their important characteristics are instead represented mathematically. Types are abstractions of values. And the so-called big O notation is an abstraction of run time.

The description of a programming language is an abstraction itself, an abstraction of all of the programs that can be written in the language. In studying the fundamentals of programming language we abstract from individual programming languages and focus on individual features that are abstractions of specific algorithmic idioms (loops, parameterization, scope, etc.). Moreover, in the description of programming language features we often use formalization tools, including grammars or rule systems, that live at an even higher level of abstraction. Table 1.1 shows the range of different abstraction levels. As you can see, programming languages involve many abstractions.

Since programming languages play such a pivotal role in computer science, it is obvious that they should be studied and understood well. But why should one study the fundamentals of programming languages and not just simply learn a few individual languages?

1.2 Why Study Programming Language Fundamentals?

Programming courses teach how to effectively use a particular programming language. By taking such a course combined with lots of practice and experience, one can become an excellent programmer in a specific programming language. Given how many languages exist and how quickly the landscape of languages evolves, this may not be an effective strategy to stay informed. In contrast, understanding the general principles that underly all languages empowers one to quickly grasp new features and whole new languages.

Nevertheless, to be a successful programmer, a viable strategy is to master the most popular language, or the one needed for a particular job, and then retrain whenever needed. This utilitarian view of programming languages is certainly adequate for programmers and software engineers, and it seems to be the strategy employed by coding boot camps.

However, being a computer scientist means more than to be just a programmer or a software engineer. No one would expect a physicist to be just a good car mechanic who understands the particular workings of a specific set of car models. Nor would we expect that a civil engineer is only able to build one specific kind of house or bridge. In the same way, we would be selling computer science short by expecting computer scientists to be just good programmers.

Computer science is still a young discipline and incorporates many different applied subjects that over time will likely spin off into separate disciplines. This is what happened in scientific disciplines with a longer tradition. For example, physics has led to mechanical, civil, and electrical engineering, and biology has led to medicine, agriculture, and ecology. Similarly, we will likely see software engineering in the future viewed as one specialization of computer science.

A computer scientist must understand the underlying principles of computing and how they are reflected in the languages used to describe computation. The study of programming language fundamentals abstracts from one programming language and looks more generally at the concepts that can be found in many or most programming languages. Such a more general understanding of programming languages also makes you a better and more flexible programmer, since it allows you to learn new languages more quickly. It also supports you in assessing the...