A Course on Temporal Databases - University of Arizona

A Course on Temporal Databases - University of Arizona

Principles of Programming Languages Lecture 06 Implementation of Block Structured Languages C SC 520 Principles of Programming Languages 1 Activations and Environment Aspects of Subroutines: Static vs Dynamic Static subroutine: code (``reentrant) Subroutine in execution: activation record, AR, activation Many activations of same code possible State of a program in execution A collection of activations In a stack or in a heap Contextual relationships among the activations

Exactly one subroutine ``environment access pointers & ``control pointers Activation contents Fixed: program code (shared) Variable: activation Instruction pointer (ip, ra) also resumption address or return address Control Pointer (dl) also control link, dynamic link Environment pointer (ep, fp) also access link, frame pointer Local environment (this activation)fp Nonlocal environment (other activations)sl , static link C SC 520 Principles of Programming Languages 2 Contour Diagram (Static) & RT Stack (Dynamic) P a Q R Q

b c d S T e Q, T, S dl = dynamic link sl = static link to to caller at RT statically enclosing activation S environment T Q(); T Q S(); S T(); R b

c Calling trace: P, R, Q, T, S, control S b Assume static binding T Note sl and dl can be far apart Q Q(); R P R(); C SC 520 Principles of Programming Languages 3 Static Nesting Level (snl) and Distance (sd ) snl = 0 a Q R P

snl = 1 Q b c d S T snl = 2 S e snl = 3 e = b; b snl(a)= 3 sd(a)= 2 snl(name declaration) = # of contour lines surrounding declaration T snl = 3 a = b; snl(b)= 3 sd(b)= 1 snl(name reference) = # contour lines surrounding reference snl(b)= 3 sd(b)= 0

a = b; R b c snl = 2 snl(b) = 2 sd(b) = 0 snl(a) = 2 sd(a) = 1 a = b; C SC 520 Principles of Programming Languages Static Distance of a Symbol Occurrence sd(name occurrence) = # of contours crossed outward from occurrence to declaration = snl(names occurrence) - snl(that names decl.) 4 Symbol Table Computes snl Symbol table maps an occurrence of x to line # snl (declaration) Offset among declarations Each name x has an ``address: (line #, snl, offset) Scanner keeps track of

Contour boundaries crossed (e.g. +1 for { & -1 for }) Current name declarations in scope Scanner can therefore Identify declaration controlling a name occurrence Replace a name occurrence by pointer to symbol table line # C SC 520 Principles of Programming Languages 5 Symbol Table (cont.) P a Q R Q b c d S T S e e = b; T b a = b; a = b; R

b c a = b; C SC 520 Principles of Programming Languages Assume for simplicity all variables are int and occupy one address # name snl offset type &c 1 P 0 0 int () 2 a 1 0 int 3

Q 1 1 int (int) 4 R 1 2 int (int) 5 b 2 0 int 6 c 2 1 int

7 d 2 2 int 8 S 2 3 void (int) 9 T 2 4 int (int) 10 e 3 0 int

11 b 3 0 int 12 b 2 0 int 13 c 2 1 int 6 higher addresses Activation Record Stack sp stack pointer = next available location

temps sp dl sl saved registers fp ra return address dl dynamic link dl sl static link sl locals dl arguments sl fp temps frame pointer = currently executing AR

locals C SC 520 Principles of Programming Languages 7 Activation Record Stack Model an AR by a struct (pretend all data are int for simplicity) struct AR { int arg[n]; int local[m]; AR* sl; AR* dl; CODE* ra; void* rx; register save area ... } Temps are pushed on top (``frame extension) during execution in the activation record and are abandoned on return Assume stack growth to higher addresses (in reality usually the other way) C SC 520 Principles of Programming Languages 8 Registers Special purpose registers: ra, sp, fp General purpose registers divided into two classes Caller-saves: transient values unlikely to be needed across calls

Callee assumes nothing valuable in caller-saves set & can be used at will (destroyed) Ex: temp values during expression evaluation in caller Caller saves these during calling sequence and they are restored after subroutine return Callee-saves: used for local variables and indexes, etc. Caller assumes these registers will not be destroyed by callee Ex: register holding pointer during a list scan Callee saves these in the prologue just after call, and restores in the epilogue just before return C SC 520 Principles of Programming Languages 9 Compiler Code Generation What is generated at CT (to be executed at RT): Upon reference to a variable name x? In caller before call to subroutine Q & after return to callerthe calling sequence? In callee before execution of body?

