1. What is Computation?

MIT OpenCourseWare43:052019-07-31English

This is the first lecture in MIT’s introduction to programming in Python. The most useful takeaway is that computers only carry out the steps you explicitly write down. They don’t infer your goal or automatically recalculate earlier results.

Overview

1. What is Computation?

Key points

  • The course builds conceptual understanding, programming skills, and problem-solving ability. Beginners should look through the problem sets ahead of time and work through the code shown in class themselves, rather than just watching the demonstrations.
  • A computer’s basic jobs are to perform calculations and store the results. Programmers can combine the basic operations built into a language to define new computations.
  • An algorithm does more than state a goal. It also gives steps that can be carried out, control flow that determines when to jump or repeat, and a clear stopping condition.
  • A stored-program computer can switch to a different sequence of instructions, letting the same machine perform different tasks. The result of a test can change the program counter so that execution skips or repeats certain instructions.
  • Correct syntax doesn’t mean an operation makes sense for the types involved. Even if a program doesn’t report an error, its actual result may differ from what the programmer expected.
  • In Python, an object’s type determines which operations it supports. Adding, subtracting, or multiplying two integers produces an integer. If either operand is a float, the result is a float, and division with `/` produces a float.
  • Assignment first evaluates the expression on the right, then binds the name on the left to that value. Rebinding `radius` doesn’t automatically update the previously calculated `area`.

Chapter notes

Course Goals and Practice Tips

  • Ana Bell opens 6.0001 and 6.00. Eric Grimson will give some of the lectures later in the semester. This session starts with the course structure, then gives an overview of what computers do before moving on to Python basics, including arithmetic operations, variables, and types.
  • The course moves quickly and gets harder fast. Before class, download and open the slides and code posted in advance, follow along with the in-class exercises, and take notes in the code so you can review it later. Read through each problem set as soon as it’s posted, but don’t feel you have to start solving it right away. Seeing the terms in advance helps you connect them to the problems when they come up in class.
  • You can’t learn to program just by watching the instructor write code. Type it out yourself as you follow along. Beginners don’t need to worry that entering a few commands in Anaconda will break their computer. Go ahead and try them to see what happens.
  • The course has three learning goals: understand the concepts, build programming skills, and learn to solve problems. Lectures teach the concepts, exams test how well you understand them, and problem sets build problem-solving skills. Writing code yourself over and over is part of all three goals.
  • The programming portion starts with how to choose which objects to create, how to represent knowledge with data structures, and how to use control flow so a program can make decisions instead of just running steps in order. Next, you learn to write clear, modular, understandable code so others can read and use it and so you can still understand your own assignments when you look back at them a year later.
  • The final part focuses more on computer science. Once you’ve learned to write programs in Python, you learn to compare the efficiency of different programs and decide which algorithm is better.

From Computation to Executable Algorithms

  • A computer’s two basic jobs are performing calculations and storing results. It can perform about a billion calculations per second, and having hundreds of GB of storage isn’t unusual. Programming languages have built-in operations such as addition, subtraction, and multiplication, which programmers can combine to define new computations.
  • Declarative knowledge states a fact, such as “Someone will win a Google Cardboard before class ends.” Imperative knowledge gives a series of steps for achieving a result. If you simply tell the machine that someone will win, it doesn’t know how to pick the winner.
  • To avoid letting personal preferences influence a manual pick, the raffle uses Python’s `random.randint` to draw 75 from the range 16 to 272, then looks it up on the sign-up sheet to identify Lauren Ziove as the winner.
  • “If y² = x, then y is a square root of x” is declarative knowledge: it only states a condition the result must satisfy. An executable algorithm starts with a guess g. For example, if x = 16 and g = 3, then g² = 9, which isn’t close enough to 16, so the new guess is the average of g and x/g. If g² is already close enough to x, stop and return g.
  • The square-root algorithm has three parts: steps to carry out in order, control flow that determines when to repeat them, and a stopping condition. Repeat the calculation with each new guess until the result is close enough to the target, for example by setting the allowed error to 0.01 or 0.0001.

