Slide 1MenuLazy Evaluation RecapLazy ApplicationLazy Data StructuresUsing Lazy PairsInfinite ListsInfinite Fibonacci SequenceAlternate ImplementationQuiz ResultsQuiz AnswersQuiz 4: Environment ClassQuiz 5: VirusesTypesSlide 15Why have types?Types of TypesType TaxonomyScheme/Python/CharmeStrict TypingScheme/Python/Charme  Java/StaticCharmeJava ExampleWhat do we need to do change our Charme interpreter to provide manifest types?ChargeDavid Evanshttp://www.cs.virginia.edu/evansCS150: Computer ScienceUniversity of VirginiaComputer ScienceLecture 31: Lecture 31: Types of TypesTypes of Types2Lecture 31: TruthinessMenu•Using Laziness•Evidence of Laziness? (Quiz Results)•Laziness through Truthiness (Static Type Checking)3Lecture 31: TruthinessLazy Evaluation Recap•Don’t evaluate expressions until their value is really needed–We might save work this way, since sometimes we don’t need the value of an expression–We might change the meaning of some expressions, since the order of evaluation matters•Change the Evaluation rule for Application•Use thunks to delay evaluations4Lecture 31: TruthinessLazy Applicationdef evalApplication(expr, env): # make Thunk object for each operand expression ops = map (lambda sexpr: Thunk(sexpr, env), expr[1:]) return mapply(forceeval(expr[0], env), ops) def evalApplication(expr, env): subexprvals = map (lambda sexpr: meval(sexpr, env), expr) return mapply(subexprvals[0], subexprvals[1:])5Lecture 31: TruthinessLazy Data Structures(define cons (lambda (a b) (lambda (p) (if p a b))))(define car (lambda (p) (p #t)))(define cdr (lambda (p) (p #f)))Note: for PS7, youare defining these as primitives, which would not evaluate lazily.6Lecture 31: TruthinessUsing Lazy Pairs(define cons (lambda (a b) (lambda (p) (if p a b))))LazyCharme> (define pair (cons 3 error))LazyCharme> pair<Procedure ['p'] / ['if', 'p', 'a', 'b']>LazyCharme> (car pair)3LazyCharme> (cdr pair)Error: Undefined name: error(define car (lambda (p) (p #t)))(define cdr (lambda (p) (p #f)))7Lecture 31: TruthinessInfinite Lists(define ints-from (lambda (n) (cons n (ints-from (+ n 1)))))LazyCharme> (define allnaturals (ints-from 0))LazyCharme> (car allnaturals)0LazyCharme> (car (cdr allnaturals))1LazyCharme> (car (cdr (cdr (cdr (cdr allnaturals)))))48Lecture 31: TruthinessInfinite Fibonacci Sequence(define fibo-gen (lambda (a b) (cons a (fibo-gen b (+ a b)))))(define fibos (fibo-gen 0 1))(define get-nth (lambda (lst n) (if (= n 0) (car lst) (get-nth (cdr lst) (- n 1)))))(define fibo (lambda (n) (get-nth fibos n)))9Lecture 31: TruthinessAlternate Implementation(define merge-lists (lambda (lst1 lst2 proc) (if (null? lst1) null (if (null? lst2) null (cons (proc (car lst1) (car lst2)) (merge-lists (cdr lst1) (cdr lst2) proc))))))(define fiboms (cons 0 (cons 1 (merge-lists fiboms (cdr fiboms) +))))10Lecture 31: TruthinessQuiz Results11Lecture 31: TruthinessQuiz Answers1. Programming languages designed by John Backus: Fortran, FP, FL(BNF – not a programming language)2. What did Gödel prove?That any axiomatic system powerful enough to express “This statement cannot be proven in the system” must be incomplete.3. What does SSS0 mean? 312Lecture 31: Truthinessclass Environment: def __init__(self, parent): self._parent = parent self._frame = { } def addVariable(self, name, value): self._frame[name] = value def lookupVariable(self, name): if self._frame.has_key(name): return self._frame[name] elif self._parent: return self._parent.lookupVariable(name) else: evalError("Undefined name: %s" % (name)) elif self._parent._frame.has_key(name)self._parent._frame[name]Quiz 4: Environment Class13Lecture 31: TruthinessQuiz 5: Viruses•Is it possible to define a procedure that protects computer users from all viruses?Here’s one procedure:o Unplug the computer from the powero Encase it in concreteo Throw it in the Potomac RiverThis is a very different question from the “Is it possible to determine if a procedure specification is a virus?” question (which we proved in class is impossible by showing how a solution to it could be used to solve the Halting Problem.14Lecture 31: TruthinessTypes15Lecture 31: TruthinessTypesNumbersStringsBeatle’s Songs that don’t end on the TonicColorslists of lists of lists of anythingprograms that halt•Type is a (possibly infinite) set of values•You can do some things with some types, but not others16Lecture 31: TruthinessWhy have types?•Detecting programming errors: (usually) better to notice error than report incorrect result•Make programs easier to read, understand and maintain: thinking about types can help understand code•Verification: types make it easier to prove properties about programs•Security: can use types to constrain the behavior of programs17Lecture 31: TruthinessTypes of TypesDoes regular Scheme have types?> (car 3)car: expects argument of type <pair>; given 3> (+ (cons 1 2))+: expects argument of type <number>; given (1 . 2)Yes, without types (car 3) would produce some silly result.Because of types, it produces a type error.18Lecture 31: TruthinessType Taxonomy•Latent vs. Manifest–Are types visible in the program text?•Static vs. dynamic checking–Do you have to run the program to know if it has type errors?•Weak vs. Strong checking–How strict are the rules for using types?•(e.g., does the predicate for an if need to be a Boolean?)–Continuum (just matter of degree)19Lecture 31: TruthinessScheme/Python/Charme •Latent or Manifest?–All have latent types (none visible in code)•Static or Dynamic?–All are dynamic (checked when expression is evaluated)•Weak or Strong?–Which is the strictest?20Lecture 31: TruthinessStrict TypingScheme> (+ 1 #t) +: expects type <number> as 2nd argument, given: #t; other arguments were: 1Python>>> 1 + True2Charme> (+ 1 #t)221Lecture 31: TruthinessScheme/Python/Charme  Java/StaticCharme•Scheme, Python, and Charme have Latent, Dynamically checked types–Don’t see explicit types when you look at code–Checked when an expression is evaluated•Java, StaticCharme have Manifest, Statically checked types–Type declarations must be included in code–Types are checked statically before running the program (Java: not all types checked statically)22Lecture 31: TruthinessJava Exampleclass Test { int tester (String s) { int x; x = s; return