Due: Friday, April 3, 2026, at 10pm

Starter code: a2_scheme_2.zip
Upload solutions via Gradescope

Goals

This assignment is designed to help you with the following:

• more practice with Scheme
• working with lists and conditionals in Scheme
• writing your own recursion Scheme functions

Collaboration policy

For this assignment, you may work alone or with a partner, but you must type up all of the code yourself. (It is therefore unexpected for two code submissions to be completely identical.)

You may also discuss the assignment at a high level with other students.

You should list any student with whom you discussed the assignment, and the manner of discussion (high level, partner, etc.) in your readme.txt file.

If you work alone, you should say so instead.

Assessment

Core requirements:

• all CR tests pass
• you do not use built-in functions like length
• your code is not hyper-tailored to pass the tests
• readme.txt contains your collaboration statement, sources, and reflection

Advanced requirements:

• satisfy the Core requirements
• all AD tests pass
• your code is not significantly more complex than needed to accomplish the task
• each function has a comment before it describing its high-level behavior
• your code uses good Scheme coding style

Getting started

First, you should download the starter files. Then copy that folder into your ProgrammingLanguages folder, open it in VS Code, and launch Docker. Check the Assignment 1 instructions if you’re unsure what to do.

Instead of doing all of our Scheme coding interactively, it’s easier to save it in a file and load that directly into Guile. These instructions assume you have code saved in a file named main.scm.

1. Launch Emacs (but keep VS Code open for its terminal) and open the file main.scm in your a2_scheme_2 directory.

2. Add the following line of scheme code and save main.scm:

(+ 1 2)

3. In the VS Code terminal, start Scheme as usual:

./scheme

4. Finally, load the code you wrote using the following expression: (load "main.scm")

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

scheme@(guile-user)> (load "main.scm")
$1 = 3

Part A: Conditionals

Special form: 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 as the result of this expression. Try to answer the following questions to yourself:

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

Note: this is really similar to the ternary if you may have seen in C or even Kotlin:

// C
(8 == 3) ? 9 : 10

// Kotlin
if (8 == 3) 9 else 10

Special form: 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 replace all of the 16s in the above code with some other value to change the output value. Try to answer the following questions to yourself:

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

Equivalence tests

Try this code, copying+pasting (or retyping!) 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. Search online as appropriate.

(Note: for understanding the string expressions, you might want to look at what happens when you type just cons 'hi 'there).)

Part B: Defining functions (a.k.a. procedures)

Special form: 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 procedure that takes a parameter and adds 1 to it.

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, given that 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, and then type (add-one 5) at the interactive Guile prompt. You should see the results:

scheme@(guile-user)> (add-one 5)
$1 = 6

So, what happened here? We used define to create a variable with name add-one and value that is the function we just created. (This is an example of how side effects may occur in functional programming: using the define special form leads to changes in how later expressions are evaluted.)

Aliasing

Add the following two lines to main.scm:

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

Run this code and try to explain to yourself what it does.

Aside: Python is kinda functional, too

Python can behave functionally. Try this:

# Python code!
addOne = lambda x: x + 1
print(addOne(5)) # prints 6

anotherAddOne = addOne
print(anotherAddOne(5)) # what does this print? Try it out! :D

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))))

Recall that you can type just a simple (a.k.a. primitive) expression in Scheme, too:

scheme@(guile-user)> (define n 10)
scheme@(guile-user)> n
$1 = 10

After executing the above code, see what the values of a, b, and c are. What happens when you call (strange 3)? Try to explain to yourself what’s going on.

Part C: Recursion

Recursion in different languages

The factorial operation can be naturally represented recursively for any positive value of n. Here is a Python version:

# Python
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

Here is a version in Kotlin:

// Kotlin
fun factorial(n: Int): Int {
    if (n == 0) {
        return 1
    } else {
        return n * factorial(n-1)
    }
}

Finally, here is the same function written in Scheme. Try typing it up and running it. Can you make sense of what it is doing?

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

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

Tracing recursive calls in Guile

One super useful technique for debugging is to use Guile’s tracing ability. It’s a little finicky, but it can be wonderfully helpful. To do this, copy and paste the entire factorial function defined in main.scm into Guile, then use the Guile command ,tr (that’s a comma followed by t and r) with a function call to trace it. Here’s what this all 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: |  |  |  |  |  6> (factorial 0)
trace: |  |  |  |  |  6< 1
trace: |  |  |  |  |  1
trace: |  |  |  |  2
trace: |  |  |  6
trace: |  |  24
trace: |  120

Tracing from a saved file

Unfortunately, tracing doesn’t work if you load the function first (e.g., with (load "main.scm")); it only works if you enter/paste it directly at the interactive prompt. But, there’s a workaround you can use: you can redirect input to the interactive prompt from a file.

