Spring 2018

### Homeworks

Current HW

HW 1: Hello World with Numbers

Due Friday 9 February 2018

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.

• How simple is the code?
• How readable is the code?
• How much time did it take to get it running?
• Is it compiled or interpreted?

Send the professor an email with your code (not as an attachment) and your short answers to the above questions.

HW 2: Grammars and Regular Expressions

Due Friday 23 February 2018

1. Define a BNF 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. 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) );```
4. Using the Clite syntax, generate both the concrete parse trees and abstract parse trees for the following statements. Feel free to do the concrete tree automatically using flex.

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

HW 3: Exercises

Due Wednesday 7 March 2018

1. Write a BNF 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. 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?
3. 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.
4. 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?
5. Why do you think there is an IEEE standard for float types but not for integer types?
6. 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 4: Semantics

Due Friday 23 March 2018

1. Consider the do-loop below. The state of the program consists of a single variable i.
```int i=0;

do {
i++;
} while (i < 5);
```

Write a purely functional python representation of the do loop itself. The top level call should be MDo( doloop, state ). The state will be a single integer that starts with the value 0. The body of the do loop consists of a Statement adding something to the state variable. The test of the do loop involves comparing the state to the expression value.

To make the doloop argument, create a simple class DoLoop that contains a test field and a body field. Assign the test field the value 5. Assign the body field the value 1. You can use the body field as the thing to add to the state.

The body of the loop should be implemented by a call to an MStmt function that should, in addition to updating state, print out something indicating it is running.

Demonstrate your functional python code works by running it. Your MStmt function should execute five times and then the MDo function should return 5 for the state (the value of i).

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`

and

`return x `

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

HW 5:

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 6: Memory, Coding Style, and Concurrency

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 7: Logic Puzzle

Due Friday, 11 May

Pick one of the following two tasks. If you do both, the second will count as an extension for project 8 (be sure to point that out in your report).

Option 1: using Lisp, Scheme, or Clojure, write some type of tree data structure (e.g. binary tree or a heap) and demonstrate that it works. Whatever data structure you build only needs to hold integers. For a binary tree, implement add and an in-order traversal. For a heap, implement add and remove.

Option 2: Go to the site Logic Puzzles. Pick a puzzle. Write a prolog program similar to this one to solve the puzzle.