Homework 1: The Basics

In this assignment you will create programs which put to use some of the week’s topics. You’ll also be introduced to some useful new ways of thinking about Scheme code. By the end of the assignment, you should be comfortable with

• The DrRacket interpreter
• Writing Racket procedures
• Using recursion with lists
• Writing tests for Racket procedures

Your implementations of the following procedures should all be placed in a single Racket file named hw1.rkt. The corresponding tests for each procedures should be in a second Racket file named tests.rkt.

The start of each file should be

#lang racket
; Your name(s) here.

Preliminaries

First, download and install Racket. Select the Racket (not Minimal Racket) distribution for your platform (almost certainly the 64-bit version for your operating system).

If you don’t already have a GitHub account, make one. As a student, you can get additional GitHub benefits such as unlimited private repositories here, but you don’t need to for this course. All of your repositories will be private to you, your partner (if you have one), and course instructors.

You’ll need Git installed in order to download and submit assignments. On macOS, Git is included with Xcode which can be installed from the App Store. On Linux, Git can be installed using your distribution’s package manager. You can install any of the many other Git tools instead, including GitHub Desktop on macOS and Windows.

Click on the assignment link. If you’re working with a partner, one partner should create a new team. The second partner should click the link and choose the appropriate team. It’s extremely helpful for the graders if you include your name and your partner’s name in the team name. Unfortunately, you cannot use the same team name for multiple assignments. You can append the homework number to your team name if you wish. (Please don’t choose the wrong team, there’s a maximum of two people and if you join the wrong one, you’ll prevent the correct person from joining.)

Once you have accepted the assignment and created/joined a team, you can clone the repository on your computer by following the instruction and begin working. But before you do, read the entire assignment and be sure to check out the expected coding style.

Be sure to ask any questions on Piazza.

Coding style

For all of the Racket code you write, you should follow the standard conventions. In particular,

1. You should let DrRacket indent your code. You can re-indent a line of code at any time by pressing tab. The Racket menu contains a Reindent All item which you can use to reindent the entire file.
2. Closing parentheses and brackets should not appear on lines by themselves (as you might do with } in C or Java). For example, a procedure to compute the arithmetic mean of two numbers might be written as

   (define (mean x y)
     (/ (+ x y) 2))
   

   or

   (define (mean x y)
     (/ (+ x y)
        2))
   

   but not as

   (define (mean x y)
     (/ (+ x y)
        2
     )
   )
   

Submission

To submit your homework, you must commit and push to GitHub before the deadline.

Your repository should contain the following files

• hw1.rkt
• tests.rkt

It may also include a .gitignore file which tells Git to ignore files matching patterns in your working directory.

Any additional files you have added to your repository should be removed from the main branch. (You’re free to make other branches, if you desire, but make sure main contains the version of the code you want graded.)

Make sure you put your name (and your partner’s name if you’re working with one) as a comment at the top of each file.

Part 1. List of Atoms

