CS 251: Programming Languages

Fall 2017

hw1: Scheme lab

Due: Friday, 09/15 at 22:00

This is an individual assignment. Work through the following lab. There are three portions that you need to turn in, labelled with (EXERCISE) below. Write your answers in a file called lab.scm and submit it to Moodle.

In addition to this lab, there are Scheme resources linked on the course page if you need help.

There are other questions intermixed throughout the lab for you to think about. You do not need to turn in answers to these. Ask in class or on the Moodle forum if the answers aren't clear.

1. Getting started in DrRacket

Start up DrRacket, which is the programming environment that we'll be using. (If you've forgotten how, go back and look at the starting logistics assignment for options on how to run it.)
If this is the first time you're starting up DrRacket, you'll see a warning about no language being specified. DrRacket supports a number of different dialects of Scheme, and it's important that you pick the right one to be consistent with the assignments we're doing. To choose a particular language, go to the Languages menu for DrRacket, select "Choose Language," and in the "Other Languages" section, choose the dialect called "R5RS." We will not be using the "Racket" dialect in this course.
You will see a pair of windows. The bottom window says "Welcome to DrRacket." That is the interactions window. This is where you can test statements to see what they will do. Try it out: in the interactions window, type
```
(+ 3 5)
```
This should add 3 to 5. In Scheme, + is a function. To call a function in Scheme, you place the name of the function and its arguments, separated by spaces, inside parentheses. This takes a little getting used to! In most programming languages, function calls look something like this:
```
function(arg1, arg2, arg3)
```
In Scheme, function calls look like this:
```
(function arg1 arg2 arg3)
```
Change your program in some way. For example, re-type it as
```
(+ 3 7)
```
Experiment with hitting the Esc key followed by either the p(revious) or the n(ext) keys, which allow you to move backwards and forwards through your command history.

2. Basic Scheme primitives

In the interactions window, enter the following:
```
(car '(apple orange pineapple))
(cdr '(apple orange pineapple))
(car (apple orange pineapple))
```
What do car and cdr do? Why is the single quote necessary? What does it do? The last line of the above should cause an error: why?
(EXERCISE) Write sequences of cars and cdrs that will pick the symbol 'mary out of the following expressions:
```
'(jane elizabeth mary kitty lydia)
'(((jane) (elizabeth) (mary) (kitty) (lydia)))
'(jane (elizabeth) ((mary)) (((kitty))) ((((lydia)))))
```
For example, to pick out 'orange from '(apple orange pineapple), I might write the line
```
(car (cdr '(apple orange pineapple)))
```
in the file I will submit.

Execute the following statements. What do cons, append, and list do?

;; This is a comment, by the way!
(cons 'x '(1 2))
(cons '(1 5) '(2 3))
(append '(1) '(2 3))
(append '(1 5) '(2 3))
(list '1 '2 '3 '(4 5))

Execute the following code. What do length and reverse do?

