CSC 533: Programming Languages
Spring 2017

HW5: Advanced Scheme

Note: late submissions will NOT be accepted for this final assignment.

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 hw5.scm. You begin by evaluating the expression (eliza), and then type in sentences as lists (with all lowercase words and no punctuation). For example,

Download a copy of this file and 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 hate ___" in the user's input. When this phrase is found anywhere in the user input, Eliza should respond with either "Hate is such an intense emotion" or else a response of the form "What is it that you hate about ___".

  3. Add at least three more rules to the Eliza rule database of your own design.

PART 2: Association Lists

On the Web, a color is usually referred to using its RGB value - a triple defining the red, blue, and green (respectively) intensities for that color. For example, red is represented as (255 0 0) and orange as (255 119 0). The following association list, which is defined in hw5.ss, contains several common colors along with their RGB values. (define COLORS '((black (0 0 0)) (gray (128 128 128)) (blood-red (102 0 0)) (blue (0 0 255)) (green (0 255 0)) (indigo (102 0 255)) (orange (255 119 0)) (red (255 0 0)) (violet (79 47 79)) (white (255 255 255)) (violet-red (204 50 153)) (yellow (255 255 0))))

  1. Define a function named getRGB that takes one input, the name of a color, and returns the RGB list for that color. For example, (getRGB 'yellow) should evaluate to (255 255 0). If a color name is provided that is not stored in the association list, the function should return a list of question marks, i.e., (? ? ?).

  2. Define a function named getComponent that takes two inputs, an expression representing a color (either an RGB triple or a color name) and the desired component (either 'R, 'G, or 'B). The function should return the appropriate RGB component for that color (or ? if that color is not recognized). For example, (getComponent 'violet 'R) should evaluate to 79, while (getComponent '(100 150 200) 'G) should evaluate to 150.

  3. When a color image is converted to grayscale, this is accomplished by replacing each pixel with a pixel whose three RGB intensities are the same. In particular, each component is the average of the three color components. Define a function named make-gray that takes one input, an expression representing a color (either an RGB triple or a color name), and returns the corresponding grayscale color. For example, (make-gray 'red) should evaluate to (85 85 85), while (make-gray '(120 140 135)) should evaluate to (132 132 132).

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 hw5.ss). Add the following functions for manipulating binary trees.

  1. Define a function named numValues that takes one input, a list representing a binary tree, and returns the number of values in the tree. For example, given the ANIMALS structure above, (numValues ANIMALS) should evaluate to 6.

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

  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.

  4. 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: Lazy Streams

Bizz-buzz is a children's game in which a circle of people take turns counting out numbers, but with a wrinkle. Two numbers are selected ahead of time, say 3 and 5. When counting out numbers, multiples of the first selected number (3) must be replaced with "bizz." Likewise, multiples of the second selected number (5) must be replaced by "buzz," and multiples of both (3 and 5) must be replaced by "bizz-buzz." For example:

1 2 bizz 4 buzz bizz 7 8 bizz buzz 11 bizz 13 14 bizz-buzz 16 17 ... If the numbers 5 and 7 were instead selected, the sequence would be: 1 2 3 4 bizz 6 buzz 8 9 bizz 11 12 13 buzz bizz 16 17 18 19 bizz ...

You are to define Scheme functions that can be used to generate streams that represent bizz-buzz sequences.

  1. Define a function named replaceStream that takes three inputs, a function, a value, and a stream. This function should behave similarly to the filterStream function written in class, except that instead of filtering the input stream based on the function, it replaces each qualifying element with the new value. For example: > (define naturals (arithSequence 1 1)) > (lazyHead naturals 10) (1 2 3 4 5 6 7 8 9 10) > (lazyHead (replaceStream even? 'boo naturals) 10) (1 boo 3 boo 5 boo 7 boo 9 boo) > (lazyHead (replaceStream (lambda (x) (and (>= x 3) (<= x 7))) 0 naturals) 15) (1 2 0 0 0 0 0 8 9 10 11 12 13 14 15)
  2. Define a function named bbSeq that takes two inputs, the selected numbers, and returns the stream representing the corresponding bizz-buzz sequence. Note that constructing a particular bizz-buzz stream can be accomplished by starting with the natural number stream, then repeatedly transforming it (using replaceStream) so that multiples of the specified numbers are replaced the corresponding words. For example:
> (lazyHead (bbSeq 3 5) 20) (1 2 bizz 4 buzz bizz 7 8 bizz buzz 11 bizz 13 14 bizz-buzz 16 17 bizz 19 buzz) > (lazyHead (bbSeq 3 7) 21) (1 2 bizz 4 5 bizz buzz 8 bizz 10 11 bizz 13 buzz bizz 16 17 bizz 19 20 bizz-buzz)