1. (8 points) Some versions of Scheme have a primitive procedure atom? that returns #t if its argument is an atom and #f if it isn’t; this isn’t built into Racket. Since Racket has primitive procedures pair? and null? that returns #t if their argument is a cons pair (such as a nonempty list) or null, respectively, we can easily write atom?. Every expression is an atom, a pair, or null. Use this to define procedure atom? in hw1.rkt. Here is some test data:
   • (atom? 3) returns #t
   • (atom? #f) returns #t
   • (atom? '(1 2)) returns #f
   • (atom? null) returns #f
   • (atom? (cons 5 10)) returns #f

   Now, it’s time to write tests to make sure your atom? works correctly. Look in tests.rkt for example tests. For each procedure, we define a test suite (using define as normal)

   (test-suite name test...)
   

   where name is the name of the test suite and it’s followed by any number of tests.

   We can create a test which tests whether an expression returns #t or #f using test-true or test-false.

   • (test-true test-name exp)
   • (test-false test-name exp)

   At the bottom of tests.rkt, there’s a definition for an all-tests test suite which, when we’re finished will consist of all of the test suites for the procedures you’re writing. And finally (run-tests all-tests). After you’ve written the tests, click the Run button and you should see a message telling you all your tests have passed or that some have failed.

   2 success(es) 1 failure(s) 0 error(s) 3 test(s) run
   

   Add at least two more tests for atom? (you can either use some of the suggestions above or come up with your own tests). Make sure you test cases where atom? returns #t and cases where it returns #f.

2. (8 points) Write a procedure list-of-atom? that takes an argument and returns #t if the argument is either an empty list or a list where every element is an atom.

   Define a new test suite to test list-of-atom? in tests.rkt.

   (define list-of-atom?-tests
     (test-suite
      "list-of-atoms?"
      (test-true "Empty list"
                 (list-of-atom? empty))))
   

   Add at least two more tests to this test suite. Try to think of all the possible edge cases (e.g., empty lists and lists containing a single element). Make sure to test cases that return #t and cases that return #f.

   Add your new test suite to the all-tests test suite.

   (define all-tests
     (test-suite
      "All tests"
      atom?-tests
      list-of-atom?-tests))
   

   Click the Run button to make sure all your tests pass. After running the tests, you can run (test/gui all-tests) in the interpreter to get a graphical version of the output. Give this a try. I found it helpful when I had many failing tests.

3. (8 points) Write a procedure not-list-of-atom? that returns #t if its argument is not a list of atoms. Of course, you could write this as

   (define (not-list-of-atom? lst)
     (not (list-of-atom? lst)))
   

   but don’t do that. Instead, write it directly using cond.

   Define a new test suite not-list-of-atom?-tests with at least three tests. Make sure to add that test suite to all-tests. Make sure to test cases that return #t and cases that return #f.

4. (8 points) Write the procedure list-of-int? that returns #t if its argument is the empty list or if it’s a list where every element is an integer. You can use integer? to test if something is an integer. Write at least three tests. Make sure to test cases that return #t and cases that return #f.

5. (8 points) Compare procedures list-of-atom? and list-of-int?. The structures of these procedures should look very similar. Write a procedure list-of-same? that takes two arguments: a predicate (like atom? or integer? or list?) and a list and returns #t if the list is empty or if every element in it satisfies the predicate.

   For example, (list-of-same? atom? lst) should behave the same as (list-of-atom? lst) and (list-of-same? integer? lst) should be the same as (list-of-int? lst).

   Write at least three tests. Try using different predicates. Examples include number?, list?, (lambda (x) (> x 3)). Make sure to test cases that return #t and cases that return #f.

6. (9 points) Write a procedure make-list-of-same that only takes one argument, a predicate, and returns a procedure. The returned procedure must take an argument and return #t if its argument is the empty list or a list for which the predicate returns #t on every element in the list.

   Thus, (make-list-of-same atom?) is the same as list-of-atom? and (make-list-of-same integer?) is the same as list-of-integer?.

   This process of taking a procedure of two arguments, list-of-same?, and rewriting it as a procedure of one argument that returns another procedure of one argument is called currying the original procedure. It’s named after Haskell Curry, an American mathematician who worked on the foundations of logic and programming languages.

   Write at least three tests. How can you test it? Well

   ((make-list-of-same integer?) '(25 'foo 18))
   

   is #f, for example. Make sure to test cases that return #t and cases that return #f.

Congratulations, you’ve completed the first part! Make sure that for each procedure you have implemented, you have created a test suite and added it to the all-tests test suite. Make sure your tests are (a) running; and (b) passing. How can you check if your tests are running? Easy! For each test suite you wrote, pick one of your tests and change it so that the test itself is wrong. Then, when you run the tests, you should get a failure. Don’t forget to change your test back to the correct version!

If you haven’t already done so recently, now would be a great time to commit all of your code and push it to GitHub. Recall that you need to first add the files, commit them, and then push.

$ git add hw1.rkt tests.rkt
$ git commit
$ git push

When you push your code to GitHub, your test suite will be run. While the tests are running, if you go to the GitHub page for your repository: https://github.com/programming-abstractions/YOUR_REPO, you’ll see a small yellow circle status icon in the header above your list of files.

Once the tests complete, the icon will change to a red ❌ if at least one test failed and a green ✓ if all tests pass.


You can click on the status icon to see more details.

Part 2. Operations on lists.

For each procedure, write the procedure and a test suite containing at least three tests and add the test suite to the all-tests test suite. You might want to write the tests first. Make sure to test your procedures under a variety of conditions like passing an empty list or a list of one element.

7. (9 points) Write (all-members lst1 lst2) which returns #t if every member of lst1 is also a member of lst2 and #f otherwise. Use equal? to perform the comparison.
   • (all-members '(a c x) '(a b x c x d)) returns #t
   • (all-members '(a c x) '(a b c)) returns #f
   • (all-members '(a) empty) returns #f
   • (all-members empty empty) returns #t
8. (9 points) Write (remove-second x lst) which removes the second occurrence of x from lst, if there is one. Use equal? to perform the comparison.
   • (remove-second 'x '(a b x c x d)) returns '(a b x c d)
   • (remove-second 'x '(a b x c x d x e)) returns '(a b x c d x e)
   • (remove-second 'x '(a b x c) )) returns '(a b x c)

   To write tests for procedure which don’t return #t or #f, use

   (test-equal? name actual expected)
   

   which defines a test with the given name which passes if actual is equal? to expected. For example, you might have the tests

   (test-equal? "Empty list"
                (remove-second 'x empty)
                empty)
   (test-equal? "Singleton, matching"
                (remove-second 'x '(x))
                '(x))
   

9. (9 points) Write (remove-pair x lst) which removes every occurrence of two consecutive instances of x in lst.
   • (remove-pair 'a '(a a b b c c a b c a a)) returns '(b b c c a b c)
   • (remove-pair 'a '(a b c a b c a)) returns '(a b c a b c a)
   • (remove-pair 'b '(a b b b a)) returns '(a b a)
   • (remove-pair 'b '(a b b b b a)) returns '(a a)
10. (8 points) Write (duplicate n exp) which builds a list containing n copies of object exp.
    • (duplicate 3 'x) returns '(x x x)
    • (duplicate 0 'y) returns '()
    • (duplicate 3 '(a b c)) returns '((a b c) (a b c) (a b c))
11. (8 points) Write (maximum lst) where lst is a nonempty list of numbers. It should return the maximum value in lst.
    • (maximum '(4 6 3 4 5 1 2)) returns 6
12. (8 points) Write (index-of lst x) which returns the 0-based index of the first occurrence of x in lst (use equal? to compare elements). If x is not in the list, return #f. (Notice that in this procedure, the list is the first parameter. That’s because this is a standard list procedure. Of course, here, you are writing the implementation (and tests).
    • (index-of '(x y z z y) 'x) returns 0
    • (index-of '(x y z z y) 'y) returns 1
    • (index-of '(x y z z y) 'a) returns #f
    • (index-of empty 'x) returns #f

Finishing up

Make sure you wrote tests of all of these, the test suite for each procedure is included in the all-tests test suite, and your tests pass. For reference, my solution involves 66 tests in total and when I run (test/gui all-tests), I get this.

Once you have finished (or better yet, frequently as you’re working), you need to push your code to GitHub since this is what we’ll use for grading. So double check that you’ve included your name and the name of your partner (if you’re working with a partner) in both files and git add/commit/push.

$ git add hw1.rkt tests.rkt
$ git commit
$ git push