CPSC 320: Programming Languages (Fall 2018)

Generally speaking, questions that have been assigned but not yet give a due date can be found on this page. Questions that have been given a due date can be found here. There is now homework due.

Pending homework questions

1. Look at Chapter 9 of the Racket Guide. Design a Racket program that recognizes the same strings as Maple recognizes as numbers. That is experiment with Maple until you think that you understand what Maple accepts as numbers, then try to write a Scheme regular expression that captures that notion.

2. #lang racket
   
   (define (fred)
     (define x 64)
     (define ichabod (gertrude))
     (ichabod 5))
   
   (define (gertrude)
     (define x 32)
     (define (harriet y)
       (+ x y))
     harriet)
   
   (module+ main
     (displayln (format "(fred) returns ~v" (fred)))
     )
   

   Consider the Racket program shown to the right:

   1. What output does this program produce?
   2. Replace x by a globally defined parameter, and recode the example to illustrate dynamic binding.

3. This question is really about Floyd-Hoare axiomatic semantics. Which statement
   • Barack Obama is president of the United States.
   • Donald Trump is president of the United States.
   is more likely to make a valid loop invariant? Under what assumptions? Why?

4. Consider the Java code shown in Figure 3. This is the partitioning algorithm from Quick sort.

   Figure 3
   public static <E extends Comparable<E>>
   void partition(E [] data, E key, Box<Integer> cut)
       {
       int left = -1 ;
       int right = data.length ;
   
       while(left<right)
           {
           do {++left ;  } while (data[left ].compareTo(key)<0) ;
           do {--right ; } while (data[right].compareTo(key)>0) ;
           if (left<right) swap(data,left,right) ;
           }
       cut.set(left) ;
       }

   1. What is the (useful) loop-invariant for the outer the while-loop?
   2. Write a {P} C {Q} claim where C is the entire first do-while loop.
   3. Consider the first inner do-while loop. What condition needs to be true for the loop to terminate?
   4. This algorithm doesn’t always run without errors. What pre-condition is necessary for the algorithm to return without errors?
   5. If the algorithm does return without errors, what is true on return?
   What parameter passing mechanism does Java use?
   Is the calling function's copy of data modified by this routine? Explain.
   How does Java’s parameter passing mechanism explain the point of the cut argument? Why isn't this just passed back as an int?