Stored Programs and Instruction Execution

  • An algorithm is a set of steps for completing a task, and you can give those steps to a computer to carry out. Early fixed-program computers could only do what they were set up to do. For example, a calculator that can only add, subtract, multiply, and divide can’t draw graphs or send email.
  • To do a different task with a fixed-program computer, you have to build another machine. A stored-program computer, on the other hand, can store and execute a sequence of instructions. Change the sequence, and the same machine can do a different task.
  • Basic computer architecture includes memory, input and output, an arithmetic logic unit (ALU), and a control unit. Memory stores both data and instructions, and the ALU performs basic operations like addition and subtraction.
  • The program counter in the control unit starts at the first instruction. The control unit fetches the current instruction and passes it to the ALU. For addition, for example, the ALU can fetch two numbers from memory and write the result back to memory. After an instruction is executed, the program counter usually increases by one to move to the next instruction.
  • A test that compares two values returns true or false. Based on that result, the program can continue to the next instruction or change the program counter to skip instructions or go back to the beginning and repeat them. After the last instruction runs, the computer can output the result.
  • Alan Turing showed that any computable task can be done with just a paper tape and six basic operations: move left, move right, read, write, scan, and do nothing. Programming languages provide more convenient basic operations. Any computation you can do in Python can, in theory, also be done in another programming language.

Syntax, Semantics, and Program Errors

  • English combines words into phrases and sentences. Python combines things like floating-point numbers, Boolean values, and strings with basic operators like addition and subtraction to form expressions. Expressions have both a value and a meaning in the language.
  • Syntax determines whether parts can be combined in a particular form. “Cat dog boy,” three nouns in a row, is ungrammatical, while “Cat hugs boy” follows a noun–verb–noun structure. Static semantics asks whether something that has the right form makes sense. You can multiply the numbers in `3.2 × 5`, but adding a string to a number doesn’t make sense even though it follows the operand–operator–operand pattern.
  • An English sentence can follow the rules of syntax and static semantics and still be ambiguous. “Flying planes can be dangerous” could mean that piloting planes is dangerous or that planes in flight are dangerous. A program, by contrast, has only one meaning: the computer just executes the instructions you wrote and won’t decide to add a variable on its own.
  • Python can easily catch syntax errors. The error message points to the line with the problem so you can go back and fix it. If a static semantic error occurs in a branch, Python only catches it when execution reaches that branch.
  • An unexpected result isn’t the same as an error message. If you expect a test case to output `0` but it outputs `10`, the program hasn’t changed the answer on its own. It has faithfully carried out the instructions you wrote. A program can also crash and stop running, or it can keep running without stopping. In the latter case, you don’t have to restart the computer to stop it.
  • A Python program consists of a series of definitions and commands. Expressions are evaluated, while commands tell the interpreter to do something. You can test a simple command like `2 + 4` in the interactive shell on the right, or write and run more complex, multiline programs in the editor on the left.

Python Objects, Types, and Operations

  • Everything in Python is an object. Programs work with data by operating on objects, and an object’s type determines which operations it supports. A scalar object can’t be broken down further, as with the integer `5`. A non-scalar object has internal structure, as with the list `[5, 6, 7, 8]`, which can be broken down into its elements.
  • The scalar types listed in this chapter are integers (`int`), floating-point numbers (`float`), Booleans (`bool`), and `NoneType`. The only Boolean values are `True` and `False`, and they must start with capital letters. `NoneType` has only one value, `None`. You can check an object’s type with `type(object)`. For example, `type(5)` shows that `5` is an integer.
  • To convert a type, put the object you want to convert in parentheses after the name of the target type. For example, `float(3)` gives `3.0`. When you use `int()` to convert a float to an integer, it keeps only the integer part without rounding.
  • Entering `3 + 2` in the interactive shell displays the result, `5`, but that’s just for the programmer to see. Writing the same line in a program and running it doesn’t produce output. To explicitly output the result, write `print(3 + 2)`. That prints `5` to the console.
  • Objects and operators can form expressions, which evaluate to a value. When both operands in addition, subtraction, or multiplication are integers, the result is an integer. If at least one is a float, the result is a float, and division with `/` always produces a float.
  • `i % j` gives the remainder when `i` is divided by `j`, and `i ** j` gives `i` raised to the power of `j`. Operations follow the usual mathematical order of precedence, and you can use parentheses to change the order of evaluation.

