CS代考计算机代写 data structure python Java Fortran c++ javascript c# flex Haskell compiler PowerPoint Presentation

PowerPoint Presentation

Names are used to identify variables, formal parameters, subprograms, and multiple other program constructions.

Names are strings of characters.

Design issues:
Are names case sensitive?
Is the length of a name limited or unlimited?
Which characters are allowed resp. is there a special format for names?
Are special words of the language reserved words or keywords?

Names

Keyword
A word that has a special meaning in certain contexts
Fortran is the only remaining widely used language whose special words are keywords. Examples:
Integer n Declaration of variable n of type integer
Integer = 3 Assignment of 3 to variable Integer
Reserved word
A word that cannot be used as a name
Potential problem:
Large amount of reserved words makes it hard to find proper names. Example: COBOL has more 300 reserved words including some of the most commonly chosen names by programmers (LENGTH, BOTTOM, DESTINATION, COUNT)
Predefined Words
A word with a predefined meaning that can be redefined

Special words

A program variable is an abstraction of a computer memory cell or collection thereof. A variable has usually 6 attributes:
Name
Most variables have a name
Address
Machine memory address associated with the variable
Might be different at different times in the program
Sometimes called l-value
Aliases
Value
Content of the memory cell(s) associated with the variable
Sometimes called r-value

Variables

Type
The type of a variable determines the range of values that the variable can store
Lifetime
The lifetime is the time during which the variable is bound to a specific memory location
Starts when the variable is bound to a cell
Ends when the variable is unbound from that cell
Scope
The scope of a variable is the range of statements in which the variable is visible
The scope rules of a language determine how a name is associated with a variable.

A binding is an association, such as between an attribute and an entity.

The time at which a binding takes place is called binding time.

Some examples:

count = count + 5 (Java statement)

The type of count is bound at compile time
The set of possible values of count is bound at compiler design time
The meaning of the operator symbol + is bound at compile time
The internal representation of the literal 5 is bound at compiler design time
The value of count is bound at execution time with this statement

Concept of Binding

Any binding can be
static
occurs before run time and remains unchanged throughout program execution
dynamic
Occurs during run time or can change during the execution

Binding Attributes to Variables

Static type binding
Explicit declaration
Statement in the program binding a type to a variable
Implicit declaration
A type is associated with a variable by default conventions
First appearance of the variable constitutes its implicit declaration
Type inference
Type of most entities is determined without requiring the programmer to specify types of the variables
Examples: ML, Haskell

area r = 3.14*r*r
Type Bindings

Static variables
Bound to memory cells before program execution starts and remain to be bounded to those cells 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. For example, recursive subprograms with only global variables are impossible
No storage sharing among variables

Storage Binding and Lifetime

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 cells that are allocated and deallocated 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
Loss of error detection at compile time

Static scope
Method of 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 categories of static-scoped languages:
Those in which subprogram can be nested
Creates static scope in subprograms
Ada, Javascript, Fortran 2003, PHP
Those in which subprograms cannot be nested
Any C-based language

Scope

procedure Big is
X : Integer;

procedure Sub1 is
X : Integer
begin
… X …
end;

procedure Sub2 is
begin
… X …
end;

begin
… X …
end;

Static parent

Many languages allow new static scopes to be defined in the midst of executable code via blocks.

void sub() {
int count;
…
while ( …) {
int count;
…
count++;
…
}
…
}
Blocks

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 on 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;

procedure Sub1 is
X : Integer
begin
… Sub2 …
end;

procedure Sub2 is
begin
… X …
end;

begin
… Sub1 … Sub2 …
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 variables takes longer
Reduces the number of parameters in subprograms
Not widely used

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)
Scope and Lifetime

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.

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.
Referencing Environment

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;

Static Scope

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();
}
Dynamic Scope

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 (modification only in one spot)
Static binding of value
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)

Named Constants

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 led to abstract data types, interfaces, and object-orientation.
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., Haskell type Integer
Some languages have unsigned integer types
Most integer types are directly supported by the hardware
Bitwise operations
Twos complement representation

Numeric Types

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

Often two data types float and double
Precision and range
Precision is the accuracy of the fraction part
Range of fraction
Range of exponent

Exponent
Fraction

8 bits
23 bits
Exponent
Fraction

11 bits
52 bits
Sign bit

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 are perhaps the simplest of all types.
Two values: true and false
Introduced in ALGOL 60
Some languages use/allow numeric expressions as conditionals, i.e., C, C++
Could be represented by a single bit but use typically a byte

Boolean 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 code UCS-4 or UTF-32

Character Types

A string is a sequence of characters.

Design issues:
Should strings simply a special kind of character array or a primitive type?
Should strings have static or dynamic length?

Operations on strings:
Assignment
Catenation
Substring reference
Comparsion
Pattern matching

Strings

C and C++
char arrays
String is terminated by character 0
Operations through standard libraries
Inherently unsafe, i.e., strcpy
Fortran 95 and Python
Strings are a primitive type
Relational operators, assignment, catenation, substring reference
Python adds indexing, searching and replacing
Java
String class
Constant strings
StringBuffer class
Changeable strings
Perl, JavaScript, Ruby, and PHP include build-in pattern-matching operations

Related Posts