CSCI 316: Preliminary Exercises to Familiarize Students with Lisp

(Not for Submission)

Try to do problems 1-7 below before our 4th class meeting (on Wednesday, Sep. 10). You should definitely have done these exercises by the end of that week. First write solutions to the problems on paper (as if you were answering exam questions), and then test your expressions by entering them at Clisp’s > prompt on mars.

Solutions to these exercises are given in the Solutions-to-Preliminary-Lisp-Exercises PDF document on Brightspace. (Needless to say, you should not look at the solution to a problem until you have solved that problem yourself or been unable to solve the problem after spending a substantial amount of time on it.)

Important Reminder

As stated at the bottom of page 5 of the 1st-day-announcements document, the first time you use your mars account for this course you need to enter the following command at mars’s xxxxx_yyyy316@mars:~$ prompt:

source /home/faculty/ykong/316setup

This should only be done once this semester. The command produces a response that says you have qualified for 0.25 pt. extra credit provided the command was entered no later than Thursday, September 11.

Assuming you have previously entered the above-mentioned command, you should be able to start Clisp on mars by entering cl at the xxxxx_yyyy316@mars:~$ prompt.

Exercises

1. Write a Lisp expression that multiplies 30 by the result of 7 minus 2. To do this, you must write a call of the function * with two arguments; the second argument will be a call of the function - with two arguments.

Solution

(* 30 (- 7 2))

1. (Exercise 1 on page 15 of Wilensky) Write Lisp expressions to evaluate the following, noting that $n^2 = n \times n$ and $n^3 = n \times n \times n$:

   • (a) $3^2 + 4^2$
   • (b) 317 + 419
   • (c) $12^3 + 1^3 - (9^3 + 10^3)$

Solutions

(a) (+ (* 3 3) (* 4 4))

(b) (+ (* 3 17) (* 4 19))

(c) (- (+ (* 12 12 12) (* 1 1 1)) (+ (* 9 9 9) (* 10 10 10)))

1. (a) Write a Lisp expression that divides thirty by the result of seven minus three in such a way that the result is a rational number (i.e., 15/2).

Solution (a)

(/ 30 (- 7 3))

(b) Write a Lisp expression that divides thirty by the result of seven minus three in such a way that the result is a floating-point number (i.e., 7.5). Do not use the FLOAT function. Hint: 30 and 30.0 are two representations of the number thirty.

Solution (b)

(/ 30.0 (- 7 3))
(/ 30 (- 7.0 3))
(/ 30 (- 7 3.0))

All three are correct solutions.

1. (Exercise 3 on page 16 of Wilensky) Write a Lisp expression that computes the mean of the five numbers eighty-three, eighty-three, eighty-five, ninety-one, and ninety-seven. Do this in such a way that the result is rational, and then in such a way that the result is a floating-point number. Do not use the FLOAT function.

Solution (Rational)

(/ (+ 83 83 85 91 97) 5)

Solution (Floating-Point)

(/ (+ 83 83 85 91 97) 5.0)
(/ (+ 83.0 83 85 91 97) 5)

1. Lisp always prints rational numbers (fractions) in lowest terms; for example, if you enter the number 20/12 at Clisp’s > prompt (with no spaces before or after the “/”) then Clisp will print the equivalent number 5/3. Write a number that you can enter at Clisp’s > prompt to determine whether or not the two integers 7,360,001,711 and 58,879,948,151 are relatively prime. If they are not relatively prime, then find their greatest common divisor. (Two integers are said to be relatively prime or coprime if no integer greater than 1 divides both of them. For example, 20 and 9 are relatively prime; but 10 and 8 are not relatively prime because 2 divides both 10 and 8.)

Solution

When you enter the number 7360001711/58879948151 at Clisp’s prompt, Clisp prints 112303/898423. Therefore:

• 7360001711/58879948151 = 112303/898423
• The latter is in lowest terms
• 7360001711/112303 = 58879948151/898423 = 65537 is a common divisor of both numbers
• Since 112303/898423 is in lowest terms, 65537 is their greatest common divisor

