Programming Language Principles

1. 3.1 from the book
Indicate the binding time (e.g., when the language is designed, when the program is linked, when the program begins execution, etc.) for each of the following decisions in your favorite programming language and implementation. Explain any answers you think are open to interpretation.

*The number of built-in functions (math, type queries, etc.)
*The variable declaration that corresponds to a particular variable reference(use)
*The maximum length allowed for a constant (literal) character string
*The referencing environment for a subroutine that is passed as a parameter
*The address of a particular library routine
*The total amount of space occupied by program code and data

2. 3.4 from the book
Give three concrete examples drawn from Java/C++ in which a variable is live but not in scope.

3. 3.9 from the book
Consider the following fragment of code in C:
{ int a, b, c;
	...
	{ int d, e;
		...
		{ int f;
			...
		}
		...
	}
	...
	{ int g, h, i;
	...
	}
	...
}

Assume that each integer variable occupies four bytes. How much total space is required for the variables in this code? Describe an algorithm that a compiler could use to assign stack frame offsets to the variables of arbitrary nested blocks, in a way that minimizes the total space required.

4. 3.16 from the book
Consider the following pseudocode:
x : integer –– global

procedure set x(n : integer)
	x := n

procedure print x
	write integer(x)

procedure foo(S, P : function; n : integer)
	x : integer := 5
	if n in {1, 3} 
		set x(n)
	else
		S(n)
	if n in {1, 2} 
		print x
	else
			P
set x(0); foo(set x, print x, 1); print x
set x(0); foo(set x, print x, 2); print x
set x(0); foo(set x, print x, 3); print x
set x(0); foo(set x, print x, 4); print x

Assume that the language uses dynamic scoping. What does the program print if
the language uses shallow binding? What does it print with deep binding? Why?

5. 3.17 from the book
Consider the following pseudocode:
	x : integer := 1
	y : integer := 2

procedure add
	x := x + y

procedure second(P : procedure)
	x : integer := 2
	P()

procedure first
	y : integer := 3
	second(add)

first()
write integer(x)

(a) What does this program print if the language uses static scoping?
(b) What does it print if the language uses dynamic scoping with deep binding?
(c) What does it print if the language uses dynamic scoping with shallow binding?