Prologue In callee before return to caller? Epilogue Assume we are generating code inside body of a subroutine named P Compiler maintains a level counter during code generation: curr_level = current static nesting level of site where code is being generated (body of P) C SC 520 Principles of Programming Languages 10 Access (Reference) to x inside P From symbol table compiler can compute: x snl(x), offset(x) P snl(P) curr_level = snl(P) + 1 (level at which ref occurs) sd(x) = curr_level - snl(x) Generate code to compute l-value into lv: ap = activation record ptr ap = fp; for(i = 0; i < sd(x); i++) ap = ap->sl ; lv = ap + offset(x); Use lv on LHS of assignment, *lv on RHS

C SC 520 Principles of Programming Languages 11 Call Q inside P Calling sequence for ``call Q in source Assume arguments passed by value sp->arg[1] = value of argument 1 ; transmit args ... sp->arg[n] = value of argument n; fp->ra= resume ; set point to resume execution in caller sp->dl = fp; set callees return link fp->ry = ry ; ; save caller-saves registers ap = fp; find AR of callee Qs declaration for(i = 0; i < sd(Q); i++) ap = ap->sl ; sp->sl = ap; set callees static link fp = sp; switch to new environment goto entrypoint(Q); from symbol table, after Q is compiled resume: note stack has not been pushed (callees responsibility) C SC 520 Principles of Programming Languages 12 Prologue Code for Subroutine Q Code executed just after caller jumps to callee Note compiler knows size of AR for Q sp = sp + size(AR of Q) ; push stack frame for current activation

fp->rx = rx; ; save any callee-saves registers now sp points to next available stack location now fp points to subroutine frame base Push could be done by caller (caller knows name of Q at CT) But this will not work for closures (see below) where caller does not know name of callee at CT C SC 520 Principles of Programming Languages 13 Epilogue code for Subroutine Q Code executed just before return to caller Note compiler knows size of AR for Q restore any callee-saves registers pop stack frame for current activation make callers activation current one restore caller-saves registers resume execution in caller just after point of call now sp points to next available stack location now fp points to frame base of caller rx = sp = fp = ry = goto fp->rx

sp - size(AR of Q) ; fp->dl; fp->ry; ; fp->ra; C SC 520 Principles of Programming Languages 14 Display Method Equivalent static chain Linked list replaced by array! Replace traversal of static chain by a single memory reference more efficient calculation of non-local environment references At CT, the maximum static nesting level is known; possible snl values are 1 .. maxsnl The display is an array D of maxsnl elements D[i] = fp for that part of the environment that is in an AR at snl i Executing at snl = 4 D[maxsnl] . . . D[4] D[3] D[2] D[1]

C SC 520 Principles of Programming Languages 15 Access (Reference) to x inside P Generate code to compute l-value into lv: lv = *D[snl(x)]+ offset(x) Use lv on LHS of assignment, *lv on RHS C SC 520 Principles of Programming Languages 16 Call Q inside P sp Q sp fp P inactive Inactive disp P fp . . . . . . D[u]

D[u] . . . . . . D[d+1] D[d+1] D[d] D[d] Before call Q Executing at snl = u in P Subr. Q defined at snl = d u C SC 520 Principles of Programming Languages After call Q Executing at snl = d + 1 (body of Q one level deeper) D[d+1] overwritten to point to new AR 17 Call Q inside P (cont.) Q defined at snl d new AR executes at snl d+1 D[d+1] points to new AR for Q Old D[d+1] (dotted link) destroyed Saved in callers AR (since part of callers display) New AR field fp->disp Other elements D[i] where i d + 2 left alone An AR deeper in the stack might need them upon return

C SC 520 Principles of Programming Languages 18 Call Q inside P (cont.) Calling sequence for ``call Q in source Let u = snl(P) & d = snl(Q) Note fp == D[u] sp->arg[1] = value of argument 1 ; transmit args . . . sp->arg[n] = value of argument n; fp->ra= resume ; set return point in caller sp->dl = fp; set callees return link fp->ry = ry; ; save caller-saves registers fp->disp = D[d+1];save callers display entry to reset on return D[d+1] = sp; set display for callee; D[1..d]are shared fp = sp; switch to callee environment goto entrypoint(Q); from symbol table, after Q is compiled resume: C SC 520 Principles of Programming Languages 19 Prologue/Epilogue code for Subroutine Q Prologue same as before sp = sp + size(AR of Q) ; push stack frame for current activation fp->rx = rx;; save any callee-saves registers Epilogue restores callers display Let rx =

