CSC 533: Programming Languages
Spring 2026

HW6: Clojure Structures

Note: 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.clj. Download this file, rename it YOURNAME-hw6.clj and enter your name in the comment at the top. Be careful to name your functions exactly as defined in the exercises.

PART 1: DNA Translations

Add the following functions to your LASTNAME-hw6.scm file. Hint: It is straightforward to convert a string to list of characters, e.g., (seq "abc") evaluates to (\a \b \c), and vice versa, e.g., (clojure.string/join '(\a \b \c)) evaluates to "abc".

1. Define a function named translate that takes one input, a string representing a codon, and returns the abbreviation for the corresponding amino acid. For example, (translate "GGA") should evaluate to "G".
2. Define a function named translate-sequence that takes one input, a string of bases, and returns the corresponding string of amino acid abbreviations. That is, the first character in the returned string should be the amino acid corresponding to the first codon (i.e., the first three bases), the second character should be the amino acid corresponding to the next codon, etc. If the length of the sequence string is not a multiple of three, any trailing bases should be ignored. For example, (translate-sequence "GGAUUCACCC") should evaluate to "GFT".
3. 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" and "ACC"), at the second base (yielding codons "GAU", "UCA" and "CCC"), or at the third base (yielding codons "AUU" and "CAC"). In addition, it is possible that the sequence has been read backwards, so the actual sequence to be translated could be "CCCACUUAGG". Define a function named translate-all-possible that takes one input, a string 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 string should be ignored in the translation. For example, (translate-all-possible "GGAUUCACCC") should evaluate to ("GFT" "NSP" "IH" "PT*" "PLR" "HL").

PART 2: Binary Trees

In class, we discussed how structured lists could be used to represent binary trees. For example, the following lists represent a tree of animal names (strings) and a tree of numbers, respectively.

    (def ANIMALS                 
       '("dog"                                 
         ("bird" ("horse" () ()) ("cat" () ()))   
         ("possum" ("dog" () ()) ()))) 
    
    (def NUMBERS
       '(2 (-1 () ()) (3 () ())))

Several utility functions (root, left-subtree, and right-subtree) are provided for you in the homework file. 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 heights of its left and right subtrees differ by at most 1.
• An AVL tree is a relatively balanced binary search tree.

Add the following functions for traversing and classifying binary trees:

4. 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, (rightmost ANIMALS) should evaluate to "possum". Note: since an empty tree does not have a rightmost element, the function should return nil when applied to an empty tree.
5. 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, (leftmost ANIMALS) should evaluate to "horse". Note: since an empty tree does not have a leftmost element, the function should return nil when applied to an empty tree.
6. Define a function named is-bst? that takes one input, a list representing a binary tree, and returns true if that list is a binary search tree (otherwise false). For example, (is-bst? NUMBERS) should evaluate to true, while (is-bst? ANIMALS) should evaluate to false.
7. Define a function named is-rel-balanced? that takes one input, a list representing a binary tree, and returns true if that list is relatively balanced (otherwise false). For example, (is-rel-balanced? ANIMALS) and (is-rel-balanced? NUMBERS) should both evaluate to true.
8. Define a function named is-avl? that takes one input, a list representing a binary tree, and returns true if that list is an AVL tree (otherwise false). For example, (is-avl? NUMBERS) should evaluate to true, while (is-avl? ANIMALS) should evaluate to false.

PART 3: OOP in Clojure

In class, we discussed how Clojure allows for the definition of "classes" via protocols and type definitions. For example, consider the following definitions for implementing a Coin class (also in the provided homework file).

For example:

9. Reimplement the count-heads function from the lectures to utilize the above "class." Your new function should take two inputs, a coin and a number of flips, and return the number of heads obtained from the simulated flips. For example, you would expect (count-heads (make-coin) 1000) to return a number close to 500. Since the number of flips could be large, this function must utilize tail-recursion.
10. Define a function named flip-until-same that simulates flipping three coins, printing the value of each flip, and stopping when all three flips are identical. It should return the number of flips. For example, if penny, nickel and dime are coins, then (flip-until-same penny nickel dime) might produce the following:
(flip-until-same penny nickel dime) :HEADS :TAILS :TAILS :TAILS :HEADS :TAILS :HEADS :TAILS :HEADS :HEADS :HEADS :HEADS => 4