Design and Implementation of Programming Languagesw
Homeworks for the course CS 3360, Summer 2017

1. (Due July 12) Read appropriate sections of Chapter 2 and for describe the following information for Fortran, LISP, Algol, Cobol, and PL/1:

2. (Due July 18) Describe fixed point numbers in Java in BNF form. Show how we can improve this description if we use Extended BNF.

3. (Due July 18) Translate the following EBNF description into BNF: <natural> := [− | +] {<digit>}+.

4. (Due July 18) Show, on an example, that the following description of propositional expressions containing & is ambiguous: <expression> := <variable> | <expression> & <expression>. Show how to make this grammar unambiguous.

5. (Due July 18) What is the strongest postcondition for the following program: {a > 0} a = a + 3;

6. (Due July 18) What is the weakest precondition for the following program: a = a + 3; {a > 0}

7. (Due July 18) Describe a state diagram for the computer to distinguish between natural numbers and variables and for detecting when each of them ends.

8. (Due July 19) Use both top-down and bottom-up approaches to parse the following expression: (a − b) * (c * d − e) + f * (g − h).

9. (Due July 21) Use pre-and post-conditions to prove that the following Java program for computing n! is correct:

  int fact = 1;
  for (int i = 1; i <= n; i++)
    {fact = fact * i;}

10. (Due July 20) Describe, step-by-step, memory allocation and values of all the variables for the program segment from Problem 9. Assume that that the variable n was the last one allocated before this program segment, and that the hex address of its location is 96EF.

11. (Due July 21) Describe, step-by-step, memory allocation and values of all the variables for the following program segment.

  public static double power(double a, int n){
    if (n == 0) {return 1;}
    else {return a * power(a, n - 1).}
  }

in main:
  double[] b = {2.0, 3.0};
  int pow = 2;
  for(int i = 0; i < 2; i++)
    {b[i] = power(b[i], pow);}
Assume that the hex address of the last used byte is A349.

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

13. (Due July 24) Write down Lisp code for computing the factorial n!.

14. (Due July 26) Trace the function sort that we described in class on the example of a list '(4 3 2). This function was defined as follows:

 (DEFUN sort(list)
    (COND
       ((NIL list) list)
       (T (insert (car list) (sort (cdr list))))
    )
 )

 (DEFUN insert(elem list)
    (COND
       ((NIL list) (CONS elem list))
       ((< elem (car list)) (CONS elem list))
       (T (CONS (car list) (insert elem (cdr list))))
    )
 )

15. (Due July 26) Define a LISP function that takes the list of prices in dollars and converts them into prices in Pesos; at present, 1 dollar = 17 Pesos.

16. (Due July 26) Define a LISP function that adds all the positive elements of the list. For example, for the list '(1 −5 3), the result should be 1 + 3 = 4.

17. (Due July 27) Define a LISP function that computes the number of elements in a given list. On the example of the 2-element list '(1 '(2 3)), show, step by step, how your function will work.

18. (Due July 27) Define a LISP function that finds the largest element of a list. On the example of the list '(1 4 3), show, step by step, how your function will work.

19. (Due July 27) Define a LISP function that computes the union of the two lists, i.e., merges the two lists and has duplicates removed. On the example of the lists '(1 2) and '(2 3), show, step by step, how your function will work.

20. (Due July 27) Define a LISP function that computes the sum of a given list of intervals. On the example of the list '('(0.5 1.0) '(3.0 4.0) '(2.1 2.9)), show, step by step, how your function will work. For extra credit: make your program also check that for each interval from the given list, the lower endpoint is smaller than the upper endpoint, and return a detailed error message if this is not the case.

21. (Due July 28) Describe what will be the quadruples generated by Java based on the following program segment:

  if(a > b && b > c)
    {c = b;}
  else
    {c = a + 1;}

22. (Due July 28) Describe what will be the quadruples generated by Java based on the following program segment:

  int fact = 1;
  for(int i = 1; i <= n: i++)
    {fact *= i;}

23. (Due July 28) Describe what will be the quadruples generated by Java based on the following program segment:

  int pow = 1;
  while(pow < a)
    {pow *= 2;}

24. (Due July 28) Write a generic method for computing the product of all the elements of a given array. This method should work no matter what data type we use.

25. (Due July 31) Explain in which of the two for-loops we can replace for parallel-for and why:

  for(int i = 0 ; i < a.length; i++)
    {a[i] *= 2;}
and
  for(int i = 0: i < a.length - 1; i++)
    {a[i] += a[i+1];}
If you believe that parallel-for is not applicable, provide an example explaining why.

26. (Due July 31) Use the graph algorithm to decide which operations can be performed in parallel first, which next, etc., in the following sequence of operations:
a ← + b c
d ← − b c
e ← + a b
f ← − b
g ← * b f

27. (Due July 31) Use Algol's call by name feature to write a program that computes the sum of an arbitrary expression Σui = l a(i).

28. (Due July 31) Give an example when a call to a Java method causes an undesirable side effect. What can be done to avoid such side effects? What is the disadvantage of this copying-everything idea?

29. (Due July 31) Give an example of a computational program for which method-as-parameter would be helpful.

30. (Due July 31) What are advantages and disadvantages of reflection in general programs? Use reflect to write a generic program for transforming inches to centimeters:

31. (Due July 31) Write a LISP program that, given a natural number n, computes n-th Fibonacci number. Trace this program for n = 4 and explain in what sense the standard way of LISP compiling can be inefficient.

32. (Due August 1) Use the predicates parent, male, and female to describe the concept of a cousin. Test your definition on an example of a sample database, either of your own relatives or of fictitious relatives.

33. (Due August 1) Write a Prolog program for computing the product a given list, Trace on the example of a list [2 5 10].

34. (Due August 1) Use wave algorithm to solve the following problem: we have the following relations between the three sides a,b, and c of a triangle and its three angles A, B, and C:

We know a, b, and A, we need to find all other parameters of the triangle.