Programming Language Principles HW 5 Solutions

1. 
The number of built-in functions is originally bound at language design time, though it may
be increased by certain implementations. C has just a few functions that are truly built-in,
notably sizeof. A large number of additional functions are defined by the standard library.
Several of these, including printf, malloc, assert, and the various stdarg routines, are
often special-cased by the compiler in order to generate faster or safer code.
The variable declaration that corresponds to a particular variable reference (use) is bound at
compile time: C uses static scope.
The maximum length of a character string (if there is a limit) is bound at language implementation
time.
Because C does not have nested subroutines, the referencing environment for a subroutine that
is passed as a parameter is always the same as the environment in effect when the subroutine
was declared.
The address of a particular library function is bound by the linker in most systems, though it
may not be known until load time or even run time in systems that perform dynamic linking
(Section 14.7). Note that we’re speaking here of virtual addresses; physical addresses
are invisible to the running program, and are often changed by the operating system during
execution).
The total amount of space occupied by program code and data is bound at run time: the
amount of stack and heap space needed will often depend on the input.

2. 
(a) If procedure P declares a local variable named x, then a global variable also named
x will be live but not in scope when executing P.
(b) A static variable declared inside a function is live but not in scope when execution is
not inside the function.
(c) Non-public fields of an object of class D are live but not in scope when execution
is not inside a method of D.

3. Variables a, b, and c are live throughout the execution of the
outer block. Variables d, e, and f are needed only in the first nested block, and can overlap the
space devoted to g, h, and i. A total of 4 × 6 = 24 bytes is required.
When compiling a subroutine, the compiler can construct a tree in which each node represents
a block, and is a child of the node that represents the surrounding block. Variables declared in
the outermost block are assigned locations at the beginning of the subroutine’s space. Variables
in a nested block are assigned locations immediately following the variables of the surrounding
(parent) block. Variables of siblings overlap.

4. With shallow binding, set_x and print_x always access foo’s local x. The program
prints
1 0 2 0 3 0 4 0

With deep binding, set_x accesses the global x when n is even and foo’s local x when n is
odd. Similarly, print_x accesses the global x when n is 3 or 4 and foo’s local x when n is 1 or
2. The program prints
1 0 5 2 0 0 4 4

5. (a) 3; (b) 4; (c) 1.