advantage / disadvantage fixed char string length
- Aids writability.
- Efficient at run-time if strings have static length.
- With static length, only compile-time string information (length and address) is needed.
- No run-time info needed.
advantage / disadvantage limited dynamic char string length
MAY need run-time information (but not in C, C++) containing max length, current len, address.
advantage / disadvantage dynamic char string length
- WILL need run-time info.
- Costly at run-time.
- Is it worth the cost?
- Memory allocation/deallocation is biggest implementation problem.
Type in which the range of possible values can be easily associated with a set of positive integers.
Type in which all possible values, which are named constants, are listed in the definition.
An ordered contiguous subsequence of an ordinal type.
What are 2 advantages of having subrange data-type in a language?
- Improves Readability -- clear to the reader that certain variables can store only certain range of values.
- Reliability -- Assigning a value to a subrange variable that is outside the specified range is detected as an error.
static binding of arrays
- Bound and storage allocated before run-time.
- Efficient (no dynamic allocation).
- Used in: C, C++ arrays declared STATIC
fixed stack-dynamic binding of arrays
- Subscript ranges are statically bound, but the allocation is done at declaration time.
- Space efficient, but run-time allocation/deallocation required.
- Used in: C, C++ arrays declared without STATIC but with constant size.
stack-dynamic binding of arrays
- Ranges dynamically bound & storage allocation is dynamic.
- Used in Ada.
- Flexible -- size of array need not be known until array is to be used.
fixed heap-dynamic binding of arrays
- Storage binding dynamic but fixed after allocation (i.e. binding is done when requested and storage is allocated from the heap, not the stack).
- Used in: Java (all non-generic arrays), C, C++ declared with non-constant size or created with "new".
- Also used in C# ArrayList arrays or arrays created with "new".
heap-dynamic binding of arrays
- Binding of subscript ranges & storage allocation is dynamic and can change at any time.
- Flexible (arrays can grow or shrink during execution).
What is an array SLICE, and why is it useful?
- A way to reference some substructure of an array as an array.
- Only useful in languages that have array operations.
What's an array access function?
Maps subscript expressions to an address in the array.
ROW MAJOR order
- Ordered in memory by rows (all elements of each row in adjacent memory locations).
- Used in most languages.
COLUMN MAJOR order
- Ordered by columns (all elements of each column in adjacent memory locations).
- Used in Fortran.
What's an associative array, and what kind of data is well suited for it?
- An unordered collection of data elements that are indexed by an equal number of values called KEYS.
- Associative arrays are ideal when data is "paired", for example employee names and ID numbers.
What's a record?
A possibly heterogeneous aggregate of data elements in which each individual element, called a field, is identified by name.
What's a field?
Each individual element in a record.
What's an elliptical reference?
Allow leaving out record names as long as the reference is unambiguous.
What's a tuple?
A data type similar to a record, except the elements are not named.
What's a list?
A sequence of values.
LIST COMPREHENSION in Python
- Based on mathematical sets & functions.
- A function is applied to each of the elements of a given list and a new list is constructed from the results.
A type whose variables are allowed to store different type values at different times during execution.
No language support for type checking a union.
Language supports type checking a union, using a type indicator called a DISCRIMINANT.
A pointer may point to a heap-dynamic variable that has been deallocated.
lost heap-dynamic variable
An allocated heap-dynamic variable may no longer be accessable to a program if no pointers point to the variable.
Why do essentially all languages have pointers?
Pointers or references are necessary to handle dynamic data structures (like linked lists), so we can't design a language without them.
- Every heap-dynamic variable includes additional memory, called a tombstone, that is itself a pointer to the heap-dynamic variable.a
- The actual pointer variable used by the program really points to the tombstone.
- When heap-dynamic variable deallocated, tombstone remains but is set to NIL. Subsequent references to this NIL tombstone through dangling pointers can be detected as a run-time error.
- Problem: tombstone costs both execution speed (one more level of indirection) and space (tombstones never deallocated).
LOCKS & KEYS
- Each pointer is a (key,address) pair. The integer key is stored in each heap-dynamic variable when it is allocated and in the pointer variable.
- When heap-dynamic variable is deallocated, its copy of the key is set to an illegal key value.
- When pointers are assigned to each other, both the key and address are copied.
- Each reference using any pointer is checked to insure the two keys match. If not, a run-time error is generated.
What is GARBAGE COLLECTION?
The process of detecting all garbage memory blocks.
What are two garbage collection strategies?
- REFERENCE COUNTER (a.k.a. EAGER) garbage collection strategy.
- MARK-SWEEP (a.k.a. LAZY) garbage collection strategy.
What is a strongly typed language?
One in which type errors are always detected, either at compile-time or run-time.
What's a function SIDE-EFFECT?
If a function changes any non-local variable.
What is REFERENTIAL TRANSPARENCY?
If any two expressions in the proram that have the same value can be substituted for one another anywhere in the program, without affecting the action of the program.
What is SHORT CIRCUIT evaluation?
A speed-up technique used by compilers to evaluate an expression without evaluating all the operands or operators.
What is COERCION?
Implicit type-conversion of operands (done by the compiler).
What is widening coercion?
Converts to a type that can include at least approximations to all the values of the original type. For example, int to float, but not float to int.
What is narrowing coercion?
Converts an object to a type that cannot include all of the values of the original type. For example, float to int.
What problem did STRUCTURED PROGRAMMING fix?
Importance of control statements in producing "understandable programs".
What's the purpose of a multiple selection statement?
Generalization of two-way selection statement to allow selection among any number of clauses.
What are the language design issues for multiple selection?
- Is execution flow through the structure restricted to include just a single selectable segment? (i.e. is there an implicit branch at the end of each selectable segment?)
- What is done if the control expression has no specified clause? (i.e. is there a "default" clause?)
- What type of control expression(s) are allowed?
- How are selectable segments specified?
- How are case values specified?
What are the 4 ways to control an iteration (Loop)?
- Counter controlled
- Logic controlled
- User controlled
- Data controlled.
What are the design issues for counter controlled loops?
- What is the type and scope of the loop variable?
- Can the loop variable be changed in the loop body?
- Are loop parameters evaluated once or at every iteration?
- Is branching into the loop body allowed?
What's a pre-test loop?
Test at beginning of loop.
What's a post-test loop?
Test at end of loop.
What C,C++, Java statements allow user controlled loops?
BREAK & CONTINUE
How does data controlled iteration work with an ITERATOR?
Returns the next element in the data structure in some order.
What are three pre-defined iterators in PHP or Ruby?
What kind of "abstraction" do subprograms provide.
What is a DEFINITION?
Describes the interface and the actions of the subProgram.
What is a DECLARATION?
Provides the protocol but not the body of a subprogram. A.k.a. "Prototypes" in C and C++.
What is a HEADER?
The first part of the definition that includes the name, kind of subProgram, formal parameters.
What is a SIGNATURE?
The number, order, and types of a subProgram's parameters. (a.k.a parameter profile) --
What is a PROTOCOL?
A subProgram's signature and, if it is a function, its return type.
What is a formal parameter?
A dummy variable listed in the header and used in the subprogram.
What is an actual parameter?
- Represents a value used in the subprogram call statement.
- It is assigned to a formal parameter.
What is an advantage and disadvantage of keyword parameters?
- Advantage: Parameters can appear in any order, avoiding parameter correspondence errors.
- Disadvantage: Programmer must know the formal parameter's name.
static vs stack-dynamic local variables
- Stack-dynamic allows recursion but subprogram cannot be history sensitive using only stack-dynamic variables.
- Static allows history sensitive, but no recursion.
What are 3 semantic modes of parameter passing?
- In mode (pass-by-value)
- Out mode (pass-by-result)
- InOut mode.
Know the 3 ways to implement InOut mode?
In C, C++, What information must be included in the formal parameters of multi-dimensional arrays, and why is this needed?
- In C, C++, the programmer must include the declared sizes of all but the first subscript in the formal parameter.
- This info is needed for the compiler to be able to construct the access function of the parameter.
What is done at run-time in Ada, C#, Java that provides the above information to subprograms without making the programmer specify it?
- Declared array size is part of array's runtime type descriptor.
- Arrays are objects.
- Use the environment of the call statement that calls the passed subprogram.
- Most natural for dynamic-scoped languages.
- Use the environment of the definition of the passed subprogram.
- Most natural for static-scoped languages.
Use the environment of the call statement that passed the subprogram as an actual parameter.
How do C, C++ implement indirect subprogram calls?
Call a function through a pointer.
How does C# implement indirect calls?
What is an OVERLOADED subprogram?
Has the same name as another subprogram in the same referencing environment.
What is a GENERIC subprogram?
- a.k.a Polymorphic subprogram
- Takes parameters of different types.
- Each call of the subprogram with particular data types for the arguments generates a different ACTIVATION (a.k.a. specialization) of the subprogram.
AD HOC POLYMORPHISM
Overloaded subprograms provide this type of polymorphism
- Usually provided in languages with object-oriented support.
- It means a variable of type T can access any object of type T or any type derived from T.
Subprogram takes generic parameters (a.k.a. "typename" parameters in C++) that are used to describe the data types of the parameters of the subprogram.
What's a CLOSURE?
A subprogram and the referencing environment where it was defined.
How does a CLOSURE work?
- Referencing environment needed if subprogram can be called from any arbitrary place in the program.
- A static-scoped language that doesn't permit nested subprograms doesn't need closures.
- Closures only needed if a subprogram can access variables in nesting scopes and it can be called from anywhere.
- To support closures, an implementation may need to provide whole program lifetime to some variables, because a subprogram may access a nonlocal variable that is normally no longer alive.
How do COROUTINES work?
- A coroutine call is named a RESUME.
- First resume of a coroutine is to its beginning.
- Subsequent calls enter at the point just after the last executed statement of the coroutine.
- All the local variables in the coroutine retain their values from the last execution.
- Coroutines repeatedly resume each other.
What is a SubProgram LINKAGE?
The call and return operations of a language.
What's in an activation record?
- stack-dynamic local variables
- return address
- dynamic link
- Saves the old EP as the dynamic link and creates a new value.
- Allocates local variables in the activation record.
- moves values of out or inout mode parameters to actual parameters.
- make return value accessable to caller.
- restore stack pointer by setting it to EP-1.
- set EP to the old dynamic link.
- restore execution status of caller.
- transfer control (back to caller's return address)
What is a block?
User-specified local scopes for variables.
What are two ways to implement blocks?
- Treat blocks as subprograms with no parameters that are always called from the same location. Create an activation record every time the block is executed.
- Since maximum storage for a block can be statically determined, statically allocate the space for variables within the block after the local variables in the activation record of the enclosing subprogram.
DEEP access to nonlocal variables
- Reference nonlocal stack-dynamic variables in a dynamic-scoped language by searching through the activation records of the other subprograms that are currently active, beginning with most recently activated.
- Similar to accessing nonlocal variables in static-scoped language except dynamic chain is followed rather than the static chain.
- Every activation record must include variable names.
- ADV/DISADV: fast subprogram linkage, but references to nonlocals, especially distant ones, are slower.
SHALLOW access to nonlocal variables
- Eliminate searching activation records by maintaining a table of information about all the variables.
- Must add new (local) variables to the table at each subprogram call, and remove them on return.
- ADV/DISADV: fast access to nonlocal variables, especially distant ones, but subprogram linkage is slower due to updating the table at each call and return.
What are two ways to implement shallow access?
- Central table of nonlocal variable names with ACTIVE bit. Table offset of each nonlocal reference is determined at compile time.
- Table containing a separate stack for each variable name. Push each time the name is declared. Always reference top of stack.