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
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 © 2004 by Massachusetts Institute of Technology. Slide 1.1.18 One of the things we will see is that it does not take long to describe the rules for connecting elements together, nor to describe the rules for determining meanings associated with expressions in our language of procedures. Our real goal is to use this language of procedures and processes to help us control complexity in large systems -- that 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 at examples from existing procedures. Slide 1.1.19 In order to capture imperative knowledge, we are going to create languages that describe such processes. This means we will need to specify a set of primitive elements -- simple data and simple procedures, out of which we will capture complex procedures. We will also need a set of rules for combining 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. Slide 1.1.20 We will see, as we go through the term, that this cycle of creating complex processes, then suppressing the details by abstracting them into black box units, is a powerful tool for designing, maintaining and extending computational systems
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 © 2004 by Massachusetts Institute of Technology. Slide 1.1.21 Indeed, that is precisely the goal of understanding computation. How can we create methodologies that make it easy to describe complex processes without getting lost in the details? Clearly a well-designed methodology for thinking about computation should enable us to build systems that robustly and efficiently compute results without error, but also should enable us to easily add new capabilities to the system. Thus, our goal is to gain experience in thinking about computation, independent of language details and specifics, in order to control complexity in large, intricate systems. Slide 1.1.22 Thus our goal in 6.001 is to use the ideas of "how to" knowledge, the ideas of describing processes through 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. This 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. Slide 1.1.23 The first tool we will use for controlling complexity is the idea 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 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 complexity of large systems
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 1.1.24 Key Ideas in 6.001 Not only are black boxes a useful tool for isolating components of a system, they also provide the basis for connecting things together. a key issue is providing methods for connecting together basic units into components that themselves can be Conventional interfaces programming paradigms treated as basic units. Thus, we will spend a lot of time talking about conventional interfaces -- standard ways of Interconnecting simpler pieces This is much like hooking up parts of a stereo system. One has standard interfaces by which components can be intertwined and this can be done without worrying about the internal 6 001 SICP ae?aspects of the components. Similarly in programming, we will describe conventions for interfacing simpler components to create new elements that can further be connected together Slide l1.25 n fact, here are three particular kinds of conventional interfaces Key Ideas in 6.001 that we will explore in some detail during the term Management of complexity Procedure and data abstract Conventional interfaces prograrmming paradigm Slide 1.1.26 Key Ideas in 6.001 We will see as we go through the term that ideas of capturing procedures in black box abstractions, then gluing them together through conventional interfaces will give us considerable power Procedure and data abstraction in creating computational machinery. At some point, however, Conventional interfaces programming paradigms even these tools will not be sufficient for some problems. At manifest typing will generalize these ideas to languages specifically oriented at some problem domain. This Metalinguistic abstraction idea of meta-linguistic abstraction will provide us with a powerful tool for designing procedures to capture processes especially as we focus on the idea of what it means to evaluate
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 1.1.24 Not only are black boxes a useful tool for isolating components of a system, they also provide the basis for connecting things together. A key issue is providing methods for connecting together basic units into components that themselves can be treated as basic units. Thus, we will spend a lot of time talking about conventional interfaces -- standard ways of interconnecting simpler pieces. This is much like hooking up parts of a stereo system. One has standard interfaces by which components can be intertwined, and this can be done without worrying about the internal aspects of the components. Similarly in programming, we will describe conventions for interfacing simpler components to create new elements that can further be connected together. Slide 1.1.25 In fact, here are three particular kinds of conventional interfaces that we will explore in some detail during the term. Slide 1.1.26 We will see as we go through the term that ideas of capturing procedures in black box abstractions, then gluing them together through conventional interfaces will give us considerable power in creating computational machinery. At some point, however, even these tools will not be sufficient for some problems. At this stage, we will generalize these ideas, to create our own languages specifically oriented at some problem domain. This idea of meta-linguistic abstraction will provide us with a powerful tool for designing procedures to capture processes, especially as we focus on the idea of what it means to evaluate an expression in a specifically designed language
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 © 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 problems, one designed to interface between higher level languages 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. 6.001 Notes: Section 1.2 Slide 1.2.1 Our goal in this course is to explore computation, especially how thinking about computation can serve as a tool for understanding and controlling complexity in large systems. Of particular interest are systems in which information is inferred from some set of initial data, whether that is finding other information on the web, or computing an answer to a scientific problem, or deciding what control signals to use to guide a mechanical system. 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
