March 05, 2001 LE Plan:

BINDING (Section 4.4)
- binding: an association.
- Storage binding: between a variable (name) and a storage object (memory 
area) where the value of the variable will be stored.
- type binding: between a variable(name) and a data type.


static binding: binding that occurs before run time and remains unchanged 
throughout program execution.

dynamic binding: binding that occurs during run time or can change in the 
course of program execution.

binding occurrence: the definition of the identifier.

applied occurrence: appearance of the identifier (uses the binding 
established).


VARIABLES: TYPE BINDINGS
STATIC TYPE BINDINGS
- type specified by a declaration statement.
- explicit declaration: statement in program that lists variable names and 
specifies that are a particular type.
         - implicit declaration: means of associating variables with types 
through default conventions instead of declaration statements. (Ex: in 
FORTRAN, the first letter of an identifier determines its type. 'I'-'N' -> 
INTEGER, otherwise -> REAL)

Note: Declarations vs. Definitions
C, C++:
- declarations: specify type and other attributes but do NOT cause 
allocation of storage.
- definitions: specify attributes and cause storage allocation.


DYNAMIC TYPE BINDING:
- variable bound to type when it is assigned a value in an assignment 
statement.

Advantage: provides a great deal of programming flexibility. (allows for 
generic or polymorphic types)

Disadvantages:
- compiler cannot detect as many errors (Ex: incorrect type of right sides 
of assignments are not detected as errors, instead the type of the left 
hand side is simply changed to the incorrect type.)
- cost:
         - type checking must be done at runtime.
         - every variable must have a descriptor associated with it to 
maintain type.

TYPE INFERENCE
- used in functional languages (ML, Haskell).
- the types of the expressions are determined without requiring the 
programmer to specify the type of the variables: the types are inferred 
from the type of constant in the expression.


VARIABLES : STORAGE BINDINGS
lifetime of a variable: the time during which the variable is bound to a 
specific memory location.

STATIC VARIABLES:
- bound to memory cells before program execution begins and remain bound to 
those same memory cells until program execution terminates.

Advantages:
- History sensitive variables (in a subprogram): retain values between 
separate executions of the subprogram. (Bertram's pseudo-random number 
generator: 2/28)
- Efficiency: all addressing of static variables can be direct.
- No run time overhead for allocation and deallocation of static variables.

Disadvantages:
- reduced flexibility: (ex: if there were only static variables then it 
would not be possible to do recursive subprograms).
- storage cannot be shared: (a program with two subprograms that require 
large unrelated arrays must both allocate memory, so twice as much memory 
is needed -- assuming both are same size)

Programming Language Support:
C, C++, Java: include the "static" specifier on a local variable definition.
FORTRAN I, II, IV: all variables static.
Pascal: no support.


STACK-DYNAMIC VARIABLES:
- variables whose storage bindings are created when their declaration 
statements are elaborated, but whose types are statically bound.
Note: elaboration: refers to storage allocation and binding process 
indicated by the declaration. Takes place when execution reaches the code 
to which the declaration is attached.
- storage allocated from the run time stack.

Advantage: allows for recursion.
Disadvantage: the run time overhead of allocation and deallocation and the 
fact that locals cannot be history sensitive.


EXPLICIT HEAP-DYNAMIC VARIABLES:
- nameless memory cells that are allocated and deallocated by explicit run 
time instructions specified by the programmer.
- storage allocated and deallocated from the heap.
- can only be referenced through pointers or reference variables.
- Since they are bound to a type a compile time, that binding is static. 
But the variables are bound to storage dynamically (during run time).

Advantage: good for dynamic structures.

Disadvantages:
- cost of references to the variables, allocation, and deallocation.
- the difficulty of using pointer and reference variables correctly.

Programming language support:
C++: through new/delete operators.
Java: ALL Java objects are explicit heap-dynamic and accessed through 
reference variables. Implicit garbage collection is used for deallocation.

IMPLICIT HEAP-DYNAMIC VARIABLES
- bound to heap storage only when they are assigned values.
- basically just names that  adapt to whatever they are asked to serve.


Advantage: allow for highest degree of flexibility.

Disadvantages:
- run time overhead of maintaining all the dynamic attributes.
- loss of error detection by the compiler. (same as for dynamic type binding).

Programming Language Support:
- polymorphic types
- generic types in Haskell.



PARAMETER PASSING (Section 8.5)
- the ways that parameters are transmitted to and/or from called subprograms.

CALL BY VALUE (Pass-By-Value):
- the value of the actual parameter is used to initialize the corresponding 
formal parameter, which then acts as a local variable in the subprogram.
- usually implemented by actual data transfer (copy the parameter).

Disadvantages:
- additional storage is needed. (since another copy of data is created)
- overhead of creating the additional storage, and the copying the data to it.



CALL BY VALUE-RESULT (Pass-By-Value-Result):
- the value of the actual parameter is used to initialize the corresponding 
formal parameter, which then acts as a local variable.
- at subprogram termination, the value of the formal parameter is 
transmitted back to the actual parameter.

Disadvantages:
- requires multiple storage for parameters and the time for copying values.
- can be parameter collision: if the procedure is called with the same 
variable as more than one actual parameter. The order that the formal 
parameters are copied back to the actual parameters (at the end of the 
subprogram) determines the value of the variable.



CALL BY REFERENCE (Pass-By-Reference):
- transmits an access path (usually just an address) to the called 
subprogram, which provides the access path to the cell storing the actual 
parameter.

Advantage: efficient: duplicate space is not required, and there is no 
copying of data.

Disadvantages:
- access to formal parameters will probably be slower because one more 
level of indirect addresses is needed then when data values are transmitted.
- inadvertent and erroneous changes may be made to the actual parameter.
- aliases can be created. can have parameter collision (see call by 
value-result).


CALL BY MACRO (Pass-By-Name):
- the actual parameters is textual substituted for the corresponding formal 
parameter in all its occurrences in the subprogram.
- the formal parameter is bound to an access method at the time of the 
subprogram call, but the actual binding to an address or value is delayed 
until the formal parameter is assigned or referenced.

Advantages:
- flexibility for the programmer.
- no environments needed.

Disadvantage: slow relative to all other parameter passing methods.


Examples of Semantic Equivalence with other models:
- if the actual parameter is a scalar variable, then it is equivalent to 
pass-by-reference.
- if the actual parameter is a constant expression, then it is equivalent 
to pass-by-value.

Appears in programming languages as Macros. (but is the cost any more?)