6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 1.1 Slide l.l.1 This first thing we need to do is discuss the focus of 6.001 What is this course all about? This seems quite obvious-- this What is the focus of 6.001 is a course about computer science. But we are going to claim This course is about Computer Science in a rather strange way that this is not really true 60015e Slide 1.1.2 What is the focus of 6.001? First of all, it is not really about science. It is really much more about engineering or art than it is about science This course is about Computer Slide 1.1.3 and it is not really about computers. Now that definitely ounds strange! But let me tell you why I claim it is not really What is the focus of 6.001? about computers. I claim it is not really about computers in the This course is about (Co same way that physics is not really just about particle accelerators, or biology is not really just about microscopes, or geometry is not really about surveying instruments
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 1.1 Slide 1.1.1 This first thing we need to do is discuss the focus of 6.001. What is this course all about? This seems quite obvious -- this is a course about computer science. But we are going to claim in a rather strange way that this is not really true. Slide 1.1.2 First of all, it is not really about science. It is really much more about engineering or art than it is about science. Slide 1.1.3 ...and it is not really about computers. Now that definitely sounds strange! But let me tell you why I claim it is not really about computers. I claim it is not really about computers in the same way that physics is not really just about particle accelerators, or biology is not really just about microscopes, or geometry is not really about surveying instruments
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 ll.7 First. what is declarative knowledge? It is knowledge that talks about what is true It makes statements of fact that one can use Declarative Knowledge to try to reason about things. For example, here is a statement of truth about square roots. It provides a definition of a square ·“ What is true” knowledge root. As a consequence if someone were to hand you a possible value for the square root of some x, you could check it by using x is the y such that y"=x and y 20 this definition. But it doesn,'t tell you anything about how to find the value of square root of x 729003 6001 sICP lide l.l. 8 Imperative Knowledge On the other hand, imperative knowledge talks about"how to ·“ How to” knowledge knowledge. It tends to describe a specific sequence of steps that characterize the evolution of a process by which one can deduce information, transforming one set of facts into a new 601 SICP Slide 1.1.9 So here for example is a very old algorithm, that is, a specific piece of imperative knowledge, for find an approximation to the Imperative Knowledge square root of some number, x “ How to” knowledge To find an approximation of square root of x Improve the guess by averaging G and x/G Keep improving the guess until it is good enough 6m: SICP Slide 1.1.10 Imperative Knowledge Okay --let's test it out. Suppose we want to find the square root “ How to" knowledge of 2. We will see how this sequence of steps describes a process for finding the square root of 2 Make a guess G Improve the guess by averaging and x/G Keep improving the guess until it is good enough
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 1.1.7 First, what is declarative knowledge? It is knowledge that talks about what is true. It makes statements of fact that one can use to try to reason about things. For example, here is a statement of truth about square roots. It provides a definition of a square root. As a consequence if someone were to hand you a possible value for the square root of some x, you could check it by using this definition. But it doesn't tell you anything about how to find the value of square root of x. Slide 1.1.8 On the other hand, imperative knowledge talks about "how to" knowledge. It tends to describe a specific sequence of steps that characterize the evolution of a process by which one can deduce information, transforming one set of facts into a new set. Slide 1.1.9 So here for example is a very old algorithm, that is, a specific piece of imperative knowledge, for find an approximation to the square root of some number, x. Slide 1.1.10 Okay -- let's test it out. Suppose we want to find the square root of 2. We will see how this sequence of steps describes a process for finding the square root of 2
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide l1.ll So here we go. We'll create a little chart to keep track of the algorithm. We want to find the square root of 2, sox=2. And Imperative Knowledge we start with some guess, say G=1. Our algorithm tells us how."How to"knowledge to improve this guess, by averaging g and x divided by g To find an approximation of square root of x G and xG Keep improving the it is good enough 729003 6001 sICP Slide 1.1.12 Imperative Knowledge So we compute X/G. And then the algorithm says to get a new How to” knowled guess, G, by averaging the old guess and this ratio--giving us a better guess for the square root of 2 Make a guess G Improve the guess by averaging G and x/G Keep improving the guess until it is good enoug Example G=1 G=(1+2)=1 601 SICP Slide ll13 If we decide we are not close enough(i.e. square our current value. Then we get a new guess, by averaging our current guess. Make a gues M E guess is too far away from 2) we can continue. We take our Imperative Knowledge current value for the guess, and compute x divided by that “ How to”knov ledge of square root of x and this new ratio. and we continue mprove the guess by averaging G and X/G Keep improving the guess until it is good enough √xfor G=(1+2)=L5 XG=4/3 1 (32+43)=17/12=1.41666 4729.003 Slide 1.1.14 Imperative Knowledge Eventually we get a value for the guess that is close enough, “ How to" knowledge and we stop. Notice how this"algorithm"describes a sequence roximation of square root of x: of steps to follow to deduce some new information from a set of Improve the guess by averaging G and x/G facts. It tells us"how to"do something Compare this with the case of the declarative or what is Example:√xfor version. It simply told us how to recognize a square root if we saw one. but nothing about how to find one XG=2G=4(1+2)=1.5 XG=2417G=(1712+2417=577408= 1,4142156
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 1.1.11 So here we go. We'll create a little chart to keep track of the algorithm. We want to find the square root of 2, so x = 2. And we start with some guess, say G = 1. Our algorithm tells us how to improve this guess, by averaging g and x divided by g. Slide 1.1.12 So we compute x/G. And then the algorithm says to get a new guess, G, by averaging the old guess and this ratio -- giving us a better guess for the square root of 2. Slide 1.1.13 If we decide we are not close enough (i.e. square our current guess is too far away from 2) we can continue. We take our current value for the guess, and compute x divided by that value. Then we get a new guess, by averaging our current guess and this new ratio. And we continue. Slide 1.1.14 Eventually we get a value for the guess that is close enough, and we stop. Notice how this "algorithm" describes a sequence of steps to follow to deduce some new information from a set of facts. It tells us "how to" do something. Compare this with the case of the declarative or "what is" version. It simply told us how to recognize a square root if we saw one, but nothing about how to find one
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