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:

116.001 SICPComputability• What we've seen...• Deep question #1: • Does every expression stand for a value?• Deep question #2: • Are there things we can't compute?• Deep question #3:• What is EVAL really?2(1) Abstraction• Elements of a Language• Procedural Abstraction:• Lambda – captures common patterns and"how to" knowledge• Functional programming & substitution model• Conventional interfaces:• list-oriented programming• higher order procedures3(2) Data, State and Objects• Data Abstraction• Primitive, Compound, & Symbolic Data• Contracts, Abstract Data Types• Selectors, constructors, operators, ...• Mutation: need for environment model• Managing complexity• modularity• data directed programming• object oriented programming4(3) Language Design and Implementation• Evaluation – meta-circular evaluator• eval & apply• Language extensions & design• lazy evaluation; streams• dynamic scoping• Register machines•ec-eval6Deep Question #1Does every expression stand for a value?7Some Simple Procedures• Consider the following procedures(define (return-seven) 7)(define (loop-forever) (loop-forever))•So(return-seven)⇒ 7(loop-forever)⇒ [never returns!]• Expression (loop-forever) does not stand for a value; not well defined.28Deep Question #2Are there well-defined things thatcannot be computed?9Countable and uncountable• Two sets of numbers (or other objects) are said to have the same cardinality (or size) if there is a one-to-one mapping between them. This means each element in the first set matches to exactly one element in the second set, and vice versa.• Any set of same cardinality as the integers is called countable.• {integers} maps to {even integers}: n Æ 2n• {integers} maps to {squares}: nÆn2• {integers} maps to {rational fractions between 0 and 1}10Countable and uncountable• Proof of last claim• Mapping from this set to integers – count from 1 as move along line• Mapping from integers to this set – first row clearly contains integers1 2 3 4 5 6 7 ….1 1/1 2/1 3/1 4/1 5/1 6/1 7/1 …2 ½ 2/2 3/2 4/2 5/2 6/2 7/2 …3 1/3 2/3 3/3 4/3 5/3 6/3 7/3 …4 ¼ 2/4 ¾ 4/4 5/4 6/4 7/4 …5 1/5 2/5 3/5 4/5 5/5 6/5 7/511Countable and uncountable• The set of numbers between 0 and 1 is uncountable, I.e. there are more of them than there are integers:• Represent any such number by binary fraction, e.g. 0.01011 Æ ¼ + 1/16 + 1/32• Assume there are a countable number of such numbers. Then can arbitrarily number them, as in this table:½ ¼ 1/8 1/16 1/32 1/64 ….1 0 1 0 1 1 0 ….2 1 1 0 1 0 1 ….3 0 0 1 0 1 0 ….• Pick a new number by complementing the diagonal, e.g.100…This number cannot be in the list!! So the assumption of countability is false, and there are more irrationals than rationals12There are more functions than programs• There are clearly a countable number of procedures, since each is of finite length, and based on a finite alphabet.• Assume there are a countable number of predicate functions, i.e. mappings from an integer argument to the values 0 or 1. Then we can arbitrarily number them.1 2 3 4 5 6 ….P1 0 1 0 1 1 0 ….P2 1 1 0 1 0 1 ….P3 0 0 1 0 1 0 ….• Play the same Cantor Diagonalization game. Define a new predicate function by complementing the diagonals. By construction this predicate cannot be in the list, yet we claimed we could list all of them. Thus there are more predicate functions than there are procedures.13halts?• Even our simple procedures can cause trouble. Suppose we wanted to check procedures before running them to catch accidental infinite loops.• Assume a procedure halts? exists:(halts? p)⇒ #t if (p) terminates ⇒ #f if (p) does not terminate• halts? is well specified – has a clear value for its inputs(halts? return-seven) Î #t(halts? loop-forever) Î #fHalperin, Kaiser, and Knight, "Concrete Abstractions," p. 114, ITP 1999.314The Halting Theorem:Procedure halts? cannot exist. Too bad!• Proof (informal): Assume halts? exists as specified.(define (contradict-halts)(if (halts? contradict-halts)(loop-forever)#t))(contradict-halts) ⇒ ??????•Wow! • If contradict-halts halts, then it loops forever.• If contradict-halts doesn’t halt, then it halts.• Contradiction! Assumption that halts? exists must be wrong. 15Deep Question #3What is EVAL really?16The dream of a universal machine…18The dream of a universal machineACME Universal machineIf you can say it, I can do it™A clock keeps time…A clock keeps time…19What is Eval really?•We do describe devices, in a language called Scheme• We have a machine that takes those descriptions and then behaves exactly as they specify• Eval takes any program as input and reconfigures itself to simulate that input program• EVAL is a universal machine20Seen another way• Suppose you were a circuit designer• Given a circuit diagram, you could transform it into an electric signal encoding the layout of the diagram• Now suppose you wanted to build a circuit that could take any such signal as input (any other circuit) and could then reconfigure itself to simulate that input circuit• What would this general circuit look like???• Suppose instead you describe a circuit as a program• Can you build a program that takes any program as input and reconfigures itself to simulate that input program?• Sure – that’s just EVAL!! – it’s a UNIVERSAL MACHINE421It wasn’t always this obvious• “If it should turn out that the basic logics of a machine designed for the numerical solution of differential equations coincide with the logics of a machine intended to make bills for a department store, I would regard this as the most amazing coincidence that I have ever encountered”Howard Aiken, writing in 1956 (designer of the Mark I “Electronic Brain”, developed jointly by IBM and Harvard starting in 193922Why a Universal Machine?• If EVAL can simulate any machine, and if EVAL is itself a description of a machine, then EVAL can simulate itself• This was our example of meval• In fact, EVAL can simulate an evaluator for any other language• Just need to specify syntax, rules of evaluation• An evaluator for any language can simulate any other language• Hence there is a general notion of computability –


View Full Document

MIT 6 001 - Lecture Notes

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 Lecture Notes
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 Lecture Notes 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 Lecture Notes 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?