DOC PREVIEW
MIT 6 001 - Interpretation of Computer Programs

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

MIT 6 001 - Interpretation of Computer Programs

Documents in this Course
Quiz 1

Quiz 1

6 pages

Databases

Databases

12 pages

rec20

rec20

2 pages

Quiz II

Quiz II

15 pages

Streams

Streams

5 pages

Load more
Download Interpretation of Computer Programs
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Interpretation of Computer Programs and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Interpretation of Computer Programs 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?