19/7/2005 6.001 SICP 1/446.001: Structure and Interpretation of Computer Programs• Today– The structure of 6.001– The content of 6.001– Beginning to Scheme9/7/2005 6.001 SICP 15/44• Geometry was once equally misunderstood.•The term comes from ghia & metra or earth& measure•But in fact it’s about…• Computer Science deals with imperative or “how to” knowledgeWhat is the focus of 6.001?• This course is about Computer Science9/7/2005 6.001 SICP 16/44Declarative Knowledge• “What is true” knowledge0 and that such theis 2≥= yxyyx9/7/2005 6.001 SICP 17/44Imperative Knowledge• “How to” knowledge• To find an approximation of square root of x:– Make a guess G– Improve the guess by averaging G and x/G– Keep improving the guess until it is good enough.2for :Example =xxG = 1X = 29/7/2005 6.001 SICP 23/44“How to” knowledgeWhy “how to” knowledge?• Could just store tons of “what is” information • Much more useful to capture “how to” knowledge – a series of steps to be followed to deduce a particular value– a recipe– called a procedure• Actual evolution of steps inside machine for a particular version of the problem – called a process• Distinguish between procedure (recipe for square root in general) and process (computation of specific result)9/7/2005 6.001 SICP 24/44Describing “How to” knowledgeNeed a language for describing processes:• Vocabulary – basic primitives• Rules for writing compound expressions – syntax• Rules for assigning meaning to constructs – semantics• Rules for capturing process of evaluation – procedures29/7/2005 6.001 SICP 25/44Using procedures to control complexityGoals:• Create a set of primitive elements– simple data and procedures• Create a set of rules for combining elements of language• Create a set of rules for abstracting elements – treat complex things as primitivesWhy? -- Can create complex procedures while suppressing detailsTarget:• Create complex systems while maintaining: efficiency, robustness, extensibility and flexibility.9/7/2005 6.001 SICP 26/44Key Ideas in 6.001• Management of complexity:• Procedure and data abstraction• Conventional interfaces & programming paradigms• manifest typing• streams• object oriented programming• Metalinguistic abstraction:• creating new languages• evaluators9/7/2005 6.001 SICP 28/44Computation as a metaphor• Capture descriptions of computational processes• Use abstractly to design solutions to complex problems• Use a language to describe processes– Primitives– Means of combination– Means of abstraction9/7/2005 6.001 SICP 29/44Describing processes• Computational process:– Precise sequence of steps used to infer new information from a set of data• Computational procedure:– The “recipe” that describes that sequence of steps in general, independent of specific instance9/7/2005 6.001 SICP 34/44Representing basic information•Numbers– Primitive element – single binary variable• Takes on one of two values (0 or 1)• Represents one bit (binary digit) of information– Grouping together • Sequence of bits– Byte – 8 bits– Word – 16, 32 or 48 bits• Characters– Sequence of bits that encode a character• EBCDIC•ASCII9/7/2005 6.001 SICP 35/44Binary numbers and operations• Unsigned integersN-1 N-2 1 0Bit place i2^(n-1) 2^(n-2) 2^1 2^0Weight b∑−=•102niiibwhere is 0 or1ib110139/7/2005 6.001 SICP 36/44Binary numbers and operations• Addition0 0 1 1+0 +1 +0 +10 1 1 1010101 111 11100 9/7/2005 6.001 SICP 37/44Binary numbers and operations• Can extend to signed integers (reserve one bit to denote positive versus negative)• Can extend to character encodings• Representation is too low level!– Need abstractions!!9/7/2005 6.001 SICP 38/44Assuming a basic level of abstraction• We assume that our language provides us with a basic set of data elements– Numbers– Characters– Booleans• And with a basic set of operations on these primitive elements• Can then focus on using these basic elements to construct more complex processes9/7/2005 6.001 SICP 39/44Our language for 6.001• Scheme – Invented in 1975• Dialect of Lisp– Invented in 19599/7/2005 6.001 SICP 40/44Rules for describing processes in Scheme1. Legal expressions have rules for constructing from simpler pieces2. (Almost) every expression has a value, which is “returned” when an expression is “evaluated”.3. Every value has a type.SyntaxSemantics9/7/2005 6.001 SICP 41/44Kinds of Language Constructs• Primitives• Means of combination• Means of abstraction49/7/2005 6.001 SICP 42/44Language elements – primitives • Self-evaluating primitives – value of expression is just object itself– Numbers: 29, -35, 1.34, 1.2e5– Strings: “this is a string” “ this is another string with %&^ and 34”– Booleans: #t, #f9/7/2005 6.001 SICP 44/44Language elements – primitives • Built-in procedures to manipulate primitive objects– Numbers: +, -, *, /, >, <, >=, <=, =– Strings: string-length, string=?– Booleans: boolean/and, boolean/or, not9/7/2005 6.001 SICP 45/44Language elements – primitives • Names for built-in procedures– +, *, -, /, =, …– What is the value of such an expression?–+ Æ [#procedure …]– Evaluate by looking up value associated with name in a special table9/7/2005 6.001 SICP 46/44Language elements –combinations• How do we create expressions using these procedures?(+ 2 3)Open parenExpression whose value is a procedureOther expressionsClose paren• Evaluate by getting values of sub-expressions, then applying operator to values of arguments9/7/2005 6.001 SICP 47/44Language elements -combinations• Can use nested combinations – just apply rules recursively(+ (* 2 3) 4) Æ10(* (+ 3 4) (- 8 2)) Æ429/7/2005 6.001 SICP 48/44Language elements --abstractions• In order to abstract an expression, need way to give it a name(define score 23)59/7/2005 6.001 SICP 50/44Language elements --abstractions• To get the value of a name, just look up pairing in environmentscore Æ 23– Note that we already did this for +, *, …(define total (+ 12 13))(* 100 (/ score total)) Æ 92• This creates a loop in our system, can create a complex thing, name it, treat it as primitive9/7/2005 6.001 SICP
View Full Document