CSC 533: Programming Languages
Spring 2014
HW4: Scheme Programming
For this assignment, you are to define numerous Scheme functions. For
simplicity, place all of your function definitions in a single file named
hw4.ss. Be sure to include a comment block at the top of the file containing you rname and also comment each function as to its behavior.
Part 1: Scheme functions
- Define functions for converting between inches and centimeters, and between
pounds and kilograms (and vice versa for each). Recall that 1 inch = 2.54 centimeters and 1 pound =
0.45359237 kilograms.
For example, (in->cm 10) should evaluate to
25.4, while (kg->lb 10) should evaluate to 22.0462262.
- Body Mass Index (BMI) is often used by doctors and dieticians in
assessing the overall health of a patient. The formula is as follows:
BMI = (weight in kilograms) / (height in meters)2
Define a function named BMI-Metric that takes two inputs, a person's
height (in centimeters) and weight (in kilograms), and returns his/her BMI.
For example, (BMI-Metric 170.0 70.0) should evaluate to
approximately 24.22.
Similarly, define a function named BMI-American that takes two inputs, a person's
height (in inches) and weight (in pounds), and returns his/her BMI.
For example, (BMI-American 65.0 170.0) should evaluate to
approximately 28.29. Note: you should be able to make use of the BMI-Metric function
here.
- According to the Center for Disease Control, body mass index correlates to
the following weight categories:
BMI < 18.5 | underweight
|
18.5 ≤ BMI < 25.0 | normal
|
25.0 ≤ BMI < 30.0 | overweight
|
30.0 ≤ BMI | obese
|
Modify your BMI-Metric and BMI-American functions so that instead of
returning a single number, they each return a list containing the BMI and the weight status.
For example, (BMI-Metric 170.0 70.0) should evaluate to
approximately (24.22 normal)
, while (BMI-American 65.0 170.0) should evaluate to
approximately (28.29 overweight)
.
- 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. For example, (num->roman 77) should evaluate to (L X X V
I I).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 for extra credit, is to use the modern roman style where
4 is IV and 90 is XC.
Part 2: Association Lists
In biology, the four bases that make up messenger RNA (mRNA) are adenine (A),
cytosine (C), guanine (G), and uracil (U). Within a cell, an mRNA sequence
is processed by a ribosome and translated into amino acids. Each grouping of 3
bases is known as a codon, and is translated to a particular amino acid.
For example, the codon GCU translates to Alanine.
The following Scheme association list
maps each codon (represented by a triplet of
base symbols) to the abbreviation for the corresponding amino acid.
(define ACIDS
'( ((U U U) F) ((U U C) F) ((U U A) L) ((U U G) L)
((U C U) S) ((U C C) S) ((U C A) S) ((U C G) S)
((U A U) Y) ((U A C) Y) ((U A A) *) ((U A G) *)
((U G U) C) ((U G C) C) ((U G A) *) ((U G G) W)
((C U U) L) ((C U C) L) ((C U A) L) ((C U G) L)
((C C U) P) ((C C C) P) ((C C A) P) ((C C G) P)
((C A U) H) ((C A C) H) ((C A A) Q) ((C A G) Q)
((C G U) R) ((C G C) R) ((C G A) R) ((C G G) R)
((A U U) I) ((A U C) I) ((A U A) I) ((A U G) M)
((A C U) T) ((A C C) T) ((A C A) T) ((A C G) T)
((A A U) N) ((A A C) N) ((A A A) K) ((A A G) K)
((A G U) S) ((A G C) S) ((A G A) R) ((A G G) R)
((G U U) V) ((G U C) V) ((G U A) V) ((G U G) V)
((G C U) A) ((G C C) A) ((G C A) A) ((G C G) A)
((G A U) N) ((G A C) N) ((G A A) E) ((G A G) E)
((G G U) G) ((G G C) G) ((G G A) G) ((G G G) G) ))
Copy-and-paste this association list into your file and add the following definitions.
- Define a function named translate that takes one input, a list
representing a codon, and returns the abbreviation for the corresponding
amino acid. For example, (translate '(G G A)) should evaluate to G.
- Define a function named translate-sequence that takes one input, an
arbitrarly long sequence of bases, and returns the corresponding list of amino acid
abbreviations. That is, the first symbol in the returned list should be the amino acid
corresponding to the first three bases, the second symbol should be the amino
acid corresponding to the next three bases, etc. If the length of the sequence
is not a multiple of three, any trailing bases should be ignored. For example,
(translate-sequence '(G G A U U C A C C C)) should evaluate to (G F T).
- When scientists extract mRNA samples from a cell, they invariably obtain
partial sequences. Since the start of the sequence may be unknown, it is unclear
exactly how the codons will be grouped in an actual translation. For example, in the sequence
GGAUUCACCC the codons could be grouped starting at the beginning
(yielding codons GGA UUC ACC), at the second base (yielding codons GAU UCA CCC),
or at the third base (yielding codons AUU CAC). In addition, it is possible that the
sequence has been read backwards, so the actual sequence to be translated should be
CCCACUUAGG.
Define a function named translate-all-possible that takes one input, an
arbitrarly long sequence of bases, and returns a list containing all six possible
translations of that sequence. Any extra bases at the beginning or end of the sequence
should be ignored in the translation. For example,
(translate-all-possible '(G G A U U C A C C C)) should evaluate to
((G F T) (N S P) (I H) (P T *) (P L R) (H L)).
Part 3: Binary Trees
In class, we discussed how structured lists could be used to represent
binary trees. For example, the following binary tree is represented by the
list to the right:
|
(define ANIMALS
'(dog
(bird (horse () ()) (cat () ()))
(possum (dog () ()) ())))
|
Several utility functions (empty?, root, left-subtree,
and right-subtree) were provided for you in the lecture notes.
Copy-and-paste these functions into your file and add the following functions for manipulating binary trees.
- Define a function named height that takes one input, a list
representing a binary tree, and returns the height of that tree. For example, given the ANIMALS
structure above, (height ANIMALS) should evaluate to 3.
- Define a function named contains? that takes two inputs, a list
representing a binary tree and an atom, and returns #t if the list
contains the atom (otherwise #f). For example, given the ANIMALS
structure above, (contains? ANIMALS 'emu) should evaluate to #f
while (contains? ANIMALS 'cat) should evaluate to #t.
- Define a function named num-occur that takes two inputs, a list
representing a binary tree and an atom, and returns the number of occurrences of the atom in that tree.
For example, given the ANIMALS structure above, (num-occur ANIMALS 'dog) should
evaluate to 2.