Scheme Introductory Lab 2

The first thing you’ll need to do is to create a repository for your project using GitHub classroom. Visit this GitHub classroom link (which I’ve placed in Moodle). Log into GitHub if need to. GitHub should then hopefully respond with a screen that says “You’re ready to go!” and will supply you with a link for the repository that you are creating. Click on that link, and you should be taken to the repository.

Once you see your repository in GitHub (not Repl.it), you should see a button labeled “Work in Repl.it.” Click it. That should set up a new repl in Repl.it, and you should be all set to work. Hopefully this is more streamlined than it was in the first assignment, since more of it should be set up, but ask for help if need be.

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 try to answer yourself:

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

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?

Try this code (you might just copy and paste all of it):

(equal? '(hi there) '(hi there))
(equal? '(hi there) '(bye now))
(equal? 3 3)
(equal? 3 (+ 2 1))
(equal? 3 3.0)
(equal? 3 (/ 6 2))
(equal? -1/2 -0.5)
(eqv? '(hi there) '(hi there))
(eqv? '(hi there) '(bye now))
(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) '(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.

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

(lambda (x)
  (+ x 1))

You should observe that the lambda function 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.

A function without a name is useless, as it is immediately garbage collected. 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 pointer named add-one, which points to the function you just created.

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.

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.

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 fact
  (lambda (n)
    (if (equal? n 1)
        1
        (* n (fact (- 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 fact 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 fact
  (lambda (n)
    (if (equal? n 1)
        1
        (* n (fact (- n 1))))))
scheme@(guile-user)> ,tr (fact 5)
trace: (fact 5)
trace: |  (fact 4)
trace: |  |  (fact 3)
trace: |  |  |  (fact 2)
trace: |  |  |  |  (fact 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 in Repl.it; let’s call it factorial.scm. Then paste the above fact function definition into that file, followed by the trace command. Here’s how my factorial.scm looks:

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

,tr (fact 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 (shown with >), enter the following command:

./scheme < factorial.scm

Don’t miss 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 typing Enter after the last command. If this works correctly (try it!) you should see output like:

> ./scheme < factorial.scm
GNU Guile 2.2.3
Copyright (C) 1995-2017 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: (fact 5)
trace: |  (fact 4)
trace: |  |  (fact 3)
trace: |  |  |  (fact 2)
trace: |  |  |  |  (fact 1)
trace: |  |  |  |  1
trace: |  |  |  2
trace: |  |  6
trace: |  24
trace: 120

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

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

(sum '(4 5 0 1))

should return

10

Special cases:

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

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 >=.]

You’re going to submit your work back to GitHub, instead of doing so on Moodle. One of the great things about doing this is that I have some tests set up that will automatically run. If the tests pass, your code is correct!

To submit your work back to GitHub, within Repl.it click on the Version Control icon on the toolbar on the left. It looks like a small branched tree with one node on the left and two nodes on the right. Repl.it has popup tooltips, so hopefully that will help.

You should then see a version control pop-up bar. In the box that says “What did you change?” enter in a comment. It can be brief; something like “added sum function” or whatever will do the trick. Then click the “Commit & push” button. If all goes well, the window will hesitate and shimmer for a bit, but then it should go through and indicate “up to date with master” near the top of the version control window.

Hopefully the above works as expected. If so, go to github.com in your browser, and find the repository there that you’re working on. You should be able to see all of the files, with your most recent updates. Perhaps most importantly, in the blue bar above your files, you should hopefully see a yellow dot, a green checkmark, or a red X next to a label with a commit id. I have your repository set up to automatically run the “meets expectations” tests on your code. (If you are curious, those tests are contained in the file tests-m.scm. (Don’t change them!) A yellow dot means the tests are still running; a green checkmark means they passed; and a red X means at least one of the tests failed for some reason. If you click that icon, you’ll see a pop-up window for two different sets of tests: one for the “meets expectations tests” and one for the “exemplary tests.” (Currently, the exemplary tests are not running.) You can click “Details” in the box that pops up, you’ll be taken to a window where you can see the results of your tests. Open up the “Run M Tests” section in the black window, and it will show you which tests failed, and what their line numbers are in the tests-m.scm file.

If you did have some tests not pass, you can go back and try again; then commit and push to GitHub to try again. DO NOT CHANGE tests-m.scm.

If all of the M tests all pass, you are likely to receive full credit for the assignment! We will be looking at your code, however, and will deduct points if your code is designed to only work on these specific tests without generalizing.

You can also run your M tests directly on Repl.it, by typing ./test-m at the command prompt. That’s faster than having GitHub do it for you, so you might do that when playing around. However, you should absolutely make sure that you do finally get your tests running on GitHub, as that’s how we’ll be grading it.

I don’t have the Exemplary tests running by default because getting an M is a good grade, and I want you to feel good about seeing your M tests pass even if your E tests aren’t passing. That said, you can enable the E tests after your M tests are passing if you want to try it. To enable the E tests on GitHub, you need to make sure that the text you type in the “What did you change?” box starts with the text E:. In other words, I might type in “E: hopefully final version”. If you do this, the Exemplary tests will run on GitHub in addition to the Meets Expectations tests. (If you haven’t changed your code at all since the last time you committed, the “What did you change?” box won’t be there. Add some whitespace or something to main.scm so you can convince Repl.it you’ve changed something.

You can also run your E tests directly on Repl.it by typing ./test-e at the command prompt.

Whenever you commit and push your code, that sends another version (called a “commit”) to GitHub that we can see. Because you can keep submitting new versions, we need to know when you are done so that we know which commit to grade. To do this, use a commit message that is labeled with the single word “SUBMITTED” in all capital letters. (If you wish to enable the E tests, it can look like “E:SUBMITTED”.

You should wait to use the message SUBMITTED until you’re sure you have committed the version you want us to grade. That said, in the unlikely event that you goof and realize that you want to commit a newer version for us to grade, you’ll need to use another message. Reusing the same tag for a different commit is generally a really bad idea. If you need to tag another commit, use the message “SUBMITTED.1” (or whatever version number you’re up to).