1. Introduction to Computation - 6.001 SICP (2004)

Name: 1. Introduction to Computation - 6.001 SICP (2004)
Uploaded: 2017-03-19T23:07:03.000Z
Duration: 1 h 4 min 30 s

Introduction

The course is about computer science, but it's not really about computers. It's more about engineering or even art than science. Computer science deals with a different kind of knowledge known as imperative or how-to knowledge.

What is Declarative Knowledge?

Declarative knowledge talks about what is true and makes statements of fact that one can use to reason about things.

A statement of truth about square roots: the square root of x is that thing Y such that Y squared equals x and for safety y is also greater than or equal to zero.

What is Imperative Knowledge?

Imperative knowledge deals with how-to information and describes specific sequences of steps that characterize the evolution of a process by which one can deduce information from one set of facts to another.

An example algorithm for computing the square root of x using imperative knowledge.

Geometry as an Analogy

Geometry was originally used for surveying instruments, but in retrospect, we know it's much more than just dealing with those tools.

In its infancy, it was easy to confuse geometry with its tools. Similarly, computer science isn't really about computers; it's more about the kind of knowledge computer science makes available to us.

Conclusion

Computer Science deals with imperative or how-to knowledge rather than declarative or what-is knowledge.

Capturing How-To Knowledge

In this section, the speaker explains why capturing how-to knowledge is important and introduces the concept of a procedure.

Importance of Deductive Information

Capturing how-to knowledge is more interesting than collecting all possible solutions.

Procedures are used to give instructions to computers on how to compute a value.

Components of a Language for Describing Computational Processes

A process is the actual sequence of steps within the computer that caused the how-to knowledge to evolve.

The language for describing procedures must have a vocabulary, rules for legally connecting elements together, rules for deducing meaning associated with elements, and standard ways of combining expressions into a sequence of steps.

Our language for describing procedures will have many features similar to natural languages.

Creating Complex Processes

In this section, the speaker discusses creating tools that make it easy to capture procedures and describe processes.

Methodology for Thinking About Computation

The goal is to use the idea of a process and our way of describing that process with procedures.

We will create languages that describe processes by specifying primitive elements, simple data and simple procedures out of which we will capture more complex things.

Our real goal in understanding computation is to use our way of describing processes with procedures to control complexity in large intricate systems.

Blackbox Abstraction

This section discusses the concept of blackbox abstraction and how it can be used to control complexity in engineering.

Key Concepts

Blackbox abstraction is a valuable tool for isolating out the components of a system.

Building blackbox abstractions and finding ways to conventionally interface them or glue them together is going to be very valuable.

Conventional interfaces are needed for putting modules together, much like dealing with a stereo system.

The goal is to explore computation, especially how thinking about computation can serve as a tool for understanding and controlling complexity in large systems.

Metalinguistic Abstraction

This section discusses metalinguistic abstraction and its use in creating separate languages specifically designed for problem areas.

Key Concepts

When problems are too complex to handle in a convenient way, we need to generalize one more level and build our own language.

We will use the notion of metalinguistic abstraction to create separate languages specifically designed for problem areas.

To describe processes we need a language appropriate for capturing the essential elements of those things.

We will see several examples of different ways of building languages, including languages that deal specifically with interfaces to hardware evaluators.

Computational Processes

This section provides an overview of computational processes and their importance in information inference.

Key Concepts

A computational process is a precise sequence of steps by which information in the form of numbers symbols or other simple data elements is used to infer new information.

Our goal is to capture descriptions of computational processes and use them as an abstraction on which we can build solutions to other problems.

We need fundamental primitives or atomic elements of the language means of combination or ways of constructing more complex things from simpler ones and means of abstraction ways of treating complex things as primitives so that we can continue this product.

Our goal is to reason about the process of information inference using computation as a metaphor to understand complex problem-solving.

Representing Information

In this section, the speaker discusses how information is represented in computers. They start by discussing how numbers are represented using binary variables and then move on to discuss how characters and symbolic words can be represented using bit sequences.

Binary Representation of Numbers

Electronic signals are used to represent information inside a computer.

Binary variables take on either a value of 0 or 1, representing one bit or binary digit.

Bits are grouped together to represent other numbers, typically in groupings of eight bits called a byte or in groupings of 16, 32, or 48 bits called a word.

We can use math to capture the equation for representing unsigned integers.

Simple Arithmetic Operations on Binary Integers

Rules for addition are just what you'd expect and we can do standard addition by simply carrying as you would in decimal arithmetic.

Similar rules apply for multiplication and other arithmetic operations.

Signed integers can be created using one bit typically the highest order bit to represent the sign positive or negative.

Abstraction Level

A level of abstraction is needed when dealing with higher-level languages for computation.

The language provides a built-in set of data structures such as numbers, characters, and boolean values along with primitive operations for manipulating them.

Scheme Language

The language used in this course is called Scheme which is a variant of Lisp invented at MIT some time ago.

