A Note For Those With Prior Computing Experience
Students coming into the first-year CS courses at the University of Waterloo (CS 115, CS 135, CS 145) often misunderstand how different the content of these courses is from what they might have encountered earlier, either in a high-school computing class or through self-study. This is a brief note explaining some of those differences and how to cope with them.
Nearly all computing courses in high schools, most introductory textbooks, and most tutorial materials available on the Web start by teaching the use of an imperative programming language. They use languages such as Java, C++, C#, C, Python, Ruby, Perl, Javascript, Visual Basic, or Turing. These languages differ in syntax, but share fundamental ideas, leading some people to expect that these ideas appear in all programming languages, and that learning to use a new language is just a matter of translating old ideas into a slightly-changed form. This is superficially true for many concepts shared by these languages, but is not true for Racket, the language used in CS 145/135/115. Racket is a functional programming language.
I will underline this substantial difference by first briefly describing the features of an imperative programming language, even though, if you're reading this note, you should already know one.
An imperative programming language provides ways of naming values (state variables), which may change during the course of the computation. The change may take place by means of an assignment statement, which computes a new value for a variable. A sequence of these statements specifies several such changes that are carried out (executed), one at a time. The resulting program fragment may look something like this:
integer j,k;
j = 1;
k = 2;
j = j + k;
After this sequence of statements is executed, j will
have the value 3, and k will have the value 2.
A sequence may be executed conditionally, if some relationship among the variables holds, such as one being equal to another. A sequence may also be repeated as long as some relationship among the variables holds; this is typically called a loop.
An imperative program typically communicates its results by means of output statements that print the values of variables, perhaps with some additional text or formatting, and may obtain data to compute with by means of input statements. Input/output, or I/O, is typically one of the first topics covered, as without it one cannot see the effects of a program.
Finally, programs can be made much more concise by writing methods or functions that generalize similar-looking code. For example, we might have the need, in some computation, to repeatedly square two variables and add the results together. We can do this with one piece of code that names two parameters and performs this computation on them. It might look like this:
function square (integer i, j) {
integer k;
k = i * i;
k = k + (j * j);
return k;
}
This code is longer than it needs to be, but never mind about
that. The point is that the function may be applied to different
arguments at several points in the program. We might
say square(3,m) at one point, and square(n,p)
at another.
Almost none of these ideas are used in CS 115/135/145.
They are all present in the full Racket language, but not in the teaching languages (subsets of Racket) used in the first CS courses. That is because they are peripheral, not central to the ideas of functional programming. We can do a lot of computing without them. In fact, their absence makes many concepts easier to explain and to reason about.
From the discussion above, functional programming retains a few basic ideas. The idea of variables survives in the sense that names can be given to values, though there is no assignment statement, so variables should properly be called constants. In fact, there are no statements. A program is a sequence of definitions (of constants and functions), and expressions. The first assignment statement we saw above, j = j + k;, had the expression j + k within it. Statements do not have values, but expressions do. The syntax is different in Racket: this expression would be written (+ j k), but the idea is the same.
Because there are no assignment statements, the body of a function definition consists of a single expression. Here is how the square function might be written in Racket:
(define (square j k)
(+ (* j j) (* k k)))
When a Racket program is run, all expressions are evaluated and their values are printed. There is therefore no need to talk about I/O, at least in a first course.
Racket does not have conditional statements, but it has conditional expressions, which have values. The teaching languages do not have loops. A form of repetition can be achieved by the use of recursion (using a function, with modified arguments, in the body expression of its definition).
To someone who knows an imperative programming language, this situation may seem crippled, as if it would be very hard to express computation under such limitations. In fact, the opposite is true. The simplicity of the teaching languages means that relatively little time is spent on learning the language and more time is spent exploring ideas of computer science. Programs are usually shorter and clearer. We can precisely describe the meaning of a program, so that error messages are easier to understand, and programming mistakes easier to correct.
If you have created a spreadsheet using an application like Microsoft Excel, you have done a primitive form of functional programming. An Excel formula is an expression, made up of applications of built-in functions. A formula may contain a conditional expression which has a value. The names of cells are like the names of variables or constants. Excel does not make it easy to define your own functions, though, and it lacks one very powerful feature of Racket and other functional programming languages: the idea that functions are values. But this is a topic to be taken up in lecture.
When writing a program in Racket, restrain any urge you might have to think about how you would have done it in an imperative programming language. That will likely just get in the way and result in your taking longer to complete the task properly. The connections between imperative and functional programming can be subtle and are best discerned after some experience with both. Instead, try to immerse yourself in the functional way of doing things, as if you had no prior exposure to computing. Later, you will be able to blend the two worlds and come out further ahead than if you only knew about one.