CSC 533: Organization of Programming Languages
Spring 2005

HW5: Scheme Programming

For this assignment, you are to define the following Scheme functions. For simplicity, place all of your function definitions in a single file named hw5.scm. Be sure to comment each function as to its behavior.

  1. Define functions for converting temperatures from Fahrenheit to Celsius, and vice versa. The formula for converting from Fahrenheit to Celsius is: tempInCelsius = (5/9) * (tempInFahrehneit - 32)

    For example, (fahr->celsius 212) should evaluate to 100, while (celsius->fahr 0) should evaluate to 32.

  2. Define a function named wind-chill that takes two inputs, a temperature (in degrees Fahrenheit) and a wind-speed (in miles per hour), and returns the corresponding wind-chill factor. The formula for computing the wind chill is:

    wind-chill = { temperature if windSpeed <= 3
    35.74 + 0.6215*temperature + (0.4275*temperature-35.75)*windSpeed0.16    otherwise

    For example, (wind-chill 38 2) should evaluate to 38 since a wind-speed of only 2 miles per hour has no effect on the temperature of 38 degrees Fahrenheit.

  3. Define a function named num-occur that takes two inputs, an atom and a list, and returns a count of the number of times the atom appears in the list. For example, (num-occur 'x '(z x e x)) should evaluate to 2.

  4. Define a function named remove that takes two inputs, an atom and a list, and returns the list with each occurrence of the atom removed. For example, (remove 'x '(z x e x)) should evaluate to (z e).

  5. Define a function named subst that takes three inputs, two atoms and a list, and returns the list with each occurrence of the second atom replaced by the first. For example, (subst 'a 'x '(z x e x)) should evaluate to (z a e a).

  6. Define a function named num-atoms that takes one input, a list containing arbitrarily nested lists of atoms, and returns the number of atoms in the list. For example, (num-atoms '(a b c)) should evaluate to 3, while (num-atoms '(a (b (d e) c))) should evaluate to 5.

  7. Define functions for converting roman numerals to numbers and back. One function, roman->num will have one input, a list of characters representing a roman numeral. It should return the number value represented by that roman numeral. For example, (roman->num '(X V I)) should evaluate to 16. Conversely, the function num->roman will have an integer as input, and should return the list of characters representing the appropriate roman numeral. The following is a list of the roman letters and numbers they represent: M = 1000, D = 500, C = 100, L = 50, X = 10, V = 5, I = 1.

    You may assume the old roman style of writing letters, where 4 is represented IIII and 90 is represented LXXXX. A harder problem, which you may attempt if you like, is to use the modern roman style where 4 is IV and 90 is XC.

  8. In class, we discussed how structured lists could be used to represent binary trees. Define a function named bst? that takes one input, a list containing numbers, and returns true if that list represents a binary search tree (assuming the tree format described in class). Recall that a binary search tree is a binary tree in which, for every node, the data in that node is greater than or equal to all data in its left subtree, and less than all data in its right subtree. For example, (bst? '(5 (3 () ()) (9 (8 () ()) (10 () ()))) should evaluate to #t, while (bst? '(5 (3 () ()) (9 (4 () ()) (10 () ()))) and (bst? '(5 (3 () ()) 9) should evaluate to #f.

  9. The following function simulates a random 1-dimensional walk. Initially, the walker is assumed to be at position 0. Depending on a random value, the walker either moves to the right (in the positive direction) or to the left (in the negative direction). The simulation ends when the walker reaches the specified goal distance, in either direction. (define (random-walk goal-dist) (define (random-walk-help position goal) (display position) (newline) (cond ((= (abs position) goal) #t) ((zero? (random 2)) (random-walk-help (add1 position) goal)) (else (random-walk-help (sub1 position) goal)))) (random-walk-help 0 goal-dist))

    As is, this function displays each step in the walk and returns #t when the walk ends. Modify the function so that it keeps track of the number of steps in the walk and returns this value instead. Your modification should only utilize tail-recursion.

  10. An interesting unsolved problem in mathematics concerns what is called the hailstone sequence of integers. This sequence is defined as follows: start with any integer. If that number is odd, then multiply it by 3 and add 1. If it is even, then divide it by 2. Now, repeat. For example, if we start with the number 5, we get the following sequence: 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, . . . Here, the subsequence 4, 2, 1 is reached which produces a loop. It is conjectured that no matter what number you start with, you will always end up stuck in the 4, 2, 1 loop. It has, in fact, been shown to hold for all starting values less than 1,200,000,000,000 . However, it still has not been proven for all numbers. Define a function named hailstone which has one input, the starting number, and which displays the hailstone sequence starting with that number and ending with 1. The function should return the length of the sequence. For example, (hailstone 1) should display the lone number 1 and evaluate to 1, while (hailstone 5) should display 5 16 8 4 2 1 and evaluate to 6. Your function should only utilize tail-recursion (perhaps a help function will be required).