Ohjelmointikielten periaatteet keväällä 2009: 2. harjoitukset

6. [Modified from Scott's Review Questions for Chapter 3, Vihavainen] Answer the following questions concerning programming languages:
   1. What is binding time? What is the advantage of binding things as early as possible? What is the advantage of delaying bindings?
   2. Explain the distinctions (if any) between the lifetime, the visibility, and the scope of a name-to-object binding?
   3. What determines whether an object is allocated statically, on the stack, or in the heap?
   4. Explain the difference between static and dynamic scope. Why does the use of dynamic scoping imply the need for run-time type checking? [*]What is meant by deep access vs. shallow access in dynamic scoping?
   5. What is a static chain? What is it used for?
   6. What is a referencing environment? [*]Describe the difference between deep and shallow binding of referencing environments. What is a closure in Scala? What is it used for?
   7. Explain the difference between overloading, coercion, generics, and polymorphism.

7. [Modified from Scott 3.1, Vihavainen] Indicate the binding time (e.g., when the language is designed, when the program is linked, when the program starts execution, etc., see [Scott, p. 105-106]) for each of the following decisions in programming languages C, Java and Scala. Explain any answers you think are open to interpretation.
   • The number of built-in functions (abs, cosine, etc.).
   • The variable declaration that corresponds to a particular variable reference (say, its use in an expression).
   • The maximum length allowed for a constant (literal) character string.
   • The referencing environment for a subroutine that is passed as a parameter (or, alternatively, for an instance of an inner class implementing an interface in Java).
   • The address of a particular library routine.
   • The total amount of space occupied by program code and data.

8. [Modified Scott 3.5] Consider the followining Scala program; subroutines are nested and the scope is static:

   var g = 0
   
   def B(a:Int) = {
     var x = 0
   
     def A(n:Int) = {
       g = n
     } // end of A
   
     def R(m:Int):Unit = {
       println(x)
       x = x/2  // integer division
       if (x >= 1)
         R(m + 1)
       else
         A(m)
     } // end of R
   
     // body of B
     x = a * a
     R(1)
   } // end of B
   
   // body of main
   B(3)
   println(g)
   

   1. What does this program print?
   2. Show the frames on the stack when A has just been called. For each frame, show the static and dynamic links.
   3. Explain how A finds g.

9. [Modified Scott 3.11] Consider the following Scala program:

   def P(A:Double, B:Double):Unit = {
   
        var X:Double = 0.0
   
        def Q(B:Double, C:Double):Unit = {
            var Y:Double = 0.0
            // . . .
            ;
        }
   
        def R(A:Double, C:Double):Unit = {
            var Z:Double = 0.0
            // . . . ---------------------------- (+)
            ;
        }
   
        // . . .
        ;
   }
   
   P(1,2)
   
   

   Scala has static scope. What is the referencing environment at the location marked by (+)?

10. [Modified Scott 3.13] Consider the following Scala program:

    var x=0  // global
    def set_x(n:Int) {x = n}
    def print_x {println(x)}
    def first {set_x(1); print_x}
    // KORJAUS!! Seuraava rivi on korvattu sitä seuraavalla! (19.3. klo 21:13)
    // def second {x:Int; set_x(2); println(x)}
    def second {var x=0; set_x(2); println(x)}
    
    // Main:
    set_x(0)
    first
    print_x
    second
    print_x
    

    What does this program print using the static scoping of Scala? What would it print if Scala had dynamic scoping? Explain both cases?

11. [*][Modified from Scott 3.16, Vihavainen] Consider the following pseudocode, with three separate subroutines and some global source code calling on these subroutines. Note that this pseudocode uses textual indentation to determine the extend and termination of different blocks, a special notation used even by some actual languages.

      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
         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 the language uses dynamic scoping. What does the program print if the language uses shallow binding? What does it print with deep binding? Why?

12. [Modified Scott 3.17] Consider the following Scala program:

    var x = 1  // global variables
    var y = 2
    
    def add {x = x + y}
    def second(P: => Unit) {var x = 2; P}  // HUOM: Tämä rivi korjattu! 
    def first {var y = 3; second(add)}
    
    // Main:
    first
    println(x)
    
    

    1. What does this program print, when Scala uses static scoping?
    2. [*] What would it print if the language used dynamic scoping with deep binding?
    3. [*] What would it print if the language used dynamic scoping with shallow binding?
    4. [korvaa koevihjeenä kohdat b ja c] What would it print if the language used dynamic scoping? Explain thoroughly how you get the result.

Takaisin harjoitusten pääsivulle.