CSC 533: Programming Languages
Late submissions will NOT be accepted for this assignment.
HW5: Scheme Structures
For this assignment, you will modifying and adding to functions that are provided for you in hw5.ss. Download this file and enter your name in the comment at the top.
PART 1: Eliza
One of the most famous/infamous programs from Artificial Intelligence was
Joseph Weizenbaum's Eliza. Written in 1966, the Eliza program was intended to
demonstrate the superficiality of AI programs at the time. Despite its lack of deep
understanding, the program became extremely popular and earned a place in AI history.
The Eliza program is intended to simulate an interview with psychotherapist.
The user interacts with
the therapist by entering a comment or question, to which the therapist responds with a
comment or question of its own. Despite the fact that the program utilizes no language
understanding, it is able to often to produce realistic responses due to its
A very basic implementation of Eliza can be found in hw5.ss.
You begin by evaluating the expression > (eliza)
(how can i help you today)
RESPONSE:(last night i dreamed about parentheses)
(have you dreamed about parentheses before)
RESPONSE:(no but i have been writing lots of scheme code)
(you are being a bit negative)
RESPONSE:(i am tired and cranky)
(do you want to be tired and cranky)
(Have a nice day)
(eliza), and then type in sentences as lists (with all lowercase words and no punctuation). For example,
Make the following modifications to the Eliza rules:
- The Eliza rules currently include a rule that looks for the word "computer", and
responds accordingly. However, this rule will not catch the plural "computers". Add a
rule to the database that similarly responds to user input containing "computers".
- Add a rule to the Eliza rule database that recognizes the phrase "I miss ___" in the
user's input. When this phrase is found anywhere in the user input, Eliza should
respond with either "Do you miss other things" or else a response of the form
"What do you miss about ___".
- Add at least three more rules to the Eliza rule database of your own design. Add a comment next to each new rule to identify it.
PART 2: Molecular Weight
The periodic table, which identifies each element and its atomic weight, is listed below as a Scheme association list:
'((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 hw5.ss file. Add the following definitions to the file.
- 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) of that element. For example, (atomic-number 'H) should evaluate to 1 while (atomic-number 'O) should evaluate to 8.
- 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.
- 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.
- 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.
- 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 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:
(bird (horse () ()) (cat () ()))
(possum (dog () ()) ())))
Several utility functions (empty-tree?, root, left-subtree,
and right-subtree) are provided for you in hw5.ss). 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 (i.e., maximum root-to-leaf path length) in the tree.
For example, given the ANIMALS structure above, (height ANIMALS) should
evaluate to 3.
- Define a function named num-occur that takes two inputs, a list
representing a binary tree and a value, and returns the number of occurrences of the value in that tree.
For example, given the ANIMALS structure above, (num-occur ANIMALS 'dog) should
evaluate to 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.
PART 4: 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 die object, where the number of sides is specified when creating the die.
(define (Die num-sides)
(define (apply op)
(cond ((equal? op 'roll) (+ 1 (random num-sides)))
((equal? op 'num-sides) num-sides)
> (define d8 (Die 8))
> (d8 'roll)
> (d8 'roll)
> (d8 'roll)
> (d8 'num-sides)
- Modify the code so that there is an additional "method" named
num-rolls, which returns the number of times that die object has been rolled. Note: this will involve using non-functional features of Scheme, which is allowable in this instance since those features are hidden inside the object. In particular, you should add a variable definition inside the
Die function, initialized to 0. When the
roll "method" is called, you will need to update that field (using
set!). Also, you should add a
num-rolls "method" to enable the user to access the number of times the die has been rolled. For example:
> (define d6 (Die 6))
> (d6 'roll)
> (d6 'roll)
> (d6 'num-rolls)