COSC 2P05: Week 3 Notes

Continued from last week

Storage Binding and Lifetime

Static variables

• Bound to memory before program execution starts and remains to be bounded to those cells until program termination
  • In Java, it will be allocated if the class is loaded, and will remain until program termination
• Usually for global variables; also for subprograms that are history sensitive
• Efficient because of direct addressing, and no allocation and deallocation during run time is required
• Disadvantages
  • Reduces flexibility
    • Example: recursive subprograms with only global variables are impossible
  • No storage sharing among variables

Stack-dynamic variables

• Type is statically bound
• Bound to memory cells when the declaration statement is executed
• Supports recursive subprograms
• Run time overhead for allocation and deallocation

Explicit heap-dynamic variables

• Nameless memory ells that are allocated and decallocated by explicit run time instructions
• Can only be referenced through pointer or reference variables
• Example (C++):

int *intnode;
intnode = new int;
// ...
delete intnode;

Implicit heap-dynamic variables

• bound to heap storage only when they are assigned values
• Example (JavaScript):

highs = [74, 84, 86, 90, 71];

• Highest degree of flexibility by allowing to write highly generic code
• Disadvantages:
  • Run time overhead of maintaining all (dynamic) attributes
  • Los of error detection at compile time

Scope

Static Scope

• Method o binding names to nonlocal variables introduced in Algol 60
• Can be determined statically (hence the name). i.e., prior to execution
• Permits to determine the type of every variable
• Two types of static stoped languages:
  • Those in which subprogram can be nested
    • Creates static stope in subprogram
    • Ada, JavaScript, Fortran 2003, PHP
  • Those in which a subprogram can not be nested
    • Any C-based language

procedure Big is // Static parent Big
	X : Integer; // X is declared
 
	procedure Sub1 is    // |
		X : Integer.     // |
		begin.           // | Subprogram1, with its own scope
		… X ….           // | A new `X` is declared
		end;             // |
 
	procedure Sub2 is.   // |
		begin.           // | Subprogram2, with its own scope
		… X …            // | No `X` declared, use global X
		end;             // |
 
	begin                          // |
	… X …                          // | Which `X` do we use?
	end;                           // | 

Blocks

Many languages allow new static scopes to be defined ain the midst of executable code via blocks (e.g. for blocks, while blocks, etc.)

void sub() {
		int count;
		…
		while ( …) {        // |
			int count;      // |
			…               // | While loop is considered a block
			count++;        // | This code will not run in Java due to 
			…               // | making 2 variables with the same name
		}                   // |
		…
	}

• Problems:
  • Might allow more access to variables and subprograms than necessary
  • Program evolution may result in restructuring, thereby destroying the initial structure

Dynamic Scope

• Based in the calling sequence of subprograms
• Can only be determined at run time
• Used in APL, SNOBOL, early LISP
• Perl and COMMON LISP allow variables to be declared to have dynamic scope

procedure Big is
	X : Integer;        // Global variable

	procedure Sub1 is
		X : Integer     // Local variable
		begin
		… Sub2 …
		end;

	procedure Sub2 is
		begin
		… X …           // "Exposing" X variable from Sub1 to Sub2
		end;

	begin
	… Sub1 … Sub2 ….    // Sub1 uses local, Sub2 uses global
	end;

• Has a profound effect on programming
  • Correct attributes of nonlocal variables cannot be determined statically
  • References to a name is not always a reference to the same variable
  • Local variables can be modified externally
  • Programs are difficult to read
  • Accessing the variables takes longer
  • Reduces the number of parameters in subprograms
• Not widely used

Scope and Lifetime

Sometimes the scope and lifetime of a variable seem to be related.

void myMethod() {
	int n;
	// ... (no other method called)
}

• Scope of n:
  • From the declaration to the end of myMethod (spatial concept)
• Lifetime of n:
  • Time beginning when the method is entered and ending when execution of the method terminates (temporal concept)

void printHeader() {
	// ...
}
 
void compute() {
	int sum;
	// ...
	printHeader();
	// ...
}

• Scope of sum:
  • From the declaration to the end of compute
• Lifetime of sum:
  • Time from when compute is called, including the time when printHeader is executed, until compute terminates.

Referencing Environment

The referencing environment of a statement is the collection of all variables that are visible in the statement.

The referencing environment heavily depends on the scope of the programming language, i.e., it differs between static and dynamic scope.

Static Scope Example

procedure Example is
	A, B : Integer;
	procedure Sub1 is
		X, Y : Integer;
		begin
			…		// X, Y of Sub1, A,B of Example
		end;
	procedure Sub2 is
		X : Integer;
		procedure Sub3 is
			X : Integer;
			begin
				…	// X of Sub3, A, B of Example
			end;		   (X of Sub2 is hidden)
		begin
			…		// X of Sub2, A, B of Example
		end;
	begin
		…			// A, B of Example
	end;

