Csci 4651 Problem set 5

Due Friday, October 10 in class

Problem 1: Algol 60 Pass-by-Name

Exercise 5.2 pp. 122-123.

Problem 2: pointers and functions in C++

To run a C++ program:

• Edit a file with any plain-text editor (gedit, emacs, pico/nano, or other), save it with the extension .cpp (for this example assume myprogram.cpp)
• Open a terminal window, use cd command to get to the folder where your C++ files are
• Type g++ myprogram.cpp to compile. If there are error messages, correct the mistake and compile again (note: an old executable a.out will still be there until it is overwritten by a new one. If your program failed to compile and you still try to run it, you would be running the old version).
• After a successful compilation you can run your program by typing a.out on the command line. If you get file not found error, use ./a.out instead.

Question 1

Write a void C++ function order that takes two pointers to int, checks if the value at the first address is larger than at the second one, and if it is, switches the values at the two addresses. I.e. if I have n = 7, m = 2 then after the call order(&n,&m) n should have the value 2, and m the value 7.

Submit the file with your function and the testing code. Your program must compile and run on the dungeon machines. Important: Even if you are familiar with a different C++ style of declaring parameter passing by reference, please use the style that was used in the example in class.

Question 2

Consider the following two C++ loops:

  while(n >= m) {
    n = n - 1;
  }

  while (*p >= *q) {
    *p = *p - 1;
  }

For each of the loop please answer: is it guaranteed to terminate? If yes, please explain why. If not, please write a program that initializes variables used in the loop in such a way that the program goes into an infinite loop (Ctrl-C stops a program).

Problem 3: ML version of traverse

The function traverse defined below is analogous to the Scheme traverse function.

let rec traverse combine action seed = function
  | [] -> seed
  | x :: xs -> combine (action x) (traverse combine action seed (xs));;

do is a reserved word in ML so the corresponding parameter is called action.

Below are two examples of using traverse to define functions on ML lists. Note that, unlike in Scheme, in ML * is an operator, not a function, so you cannot pass it as an argument to traverse. Instead we define a simple function mult and pass it as a parameter. The same needs to be done for +, -, and ::.

let comb x y = x :: y;;
let mult x = x * x;;
let mapsquare = traverse comb mult [];;
mapsquare [1; 5; 7; -2];;

let comb x y = x + y;;
let act x = 1;;
let count x = (traverse comb act 0) x;;

Note a different syntax used to define count (x is used in the definition). This syntax makes a function that can be applied to a list of any type.

Your task is to define the following functions by passing appropriate parameters to traverse:

1. sumlist to sum up elements of an integer list
2. remove5 to remove all 5s from an integer list
3. min to find a minimum of a list integers (you must use traverse). It should return a very large number for an empty list
4. reverse to reverse any list (try it on a list of strings and a list of integers). You may use append function in the lab for this problem.

Writing and using a traverse function for a tree type

You are given the following definition of a tree type and two sample trees:

(* tree type and two sample trees *)

type 'a tree = Empty | Node of 'a * 'a tree * 'a tree;;

let intTree = Node (5, Node (3, Empty, Empty), 
Node (6, Node (7, Empty, Empty), Empty));;

let strTree = Node ("apples", Empty, Node ("bananas", 
Node ("oranges", Empty, Node ("grapes", Empty, Empty)), Empty));;

Question 1

Draw a picture of the two given trees.

Question 2

Write a function traversetree which takes three parameters, combine, action, and seed, and returns a function to perform an operation on a tree, the same way as traverse returns a function that works on lists. Here are more details:

• combine takes 3 parameters: the result of action on a Node and the result of two recursive calls: to the left and to the right subtrees.
• action is applied to the value of a Node
• seed is returned from an empty tree

Use the traversetree function to define the following functions:

1. addtree to add all elements in a tree of integers
2. concattree to concatenate all strings in a tree of strings. The operation ^ performs string concatenation.
3. flattentree to return a list of all elements in a tree. For instance, for the first tree above it should return [5; 3; 6; 7] The order of elements in the list does not matter. Important: the function should work on trees of any type. See count example above for the correct syntax.
4. Extra credit: find that takes a tree and an element and returns true if the element is in the tree and false otherwise. Hint: action should perform the check.
   Note: this is a difficult problem, do not spend too much time on it.

CSci 4651 course web site