CS计算机代考程序代写 scheme python compiler Java flex c++ Fortran Lecture_18_NamingBindingStorage

程序代写 CS代考 / c++代写, compiler, Fortran代写, Java代写代考, Python代写代考, Scheme代写代考

Lecture_18_NamingBindingStorage

Naming, Binding, and
Storage

CSCI 3136: Principles of Programming Languages

Agenda
• Announcements

• Assignment 7 is out and due July 5.
• Test 2 in class time on July 5.
• Lectures are being recorded

• Readings: Read Chapter 3
• Lecture Contents

• Motivation
• Naming and Binding
• Reference Environments and Scope
• Binding Times
• Object and Binding Lifetimes
• Storage Allocation

2021-06-28 8:38 AM 2

Keywords
Naming
• Name
• Mnemonic
Binding
• Association
Binding Times
• Early Binding
• Late Binding
• Compile time
• Link time
• Load time
• Run time

Scope
• Reference Environments
• Scope of a binding
Binding Lifetime
• Dangling pointers / references
• Memory leaks
Storage
• Allocation
• Deallocation
• Static memory
• Heap
• Dynamic allocation
• Stack

Stack-based allocation
• Subroutines / functions /

procedures / methods
• Caller
• Callee
• Stack frame
• Arguments
• Return address
• Return value
• Local variables
• Temporary variables
• Registers
• Stack pointer
• Base pointer

2021-06-28 8:38 AM 3

End of this Part
CSCI 3136

2021-06-28 8:46 AM 4

Motivation
CSCI 3136

2021-06-28 8:46 AM 5

Motivation
• Programs manipulate data through execution of

code
• Both data and code needs to be identified when

used in the program
• We use names (symbols) to identify the data or

code
• How we link the symbols to the code or data affects

what we can do!
• Question: Fundamentally, is there a difference

between code and data?

2021-06-28 8:38 AM 6

Naming and Binding
• A Name is a (mnemonic) string representing code or

