CSC 533: Programming Languages
Spring 2019

HW5: Scheme Structures

Late submissions will NOT be accepted for this assignment.

For this assignment, you will modifying and adding to functions that are provided for you in 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 pattern-matching capabilities.

A very basic implementation of Eliza can be found in You begin by evaluating the expression (eliza), and then type in sentences as lists (with all lowercase words and no punctuation). For example,

> (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) RESPONSE:(bye) (Have a nice day) >

Make the following modifications to the Eliza rules:

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

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

  3. 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: (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 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) 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 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-tree?, root, left-subtree, and right-subtree) are provided for you in 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 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.

  3. 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) (else 'UNDEFINED))) apply)

For example:

> (define d8 (Die 8)) > (d8 'roll) 3 > (d8 'roll) 4 > (d8 'roll) 5 > (d8 'num-sides) 8
  1. 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) 3 > (d6 'roll) 4 > (d6 'num-rolls) 2