Homework 2: Scheme Intro 2

Table of Contents

This assignment is to be done individually. You can talk to other people in the class, me, and any of the course staff (graders, lab assistants, prefects) for ideas and to gain assistance. You can get direct help debugging your code from me and any of the course staff, and you're welcome to show us your code during debugging or other conversations. The code that you write should be your own, and you shouldn’t directly show or share your code with other students (although you may discuss general debugging strategies with others). See the course syllabus for more details and bring any questions to Anna.

1 Get started

Download the starter code here.

As in the previous homework and in the class lab, get started in either VS Code with Docker or using the courses drive and local installation of our tools. Look back at the instructions for homework 1 if you've forgotten how to do any of these steps. Move the unzipped folder with the starter code into either the folder for your Docker container or to your student work folder on COURSES before you begin.

2 Run a saved program

Entering your code interactively is fun, but not a good idea for creating large programs. A better way to go is to write your code in a file, saving it, and then loading it directly. You might have tried this in the in-class lab - this section walks through it in a little more detail.

In principle, you could load a file with any name, but I’ve created one called main.scm in order for you to get started. So find the file main.scm in VS Code (files are under the Explorer view, which is the top button in the left sidebar), open it (click on its name - you'll see it open in the VS Code editor in the middle of the window), and enter in the following one line of Scheme code: 

(+ 1 2)

You can then start up Scheme as usual by typing the following in the terminal window: 

./scheme

Finally, load in the code you wrote with the following Scheme code: 

scheme@(guile-user)> (load "main.scm")

If this worked correctly, you should see the results of running your code.

3 Conditionals

3.1 if

Enter the following code into main.scm: 

(if (equal? 8 3)
    9
    10)

Run the code, then modify the condition following if to get a different value to return. Questions for you to make sure you can answer:

  • What does if do?
  • Where is the traditional then and else that you would expect to see?

3.2 cond

Now enter the following code into main.scm, and run it: 

(cond ((equal? 16 3) (+ 3 8))
      ((equal? 16 8) 12)
      (else (* 6 3)))

See if you can you replace all of the 16’s in the above code with some other value to change the output value. Questions for you to try to answer yourself:

  • What does cond do?
  • What are the varying levels of nested parentheses for?

3.3 Equivalence tests

Try this code, copying and pasting one line at a time to see the results: 

(equal? '(hi . there) (cons 'hi 'there))
(equal? 3 3)
(equal? 3 (+ 2 1))
(equal? 3 3.0)
(equal? 3 (/ 6 2))
(equal? -1/2 -0.5)
(eqv? '(hi . there) (cons 'hi 'there))
(eqv? 3 3)
(eqv? 3 (+ 2 1))
(eqv? 3 3.0)
(eqv? 3 (/ 6 2))
(eqv? -1/2 -0.5)
(= 3 3)
(= 3 (+ 2 1))
(= 3 3.0)
(= 3 (/ 6 2))
(= -1/2 -0.5)
(= '(hi . there) (cons 'hi 'there))  ;; yes, this will give an error

See what kind of responses you get. Try to think through for yourself how equal?, eqv? and = are different. (For understanding the string ones, you might look at what happens when you type just (cons 'hi 'there).

4 Defining functions

4.1 lambda

In main.scm, enter this code, and then load it: 

(lambda (x)
  (+ x 1))

You should observe that the lambda command returns a function without a name. In this case, you have defined a function that takes a parameter and adds 1 to it. Functions in Scheme are called procedures by Guile. I’ll generally use either term depending on context.

4.2 Give it a name

A function without a name and with no references to it is useless, as it is immediately garbage collected - that is, since there are no references to it, its memory is reclaimed; we'll talk more about garbage collection later this term. Try this instead: 

(define add-one
  (lambda (x)
    (+ x 1)))

Save this code, load it, then type (add-one 5) at the interactive prompt. You should see the results. So what happened here? define created a variable named add-one, which refers to the function you just created. (This is an example where even though we're doing functional programming, we do have a side effect: running the define expression leads to changes in how later expressions are evaluated.)

4.3 Aliasing

Add the following two lines to main.scm, then load it at the interactive prompt. 

(define another-add-one add-one)
(another-add-one 5)

Try to explain to yourself what the above code does.

4.4 Local variables

You can declare local variables in Scheme via the use of let. For example, try the following code: 

(define a 5)
(define b 6)
(define c 7)
(define strange
  (lambda (x)
    (let ((a 1) (b 2) (c 3))
      (+ x a b c))))

After executing this code, see what are the values of a, b, and c are. Then see what what you get when you make the call (strange 3). Try to explain to yourself what’s going on.

4.5 Recursion

Here’s a factorial, done recursively. Copy and paste, run it, and see if you can make sense out of what it is doing. 

(define factorial
  (lambda (n)
    (if (equal? n 0)
        1
        (* n (factorial (- n 1))))))

Note that there is no return statement here as you would find in other languages you may know. In Scheme, return is implicit and automatic.

One super useful technique for debugging is to use Guile’s tracing ability. It’s a little finicky, but it’s wonderfully helpful. To do this, copy and paste the entire factorial function defined in main.scm, then use the Guile command ,tr (that’s a comma at the beginning of the line) with a function call to trace it. I’ve copied and pasted my complete session here so you can see what it looks like. 

scheme@(guile-user)> (define factorial
  (lambda (n)
    (if (equal? n 0)
        1
        (* n (factorial (- n 1))))))
scheme@(guile-user)> ,tr (factorial 5)
trace: (factorial 5)
trace: |  (factorial 4)
trace: |  |  (factorial 3)
trace: |  |  |  (factorial 2)
trace: |  |  |  |  (factorial 1)
trace: |  |  |  |  |  (factorial 0)
trace: |  |  |  |  |  1
trace: |  |  |  |  1
trace: |  |  |  2
trace: |  |  6
trace: |  24
trace: 120

Tracing can help you see all of your recursive calls, and what the parameters and return values are at each shot.

Try this out yourself to make sure you can make it work.

Unfortunately, tracing doesn’t work if you load the function first; it only works if you enter/paste it directly at the interactive prompt. That’s cumbersome. But there is a workaround you can use: you can redirect input to the interactive prompt from a file.

Here’s how to do so. First, create another file; let’s call it factorial.scm. Then paste the above factorial function definition into that file, followed by the trace command. Here’s how my factorial.scm looks: 

(define factorial
  (lambda (n)
    (if (equal? n 1)
        1
        (* n (factorial (- n 1))))))

,tr (factorial 5)

Don’t miss the fact that I’ve got at least one newline at the end of the file: that’s important.

Then, in the terminal window, quit Guile. You can do so by typing ,q. Once you are back at the bash prompt (e.g., on mine, csuser@d8d81de83bc9:/workspaces/ProgrammingLanguages/scheme2Starter$), enter the following command: 

./scheme < factorial.scm

You probably noticed the < above before factorial.scm. This is the bash redirect operator. It means that ./scheme should run as if you were using it interactively, but it should simulate you typing in the input from factorial.scm. That’s why the newline at the end of the file is important; that’s necessary to simulate you hitting return after the last command. If this works correctly (try it!) you should see output like: 

csuser@d8d81de83bc9:/workspaces/ProgrammingLanguages/scheme1Starter$ ./scheme < factorial.scm 
GNU Guile 3.0.7
Copyright (C) 1995-2021 Free Software Foundation, Inc.

Guile comes with ABSOLUTELY NO WARRANTY; for details type `,show w'.
This program is free software, and you are welcome to redistribute it
under certain conditions; type `,show c' for details.

Enter `,help' for help.
trace: (factorial 5)
trace: |  (factorial 4)
trace: |  |  (factorial 3)
trace: |  |  |  (factorial 2)
trace: |  |  |  |  (factorial 1)
trace: |  |  |  |  |  (factorial 0)
trace: |  |  |  |  |  1
trace: |  |  |  |  1
trace: |  |  |  2
trace: |  |  6
trace: |  24
trace: 120

Again, this is a really helpful way to help you debug your code.

For some longer files or more complex traces, trace will print some additional (irrelevant) information at the beginning, which can make it a little harder to see the trace that you wanted to see. It's thus sometimes helpful to run trace twice, separated by some newlines, so that the second one is separated from all the stuff at the top. Here's an example of how I modified my file to do that: 

(define factorial
  (lambda (n)
    (if (equal? n 0)
        1
        (* n (factorial (- n 1))))))

,tr (factorial 5)
(newline) ;;Function for displaying a newline!
(newline)
(newline)
,tr (factorial 5)

5 Your tasks to submit

5.1 multiply

In the main.scm file that I provided, write a recursive function named multiply that multiplies up all the elements in a list. For example: 

(multiply '(4 5 2 1))

should return 

40

Special cases:

  • If the list is empty, it should return 1.
  • We will not test your code with anything other than a (possibly empty) simple list of numbers.

5.2 keep-first-n

Also in the main.scm file that I provided, write a recursive function named keep-first-n that returns a list of the first n elements in a list.

Example: 

(keep-first-n 3 '(a b c d e f g h i))

should return 

(a b c)

Special cases:

  • If n is 0, you should return the empty list.
  • If n is bigger than the length of the list, or if n is negative, return the empty list.

Your function should not use any other Scheme functions than those which have been introduced in this lab or the previous one. [An exception: if you wish, you may use the functions <, >, <=, or >=.]

6 How to test your work

I've provided two files with tests:

  • M tests: The M ("meets expectations") tests are focused on the core functionality of your functions. You should run these tests first, and if these aren't passing, you should debug your code before moving on to the E-tests. The M tests are defined in tests-m.scm, and you can run all of these tests on your code by typing ./test-m at the command prompt. When you run the tests, you'll see a print out of how many tests passed and how many failed. If all of them passed, you should see Failing tests: 0. as the final print out.

If some tests fail, you'll get to see which specific tests had issues: 

> ./test-m
FAILED:
   "/home/runner/SchemeIntro2/scheme-starter-2-master/tests-m.scm":line 7
   (test-equal 40 (multiply (quote (4 5 2 1))))
FAILED:
   "/home/runner/SchemeIntro2/scheme-starter-2-master/tests-m.scm":line 8
   (test-equal 240 (multiply (quote (4 5 2 1 -2 -3))))

Here, the first failed tests is saying that the returned value for (multiply (quote (4 5 2 1))) should be equal to 40, but apparently my code did not return 40. To debug, I might run (multiply (quote (4 5 2 1)) (after loading main.scm), see what the code is returning (or what error is being raised), and then use trace if I'm not sure what to do next.

  • E tests: The E ("exemplary") tests focus more on edge cases and less on expected inputs to your functions. You can decide whether or not you are aiming to pass these tests (see grading information in the Homework Policies for details). The E tests are defined in tests-e.scm, and you can run all of these tests on your code by typing ./test-e at the command prompt.

Occasionally, you might get a permissions error when trying to run the tests: 

> ./test-e
bash: ./test-e: Permission denied

This occurs when the execution permissions for the files have inexplicably been changed. To fix it, you can run the following at the comand prompt: 

chmod a+x test-m test-e

chmod is the command-line function to change the access permissions for files. a+x says to grant all users executable permissions to the files that follow; here test-m and test-e.

7 How to submit your work

You'll submit your work on Gradescope. First, create a CollaborationsAndSources.txt file in the same folder as your code. In that file, indicate in what ways (if any) you collaborated with other people on this assignment and . Indicate any people you talked about the assignment with besides me (Anna) and our prefect. Did you share strategies with anyone else? Talk about any annoying errors and get advice? These are fine things to do, and you should note them in the CollaborationsAndSources.txt file. Give the names of people you talked with and some description of your interactions. If you used any resources outside of our course materials, that is also something to note in Collaborations.txt. If you didn't talk with anyone or use any outside sources, please note that explicitly in CollaborationsAndSources.txt. Look back at the Homework 1 instructions if you want more details on the CollaborationsAndSources.txt file.

After making CollaborationsAndSources.txt and finishing the assignment, upload your files on Gradescope. Note that if you submit a zip, you should submit a zip of the files, not a zip of the folder that contains the files. If all tests fail on Gradescope but they're working on your machine, this is likely the problem.

On Gradescope, you should see autograder output for the same tests as you ran locally. There is a very small but possible chance that you have coded something highly unexpected that cause the tests pass on the computer you’re working on, but not on Gradescope. We will be grading this assignment based on the results of the tests on Gradescope, so you should make sure to pay attention to how the tests run there as well when you submit.

For grading, you'll earn at least an M if the following conditions are all met:

  • All M tests pass
  • A visual inspection of your code shows that you have not hyper-tailored your code to pass the tests. Hyper-tailoring your code would be doing things like checking for the exact input from the test, meaning you haven't written your code in a way that would work for similar inputs see Homework policies for more on this).
  • You have a CollaborationsAndSources.txt with the information described above.

You'll earn an E if:

  • All conditions above for an M are met.
  • All the E tests pass.
  • Your code is not significantly more complex than needed to accomplish the task.
  • You have a comment before each function describing what the function does (its input/output behavior, not a play-by-play of "first checks… then makes a recursive call …").

If your code does not meet the criteria for an M or an E, then you'll earn a grade of NA (Not Assessable) or SP (Some Progress) for the assignment. Not Assessable means that your submission does not have an attempt at one or more functions in the assignment. Some Progress means that your submission has some code (in the correct language) for all functions in the assignment, but that the code does not pass all of the M tests, is hyper-tailored to the tests, and/or is missing a CollaborationsAndSources.txt file. You have two revisions to use at any point during the term if you earn an SP or M grade and would like to revise your code and have us change your grade.

When you get your grade back, you'll also get some feedback from the graders: they may comment on the style and structure of your code, suggesting ways that it excels and ways it might be improved. Pay attention to those comments! Even though style and structure are not directly graded in this course,striving to write code with better style and structure often leads to quicker debugging and makes your code easier to work with (which you'll appreciate when you have to keep working with the same code over many weeks in the interpreter project).

Good luck, ask questions, and have fun!

Assignment originally designed by Dave Musicant - thanks for sharing!