The Procedure Abstraction Part II: Symbol Tables, StorageThe Procedure as a Control AbstractionSlide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9The Procedure as a Name SpaceSlide 11Do People Use This Stuff ?Lexically-scoped Symbol TablesExampleSlide 15Implementing Lexically Scoped Symbol TablesSlide 17The Procedure as an External InterfaceWhere Do All These Variables Go?Placing Run-time Data StructuresHow Does This Really Work?Where Do Local Variables Live?Translating Local NamesStorage for Blocks within a Single ProcedureVariable-length DataActivation Record BasicsActivation Record DetailsSlide 28Communicating Between ProceduresPowerPoint PresentationEstablishing AddressabilityEstablishing AddressabilitySlide 33Slide 34Slide 35Slide 36Procedure LinkagesSlide 38Slide 39Slide 40Slide 41Slide 42The Procedure AbstractionPart II: Symbol Tables, StorageCopyright 2003, Keith D. Cooper, Ken Kennedy & Linda Torczon, all rights reserved.Students enrolled in Comp 412 at Rice University have explicit permission to make copies of these materials for their personal use.The Procedure as a Control AbstractionProcedures have well-defined control-flowThe Algol-60 procedure call•Invoked at a call site, with some set of actual parameters •Control returns to call site, immediately after invocationThe Procedure as a Control AbstractionProcedures have well-defined control-flowThe Algol-60 procedure call•Invoked at a call site, with some set of actual parameters •Control returns to call site, immediately after invocationint p(a,b,c) int a, b, c;{ int d; d = q(c,b); ...}…s = p(10,t,u);…The Procedure as a Control AbstractionProcedures have well-defined control-flowThe Algol-60 procedure call•Invoked at a call site, with some set of actual parameters •Control returns to call site, immediately after invocationint p(a,b,c) int a, b, c;{ int d; d = q(c,b); ...}int q(x,y) int x,y;{ return x + y;}…s = p(10,t,u);…The Procedure as a Control AbstractionProcedures have well-defined control-flowThe Algol-60 procedure call•Invoked at a call site, with some set of actual parameters •Control returns to call site, immediately after invocationint p(a,b,c) int a, b, c;{ int d; d = q(c,b); ...}int q(x,y) int x,y;{ return x + y;}…s = p(10,t,u);…The Procedure as a Control AbstractionProcedures have well-defined control-flowThe Algol-60 procedure call•Invoked at a call site, with some set of actual parameters •Control returns to call site, immediately after invocationint p(a,b,c) int a, b, c;{ int d; d = q(c,b); ...}int q(x,y) int x,y;{ return x + y;}…s = p(10,t,u);…The Procedure as a Control AbstractionProcedures have well-defined control-flowThe Algol-60 procedure call•Invoked at a call site, with some set of actual parameters •Control returns to call site, immediately after invocationint p(a,b,c) int a, b, c;{ int d; d = q(c,b); ...}int q(x,y) int x,y;{ return x + y;}…s = p(10,t,u);…Most languages allow recursionThe Procedure as a Control AbstractionImplementing procedures with this behavior•Requires code to save and restore a “return address”•Must map actual parameters to formal parameters (cx, by)•Must create storage for local variables (&, maybe, parameters)p needs space for d (&, maybe, a, b, & c)where does this space go in recursive invocations?Compiler emits code that causes all this to happen at run time int p(a,b,c) int a, b, c;{ int d; d = q(c,b); ...}int q(x,y) int x,y;{ return x + y;}…s = p(10,t,u);…The Procedure as a Control AbstractionImplementing procedures with this behavior•Must preserve p’s state while q executesrecursion causes the real problem here•Strategy: Create unique location for each procedure activationCan use a “stack” of memory blocks to hold local storage and return addressesCompiler emits code that causes all this to happen at run time int p(a,b,c) int a, b, c;{ int d; d = q(c,b); ...}int q(x,y) int x,y;{ return x + y;}…s = p(10,t,u);…The Procedure as a Name SpaceQuickTime™ and aTIFF (LZW) decompressorare needed to see this picture.QuickTime™ and aTIFF (LZW) decompressorare needed to see this picture.The Procedure as a Name SpaceWhy introduce lexical scoping? •Provides a compile-time mechanism for binding “free” variables•Simplifies rules for naming & resolves conflicts•Lets the programmer introduce “local” names with impunityHow can the compiler keep track of all those names?The Problem•At point p, which declaration of x is current?•At run-time, where is x found?•As parser goes in & out of scopes, how does it delete x?The Answer•The compiler must model the name space•Lexically scoped symbol tables (see § 5.7.3)Do People Use This Stuff ?C macro from the MSCP compiler#define fix_inequality(oper, new_opcode) \ if (value0 < value1) \ { \ Unsigned_Int temp = value0; \ value0 = value1; \ value1 = temp; \ opcode_name = new_opcode; \ temp = oper->arguments[0]; \ oper->arguments[0] = oper->arguments[1]; \ oper->arguments[1] = temp; \ oper->opcode = new_opcode; \ }Declares a new nameQuickTime™ and aTIFF (LZW) decompressorare needed to see this picture.Lexically-scoped Symbol TablesThe problem•The compiler needs a distinct record for each declaration•Nested lexical scopes admit duplicate declarationsThe interface•insert(name, level ) – creates record for name at level•lookup(name, level ) – returns pointer or index•delete(level ) – removes all names declared at levelMany implementation schemes have been proposed (see § B.4)•We’ll stay at the conceptual level•Hash table implementation is tricky and detailedSymbol tables are compile-time structures the compiler use to resolve references to names.We’ll see the corresponding run-time structures that are used to establish addressability later.§ 5.7 in EaCExampleprocedure p {int a, b, cprocedure q {int v, b, x, wprocedure r {int x, y, z….}procedure s {int x, a, v…}… r … s}… q …}B0: {int a, b, cB1: {int v, b, x, wB2: {int x, y, z….}B3: {int x, a, v…}…}…}Lexically-scoped Symbol TablesHigh-level idea•Create a new table for each scope•Chain them together for lookup“Sheaf of tables” implementation• insert() may need to create table• it always inserts at