### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 230 Class Note for CS 50200 at Purdue

### View Full Document

## 22

## 0

## Popular in Course

## Popular in Department

This 31 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Purdue University taught by a professor in Fall. Since its upload, it has received 22 views.

## Similar to Course at Purdue

## Reviews for 230 Class Note for CS 50200 at Purdue

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Type Inference and S ra ric Analysis CS 502 Lec rur39e 4 9208 Static Semantics Check for correctness l Beyond simple syntactic checking Enable optimization l Boxing and unboxing l Shape and pointsto analysis I Optimized representations Enable improved code generation Role of Types III Typechecking l CaTching errors I Types as conTracT beTween implemenTors and programmers l STaTic vs dynamic El ML vs Scheme El Wha r abou r Java III Efficient compila rion l STaTic checking guaranTees cerTain properTies El Eg only applied To in regers Types in Compila rion III Early examples I ForTran enforced s rric r separaTion beTween floaTingpoinT and in reger opera rions El Modern language implemen ra rions Tha r Suppor r overloaded opera rions require some form of run rime TypeTest l Handling variable sized da ra El In Pascal array sizes were par r of an array39s Type El S ra ric layou r of size informa rion is necessary To genera re efficien r code I WhaT happens when size informafion is unknown 39 May need To quotboxquot daTa Guarantees provided by types III Types provide guarantees useful to an implementation l Two pointers with incompatible types cannot alias one another I Loads and stores on objects of different types can be segregated El Supports more aggressive code motion l Optimizing method lookup in an objectoriented language El If dynamic type of a class is known replace expensive lookup with direct jump I Only objects that are references or pointers need to be traversed by a garbage collector Types aT RunTime III Scheme requires runTime Type TesTs l Eg is car applied To a lisT III ObjecTorienTed languages supporT runTime Type inspecTion I Needed To supporT downcasTs l Type hierarchy musT be exposed in The underlying implemenTaTion El Handling polymorphic equaliTy in ML l EqualiTy applies To objecTs of many differenT Types III Compilers musT ofTen propagaTe informaTion To runTime39 l DisTinguish beTween poinTers and inTegers Type Checking STrong vs Weak I Are Type errors allowed To go undeTecTed STaTic vs Dynamic I Are Type errors allowed To manifesT aT runTime We are concerned wiTh implemenTing Type checkers ThaT provide sTrong sTaTic Typing Case S rudy Polymorphism Polymorphism means having many formsquot Adhoc polymorphism l Overloading To opera re over sTrings and numbers I Parame reric polymorphism programs parameTerized over Types III Explici r III Implici r Polymorphism III ExpliciT l Type parameTers in funcTion definiTion leT va id fnTType gt fnaT gt a in idinT 3 idboo True El Requires having values of Type quotTypequot El Very powerful buT Type sysTem is complex III ImpliciT l Type parameTers noT admiTTed l InsTead Types can conTain Type variables which represenT unknown Types Implici r Polymorphism Example I leT vol id fno39o gt 1 in id339 id rrue Implici r polymorphism is o res rric red form of explici r polymorphism l Types musT be discovered To recover informo rion los r by omi r ring Type poromeTers Inference If we omi r Type porome rers we mus r discover whe rher The in rended use of on expression mo rches i rs oc ruol use Implico rions for compilo rion I How do we genero re code for a polymorphic procedure ThoT may be applied To objec rs wi rh very differen r represen ro rions Firs r need To unders rond how inference IALQr39kS Type Variables In ML a Type can be a Type variable I 39a 39b l a Type oper39aTor39 inT bool inT gt inT Types conTaining Type variables are polymorphic oTher39wise They are monomor39phic How do we char39acTer39ize languages like Pascal Java Typechecking MaTch Type operaTors and insTanTiaTe Type variables Need To define where Type variables can appear MusT also enforce conTexTual dependencies l a 9 a subsTiTuTing inT for a musT be done uniformly for all occurrences of The Type variable in The Type Typechecking Perform conTexTsensiTive Type insTanTiaTion using unificaTion l UnificaTion fails when El Trying To maTch Two disTincT Type operaTors inT and bool III insTanTiaTing a Type variable To a Term conTaining ThaT variable 39a and 39a 9 inT l Example Try To Typecheck The following expression fn x gt xx ConsTrainT Based Typing El consTrainTs define equaTions beTween Type expressions ThaT may conTain Type variables E Type inference rules calcuIaTe Types and Their consTrainTs 393 ValidaTe The correcTness of a given seT of consTrainTs under a subsTiTuTion a mapping beTween Type variables and Types SubsTiTuTions A subsTiTuTion 0 is a mapping from Type variables To Types A conTexT is a lisT of variables To Their Types Given a conTexT F and an expression T a soluTion is a pair 0 T where T is a Type such ThaT Type checking CT in The conTexT 0 F yields T Example ConTexT f X a Y Term T fa Possible soluTions X Y gtinTinT X Y gtZ Z X Y gtZZ inT Z X Y gtinT gtinT X H inT gt inT Y H inT inT inT gt inT ConsTr39ainTs El ConsTr39ainTs defined by semanTics of language consTr39ucTs El Goal of Type inference is To find a subsTiTuTion of Type variables To Types ThaT saTisfy gener39aTed consTr39ainTs El Example Expression T fnx 39a gt 39b xO ConsTr39ainT seT inT gt 39c 39a gt 39b SubsTiTuTion 39a H inT 39b H bool 39c H bool Goal is To find mosT gener39al unifier39 for39 a given seT of consTrainTs UnificaTion El Allows us To calculaTe a soluTion mosT general To a consTr39ainT SeT unify C if c is empTy Then else leTSTUC39Cin if S T Then unifyC39 else if S X and X noT e FVT Then unifyX 39 Tlc O X 39 T else if T X and X noT e FVS Then unifyX gt SC o X gt S elseif551 gt52andTT1 gtT2 Then unifyC39 U 1 T1 52 T2 else fail Typechecking El Perform conTexTsensiTive Type insTanTiaTion using unificaTion I UnificaTion fails when U Trying To maTch Two disTincT Type operaTors inT and bool El insTanTiaTing a Type variable To a Term conTaining ThaT variable 39a and 39a 9 inT I Example Try To Typecheck The following expression fn x gt xx Example The Type of lengTh in The following program leT fun lengTh I if null I Then 0 eISe SucclengThTll is 39a lisT 9 inT How does The ML Typechecker deduce This Type Perform a boTTomup inspecTion of The program maTching and synThesizing Types while proceeding To The rooT 39 The Type of an expression is compuTed from The Type of iTs subexpressions and The Type consTrainTs imposed by The conTexT 39 ImporTanT properTy order in which we examine programs and perform unificaTion does noT affecT final resulT le r fun length I if null I Then 0 eISe SucclengThTll Exomgle gcon rz i Consider The Type of leng rh Perform Typechecking using a bo r romup der39ivo rion l 390 null 39b list gt bool nulll bool 39o 39b list 0 inf Tl 39c list gt 39c lisf T 39C 3 39c 39b I 39c liST Type of iniTiolly unknown definifion of null by definiTion of null by definifion of TI unificofion Ie r fun length I if null I ThenO Examgle gcon rz m eISe SucclengfhTl lengTh 39a 9 39d by defini rion of fn lengThTll 39d 39a 39c lisT unificaTion succ in r 9 inT by defini rion of SUCC succlengTh in r 39d inf unificaTion if null inT by defini rion of condiTional fn gt 39c lisT 9 in r Basic algoriThm 1 A variable x inTroduced as a funcTion argumenT assigned a new Type variable STore ltx39agt in a Type environmenT where 39a is fresh 2 In a condiTionaI predicaTe Type unified wiTh bool The True and false branch unified wiTh one anoTher This Type call iT 39b is The Type of The condiTionaI 3 The Type of e in a funcTion fn x gt e is inferred in a conTexT where x is associaTed wiTh a new Type variable 4 In an applicaTion f x f is unified againsT A 9 39b where A is The Type of x and 39b is a new Type variable The Type of f is Therefore a funcTion Type whOSe domain is unifiable To 39b 39b or iTs insTanTiaTion is reTurned as The Type of The funcTion AlgoriThm sconTz D To Typecheck IeT expressions inTroduce noTion of genericiTy WhaT is The Type of The expression 393 fn 1 gt f3 fTrue CannoT Type This in ML because f39s Type is considered non generic 39339 The firsT occurrence of f deTermines a Type inT 9 39a and The second deTermines a Type bool 9 39a 39339 Can39T unify These Two Terms Nongeneric Type variables cannoT be insTanTiaTed muITiple Times wiThin Their defined conTexT To implemenT generic Types make a copy of The Type for every disTincT conTexT in which iT occurs Algori rhm scon rz El Wha r abou r eTvaf fnxgtx in f3fTrue end B Here we will assign 1 Type 39a 9 39a and view 39a as generic I a can assume differen r values for differen r ins ran ria rions of f in The IeTbody Algori rhm scon rz U Need To be careful ro no r copy nongeneric variables eTvaffnggteTvahg in pairh3hTrue end in end Def A Type variable occurring in The Type of an expression e is generic wi rh respec r ro e iff i r does no r occur in The Type of The binder of any func rion defini rion enclosing e AlgoriThm sconTz 1 To Typecheck a eT expression Typecheck iTs declaraTion obTaining an environmenT of idenTifiers and Types used To Typecheck The eTbody 2 Recursive definiTions IeT fun f f in f InsTances of The Type variable in The recursive definiTion musT be nongeneric while insTances in The body are generic Issues III In The presence of imperaTive feaTures Type inference algoriThm jusT described would lead To incorrecT inferences IeT val r ref fn x gt x in r fn x gt x 1 r True end Would infer a Type for r a gt a ref WhaT are The implicaTions Value Res rric rion El Approxima re when if is safe ro generalize Type variables I Use syn rac ric s rruc rure 39 Define a no rion of expansiveness I A nonexpansive variable U cons ran rs U nullary cons rruc rors El variables 393 func rion expressions fn x gt x Value ResTricTion D All oTher expression including funcTion applicaTions leT expressions condiTionals are expansive I Their evaluaTion may enTail nonTrivial compuTaTion ThaT may lead To The creaTion of ref cells I Value polymorphism D given val paT exp El Types of variables appearing in paT can be closed by generalizing Those Type variables appearing free in Their Types buT noT in The conTexT if and only if The expression on The righThand side is nonexpansive Value Res rric rion 393 Example revisi red I The expression val r ref fn x gt x D The righThand side is expansive and The Type variables associa red wi rh X canno r be generalized

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.