Class Note for CS 403 at UA-Programming Languages (3)
Class Note for CS 403 at UA-Programming Languages (3)
Popular in Course
Popular in Department
This 4 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Alabama - Tuscaloosa taught by a professor in Fall. Since its upload, it has received 22 views.
Reviews for Class Note for CS 403 at UA-Programming Languages (3)
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: 02/06/15
Lecture 8 Tuesday 2502 Today Finish garbage collection Introduce static vs dynamic scope Review for exam Reading Assignments For Next Class Finish reading Chapter 771 through 773 Read Chapter 33 Assignments Assignment 2 Due now Assignment 3 Due one week from Thursday 214 Exams Thursday 217 Open book open notes SpnngZEIEIZCS 403 0 st Pa 21 Reference Counts May have to be modified When a function nishes and its variables die Any time a pointer variable appears on the le handside of an assignment statement Any time the garbage collection routine reclaims a chunk of heap space containing a pointer Reference counts don t work on circular lists Why not 5pm 2am cs 403C155 Natzs P e A Approaches to Garbage Collection Reference counts Don t always work well Mark and sweep Works better than reference counts but much more complicated Typical approaches are periodic At some frequency the garbage collection routine runs resulting in periodic performance costs SpnngZEIEIZCS 403 0 st Pa 2 2 Reference Counts Snack 3mm n we 5pm 2am cs 403C155 Natzs P e 5 Reference Counts For every heap object Keep a counter ofthe number of pointers pointing to that object Modify the reference counts everytime a pointer changes either up or down as appropriate When a reference count reaches 0 reclaim that object Requirements Language must keep trackofpointers that change or die eg local variables when a function returns Language must also keep track of pointers within the heap itself when such pointers are either changed or their space is reclaimed Mark and Sweep SpnngZEIEIZCS 403 0 st Pa 2 z Better than reference counts Simplest form 3 steps Collector walks through heap marks each block tentatively as useless Beginning with each pointer outside the heap collector recursively explores all linked data structures in the program marking each newly discovered block as useful Collector again walks through the heap again returning every useless block to free space 5pm 2am cs 403C155 Natzs P e 5 Mark and Sweep improved picture over last day s notes Step 1 Problems with this Version X useless Y useful allocated unallocated smznnzcs maximums p 7 Nonfixedsize blocks Every block must start with An indication of its size An indication of whether or not it is currentlyfree Collector must be able to find pointers embedded within each block Some information at the beginning of the block regarding where the internally embedded pointers are smznnz cs 12st P e m Mark and Sweep Step 2 X useless Y useful allocated unallocated smznnzcs maximums p 2 Scope Def The scope of a variable is the range of statements over which it is visible Def The nonlocal variables of a program unit are those that are visible but not declared there The scope rules of a language determine how references to names are associated with variables smznnz cs 12st P e n Mark and Sweep Step 3 X useless Y useful allocated unallocated l smznnz cs 402st P 29 Static Scope Based on program text To connect a name reference to a variable you or the compiler must nd the declaration Search process search declarations rst locally then in increasingly larger enclosing scopes until one is found for the given name Enclosing static scopes to a speci c scope are called its static ancestors the nearest static ancestor is called a static parent smznnz cs 12st P 212 Static Scope Procedure Nesting procedure 171 M 11 var x procedure pa AB T3 as x 3 a body of 173 A body of n x mm X 5 osmium 4 X7 x body of P1 0 Spring 2002 CS 403 Class Notes Pa e 13 Scope Nesting in C for inti 1 i lt 50 i int x x 1 for intj 1 j lt 50 j cout ltlt x ltlt endl outer x X i39 3 Spring 2002 CS 403 Class Notes Pa e 15 Static Scope Hierarchy P1 P2 P4 P3 F1 This hierarchy represents the nesting structure of the program on the preceding slide 32mg 2002 cs 403 Class Notes pa 3 14 Dynamic Scope Based on calling sequences of program units not their textual layout temporal versus spatial References to variables are connected to declarations by searching back through the chain of subprogram calls that forced execution to this point Spring 2002 CS 403 Class Notes Pa e17 Static Scope with Blocks a method of creating static scopes inside program unitsfrom ALGOL 60 Examples CandC for int index Spring 2002 CS 403 Class Notes Pa e 15 Evaluation of Dynamic Scoping Advantage convenience Disadvantage poor readability ease of making errors Dynamic scoping was a mistake in the languages that supported it APL SNOBOL Lisp Still used in Unix shell programming Spring 2002 CS 403 Class Notes Pa e 18 Static vs Dynamic Scope Behavior Differences l a integer rrglubaldezlaratmn 2 mzedurefis a a 1 Av mzedure Semnd a a integer lmideumm a mo 7 a 2 s ifreadunteger0gtll 9v Semnd Ill else it limo n writeuntegera Static scope output 77 Dynamic scope output 77 SpurgZE ZCSACEChss Nates 219 Exam Review Topics Compilation vs interpretation 16 Specifying language syntax BNF 21 Binding time 31 Storage management Static stack heap 32 Pointers and heap management 32 77 Scope rules 331 332 SpurgZE ZCSACEChss Nates an Some Question Types not guaranteed to be exhaustive Write the BNF for a particular language subset Identify whether a particular program subset is consistent with a particular BNF speci cation Write the assembly pseudocode for a particular program subset Draw pictures of the runtime stack at various points in a program s execution Write code with a dangling reference or memory leak Indicate whether a particular se ment of code contains a dangling reference memory lea both or neither Short answer truyfalse with justi cation explain some concept etc 2m2 cs 403 Class Nates
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'