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 Effects—Functions• Language design and runtime design 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 continuations.• Tension between these effects and structure of machines• Machine languages typically on l y make it easy to acces s things ataddresses like R + C, where R is an address in a register and C is arelatively small integer constant.• Therefore, fixed offsets good, data-dependent offsets bad.Last modified: Thu Apr 28 01:59:31 2005 CS164: Lecture #24 11: No recursion, no nesting, fixed-sized data• Total amount of data is bounded, and th ere is only one instantiationof a function at a time.• So all variables, r eturn addresses, and return values can go in fixedlocations.• No stack needed a t all.• Characterized FORTRAN programs in the early days.• In fact, can dispense with call instructions 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, progra m 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 s everal instantiations ofa fun ction can be active simultaneously.• Calls for some kind of expandable datastructure: a stack.• However, variable sizes still fixed, sosize of each activation record (stackframe) is fixed.• So dynamic links not really needed.Suppose f calls g calls f , as at right.• If stack pointe r in register, all vari-ables and next frame are at known off-sets from s tack 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 al l ows all quantities on stack tohave fixed size.• So Java imp l ementations have fixe d-size stack frames.• But does cost heap allocation, sosome languages 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 fix ed offsets of datafrom frame base (frame pointer).• Suppose f calls g, which has variable-sized unboaxed a rray (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-Level Addressing• When function s 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: retu r n g (n-1, q*2)• Here, y can be any distance away fromtop of stack.f’sframeg’sframeg’sframe...g’sframeTop of stackEnclosing fHow fa r???Last modified: Thu Apr 28 01:59:31 2005 CS164: Lecture #24 5Static Links• To overcome this problem, goback to environment diagrams!• Each diagram had a pointer tolexically enclosing environment• In Pyth example from last slide,each ‘g’ frame contai ns a pointerto the ‘f’ frame where that ‘g’was defined: thestatic link(SL)• To access local variable, useframe-base pointer (or maybestack pointer).• To access global, use absoluteaddress.• To access local of nesting func-tion, follow static link once perdifference in levels of nesting....raDLSLf’s frameraDLSLg’s fra meraDLSLg’s fra meraDLSLg’s fra meTop of stackLast modified: Thu Apr 28 01:59:31 2005 CS164: Lecture #24 6The Global Display• Historically, first solution to nestedfunction problem used an array indexedby call l evel, 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 i ts 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’sframef2’sframeg2’sframeg2’sframeg1’sframef00g11g22DISPLAYLast modified: Thu Apr 28 01:59:31 2005 CS164: Lecture #24
View Full Document
Unlocking...