Class 02: Thinking Formally

Held Monday, August 28, 2000

Summary

Today we continue our exploration of computer science by writing our first algorithm and considering issues of formal languages.

Notes

• Assignment:
  • Scan through the introductory HTML lab
• If you haven't done so already, please fill out the introductory survey.
  • My preliminary responses to your questions are now available. My responses to the CS152 survey are also available. You can even learn about some of my undergraduate grades.
  • Thanks to those of you who reminded me to consider multicultural issues in my teaching style. I hope that most of you can deal with my somewhat informal style.
  • For those of you who are concerned: most of you are at the beginning level, having used computers primarily for word processing, games, and sometimes surfing the 'net.
  • I was impressed that at least one of you read my CV and at least one of you read my list of CDs I've listened to recently.
• Every Monday at noon, the department hosts a brown-bag film festival at noon. See interesting talks by great computer scientists. (Okay, sometimes you see mediocre talks by great computer scientists, but then we all make sarcastic comments.) I'm pretty sure that you can pick up a bag lunch if you're on meal plan.
• If you've talked to students in the other section of 151, you may have noted that the two sections are following a different schedule (with some difference in topics). Each faculty member teaches 151 differently. We're starting Scheme a little bit after the other section, but we'll catch up after a few weeks.
• My wife managed to break a toe yesterday, so I won't be in my office during office hours today.

Overview

• Why are you here?
• The need for formal languages
• HTML: A formal language for representing hypertexts
• Paradigms for programming and problem solving

Why are you here?

• I wrote the question on the board, but never got to it in class.
• I also wrote the question on the survey, but I'd like to hear some public answers.
• So, we'll go back to the hat trick for volunteers.

The Need for Formality

• Some people wonder why we need computer languages like Scheme, Pascal, C, Java, and the ilk.
• In part, it's probably because the computer elite want to maintain their sense of superiority over the masses.
• In greater part, it's because English and other ``natural'' languages can be ambiguous. At the very least, they have many similar structures that are interpreted very differently. Consider the classic pair of
  • Time flies like an arrow.
  • Fruit flies like a banana.
• As I've said (and will say again), computers are sentient and malicious. it often seems that they'll do their best to misinterpret whatever it is you write.
• As an exercise, we're going to write a set of instructions that would help a foolish person (SamR) make a peanut butter and jelly sandwich.
  • One person will be the recorder.
  • I'll use the hat trick to get people to write it.
  • I'll then follow your instructions to the best of my ability.
  • You will then have a chance to refine your instructions.
  • I apologize in advance for any food wasted.

Programming Paradigms

• Now that we've established the need for formal languages, we need to think a little bit about the design of such languages.
• It turns out that there are different ways of thinking about problem solving, and these different ways of thinking lead to different types of languages. (We often call these problem-solving paradigms.)
• Computer Scientists have developed a number of strategies for looking at algorithm and data design, including
  • procedural / imperative
  • object-oriented
  • functional
  • logical
  • declarative
• While individual definitions of each category may differ, most definitions have some similarities.
• In the imperative paradigm, algorithms are sets of instructions not unlike standard recipes. Do this. Do that. Do whatever N times.
  • Common imperative languages: Ada, Basic, C, Fortran, Pascal
• In the object-oriented paradigm, algorithms are sets of objects that interact. Most typically, objects are reactive: They exectute algorithms in response to events that happen. For example, most of you have an algorithm that says "When the instructor asks for volunteers, scrunch down in my seat."
  • Common object-oriented languages: C++, Java, Smalltalk
• In the functional paradigm, programs are collections of function definitions and function applications. At times, functional programming feels mathematical, but it can also be used in many other domains. You may remember dealing with the compose function in mathematics. Surprisingly enough, functional languages are the only ones that include something like compose.
  • Common functional languages: Haskell, LISP, ML, Scheme
• In the declarative paradigm, programs are collections of facts. Behind the scenes, there is something that knows how to deal with the facts. For example, we can give an experienced baker a list of ingredients for cookies and not worry about formal instructions.
  • Common declarative languages: Prolog, SQL
• As an example, we'll consider the problem of updating grades using each of the paradigms.
• At Grinnell, we deem it important that students study a variety of paradigms early in their careers, whether or not they are computer science majors.
  • As I said before, thinking differently is part of a liberal arts education.
• In CS151, you will study functional and imperative programming.
• If you go on to CS152, you will study object-oriented and imperative programming.