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 and Compilers

by: Mr. Hayley Barton

Programming Languages and Compilers COMPSCI 164

Mr. Hayley Barton

GPA 3.93


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

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 16 page Class Notes was uploaded by Mr. Hayley Barton on Thursday October 22, 2015. The Class Notes belongs to COMPSCI 164 at University of California - Berkeley taught by Staff in Fall. Since its upload, it has received 24 views. For similar materials see /class/226666/compsci-164-university-of-california-berkeley in ComputerScienence at University of California - Berkeley.


Reviews for Programming Languages and Compilers


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/22/15
Compiling HigherOrder Languages Lec rur e 24 Prof Necula CS 164 Overview Why higherorder languages Higherorder cons rr39uc rs for Cool Type checking Code gener a rion Prof Necula CS 164 Motivating Example Consider a Graphical User Interface GUI Listens to events from the user key press mouse move and invokes applicationspecific code Let39s write a GUI that counts the total number of events and also prints a message for all mouse events We use a toolkit similar to AWT with classes Event KeyEvent MouseEvent Prof Necula CS 164 User Interface Code class KeyListener keye KeyEvent Object class MouseListener mousee MouseEvent Object class Ui klsn KeyListener mlsn MouseListener Application specific listeners setKeyListenerk KeyListener klsn lt k setMouseListenerm MouseListener mlsn lt m dispatchEvente Event case e o k KeyEvent gt klsnkeyk m MouseEvent gt mlsnmousem Dispatch event to listeners Prof Necula CS 164 Client Code class Counter count Int lt O incrgtlt Int count lt count x class Log printgtlt String Adapter classes class MyKeyListener inherits KeyListener c Counter initcount Counter MyKeyListener c lt count sel keye KeyEvent cincr1 class MyMouseListener inherits MouseListener count Counter log Log initc Counter I Log MyMouseListener mousee MouseEvent countincr1 logprint got onequot let c Counter lt new Counter in install the listeners into the UI uisetKeyListenernew MyKeyListenerinitc uisetMouseListenernew MyMouseListenerinitc new Log Prof Necula CS 164 5 Notes A proliferation of classes and code Some are really interfaces KeyListener MouseListener Some are small adapters MyKeyListener MyMouseListener These classes add complexity new namespaces new constructors without adding much value The KeyListener objects implement function key Idea add firstclass functions to the language Functions can be passed as arguments Expressions can evaluate to functions Fields can have function values As powerful as KeyListener objects Prof Necula CS 164 6 Overview Why higherorder languages Higherorder constructs for Cool Type checking Code generation Prof Necula CS 164 7 New Syntax for Constructing Functions Add new syntax for function expressions fun x T1 T2 E An anonymous function with one argument x of type T1 and result of type T2 and body E Same syntax as methods But can appear anywhere not just as 0 features let c Counter lt new Counter in fun e KeyEvent Object cincr1 The body of the function can refer to all identifiers in scope not just to self and the attributes Similar syntax to lambda from Scheme or Lisp With types fewer parentheses and modern Greekquot keywords Prof Necula CS 164 8 New SynTax for Invoking FuncTions We add The synTax E1052 EvaluaTe E1 To a funcTion evaluaTe E2 To a value and invoke The funcTion wiTh ThaT value leT lisTener lt fun e KeyEvenT in lisTenere How is E1E2 differenT Than El39mE2 E1 musT evaluaTe To a funcTion ThaT is invoked El39 musT evaluaTe To an objecT wiTh a meThod m The acTual code ThaT is invoked is obTained from The dispaTch Table of El39 In meThod calls we pass boTh a quotselfquot argumenT and acTual argumenTs In funcTion calls we pass only The acTual argumenT Prof Necula CS 164 ExTended Cool Types Cool expression used To evaluaTe To objecTs All Types were Cool classes we ignore SELFTPE Today We need To declare fields wiTh funcTion values We need Types for such fields A funcTion is characTerized by The Type of The argumenTs ThaT iT expecTs The Type of The resuIT iT yields We add The funcTion Type T1 gt T2 Type of funcTions wiTh argumenT of Type T1 and resulT of Type T2 We consider only funcTions wiTh one argumenT here Thus new synTax for Types T C T1 gt T2 Prof Necula CS 164 FuncTion Types Examples KeyEvenT gt ObjecT The Type of a key isTener One expression wiTh This Type fun e KeyEvenT ObjecT cincr1 KeyEvenT gt ObjecT gt KeyEvenT gt ObjecT The Type of a funcTion ThaT Takes a key isTener and reTurns a key isTener One expression wiTh This Type fun Isn KeyEvenT gt ObjecT KeyEvenT gt ObjecT fun e KeyEvenT ObjecT sne cincr1 Wraps The isTener Isn wiTh counTing Prof Necula CS 164 User InTer face wiTh HigherOrder FuncTions class HighOrderUi klsn KeyEvenT gt ObjecT mlsn MouseEvenT gt ObjecT seTKeyLisTenerk KeyEvenT gt ObjecT klsn lt k seTMouseLisTenerrn MouseEvenT gt ObjecT mlsn lt rn dispaTchEvenTe EvenT case e of k KeyEvenT gt klsnk m MouseEvenT gt mlsnm No need To define KeyLisTener and MouseLisTener Prof Necula CS 164 12 ClienT Code wiTh HigherOrder FuncTions class CounTer counT InT lt O incrgtlt InT counT lt counT X class Log prinTgtlt STring leT c CounTer lt new CounTer in uiseTKeyLisTener fun e KeyEvenT ObjecT cincr1 uiseTMouseLisTener fun e MouseEvenT ObjecT cincr1 prinTquotgoT onequot No need To define The adapTers MyKeyLisTener and MyMouseLisTener The funcTions can access The variables in scope Prof Necula CS 164 13 Side NoTe on Java Java addresses The verbosiTy associaTed wiTh adapTers in a sligthy differenT way Java allows one To wriTe anonymous nesTed classes leT c CounTer lt new CounTer in uiseTKeyLisTenernew KeyLisTener keye KeyEvenT cincr1 D The KeyLisTener is an inner class derived from KeyLisTener AdvanTages No need To invenT The name MyKeyLisTener The body of The new class can access c direchy We have a more ambiTious consTrucT ThaT reduces verbosiTy even more Prof Necula CS 164 14 Overview Why higherorder languages Higherorder constructs for Cool Type checking Code gener ation Prof Necula CS 164 Typing Rules Function Invocation Typing rule for function invocations ONCheTlaT2 OIllChe1T1 O M C h ee1 T2 Examples let lsn KeyEvent gt Object in lsnnew KeyEvent This rule is not sufficient let lsn Event gt Object in lsnnew KeyEvent Is not welltyped We must relax the typing of actual arguments like for method calls Prof Necula CS 164 Typing Rules FuncTion Invocation Relaxed Typing rule for funcTion invocaTions ONCkeT1aT2 ONChe1T139 Tl39ng ONChee1T2 The Type of The acTuaI argumenT musT conform To The Type of The funcTion parameTer Prof Necula CS 164 17 Typing Rules FuncTion Expression OT1gtltIllCheT3 T3gT2 ONCkfungtltT1T2eT1a T2 Use cur r enT objecT environmenT 0 To check The body For Cool meThods we use a Toplevel environmenT wiTh only self and The aTTr39ibuTes Prof Necula CS 164 18 SubTyping wiTh FuncTion Types We musT also exTend The 3 and lub oper aTions on Types Recall T g T39 means ThaT a value of Type T suppor Ts a operaTions of values of Type T39 C s D when C is a subclass of D Can we have T1 gt T2 3 C No a funcTion does noT supporT meThod dispaTch Can we have C 3 T1 gt T2 No we cannoT apply an objecT To an argumenT Can we have 51 52 T1 gt T2 Yes someTimes Prof Necula CS 164 When can we have 51 2 5 T1 T2 Consider a value v of Type 1 gt 52 When can we use v in place of a value of Type T1 gt T2 We musT be able To Apply v To an objecT of Type T1 and obTain a resulT of Type Tz Ok if T1 3 1 and 52 3 T2 NoTe The direcTion of subTyping on T1 3 51 Example We had This code uiseTKeyLisTener fun e KeyEvenT ObjecT cincr1 D AnoTher correcT varianT uiseTKeyLisTener fun e ObjecT InT cincr1 Because ObjecT gt InT g KeyEvenT gt ObjecT Prof Necula CS 164 20 10 LeastUpperBound with Function Types ubT1 gt T2 C is no r defined If is an error To refurn a func rion in a branch and an objecf in anofher ubT1 gt T2 51 gt 52 gbT1 1 gt ubT2 2 gbT1 1 is The greafesf lower bound of T1 and 51 39 9bT1 51 S T1 and 9bT1 51 S 51 gbC D C if D g C and undefined o rher wise gbT1 gt T2 51 gt 52 ubT1 1 gt gbT2 52 Prof Necula CS 164 Overview Why higherorder languages Higherorder cons rr39uc rs for Cool Type checking Code gener a rion Prof Necula CS 164 II SourceToSource Translation We are adding a feaTure To The language BuT we are noT exTending The seTs of programs we can wriTe We only make iT more convenienT To wriTe some programs We can use a new code generaTion sTraTegy InsTead of generaTing assembly language We compile Cool programs wiTh higherorder funcTions inTo Cool programs wiThouT higherorder funcTions Then we can use The exisTing Cool compiler debugger runTime sysTem This is called sourceTosource TranslaTion Can be done aT The AST level afTer semanTic analysis This is how Java implemenTs inner classes Backwards compaTible wiTh old virTual machines Prof Necula CS 164 23 Code Generation for FuncTions FuncTion expression have delicaTe scoping issues The body of The funcTion may refer To self aTTribuTes local variables We are going To consider several cases in Turn Case 1 FuncTion body does noT refer To self aTTribuTes or locals Case 2 FuncTion body does refer To self and aTTribuTes buT noT To locals Case 3 The full house Prof Necula CS 164 24 Global FuncTions Case 1 FuncTions whose body does noT refer To self aTTribuTes or local variables leT f InT gt InT lt fun x InT InT x 1 in f5 Such funcTions could JusT as well appear aT Toplevel Like funcTions in C or C We could generaTe code like for a regular funcTion Or we compile This inTo Cool We creaTe an adapTer proxy objecT for The funcTion class MyFun applyx InT InT x 1 leT fa MyFun lt new MyFun in faapply5 Prof Necula CS 164 25 Member FuncTions Case 2 FuncTions ThaT do noT access local variables BuT may access self and aTTribuTes class CounTer counT InT lt O lisTenerO ObjecT a ObjecT fun X ObjecT ObjecT counT lt counT 1 l leT f ObjecT a ObjecT new CounTerlisTener in f1 The proxy objecT musT have access To The hosT CounTer Prof Necula CS 164 26 I3 Translation of Member Functions Code from previous slide is translated as follows class Counter count Int lt O getcount Int count setcountgtlt Int count lt X listenerO CounterListener new CounterListenerinitseIf class CounterListener host Counter initc Counter host lt c applygtlt Object Object hostsetcounthostgetcount 1 let fp CounterListener lt new Counterlistener in fpapply1 Prof Necula CS 164 Translation of Member Functions Notes The compiler generates the code for the adapter classes The programmer does not have to write or maintain it I This is how Java inner classes are compiled The compiler might have to add access methods for private fields This is a security hole in Java if your class has inner classes that access the private fields they will be made accessible Same might happen even if a subclass of your class has inner classes This could be fixed by not doing sourcetosource translation Prof Necula CS 164 Nested Functions Case 3 Functions that access local variables let incr Int lt 3 in let f Int gt Int lt fun x Int x incr in f2 The proxy object for quotfquot must have access to incr class MyFun host H incr Int inith Host i Int host lt h incr lt h applyx Int x incr let incr Int lt 3 in let fp MyFun lt new MyFuninitself incr in fpapply2 Prof Necula CS 164 29 Complications with Nested Functions Consider the code let incr Int lt 3 in let f Int gt Int lt fun x Int incr lt 4 x incr in incr lt 5 f2 Does f see the incr lt 5quot Does code see the incr lt 4quot In our compilation scheme the proxy has a m of incr Proxy does not see the changes to incr after is was created Code does not see the changes to incr made in the proxy In code above the result is 2 4 6 Prof Necula CS 164 30 15 Complications wiTh NesTed FuncTions Changes To aTTribuTes are visible because They are made in The same objecT Java inner classes can only access quotfinalquot local variables CannoT be assignedTo in The code nor in The proxy Similar resTricTions in all higherorder languages FuncTional languages even discourage quotassignablequot variables Prof Necula CS 164 31 Conclusions Higherorder funcTions can lead To more compacT and eleganT code Heavily used in graphical ToolkiTs callbacks iTeraTors We can combine The 00 and funcTional paradigm SourceTosource TranslaTion is an easy way To add language feaTures Prof Necula CS 164 32


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

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

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

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

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

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.