Midterm Study Aid

Answering these questions should help you prepare for the midterm exam.

1. 
   

   Be able to define and give examples of the terms listed here (the "For the midterm ..." parts).

   
   
2. 
   

   What is an L-value? An R-value? Show which ones are used where in this programming language statement:

      result := (x + delta) * result ;
   

   
   
3. 
   

   Suppose the machine you want to run a program on has a load/store architecture, with these 5 instructions:

      load  address, reg
      add   reg, reg, reg
      sub   reg, reg, reg
      mul   reg, reg, reg
      store reg, address
   

   For simplicity, let's have an address be the name of a static variable that will be turned into a memory location by the loader. A reg is the name of a register, and let's say we have 3 of them:

      R1, R2, R3
   

   The add instruction adds the second reg to the first and places the result in the third. The sub instruction subtracts the second reg from the first and places the result in the third. The mul instruction multiplies the first reg by the second, and places the result in the third. The store instruction places the value in the reg into the memory location named in address.

   Now consider this statement in a programming language:

      result := offset + (width * n) ;
   

   The assembly code generated by the compiler might look like this:

      load width, R1
      load n, R2
      mul R1, R2, R1
      load offset, R2
      add R2, R1, R1
      store R1, result
   

   Generate similar assembly code for these programming language statements:

      a) net := gross - costs
      b) vol := (length * width) * height
      c) cube := (X * X) * X
      d) final := ((a - aBase) * (b - bBase)) * (c - cBase)
   

   
   
4. 
   

   Consider a machine with a stack architecture (like the Java VM we discussed), with these instructions:

      push address
      add
      sub 
      mul
      pop address
   

   The machine maintains a stack of integers that is potentially unbounded. An address is the name of a storage location, which will be converted to an actual machine memory location by the loader. The push instruction takes the value found at address and pushes it onto the computation stack. The add instruction adds the top item on the stack to the next-to-top item, pops off both, and pushes the result onto the stack. The sub instruction substracts the top stack item from the next-to-top item, pops off both, and pushes the result back on the stack. The mul instruction multiplies the top stack item by the next-to-top item, pops off both, and pushes the result back on the stack. The pop instruction pops the top item off the stack and places the value into the location named by address.

   Now consider this statement in a programming language:

      result := offset + (width * n) ;
   

   The assembly code generated by the compiler might look like this:

      push offset
      push width
      push n
      mul
      add
      pop result
   

   Generate similar assembly code for these programming language statements:

      a) net := gross - costs
      b) vol := (length * width) * height
      c) cube := (X * X) * X
      d) final := ((a - aBase) * (b - bBase)) * (c - cBase)
   

   
   
5. 
   

   Choose any PL you know well. For each of the 6 major binding times (definition time, implementation time, program writing time, compile time, link/load time, runtime) discuss properties and aspects of programs in that language that are bound at each time. Explain each item you name.

   
   
6. 
   

   Define the following terms highlighting the essential difference(s) between each pair of terms:

      eager evaluation order and lazy evaluation order 
      Static scoping and dynamic scoping 
      static and dynamic type checking
      static and dynamic memory allocation
   

   
   
7. 
   
   Write, in a syntax of your choice, a program that will have 4 different outputs depending on whether parameters are passed to subprograms by

   1. value
   2. reference
   3. value/result
   4. name
   
   
8. 
   

   Recall that in a theoretical sense, a "language" is just a collection of strings formed over some alphabet. Write a regular expression for each of the following languages.

   a) C-style comments  ( anything between "/*" and "*/" )   
   b) identifiers containing only alpahnumeric characters, and "_"
      (underscore) with the additional constraints that they must
      begin with underscore and have at least 2 characters total.
   c) scientific notation
   d) strings in which every "begin" is eventually followed by an "end" before
      another "begin" occurs... and every "begin" has an "end"
         example(yes):  i never begin what i can't end 
         example(yes):  i begin you end, we have beginnings and endings
         example(yes): begin end begin end end end end begin end i'm dizzy
         example(no):  you end what I begin
         example(no):  We begin they begin everyone ends no end in sight
   

   
   
9. 
   

   Write a Perl program that will examine all lines in a text file and print out only the ones that contain substring in one of the previous regular languages.

   
   