Everything written in Scheme will be composed of expressions that follow simple rules.

Introduction to Scheme

In this section, we learn about the syntax and semantics of expressions in Scheme. We also learn about the three components of expressions: primitives, means of combination, and means of abstraction.

Primitives

Primitives are the simplest elements on top of which all other computational constructs are built.

Self-evaluating expressions include numbers, strings, and booleans.

Built-in procedures allow us to manipulate primitive objects. For example, the symbol "+" is a name for the primitive procedure or operation of addition.

Means of Combination

Means of combination tell us how to combine smaller pieces to get bigger constructs.

The standard means of combination consists of an expression that applies a procedure to a set of arguments in order to create a new value.

Means of Abstraction

There were no bullet points with timestamps associated with them for this topic.

Evaluating Combinations

In this section, we learn about evaluating combinations in Scheme.

Syntax for Combination

The syntax for combination always consists of an open parenthesis followed by an expression whose value is a procedure followed by some number of other expressions whose values are obtained using these same rules followed by a matching closed parenthesis.

Semantics for Combination

There were no bullet points with timestamps associated with them for this topic.

Combinations

In this section, the speaker discusses how combinations can be nested arbitrarily and how we can use a combination whose parts are themselves combinations.

Nested Combinations

Combinations can be nested arbitrarily.

We can use a combination whose parts are themselves combinations.

Recursively apply these rules to evaluate combinations of arbitrary depth.

Rules for Evaluating Expressions

In this section, the speaker explains the rules for evaluating expressions in Scheme.

Applying Procedures to Arguments

First, get the values of the sub-expressions.

Then apply the procedure to the arguments and further reduce the expression.

Abstraction with Define

In this section, the speaker discusses how we can give an expression a name using define in Scheme.

Defining Expressions with Names

Use define to give an expression a name.

The expression will serve as a name typically some sequence of letters and other characters followed by an expression whose value will be associated with that name.

This creates a special form that does not follow normal rules of evaluation for a combination.

Associating Names with Values

Pair names together with deduced values in an environment (a big table).

We look up pairings of names and values in that table when we want to get back their value.

Using Names as Abstractions

In this section, the speaker explains how we can use names as abstractions once they have been associated with expressions using define in Scheme.

Creating Complex Expressions

Create complex expressions and give them names using define.

By using that name treat the whole expression as if it were primitive.

We can refer to that expression by name and write new complex expressions evolving those names giving the resulting expression another name.

Evaluation Rules and Mechanisms

In this section, we learn about the evaluation rules and mechanisms in Scheme programming language. We explore two different worlds of evaluation: visible world and execution world. We also discuss how expressions are processed by a reader and evaluator to compute values.

Two Different Worlds of Evaluation

There are two different ways of looking at what happens during evaluation: visible world and execution world.

The visible world is what we see when we type an expression at the computer, leading to some printed result.

The execution world is what happens within the computer, including how objects are represented and how the actual mechanism evaluation takes place.

Processing Expressions

Our goal is to capture computation in expressions and then use those expressions to compute values.

When an expression is entered into the computer from our visible world, it is first processed by a mechanism called a reader which converts this expression into an internal form appropriate for the computer that form is then passed to a process called an evaluator.

This evaluator encapsulates our rules for evaluation and reduces the expression to its value using exactly the rules we've been talking about.

Primitive Objects

Self-evaluating expressions have values that are just themselves. For example, 23 self-evaluates as 23.

A name for something typically created by evaluating a defined expression. When we ask the computer to evaluate an expression such as pi, it recognizes it as a name and returns its associated value from the environment.

Special Forms

Special forms like define have different rules. We first apply our evaluation rules to the second sub-expression of the define. Once we've determined that value, we then take the first sub-expression without evaluation and create a pairing of that name and the computed value in a structure called an environment.

Since the goal of the define expression is to create this pairing, we don't really care about the value of the define expression itself. It's just used for the side-effect of creating despairing and thus typically we leave the value returned by define expression as unspecified.

Scheme Programming Language

In this section, the speaker explains how values are returned in different implementations of Scheme and how to apply rules for simple computations or combinations involving built-in arithmetic procedures. The speaker also demonstrates how to define a new name and bind it with an existing value.

Rules for Simple Computations

For simple computations or combinations involving built-in arithmetic procedures, use the self-evaluation rule to get the values of sub-expressions and then apply the value associated with the symbol.

When evaluating a combination, get the values of sub-expressions using the name rule. If a name is defined, pair it with its corresponding value in the environment.

To evaluate a defined expression that pairs a new name with an existing value, use the name rule to find its value and create a binding between them.

Primitive Data and Procedures

Built-in names like addition or multiplication have internal representations as primitive procedures. When their names are evaluated, their values are looked up in the environment and returned as expressions.

The main issue is to see that symbols have values associated with them. Primitive procedures can be used as expressions by calling them directly.

Capturing Common Patterns

In this section, we will turn to capturing common patterns in procedures.