Homework 6: Scheme, Scheme Data Abstraction

hw06.zip

Due by 11:59pm on Thursday, August 3

Instructions

Download hw06.zip. Inside the archive, you will find a file called hw06.scm, along with a copy of the ok autograder.

Submission: When you are done, submit the assignment by uploading all code files you've edited to Gradescope. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on Gradescope. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Readings: You might find the following references useful:

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 points.

Scheme is a famous functional programming language from the 1970s. It is a dialect of Lisp (which stands for LISt Processing). The first observation most people make is the unique syntax, which uses a prefix notation and (often many) nested parentheses (see http://xkcd.com/297/). Scheme features first-class functions and optimized tail-recursion, which were relatively new features at the time.

Fun comic

Recommended VSCode Extensions

If you use VSCode as your text editor, we have found these extensions to be quite helpful for Scheme :)

Before:

After:

Extensions:

vscode-scheme

Rainbow Brackets

You may find it useful to try code.cs61a.org/scheme when working through problems, as it can draw environment and box-and-pointer diagrams and it lets you walk your code step-by-step (similar to Python Tutor). Don't forget to submit your code by submitting to the appropriate Gradescope assignment though!

Scheme Editor

You can write your code by either opening the designated .scm file in your text editor, or by typing directly in the Scheme Editor, which can also be useful for debugging. To run this editor, run python3 editor. This should pop up a window in your browser; if it does not, please navigate to localhost:31415 while python3 editor is still running and you should see it. If you choose to code directly in the Scheme Editor, don't forget to save your work before running Ok tests and before closing the editor. To stop running the editor and return to the command line, type Ctrl-C.

Make sure to run python3 ok in a separate tab or window so that the editor keeps running.

If you find that your code works in the online editor but not in your own interpreter, it's possible you have a bug in your code from an earlier part that you'll have to track down. Every once in a while there's a bug that our tests don't catch, and if you find one you should let us know!

Required Questions

Scheme Lists

Q1: No Repeats

Implement no-repeats, which takes a list of numbers lst as input and returns a list that has all of the unique elements of lst in the order that they first appear, but no repeats. For example, (no-repeats (list 5 4 5 4 2 2)) evaluates to (5 4 2).

Hint: How can you make the first time you see an element in the input list be the first and only time you see the element in the resulting list you return?

Hint: You may find it helpful to use the filter procedure with a helper lambda function to use as a filter. To test if two numbers are equal, use the = procedure. To test if two numbers are not equal, use the not procedure in combination with =.

(define (no-repeats lst)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q no_repeats

Scheme ADTs

Teachers and Students

In the following questions, you'll be using data abstractions for students and teachers:

The teacher abstraction keeps track of the teacher's name, the class they teach, and the students enrolled in their class. Specifically, a teacher's name and class are atomic symbols, and their students is a list of student objects.
The student abstraction keeps track of a student's name and the classes they have attended. Specifically, a student's name is an atomic symbol, and their classes is a list of atomic symbols representing all classes attended. For example, if a student had attended cs61a and astronomy, their classes list would be (cs61a astronomy).

Additionally, you have access to selector functions to get information from a student or teacher instance:

student-get-name returns the name of a specific student instance.
student-get-classes returns a list of the classes that the student has attended.
teacher-get-name returns the name of a specific teacher instance.
teacher-get-class returns the class that the specific teacher instance teaches.
teacher-get-students returns a list of student instances that are enrolled in the teacher's class.

A summary of the constructor and selector procedures are listed below

; Constructors
(student-create name classes)
(teacher-create name class students)

; Selectors
(student-get-name student)
(student-get-classes student)
(teacher-get-name teacher)
(teacher-get-class teacher)
(teacher-get-students teacher)

Although we may not know how the constuctor or selector procedures are implemented, we can still use them to create our own student/teacher instances and get information from them (that's the beauty of abstraction!).

You will be using these procedures to solve the following two questions.

Q2: Students: Attend Class

Implement student-attend-class. This method takes in a student and a class as input, and returns a new student abstraction with the class list updated to reflect the class attended.

Important: Add the new class to the beginning of the student's class list. Make sure to use the constructor and selector procedures defined above!

(define (student-attend-class student class)
    'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q student_attend_class

Q3: Teachers: Hold Class

Implement teacher-hold-class. This method takes in a teacher as input, and emulates holding a class. Specifically, the function should return a new updated teacher, where all student objects in the teacher's students list have updated class lists to reflect their attendance.

Be sure to keep the abstraction barrier in mind! Additionally, you can use the student-attend-class procedure implemented in the previous problem, as well as any necessary constructor and selector procedures. You may also find the map function useful.

(define (teacher-hold-class teacher)
    'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q teacher_hold_class

Scheme Tree ADT

Q4: Add Leaf

Below is a Scheme-ified data abstraction of the Tree class we've been working with this semester.

; Constructs tree given label and list of branches
(tree label branches)

; Returns the label of the tree
(label t)

; Returns the list of branches of the given tree
(branches t)

; Returns #t if the given tree is a leaf, otherwise return #f
(is-leaf t)

Implement add-leaf, a Scheme procedure that takes in a tree instance t and a number x.

This procedure will return a new tree where for each non-leaf node in the tree, append a new leaf with the label x to that node's branches. If the input tree is a leaf, the resulting tree is unchanged.

Below is an example of a tree t and the result after add-leaf is applied to t with x as 5.

add

Hints:

append will merge the elements in two Scheme lists together. For example, (append (list 1 2) (list 3 4)) results in (1 2 3 4)

map applies a procedure onto every item in a Scheme list. For example, (map - (list 2 4)) results in (-2 -4)

You may find it useful to create a helper lambda function to pass in as the procedure to map

To create a tree with no branches, you must specify nil for its branches. For example, (tree 5 nil) is a leaf with 5.

We've provided you with some starter code, but you do not have to follow the skeleton.

If you're having trouble debugging this problem, try drawing it out!

(define (add-leaf t x)
    (if __________________
        __________________
        (begin
            (define mapped-branches (map __________________ __________________))
            (tree __________________ (append __________________ __________________))
        )
    )
)

Use Ok to test your code:

python3 ok -q add-leaf

Exam Practice

The following are some Scheme List exam problems from previous semesters that you may find useful as additional exam practice.

Submit

Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.