Untitled 2
Binding and typing and namespaces
A binding is an association between an entity and an attribute, such as between a variable and its type or value, or between an operation and a symbol
Variable scope Be able to identify both static and dynamic scope
Variable Scope is the range of statements in which the variable is visible | A variable is visible in a statement if it can be referenced or assigned in that statement | Static scoping is when the scope of a variable is determined prior to program execution and is unchanged throughout (can be located prior to execution) | Dynamic scoping is when the scope is determined at run time and can change during execution
Basic types and their implementation
The type of a variable determines the range of values the variable can store and the set of operations that are defined for values of the type | Types tell the compiler and the CPU how to interpret the ones and zeros in memory | The type dictates how much memory to allocate and specifies how data should be interpreted
Know implementation of arrays
row-major order and column-major order are methods for storing multidimensional arrays in linear storage such as random access memory
Variables=(name,address,value,type,lifetime,scope)
A name is a string of characters used to identify some entity in a program (not all variables have names) | The address of a variable is the machine address with which it is associated (a variable can have different addresses at different places in program, called l-value – left assignment) | The value of a variable is the contents of the memory cell(s) associated with the variable (called r-value, right side of assignment) | The type of a variable determines the range of values the variable can store and the set of operations that are defined for values of the type | The lifetime of a variable is the time during which the variable is bound to a specific memory location | The scope of a variable is the range of statements over which the variable is visible
Aliases, binding and binding times
Aliases – two or more variables bound to same storage address – negative effect on readability but difficult to eliminate entirely from a language, created via points, reference variables, C and C++ unions
Binding – the association of attributes with program entities, i.e – between a variable and its type value, operation and a symbol, Static (before run time – C) and dynamic (occurs during execution – JavaScript, python)
The time at which a binding takes place is called binding time
Bindings can take place at: Language design time, language implementation time, compile time, load time, link time, run time
Names: case-sensitivity, length, style (_ vs. camel), reserved or not
Name length – Fortran 95 – 31 characters, C99 – no length limitation (first 63 significant), Java,C#,Ada no length limit + all significant
_ notation – all words separated by _, largely replaced by camel notation (my_stack) | Camel notation – all words capitalized except first (myStack) | Case-sensitivity – uppercase and lowercase letters are treated as different characters and result in distinct names (Utilized by many languages, notably the C based languages (C, C++, Java, C#, etc.) , disadvantage: lower readability since similar looking names can have completely different meanings | Reserved word – special word of a programming language that is prohibited from being used as a name, Drawback – there may be too many reserved words, lowered writability (COBOL has 300)
Addresses can vary (think stack-dynamic and redeclarations); meaning of l-value
L-value – address of a variable, named so because the address is what is required when the name of a variable appears in the left side of an assignment
Type as range of values and applicable operations; abstract vs. physical memory cells
int in Java – specifies a value range of -2147483648 to 2147483647 and arithmetic operations | Physical memory cells are byte size, with one byte having eight bits. This is too small for most program variables. | Abstract memory cells have the size necessary by the variable with which it is associated (memory cell = abstract memory cell)
Binding times: language-design, language-implementation, compile-time, link/load/run-time
Binding time – time when binding takes place
Can occur at: Language design time – bind operator symbols to operations, Language implementation time – bind floating point type to a representation, Compile-time – bind a variable to a type in C or Java, Link/load time – bind a C or C++ static variable to a memory cell, Run-time – bind a non-static local variable to a memory cell
Static vs. dynamic; physical mapping (segmentation/paging etc.) abstracted away…
Physical binding of a variable to a storage cell is complex, because page or segment of the address space in which the cell resides may be moved in and out of memory many times during program execution. | Static binding – occurs before run time begins and remains unchanged throughout program execution | Dynamic binding– occurs at run time and can change in the course of a program execution
Understand explicit and implicit static type binding
Explicit declaration – statement listing variable names and specifying their particular type (Like casting a type to another. Ex: float a = 4.20; int b = (int)a;) | Implicit declaration – use default conventions to associate variables with types (Done by compiler, interpreter, language processor. Ex: float a = 4.20;)
Distinguish declaration from definition
Declaration – tells compiler the name of the variable, type of value and initial value (int f;) | Definition – where variable gets stored(memory gets allocated) int f(int a) { return a; }
Understand an example of dynamic type binding
dynamic any;
Four categories of storage binding: static, stack-dynamic, explicit and implicit heap-dynamic
Static variables – bound to memory cells before execution begins and remain bound to the same memory cells until termination | Stack-dynamic variables – storage bindings are created at the same time as the declaration statements are elaborated(binding process and storage allocation); types are statically bound | Explicit heap-dynamic variables – nameless/abstract memory cells allocated and deallocated by explicit run-time instructions written by programmer | Implicit heap-dynamic variables – bound to heap storage only when assigned values
History/structural sensitivity of static variables; lifetime
Sometimes it is convenient to have subprograms that are history sensitive. (Such a subprogram must have local static variables) | When it may be useful: (History sensitive variables may be useful in data manipulation subprograms, where some operation is performed on a variable, and the function exits, then the function is called again. This way, the function doesn’t have to take the variable as a parameter, but only to return it.)
Relationship of scope to stack-dynamic lifetime
Static scope is textual and lifetime is a temporal concept.
Advantages and disadvantages of explicit heap-dynamic variables
Advantages –provides a convenient way to build data structures | Disadvantages – cost of references to variables, complexity of storage management
Implicit heap-dynamic management; garbage collection
Languages like Java have no way of explicitly destroying a heap dynamic object; relies on implicit garbage collection
Static type checking, coercion and dynamic type checking (think virtual)
Static type checking – Types checked before run-time | Dynamic type checking – Types checked on the fly, during execution | Coercion – automatic conversion of a data type to another (implicit type conversions)
Strong typing examples and nearly strong typing; advantage and disadvantage
Language is strongly typed if type errors are always detected, requires that the types of all operands can be determined either at compile time or run time | Java and C# are nearly strongly typed. No implicit ways type errors can go undetected
Type compatibility and type equivalence (name vs. structural)
Name type equivalence – two variables have equivalent types if they are defined in the same declaration or declarations that use same type name | Structure type equivalence – two variables have equivalent types if their types have identical structures.
Static scope rules and static ancestry; follow an example of name-resolution using scope; application to blocks
STATIC SCOPE RULES: 1. Correct declaration is found by first searching declarations of subprogram 2. If no declaration found for var, search continues in declarations of subprogram (STATIC PARENT) that declares current subprogram 3. Undeclared var error is shown if parents of parents (STATIC ANCESTORS) has no declaration
Hiding possibilities of scope and evaluation of this
A declaration for a variable effectively hides any declaration of a variable with the same name in the larger enclosing scope.
Problems with static scope include forcing programs into unusual configurations
Allows more access to both subroutines and variables than is necessary. Encouraged to use far more globals than necessary. May not reflect underlying conceptual design.
Dynamic scope rules and dynamic ancestry; follow an example of name-resolution given a sequence of calls
Referencing environments (know definition) (just another way of capturing scope)
Referencing environment – collection of all variables that are visible in the statement.
Primitive data types vs. user-defined data types
User defined types improve readability and modifiability, allows for meaningful names for types. | Data types that are not defined in terms of other types are called primitive data types.
Basic information about these data types:
Integer,Floating-point – model real numbers, Decimal – store fixed number of decimal digits w/ implied decimal point, Boolean -true/false, Character – ASCII (32bit Unicode in Fortran),Character strings – array or built-in or object, null-termination and associated errors, regular expressions for pattern matching – Character strings are static or dynamic length and associated bookkeeping, three styles of storage management for dynamic
What is an enumeration type? Know the three design issues on p. 259
An enumeration type is a type in which all the possible values, which are named constants, are provided/enumerated in the definition. Example: enum meats {Beef, Pork, Chicken, Turkey, Veal, etc…} The enum type is an ordinal value which assigns a number value by order to identifiers in its list
Three design issues: 1.Is an enumeration constant allowed to appear in more than one type definition and how is that checked? 2. Are enumeration values coerced to integer? 3. Are any other types coerced to an enumeration?
What are subrange types? How do they differ from derived types in terms of type checking?
Know the points made in section 6.4.3
Enumeration types can provide advantages in both readability and reliability. 1. No arithmetic operations are legal on enumeration types 2. No enumeration variable can be assigned a value outside its defined range (Because C treats enum like integers, it does not provide the 2 advantages above)
Know the design issues for array types on p. 263
Primary design issues specific to arrays: 1. What types are legal for subscripts? 2.Are subscripting expressions in element references range checked? 3. When are subscript ranges bound? 4. When does array allocation take place? 5. Are ragged or rectangular multidimensional arrays allowed, or both? 6. Can arrays be initialized when they have their storage allocated? 7. What kind of slices are allowed, if any?
Why does Fortran choose to use the same syntax for array indexing as for function calls?
An array access is a mathematical function. Prof. stated that, at the time, keyboards did not have square brackets [ ]
What is involved in subscript range checking? Must it be done? Do all languages do it?
How is array initialization handled in different languages?
What is a static array?
A static array is one in which the subscript ranges are statically bound and storage allocation is static (done before run time), Advantage: efficiency (no dynamic allocation/deallocation), Disadvantage: storage for the array is fixed for the entire execution time of the program
What is a fixed stack-dynamic array? What is an advantage of using them?
A fixed stack-dynamic array is one in which the subscript ranges are statically bound, but the allocation is done at declaration elaboration time during execution, Advantage: space efficiency, Disadvantage: requires allocation/deallocation
What is a stack-dynamic array?
A stack-dynamic array is one in which the binding subscript ranges and storage allocation are bound at run time
What is a fixed heap-dynamic array?
A fixed heap-dynamic array is similar to a fixed stack-dynamic array when it comes to the subscript ranges and storage bindings being fixed after storage is allocated. Differences are that the subscript ranges and storage bindings are done when the user program requests them during execution, and the storage is allocated from the heap, rather than the stack, Advantage: flexibility, Disadvantage: allocation time from the heap (longer than the stack)
What is a heap-dynamic array? (In all of these, what are the binding times of indices and storage?)
A heap-dynamic arrayis one in which the binding of subscript ranges and storage allocation is dynamic and can change any number of times during the array’s lifetime, Advantage: flexibility,Disadvantage: allocation/deallocation takes longer and may happen many times during execution of the paragraphs
How are declare blocks in Ada used with stack-dynamic arrays on p. 266
What keywords or function calls are used in C/C++ for allocation and deallocation of fixed heap-dynamic arrays?
The standard C library functions malloc and free, which are general heap allocation and deallocation operations, can be used for C arrays. | C++ uses the operators new anddelete to manage heap storage. An array is treated as a pointer to a collection of homogeneous storage cells, where the pointer can be indexed (p. 253)
How are arrays handled in Java?
Non-generic arrays are fixed-heap dynamic. Java allows initialization during allocation. Java supports jagged arrays. All elements required to be the same type.
Be familiar with the various initialization methods in section 6.5.5 What kinds of operations are typical for arrays?
Array initialization in section 6.5.4…
C – Integer array – int list [] = { 4 , 5, 6 }; | Character array (string) – char phrase [] = “CS320 group is the best!” ;
C and C++ – String array – char *names [] = {“Bob”, “laptop”, “Django”};
Java – String array – String [] names = {“Bob”, “Jake”, “ETC”};
Operations typical for arrays: assignments, catenation, comparison for equality or inequality , and slices (pg 255)
What is a slice of an array (give a specific example)?
A slice is some substructure of an array; nothing more than a referencing mechanism. Slices are only useful in languages that have array operations
(python ex)
vector = [5,11,252,41,78,977] #index starts at 0
vector[2:4]
>>[252, 41]
Given a two-dimensional array, show how the address of an element is computed from the indices and element type
Row major – A[i][j] = A + i * numCols + j (assuming the index starts at 0) | Column major – A[i][j] = A + j * numRows + i (as above)
What are row-major and column-major order? Be able to show the difference in an example
Row-major order – the elements of the array that have as their first subscript the lower bound value of that subscript are stored first, followed by the elements of the second value of the first subscript, and so forth. If the array is a matrix, it is stored by rows. For example, if the matrix had the values:
3 4 7
6 2 5
1 3 8
it would be stored in row major order as 3, 4, 7, 6, 2, 5, 1, 3, 8
Column-major order – the elements of an array that have as their last subscript the lower bound value of that subscript are stored first, followed by the elements of the second value of the last subscript, and so forth. If the array is a matrix, it is stored by columns. If the example matrix were stored in column major order, it would have the following order in memory: 3, 6, 1, 4, 2, 3, 7, 5, 8
What is an associative array?
Associative array – an unordered collection of data elements that are indexed by an equal number of values called keys. (Another word, user-defined indexes)
%hi_temps = (“Mon” => 77, “Tue” => 79, “Wed” =>65, …);
$hi_temps{“Wed”} = 83;
Design issue: form of references to their elements