CSC 533: Organization of Programming Languages
Spring 2017

HW4: Scheme Programming I


For this assignment, you are to define the following Scheme functions. For simplicity, place all of your function definitions in a single file named YOURNAME-hw4.ss, where YOURNAME is your name. Be sure to comment each function as to its behavior.

Numerical Functions

  1. Define a function named windChill 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:

    windChill = { temperature if windSpeed <= 3
    35.74 + 0.6215*temperature + (0.4275*temperature-35.75)*windSpeed0.16    otherwise
  2. Define a predicate function named leap-year that takes one input, a positive integer representing a year, and returns #t if it is a leap year (otherwise, #f). In general, years that are evenly divisible by 4 are leap years, unless they are divisible by 100 but not 400. For example, (leap-year 2008) and (leap-year 2000) should evaluate to #t, but (leap-year 2009) and (leap-year 2100) should evaluate to #f.

  3. Define a function named days-in-year that takes one input, a positive integer representing a year, and returns the number of days in that year. For example, (days-in-year 2008) should evaluate to 366 since it is a leap year, but (days-in-year 2100) should evaluate to 365 since it is not.

  4. Define a function named total-days that takes two inputs, the starting and ending years in a range, and returns the total number of days in that range. You may assume that both inputs are positive integers, and that the first input is less than or equal to the second. For example, (total-days 2008 2010) should evaluate to 1096 since the years in the range consist of 366, 365, and 365 days, respectively.

List Functions

  1. 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 ancient 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.

  2. Define a function named numCount1 that takes one input, a list containing arbitrary values, and returns a count of how many list elements are numbers. For example, (numCount1 '(z 4 (a 3) 2 foo)) should evaluate to 2.

  3. Define a more general function named numCount2 that takes one input, a list containing arbitrary values, and returns a count of how many numbers appear anywhere in the list (including in nested sublists). For example, (numCount2 '(z 4 (a 3) 2 foo)) should evaluate to 3.

Dice Simulations

The built-in random function generates a pseudo-random integer from 0 up to its input (exclusive). For example, the call (random 4) would return either 0, 1, 2, or 3. Using this function, write the following functions for simulating coin flips.

  1. Define a function named dice-roll that has no inputs and simulates the roll of two six-sided dice. That is, the call (dice-roll) should return an integer from the range 2 through 12, following the appropriate probability distribution (e.g., 7 is the most likely roll, 2 and 12 are the least likely).

  2. Define a function named average-rolls that takes one input, a positive integer, and simulates that many rolls of the dice, returning the average of all of those rolls. For example, the call (average-rolls 1000) should simulate 1000 dice rolls and return the average. Since the number of rolls could be large, your function should utilize tail-recursion.

  3. Define a function named count-dice that takes two inputs, a number of rolls and the desired total. The function should simulate the specified number of rolls and return the number of times the desired total was obtained. For example, the call (count-dice 1000 7) should simulate 1000 dice rolls and return the number of times 7 was rolled. Since the number of rolls could be large, your function should utilize tail-recursion.

Recursive Square Root

Scheme provides the built-in function sqrt that returns the square root of its input. For example, (sqrt 9) will evaluate to 3. For now, ignore this function and write your own. One method for approximating the square root of a number is Newton's algorithm. According to this algorithm, in order to find the square root of some number N, first start with an initial guess of 1. Then improve upon that old guess using a new guess that is the average of the old guess and N/(old guess). By repeatedly improving upon the previous guess in this way, you get closer and closer to the actual square root. For example, in order to approximate the square root of 9, start with 1, then 5 (the average of 1 and 9/1), then 17/5 (the average of 5 and 9/5), etc.

Consider the following function for computing the square root of a number using Newton's method. The second input, reps, is used to specify how many repeated improvements are to be made on the initial guess.

(define (newton-sqrt n reps) (define (newton-sqrt-help guess reps-left) (if (zero? reps-left) guess (newton-sqrt-help (improve guess n) (sub1 reps-left)))) (newton-sqrt-help 1 reps))
  1. Define a function named improve that improves upon the old guess as described above. Type in newton-sqrt and use it to approximate the square roots of various numbers.

  2. Having to decide ahead of time how many repeated improvements are to be made is not very desirable. Instead, we would like the function to repeatedly improve the guess until the guess is "close enough" (in some sense). For our purposes, we will consider a guess to be close enough if its square is within .001 of the input number. Define a predicate function named close-enough? that does this, and alter newton-sqrt to make use of this stopping condition.