sp = fp = D[u] ry = goto u = snl(Q) this is known to compiler fp->rx; ; restore callee-save registers sp - size(AR of Q) ; pop stack frame for current activation fp->dl; make callers activation current = fp->disp; restore callers display fp->ry; ; restore caller-saves registers fp->ra; resume execution in caller just after point of call C SC 520 Principles of Programming Languages 20 Costs: Static Chain vs Display Compare count of memory references Exclude argument transmission, reg. saves (common to both) Assume fp, sp held in registers Analyze calling sequence for static chain instruction # refs fp->ra= resume ; 1 sp->dl = fp;

1 sp->ry = ry; ; ap = fp; 0 for(i = 0; i < sd(Q); i++) ap = ap->sl; sd(Q) sp->sl = ap; 1 fp = sp; 0 goto entrypoint(Q); 0 sd(Q)+3 C SC 520 Principles of Programming Languages 21 Costs (cont.) Comparison by # memory references: Operation Static chain Display Access local l-value 1 1 Access nonlocal x l-value sd(x) 2 Call Q

sd(Q)+ 3 5 Q Prologue 0 0 Q Epilogue 3 5 Need lots of sd(x)> 2 & sd(Q)> 2 to make worth it C SC 520 Principles of Programming Languages 22 Funargs (Procedure/Function Arguments) P P U R P void P(int x); x U void U(int F(int)); F function formal F(2);

void R(); R T void R(int y); T y U(P); U(T); function actual P Consider call U(T); (both U and T are visible in body of R) T is not visible to U no T activation in the static chain of U at the call T(2) in U, cannot locate definition environment of T! How is the call F(2) implemented? Must work for any F actual What is passed to U in U(T)? R(); C SC 520 Principles of Programming Languages 23

Funargs (cont.) Consider call F(2); Previous calling sequence cannot be used. Missing information shown in blue: sp->arg[1] = value of argument 1 ; ; transmit args fp->ra= resume ; set return point in caller sp->dl = fp; set callees return link save caller-saves registers fp->ry = ry ; ; ap = fp; find AR of callee Fs declaration for(i = 0; i < sd(F); i++) ap = ap->sl ; sp->sl = ap; set callees static link fp = sp; switch to new environment Dont know what F really is at CT and dont know sd(F) and entrypoint(F) goto entrypoint(F); from symbol table, after F is compiled resume: C SC 520 Principles of Programming Languages 24 Calling a Formal: F(); inside U(F)

sd(F) is unknown at CT At RT, the actual functional argument need not even be in Us static chain it is inaccessible from the current AR environment of definition of each funarg must be passed to U as part of actual argument A funarg or closure is a pair (ip, ep) where: ip = entry address of the actual argument procedure ep = reference to most recent activation of definition environment of actual argument procedure C SC 520 Principles of Programming Languages 25 Closure Implementation A closure is a pair of references: struct CL { CODE* ip; instruction pointer (entrypoint) AR* ep; environment pointer } Closure f is built in caller when a named procedure is passed as an actual f is copied to callee U as actual corresponding to formal F : effectively ``F = f When U calls F, the static link in the new activation is set by sp->sl = F.ep and the jump is by goto F.ip C SC 520 Principles of Programming Languages 26 Call F inside U

Calling sequence for ``call F in source where F is a function formal sp->arg[1] = value of argument 1 ; transmit args ... sp->arg[n] = value of argument n; fp->ra= resume ; set return point to resume execution sp->dl = fp; set callees return link fp->ry = ry ; ; save caller-save registers ap = fp; find AR of callee Qs declaration for(i = 0; i < sd(Q); i++) ap = ap->sl ; sp->sl = F.ep; set callees static link fp = sp; switch to new environment goto F.ip; entrypoint of code of actual resume: C SC 520 Principles of Programming Languages 27 Constructing and Passing Closure Consider call U(T)in AR for R Case: actual proc T is visible, named proc & so is U sp->arg[1].ip = entrypoint(T); fp->ra= resume ; set return point to resume execution sp->dl = fp; set callees return link fp->ry = ry ; ; ap = fp;

