New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Programming Languages

by: Mireya Heidenreich

Programming Languages CS 3723

Mireya Heidenreich
GPA 3.55

Qing Yi

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Qing Yi
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

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.

Similar to CS 3723 at UTSA

Popular in ComputerScienence


Reviews for Programming Languages


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

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


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.