CSC 533: Programming Languages
Late submissions will NOT be accepted for this assignment.
HW5: Scheme Structures
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), 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:
- 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 1: DNA Translations
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 (defined in hw5.ss)
maps each codon (represented by a triplet of
base symbols) to the abbreviation for the corresponding amino acid.
'( ((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) ))
Add the following definitions to your
hw5.ss file. Note: you should comment
each function with a description of its behavior.
- 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.
- 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).
- 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
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:
(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.