save caller-save registers find AR of argument Ts declaration for(i = 0; i < sd(T); i++) ap = ap->sl ; sp->arg[1].ep = ap; ap = fp; environment of T set in callee for(i = 0; i < sd(U); i++) ap = ap->sl ; sp->sl = ap; set callees static link fp = sp; switch to new environment goto entrypoint(U); from symbol table resume: C SC 520 Principles of Programming Languages 28 Prologue/Epilogue Code Same as for ``named calls, since code is generated once for each possible named actual such as T Information for allocation/deallocation known at CT for T C SC 520 Principles of Programming Languages 29 Calls with Formal Procedures: Cases Let F, F name formal functional parameters and let U name a visible, actual proc Discuss implementation of calling sequences for each of:

U(F); F(T); F(F); C SC 520 Principles of Programming Languages 30 Calls with Formal Procedures: F(T) Call to a formal proc with an actual visible named proc sp->arg[1].ip = entrypoint(T); ap = fp; find AR of argument Ts declaration for(i = 0; i < sd(T); i++) ap = ap->sl ; sp->arg[1].ep = ap; environment of T set in callee fp->ra= resume ; set return point to resume execution sp->dl = fp; set callees return link fp->ry = ry ; ; save caller-save registers ap = fp; for(i = 0; i < sd(F); i++) ap = ap->sl ; sp->sl = ap; set callees static link set callees static link spsl = F.ep; fp = sp; goto F.ip; resume:

switch to new environment from closure of F C SC 520 Principles of Programming Languages 31 Challenge Can we implement functional parameters using the display? Where does F get its display? (No static chain to unravel given only a starting environment F.ep) How is display restored upon return? C SC 520 Principles of Programming Languages 32 Blocks Extend existing environment: { int x; . . . } Special case of subroutine: No parameters No name Called in one placewhere defined Statically prior env. (surrounding block) == dynamically prior surrounding { float x,y; x = z; y = 3; w = y;

} block C SC 520 Principles of Programming Languages void function B(); { float x, y; x = z; y = 3; w = y; } surrounding B(); block 33 Block Activation/Deactivation A block is like a procedure, but Nameless (because called from only one place) Parameterless Defined at its point of invocation (inline text) Same static binding rules apply (static link == dynamic link) sp->sl = fp; set callees return link fp = sp; switch to new environment sp = sp + size(AR of B) ; push stack frame for block activation entrypoint(B): . . . Body of B . . . sp = sp - size(AR of B) ; pop stack frame for current activation fp = fp->sl; reactivate containing block resume: Why are references in body of B resolved correctly?

Can remove need for new AR by allowing callers AR to grow and shrink C SC 520 Principles of Programming Languages 34 Exercise Show how to handle block entry/exit with using the display method Q sp sp D[u+1] P D[u] fp B D[u] . . . . . . Before block B entry Executing at snl = u in P C SC 520 Principles of Programming Languages fp D[u+1] . . .

disp P . . . After block B entry Executing at snl = u + 1 (body of B one level deeper) D[u+1] overwritten to point to new AR 35 Non-local gotos A sp D label L B fp B C C C D B D A

sp A fp { . . . goto L; . . . } D(); C(); { B(); L: print x; } C SC 520 Principles of Programming Languages sd(L) = snl(use L) snl(def L) = snl(D)+1 snl(L) ap = fp; for(i = 0; i < sd(L); i++) ap = ap->sl ; fp = ap; sp = fp + size(AR of A) ; goto address(L); What if display is used? How restore environment of A? 37 Label Scope Rules Vary /* In C, labels have entire function as scope */ #include main()

