'&$%CSE 341:Programming LanguagesWinter 2006Lecture 18— Tree-Iterator Example and Static vs. Dynamic TypingCSE341 Winter 2006, Lecture 18 1'&$%An Extended ExampleYou’ve seen several advanced and abstract notions:• iterators for separating traversal from processing• thunks for delaying evaluations• passing continuations for “what to do next”– let/cc “forgets what you’re doing” like exceptions– but passing a “continuation function” is a similar idiom• tail recursionAn elegant example that puts it all together: a tree iteratorCSE341 Winter 2006, Lecture 18 2'&$%Cool things about the tree iteratorFundamentally, tree iteration requires a conceptual stack.But using the call-stack is inconvenient because of delayed evaluation.Instead the stack is implicit in our “continuation functions”.And everything is a tail call!Food for thought: There is an automatic transformation that makesevery function call in every program a tail call, eliminating a call-stackand using “continuation functions” instead. Calledcontinuation-passing style.CSE341 Winter 2006, Lecture 18 3'&$%Good and Bad Things About TypesStrong vs. Weak typingIn languages with weak typing, there exist programs thatimplementations must accept at compile-time, but at run-time theprogram can do anything, including blow-up your computer.Examples: C, C++Old “wisdom”: “Strong types for weak minds”New “wisdom”: “Weak typing endangers society and costs billions ayear”Why weak typing? For efficient and low-level implementation(important for 1% of low-level systems)(Not just) My view: Programming is hard enough withoutimplementation-defined behavior. This has little to do with types.CSE341 Winter 2006, Lecture 18 4'&$%Static vs. Dynamic TypingIn ML and Scheme adding strings (‘‘hi’’ + ‘‘mom’’ or (+ ‘‘hi’’‘‘mom’’)) is an error, but in ML it’s at “compile-time” (static) andScheme it’s at “run-time” (dynamic).Indisputable facts:• A language with static checks catches certain bugs without testing(earlier in the s oftware-development cycle)• It is impossible to catch exactly the buggy programs atcompile-time– “Will a program add a string” trivially harder than “Will aprogram terminate”– Application-logic bugs remain (e.g., using factorial where youmeant to use fibonacci)CSE341 Winter 2006, Lecture 18 5'&$%Static CheckingKey questions for a compile-time check (e.g., type-checking):1. What is it checking? Examples (and not):• Primitives (+, apply, ...) are never applied to “inappropriate”values• hd is never applied to the empty list2. Is it sound? (Does it ever accept a program that at run-time doeswhat we claimed it could not? “false negative”)3. Is it complete? (Does it ever reject a program that could not dothe “bad thing” at run-time? “false positive”)All non-trivial static analyses are either unsound or incomplete.Good design leads to “useful subsets” of all programs, typically (butnot always) ensuring soundness and sacrificing completeness .CSE341 Winter 2006, Lecture 18 6'&$%A Question of EagernessAgain, eve ry static type system provides certain guarantees. Here aresome things for which useful static checks have been developed, butare not c ommonly in type systems (yet?): NULL dereferences,division-by-zero, data races, ...There is also more than “compile-time” or “run-time”. Consider x/0.• Compile-time: reject if code is “reachable” (maybe dead branch)• Link-time: reject if code is “reachable” (maybe unused function)• Run-time: reject if code executes (maybe branch never taken)• Even later: maybe delay error until “bad number” is used to indexinto an array or something.– Crazy? Floating-point allows division-by-zero; gives you nan.CSE341 Winter 2006, Lecture 18 7'&$%Exploring Some Arguments1. Dynamic/static typing is more convenient(define (f x) (if (> x 0) (* 2 x) #f))(let ([ans (f y)]) (if ans e1 e2))datatype intOrBool = Int of int | Bool of boolfun f x = if x > 0 then Int (2*x) else Bool falsecase f y ofInt i => e1| Bool b => e2(define (cube x) (if (not (number? x))(error ’cube ‘‘bad arguments’’)(* x x x)))(cube 7)fun cube x = x * x *xcube 7CSE341 Winter 2006, Lecture 18 8'&$%Exploring Some Arguments2. Static typing prevents / doesn’t prevent useful programs• Overly restrictive type systems certainly can (Pascal array sizes,lack of polymorphism)• datatype gives you as much or as little flexibility as you want –can embed Scheme in ML:datatype SchemeVal = Int of int | String of string| Fun of SchemeVal -> SchemeVal| Cons of SchemeVal * SchemeValif e1then Fun (fn x => case x of Int i => i * i * i)else Cons (Int 7, String ‘‘hi’’)Viewed this way, Scheme is “unityped” with “implicittag-checking” which is “just” a matter of convenience.CSE341 Winter 2006, Lecture 18 9'&$%Exploring Some Arguments3. Static/dynamic typing better for code evolution• Dynamic: If you nee d to c hange the type of something, theprogram will still c ompile; easier t o increme ntally upgrade othercode to support the change?• Static: If you change the type of something, the type-checkerguides you to all the places you need to change?In practice, ML’s pattern exhaustiveness is great for the latter.CSE341 Winter 2006, Lecture 18 10'&$%Exploring Some Arguments4. Types should/shouldn’t be extensible (new case s throughoutprogram, at run-time, etc.)• Dynamic: necessary for abstraction, neces sary for an evolvingworld (ubicomp, service disc overy, etc .), even ML does it forexceptions• Static: can never establish exhaustiveness, must always have“default” c lausesA viewpoint: You probably want both options in your language and tothink c arefully in design phase.CSE341 Winter 2006, Lecture 18 11'&$%Exploring Some Arguments5. Types make code reuse harder/easier.• Dynamic: Soundness means you’ll nev er be as flexible assomebody wants; if you use cons cells for eve rything, you can havea rich library for them• Static: Using separate types catches bugs and enforcesabstractions; we can provide enough flexibility in practice (e.g.,with polymorphism)Design issue: Whether to build a new data structure or encode withexisting ones (for libraries) is an important consideration.CSE341 Winter 2006, Lecture 18 12'&$%Exploring Some Arguments6. Types make programs faster/slower.• Dynamic: Don’t have to code around the type system or duplicatecode; optimizer can
View Full Document
Unlocking...