Due Dates

Lab 1 is due on Friday December 22, 2006.

Goals

Familiarize yourself with the fundamental concepts of the Scheme programming language.
Learn to use Chez Petite Scheme for interpreting and debugging Scheme code.
Learn enough basics to begin working on the Scheme project.

Overview

Scheme is a descendant/variety of Lisp (LISt Processor, developed by John McCarthy in the late 1950s). A successful Scheme program is built from the ground up, from small building blocks which are written, tested, verified, and then used as a foundation for more complex routines. In this lab, you will gain familiarity with the language by writing very small routines and functions to accomplish some very basic tasks. Most of the programs you will be writing will actually be single line snippets of code, and can be written entirely in the interpreter.

There are several good Scheme interpreters at your disposal. We will be using Chez Petite Scheme. This Scheme interpreter is one of the scheme interpreters available in the labs, and you can download a free copy for your PC by going to www.scheme.com. When you download the interpreter, you can also get a simple development environment in a package called the Scheme Widget Library (SWL). The feature of SWL that may interest you for the purposes of this course is the little editor included with SWL; it does parentheses matching for you and works nicely in concert with the interpreter.

Pre-lab Work

Make sure your CS account is in working condition and that you can log onto our systems without any problems. If you are experiencing login problems, contact a system administrator during normal business hours. For other problems, email problems@cs.rit.edu.

Read the web page at http://www.csm.astate.edu/schemel.html. On one page you will find a general introduction to the Scheme language. As a general reference, you will want to bookmark The Scheme Programming Language by Dybvig. The entire book is available on line. Finally, reading the first chapters of The Little Schemer will put you in the frame of mind for doing work in a functional language.

On a personal note, when I took this course, we used Lisp, and I found Lisp difficult to learn. I wasn’t used to thinking about programming in this way. Somehow I discovered The Little Schemer, and it made a big difference in helping me to gain control of the functional programming paradigm. It also convinced me that the Scheme language is appreciably more regular than Lisp. I hope you enjoy The Little Schemer, and I’m pretty sure you’ll find the presentation unique.

In-lab Work

For this lab, you will be working individually. You are encouraged to discuss the lab with your fellow classmates, but do not provide full solutions to each other.

Running Scheme

Scheme must be run from the command line with this command:

% petite ;;for Chez Petite Scheme

Optionally, you can specify a filename to load:

% petite my-max.ss

The Scheme interpreter prompt is a single greater-than, >.

% petite

Scheme statements are evaluated as soon as they are entered:

> (+ 1 2)

Scheme will not evaluate a statement until it is fully entered (the outside parentheses match)

> (+

1 2)

If you get stuck, such that the interpreter seems to be wanting something more, but you have no idea what it wants, type control-C (^C). That will stop whatever is going on, and return the Scheme prompt:

Error: variable | is not bound.

Type (debug) to enter the debugger.

> eg

Variables and functions created in the interpreter remain global. The most recent definition is the binding Scheme will use. If you entered Scheme code in a separate file, you can use the load command to reload all its contents into your interpreter’s environment:

>(load "my-max.ss")

To exit the Scheme interpreter, evaluate (i.e., surround it with parentheses) the exit function:

> (exit)

If an error is encountered during any evaluation, Scheme will display some information about the error and allow you to perform debugging.

