CSC 533: Programming Languages
Spring 2021

HW6: Scheme Structures

Late submissions will NOT be accepted for this assignment.

For this assignment, you will modify and add to functions that are provided for you in hw6.scm. Download this file, rename it YOURNAME-hw6.scm and enter your name in the comment at the top. Be careful to name your functions exactly as defined in the exercises, and be sure to comment each function as to its behavior.

PART 1: Molecular Weight

The periodic table, which identifies each element and its atomic weight, is listed below as a Scheme association list: (define PERIODIC-TABLE '((H Hydrogen 1.0080) (He Helium 4.0026) (Li Lithium 6.9410) (Be Beryllium 9.0122) (B Boron 10.8100) (C Carbon 12.0110) (N Nitrogen 14.0067) (O Oxygen 15.9994) (F Fluorine 18.9984) (Ne Neon 20.1790) (Na Sodium 22.9898) (Mg Magnesium 24.3050) (Al Aluminum 26.9815) (Si Silicon 28.0860) (P Phosphorus 30.9738) (S Sulfur 32.0600) (Cl Chlorine 35.4530) (Ar Argon 39.9480) (K Potassium 39.1020) (Ca Calcium 40.0800) (Sc Scandium 44.9559) (Ti Titanium 47.9000) (V Vanadium 50.9414) (Cr Chromium 51.9960) (Mn Manganese 54.9380) (Fe Iron 55.8470) (Co Cobalt 58.9332) (Ni Nickel 58.7100) (Cu Copper 63.5460) (Zn Zinc 65.3700) (Ga Gallium 69.7200) (Ge Germanium 72.5900) (As Arsenic 74.9216) (Se Selenium 78.9600) (Br Bromine 79.9040) (Kr Krypton 83.8000) (Rb Rubidium 85.4678) (Sr Strontium 87.6200) (Y Yttrium 88.9059) (Zr Zirconium 91.2200) (Nb Niobium 92.9064) (Mo Molybdenum 95.9400) (Tc Technetium 98.9062) (Ru Ruthenium 101.0700) (Rh Rhodium 102.9055) (Pd Palladium 106.4000) (Ag Silver 107.8680) (Cd Cadmium 112.4000) (In Indium 114.8200) (Sn Tin 118.6900) (Sb Antimony 121.7500) (Te Tellurium 127.6000) (I Iodine 126.9045) (Xe Xenon 131.3000) (Cs Caesium 132.9055) (Ba Barium 151.9600) (La Lanthanum 138.9055) (Ce Cerium 140.1160) (Pr Praseodymium 140.9077) (Nd Neodymium 144.2420) (Pm Promethium 145.0000) (Sm Samarium 150.3600) (Eu Europium 151.9640) (Gd Gadolinium 157.2500) (Tb Terbium 158.9254) (Dy Dysprosium 162.5000) (Ho Holmium 164.9303) (Er Erbium 167.2590) (Tm Thulium 168.9342) (Yb Ytterbium 173.0450) (Lu Lutetium 174.9669) (Hf Hafnium 178.4900) (Ta Tantalum 180.9479) (W Tungsten 183.8500) (Re Rhenium 186.2000) (Os Osmium 190.2000) (Ir Iridium 192.2200) (Pt Platinum 195.0900) (Au Gold 196.9665) (Hg Mercury 200.5900) (Tl Thallium 204.3700) (Pb Lead 207.2000) (Bi Bismuth 208.9806) (Po Polonium 210.0000) (At Astatine 210.0000) (Rn Radon 222.0000) (Fr Francium 223.0000) (Ra Radium 226.0254) (Ac Actinium 227.0000) (Th Thorium 232.0381) (Pa Protactinium 231.0359) (U Uranium 238.0289) (Np Neptunium 237.0482) (Pu Plutonium 242.0000) (Am Americium 243.0000) (Cm Curium 247.0000) (Bk Berkelium 249.0000) (Cf Californium 251.0000) (Es Einsteinium 252.0000) (Fm Fermium 257.0000) (Md Mendelevium 258.0000) (No Nobelium 259.0000) (Lr Lawrencium 266.0000) (Rf Rutherfordium 267.0000) (Db Dubnium 268.0000) (Sg Seaborgium 269.0000) (Bh Bohrium 270.0000) (Hs Hassium 270.0000) (Mt Meitnerium 278.0000) (Ds Darmstadtium 281.0000) (Rg Roentgenium 282.0000) (Cn Copernicium 285.0000) (Nh Nihonium 286.0000) (Fl Flerovium 289.0000) (Mc Moscovium 290.0000) (Lv Livermorium 293.0000) (Ts Tennessine 294.0000) (Og Oganesson 294.0000) ))

This association list is also included in the downloaded hw6.scm file. Add the following definitions to the file.

  1. Define a function named atomic-number that takes one input, the symbol for an element, and returns the atomic number (i.e., its position in the table, starting at 1) of that element. For example, (atomic-number 'H) should evaluate to 1 while (atomic-number 'O) should evaluate to 8.

  2. Define a function named atomic-weight that takes one input, the symbol for an element, and returns the atomic weight of that element. For example, (atomic-weight 'H) should evaluate to 1.008 while (atomic-weight 'O) should evaluate to 15.9994.

  3. Define a function named molecular-weight1 that takes one input, a list of element symbols, and returns the molecular weight (i.e., the sum of all of the atomic weights) for that list. For example, (molecular-weight1 '(Na Cl)) should evaluate to 58.4428 while (molecular-weight1 '(H H O)) should evaluate to 18.0154.

  4. When writing formulas for molecules in which an element appears multiple times, scientists use subscripts to denote repetition. For example, the formula for water is written H2O instead of HHO. Copy your molecular-weight1, rename it molecular-weight2, and modify it to handle lists in which an element may be followed by a number. For example, (molecular-weight2 '(H 2 O)) should evaluate to 18.0154.

  5. Complex formulas can contain nested sub-formulas. For example, the formula for isopropyl alcohol is (CH3)2CHOH. Copy your molecular-weight2, rename it molecular-weight3, and modify it to handle nested lists. For example, (molecular-weight3 '((C H 3) 2 C H O H)) should evaluate to 60.0964.

PART 2: 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-tree?, root, left-subtree, and right-subtree) are provided for you in hw6.scm). 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 (i.e., maximum root-to-leaf path length) in the 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 a value, and returns #t if the list contains the value (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 has-dupes? that takes a binary tree as input and returns #t if any item appears more than once in the tree. For example, (has-dupes? ANIMALS) should evaluate to #t, since the symbol dog appears more than once in the tree.

PART 3: OOP in Scheme

In class, we discussed how first-class functions and closures could support the equivalent of classes, with private data and methods. The following function models a weighted coin, where the expected percentage of HEADS (an integer between 0 and 100) is speccified.

(define (Coin head-percent) (define (apply op) (cond ((equal? op 'flip) (if (< (random 100) head-percent) 'HEADS 'TAILS)) ((equal? op 'percent) head-percent) (else 'UNDEFINED))) apply)

For example:

> (define dime (Coin 50)) > (dime 'flip) HEADS > (dime 'flip) TAILS > (dime 'flip) TAILS > (dime 'flip) HEADS > (dime 'percent) 50
  1. To test that the weighted coin object behaves as desired, define a function named check that takes two inputs, a coin object and a number of flips. The function should simulate the specified number of coin flips and return the percentage of flips that were HEADS. Since the number of flips could be large, your function should utilize tail-recursion. For example:
    2. > (define penny (Coin 50)) > (check penny 10000) 49.6 > (define nickel (Coin 25)) > (check nickel 100000) 25.085
  2. Modify the Coin function so that there is an additional "method" named num-flips, which returns the number of times that coin object has been flipped. Note: this will involve using non-functional features of Scheme, which is permissible in this instance since those features are hidden inside the object. In particular, you should add a "field" (a variable defined to be 0) inside the Coin function. When the flip "method" is called, you will need to update that field (using set!). Also, you should add a num-flips "method" (by adding another cond option in the nested apply function) to enable the user to access the number of times the die has been rolled. For example: > (define quarter (Coin 50)) > (quarter 'flip) TAILS > (quarter 'flip) TAILS > (quarter 'num-flips) 2