SPECIAL TOPICS ECEN 5023
Popular in Course
Popular in ELECTRICAL AND COMPUTER ENGINEERING
This 10 page Class Notes was uploaded by Mrs. Lacy Schneider on Thursday October 29, 2015. The Class Notes belongs to ECEN 5023 at University of Colorado at Boulder taught by Staff in Fall. Since its upload, it has received 19 views. For similar materials see /class/231800/ecen-5023-university-of-colorado-at-boulder in ELECTRICAL AND COMPUTER ENGINEERING at University of Colorado at Boulder.
Reviews for SPECIAL TOPICS
Report this Material
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: 10/29/15
System F A Calculus for Modeling Generics Syntax T iaiVaT e xiXTeiee AaeieT Evaluation contexts i ET Reduction rules Aa eT a gt gt Te Type rules FozFeT I39FeVozT1 I39FTgok I39FAozeVozT I39FeT2ozH7 2T1 I39FTlok I397XT1FeT2 FFAXIT1SIT1gtTQ Well formed Types aer RQFTOk I39Fozok I39FVozTok I39FTlok I FTQOk I39FTlaTgok id Aa AXa X gtidiVa aHa idint gt A Xint X int A int idint2 gt 2 int idbool gt A Xboo X bool A bool double Aa Af a A 1 A3 a ff a gtdoubeiV0 agtagtagta doubleint succ 2 gt 4 int Polymorphic Functions on Lists Suppose that operations on lists have the following types nil Va list a cons Va a A list a A list a isnil Va list a A bool hd Va list 3 Ha tl Va list a A list a The map function applies a function to each element in a list creating a new list map Va Vb a A b A list a A list b map Aa Ab Af agt b fix A m list a A list b Als list a if isnia ls then nib consbf heada ls m tail a ls r Type Safety Theorem Preservation lfl39 F e T and e a e then I F e T Theorem Progress If F e T then either e is a value or there is some e such that e a e Theorem Normalization If F e T then for some v e v and v is a value Erasure Typability Type Inference erasex X eraseX T e X erasee erasee1 e2 erasee1 erasee2 eraseAa e erasee eraseeT erasee unit Theorem Wells It is undecidable Whether for a given closed term e in the untyped lambda calculus there is some term e in System Fsuch that erasee e Parametricity gt The type of a polymorphic function constrains the kinds of behavior that function gt For example the following is the only function that has type Va 04 gt 042 Aa Axum X gt Can you think of all the functions that implement the type Vaa gt a gt a gt 047 gt Can you think of all the functions that implement V043 Oz gt gt list 04 gt list Type passing versus type erasure gt The run time semantics presented earlier is called type passing because type application eg AaX Oz Xint substites a type for a type variable producing X int X gt However the types play no important role during run time so performing this substitution is useless work gt Alternatively we can erase types and just evaluate programs using the run time semantics of the untyped lambda calculus gt However to preserve evaluation order we have to be careful with the erasure of type abstraction and type application eraseAa e erasee eraseeT erasee unit First class Polymorphism System F is an example of a language with first class polymorphism V V Polymorphic values can be passed as arguments to functions returned from functions and stored in memory eg as an element of a list V First class polymorphism is rather unusual in programming languages C doesn39t have it ML doesn39t have it Java doesn39t have it V The following is a simple example of a function that uses first class polymorphism AafVaagta fint 1 fbool true Compiling Generics gt There are two common approaches to compiling generics 1 One uniform implementation with boxed representations 2 Typespecialized implementations generated for eac Instantiation gt With first class polymorphism if you want to use typespecialization you have to do run time code generation Though wholeprogram analyses can reduce the need for this
Are you sure you want to buy this material for
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'