Dynamic Scope Example

void sub1() {
	int a, b;
	…		// a, b of sub1, c of sub2, d of main
}			//  (c of main and b of sub2 are hidden)
void sub2() {
	int b, c;
	…		// b, c of sub2, d of main
	sub1();	//  (c of main is hidden)
}
void main() {
	int c, d;
	…		// c, d of main
       sub2();
}

Static Scope Example 2

procedure main is
    x,y,z : Integer;
    
    procedure sub1 is
        x,z : Integer;
        begin
            x := 3;
            z := 9;
            sub2();
            x := x + y + z;
            print(x)
        end

    procedure sub2 is
        x : Integer;
        begin
            x := 4;
            y := x * z + 1
        end
begin
    x := 0;
    y := 2;
    z := 4;
    sub1()
end

End of lecture 1

You do not need to draw out the whole table, but it it good as you can get most marks from showing your work vs just writing an answer.

Dynamic Scope Example 2

procedure main is
    x,y,z : Integer;
    
    procedure sub1 is
        x,z : Integer;
        begin
            x := 3;
            z := 9;
            sub2();
            x := x + y + z;
            print(x)
        end

    procedure sub2 is
        x : Integer;
        begin
            x := 4;
            y := x * z + 1
        end
begin
    x := 0;
    y := 2;
    z := 4;
    sub1()
end

Named Constants

A named constant is a variable that is bound to a value only once.

• Useful aid to improve readability and reliability
• Can be used to parametrize programs (modifications only in one spot)
• Static binding of issue
  • Only previously named constant, constant values, and operators are allowed in assigning a value to the named constant (FORTRAN)
• Dynamic binding of value
  • Also variables are allowed in assigning a value to the constant (C++, Java)
• C++ allows static binding (const) or dynamic binding (readonly)

Data Types

A data type defines a collection of data values and a set of predefined operations on those values

• Early languages (pre Fortran 90) had only a few data structures. More complex data had to be implemented
• COBOL was the first language that allowed more data types to be defined by the user
  • e.g. arbitrary decimal data types, records
• ALGOL 68 introduced a new approach by providing a few basic types and flexible structure-defining operators that allow the programmer to design a data structure for their need
• Later, that idea lead to abstract data types, interfaces, and object-orientation

Numeric Data Types

Most early programming languages had only numeric data types.

Integer

• Most common primitive numeric data type
• Languages often support different sizes
  • e.g. in Java, we have byte, short, int, and long
• Some languages have unlimited integers
  • e.g. in Haskell, type Integer
• Some languages have unsigned integer types
• Most integer types are directly supported by the hardware
• Bitwise operations
• Twos complement representation

Floating-point

• Model real numbers
  • Approximation, not precise value
  • Loss of accuracy through arithmetic operation
• Represented by fraction and exponent
  • IEEE Floating-Point Standard 754
    • 1 sign bit, 8 exponent bits, 23 fraction/mantissa bits
    • 1 sign bit, 11 exponent bits, 52 fraction/mantissa bits
• Often two data types
  • float and double
• Precision and range
  • Precision is the accuracy of the fraction part
  • Range of fraction
  • Range of exponent

Decimal

• Fixed number of decimal digits
• Primary data types for business data processing
• Usually stored by using binary codes for decimal digits
  • Binary Coded Decimal (BCD)
  • Precise representation
  • Wasteful representation
    • 1 or 2 digits per byte

Boolean Types

Boolean types are the simplest of all types.

• Two values: true or false
• Introduced in ALGOL 60
  • Previously used a system like: if x > 5 GOTO place
• Some languages use/allow numeric expressions as conditionals
  • e.g. C, C++
• Could be represented by a single bit but use typically a byte
  • 8 booleans could fit in a byte
  • Typically use a full byte because it is easier to get a byte than a single bit

Character Types

Character data are stored as numeric codings

ASCII

American Standard Code for Information Interchange

• 7-bit encoding allowing an additional bit for parity

ISO 8859-1

• 8-bit encoding

Unicode

• 4 byte character codes UCS- or UTF-32

Strings

A string is a sequence of characters.

Design issues:

• Should strings simply be a special kind of character array or a primitive type?
• Should strings have static or dynamic length?

Operations on strings:

• Assignment
• Catenation
• Substring reference
• Comparison
• Pattern matching

Strings (C++)

• char array
• String is terminated by character 0
• Operations through standard libraries
  • Inherently Unsafe (e.g. strcpy)

Strings (Fortran 95 and Python)

• Strings are a primitive type
• Relational operators, assignment, catenation, substring reference built in
• Python adds indexing, searching and replacing

Strings (Java)

• String class
  • Constant strings
• StringBuffer or StringBuilder classes
  • Changeable strings

Strings (Perl, JavaScript, Ruby, PHP)

• include built-in pattern matching operations (regex)