### 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

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

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

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

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

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

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

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

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

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

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