581362 Ohjelmointikielten periaatteet keväällä 2007: 2. harjoitukset 30.1.

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. What is an elaboration? Why is it needed?
   5. Explain the difference between static and dynamic scope. Why does the use of dynamic scoping imply the need for run-time type checking? Describe the association list (A-list) and central reference table data structures used to implement dynamic scoping. What is meant by deep access vs. shallow access in dynamic scoping?
   6. Explain the purpose of a compiler's symbol table.
   7. What is a static chain? What is it used for?
   8. What is a referencing environment? Describe the difference between deep and shallow binding of referencing environments. What is a closure? What is it used for?
   9. 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 your favorite programming language and implementation. 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 in some object-oriented language you know).
   • The address of a particular library routine.
   • The total amount of space occupied by program code and data.

8. [Modified from Scott 3.4, Vihavainen] Give three conceptually different concrete examples drawn from programming languages with which you are familiar in which a variable or some other object is live but not in scope. (Hint: consider how different abstraction and information hiding mechanisms may affect the visibility and accessability of objects.)

9. [Scott 3.5] Consider the following pseudocode, assuming nested subroutines and static scope:

     procedure main
        g : integer
   
           procedure B(a : integer)
              x : integer
   
              procedure A(n : integer)
                 g := n
   
              procedure R(m : integer)
                 write_integer(x)
                 x /:= 2 -- integer division
                 if x > 1
                    R(m + 1)
                 else
                    A(m)
   
           -- body of B
              x := a × a
              R(1)
   
     -- body of main
        B(3)
        write_integer(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.

10. [Scott 3.11] Consider the following pseudocode:

      procedure P(A, B : real)
         X : real
    
      procedure Q(B, C : real)
         Y : real
         . . .
    
      procedure R(A, C : real)
         Z : real
         . . . -- (*)
    . . .
    

    Assuming static scope, what is the referencing environment at the location marked by (*)?

11. [Scott 3.13] Consider the following pseudocode:

       x : integer  --global
    
       procedure set_x(n : integer)
          x := n
    
       procedure print_x
          write_integer(x)
    
       procedure first
          set_x(1)
          print_x
    
       procedure second
          x : integer
          set_x(2)
          print x
    
    
       set_x(0)  --pääohjelma
       first()
       print_x
       second()
       print_x
    

    What does this program print if the language uses static scoping? What does it print with dynamic scoping? Why?

12. [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?

13. [Scott 3.17] Consider the following pseudocode:

        x : integer := 1  --globaalit
        y : integer := 2
    
        procedure add
           x := x + y
    
        procedure second(P : procedure)
           x : integer := 2
           P()
    
        procedure first
           y : integer := 3
           second(add)
    
        first()            --pääohjelma
        write integer(x)
    

    1. What does this program print if the language uses static scoping?
    2. What does it print if the language uses dynamic scoping with deep binding?
    3. What does it print if the language uses dynamic scoping with shallow binding?

Takaisin harjoitusten pääsivulle.