Names, Scope, andBindingsCOMS W4115Prof. Stephen A. EdwardsSpring 2003Columbia UniversityDepartment of Computer ScienceWhat’s In a Name?Name: way to refer to something elsevariables, functions, namespaces, objects, typesif ( a < 3 ) {int bar = baz(a + 2);int a = 10;}Names, Objects, and BindingsObject1 Object2Object3Object4Name1Name2Name3Name4bindingbindingbindingbindingNames, Objects, and BindingsObject1 Object2Object3Object4Name1Name2Name3Name4bindingbindingbindingbindingWhen are objects created and destroyed?When are names created and destroyed?When are bindings created and destroyed?Object LifetimesWhen are objects created and destroyed?Object LifetimesThe objects considered here are regions in memory.Three principal storage allocation mechanisms:1. StaticObjects created when program is compliled, persiststhroughout run2. StackObjects created/destroyed in last-in, first-out order.Usually associated with function calls.3. HeapObjects created/deleted in any order, possibly withautomatic garbage collection.Static Objectsclass Example {public static final int a = 3;public void hello() {System.out.println("Hello");}}Static class variableCode for hello methodString constant “hello”Information about Example class.Static ObjectsAdvantages:Zero-cost memory managementOften faster access (address a constant)No out-of-memory dangerDisadvantages:Size and number must be known beforehandWasteful if sharing is possibleStack-Allocated ObjectsNatural for supporting recursion.Idea: some objects persist from when a procedure iscalled to when it returns.Naturally implemented with a stack: linear array ofmemory 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 variablesand bookkeeping information.Activation Recordsargument 2argument 1return address ← frame pointerold frame pointerlocal variablestemporaries/arguments← stack pointer↓ growth of stackActivation RecordsReturn AddressFrame PointerxA’s variablesReturn AddressFrame PointeryB’s variablesReturn AddressFrame PointerzC’s variablesint A() {int x;B();}int B() {int y;C();}int C() {int z;}Stack-Based LangaugesThe FORTH language is stack-based. Very easy toimplement cheaply on small processors.The PostScript language is also stack-based.Programs are written in Reverse Polish Notation:2 3 * 4 5 * + . ( . is print top-of-stack)26 OKFORTH: CHANGE 0 ;: QUARTERS 25 * + ;: DIMES 10 * + ;: NICKELS 5 * + ;: PENNIES + ;: INTO 25 /MOD CR . ." QUARTERS"10 /MOD CR . ." DIMES"5 /MOD CR . ." NICKELS"CR . ." PENNIES" ;CHANGE 3 QUARTERS 6 DIMES 10 NICKELS112 PENNIES INTO11 QUARTERS2 DIMES0 NICKELS2 PENNIESFORTHDefinitions are stored on a stack. FORGET discards thegiven definition and all that came after.: FOO ." Stephen" ;: BAR ." Nina" ;: FOO ." Edwards" ;FOO EdwardsBAR NinaFORGET FOO ( Forgets most-recent FOO)FOO StephenBAR NinaFORGET FOO ( Forgets FOO and BAR)FOO FOO ?BAR BAR ?Heap-Allocated StorageStatic works when you know everything beforehand andalways need it.Stack enables, but also requires, recursive behavior.A heap is a region of memory where blocks can beallocated and deallocated in any order.(These heaps are different than those in, e.g., heapsort)Dynamic Storage Allocation in Cstruct 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 AllocationRules:Each allocated block contiguous (no holes)Blocks stay fixed once allocatedmalloc()Find an area large enough for requested blockMark memory as allocatedfree()Mark the block as unallocatedSimple Dynamic Storage AllocationMaintaining information about free memorySimplest: Linked listThe algorithm for locating a suitable blockSimplest: First-fitThe algorithm for freeing an allocated blockSimplest: Coalesce adjacent free blocksDynamic Storage AllocationSNS SN↓ malloc( )S S N S S NSimple Dynamic Storage AllocationS S N S S N↓ free()S SNDynamic Storage AllocationMany, many other approaches.Other “fit” algorithmsSegregation of objects by sizeMore clever data structuresHeap VariantsMemory pools: Differently-managed heap areasStack-based pool: only free whole pool at onceNice for build-once data structuresSingle-size-object pool:Fit, allocation, etc. much fasterGood for object-oriented programsFragmentationmalloc( ) seven times givefree() four times givesmalloc( ) ?Need more memory; can’t use fragmented memory.Fragmentation and HandlesStandard CS solution: Add another layer of indirection.Always reference memory through “handles.”ha hb hc*a *b *c↓ compactha hb hc*a *b *cThe originalMacintosh didthis to savememory.Automatic Garbage CollectionRemove the need for explicit deallocation.System periodically identifies reachable memory andfrees unreachable memory.Reference counting one approach.Mark-and-sweep another: cures fragmentation.Used in Java, functional languages, etc.Automatic Garbage CollectionChallenges:How do you identify all reachable memory?(Start from program variables, walk all data structures.)Circular structures defy reference counting:A BNeither is reachable, yet both have non-zero referencecounts.Garbage collectors often conservative: don’t try to collecteverything, just that which is definitely garbage.ScopeWhen are names created, visible, and destroyed?ScopeThe scope of a name is the textual region in the programin which the binding is active.Static scoping: active names only a function of programtext.Dynamic scoping: active names a function of run-timebehavior.Scope: Why Bother?Scope is not necessary. Languages such as assemblyhave exactly one scope: the whole program.Reason: Information hiding and modularity.Goal of any language is to make the programmer’s jobsimpler.One way: keep things isolated.Make each thing only affect a limited area.Make it hard to break something far away.Basic Static ScopeUsually, a name begins life where it is declared and endsat the end of its block.void foo(){int k;}Hiding a DefinitionNested scopes can hide earlier definitions, giving a hole.void foo(){int x;while ( a < 10 ) {int x;}}Static Scoping in Javapublic void example() {// x, y, z not visibleint x;// x visiblefor ( int y = 1 ; y < 10 ; y++ ) {// x, y visibleint z;// x, y, z visible}// x visible}Nested Subroutines in Pascalprocedure
View Full Document
Unlocking...