Homework 2: Scheme Intro 2

Table of Contents

This assignment is to be done individually. You can talk to other people in the class to come up with ideas and get help with general concepts, but you should not show others your code, nor see others' code. You can get direct help debugging from Anna and any of the course staff (graders, lab assistants, prefects).

1. Get started

Download the starter code here.

As in the previous homework and in the class activity, move the downloaded code to your ProgrammingLanguages folder, open it in VS Code, and launch Docker. Look back at the Development Setup Guide or the instructions for Homework 1 if you've forgotten how to do any of these steps.

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, save it, and then load it directly. You might have tried this in the in-class activity - 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.

You have two options here - continue in VSCode, or switch to Emacs for file editing (but continue to the VSCode terminal because it has the Docker container). The advantage of Emacs over VSCode is that it properly indents Scheme code automatically, and has better syntax highlighting. If you use the Scheme extension in VSCode (see the Development Setup if you may have skipped this step), the syntax highlighting is okay, but you'll have to be mindful about indentation.

To open the file in Emacs, launch Emacs and then select Open File from the menu. To open it in VS Code, locate it in the file explorer on the lefthand side of your screen. Once you've opened main.scm in your preferred editor, add the following line of Scheme code and save the file: 

(+ 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. Ask questions online as appropriate. 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 using 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/scheme2Starter$ ./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 '(a b c d e f g h i) 3)

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 homework 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/SchemeHomework2/scheme-starter-2-master/tests-m.scm":line 7
   (test-equal 40 (multiply (quote (4 5 2 1))))
FAILED:
   "/home/runner/SchemeHomework2/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 Syllabus 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 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, helped, or got help from people other than 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 notes you took in class or the starter files that Anna provided, that is also something to note in CollaborationsAndSources.txt. If you didn't talk with anyone or use any outside sources, please note that explicitly.

After making CollaborationsAndSources.txt and finishing the assignment, run ./zipitup in the terminal. (Again, if you get permission errors, run chmod a+x ./zipitup first). Then, upload the zip file to Gradescope.

On Gradescope, you should see autograder output for the same tests as you ran locally. There is a small but nonzero chance that your tests will fail on Gradescope, even if they pass on your own computer. If this happens, it is likely because you coded something in an unusual way. If this happens, first double-check that you're submitting to the correct assignment on Gradescope, then try re-uploading and rerunning the autograder, then see if there are error messages that can help you troubleshoot. It's also fine to reach out to Anna or the course staff for help if you're stuck.

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.
  • 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 …").
  • Your code uses good Scheme coding style.

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.

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! For major style issues, the graders will always ask you to revise and resubmit your code. For more minor issues, they will be more lenient with earlier assignments, but standards will be higher once you have gotten feedback about particular style conventions. This isn't just to be annoying: 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!

Author: annameyer

Created: 2026-01-02 Fri 16:26

Validate