CSC 533: Programming Languages
Spring 2022
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 LASTNAME-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: 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
maps each codon (represented by a triplet of
base symbols) to the abbreviation for the corresponding amino acid.
(define ACIDS
'( ((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 functions to your LASTNAME-hw6.scm
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
arbitrarily 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).
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 arbitrary binary trees.
- Define a function named rightmost that takes one input, a list
representing a binary tree, and returns the rightmost value in the tree.
For example, given the ANIMALS structure above, (rightmost ANIMALS) should
evaluate to possum.
- Define a function named leftmost that takes one input, a list
representing a binary tree, and returns the leftmost value in the tree.
For example, given the ANIMALS structure above, (leftmost ANIMALS) should
evaluate to horse.
- Define a function named height that takes one input, a list
representing a binary tree, and returns the height of that tree. Recall that the height of a tree is the number of nodes on the longest path from the root to a leaf. For example, given the ANIMALS
structure above, (height ANIMALS) should evaluate to 3.
Recall the following definitions from Data Structures:
- A binary search tree is a binary tree where, for every node in the tree, the values in its left subtree are smaller than the node value and the values in its right subtree are greater than or equal to the node value.
- A relatively-balanced binary tree is a binary tree where, for every node in the tree, the height of its left and right subtrees differ by at most 1.
- An AVL tree is a relatively-balanced binary search tree.
For example, the tree below is a binary search tree, but is not balanced. Thus, it is not an AVL tree.
|
(define NUMS
'(8
(6 (5 () ()) (7 () ()))
(12 () (15 (14 () ()) ()))))
|
Add the following functions for manipulating binary trees containing numbers:
- Define a function named is-bst? that takes one input, a list of numbers
representing a binary tree, and returns #t if that list
is a binary search tree (otherwise #f). For example, given the NUMS
structure above, (is-bst? NUMS) should evaluate to #t.
- Define a function named is-balanced? that takes one input, a list of numbers
representing a binary tree, and returns #t if that list
is relatively-balanced (otherwise #f). For example, given the NUMS
structure above, (is-balanced? NUMS) should evaluate to #f.
- Define a function named is-avl? that takes one input, a list of numbers
representing a binary tree, and returns #t if that list
is an AVL tree (otherwise #f). For example, given the NUMS
structure above, (is-avl? NUMS) should evaluate to #f.
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 die object, where the number of sides is specified when creating the die.
(define (Die num-sides)
(define roll-count 0)
(define (apply op)
(cond ((equal? op 'roll) (begin (set! roll-count (+ 1 roll-count))
(+ 1 (random num-sides))))
((equal? op 'num-sides) num-sides)
((equal? op 'num-rolls) roll-count)
(else 'UNDEFINED)))
apply)
For example:
> (define d8 (Die 8))
> (d8 'roll)
3
> (d8 'num-sides)
8
> (d8 'roll)
4
> (d8 'roll)
7
> (d8 'num-rolls)
3
- Redefine your count-dice function from HW5 to utilize the above "class." Recall that this function takes three inputs, the number of die sides, the number of rolls, and the desired dice total. For example, (count-dice 6 1000 7) should simulate 1,000 rolls of two 6-sided dice and return the number of 7's obtained. As before, this function must utilize tail-recursion.