Title image Fall 2018


HW 6: Memory, Coding Style, and Concurrency

Due Thursday, 25 April 2019.
  1. Give an example of a data structure that would not automatically be freed by a reference counting approach to garbage collection.
  2. Would mark-sweep or copy collection clean up the data structure from question 1? Why?
  3. From an implementation point of view, is mark-sweep or copy collection more difficult to code? Explain.
  4. Write a Python function in imperative style that calculates the average squared error between the corresponding elements of two lists and returns the value. You can assume the lists are the same length. The two lists [1, 2, 3] and [2, 0, 1] should return 3.0.
  5. Write a recursive Python version of the same function. Make sure the two functions return the same value for the same input.
  6. Write a lambda function in Python that executes the same function. Make sure it also returns the same value for the same input. [Hint: use list comprehension and the built-in sum function.]
  7. Using a very large list, time the three functions and see which is most efficient. Is there a size for which any of the three methods fails?
  8. Give an example of an application where a race condition might occur if you used concurrent programming to solve the problem.
  9. Given an example of an application where a deadlock might occur if you used concurrent programming to solve the problem.

HW 5: More Semantics

Due Tues 16 April 2019

  1. What is the purpose of an assertion statement? Write a short Python program that sums the elements of a list and returns the average. Use an assertion to catch the case where the length of the list is zero.
  2. What is the difference between a procedure, a function, and a method? Write a short Python program showing an example of each.
  3. Is Python pass by value or pass by reference? Explain your answer, possibly by showing a code example.
  4. What are the tradeoffs between giving the programmer responsibility for memory management versus handling it automatically as part of the language?
  5. In C/C++, what is the benefit of using a pointer to a variable as an argument instead of the variable itself? What are the drawbacks?
  6. Why is it difficult to formally represent the semantics of a try/catch statement? Is this, perhaps, an argument for operational semantics?

HW 4: Semantics

Due Thursday 4 April 2019

  1. Consider the Python code we have been looking at in class. It implements purely functional meaning functions for a subset of Clite, that I am calling Cliter. It supports while loops, but not for loops. Your job is to add support for a for loop.

    Write a class ForLoop to implement the for loop AST node. It should have fields

    • initial : Statement (e.g. j = 0)
    • test : Expression (e.g. j < 5)
    • body : Statement (e.g. a = a * 3)
    • post : Statement (e.g. j = j + 1 )

    Write the function M_ForLoop to execute the intial statement, then loop in a manner similar to that of the while loop. Because the initial statement should be evaluated just once, you will need two functions (M_ForLoop should call M_ForLoopLooper, which is recursive). Remember to make M_ForLoopLooper purely functional, so you will need to be careful about how you make sure the body statement is evaluated before the post statement.

    Demonstrate your functional python code works by running it with the following test code:

    def testForLoop():
        # initial, test, post
    #     for (i=0; i < 5; i = i + 1) {
    #         a = i+2 # body
    #     }
        init = Assignment( Variable("i"), Value(0) )
        test = Relation( Variable("i"), "<", Value(5) )
        post = Assignment( Variable("i"), BinaryExpression(Variable("i"),"+",Value(1)) )
        body = Assignment( Variable("a"), BinaryExpression(Variable("i"),"+",Value(2)) )
        loop = ForLoop( initial=init, test=test, body=body, post=post )
        state = State()
        state = M_ForLoop( loop, state )
        print( state )

    The output should be
    i: 5
    a: 6
  2. Consider the following statement:
    a = b;

    The statement is valid in Java, C, and Python (even with the semi-colon), assuming proper prior declarations or assignments. Assume the types are such that the compiler does not give an error.

    For each language, explain what occurs, or might need to occur to execute this statement. Are there any differences?

  3. Why do you think most programming languages use sequential semantics?
  4. What are some applications for concurrent semantics?
  5. What is the difference between
    print x


    return x 

    in terms of their semantics? What about in terms of the movement of data?

HW 3: A chance to think more about C

Due Thursday March 7 2019

  1. For global variables in C: (1) how can they be accessed in other compilation units? (2) how can a global variable be hidden from other compilation units? (3) why would you want to hide global variables?
  2. For C, give three examples of r-values that cannot be l-values. Give three more examples of l-values. Are there l-values that cannot be r-values? Explain your answer.
  3. What is the definition of true and false in C with respect to the condition for an if-statement? Compare to Java. What are the benefits and drawbacks?
  4. Why do you think there is an IEEE standard for float types but not for integer types?
  5. Write two syntatically identical functions in C and Java that have different semantic meanings. Demonstrate the differences by printing out something and explain the semantic differences.

HW 2: More with Grammars and Regular Expressions

Due Tuesday February 26 2019

  1. Write an EBNF grammar to describe the roman numerals from 0 to 100. Solve the same problem using regular expressions and test it on this file using either flex or egrep. Here is a chart.
  2. Using the Clite syntax, generate both the concrete parse trees and abstract parse trees for the following statements.

    • a = b * ( 5 + c );
    • if( a == 0 || b > 0 )
        b = 0;
        b = a;

HW 1: Grammars and Regular Expressions

Due Tuesday February 19 2019

  1. Define an EBNF grammar with the alphabet {a, b} that defines strings that start with an a, have one or more b symbols and end with an a.
  2. Define a regular expression for the prior grammar. Note that you can test regular expressions using the terminal command egrep. You can use the following ABA test file. There are three lines that match the proper specification.
  3. Demonstrate that addition in C is not associative (in the mathematical sense). The following two statements should print significantly different results. You need to figure out appropriate types and values for a, b, and c. Can you do the same with multiplication?
    printf( "%f\n", (a + b) + c );
    printf( "%f\n", a + (b + c) );

HW 0: Hello World with Numbers

Due Tuesday 12 February 2019

Pick a language you do not know and write a program in that language that computes the average of three numbers and prints out the result. Run your code and make sure it works.

Send the professor an email with your code (not as an attachment) and your short answers to the above questions. Please include the phrase "CS333 HW0" in the subject of the email.

Word to the wise: Stephanie uses filters to direct HW emails into the proper folders. At the end of the semester, when she records who completed HW's, she looks in those folders. If an email isn't there because the filter didn't catch it, then you likely won't get credit for that HW.