Programming Languages
CSCI-GA.2110-003 Fall 2020
Binding, scopes, and control structures
Names
What can we name?
■ mutable variables
■ values
■ functions
■ types
■ type constructors (e.g., list or vector)
■ classes
■ modules/packages
■ execution points (labels)
■ execution points with environment (continuation)
2 / 34
Binding times
A binding is an association of two things. The first is usually a name. Binding time is the time at which the association is made.
Binding times:
■ Language design time: semantics of most language constructs
■ Language implementation time: implementation dependent semantics
■ Compile time
■ Link time
■ Run time
Static means before run time, dynamic means during run time.
3 / 34
Binding in C++
1 class Base {
2 public:
3 virtual void value() { cout << "base␣class"; return; }
4 };
5 class Child : public Base {
6 public:
7 virtual void value() { cout << "child␣class"; return; }
8 };
9
10 int main() {
11 Base x;
12 Child y;
13 x=y;
14 x.value(); // static binding
15 Base *xp = new Child();
16 Base &xr = y;
17 xp->value(); // runtime binding
18 xr.value(); // runtime binding
19 return 0;
20 }
4 / 34
Scope and lifetime
Scope: the region of program text where a binding is active.
Lifetime: the period of time between the creation of an entity and its destruction.
Note that these talk about two different things. Scope is a place (or many places), whereas lifetime is a time span.
5 / 34
Lifetimes
For objects residing in memory, there are typically three areas of storage, corresponding to different lifetimes:
■ static objects: lifetime of entire program execution ◆ globals, static variables
■ stack objects: from the time the function or block is entered until the time it is exited
◆ local variables
■ heap objects: arbitrary lifetimes, not corresponding to the entrance or
exit of a function or block
◆ dynamically allocated objects, e.g., with new
6 / 34
Scopes
Two major scoping disciplines:
■ static: binding of a name is given by its declaration in the innermost enclosing block
◆ Most languages use some variant of this
◆ Closest nested scope rule usually applies.
■ dynamic: binding of a name is given by the most recent declaration encountered at runtime
◆ Used in Lisp, Snobol, APL
7 / 34
Scoping example
var x = 1;
function f () { print x; } functiong(){varx=10; f();} function h () { var x = 100; f(); } f(); g(); h();
Scoping Output
Static 1 1 1 Dynamic 110100
8 / 34
Closest nested scope & hiding
program A;
var I:integer;
K:char;
procedure B; var K:real;
L:integer;
procedure C; var M:real; begin
(*scope A+B+C*) end;
(*scope A+B*) end;
(*scope A*) end.
9 / 34
Static scoping variations
What is the scope of x? {
■ ■ ■
C++, Ada: statements2
Legacy C, Pascal: statements2 (but statements1 not allowed) Javascript: entire block
}
statements1; var x = 5; statements2;
10 / 34
Memory Allocation
■ Static: allocated once at compile time (usually in protected memory.) Usually include:
◆ Strings, constants, static variables.
■ Stacks: allocated in frames on a first-in last-out basis. Frames usually
store:
◆ Actual parameters
◆ Temporaries
◆ Local variables
◆ Bookkeeping information
◆ Return address
■ Heap: allocated from main memory according to an allocation policy.
◆ First-fit ◆ Best-fit
11 / 34
Overloading
Overloading is a form of ad-hoc polymorphism whereby methods and operators can have several meanings depending on context.
■ Functions: normally distinguished by the function signature.
■ Custom memory allocation (C++: new and placement-new) ■ Operators
◆ Some languages can define new operators (ALGOL 68, Fortran, F#, Smalltalk)
◆ And others can’t. (ML, Prolog)
◆ Some languages will overload only a limited set (C++, Pascal, C#)
◆ And others don’t support overloading at all. (C, Java, JavaScript,
BASIC)
Do not confuse with a similar but distinct concept of coercion.
12 / 34
Control Structures
A control structure is any mechanism that departs from the default of straight-line execution.
■ selection
◆ if statements
◆ case statements ■ iteration
◆ while loops (unbounded)
◆ for loops
◆ iteration over collections
■ other
◆ goto
◆ call/return
◆ exceptions
◆ continuations
13 / 34
The Infamous GoTo
■ In machine language, there are no if statements or loops.
■ We only have branches, which can be either unconditional or conditional
(on a very simple condition).
■ With this, we can implement loops, if statements, and case statements. In
fact, we only need
1. increment
2. decrement
3. branch on zero
to build a universal machine (one that is Turing complete).
■ We don’t do this in high-level languages because unstructured use of the goto can lead to confusing programs. See “Go To Statement Considered
Harmful” by Edgar Dijkstra.
14 / 34
Selection
■ if Condition then Statement – Pascal, Ada
■ if (Condition) Statement – C/C++, Java
■ To avoid ambiguities, use end marker: end if, “}”
■ To deal with multiple alternatives, use keyword or bracketing:
if Condition then Statements
elsif Condition then Statements
else Statements
end if;
15 / 34
Nesting
if Condition1 then
if Condition2 then
Statements1 end if;
else Statements2
end if;
16 / 34
Statement Grouping
■ Pascal introduces begin-end pair to mark sequence
■ C/C++/Java abbreviate keywords to { }
■ Ada dispenses with brackets for sequences; keywords for the enclosing
control structure are sufficient
for J in 1..N loop … end loop
◆ More writing but more readable
■ Another possibility – make indentation significant (e.g., ABC, Python,
Haskell). Python example:
def fib(n):
print ’n␣=’, n if n > 1:
return n * fib(n – 1) else:
print ’end␣of␣the␣line’ return 1
17 / 34
Short-circuit evaluation
ifx/y>5thenz:= … –whatify=0? ify/=0andx/y>5thenz:= …
But binary operators normally evaluate both arguments. Solutions:
■ a lazy evaluation rule for logical operators (Lisp, C)
C1 && C2 // don’t evaluate C2 if C1 is false
C1 || C2 // don’t evaluate C2 if C1 is true ■ a control structure with a different syntax (Ada)
— don’t evaluate C2 if C1 and then C2 then — if C1 is false
ifC1orelseC2then — ifC1istrue
18 / 34
Multiway selection
Case statement needed when there are many possibilities “at the same logical level” (i.e., depending on the same condition)
case Next_Char is
when ’I’ when ’V’ when ’X’ when ’C’ when ’D’ when ’M’ when others
=>Val:=1;
=>Val:=5;
=> Val := 10;
=> Val := 100;
=> Val := 500;
=> Val := 1000;
=> raise Illegal_Numeral;
end case;
Can be simulated by sequence of if-statements, but logic is obscured.
19 / 34
The Ada case statement
■ no flow-through (unlike C/C++)
■ all possible choices must be covered
◆ if all choices not covered explicitly, default action is mandatory ■ no inaccessible branches:
◆ no duplicate choices (C/C++, Ada, Java)
■ choices must be static (Ada, C/C++, Java, ML)
■ in many languages, type of expression must be discrete (e.g., no floating
point, no string)
20 / 34
Implementation of case
A possible implementation for C/C++/Java/Ada style case:
(If we have a finite set of possibilities, and the choices are computable at compile-time.)
■ build table of case handlers, one entry for each case
■ transform input value to table index
■ branch to that address
■ execute
■ branch to end of case statement (if break keyword used)
This is not the typical implementation for a ML/Haskell style case.
21 / 34
Complications
case (n+1) is
when integer’first..0 when 1
when 3 | 5 | 7 | 11 when 2 | 4 | 6 | 8 | 10 when 21
when 12..20 | 22..99 when others
⇒ Put_Line(“negative”);
⇒ Put_Line(“unit”);
⇒ Put_Line(“small␣prime”); ⇒ Put_Line(“small␣even”); ⇒ Put_Line(“house␣wins”); ⇒ Put_Line(“manageable”); ⇒ Put_Line(“irrelevant”);
end case;
Implementation would be a combination of tables and if statements.
22 / 34
Consider: Serial Copy
void send (int *to, int *from, int count) {
do { /* precondition: count > 0 */ *to++ = *from++;
} while (–count > 0); }
This is called serial copy. It requires a test and branch after each copy. Is there a more efficient way of doing this?
23 / 34
Unstructured Flow (Duff’s device)
void send (int *to, int *from, int count) { register n = (count + 7) / 8;
switch (count % 8) {
} }
case 0: case 7: case 6: case 5: case 4: case 3: case 2: case 1:
do {
*to++ = *from++; *to++ = *from++; *to++ = *from++; *to++ = *from++; *to++ = *from++; *to++ = *from++; *to++ = *from++; *to++ = *from++; while (–n > 0);
}
24 / 34
Duff’s Demystified (How Case Statements Actually Work in C)
if(x==0) goto label_case1; if(x==1) goto label_case2; if(x==2) goto label_case3; if(x==3) goto label_case4; goto label_finish;
label_case1: label_case2: label_case3: label_case4: label_finish:
do-something();
goto label_finish; /* break */ do-something();
goto label_finish; /* break */ do-something();
goto label_finish; /* break */ do-something();
25 / 34
Indefinite loops
■ All loops can be expressed as while-loops ◆ good for invariant/assertion reasoning
■ condition evaluated at each iteration
■ if condition initially false, loop is never executed
while condition loop … end loop; is equivalent to
if condition then
while condition loop … end loop;
end if;
if condition has no side-effects
26 / 34
Executing while at least once
Sometimes we want to check condition at end instead of at beginning; this will guarantee loop is executed at least once.
■ repeat … until condition; (Pascal)
■ do { … } while (condition); (C)
can be simulated by while + a boolean variable:
first := True;
while (first or else condition) loop
…
first := False; end loop;
27 / 34
Breaking out
A more common need is to be able to break out of the loop in the middle of an iteration.
■ break (C/C++, Java)
■ last (Perl)
■ exit (Ada)
loop
… part A …
exit when condition; … part B …
end loop;
28 / 34
Breaking way out
Sometimes, we want to break out of several levels of a nested loop ■ give names to loops (Ada, Perl)
■ use a goto (C/C++)
Outer: while C1 loop … Inner: while C2 loop …
Innermost: while C3 loop …
exit Outer when Major_Failure; exit Inner when Small_Annoyance;
…
end loop Innermost; end loop Inner;
end loop Outer;
29 / 34
Definite Loops
Counting loops are iterators over discrete domains:
■ for J in 1..10 loop … end loop;
■ for(inti=0;i