Activity: Scheme Recursion Practice

Table of Contents

1 Activity structure

This is an activity not an assignment. That means it is not a graded assessment: you won't get formal feedback on it, but it is a great chance to practice with the ideas we've been talking about and it may also guide you through some new ideas. You'll work on it during class, usually with another students, or if you have to miss class, you'll complete it outside of class.

If you're working with someone, you should work in a paired programming style. At any point in time, one of you is "driving," i.e. actually using the keyboard and mouse. The other is actively engaged following along, preventing bugs, and providing ideas. You'll tradeoff who is driving about every 10 minutes, and it's important that regardless of whose computer you're using, you take turns typing and controlling it - the owner of the computer should not be the only one who drives. Before you start coding for a new part of the activity, I strongly encourage you to sketch out your strategy with your partner. You might discuss possible approaches together, and write down some ideas on paper that will then help you when you begin coding.

At the end of class, you should make sure you turn your code in (even if you're not done), as that gives you access to my solutions, and to email the code to your partner (so they can turn it in to access my solutions).

2 Setup

If both you and your partner have computers with you with the tools for our class setup on it, decide whose computer you'll be using.

Them you'll do the activity in VS Code: download the starter code (below), unzip it, move it into the ProgrammingLanguages folder for our docker container, and then open that folder as a docker in VSCode.

Click here to download the starter code for this activity.

3 Tasks

Put all of your code for these tasks in main.scm.

3.1 get-last

We want to write a function get-last that returns the last item in a list, or an empty list if given an empty list as input. Here are some example inputs and expected outputs:

(get-last '(13)) ;; Returns 13
(get-last '(1 4 6)) ;; Returns 6
(get-last '((1 2) 7)) ;; Returns 7 (the two items are (1 2) and 7).

Here's the beginning of the implementation, with ??? at spots in the code I haven't completed:

(define get-last
  (lambda (lst)
    (if (null? ???)
        '()
        (if (null? ???)
            ???
            (get-last ???)))))

Copy and paste this skeleton into main.scm, and then modify each ??? so that the code will work correctly.

(Hint: Walk yourself through each part of the code, talking about it out loud with your partner. For instance, to fill in the first ??? I might say "Okay, if ??? is null, then this will return an empty list. When what thing is null do we want to return an empty list?")

To test your code, you can try it with the examples in Scheme, and feel free to make up your own too! For most homeworks, you'll also have automated tests; this won't necessarily be true for most activities, but this activity does have some automated tests to show you how to run them. To run the tests for this function, type the following at the command line (not in Guile!):

./test-get-last

The tests in tests-get-last.scm will be run on your code, and you'll see how many passed and how many failed. I encourage you to try testing on your own first, and then if you think everything is working, try running my tests. (To run your code yourself, you can copy the function from main.scm into Guile, or alternatively, type (load "main.scm") in Guile to load the code in main.scm.)

3.2 list-length

Write a function list-length that computes the length of a list. Here are some example inputs and expected outputs:

(list-length '(13)) ;; Returns 1
(list-length '(1 4 6)) ;; Returns 3
(list-length '((1 2) 7)) ;; Returns 2 (the two items are (1 2) and 7).

You can assume that the input is a list, not a number or other structure. Do not use the built-in function length.

As above, first test the function yourself, and then try running my tests:

./test-length

3.3 nth

Write a function nth that gets the nth item in a list. We'll assume that the first item is the 1th item. Here are some example inputs and expected outputs:

(nth 1 '(3 5 7)) ;; Returns 3
(nth 2 '(3 5 7)) ;; Returns 5
(nth 1 '((1 2) 7)) ;; Returns (1 2)

You can assume that the input is a list, not a number or other structure. If the index to look for is longer than the length of the list or less than 1, return an empty list.

As above, first test the function yourself, and then try running my tests:

./test-nth

3.4 Understanding if

You might wonder whether if can be implemented in Scheme like normal procedures, or if something special is needed to evaluate if. The starter code contains a function example-fn. Try calling example-fn with an unbound variable, e.g.: (example-fn WOW). What happens?

Now, try writing an if statement involving an unbound variable in either the consequent or alternative, and make sure that the test in the if statement will not lead to the expression with the unbound variable. Here's an example of what I mean:

(if #t
    3
    WOW)

Try running the if-statement. What happens?

Based on what you've seen here, discuss with your partner (or brainstorm on your own) about whether the following attempt at re-defining if would produce something that is equivalent to the original if:

(define new-if
  (lambda (predicate consequent alternative)
          (cond (predicate consequent)
                (else alternative))))

In a comment at the end of main.scm, indicate whether this is equivalent and briefly justify your answer. Consider what this means for when you write an interpreter for Scheme: will you be able to treat if like any other procedure, or will it need to be handled as a special case? Special forms are particular keywords or constructs that need to be handled differently.

4 Turning in activities

To turn in this activity, zip up the folder with your code, and upload that zip on Moodle. Additionally, email the zip to your partner so they can turn it in too. Even if you worked with a partner or you didn't finish, everyone should turn in the activity in order to gain access to my solutions.