New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Programming Languages

by: Mrs. Carolyne Abbott

Programming Languages CS 6610

Mrs. Carolyne Abbott
GPA 3.71

Westley Weimer

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Westley Weimer
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 11 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 6610 at University of Virginia taught by Westley Weimer in Fall. Since its upload, it has received 18 views. For similar materials see /class/209657/cs-6610-university-of-virginia in ComputerScienence at University of Virginia.

Similar to CS 6610 at UVA

Popular in ComputerScienence


Reviews for Programming Languages


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: 09/21/15
Modeling and Understanding ObjectOriented Programming BECAUSE THEN TH I39M THINKING ABOUT IT39S MY PATRIOTIC BUYXNG A MORE FUEL g own To REDUCE THE EFFICIENT CAR COUNTRYS DEPENDENCE ON FOREIGN SOURCES D OIL f39 T F M L I l w M l muu scommms a Am c AND THE STATEMENT MOULD BE quotHEY EVERY NE DON39T NDE STAND lAJHAT FUNGIBLE MEANS AT LEAST I NOULDN T OIL IS A FUNGXBLE BE FUNDING THEM COMMODITY THE MYSELF CAPITALIST SYSTEM VIRTUALLY GUARANTEES 1 THA t Official Survey o Please fill out the Toolkit course survey o 40142 CS 6551 o Apr212006 Midnight gt May042006 9am Why not do it this evening lF YOU WA YD sum m FUN NT is STAY DADquot 5v m ADOW some 6 KS TO YOUR A SURl RlSE o v AN SOME SFEClN NTERST WPS ARE lN FOR F THOSE POLE lRTUNJX All DWECDM DF DRN lNG LEAN Dy FAVOR WNW S Cunning Plan Focus On Objects o A Calculus For 00 o Operational Semantics o Type System o Expressive Power o Encoding 00 Features YOU ALREADY GO Ds FOR 1 E CHR 15 AND LABOR DAY BUT I TOTALLY THlNK HE NEEDS MOR A o 2004 Krlsmm erauh kemoardnighuuzyuom o We want a wcalculus or IMP for objects The Need for a Calculus o There are many 00 languages with many combinations of features o We would like to study these features formally in the context of some primitive language Small essential flexible 4 Why Not Use kCalculus for 00 We could define some aspects of 00 languages using kcalculus eg the operational semantics by means of a translation to kcalculus But then the notion of object be secondary Functions would still be firstclass citizens Some typing considerations of 00 languages are hard to express in Xcalculus ie objectorientation is not simply syntactic sugar Object Calculi Summary As in kcalculi we have operational semantics denotational semantics type systems type inference algorithms guidance for language design We will actually present a family of calculi typed and untyped firstorder and higherorder type systems We start with an untyped calculus 5R An Untyped Object Calculus o An object is a collection of methods Their order does not matter o Each method has A body that produces a result o The only operations on objects are Method invocations Method update A bound variable for self denoting the host object Untyped Object Calculus Syntax o Syntax ab variables object constructor g is a variant of Greek letter 0 x is the local name for self I am method invocation no arguments just the self method update this is an expression the result is a copy of the object with one method changed This is called the Untyped gcalculus Abadi amp Cardelli I am e ggtlt b First Examples o An object o with two methods m1 and mZ m1 returns an empty object m2 invokes m1 through self omisx1 m2gxxm11 o A bit cell with three methods value set and reset value returns the value of the bit 0 initially set sets the value to 1 reset sets the value to 0 models state without MIMP objects are primary b value ggtlt 0 set ggtlt xvalue e gy 1 reset ggtlt xvalue e gy 0 Operational Semantics o a a b means that a reduces in one step to b o The rules are let 0 be the object mi ggtlt bi omi H OX bi omk e gy b A mk Y b mi glxl bi 1 e 1 n 14 o We are dealing with a calculus of objects o This is a deterministic semantics has the Church Rosser or diamond property Expressive ness A calculus based only on methods with self Xpressive is this language Let s see Can we encode languages with fields Yes Can we encode classes and subclassing Hmm Can we encode Acalculus H Encoding fields Fields are methods that do not use self Field access of is translated directly to 0d invocation ofquot Field update of e equot is translated to of e ggtlt equot We will drop the ggtlt from field definitions and updates As Expressive As A o Encoding functions A function is an object with two methods arg the actual value of the argument val the body of the function A function call updates arg and invokes val o A conversion from Acalculus expressions gtltarg read the actual argument 1arg e W Q2Val e arg W Marga val X Q The initial value of the argument is undefined o From now on we use 7 notation in addition to g imam gtlt Acalculus into gcalculus Encoding Classes Consider the conversion of kxx 5 A w is just an object with a new Let 0 arg gz Zarg val gx Xarg method for generating new objects AXX 5 Oarg 4 GW 5Vat A repository of code for the methods of the Consider now the evaluation of this latter gterm generated ObjeCtS 50 that generated ObjeCtS d0 Let 0 arg gm 5 val gm Xarg not carry the methods with them 0mg 4 gm 5Val gt o Example for generating o mi gx bi o val arg gy 5 val gx Xargval gt C neW 92 mi 900 Z miX Xargo lx o arg gt m gself xx bi 5o y 5 The object can also carry updateable methods Note that the mi in c are fields don t use self Class Encoding Example Inheritance and Subclassing A class of bit ceus o Inheritance involves reusing method bodies BitClass new gZ val gx 0 FlipBitClass set 90 2395 X new gz BitClassnewflip lt gx Zflip X reset gx Zreset x set dz 7 XVal lt gm 1 flip gZ Xx xval lt not xval reset gz Ax xval lt gy 0 0 Example 39 Example FlipBitClassnew gt val gx 0 BitClassnew gt val gx 0 t BtCl t set gx BitClassset X se dx 1 ass se X reset gx BitClassreset X reset Gtx B tCtaSSreset X The new object carries with it its identity flip gX FlipBitClassflip X The indirection through BitClass expresses the dynamic dis atch through the BitClass method table We can model method overriding in a similar way 15 51 FirstOrder Object Types Object Types Subtyping The previous calculus was untyped Second attempt Can write invocations of nonexistent methods A mi A1 foo gx bogus Specify the available methods and their result types We want a type SYStem that guarantees that wett39 Wherever an object is usable another with more typed expressions only invoke existing methods methods Should also be usable FirSt attempt This can be expressed using width subtyping An object s type specifies the methods it has available A lt B B lt C A m1 m2 mn Not good enough A lt A A lt C If 0 m then we still don t know if omm is safe n gt k We also need the type of the result of a method ml A17 mn An lt ml A17 7 mk Ak Typing Rules rhbiA 711A7 A n1 Abb 2 A r h mi 2 51 2 A by 2 A r h bum 2 A Fl bA miZAZEA FmAl b Ai F bml lt b Z A Type System Results Theorem Minimum types If F l a A then there exists B such that for any A such that F l a A we have B lt A If an expression has a type A then it has a minimum most precise type B Theorem Subject reduction f l aAanda gtvthen l VA Type preservation Evaluating a welltyped expression yields a value of the same type Type Examples o Consider that old BitCell object o value gX 0 set gx xvalue lt gy 1 reset gx xvalue lt gy 0 o An appropriate type for it would be BitType value int set BitType reset BitType Note that this is a recursive type Consider part of the derivation that o BitType for set I 2 BitType value 2 int 6 BitType T I BitType y I BitType F 1 2 int 1 Z BitType F va1ue e 301 Z BitType Unsoundness of Covariance Object types are m not cocontravariant Example of covariance being unsafe LetU andLmU By our rules L lt U LetP xUfUandQ xLfU Assume we mistakenly say that Q lt P hoping for covariance in the type of x Consider the expression q Q X m 1 f slstQ SXm Then q P by subsumption with Q lt P Hence qx lt P This yields the object x f gsQ sxm Hence qx lt f U yet qx lt f fails Covariance Would Be Nice Though o Recall the type of bit cells BitType value int set BitType reset BitType o Consider the type of flipable bit cells FlipBitType value int set FlipBitType reset FlipBitType flip FlipBitType o We would expect that FlipBitType lt BitType o Does not work because object types are invariant o We need covariance subtyping of recursive types Several ways to fix this Variance Annotations Covariance fails if the method can be updated If we never update set reset or flip we could allow covariance We annotate each method in an object type with a variance means readonly Method invocation but not update means writeonly Method update but not invocation 0 means readwrite Allows both update and invocation We must change the typing rules to check annotations And we can relax the subtyping rules Who Are You This is the part where we mention our names I m abysmal at remembering them so you ll have to help me out and something we like eg m partial to Babylon 5 Programming Languages Topic of Ultimate Mastery Wes Weimer CS 655 TR 500615 MEC 339 http wwwcsvirginiaeduweimer655 Today s Class Vague Historical Context Goals For This Course Requirements and Grading Course Summary Convince you that PL is useful MGta39LeVel 39nformatlon What Have You Done For Us Lately Please interrupt at any time Isnt PL a solved problem completely CmmUlent queries PL is an old field within Computer Science I don t understand please say it another way 1920 s computer person Slow down you talk too fast 1936 Church s Lambda Calculus PL Wait I want to read that 1937 Shannon s digital circuit design I don t get joke x please explain 1940 s first digital computers GoAHEAD HAVEALLTHESE 1950 s FORTRAN PL I VE MlSSED 10x SHOULDN39T LQOK x Don t mm I mm or W BE PLANNlNG lTS too MUCH To AsK 39 m I 1 958 LISP Pl TV SHOW now m LlFE 1m NE sn mam BELlEVE u o You WERE REG SNE smme TIMTS THE 1960 s Unix 1972 C Programming Language 1981 TCPIP 1985 Microsoft Windows 1992 Ultima Underworld Wolfenstein 3D I LL GET T 0 14le um FQR 4 I M EXl ECTlNG AROJND THE W AN l NM Don t We Already Have Compilers DOCTOR FUN i a E a a c a Progrss Dismal View Of PL Research DOCTOR FUN v Parts of Computer Science CS Math gtlt Logic Engineering Science from Latin scientia knowledge refers to a system of acquiring knowledge based on empiricism experimentation and methodological naturalism aimed at finding out the truth We rarely actually do this in CS CS theory Math logic Systems Engineering bridge building Programming Languages o Best of both worlds Theory and Practice Only pure CS theoryis more primal o Touches most other CS areas Theory DFAs PDAs TMs language theory eg LALR Systems system calls assembler memory management Arch compiler targets optimizations stack frames Numerics FORTRAN IEEE FP Matlab Al theorem proving ML search DB SQL persistent objects modern linkers Networking packet filters protocols even ruby on rails Graphics OpenGL LaTeX PostScript even Logo LISP Security buffer overruns net bytecode PCC Software Engineering obvious Overarching Theme assert and shall convince you that PL is one of the most vibrant and active areas of CS research today It has theoretical and practical meatiness It intersects most other CS areas You will be able to use PL techniques in your own projects Goal 1 oLearn to use advanced PL techniques Useful Complex Knowledge o A proof of the fundamental theorem of calculus o A proof of the maxflow mincut theorem o Nifty Tree node insertion eg BTrees AVL RedBlack o The code for the Fast Fourier Transform o And so on No Useless Memorization o I will not waste your time with useless memorization o This course will cover complex subjects o I will teach their details to help you understand them the first time o But you will never have to memorize anything lowlevel o Rather learn to apply broad concepts Goal 2 When not if you design a language it will avoid the mistakes of the past and you ll be able to describe it formally Story The Clash of Two Features Real story about bad programming language design Cast includes famous scientists ML 3982 is a functional language with polymorphism and monomorphic references ie pointers Standard ML 3985 innovates by adding polymorphic reference It took 10 years to fix the innovation Polymorphism Informal Code that works uniformly on various types of data Examples length a list a int takes an argument of type list of 0 returns an integer for any type a head a list a a Type inference generalize all elements of the input type that are not used by the computation References in Standard ML Like updatable pointersquot in C Type constructor ptr r Expressions alloc r a ptr r allocate a cell to store a r e I when e ptr t read through a pointer e e39 with e ptrr and e39 I write through a pointer Works just as you might expect Polymorphic References A Major Pain Consider the following program fragment Code Type inference fun idx x val c alloc id idocgt0c foranyu c pfr on a on for any a fun incx x 1 inc in r int c inc 0 quothiquot Ok since c pi39r39in139 inf Ok since c pi39r39 string a string Reconciling Polymorphism and References Type system fails to prevent a type error Solutions examples weak type variables polymorphic variables whose instantiation is restricted difficult to use several failed proofs of soundness value restriction generalize only the type of values easy to use simple proof of soundness Story Java Bytecode Subroutines Java bytecode pro rams contain subroutines jsr that run in the cal er39s stack frame jsr complicates the formal semantics of bytecodes Several verifier bugs were in code implementing jsr 30 of typing rules 50 of soundness proof due to jsr It is not worth it In 650K lines of Java code 230 subroutines saving 2427 bytes or 002 13 times more space could be saved by renaming the language back to Oak In 1994 the language was renamed Java after a trademark search revealed mat we name Oak was used by a manufacturer of video adapter cards Recall Goal 2 When not if you design a language it will avoid the mistakes of the past and you ll be able to describe it formally Goal 3 Understand current PL research PLDI POPL OOPSLA Fina Gal Fun 5 Assi nments PrerequISItes 4 g u I Short Homework ASSIgnments 7 Undergraduate Q Scribe Notes 25 classsize compilers Final PrOJect course Final Exam Mathematical Course Evaluations ICANT BEUEVE IT Il lA iET WRWEA wage otsosoop m atu n W aka W W W N CHTV a g l H i Q Homework Problem Sets Scribe Notes o Some material can be mathy Longstanding CS tradition o Much like in Calculus practice is o Every class one or two students take handy detailed notes and latex them up o Short 3 problems HW o post the notes This course has no TA Provides I don t Went to be grading a formal set of course note o You have one week to do each one practice paper writing typesetting study guides Final Project Final Exam o Literature survey implementation o I reserve the right to make prOJect or research prOJect threatening noises about a take Write a 10page paper a la PLDI home final exam o Give a 1015 minute presentation But there s no TA 0 On the tOPiC Of your ChOlCe Draw your own conclusions I will help you find a topic many Notably if everyone does quite well on examples all other assignments the final Best integrate PL with your current beCOmeS unnecessary research How Hard Is This Class This Shall Be Avoided v In 1930 the Republicancontrolled House of Resentatives in an effort to alleviate the effects of the Anyone Anyone the Great Depression passed the Anyone Anyone The tariff bill The HawleySmoot Tariff Act Which anyone Raised or lowered raised tariffs in an effort to collect more revenue for the federal government Did it work Anyone Anyone know the effects Key Features of PL Amgnn dungeons Uragans caMe an E Where are we at L guns mm new Me we purge drugm I y 39 Nama was J MEN an Vungeahs Programs and Languages Programs What are they trying to do Are they doing it Are they making some other mistake Were they hard to write Could we make it easier Should you run them How should you run them How can I run them faster Programs and Languages Languages Why are they annoying How could we make them better What tasks can they make easier What cool features might we add Can we stop mistakes before they happen Do we need new paradigms How can we help out My Favorite Domain Common PL Research Tasks o Design a new language feature o Design a new type system checker o Design a new program analysis o Find bugs in programs o Design a new feature meaning o Transform programs source or assembly o Interpret and execute programs o Prove things about programs o Optimize programs Grand Unified Theory CS 655 Core Topics Design a new type system Operational semantics Your typechecker becomes a bugfinder Type theory No type errors gt proof program is safe Verification conditions 5i Design a new language feature Abstract interpretation K To prevent the sort of mistakes you found Lambda Calculus i 39 r Write a sourcetosource transform Concurrency r 3 quot39 Your new feature works on existing code Type systems Mf f 1 5 So 91 A VOTE OF 8 To 2 WE HAVE DEClDED To SM Tm MDUSTRIAL YZEVowtoN COMETEL AND Go mom INTO me ELELTRONIC AGE Special Topics In Our Next Exciting Episode Program Verification Using lt9 Ggt U n Def oX nx n CounterexampleGuided Abstraction ltx e ogt U oX n GXI ny 6Y Refinement Type Systems For Resource Management ltb 5gt U false Possibly Bug Finding And Verification In The Real World Coverity guest lecture What do you want to hear about ltwhile b do c ogt U o ltb ogt U true ltc while b do c ogt U o39 ltwhile b do c o gt U o39 Meat Today Judgments Rules of Inference Hypothesis1 HypothesisN hypotheses therefore result Conclusion lte GgtUn Fl bzbool Fl e1zt Fl e2t Z39ZPgtQgtPgtP Fl ifbthene1elsee2t G A 2 F b X I FX For any given proof system a finite number of rules of inference or schema Can really show anything Varies by judgment are llSted 50m Wh F Rule instances should be easily checked What is the definition of NP


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Bentley McCaw University of Florida

"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!"

Allison Fischer University of Alabama

"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!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"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."

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.