First, create another file; let’s call it factorial.scm. Then paste the above factorial function in this file, followed by the trace command. Here’s what it should look like:

; File: factorial.scm

; Procedure factorial - computes n! 
(define factorial
  (lambda (n)
    (if (equal? n 0)
	1
	(* n (factorial (- n 1))))))

; Show the trace
,tr (factorial 5)

Don’t miss the blank line at the end of the file: that will tell Guile that the file is done being read.

In the terminal window, quit Guile by typing ,q. Then enter the following in the terminal:

./scheme < factorial.scm

This < factorial.scm redirects the input to be from the given file instead of from the keyboard. It will run ./scheme as if you were using it interactively, but instead of you typing it uses the characters in the file factorial.scm. That blank line at the end acts as you hitting return after the last command.

If the trace output gets too busy, it may be helpful to run it twice (so you can avoid trying to read the extra stuff it prints at the beginning). Try this version:

; File: factorial.scm

; Procedure factorial - computes n! 
(define factorial
  (lambda (n)
    (if (equal? n 0)
	1
	(* n (factorial (- n 1))))))

; Show the trace (twice)
,tr (factorial 5)
(newline)          ; function for displaying a newline
(newline)
(newline)
,tr (factorial 5)

Part D: Your assignment

For this assignment, you will write two recursive procedures in Scheme. For both, you should not use Scheme functions other than those which have been introduced in this homework or the previous one. You also should not use the built-in function length.

Note: You may, however, use the functions <, >, <=, and >= as appropriate.

Procedure: multiply

In the main.scm file included with the starter code, write a recursive function named multiply that multiples up all of the elements in a list. For example:

(multiply '(4 5 2 1))

should evaluate to:

40

Special cases:

• If the list is empty, the procedure should return 1.

Note that we will not test your code with anything other than a (possibly empty) list of numbers.

Procedure: keep-first-n

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

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

should evaluate to:

(a b c)

Special cases:

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

Testing your work

You have two files with tests for testing the core functionality (required for a grade of CR) and the advanced edge cases (required for a grade of AD) of your two procedures.

• CR tests: If these aren’t passing, debug them before moving on to the AD tests. The CR tests are defined in tests-cr.scm, and you can run all of them on your code by typing ./test-cr at the command prompt.

If all tests pass, it should say Failing tests: 0. as the final print out. If some fail, you see which specific test(s) had issues:

> ./test-cr
FAILED:
  "/workspaces/ProgrammingLanguages/a2_scheme_2/tests-cr.>scm":line 7
  (test-equal 40 (multiply (quote (4 5 2 1))))
FAILED:
  "/workspaces/ProgrammingLanguages/a2_scheme_2/tests-cr.scm":line 8
  (test-equal 240 (multiply (quote (4 5 2 1 -2 -3))))

The first failed test says the resulting value for (multiply (quote (4 5 2 1))) was expected to be 40, but my code resulted in a different value. To debug, I could load main.scm in Guile and run (multiply (quote (4 5 2 1))) to see what my code is returning or what error is being raised. I could also use ,tr if I get lost in the recursive calls.

• AD tests: These tests look more at edge cases rather than expected inputs. They are defined in tests-ad.scm, and can be run using ./test-ad at the command prompt.

Note that if you get permissions errors when trying to run tests, you probably have to fix the execution permissions for the relevant files:

> ./test-ad
bash: ./test-ad: Permission denied
> chmod a+x test-cr test-ad

Submitting your work

As with the first assignment, you will submit your work in two files.

Scheme code

The file main.scm should contain your two procedures multiply and keep-first-n. Make sure to add a comment above each of your procedures to describe its behavior at a high level (e.g., what it takes as input and what it returns as output).

Readme

For each assignment for this course you will also need to submit a file readme.txt in which you should write:

1. Your collaborations with anyone on the assignment
2. Your use of any outside sources on the assignment
3. Your reflection

You should be specific about your collaborations and sources – they shouldn’t just be empty or lists of names of people. If you worked alone and/or did not use any outside sources, you should say so.

For your reflection, spend a couple of sentences answering the following:

• Were there any particular issues or challenges you dealt with in completing this assignment?
• How long did you spend on this assignment?

Submitting to Gradescope

Once you have your two files, you will combine them into a single file using this command:

./zipitup

(make sure you’re in the terminal in the assignment folder). If you get an error about file permissions, first run chmod a+x zipitup.

Submit your .zip file to Gradescope at this link.

Note that it is possible (although unlikely) that the tests will pass on your computer but fail on Gradescope. If this happens, it’s probably because you coded something in an unusual way. Double-check that you’re submitted to the correct assignment and then check if any error messages can help you troubleshoot. If you’re still having issues, check with Tanya.