{ int i = 3; int n = 10; printf("before forward jump i = %d\n", i); goto fore; back: printf("after back jump i = %d\n", i); if (n < 3) { int i = 7; int j = 13; fore: i = i + 1; printf("after forward jump i = %d\n", i); printf("after forward jump j = %d\n", j); goto back; } else { int i = 99; printf("after else i = %d\n", i); } printf("before return i = %d\n", i); } C SC 520 Principles of Programming Languages 38 Label Scope Rules (cont.) opu> cc labels.c opu> a.out before forward jump i = 3 after forward jump i = 1 after forward jump j = 0 after back jump i = 3 after else i = 99 before return i = 3 opu> C SC 520 Principles of Programming Languages 39 Returned Subroutines main() {

int(int) makemult(int n) { int t(int x){ return n*x; }; return t; } int(int) f; int y; f = makemult(3); y = f(2); } C SC 520 Principles of Programming Languages 40 Returned Subroutines (cont.) null pointer = frame pointer = . . . r0 = makemult(3) f = r0 . . . main Before call to makemult(3) ra dl fp code sl f

fp y At prologue of makemult(3) main ra makemult ra dl dl sl sl f n 3 y fp At return from makemult(3) (closure): typically in register ep C SC 520 Principles of Programming Languages

ip code r0 = x r1 = n r0 = mul r0 r1 41 Returned Subroutines (cont.) code After assignment f = . . . main ra . . . r0 = makemult(3) f = r0 makemult ra dl dl sl sl f n r0 = f(2) 3

r0 = x r1 = n r0 = mul r0 r1 y fp ep At prologue of call f(2) ip f ra dl main ra makemult ra dl dl sl sl f n sl x Note static and

dynamic links differ 3 y ep C SC 520 Principles of Programming Languages ip 2 fp r0 = x r1 = n r0 = mul r0 r1 42 Returned Subroutines (cont.) After assignment y = f(2) makemult ra main ra dl dl sl sl f

n y fp 3 6 ep ip r0 = x r1 = n r0 = mul r0 r1 The AR for makemult(3) is never ``popped while main() is active main activation refers to a function value f functional value f requires definition of n in makemult AR function f in environment can be called again many times So lifetime of makemult AR is lifetime of main ARs now managed on a heap, along with closures C SC 520 Principles of Programming Languages 43

Recently Viewed Presentations

  • Lloyds European Coverholder Event supporting the coverholder network

    Lloyds European Coverholder Event supporting the coverholder network

    Lloyd's European Coverholder Event 'supporting the coverholder network ' 3 November 2010
  • Generative Alignment and Semantic Parsing for Learning from ...

    Generative Alignment and Semantic Parsing for Learning from ...

    Generative models for grounded language learning from ambiguous, perceptual environment. Unified probabilistic model incorporating linguistic cues and MR structures (vs. previous approaches) General framework of probabilistic approaches that learn NL-MR correspondences from ambiguous supervision. Disambiguates the training data
  • Here We Stand

    Here We Stand

    We stand with you because of the Church's ministry and brotherhood and not by the culture's impulses or bandwagons. [click] You stand claimed and positioned in this Baptismal Sacrament, crowned and preserved through this Holy Communion. [click] You stand with...
  • Waste Management - gleninnes-h.schools.nsw.gov.au

    Waste Management - gleninnes-h.schools.nsw.gov.au

    Questions surrounding the issue of waste disposal have traditionally received a great deal of attention. It is becoming more apparent, however, that the focus needs to be on the more sustainable goals of waste minimisation and waste recovery - reducing,...
  • Unit A - Human Activity and Biodiversity

    Unit A - Human Activity and Biodiversity

    Unit A - Human Activity and Biodiversity. 4.1 Reduction of Biological Diversity. Outcomes. ... Example: Swift Fox used to be common in Canada but by 1928 it was extirpated from Canada. ... can help endangered species.
  • IESBA Project Updates

    IESBA Project Updates

    Safeguards in the Code should be neutral and should not distinguish b/w actions that might be performed by professionals who are employed by the firm versus those external to the firm. Agreement that in some cases, e.g., for SMPs, it...
  • SY-1 Acquisition Support Acquisition Support Divisi Aeronautical Systems

    SY-1 Acquisition Support Acquisition Support Divisi Aeronautical Systems

    Your contract. is the foundation for . everything. you will give and receive on your program
  • ERCOT Estimated Total DER Growth 2015-2018 (MW)

    ERCOT Estimated Total DER Growth 2015-2018 (MW)

    Diesel limited growth. Nat Gas Significant growth. Energy Storage limited growth. Utility Scale Batteries (> 1 MW) ... 2019 - SODGs are mapped to their corresponding Loads in the ERCOT Network model. Using the Telemetry of those mapped Loads, ERCOT...