CPSC 320: Programming Languages ( Fall 2019)

---

Questions Still Pending

Pending homework questions can be found at http://casper.unbc.ca/Semesters/2019-05F/320-homework-pending.php.

---

Questions due by Thursday, December 12.

6. What is the weakest pre-condition P for

   {P}if e then s1 else s2 endif{Q} ?

   To write the answer to this question, it is appropriate, and probably necessary, to write things something like “Suppose that P₁ is the weakest pre-condition such that {P₁}s1{Q} and that….”

   NB The font may not be clear here. I am asking for partial correctness assertions, not total correctness assertions.

7. The code below gives a fragment of an algorithm to provide a candidate for a majority element.

   If the algorithm works correctly, and data has a majority element, then candidate will be equal to that element at the end of the loop.

         int count1 = 0 ;
         E candidate = null ;
         for (int i=0;i<data.length;++i)
             {
             if (count1==0)
                 {
                 candidate = data[i] ;
                 count1=1;
                 }
             else if (candidate.equals(data[i]))
                 {
                 count1 += 1 ;
                 }
             else
                 {
                 count1 -= 1 ;
                 }
             }
         

   Attempt to find an axiomatic semantic proof of the correctness of this code.

---

Questions due by Friday, December 13.

8. Find a language that has some feature using dynamic scoping (other than a control structure), and demonstrate through code that it is dynamically rather than lexically scoped.
9. Find scenarios that distinguish between the five parameter passing mechanisms discussed in class.

---

Questions due by Saturday, November 9.

4. In the operational semantics discussed in class, the meaning of an expression e was a function of the type:

           E[e] : E → S → V
         

   where
   • E is the set of environments.
   • S is the set of stores (memory states).
   • V is the set of values.
   1. How would you change the type of “E[e]” to accommodate Java-like expressions x++ and ++x?
   2. Write rules for

      E[x++] and E[++x]
            

      .
5. Using the operational semantics discussed in class, write down the meaning of an expression of the form let b in e.

---

Questions due by Friday, October 11.

1. Write a regular expression that describes binary numbers divisible by 3.
2. Write a description of Backus-Naur Form described in class in EBNF. (This is easy to find on the web. If you find a web resource, provide a link to it.)
3. Extend the grammar

   <expr> ::= <term>
            | <expr> + <term>
            | <expr> - <term>
   <term> ::= <factor>
            | <term> * <factor>
            | <term> / <factor>
   <factor> ::= ( expr )
            | number
            | variable
         

   1. to include exponentiation (use ^ or **) and unary minus.
   2. Document whether or not your grammar allows:

      • - - x 

      • x ^ y ^ z

      • - x ^ y (and explain how you want this to group)

      • x ^ - y