10. 
    

    Compare and contrast scripting languages to more traditional application development languages.

    
    
11. 
    

    Is Perl strongly typed, or weakly typed?
    What are the basic types in Perl?
    What type constructors (for making types other than the basic ones) are available in Perl?
    Explain the notion of "context" in Perl; give examples from Perl programs demonstrating its effects at run-time.

    
    
12. 
    

    Is Java strongly typed, or weakly typed?
    What are the basic types in Java?
    What type constructors (for making types other than the basic ones) are available in Java?

    
    
13. 
    

    Is ML strongly typed, or weakly typed?
    What are the basic types in ML?
    What type constructors (for making types other than the basic ones) are available in ML?

    
    
14. 
    
    Consider the following ML code:

      val k = 3;
      fun foo n = n + k;
      val k = 9;
      foo 12;
    

    What value does the ML interpreter produce for the last line, the evaluation of function "foo" in the argument 12? Explain how this happens in terms of ML scope, symbol table structure, binding times, etc.
    
    
15. 
    
    Write a higher-order ML function that will take an integer argument (let's say "n"), and will return a function that will take an argument and add "n" to it.
    
    
16. 
    
    (harder) Write the following higher-order ML function:
    Call your function "maker" since it will be making a function definition to return as its value. Function maker will take 2 arguments... an integer (let's say "n") and a function (let's say "f").
    Maker will then manufacture and return another function of 1 argument that invoke the "n" nested invocations of function "f" function starting on that argument.
    Note the type issues... "f" has to be a function that produces a type that can be summed.
    
    
17. 
    

    Write a program fragment (pick your favorite language or code notation) that produces different output when executed with static scope than when executed with dynamic scope.

    Explain the scoping rules in use in Perl.

    Explain the scoping rules in use in Java.

    Explain the scoping rules in use in ML.

    
    
18. 
    

    Explain how a runtime stack works. What is a stack frame (activiation record)?
    What information is stored in a stack frame?

    Assume we have static scoping. How is the information in a stack frame, and in the runtime stack in general, used to find the proper memory locations for non-local refences when a program executes? What about local references?

    Repeat this explanation assuming we have dynamic scoping.

    
    
19. 
    
    Consider the following code:

     1  program midterm
    
     2  int x = 0, y = 1;
     3  real r = 2.14;
    
     4  procedure proc1 (int k) returns real
     5    int z, x, m;
     6    real r;
     7    x := proc2(k) ;
     8    r := x*k ;
     9    return r ; 
    10  end proc1
    
    11  procedure proc2 (real m) returns int
    12    int p;
    13    p := (int) m * m ;
    14    return p;       
    15  end proc2
    
    16  begin /* main */
    17    r := proc1(y);
    18  end program
    

    Draw a memory layout and he runtime stack that exists when execution first gets to line 14. Show the static chain pointers, dynamic chain pointers, return addresses, parameters, local variables, and any other items you think need to be in the stack frame for a procedure. For return addresses, you can use the line numbers.
    
    
20. 
    

    Does a programming language have to have a run-time stack? Are there (or have there been) any languages that do not have a runtime stack?

    What common features of programming languages can I not have if I do not have a runtime stack?

    What is static memory management?
    What is dynamic memory management?
    Are there forms of dynamic memory management other than runtime stack (or stack-based)?

    
    
21. 
    

    Consider this program fragment, with nested static scopes:

       program example {
    
          int x = 5;
          real y = 2.5;
    
          procedure p1 (int x, int z) {
             boolean flag = false;
             real r2;
    
             procedure inner (real p1) {
                int x;
                boolean flag = false;  /* line 1 */
                x = (p1 + z) * y ;     /* line 2 */
             }
          }
       }
    

    Show the structure and contents of the compiler symbol table once the compiler has finished parsing line 1 above.

    Show sample machine instructions that would correctly find the local and non-local storage for line 2 above. This will require you to use the various structures in the stack frame and run-time stack.

    
    
22. 
    

    What is non-deterministic computation?

    Give an example of a programming language statement that expresses a nondeterministic computation.

    
    
23. 
    

    What is a display? What does it replace in the runtime system of a statically scoped language? How does it work?

    
    
24. 
    

    Explain what a "calling sequence" is. What are the major divisions of a calling sequence? What activities happen in each division?