Bindings & The Symbol Table
What is binding and what are the different types of it?
The process of associating an attribute with a name
Static binding: occurs before execution
Dynamic binding: occurs during execution
What is a type constructor?
- mechanisms used with a group of basic types to construct more complex types (combine basic types to create complex data structures like arrays or records)
Define type equivalence and the difference between structural equivalence and name equivalence
Type equivalence: rules for determining if 2 types are the same
Structural equivalence: 2 data types are the same if they have the same structure
Name equivalence: 2 data types are the same if they have the same name
What is the difference between static and dynamic scoping?
Static scoping: all declarations processed prior to execution
AKA lexical scoping
Symbol table is managed by a compiler
Bindings of declarations are all static
Dynamic scoping: declarations are processed as they are encountered along an execution path
an interpreter must initialize & maintain a symbol table at run time
What is binding time?
The moment when an attribute is assigned or bound to a name
What is the purpose of a symbol table?
It stores bindings between names and their attributes, managing variable and function references
What is a simple type in programming?
What is the difference between simple types and complex types?
Simple types have no other structure than their inherent arithmetic or sequential structure... complex types are formed by combining simple types or other complex types. allows for more elaborate data structures
What is the difference between a statically typed language and a dynamically typed language
Statically typed language: types are checked at compile time
Dynamically typed language: types are determined at runtime
What is a lexical address and how is it used in static scoping?
Lexical address: consists of a level number and an offset
This addressing system allows for static scoping, because the compiler can use its lexical address to locate it.
What are the basic operations of a symbol table?
Insert a new binding, look up attributes bound to a name, and delete a binding.
what is a scope hole?
A gap in a variable’s visibility within a certain scope, often caused by a local variable shadowing a global one (local variable has the same name as a global variable)
Discuss the different simple types discussed in lecture plz :p
B - O - E - S
Does casting have a purpose in a dynamically typed language?
No, casting does not have a purpose in a dynamically typed language. In dynamically typed languages, types are determined at runtime, so there’s no need to explicitly cast or convert types ahead of time. The language automatically adjusts and interprets the types as needed during execution.
Be able to determine a programs output using either static or dynamic scoping
Static Scoping: Looks at where variables are defined in the code (lexical structure).
- looks for the closest x in the code.
Dynamic Scoping: Looks at the order in which functions are called at runtime (call stack).
- checks the most recent x used when calling function
Define a discriminated union and why it is useful.
A discriminated union includes a tag that indicates the current type stored, making it safer by preventing type mismatches.
What is overload resolution? How does it work?
process of choosing a unique function among many with the same name
expands lookup operation in the symbol table, to perform lookups based not only on the name of the function, but also the number of parameters and their data types
What are subrange types, and what benefits do they provide?
Subrange types are contiguous subsets of a type, enhancing documentation, allowing semantic checks, and potentially using less memory
What is the difference between casting and conversion?
Casting: reinterpreting the memory as a different type (without changing the underlying bit representation)
Conversion: changing the data type (converting from one type to another)
What is name equivalence in type systems?
Name equivalence considers two types the same only if they share the exact name, unlike structural equivalence, which compares internal structure.
How does a symbol table assist with static scoping?
The symbol table stores variable bindings, allowing the compiler to reference variables based on their lexical position in the code.
In what way does dynamic scoping affect the output of a program compared to static scoping? Give output with static vs dynamic
#include <stdio.h>
int x = 1; // Global variable x
char y = 'a'; // Global variable y
void p() {
double x = 2.5; // Local x in function p, shadows global x
printf("%c\n", y); // Prints y
{
int y[10]; // Local y array, shadows global y within this block
}
}
void q() {
int y = 42; // Local y in function q, shadows global y
printf("%d\n", x); // Prints x
p();
}
int main() {
char x = 'b'; // Local x in main, shadows global x within main
q();
return 0;
}
Dynamic scoping allows nonlocal variables to be bound at runtime based on the execution path, potentially altering the program output depending on this path
Output with static:
1
a
Output with dynamic:
98
*
What are the different type constructors discussed in lecture
C - U - A - F - PR
Cartesian Product
Union
Array
Function Type Constructor
Pointer and Recursive Types
Define type conversion and the different types
IE - WN
Converting from 1 type to another (can be built into the system to happen automatically)
Implicit conversion (coercion): inserted by the translator
Explicit conversion (cast): conversion directives are written into code
Widening conversion: target data type can hold all of the converted data without loss of value
Narrowing conversion: conversion may involve a loss of data
How does structural equivalence determine type equivalence for two recursive types, and what challenge does recursion introduce?
Structural equivalence requires that two recursive types have identical structures and type constructors for equivalence. Recursion complicates this by requiring a deep comparison through recursive references, which can be difficult to implement without infinite looping or complex checks.
Explain the difference between a function set and a Cartesian product as type constructors and provide an example of each.
A function set represents all possible mappings from one type to another (e.g., int -> bool), while a Cartesian product is an ordered combination of types (e.g., struct {int, float}). A function set is like all possible functions from int to bool, while a Cartesian product would be like a struct with int and float fields.