6.001 SICP Computability(1) Abstraction(2) Data, State and Objects(3) Language Design and ImplementationTime for some prizes!Deep Question #1Some Simple ProceduresDeep Question #2Countable and uncountableSlide 10Slide 11There are more functions than programshalts?The Halting Theorem: Procedure halts? cannot exist. Too bad!Deep Question #3The dream of a universal machine…The dream of a universal machineWhat is Eval really?Seen another wayIt wasn’t always this obviousWhy a Universal Machine?Turing’s insightSlide 24Slide 25The halting problemThe Halting theoremTuring’s historySlide 29Slide 30Slide 31Slide 32From Whence Recursion?Infinite Recursion without DefineSlide 35Harnessing recursionHarness this anonymous recursion?How do we stop the recursion?CompareParameterize (capture f)The Y CombinatorHow to Design F to Work with Y?Implication of 2: F Can End the RecursionExample: An F That Terminates a RecursionImplication of 1: F Should have Proc as ArgSlide 46Slide 47So What is proc?Putting it all togetherY Combinator: The Essence of RecursionThe Limits of Lambda and YSlide 5216.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-eval5Time for some prizes!6Deep 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.8Deep 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}: nn2•{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 integers 1 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.14The 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…17The dream of a universal machineACME Universal machineIf you can say it, I can do it™A clock keeps time…A clock keeps time…A tide clock keeps track of tides…A tide clock keeps track of tides…A bright red Ferrari F-430…A bright red Ferrari F-430…EVAL19What 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
View Full Document
Unlocking...