Variable Assignment and Rebinding

  • Use descriptive variable names to store values so later code can reuse those values by name. In Python, `=` binds the value obtained on the right to the variable name on the left. For example, `pi = 3.14159` directly binds a float, while `pi_approx = 22 / 7` first performs the division and then binds the result.
  • To calculate the area of a circle, first bind `pi` to `3.14159` and `radius` to `2.2`. When Python runs the area assignment, it looks up the values currently bound to those two names, evaluates the expression, and binds the resulting float to `area`.
  • An assignment statement isn’t a mathematical equation. On the left is the variable name to bind, and on the right is the expression to evaluate. If you want the computer to find `X`, you first have to work out the formula and then explicitly tell it how to calculate the value, rather than just giving it an equation and expecting it to solve it on its own.
  • A new assignment can rebind the same variable name. When `radius = radius + 1` runs, it uses `2.2`, the value previously bound to `radius`, to calculate `3.2`, then binds `radius` to the new value. After that, you can no longer access the original `2.2` through `radius`. If nothing references the old value anymore, Python’s garbage collector may reclaim it.
  • After `radius` changes, `area` still holds the result of the previous calculation because the program only ran the radius assignment and didn’t rerun the area assignment. To update `area`, you have to run the statement that calculates the area again after changing the radius.

What it answers

What’s the difference between declarative and imperative knowledge?
Declarative knowledge states a fact, such as the relationship a square root satisfies. Imperative knowledge gives steps for finding the answer. For example, check whether the current guess is close enough. If it isn’t, average the current guess with the original number divided by that guess, then repeat.
How does a computer skip or repeat instructions?
The program counter usually advances to the next instruction. When the program reaches a test, the result can change where the counter points, letting the program skip instructions or jump back to an earlier one.
Why do I see `5` when I enter `3 + 2` in an interactive environment, but get no output from a script?
The interactive environment displays the result of evaluating the expression. An expression on its own in a script doesn’t explicitly output anything. Use `print(3 + 2)`.
Does converting a float to an integer round it?
No. The conversion cuts off the fractional part and keeps only the integer part.
Why doesn’t `area` change after running `radius = radius + 1`?
That statement only uses the old radius to calculate a new value and binds `radius` to it. To update `area`, you have to rerun the assignment statement that calculates the area.

Quotes

The more you practice, the better you get at it.
Computers only do what you tell them to do.
And the last part of the recipe was a way to stop, right?
We never told it to recalculate the value of area.

Mentioned

  • Ana Bell — The instructor leading this introductory lecture.
  • Eric Grimson — The professor who will give some of the lectures later in the semester.
  • 6.0001 — One of the courses students are welcomed to at the start of the lecture, covering Python programming, problem solving, and algorithm comparison.
  • Python — The programming language used in the course to demonstrate the raffle, objects, arithmetic operations, and variable assignment.
  • Anaconda — The development environment for the course, introduced by the instructor during the classroom raffle demonstration.
  • Alan Turing — The instructor cites his work showing what can be computed using a paper tape and six basic operations.
  • 算法 — A method for solving a problem that consists of executable steps, control flow, and a stopping condition.
  • 存储程序计算机 — A computer that can store and execute replaceable sequences of instructions, allowing the same machine to perform different tasks.
  • 程序计数器 — A component of the control unit that determines which instruction is currently being executed. It can advance in order or jump based on a test result.
  • 名称绑定 — Assignment associates a variable name with the result of evaluating an expression. A later assignment can change that association.