CS 3360 Design and Implementation of Programming Languages
Summer 2017, Test 2

Name: __________________________________________________________

1. Describe the expression (a − b * c) * (c * d − e) + f − (g − h) in Lisp's prefix form.

2. Use bottom-up algorithm to parse the expression from Problem 1, build the dependency graph, explain which operations can be performed in parallel first, which next, etc.
3. Describe what will be the quadruples generated by Java based on the following program segment:
  for(int i = 1; i <= n: i++)
    {c[i] = a[i] + b[i];}
4. Can we use parallel-for in computations of Problem 3? Explain your answer.
5. Use the algorithm from Problem 3 to write a generic Java method for computing the component-wise sum of two arrays. This method should work for all possible numerical data types: int, short, char, double, float.
6. Write a LISP function for computing the component-wise sum of two lists. Trace it on the example of the lists '(1 10 100) and '(2 20 200), the result should be '(3 30 300).
7. Write a Prolog program for computing the component-wise sum of the two lists. Trace it on the same example as in Problem 5.
8. We all know how to find the largest element of an array. Use Algol's call-by-name feature to write a method max(index, lower, upper, expression) that would be able to compute the largest value of a given expression when the index of this expression ranges between the given lower bound and the given upper bound. Show, step by step, how this method can be used to find the largest value of the expression (0.1 * j) - sqr(0.1 * j), when j ranges from 0 to 10.
9. Use the predicates parent, male, and female to describe the concept of a brother. Test your definition on the following database related to the Russian czar Peter I, the founder of St. Petersburg, Russia:
 parent(alexei, peter).
 parent(alexei, ivan).
 parent(alexei, sofia).
 male(peter).
 male(ivan).
 female(sofia).
 ? brother(X, Y).
The goal is to find all the brothers. Show, step by step, how Prolog will do it.
10. Use wave algorithm to solve the following problem:
  • we know that distance d is equal to velocity v multiplied by time t: d = v * t;
  • we know that the cost c of the gas is proportional to the amount of fuel: c = 2.10 * f;
  • we know that the amount of fuel f is proportional to the distance: f = d / 20.
We know the velocity v and the time t. We need to compute the cost c of the gas.