CS 135: Designing Functional Programs

For Prospective Students

As the diagram below shows, there are three different entry points to the introductory CS course sequence at UW. This page is about the sequence CS 135/136. In order to explain this sequence, we must briefly describe the others and explain something about the intentions of all of them.

Diagram of course sequences

Any introduction to computer science starts by exploring the nature of computation, how it is expressed and how it is carried out. There are many different strategies for such an exploration, but most involve some amount of programming, that is, learning to write programs that accomplish tasks. By and large, a computer scientist does not do all their programming in one language; instead, they choose a language to fit the task and the circumstances. Still, one has to start somewhere, and a first course in computer science at university usually either assumes experience in some language, or teaches some language to its students.

The major development in software in the last fifteen years has been the spread of object-oriented methods in order to develop and maintain large software systems. Languages such as Java and C++ are in use throughout industry and academia, and new languages are being developed and marketed. Many of the computer applications you may be familiar with from prior experience or media coverage were developed using these languages. Most institutions use one of these languages in their introduction to computer science.

Object-oriented languages such as Java and C++ are designed for industrial use, and are complex. Using them for an introduction to computer science is like taking students studying to be commercial pilots and putting them into the cockpit of a Boeing 747 on their first day. It would be better to use a small two-seater trainer plane, or even a flight simulator, and that is what is actually done for such students. The computer science equivalent is a teaching language, one which is not typically used commercially, but which prepares the way for the use of a more complex language.

There are some object-oriented teaching languages, but they are not in widespread use, and it is hard to find textbooks and other support materials. Another approach, the one used in CS 135/136, is to use a completely different style of language in order to explore the fundamental nature of computation. If the situations which led to the development of object-oriented languages can be explored by using this other style of language, then students will be in a good position to move to a complex object-oriented language.

The teaching language in CS 135 is Racket, a simple functional language that was used in teaching at MIT for more than twenty years, and is currently in use at several institutions in North America (Berkeley, Caltech, Brown, Northeastern, Chicago, Utah). A functional language expresses computation as the application of functions to data. You have already had exposure to this concept through your elementary and high-school mathematics courses. Suppose we define the functions sum(x,y)=x+y and prod(x,y)=xy . If we then ask the value of the expression prod(sum(1,3), sum(2,4)) , it is simple to evaluate it by substitution:

prod(sum(1,3), sum(2,4)) = prod(4, sum(2,4)) = prod(4,6) = 24

Racket makes two changes to this standard notation; it puts the name of the function inside the brackets instead of outside, and replaces the commas with spaces. In Racket, the same expression would be written as (prod (sum 1 3) (sum 2 4)). The rule for evaluation then becomes: find a matching pair of brackets with no other brackets inside it. What is inside is a function name and some data. Substitute: that is, replace the brackets and what's inside with the value of the function applied to the data. Continue doing this until you're left with a single value.

(prod (sum 1 3) (sum 2 4)) = (prod 4 (sum 2 4)) = (prod 4 6) = 24

Now you know Racket! Well, not quite. Racket has some built-in functions to improve clarity and expressiveness (it uses * and + instead of prod and sum), and allows you to use them to define your own functions. Here, computation is the definition of functions and evaluation of expressions.

In this simple framework, CS 135 explores concepts in introductory computer science, making connections to Math 135/137, aiming at deep understanding. Just because the framework is simple doesn't mean the course is; the language we use doesn't get in the way of the intellectual challenges, and in fact allows us to get to them sooner, because less time is spent on language details. We believe CS 135 is suitable both for students with no prior exposure to programming, and those who have taken programming courses in high school. Those with prior experience will not have seen material of this form before, and can benefit from extensive bonus/challenge exercises (see the Enhancements page for more details). We also believe that the enhancement material will be attractive to students contemplating taking the advanced Math sections.

We recommend CS 135 for students who like math and who are interested in learning more about computer science. It is required for CS majors, hence the label "CS majors and enthusiasts" in the diagram above. For those unsure of their math ability or unconvinced of the benefits of learning some computer science, CS 115 uses the same approach as CS 135 but only covers about two-thirds of the material.

CS 136 interleaves continued exploration using Racket with an introduction to the industrially-successful C language, leading to a deeper understanding of the varieties of ways in which computation can be expressed, and awareness of the issues that arise in real-world computation. Students leaving CS 136 will have had a representative look at computer science and the CS program at Waterloo, and will be prepared for future CS courses in either the major or non-major sequences.

CS 116 explores some of the same issues as CS 136 using the scripting language Python. It prepares students for CS non-major courses. Students leaving CS 116 who are interested in a CS major, joint, or double honours can take CS 136 to gain access to CS major courses.

Students with a high level of mathematical ability and keen interest in computer science can opt for CS 145/146, which cover material from CS 135 and CS 136 (respectively) plus enrichment topics. These courses are particularly recommended to those taking the advanced Math courses. More information is available in the section of the same name of the CS 145 course Web page.

The textbook for CS 135, 115, and 145 (How To Design Programs, by Felleisen, Findler, Flatt, and Krishnamurthi) is available on-line (though we recommend that you buy a physical copy). If you have a personal computer and can install software on it, you can try out Racket.

We asked CS 135 students (who chose it at a time when most students took a Java-based course instead) what they would say to prospective students. Here are some of their responses.

So far, I've found the course to be as described in the outlines: it is a course for those with no experience and those with experience at the same time. As an experienced programmer (OOP with C++ and PHP), I've found this course requires a considerable amount of analysis of functions at a more fundamental level than the two preceding languages, and, consequently, has provided me with some insight as to "why" and "how" functions in more common languages work. Prior to this course, many things I took for granted concerning programming; that is no longer the case.

I would suggest to the student that CS 135 places emphasis on the logic behind programming rather than the idea of programming in general, and, particularly if he/she is majoring in CS, that the knowledge gained in CS 135 is more helpful in the long run for future CS courses than [the courses using Java]. In fact, many students capable of attempting [the advanced Java course] with reasonable success ought to take CS 135 instead, for those very reasons; they may be able to program in Java, but they may not fully grasp what is happening at a much simpler level within the language, which I believe CS 135 helps students do.

It gives the ideas a simple turn that makes them (relatively) easier to understand.

Those who think they know programming -- this course will prove to you that you do not know anything -- so TAKE IT.

We'll leave the last word to the parent of a CS 135 student, a math professor who looked over the course materials and concluded:

Racket is beautiful!

We would be happy to answer any questions you might have. The Personnel page has instructor contact information.

Last modified on Friday, 27 April 2018, at 19:04 hours.