Names Scope and Bindings COMS W4115 Prof Stephen A Edwards Fall 2003 Columbia University Department of Computer Science What s In a Name Name way to refer to something else variables functions namespaces objects types if a 3 int bar baz a 2 int a 10 Names Objects and Bindings binding Object4 Name1 Object3 Name2 ing d bin Object1 Object2 g n i Name3 nd bi b Name4 g indin Names Objects and Bindings binding Object4 Name1 Object3 Name2 g din g bin in ind b Object1 Object2 Name3 Name4 g indin b When are objects created and destroyed When are names created and destroyed When are bindings created and destroyed Object Lifetimes When are objects created and destroyed Object Lifetimes The objects considered here are regions in memory Three principal storage allocation mechanisms 1 Static Objects created when program is compliled persists throughout run 2 Stack Objects created destroyed in last in first out order Usually associated with function calls 3 Heap Objects created deleted in any order possibly with automatic garbage collection Static Objects class Example public static final int a 3 public void hello System out println Hello Static class variable Code for hello method String constant hello Information about Example class Static Objects Advantages Zero cost memory management Often faster access address a constant No out of memory danger Disadvantages Size and number must be known beforehand Wasteful if sharing is possible Stack Allocated Objects Natural for supporting recursion Idea some objects persist from when a procedure is called to when it returns Naturally implemented with a stack linear array of memory that grows and shrinks at only one boundary Each invocation of a procedure gets its own frame activation record where it stores its own local variables and bookkeeping information Activation Records argument 2 argument 1 return address frame pointer old frame pointer local variables temporaries arguments stack pointer growth of stack Activation Records Return Address Frame Pointer x A s variables Return Address Frame Pointer y B s variables Return Address Frame Pointer z C s variables int A int x B int B int y C int C int z Stack Based Langauges The FORTH language is stack based Very easy to implement cheaply on small processors The PostScript language is also stack based Programs are written in Reverse Polish Notation 2 3 4 5 26 OK is print top of stack FORTH CHANGE 0 QUARTERS 25 DIMES 10 NICKELS 5 PENNIES INTO 25 MOD CR 10 MOD CR 5 MOD CR CR CHANGE 3 QUARTERS 112 PENNIES INTO 11 QUARTERS 2 DIMES 0 NICKELS 2 PENNIES 6 QUARTERS DIMES NICKELS PENNIES DIMES 10 NICKELS FORTH Definitions are stored on a stack FORGET discards the given definition and all that came after FOO Stephen BAR Nina FOO Edwards FOO Edwards BAR Nina FORGET FOO Forgets most recent FOO FOO Stephen BAR Nina FORGET FOO Forgets FOO and BAR FOO FOO BAR BAR Heap Allocated Storage Static works when you know everything beforehand and always need it Stack enables but also requires recursive behavior A heap is a region of memory where blocks can be allocated and deallocated in any order These heaps are different than those in e g heapsort Dynamic Storage Allocation in C struct point int x y int play with points int n struct point points points malloc n sizeof struct point int i for i 0 i n i points i x random points i y random do something with the array free points Dynamic Storage Allocation free malloc Dynamic Storage Allocation Rules Each allocated block contiguous no holes Blocks stay fixed once allocated malloc Find an area large enough for requested block Mark memory as allocated free Mark the block as unallocated Simple Dynamic Storage Allocation Maintaining information about free memory Simplest Linked list The algorithm for locating a suitable block Simplest First fit The algorithm for freeing an allocated block Simplest Coalesce adjacent free blocks Dynamic Storage Allocation S N malloc S S S N S S N S N Simple Dynamic Storage Allocation S S N S S free S S N N Dynamic Storage Allocation Many many other approaches Other fit algorithms Segregation of objects by size More clever data structures Heap Variants Memory pools Differently managed heap areas Stack based pool only free whole pool at once Nice for build once data structures Single size object pool Fit allocation etc much faster Good for object oriented programs Fragmentation malloc seven times give free four times gives malloc Need more memory can t use fragmented memory Fragmentation and Handles Standard CS solution Add another layer of indirection Always reference memory through handles ha hb hc a b c compact ha hb hc a b c The original Macintosh did this to save memory Automatic Garbage Collection Remove the need for explicit deallocation System periodically identifies reachable memory and frees unreachable memory Reference counting one approach Mark and sweep another cures fragmentation Used in Java functional languages etc Automatic Garbage Collection Challenges How do you identify all reachable memory Start from program variables walk all data structures Circular structures defy reference counting A B Neither is reachable yet both have non zero reference counts Garbage collectors often conservative don t try to collect everything just that which is definitely garbage Scope When are names created visible and destroyed Scope The scope of a name is the textual region in the program in which the binding is active Static scoping active names only a function of program text Dynamic scoping active names a function of run time behavior Scope Why Bother Scope is not necessary Languages such as assembly have exactly one scope the whole program Reason Information hiding and modularity Goal of any language is to make the programmer s job simpler One way keep things isolated Make each thing only affect a limited area Make it hard to break something far away Basic Static Scope Usually a name begins life where it is declared and ends at the end of its block void foo int k Hiding a Definition Nested scopes can hide earlier definitions giving a hole void foo int x while a 10 int x Static Scoping in Java public void example x y z not visible int x x visible for int y 1 y 10 y x y visible int z x y z visible x visible Nested Subroutines in Pascal procedure mergesort var N integer procedure split var I integer begin end procedure merge var J integer begin end begin end Nested Subroutines in Pascal procedure A procedure B procedure C begin end procedure D begin C
View Full Document
Unlocking...