> (my-max 'a)

Error: incorrect number of arguments to #<procedure>.

Type (debug) to enter the debugger.

There are many commands you can issue within the debugger; use ? to see the top level of choices. Here is an illustrative session (my commands are in bold):

> (my-max 'a)

Error: incorrect number of arguments to #<procedure>.

Type (debug) to enter the debugger.

> (debug)

debug> ?

Type e to exit interrupt handler and continue

r to reset scheme

a to abort scheme

n to enter new cafe

i to inspect current continuation

s to display statistics

debug> i

#<system continuation in error> : ?

length(l) ........... display number of free variables

depth ............... display number of frames in continuation stack

ref(r) .............. inspect [nth] frame element

set!(!) ............. set [nth] free variable to value, if assignable

down(d) ............. inspect [nth] next frame

eval(e) ............. evaluate expression in context of current frame

show(s) ............. show code and free variables

show-frames(sf) ..... show the next [n] frames

call ................ inspect the code for the pending call

code(c) ............. inspect the code for the pending procedure

file ................ switch to source file containing the pending call

?? .................. display more options

#<system continuation in error> : ??

print(p) ............ pretty-print object

write(w) ............ write object

up(u) ............... return to [nth] previous level

top(t) .............. return to initial object

forward(f) .......... move to [nth] next expression

back(b) ............. move to [nth] previous expression

=> .................. send object to procedure

file ................ switch to named source file

list ................ list the current source file [line [count]]

files ............... show open files

mark(m) ............. mark location [with symbolic mark]

goto(g) ............. go to marked location [mark]

new-cafe(n) ......... enter a new cafe

quit(q) ............. exit inspector

help(h) ............. help

#<system continuation in error> : q

debug> e

You probably will not need the debugger for purposes of this lab.

To assign a value to a global variable, use define. Remember that expressions always need to be in prefix notation, with the operator preceding the values:

> (define a (+ 1 2))

To display the current value of a variable, simply enter its name:

> a

Function invocation is done via a list. Remember that the quote before a list tells the interpreter not to evaluate its contents (but instead treat it as a data set):

> (car '(A B C))

Note that Scheme is not case-sensitive; upper and lower-case letters are equivalent.

Another very useful built-in function in Scheme is trace. The trace function allows you to register a function, and then whenever that function is invoked, the call sequence is traced out on the screen. When you start to look at recursive functions, this will be an infinitely (well, I hope it's not infinitely) useful tool to see how the function is being called repeatedly. The general form of the call is:

> (trace function-name)

Any subsequent invocations of the function will cause trace output to be displayed to the screen. To turn off tracing, use untrace.

> (untrace function-name)

Throughout this lab you will be experimenting with various statements and how they are interpreted. You should now have enough information to begin your lab.

Lab 1 - Scheme Fundamentals

For this activity, you will be constructing a file, schemeLab1.ss, which will contain the results for all 10 questions. Please use the included schemeLab1.ss file as a template to put your answers into. As you are constructing your answers, you may find it easier to work directly in the interpreter until you reach a solution. Also, some of the questions build on previous answers, so be sure to answer the questions in order.

Question 1

Show the Scheme code for performing the following mathematical statements (keeping in mind to preserve standard operator precedence). From here on out, always use define to create each variable globally (e.g., (define x ...) )

a. x = 9 * 7

b. y = 1 + 5 + 2 + 8 – 3 – 4 – 1 ;; take advantage of variable arguments

c. z = 3 + 4 * 8 / 2 – 6

Question 2

Make Scheme code that will produce the following results. You must use define. Please note that the variables l1 and l2 and l3 are short for list1, list2, list3 and are NOT the numbers 11, 12 and 13.

a. l1 = (LEAF #\a 3)

b. l2 = ("Stan" KYLE (+ 4 1))

c. A single list, l3, containing the three results, x, y & z, from question 1.

Question 3:

Using only the function cons, construct the following representations. You must use define. Each symbol in the list should have a corresponding cons, i.e. do not simply re-specify the list by consing an exact representation of the list onto nil.

a. cons1 = (A . B) ;; this is a dotted list

b. cons2 = (C D E)

c. cons3 = (F (G H) I)

Question 4:

Using only car and cdr, create the following variables. You must use define. Be careful that the results are symbols and not symbols in a list. If your result is a symbol in a list you need to perform an additional car.

a. a1 = A (the element A in cons1)

b. b1 = B (the element B in cons1)

c. e1 = E (the element E in cons2)

d. h1 = H (the element H in cons3)

Question 5:

Both Lisp and Scheme interpreters often supply functions named first, second, third, … tenth for accessing elements in a list. Chez Petite Scheme does not include these functions, but you can easily make them. The Little Schemer leads you through creating the functions first, second, third on page 119.

Create the functions first, second, and third, and use them, when possible, to access the same elements in Questions 4. Use must use define. If it is impossible to use the three previously mentioned routines for an individual question, you may fall back on car and cdr.

a. a2 = A (the element A in cons1)

b. b2 = B (the element B in cons1)

c. e2 = E (the element E in cons2)

d. h2 = H (the element H in cons3)

Question 6:

Write a my-max function and then use it within another function that works on lists. Do not use the built in max function anywhere in this question.

a. Write a function, my-max, which returns the greater of two numbers, which are passed in as arguments.

i.e. >(my-max 3 100)

100

b. Now write a function, my-max-list, which takes two lists as arguments and computes a list which contains the greatest element from each position in the two lists.

i.e. >(my-max-list '(1 2 8 9 5) '(2 1 7 11 4))

(2 2 8 11 5)

Question 7:

Write a recursive function, my-count, which takes a symbol, a list of symbols and a count as arguments. It should return an integer representing the number of times that symbol occurred in the list. The count variable denotes the number of times the symbol has already been seen in the list (i.e. initially called with 0). If count is non-zero initially, my-count should return the sum of the initial count and the count of times the symbol occurred in the list.

i.e. >(my-count 'A '(A B C A D A E F G A) 0)

Question 8:

Write a function, my-adjoin, which takes as arguments a symbol and a list of symbols. It creates a new list with the symbol added onto the end of the list, as long as the symbol is not already in the list. Hint – first write a function called my-member which will return #t if the symbol is in the list, and #f otherwise. Use my-member to find if the element is in the list, and then use append to add a new symbol to the end of the list.

i.e. >(my-adjoin 'D '(A B C))

(A B C D)

Question 9:

Rewrite this Scheme function to use cond instead of if. First, explain what this function does and how it works.

Hint – x is a symbol, and ylist is a list of symbols.

(define mystery

(lambda (x ylist)

( if (null? ylist) 0

(if (eq? (car ylist) x) 0

(let ((z (mystery x (cdr ylist))))

(and z ( + z 1)))))))

Question 10:

Write a function, my-flatten, which takes as input a list and returns a flattened verision of the same list. Hint – Use list? to check whether a given element is a list or not. You may use cons and append.

i.e. >(my-flatten '(a (b c) (d (e (f g) h) i) j) )

(a b c d e f g h i j )

Question 11:

Write a function, my-gcd, which takes as input 2 numbers and returns the greatest common divisor. Use Euclid's algorithm (Look it up on the web, if you are not familiar with it.).

i.e. >(my-gcd 21 49)

This lab will probably take you about 8 hours to accomplish. An experienced Scheme programmer would probably knock this work off in less than 30 minutes, but it takes some time and effort to learn functional programming when you’re new to it. Schedule enough time to do the work, and be ready to dig into the documentation and think hard.

How to test your code:

You can use this program schemeLabDriver.ss to test your code in your file schemeLab1.ss.

From within the Scheme repl, load the file schemeLabDriver.ss. That will cause your file schemeLab1.ss to load, and then your routines will be tested in a variety of ways.

You can then compare your answers with those in this file schemeLab1.answers.ss.

What you will submit:

Your file schemeLab1.ss will be the product you will submit for this lab.

Be sure to test each of your routines fully.

When your lab is complete, submit your schemeLab1.ss to me as an e-mail attachment.

Good luck, and have some fun…

(This lab was adapted to Scheme from work done in Lisp by Sean Strout. Thanks to Sean for his help.)