Names, Scopes, and Bindings Flashcards
Covers Names, Scopes, and Bindings
Define Names
Mnemonic string used to represent something else; Sort of like tokens. Allows us to refer to variables, types, operations, etc… rather than low-level concepts like addresses.
Define Binding
Association between 2 things; a name and the thing it names.
What is Binding Time?
The point at which binding is created. Or, more generally, the point at which any implementation decision is made.
What is a regular expression?
Formal notation for the lexical structure to ensure clear rules.
What is the scope of the Binding?
The part of the program (textually) in which the binding is active.
Some things are defined during language design time. Name a few.
- Program structure
- Primitive types
- Constructors
Name some items that can be defined during the language implementation time.
- I/O
- Number of bits in primitive types
- How overflow is handled
- Organization of maximum size of stack and heap
What are some pros/cons defining more at language design time than implementation time.
- Portability
- Disallows architecture specific optimization
What are some pros/cons of binding in early stages VS later stages
- Greater efficiency
- Less flexibility
(T/F) The compiler is written during the programming language design time.
False. The compiler is written during the implementation phase.
At what point can programmers modify the programming language?
During the language implementation time.
What things are determined during program writing time?
- Algorithms
- Names
- Data Structures
What things are determined during link time?
- Layout of the whole program in memory
What is determined during load time?
- Choice of physical addresses
What things are determined during compile time?
The layout of statically defined data in memory
What things are determined during run time?
- Variable values
- Sizes of strings
- Start-up time
What is Static Binding?
Binding that happens before run time.
What is Dynamic Binding?
Binding that occurs during run time.
Compilers VS Interpreters: Which has early binding time?
Compilers
Name the 7 language times or phases that binding depends on.
- Design time
- Implementation time
- Program writing time
- Compile time
- Link time
- Load time
- Run time
Define Bindings Lifetime
The period of time between the creation and the destruction of a name-to-object binding.
Define Object Lifetime
The time between the creation and destruction of an object.
Name key events during an objects lifetime
- Creation of object
- Creation of bindings
- How objects are referenced using the bindings
- Temporary deactivation of binding
- Reactivation
- Destruction of both bindings and objects.
When does a dangling reference occur?
When a binding outlives the object.
What is the scope of a binding?
The region of the program in which the binding is active.
When does an object become garbage?
This happens when an object outlives its binding.
Depending on the lifetime of an object, what are the 3 ways to store them?
- Static
- Stack
- Heap
What happens to objects during Static storage allocation?
Objects are given an address that is maintained through the life of the program.
What happens to memory during Stack storage allocation.
Memory allocated in last-in, first-our order, usually in conjunction with subroutine calls and returns.
Describe Heap storage allocation
A region of storage in which sub-blocks can be allocated and deallocated at arbitrary times.
What are some examples of statically allocated memory?
- Global defines
- Code Language translation to machine
- Static variables
- Explicit constants
- Tables used for debugging
Give an example of when static allocation can be used for the whole program.
Static allocation can be used when a language does not support recursion.
List the objects and information commonly found in a stack frame.
- Arguments
- Return address
- Misc bookkeeping
- Local variables
- Temporaries
What is stack allocation typically used for?
- Parameters
- Local Variables
- Temporaries (intermediate values of expressions)
Why use a stack? Give three reasons.
- Allocate space for recursive routines
- Reuse space
- Space for active routines is less than space for all routines (like static allocation)
Stacks use two pointers to keep track of subroutine calls. What are they?
- SP - Stack Pointer
- FP - Frame Pointer
In a stack, what does the stack pointer point to?
First unused location of the stack. Top of the stack.
In a stack, what does the frame pointer point to?
Close to the return address of the subroutine.
In heap allocation, what is internal fragmentation?
This occurs when storage management allocates a block that is larger than required to hold a given object.
In heap allocation, what is external fragmentation?
Memory is available, but in small non-contiguous pieces.
What are heap stuctures’ two main principal concerns?
- Speed
- Space
What is a disadvantage to more intricated heap management?
Time consumption
What is the calling sequence?
The code executed by the caller immediately before and after the call.
What is garbage collection?
Deallocates memory when objects are no longer used.
What are the advantages of explicit garbage collection?
- Simpler compiler implementation
- Better execution speed
What are the disadvantages to explicit garbage collection?
- Subject to dangling references
- Programmer errors causing memory leaks
What are the advantages of implicit garbage collection?
- Simplifies programming task
- No dangling references
- Fewer memory leaks
What are the disadvantages of implicit garbage collection?
- Adds complexity to the implementation of a language
- Reduces execution speed
What is a more precise definition for scope?
A program section of maximal size in which no bindings change.
What is a referencing environment?
The set of active bindings at any given point in a program’s execution.
What do scope rules do?
Define referencing environment.
Describe elaboration.
Refers to the process by which declarations become active when control first enters a scope.
What happens to the binding of global variables that are redeclared?
These bindings are deactivated temporarily untill the duplicate variable goes out of scope.
Describe static scoping.
This happens when the scope of the binding is determined at compile time by examining the text of the program.
Describe dynamic scoping.
This happens when the scope of a binding is determined at runtime (and depends on flow of execution).
Describe the most closely nested rule.
An identifier is known in the scope in which it is declared and in each enclosed scope, unless it is redeclared in an enclosed scope.
(T/F) Outer enclosing routines are not visible to nested subroutines.
FALSE
How are static links used?
Each frame points to the frame of the (correct instance of) the routine inside which it was declared.
In Pascal, how can pointer point to a node that includes the pointer type?
Example:
ListPtr = POINTER TO ListNode
ListNode = RECORD
data: ... next: ListPtr;
END
A pointer is an exception because it can reference any type and still have the same size.
What does information hiding allow the system to do?
It helps make details invisible to parts of the system that don’t need them.
What are some of the benefits of information hiding?
- Reduces cognitive load on programmers
- Reduces the risk of name conflicts
- Can limit access to internals of another abstraction (undefined symbol errors)
How can variables keep their values after leaving their local subroutine invocation?
- Static in C
- Save in Fortran
What is a module? Describe it’s visibility with respect to the whole system.
A module is a collection of objects that are visible to other objects inside the module unless exported.
How are global modules in Modula-2 divided?
Describe their contents.
- Definition module
- Defines the interface
- Contains all info needed to compile a module that uses it (exported names, types, etc)
- Implementation module
- Defines internals
How many instances can Modula-2 have?
How can instances be created?
One instance.
Each instance is a separate module. The code has to be duplicated for a separate instance.
What is a technique in Modula-2 that allows multiple instances of a module?
The module can be used as a manager of a type rather than the type itself.
Do classes dynamically bind procedures to a type?
No. They statically bind procedures to a type.
Programming in the large:
What are the pros/cons of independent compilation?
Can compile different parts of a program independently; however, there is no type checking accross the compilation units.
Programming in the large:
What are some of the benefits of separate compilation?
Can compile different parts of a program independently with type checking across the compilation units.
During separate compilation, the definition module is written and compiled to get a symbol file. With the symbol files, clients can compile their code to get what kind of file?
Object file.
What is Dynamic Scope?
This scope applies to the most recent binding encountered in the program execution.
APL, Lisp, Perl use dynamic scope.
What are some disadvantages of dynamic scoping?
- While subroutines are executing, its local variables are exposed to subprograms.
- Cannot statically type check references.
- Difficult to understand (need to know the path of the calling sequence).
When implementing a static scope in a compiler, what kind of table gets created to store object names and attributes?
Symbol table.
The symbol table attributes includes various things that the compiler needs to know about the name. Name some of these attributes.
- Name type
- Address of offset
- Value of constant, etc.
What are some basic operations provided by a symbol table?
- Create an empty symbol table
- Insert an entry
- Lookup an entry
- Delete an entry
What kind of table can be used to create a symbol table with a monolithic block?
A hash table can be used.
- Insert entries into the table when variables are declared.
- Lookup entries when variables are declared.
In a flat block structure, a symbol table will have variable values for two scope levels. Which are these two basic scope levels?
- Global
- Local
What kind of storage structure is used on a flat block symbol table?
A stack is used. This allows entries to be added in a LIFO way.
On the symbol table, what scope level are global variables in?
Level 1
Symbol tables keep track of variable scopes with levels. If a variable has multiple entries in the symbol table, which scope level is chosen at a given instance?
The variable entry with the highest scope level is selected.
Using a stack to organize a symbol table is simple. Inserting and removing entries is done quickly. On the other hand, what are some drawbacks when using a stack?
- Slow lookup E.g., searching for globals located at the end of a stack.
- For debuggers, symbol table info is usefull. It should not be removed when not used.
As opposed to using a stack data structure for a symbol table, the Leblanc-Cook has improvements that help read items from the table a lot quicker. What technique does this table use?
- Each scope is assigned a unique serial #.
- Stores identifiers in a hash table.
- Table chains entries with the same identifier.
- A separate scope stack records the scopes that belong to the current referencing env.
When a Leblanc-Cook symbol table item goes out of scope, which data structure gets updated, the hash table or the scope stack?
The scope stack. Items get poped off the stack. The updated stack ensure the correct version of the item gets used.
The Leblanc-Cook symbol table works great for static scope during compilation. What are two common symbol tables used for dynamic scope (runtime)?
- Association List
- Central reference table
In an Association list symbol table, entries are placed in what kind of a data structure?
The items are placed on a stack during runtime (dynamic scope)
What kind of data structure gets used in a Central reference symbol table?
Hash table
On a Central Reference Table, new entries are added at the fron of a chain and lookup retreives the first entry in the chain. When an item is no longer in scope, is the item kept or deleted?
The item is deleted.
Deep Binding Vs Shallow Binding
This type of binding occurs when a routine is called.
Shallow Binding
Deep Binding Vs Shallow Binding
This type of binding occurs when a routine is referenced.
Deep Binding
In deep binding, it is important to keep track of the reference location and the binding environment of the subroutine. What is the name of this event?
Closure
Define First Class Objects, and give examples.
These objects can be passed as parameters, returned, and assigned to a variable.
- Simple types
- Functions in functional languages
Define Second Class Objects, and give an example.
Objects that are passed but not returned or assigned.
- Procedures in many imperative languages.
Define Third Class Objects, and give an example.
These objects cannot be passed, returned, or assigned.
- Labels in most languages.
In Perl, the ‘local’ keyword is used to make variables local in a block. When the program leaves the block, the saved value is restored to the symbol table.
This approach gives (Dynamic | Static) binding of names, and (Shallow | Deep) binding of reference environments.
Choose the best answers.
Dynamic
Shallow
In Perl, a variable can be marked as a lexical variable in a block using the ‘my’ keyword. The variable is newly allocated in the block, and deallocated when the program leaves the block. It is stored in a stack-based structure separate from the symbol table.
This technique gives (Dynamic | Static) binding for names, and (Shallow | Deep) binding of the reference environment for that variable.
Choose the best answers.
Static
Deep
What is an alias?
An alias is a set of multiple names that refer to the same object in a scope.
When does overloading occur?
This occurs when multiple objects are bound to the same name in a scope.
If + is overloaded,
2.3 + 3.4 = 5.7
and
2 + 3 = 5
When does polymorphism occur?
This occurs when methods work with multiple type parameters.
When does coercion occur?
This occurs when a compiler automatically converts a value from one type to another when a second type is required by context.
If + is only defined for int, then
2.3 + 3.4 = 5