data:
• x, sin, foo, prog1, null? are names
• 42, 3.14, “test”, false, are literals, not names
• +, !=, << . . . are operators and may be names if they are not built-in • A Binding is an association between a name and code or data: • Name and value (for constants) • Name and memory location (for variables) • Name and function • Name and label (for gotos) • Names and bindings are stored in a symbol table at compile time 2021-06-28 8:38 AM 7 Referencing Environment and Scope • A Referencing Environment is a complete set of active bindings at a point in a program • The Scope of a Binding is • the region(s) of a program or • time interval(s) in the programs execution during which the binding is active • A Scope is a maximal region of the program where no bindings are destroyed e.g., body of a procedure • When do bindings occur? int foo(int a, int b) { // Inside the braces is // the scope of foo } 2021-06-28 8:38 AM 8 End of this Part CSCI 3136 2021-06-28 8:38 AM 9 When are Bindings Created? CSCI 3136 2021-06-28 8:38 AM 10 Binding Times • Compile time • Link time • Load time • Run time 2021-06-28 8:38 AM 11 foo.o Compile-Time Binding Bindings are encoded in machine code • Literals are stored in the object file final static String hello = “Hello, World!\n”; • Static data static int [] ThirdYearCore = {3101, 3110, 3120, 3130, 3136, 3171}; • Local (static/private) functions private int helper( … ) { ... } • Gotos / labels • Switch statements switch(c) { case “YES: ... case “NO”: ... case “MAYBE”: ... } DATA “Hello, World!\n” 3101, 3110, 3120, 3130, 3136, 3171 CODE for(…) { ... goto error ... } ... error: … 2021-06-28 8:38 AM 12 ahchoo.exe Link-Time Binding Bindings are initiated by compiler but finalized by linker • Function calls between separately compiled modules int qux(…) { ... bar(...) ... } • Global variables int errno foo.o DATA “Hello, World!\n” 3101, 3110, 3120, 3130, 3136, 3171 CODE qux: … call bar moo.o DATA errno: 0 CODE bar: … zoo.o DATA PI: 3.141… CODE 2021-06-28 8:38 AM 13 Boo.dylib Load-Time Binding Bindings are finalized when program is loaded • Static data locations are fixed (if not done by linker) • Calls to dynamic libraries • Loading of required classes (Java) ahchoo.exe foo.o DATA “Hello, World!\n” 3101, 3110, 3120, 3130, 3136, 3171 CODE qux: … call bar moo.o DATA errno: 0 CODE bar: … zoo.o DATA PI: 3.141… CODE Stack Heap Data Code Data Code Loaded Program 2021-06-28 8:40 AM 14 Run-Time Binding Bindings become active during execution • Set variables a = 42; • Local and temporary variables created on the stack int foo(…) { Object b; ... } • Dynamic memory allocation on the heap (assign references to variables) b = new Object() Stack Heap Data Code a: 42 b 2021-06-28 8:40 AM 15 Early vs Late Binding • When a name is bound affects the program! • Early binding : (compile/link/load time) • Faster code • Typical in compiled languages Example • Functions in C • Late binding : (run time) • Greater flexibility • Typical in interpreted languages Example: • Lambda expressions in Scheme, Java, Python, etc 2021-06-28 8:40 AM 16 End of this Part CSCI 3136 2021-06-28 8:40 AM 17 Object and Binding Lifetimes CSCI 3136 2021-06-28 8:40 AM 18 Object and Binding Lifetimes • Object lifetime : lifetime of code or data • Binding lifetime lifetime of association between name and object 2021-06-28 8:40 AM 19 Object Lifetimes Lifetime of code or data • Period between creation and destruction of object Examples: • Time between allocation (malloc) to deallocation (free) of a piece of memory a = malloc(…); ... free(a); • Time between start/end of a function call (all local variables) int foo(…) { int a; int b; int c; ... } 2021-06-28 8:40 AM 20 Binding Lifetimes Lifetime of association between name and object • Period between the creation and destruction of name to object binding Examples: • Assignment to re-assignment of a pointer to memory a = new Object(); … a = null; • Assignment to re-assignment of a function pointer func = &func_a; … func = &func_b; 2021-06-28 8:40 AM 21 Object Lifetimes vs Binding Lifetimes • Key Idea: Lifetime of bindings typically match lifetime of objects except in the case of aliases • Two common mistakes • Dangling reference : no object for a binding E.g., a pointer refers to an object that has already been deleted m = malloc(…); … free(m); // m no longer points to valid memory • Memory leak : no binding for an object (preventing the object from being deallocated) m = malloc(…); m = NULL; // memory allocated by malloc no longer accessible 2021-06-28 8:40 AM 22 multiple bindings to same object End of this Part CSCI 3136 2021-06-28 8:40 AM 23 Storage Allocation CSCI 3136 2021-06-28 8:40 AM 24 Storage Allocation • Idea: An object’s life-time depends on where it resides • Options for Storage: • Static memory (Data) • Heap • Stack Stack Heap Data (Static) Code 2021-06-28 8:40 AM 25 Static Objects • Stored at a fixed absolute address • Lifetime is the whole program execution • Examples: • Global variables • Static variables local to subroutines that retain their value between invocations • Constant literals (strings) • Tables for run-time support: debugging, type checking, etc. • Space for subroutines, including local variables in languages that do not support recursion (e.g., early versions of FORTRAN) • Allocated at compile/link/load time. Stack Heap Code Data (Static) 2021-06-28 8:40 AM 26 Objects on the Heap • Stored on heap • Created and destroyed at arbitrary times • Explicitly by programmer E.g., malloc(), new, free() • Implicitly by garbage collector • Examples: • Objects (Java) • Dynamically sized memory • Large objects Code Data (Static) Stack Heap 2021-06-28 8:40 AM 27 Heap-Based Allocation • The heap is a region of memory from which objects can be dynamically allocated • The heap can grow as memory demands of a program grow. • Each program has a heap (memory) manager • Part of the program’s runtime environment • Program’s make requests to the heap manager to allocate and deallocate memory • In C: malloc() / realloc() / free() • In C++: new / delete operators • In Java: new operator Code Data (Static) Stack Heap Heap Manager 2021-06-28 8:40 AM 28 Heap-Based De-allocation Deallocation can take two forms: • Explicit deallocation by programmer • Used in Pascal, C, C++ • Efficient • May lead to bugs that are difficult to find: • Dangling pointers/references from deallocating too soon • Memory leaks from not deallocating • Automatic deallocation by garbage collector • Used in Java, functional, and logic programming languages • Can add significant runtime overhead • Safer 2021-06-28 8:40 AM 29 Objects on the Stack • Stored on stack in connection with a subroutine / method / function call • Lifetime from invocation to return from subroutine • Allocation is automatic with each call • Examples: • All local variables • Arguments to a function • Return address • Temporary values Heap Code Data (Static) Stack 2021-06-28 8:40 AM 30 End of this Part CSCI 3136 2021-06-28 8:40 AM 31 Stack-based Allocation CSCI 3136 2021-06-28 8:40 AM 32 Stack Based Allocation • Idea: When a subroutine (function) is called, a stack frame is pushed on the stack • Stack Frame contains: • Arguments passed to the subroutine • Space for the return value (optional) • Return address of caller • Local variables • Temporary (hidden) variables • Registers that must be saved across calls Arg n … Arg 2 Arg 1 Return Value Return Addr Local var 1 Local var m Local var 2 … Saved reg t Base Pointer … Temp var 2 Temp var r Tem var 1 … Saved reg 2 Saved reg 1 … … … … … … … Stack 2021-06-28 8:40 AM 33 Before the Call Caller • Pushes arguments on the stack • Pushes a dummy return value (optional) • Executes call instruction call foo • Pushes return address on stack • Jumps to subroutine (callee) Arg n … Arg 2 Arg 1 Return Value Return Addr … … … … … … … Stack 2021-06-28 8:40 AM 34 During the Call Callee • Saves base pointer • Allocates local variables • Allocates temporary variables • Saves registers • Performs body of subroutine • Restores registers • Destroys local and temp variables • Returns ret • Pops return address off stack • Jumps to return address Arg n … Arg 2 Arg 1 Return Value Return Addr Local var 1 Local var m Local var 2 … Saved reg t Base Pointer … Temp var 2 Temp var r Temp var 1 … Saved reg 2 Saved reg 1 … … … … … … … Stack 2021-06-28 8:40 AM 35 After the Call Caller • Pops arguments off the stack Arg n … Arg 2 Arg 1 … … … … … … … Stack Return Value 2021-06-28 8:40 AM 36 Stack Management 0xDEADBEEF 3.14 42 Return Addr Local var 1 Local var m Local var 2 … Saved reg t Base Pointer … Temp var 2 Temp var r Temp var 1 … Saved reg 2 Saved reg 1 … … … … … … … • The stack is managed through two pointers (kept in registers) • Stack pointer points to the top of the stack • Frame (base) pointer points to the current stack frame Note: One of the registers typically saved on the stack is the previous frame pointer • Example: call foo(42, 3.14, "Hello") BP SP 2021-06-28 8:40 AM 37mov SP, BP; BP = SP A Linked List of Stack Frames … … … … … … … • The stack frames are all linked, from the current function being executed all the way back to main() • Stack frames contain • Return address of each function • Arguments passed • Local variables • A debugger can easily access all this information and allow you to debug your program! … … … … … … … … … … … … … … … … … … … … … BP 2021-06-28 8:40 AM 38

Related Posts