Lecture #24: Achieving Runtime Effects---Functions1: No recursion, no nesting, fixed-sized data2: Add recursion3: Add Variable-Sized Unboxed Data4: Allow Nesting of Functions, Up-Level AddressingStatic LinksThe Global DisplayLecture #24: Achieving Runtime Effec ts—Func tions• Language design and runtime desi g n interact. Semantics of func-tions make good example.• Levels of function features:1. Plain: no recursion , no nesting, fixed-sized data with size knownby compiler.2. Add recursion .3. Add variable-sized unboxed data.4. Allow nesting of functions, up-level addressing.5. Allow function values w/ properly nested accesses only.6. Allow general closures.7. Allow continuation s.• Tension between these effects and structure of machines• Machine la nguages typically only make it easy to access things a taddresse s like R + C, where R is an address in a register and C is arelatively small integer constant.• Therefore , fixed offsets good, data-dependen t offsets bad.Last modified: Thu Apr 28 01:59:31 2005 CS164: Lecture #24 11: No recursion, no nes ting, fixed-s ized data• Total amount of data is bounded, and there is only one instanti a ti onof a function at a time.• So all variables, retur n addresses, and return values can go in fixedlocations.• No stack needed at all.• Characterized FORTRAN programs in the early days.• In fact, can dispense with call instruction s altogether: expand func-tion calls in-line. E.g.,def f (x):x *= 42y = 9 + x;g (x, y)f (3)=⇒ becomes =⇒x_1 = 3x_1 *= 42y_1 = 9 + x_1g (x_1, y_1)• However, program may get bi g g er than you want. Typically, one in-lines only small, frequently executed functions.Last modified: Thu Apr 28 01:59:31 2005 CS164: Lecture #24 22: Add recursion• Now, total amount of data is un-bounded, and severa l instantiation s ofa function can be acti ve simultan eously.• Calls for some kind of exp andable datastructure: a stack.• However, variable si zes still fixed, sosize of each activation r ecord (stackframe) is fixed.• So dynamic links not really needed.Suppose f calls g calls f, as at right.• If sta ck pointer in register, all vari-ables a nd next fra me are at known off-sets from stack pointer....raf’slocalsargumentsto grag’slocalsargumentsto fraf’slocalsTop of stackBase of1st framefixed distanceLast modified: Thu Apr 28 01:59:31 2005 CS164: Lecture #24 33: Add Variable-Sized Unboxed Data• “Unboxed” means “not on heap.”• Boxing all ows all quantitie s on stack tohave fixed size.• So Java implementa tions have fixed-size stack frames.• But does cost heap allocation , sosome langua g es also provide for placingvariable-sized data directly on stack(“heap allocation on the stack”)• alloca in C, e.g.• Now we need dynamic link (DL).• Can still insure fixed offsets of da tafrom frame base (frame pointer).• Suppose f calls g, which has variable-sized unboaxed array (see right)....raDLf’slocalsargumentsto graDLlocalpointerotherlocalsunboxedstorageTop of stackFrame pointerLast modified: Thu Apr 28 01:59:31 2005 CS164: Lecture #24 44: Allow Nesting of Functions, Up-Le vel Addressing• When functions can be nested, thereare three classes of variable:a. Local to function.b. Local to enclosing function.c. Global• Accessing (a) or (c) is easy. It’s (b)that’s interesting.• Consider (in Pyth or recent Python):def f ():y = 42 # Local to fdef g (n, q):if n == 0: return q+yelse: return g (n-1, q*2)• Here, y can be any distance away fromtop of stack.f’sframeg’sframeg’sframe...g’sframeTop of stackEnclosing fHow far???Last modified: Thu Apr 28 01:59:31 2005 CS164: Lecture #24 5Static Links• To overcome this problem, goback to environment diagrams!• Each diag ram had a pointer tolexically enclosin g environment• In Pyth example from last slide,each ‘g’ frame contains a poin terto the ‘f’ frame where tha t ‘g’was defined: thestatic link(SL)• To access local variable, useframe-base pointer (or maybestack pointer ).• To access g l oba l, use absoluteaddress.• To access local of nesting func-tion, follow static link once perdifference in levels of nesting....raDLSLf’s frameraDLSLg’s fr a meraDLSLg’s fr a meraDLSLg’s fr a meTop of stackLast modified: Thu Apr 28 01:59:31 2005 CS164: Lecture #24 6The Global Display• Historically, first solution to nestedfunction p roblem used an array indexedby call level, rather than static links.def f0 ():q = 42def f1 ():def f2 (): ... g2 () ...def g2 (): ... g1 () ...def g1 (): ... f1 () ...• Each time we enter a function at lex-ical level k (i .e., nested inside k func-tions), save pointer to its frame base inDISPLAY[k]; restore on exit.• Access variable at lexical level kthrough DISPLAY[k].• Relies heavily on scope rules and properfunction-call nestingf0’sframeg1’sframef00g11DISPLAYLast modified: Thu Apr 28 01:59:31 2005 CS164: Lecture #24 7The Global Display• Historically, first solution to nestedfunction p roblem used an array indexedby call level, rather than static links.def f0 ():q = 42def f1 ():def f2 (): ... g2 () ...def g2 (): ... g1 () ...def g1 (): ... f1 () ...• Each time we enter a function at lex-ical level k (i .e., nested inside k func-tions), save pointer to its frame base inDISPLAY[k]; restore on exit.• Access variable at lexical level kthrough DISPLAY[k].• Relies heavily on scope rules and properfunction-call nestingf0’sframeg1’sframef1’sframef00f11DISPLAYLast modified: Thu Apr 28 01:59:31 2005 CS164: Lecture #24 7The Global Display• Historically, first solution to nestedfunction p roblem used an array indexedby call level, rather than static links.def f0 ():q = 42def f1 ():def f2 (): ... g2 () ...def g2 (): ... g1 () ...def g1 (): ... f1 () ...• Each time we enter a function at lex-ical level k (i .e., nested inside k func-tions), save pointer to its frame base inDISPLAY[k]; restore on exit.• Access variable at lexical level kthrough DISPLAY[k].• Relies heavily on scope rules and properfunction-call nestingf0’sframeg1’sframef1’sframef1’sframef00f11DISPLAYLast modified: Thu Apr 28 01:59:31 2005 CS164: Lecture #24 7The Global Display• Historically, first solution to nestedfunction p roblem used an array indexedby call level, rather than static links.def f0 ():q = 42def f1 ():def f2 (): ... g2 () ...def g2 (): ... g1 () ...def g1 (): ... f1 () ...• Each time we enter a function at lex-ical level k (i .e., nested inside k func-tions),
View Full Document
Unlocking...