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
- 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
|
- 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.
- 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.
- 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
- 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.
- 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.
- 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.
- 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).
- 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.
- 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))
- 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.
- 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.