Conclusion: The two integers are not relatively prime, and their greatest common divisor is 65537.

1. (Exercise 4 on p. 16 of Wilensky) The Lisp function SQRT returns the non-negative square root of any non-negative real argument. Use this function to write two Lisp expressions that evaluate to the roots of the equation $x^2 - 11x - 1302 = 0$. In other words, use SQRT to write two Lisp expressions that are respectively equivalent to the following:

   (a) $\frac{-(-11)+\sqrt{(-11)\times(-11)-4\times1\times(-1302)}}{2\times1}$

   (b) $\frac{-(-11)-\sqrt{(-11)\times(-11)-4\times1\times(-1302)}}{2\times1}$

Solutions

(/ (+ (- -11) (SQRT (- (* -11 -11) (* 4 1 -1302)))) (* 2 1))

(/ (- (- -11) (SQRT (- (* -11 -11) (* 4 1 -1302)))) (* 2 1))

1. (Exercise 7 on p. 17 of Wilensky) Write a Lisp expression that can be entered at Clisp’s > prompt to determine the order in which Common Lisp evaluates function arguments when it calls a function; the expression you write may use SETF. You may assume that the order is either left-to-right or right-to-left, and that the same order is used in all Common Lisp function calls.

   Hint: Consider a function call (- <expr>1 <expr>2). To evaluate this call with left-to-right argument evaluation order, do the following: First, evaluate <expr>1; next, evaluate <expr>2; finally, subtract the second result (i.e., the value of <expr>2) from the first result (i.e., the value of <expr>1). To evaluate this call with right-to-left argument evaluation order, do the following: First, evaluate <expr>2; next, evaluate <expr>1; finally, subtract the first result (i.e., the value of <expr>2) from the second result (i.e., the value of <expr>1). Normally, both evaluation orders would of course produce the same final value. But if evaluation of one of the two arguments has a side-effect, then evaluation order may make a difference. Try to think of an expression (- <expr>1 <expr>2) for which one of the argument evaluation orders would produce an error but the other would not.

First Solution

Evaluating (- x (setf x 4)) (without first giving a value to x) produces an error message that says x has no value, which is consistent with left-to-right evaluation. If arguments were evaluated in right-to-left order, then there would be no error and the call of - would return 0!

Second Solution

Evaluation of (- (setf x 9) (* x (setf x 2))) gives -9, which is consistent with left-to-right evaluation. If arguments were evaluated in right-to-left order, then the expression would instead evaluate to 5!

Comparison with Other Languages

Java and Python: Both use left-to-right argument evaluation order.

• Java: System.out.print((x=9)-x*(x=2)); prints -9 (not 5)
• Python: print((x:=9)-x*(x:=2)) prints -9 (not 5)

C++ and Scheme: Do not specify the order of evaluation of arguments, so no particular order can be assumed. This allows compilers to generate faster code in some cases but makes certain programs’ behavior implementation-dependent.

• C++: cout << (x=9)-x*(x=2); might print -9 or 5

Installing Clisp on Your Computer

Windows PC

If you are interested in using Clisp on a Windows PC, first download the file clisp-2.49-win32-mingw-big.zip via the URL https://sourceforge.net/projects/clisp/files/clisp/2.49/clisp-2.49-win32-mingw-big.zip/download and unzip the zip archive to a folder. Then check that the folder contains a file named clisp.exe, and add the folder to your PATH—if you don’t know how to add the folder to your PATH then see, e.g., https://www.computerhope.com/issues/ch000549.htm.

After that you should be able to run Clisp by opening a powershell or cmd window on your PC and then entering clisp in that window.

Mac

Clisp is also available for a Mac. If the Homebrew package manager (see https://brew.sh) is installed, then you should be able to install Clisp by entering the following command in a terminal window on the Mac:

brew install clisp

Note

You are not required to install Clisp on your PC or Mac. (Many students have done so, but I cannot guarantee that you will be able to.)