(length '(alan grace ada))
(reverse '(alan grace ada))
(member 'grace '(alan grace ada))
(member 'alonzo '(alan grace ada))

3. Saving your code

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, save it, then run it. Here's how to do it.

Make sure that you have your network drives mounted. You'll want to save your code in your HOME folder (deprecated) or COURSES folder (under cs251-00-f17/StuWork/yourname).
Start typing in some Scheme code in the definitions window at the top of the screen. Use any of the above examples that you wish. When finished, save your program by going to the File menu, and choosing Save Definitions.
Run your program by clicking on the clicking on the Run button or press Ctrl-R.

You should generally use this approach for entering and running Scheme code, but entering code directly into the interactions window is good for testing out quick ideas.
To switch input focus back to the definitions window, press Ctrl-E (twice). (This is a bit cumbersome; if you find a better way, tell me!)

4. Conditionals

Scheme has a number of different predicates for testing equality.

Try this code:

(equal? 3 3)
(equal? 3 (+ 2 1))
(equal? 3 3.0)
(equal? 3 (/ 6 2))
(equal? -1/2 -0.5)
(equal? '(to be) '(to be))
(equal? '(to be) '(not to be))

(eqv? 3 3)
(eqv? 3 (+ 2 1))
(eqv? 3 3.0)
(eqv? 3 (/ 6 2))
(eqv? -1/2 -0.5)
(eqv? '(to be) '(to be))
(eqv? '(to be) '(not to be))

(= 3 3)
(= 3 (+ 2 1))
(= 3 3.0)
(= 3 (/ 6 2))
(= -1/2 -0.5)
(= '(to be) '(to be))  ;; yes, this will give an error

What kind of responses do you get? How are equal?, eqv?, and = different?

Enter the following code:
```
(if (equal? 8 3)
    9
    10)
```
Modify the condition following if to get a different value to return.

(Note that Scheme pays no attention whatsoever to how you indent your code. The above indenting is stylistically useful to see what the if expression is doing, but you could technically indent it any way you like. When in doubt, press Ctrl-I to have DrRacket reindent your code.)
Enter the following code:
```
(cond ((equal? 16 3) (+ 3 8))
      ((equal? 16 8) 12)
      (else (* 6 3)))
```
Can you replace all of the 16's in the above code with some other value to change the return value? What does the cond expression do?

5. Defining functions

In a new file, enter in the following code, save it, then run it.
```
(lambda (x)
  (+ x 1))
```
What does Scheme return? The lambda expression returns a function without a name. In this case, you have defined a function that takes an argument and adds 1 to it. Functions are called procedures in Scheme.
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, run it, then type (add-one 251) in the interactions window. The define expression created a pointer, called add-one, which points to the function you just created.
Try this out:
```
(define another-add-one add-one)
(another-add-one 251)
```
At the pointer level, what is happening here? Draw a picture on this paper indicating what is happening.
You can declare "local" variables in Scheme via the use of the let expression. For example, try the following code:
```
(define a 5)
(define b 6)
(define c 7)
(define strange
  (lambda (x)
    (let ((a 1) (b 2))
      (+ x a b))))
```
After executing this code, what are the values of a, b, and c? What about what you get when you make the call (strange 23)? Why?

6. Recursion

Enter the following function. What does it do? Why?
```
(define mystery
  (lambda (lst)
    (if (null? lst)
        lst
        (append (mystery (cdr lst))
                (list (car lst))))))
```
To watch your program in action with the debugger, click the "Debug" button instead of the "Run" button. Then run your code by typing (in the interactions window)
```
(mystery '((1 2) (3 4) 5 6))
```
A series of debugging buttons will appear at the top of the definitions window. Click "Step" repeatedly, and watch the pointer move through your code. Also watch the gray bar to the far left of the debugging buttons. DrRacket will show you the return values for function when they are called. You can also hover your mouse over variables (hover the mouse over the variable lst, for example), and DrRacket will show you those variable values to the right of the debugging buttons. You can also see the stack of function calls and variable values to the right.

You can use the "Go" button to resume execution of your code.

Note that there is no return statement here, as you would find in other languages you may know. Why? How is the return value determined in the above function?

So, what does the mystery function do? Why?

Modify the program as follows:

(define mystery
  (lambda (lst)
    (if (null? lst)
        lst
        (begin
          (display lst)
          (newline)
          (append (mystery (cdr lst))
                  (list (car lst)))))))

What do begin, display, and newline do?

(EXERCISE) Write a recursive function, 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)
```
Your code should do something appropriate if n is too big or too small (negative). It doesn't matter to me precisely what it does under these circumstances, so long as it does something reasonable (doesn't crash or return complete nonsense).

Your function should not use any other Scheme function than those which have been introduced in this lab. (An exception: if you wish, you may use the functions <, >, <=, or >=.)
(EXERCISE) Write a recursive function named sum that adds up all the elements in a list. For example:
```
(sum '(5 5 0 5 7))
```
should return
```
22
```
Do something reasonable if the list is empty.

Start early, have fun, and discuss questions on Moodle.