Programming Languages CS 3723
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 29 page Class Notes was uploaded by Mireya Heidenreich on Thursday October 29, 2015. The Class Notes belongs to CS 3723 at University of Texas at San Antonio taught by Qing Yi in Fall. Since its upload, it has received 8 views. For similar materials see /class/231382/cs-3723-university-of-texas-at-san-antonio in ComputerScienence at University of Texas at San Antonio.
Reviews for Programming Languages
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
Scope Functions and Storage Management Implementing Functions and Blocks cs3723 1 Topics El Block structured languages and stack storage I Inline Blocks I Storage for local global variables I Firstorder functions I Implementing function call and return I Passing parameters and returning result I Higherorder functions I deviations from stack discipline I language expressiveness gt implementation complexity E Additional issues I parameter passing I tail recursion and iteration cs3723 Blocks in CCl outer int X 2 block I Inty 3 Inner X 239 block n Blocks regions of code that introduces new variables I Blocks are nested but not partially overlapped I What aboutjumping into the middle of a block I Local variable created by the current block I Global variable created by surrounding blocks II Storage management I Enter block allocate space for variables I Exits block some or all space may be deallocated cs3723 Blocks in Functional languages II ML let fun gy y 3 in let fun hz ggz in h3 end end I Lisp lambda g lambda h h 3 lambda Z 9 9 Z lambda v y 3 cs3723 Summary of Blocks n Blocks in common languages I C I Algol begin end I ML let in end a Two forms of blocks I In line blocks I Blocks associated with functions or procedures El Topic block based memory management I Access to local variables global variables and function parameters cs3723 Managing Data Storage In a Block a Local variables I Declared inside the current block In Enter block allocate space a Exit block deallocate space a Global variables I Declared in a enclosing block a Already allocated before entering current Block 1 Remain allocated after exiting current block a Function parameters I Input parameters a Allocated and initialized before entering function body El Deallocated after exiting function body I Return parameters El Address remembered before entering function body 1 Value set after exiting function body cs3723 Scoping rules Finding non local global variables El Global and local variables int X0 fun gz xz fun hz let x 1 in 92 end 912 Z 3 El Static scope 39 I Find global declarations in the closest enclosing blocks in program text a Dynamic scope I Find global variables in the most recently entered blocks cs3723 Managing Blocks El Activation record data structure allocated on runtime stack Contains space for local variables in the block determined as compile time Contains values of local variables a Evaluated at runtime Before evaluatin each block ush it s activation record onto a runtime stack agter exit the b ock pop activation record off stack int XO Push record with space for x y int YX1 Set values of X y int zxyxy Push record for inner block Set value of z Pop record for inner block Pop record for outer block May need space for variables and intermediate results like Xy XY cs3723 8 Simpli ed Machine Model Registers Code Data Stack Program Counter E Heap Envnronment Pomter i cs3723 9 Data Storage Management n Runtime stack I contains data related to block entryexit I Environment pointer current stack position I Block entry add new data to stack I Block exit remove outdated data a Heap I Contains data of varying lifetime I Variables that last throughout the program I Data pointed to by variables on the runtime stack a Environment pointer points to current stack position I Block entry add new activation record to stack I Block exit remove most recent activation record El Registers code segment and program counter I Ignore registers I Details of instruction set will not matter C53723 10 Managing Activation Records Compilers generate instructions for I Pushing and popping activation records I Deciding the size of activation records I Connecting control links Finding locations of local variables I Calculating the offset of each local variable I Location environment pointer offset Finding locations of global variables I How to find the scope of the variable C53723 11 Activation record for inhne blocks static scoping Environment Pointer IIControl link I Link to activation record of previous calling block I Depends on dynamic behavior of program nAccess link I Link to activation record of immediate enclosing block I Depends on static form of program text nPush record on stack I Set new control link to env ptr I Set env ptr to new record nPop record off stack I Follow current control link to reset environment pointer C53723 12 Example inhne blocks int x0 int yx1 int zxyXy Push record with space for x y Set values of x y Push record for inner block Set value of 2 Pop record for inner block Pop record for outer block Environment CS3723 g 13 Functions and procedures Functions parameterized blocks I fn X ygt X y 23 I lambda X y X y 2 3 I Formal and actual parameters 1 x y formal parameters a 2 3 actual parameters for x y I Activation record for functions include I Parameters I Return address 1 The instruction to jump to after finishing evaluation I Return Result Address 1 Location to put return value before exit C53723 14 Activation record for functions nReturn address I Where to continue execution after exit I Pointer to code space nReturn result address I Where to put return result I Pointer to caller s activation record nParameters I Values for formal Environment Pointer parameters I Initialized with actual parameters C53723 15 Example function calls factk factn if nlt 1 then 1 else n factn l fact3 factZ factl f cs3723 Function Abstraction As Values let Val X1 outer block fun gz Xz I fun hz I let x 2 in gz end in h3 end I h3 El What are values for g and h I How to determine their access links I Nameless inlined blocks 3 Access link control link g3 I Named function blocks 1 Enclosing block of name declaration C53723 17 Closures n A function value is a closure env code I code a pointer to the function body in code space I env current runtime stack 1 Activation records of enclosing scopes a When a function is called I Retrieve value closure of function using its name I Push a new activation record onto runtime stack I Set control link to environment pointer modify environment pointer I Set return address return value addr parameters and local variables I Set access link to the activation record ptr in closure I Set program pointer to the code pointer in closure C53723 18 Function Values as Closures outer block let val X1 fun gz Xz fun hz let x 2 in 4 92 end in h3 end cs3723 Summary Function Parameters El Use closure to maintain I A code pointer to the body of the function I A data pointer to the enclosing environment of function body El When called set access link data pointer from closure then jump to the code pointer I All access links point up in stack I May jump past activation records to find global variables I Still push and pop activation records using stack last in first out order C53723 20 Parameter passing El Each function definition introduces a sequence of formal parameters that are used as local variables in the function body I When the function is called each formal parameter is matched against an actual parameter I What is the relation between each pair of formalactual parameter Passby name I Renaming each occurrence of a formal parameter in function body with its actual parameter delay of evaluation I Used in Lambda calculus and sideeffect free languages Passbyvalue I Each formal parameter is mapped to the value of its actual parameter I Callee cannot change values of actual parameters Passbyreference I Each formal parameter is mapped to the storage of its actual parameter I Callee can change values of actual parameters I Formal parameters in activation record may be aliased n Aliasing two names refer to same location C53723 21 Example What is the nal result pseudocode f 399m V int f int x x x1 return x main int y 0 333 Java print fyy lie cs3723 Standard ML fun fx int ref x x1 x val y ref 0 int ref W y fun f z int let val x ref 2 in x x1 x end val y ref 0 int ref fy y 22 Return Function as Result a Language feature I Functions that return new functions a Eg fun composefg fn x gt gf x El Function created dynamically I Each function value is a closure env code where code may contain references to variables in env I code not created dynamically static compilation El Need to save the runtime environment of function as a pointer to enclosing activation records I But the enclosing activation record may have been popped off the runtime stack I Returning functions as results not allowed in C 1 Just like returning pointers to local variables C53723 23 Exampleskip Function Closure as Returned Result fun mkcounter init int let val count ref init fun counterincint count count inc count in counter end end val c mkcounter1 c2 c2 uter block must be saved after being popped from runtime stack cs3723 24 Summary Return Function Results El Use a closure to maintain the runtime environment of a function El May need to keep activation records of functions event after the function calls return I Stack last in first out order fails a To support return functions as results need to extend the standard stack implementation I Put activation records on heap I Invoke garbage collector as needed I Not as crazy as is sounds a May only need to search reachable data C53723 25 Tail recursion n A function call from g to f is a tail call I if g returns the result of calling f with no further computation tall call not a tall call El Example I fun gx if xgt0 then fx else fx2 El Optimization I Can pop activation record on a tail call I Especially useful for recursive tail call f to f n Callee s activation record has exactly same form n Callee can reuse activation record of the caller u The sequence of recursive calls can be translated into a loop C53723 26 Example What is the result f13 m i Expressed in loop A fun fxy let val z refx in while not lz gty do 2 2 lz A 2 end fun fxy if xgty then X f13 7 else f2x y f13 7 C53723 27 Tail recursion elimination f13 fun fXy if xgty then x else f2x y f13 Optimization pop followed by push gt reuse activation record in place Conclusion tail recursive function calls are equivalent to iterative loops C53723 28 Tail recursion and iteration Nontail recursive function fun mapListf nil nil mapListf Xy fX mapListfy Tail recursive function fun lastxnil X ast Xy asty Iteration fun astinput let val y ref input in while nottlynil do y ty end hde end El Step1 what parameters change when making recursive calls I create a reference for each changed parameter NOTE no need to create reference for the return result 1 Tail recursion only returns at the base case Step2 what is the base case of recursion This is the stop condition for the while loop Step3 what to do before making tail call loop body prepare for the next tail call Step4 return base case value cs3723 29