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.

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

  1. 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.
  2. 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.
  3. 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:

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:

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