This is a course page of
David Casperson
Associate Professor
Computer Science
University of Northern British Columbia

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.

  1. 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 P1 is the weakest pre-condition such that {P1}s1{Q} and that….”

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

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

  1. 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.
  2. Find scenarios that distinguish between the five parameter passing mechanisms discussed in class.

Questions due by Saturday, November 9.

  1. 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]
            
      .
  2. 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
Home page Semesters Site Map
go back Fall 2019 go forward
2022-12 other links

Java
CPSC 200 [Other years]
CPSC 320 [Other years]
Homework
CPSC 370 [Other years]
 
Labour News
 
David’s Schedule

Semester Dates…