CPSC 320: Programming Languages ( Fall 2016)

---

Questions Still Pending

All remaining homework is due by December 2, but there is some flexibility in the deadline.

---

Questions due by Friday, December 02

---

3. Consider the following Racket program:

   #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)))
     )
   

    
   1. What output does this program produce?
   2. What output would this program produce if Racket used static scoping?
   3. What output would this program produce if Racket used dynamic scoping?

---

4. Figure 1

   <condition> ::= true | false
   

   <var>       ::= a | b | c | d
   

   <value>     ::= 3 | 5
   

   <assignment> ::= <var> := <value>
   

   <block> ::=
         begin <block-body> end
       | begin              end

   <block-body> ::=    <statement>
      | <block-body> ; <statement>
   

   <statement> ::=
         <if-then-stat>
       | <bal-stat>
   

   <if-then-stat> ::=
         if <condtion> then <statement>
   

   <bal-stat> ::=
         <block>
       | <if-then-else-stat>
       | <assignment>
   

   <if-then-else-stat> ::=
         if <condition> then <bal-stat> else <statement>
   

   Consider the grammars shown in Figures 1 and 2. They both specify vaguely C like-languages that differ only in their treatment of if-then statements.

   Determine which of the following statements have legal parses according to the two grammars:

   1. begin end

   2. b := 3

   3. b := 3; c := 5

   4. begin b := 3; c := 5 end 

   5. if false then begin b := 3 end 

   6. if false then
            begin if true then b := 3
            end
            else c := 5

   NB: there is a correction in part (f.) above. Thanks to Lee C. for noticing.

   Figure 2

   <condition> ::= true | false
   

   <var>       ::= a | b | c | d
   

   <value>     ::= 3 | 5
   

   <assignment> ::= <var> := <value>
   

   <block> ::=
         begin <block-body> end
       | begin              end

   <block-body> ::=    <statement>
      | <block-body> ; <statement>
   

   <statement> ::=
         <if-then-else-stat>
       | <no-last-else-stat>
   

   <no-last-else-stat> ::=
         <assignment>
       | <block>
       | <if-then-stat>
   

   <if-then-stat> ::=
         if <condtion> then <no-last-else-stat>
   

   <if-then-else-stat> ::=
         if <condition> then <statement> else <statement>
   

   Does either grammar solve the problem of dangling else statements? If so, how? If not, why not?

---

Assigned 2016-11-16

5. Write a Scheme function average that takes an arbitrary number of numeric arguments and computes their average. The point is to show that you know how to write a Scheme function that receives an arbitrary number of arguments.

6. Write a Scheme function (format-seq arg ...) that takes an arbitrary number of numeric arguments and returns that is similar to (format "~s" (list arg ...)).

   For instance, (format-seq 3 "cow" 5) should return the string “(3 "cow" 5)”.

   However, format-seq should also have three optional keyword arguments #:start, #:end, and #:sep (with default values "(", ")", and " " resepctively) that determine the initial, final, and separator strings.

   For instance, (format-seq #:end " <<<" 3 "cow" 5 #:sep "+") should return the string “(3+"cow"+5<<< ”.

   The point is to show that you know how to write a Scheme function that receives optional and keyword arguments.

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

---

Assigned 2016-11-17

8. Figure 3
   private 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) ;
       }

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

---

Assigned 2016-11-20

9. Consider the statement

   while (i>0) { a *= (i--) ; } 

   • What is one pre-condition that results in the post-condition “i=0, a=120”?
   • What is the weakest pre-condition that results in the post-condition “i=0, a=120”?

10. Consider the statement

    while (i>0) { s += (i--) ; } 

    What is the strongest post-condition that we can assert for the pre-condition “i=4, s=5”?

---

Questions previously due Monday, 24 October

from 2016-09-21

1. Experiment with Maple to determine what its rule for numbers are. Then write a Racket regular expression that recognizes those numbers.

---

from 2016-10-12

2. Read the Racket Guide or Reference Manual to find out about Parameters.

   Write a Racket program that uses (current-output-port) to illustrate how parameters work, in particular how they are dynamically bound.

---