《Structure and Interpretation of Computer Programs》lecture 1 webhand.pdf_大学文库

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 1.1.4 In fact, geometry is a good analogy to use here. It has also a What is the focus of 6. 001? terrible name which comes from two words ghia or earth and metra or measurement. And to the ancient Egyptians, · This course is about the earth, or surveying. Thousands of years ago, the Ni suring that is exactly what geometry was--instruments for mea An analogy is to Geometry his comes from Ghia Metra annually flooded, and eventually retreated, wiping out most of Earth& Measure the identifying landmarks. It also deposited rich soil in its wake, making the land that it flooded very valuable, but also very hard to keep track of. As a consequence, the egyptian priesthood had to arbitrate the restoration of land boundaries after the annual 2203 6 001 SICP I flooding. Since there were no landmarks, they needed a better way of determining boundaries, and they invented geometry, or earth measuring. Hence, to the Egyptians, geometry was surveying--and about survey ing instruments. This is a common effect. When a field is just getting started, it's easy to confuse the essence of the field with its tools, because we usually understand the tools much less well in the infancy of an area. In hindsight, we realize that the important essence of what the egyptians did was to formalize the notions of space and time which later led to axiomatic methods for dealing with declarative, or What Is kinds of knowledge ---So geometry not really about measuring devices, but rather about declarative knowledge Slide 1.1.5 So geometry is not really about surveying, it is actually What is the focus of 6.001? of knowledge known as declarative, or"what is uue ar kind fundamentally about axioms for dealing with a particul · This course is about knowledge An analogy is to Geometry This comes fr metra measure Geometry deals with Declarative or"What is"knowledge. 600SC Slide 1.1.6 What is the focus of 6.001? By analogy to geometry, Computer Science is not really about computers--it is not about the tool. It is actually about the kind This course is about Computer of knowledge that computer science makes available to us What we are going to see in this course is that computer science is dealing with a different kind of knowledge- Imperative or This comes from Ghia metra or Earth measure how toknowledge. It is trying to capture the notion of a corsetry deals with Declarative or "What is"knowledg process that causes information to evolve from one state to Computer Science deals with Imperative or How to" knowledge another, and we want to see how we can uses methods to capture that knowledge

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 1.1.4 In fact, geometry is a good analogy to use here. It has also a terrible name, which comes from two words: GHIA or earth, and METRA or measurement. And to the ancient Egyptians, that is exactly what geometry was -- instruments for measuring the earth, or surveying. Thousands of years ago, the Nile annually flooded, and eventually retreated, wiping out most of the identifying landmarks. It also deposited rich soil in its wake, making the land that it flooded very valuable, but also very hard to keep track of. As a consequence, the Egyptian priesthood had to arbitrate the restoration of land boundaries after the annual flooding. Since there were no landmarks, they needed a better way of determining boundaries, and they invented geometry, or earth measuring. Hence, to the Egyptians, geometry was surveying -- and about surveying instruments. This is a common effect. When a field is just getting started, it’s easy to confuse the essence of the field with its tools, because we usually understand the tools much less well in the infancy of an area. In hindsight, we realize that the important essence of what the Egyptians did was to formalize the notions of space and time which later led to axiomatic methods for dealing with declarative, or What Is kinds of knowledge. --- So geometry not really about measuring devices, but rather about declarative knowledge. Slide 1.1.5 So geometry is not really about surveying, it is actually fundamentally about axioms for dealing with a particular kind of knowledge, known as Declarative, or "what is true" knowledge. Slide 1.1.6 By analogy to geometry, Computer Science is not really about computers -- it is not about the tool. It is actually about the kind of knowledge that computer science makes available to us. What we are going to see in this course is that computer science is dealing with a different kind of knowledge -- Imperative or "how to" knowledge. It is trying to capture the notion of a process that causes information to evolve from one state to another, and we want to see how we can uses methods to capture that knowledge

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 1. 1. 15 So what we have seen is that imperative and declarative knowledge are very different. One captures statements of fact; How to” knowledge the other captures methods for deducing information. It is easy to see why the latter is more interesting. For example, one could Why"how to"knowledge? in principle imagine try ing to collect a giant listing of all Could just store information when you need it. Much more convenient is to capture the or possible square roots, and then simply looking up a square Much more useful to capture"how to" knowledge-a eries of steps to be followed to deduce a particular process of deducing a specific square root as needed. Thus, we call this a proeedure are primarily interested in "how to" knowledge - we want to be able to give the computer instructions to compute a value, and this means we need a way of capturing the"how to"knowledge 729003 6001 sICP In particular, we want to describe a series of specific mechanical steps to be followed in order to deduce a particular value associated with some problem, using a predefined set of operations. This"recipe"for describing"how to" knowledge we call a procedure Slide 1.1.16 How to” knowledge When we want to get the computer to actually compute a value. that is, use the how to"knowledge to find the value associated Why“ how to" knowledg with a particular instantiation of the problem, we will evaluate Could just store information an expression that applies that procedure to some values. The how to” knowledge-a actual sequence of steps within the computer that cause the series of steps to be followed to deduce a particular value how to" knowledge to evolve is called a process. Much of our call this a proeedure focus during the term will be in understanding how to Actual evolution of steps inside machine for a particular different kinds of processes by describing them withcontrol procedures 6001 SICP Slide 1.1.1z Now we want to create tools that make it easy for us to capture procedures and describe processes, and for that we will need Describing" How to"knowledg language. Whatever language we choose to use to describe Need a language for describing processes computational processes, it must have several components Vocabulary First, it will have a vocabulary -a set of words on which we Rules for writing compound expressions-syntax build our description. These will be the basic elements of Rules for assigning meaning to constructs-semantics computation, the fundamental representations of information Rules for capturing process of evaluation- procedures and the fundamental procedures that we use to describe all other procedures Second, it will have a set of rules for legally connecting elements together -that is, how to build more complex parts of L soames a procedure out of more basic ones. This will be very similar to the syntax of a natural language Third, it will have a set of rules for deducing the meaning associated with elements of the description. This will be very similar to the semantics of a natural language And finally, we will need standard ways of combining expressions in our language together into a sequence of steps that actually describe the process of computation We will see is that our language for describing procedures will have many of the same features as natural uages, and that we will build methods for constructing more complex procedures out simpler pieces in natural

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 1.1.15 So what we have seen is that imperative and declarative knowledge are very different. One captures statements of fact; the other captures methods for deducing information. It is easy to see why the latter is more interesting. For example, one could in principle imagine trying to collect a giant listing of all possible square roots, and then simply looking up a square root when you need it. Much more convenient is to capture the process of deducing a specific square root as needed. Thus, we are primarily interested in "how to" knowledge -- we want to be able to give the computer instructions to compute a value, and this means we need a way of capturing the "how to" knowledge. In particular, we want to describe a series of specific, mechanical steps to be followed in order to deduce a particular value associated with some problem, using a predefined set of operations. This "recipe" for describing "how to" knowledge we call a procedure. Slide 1.1.16 When we want to get the computer to actually compute a value, that is, use the "how to" knowledge to find the value associated with a particular instantiation of the problem, we will evaluate an expression that applies that procedure to some values. The actual sequence of steps within the computer that cause the "how to" knowledge to evolve is called a process. Much of our focus during the term will be in understanding how to control different kinds of processes by describing them with procedures. Slide 1.1.17 Now we want to create tools that make it easy for us to capture procedures and describe processes, and for that we will need a language. Whatever language we choose to use to describe computational processes, it must have several components. First, it will have a vocabulary -- a set of words on which we build our description. These will be the basic elements of computation, the fundamental representations of information and the fundamental procedures that we use to describe all other procedures. Second, it will have a set of rules for legally connecting elements together -- that is, how to build more complex parts of a procedure out of more basic ones. This will be very similar to the syntax of a natural language. Third, it will have a set of rules for deducing the meaning associated with elements of the description. This will be very similar to the semantics of a natural language. And finally, we will need standard ways of combining expressions in our language together into a sequence of steps that actually describe the process of computation. We will see is that our language for describing procedures will have many of the same features as natural languages, and that we will build methods for constructing more complex procedures out simpler pieces in natural ways

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide ll18 bing How to” knowledge One of the things we will see is that it does not take long to describe the rules for connecting elements together, nor to Need a language for describing processes describe the rules for determining meanings associated with Vocabulary expressions in our language of procedures Rules for writing compound expressions-syntax Our real goal is to use this language of procedures and g meaning to constructs- semantics processes to help us control complexity in large systems-that Rules for capturing process of evaluation-procedures is, to use the language and its elements to design particular procedures aimed at solving a specific problem. We will spend much of the term doing this, both from scratch, and by looking 903 6 001 SICP at examples from existing procedures Slide 1.1.19 In order to capture imperative knowledge, we are going to Using procedures to control reate languages that describe such processes. This means we complexity will need to specify a set of primitive elements --simple data and simple procedures, out of which we will capture complex Create a set of primitive clements in language-simple data and simple procedures procedures. We will also need a set of rules for combining Create a set of rules for combining elements of langunge primitive things into more complex structures. And once we have those complex structures, we will want to be able to abstract them --give them name so that we can treat them as primitives 6001 SIC? Slide 1.1.20 Using procedures to control We will see, as we go through the term, that this cycle of complexity creating complex processes, then suppressing the details by Goals abstracting them into black box units, is a powerful tool for reate a set of primitive elements in Language -simple dat and simple procedures designing, maintaining and extending computational systems Create a set of rules for combining elements of langunge Create a set of rules for abstracting clements-treat complex things as primitives Allows us to eate complex procedures while 1001 SICP

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 1.1.2 Indeed, that is precisely the goal of understanding computation How can we create methodologies that make it easy to describe USing procedures to control complex processes without getting lost in the details? Clearly a complexity well-designed methodology for thinking about computation Create a set of primitive elements in language-sumple data and simple procedures should enable us to build systems that robustly and efficiently Create a set of rules for combining elements of language compute results without error, but also should enable us to Create a set of rules for abstracting elements- treat complex things as primitives easily add new capabilities to the system. Thus, our goal is to gain experience in thinking about computation, independent of Allows us to rente complex procedures while suppressing details language details and specifics, in order to control complexity in Target arge, intricate systems Create complex systems while maintaining: robustness, efficiency, extensibility and flexibility 6001 sICP Key Ideas in 6.001 hus our goal in 6.001 is to use the ideas of how to' knowledge, the ideas of describing processes throug Management of complexity procedures, to control complexity of large systems. We don't just want to write small programs, we want to understand how the ideas of procedures and their pieces can be used to construct large systems in well-engineered ways his means we need tools for handling complex systems, and we are going to see a range of such tools, built on the language of procedures 601 SICP Slide 1.1.23 The first tool we will use for controlling complexity is the idea Key Ideas in 6.001 of an abstraction, a black box, if you like. Take the method we just described for computing square roots. While it is useful to know how to do this, one can easily imaging problems in which Procedure and data abstraction one simply wants the square root, and one doesn't care how it is derived. Imagine creating a black box that captures the idea of square root--one simply puts values in the correct slot, and out come appropriate square roots. This idea of isolating the use of a procedure from its actual implementation or mechanism is a central idea that we will use frequently in controlling 6m: SICP complexity of large systems

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 1.1.27 And as a consequence we will see several different mechanisms for creating new languages--ones designed for particular Key Ideas in 6.001 problems, one designed to interface between higher level anguages and the hardware that actually does the work, and ones that get to the heart of any computer language, by focusing on the essence of computation--evaluation of expressions Conventional interfaces programming paradigms Metalinguistic abstraction 6.001 Notes: Section 1.2 Slide 1.2.1 rse is to explore computation, especially how thinking about computation can serve as a tool for Computation as a metaphor understanding and controlling complexity in large systems Of Capture descriptions of computational processes particular interest are systems in which information is inferred Use abstractly to design solutions to complex from some set of initial data. whether that is finding other information on the web, or computing an answer to a scientific Using a language to describe processes Primitives problem, or deciding what control signals to use to guide a mechanical system Means of combination Means of abstraction For such systems to work, they need some process by which such inference takes place, and our goal is to be able to reason about that process. In using computation as a metaphor to understand complex problem solving, we really want to do two things. We want to capture descriptions of computational processes. And we want to use the notion of a computational process as an abstraction on which we can build solutions to other complex problems We will see that to describe processes, we need a language appropriate for capturing the essential elements of processes. This means we will need fundamental primitives(or atomic elements of the language), means of combination(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 process)

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 1.2.2 So let's begin our discussion of a language for describing Describing pr ocesses computational proc To do this, we really need to provide a definition of or at least some intuition behind the idea of a computational process. In simple terms, a computational Precise sequence of steps used to infer new information from a set of data process is a precise sequence of steps by which information (in Computational procedure the form of numbers, symbols, or other simple data elements )is The"recipe "that describes that sequence of used to infer new information This could be a numerical computation(e.g. a set of steps to compute a square root, as we saw earlier), or it could be a symbolic computation(finding a piece of information on the Web), or some other inference 2m03 6 001 SICP I based on information. While the computational process refers to the actual evolution f information in the computation, we also want to be able to capture a description of the actual steps in th computation, and we refer to this recipe as a computational procedure: a description of the steps in the computation. Thus, our language will allow us to describe"recipes "and to use these descriptions on particular instances of problems, that is, will"bake solutions using the recipes Slide 1.2.3 First, we need to understand how we are going to representation information. which we will use as the basis for our Representing basic information computational processes. To do this, we need to decide on Atomic element- single binary variable epresentations for numeric values and for symbolic ones Let's start with numbers sents one bit(binary digit)of information To represent a number, we start with the most atomic element Because ultimately we will represent information internally inside the computer, we will use electronic signals to do so Characters These are most conveniently represented by using a high uence or bis that encode a character voltage or current or a low voltage or current to represent 6 001 SICP fundamental values. Thus, the most primitive element in representing a value is a binary variable, which takes on one of two values: a zero or a one. This variable represents one bit, or binary digit, or information Of course, we need to group these bits together to represent other numbers, which we do typically in groupings of 8 its(a byte or in groupings of 16, 32, or 48 bits(a word Once we have sequences of bits, we can use them not only to represent other numbers, but we can envision encodings, in which numbers or bit sequences are used to represent characters. And characters can further be group together to represent symbolic words. Though we wont worry about it much in this course, there are standard encoding schemes for using bit sequences to represent characters as well as numbers. Typically the first few bits in a sequence are used as a tag to distinguish a number from an encoding for a charact

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 1.2.2 So let's begin our discussion of a language for describing computational processes. To do this, we really need to provide a definition of, or at least some intuition behind, the idea of a computational process. In simple terms, 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. This could be a numerical computation (e.g. a set of steps to compute a square root, as we saw earlier), or it could be a symbolic computation (finding a piece of information on the Web), or some other inference based on information. While the computational process refers to the actual evolution of information in the computation, we also want to be able to capture a description of the actual steps in the computation, and we refer to this recipe as a computational procedure: a description of the steps in the computation. Thus, our language will allow us to describe “recipes” and to use these descriptions on particular instances of problems, that is, will “bake solutions” using the recipes. Slide 1.2.3 First, we need to understand how we are going to representation information, which we will use as the basis for our computational processes. To do this, we need to decide on representations for numeric values and for symbolic ones. Let’s start with numbers. To represent a number, we start with the most atomic element. Because ultimately we will represent information internally inside the computer, we will use electronic signals to do so. These are most conveniently represented by using a high voltage or current or a low voltage or current to represent fundamental values. Thus, the most primitive element in representing a value is a binary variable, which takes on one of two values: a zero or a one. This variable represents one bit, or binary digit, or information. Of course, we need to group these bits together to represent other numbers, which we do typically in groupings of 8 bits (a byte) or in groupings of 16, 32, or 48 bits (a word). Once we have sequences of bits, we can use them not only to represent other numbers, but we can envision encodings, in which numbers or bit sequences are used to represent characters. And characters can further be group together to represent symbolic words. Though we won’t worry about it much in this course, there are standard encoding schemes for using bit sequences to represent characters as well as numbers. Typically the first few bits in a sequence are used as a tag to distinguish a number from an encoding for a character