CSCI 316: Lisp Assignment 1

Due Date: October 8, 2025

Submission instructions are given below.

This assignment will count 1.5% towards your grade if the grade is computed using Rule A.

Important Notes

• NOTE: Lisp Assignment 2 (which was part G of this assignment in many previous semesters) will be due on October 10, 2025, just 2 days after the due date for this assignment!

• IMPORTANT: Questions that are at least somewhat similar in nature to certain of the exercises of this assignment will carry at least 8 pts. on Exam 1. Such exam questions may well be posed as multiple-choice or multiple-response questions, and without any hints such as those in sections E and F.

• Function calls in exam questions are more likely to be written using Lisp notation than the box notation used in ch. 1–2 of Touretzky—e.g., the function call in the last part of Touretzky’s exercise 2.20 (on p. 65 in sec. 2.14) is more likely to be written as (cons '(in one ear and) '(out the other)).

A. Exercises After Reading Secs. 2.1 – 2.4 of Touretzky

(Touretzky gives solutions in Appendix C.)

Do exercises 2.1, 2.2, 2.3, and 2.4 on p. 32 (in sec. 2.2) and pp. 34–35 (in sec. 2.4) of Touretzky.

Note on Cons Cell Representations

When you are asked to draw a cons cell representation, you may do so in any of the ways described below. So the three drawings below are all good ways to draw the cons cell representation of ((SHE (HAS 3)) VERY (GOOD) FRIENDS). Observe that a proper list has one closing parenthesis for each occurrence of NIL in its cons cell representation!

Different Ways to Draw the Cons Cell Representation of a Lisp List

Recall from secs. 2.1–2.4 that Touretzky draws the cons cell representation of a Lisp list by depicting each cell as a box with left and right parts that represent fields of the cell. (As explained in sec. 2.10, the fields represented by the box’s left and right parts are respectively called the CAR and the CDR.) Each field contains a pointer that is depicted as an arrow in the drawing; the arrow exits downwards from the box’s left part but exits rightwards from its right part.

Such a drawing can be simplified by depicting each cons cell as a small dot instead of a box—the arrows that exit the left and right parts of each box in the original drawing are respectively replaced by an arrow that exits downwards from corresponding dot and an arrow that exits rightwards from the dot.

Such simplified drawings can be further simplified by omitting the arrowheads and/or making the dots invisible.

Yet another way to draw cons cell representations is shown in Fig. 10.2 on p. 393 of Sethi (p. 9 of the course reader). The SDRAW function described on p. 186 of Touretzky (after sec. 6.9) prints drawings of the cons cell representations of lists. This function is available to you on mars if you start Clisp on that machine using the cl command.

B. Exercises After Reading Secs. 2.5 – 2.8 of Touretzky

(Touretzky gives solutions in Appendix C.)

Do exercises 2.5, 2.6, and 2.8 on p. 37 (in sec. 2.5), p. 38 (in sec. 2.6), and p. 41 (in sec. 2.8).

C. Exercises After Reading Secs. 2.9 – 2.14 of Touretzky

(Touretzky gives solutions in Appendix C.)

(a) Do exercises 2.10 and 2.11 on p. 45 (in sec. 2.10.1).

(b) Do all parts of exercise 2.15 except the last part, and exercise 2.16. These are on p. 50 (in sec. 2.10.3).

(c) Do exercise 2.17 on pp. 51–52 (in sec. 2.10.4), exercise 2.19 on p. 63 (in sec. 2.13), and exercise 2.20 on p. 65 (in sec. 2.14).

D. Exercises After Reading Secs. 3.7 – 3.10 of Touretzky

(Touretzky gives solutions in Appendix C.)

Do exercises 3.9, 3.10, 3.13, and 3.14 on pp. 90–91, in sec. 3.10.

Note: In exercise 3.10, the expressions are to be corrected only by inserting or removing ' characters, and you should not insert ' immediately before an occurrence of (third, (list, (+, or (cons.

E. Exercises After Reading Secs. 2.17 and 6.3 – 6.4 of Touretzky

(Solutions are given in the Solutions-to-sections-E-&-F-of-Lisp-Asn-1 document on Brightspace.)

(a) Do the following for each of the expressions (i)–(xvi) below: If the expression has no value (i.e., an error occurs when it is evaluated) or if its value is a dotted list, then explain why. Otherwise, write down the proper list that is the expression’s value.

Hint: In all cases where the value is a proper list, that list can be obtained from (⋯A⋯ ⋯B⋯ ⋯C⋯ ⋯D⋯ ⋯E⋯ ⋯F⋯ ⋯G⋯) by replacing each “⋯” with zero or more opening or closing parentheses, but you must write ( and ) in just the right places!

(i) (cons 'A '((B) C D (E F) G))
(ii) (list 'A '((B) C D (E F) G))
(iii) (append 'A '((B) C D (E F) G))
(iv) (cons '(A (B) C) '(D E (F G)))
(v) (list '(A (B) C) '(D E (F G)))
(vi) (append '(A (B) C) '(D E (F G)))
(vii) (cons '(A) '((B) C D E (F)) '(G))
(viii) (list '(A) '((B) C D E (F)) '(G))
(ix) (append '(A) '((B) C D E (F)) '(G))
(x) (cons '(A (B) C D E (F)) 'G)
(xi) (append '(A (B) C D E (F)) 'G)
(xii) (list '(A (B) C D E (F)) 'G)
(xiii) (append '(A B) 'C '(D E F G))
(xiv) (list '(A (B) C D E F G))
(xv) (list (append '(A B) '(C)) (cons '(D E F) '(G)))
(xvi) (cons (list '(A B) '(C)) (append '(D E F) '(G)))

Solutions to Part (a)

(i) (cons 'A '((B) C D (E F) G)) => (A (B) C D (E F) G)
(ii) (list 'A '((B) C D (E F) G)) => (A ((B) C D (E F) G))
(iii) (append 'A '((B) C D (E F) G))
      => Error: first argument must be a list
         (Every argument of append other than the last is required to be a list)
(iv) (cons '(A (B) C) '(D E (F G))) => ((A (B) C) D E (F G))
(v) (list '(A (B) C) '(D E (F G))) => ((A (B) C) (D E (F G)))
(vi) (append '(A (B) C) '(D E (F G))) => (A (B) C D E (F G))
(vii) (cons '(A) '((B) C D E (F)) '(G))
       => Error: cons expects exactly two arguments
(viii) (list '(A) '((B) C D E (F)) '(G)) => ((A) ((B) C D E (F)) (G))
(ix) (append '(A) '((B) C D E (F)) '(G)) => (A (B) C D E (F) G)
(x) (cons '(A (B) C D E (F)) 'G)
    => Dotted list: (A (B) C D E (F)) . G
       (Second argument to cons is not a list)
(xi) (append '(A (B) C D E (F)) 'G)
     => Dotted list: (A (B) C D E (F)) . G
        (Last argument to append is not a list)
(xii) (list '(A (B) C D E (F)) 'G) => ((A (B) C D E (F)) G)
(xiii) (append '(A B) 'C '(D E F G))
       => Error: second argument must be a list
          (Every argument of append other than the last is required to be a list)
(xiv) (list '(A (B) C D E F G)) => ((A (B) C D E F G))
(xv) (list (append '(A B) '(C)) (cons '(D E F) '(G))) => ((A B C) ((D E F) G))
(xvi) (cons (list '(A B) '(C)) (append '(D E F) '(G))) => (((A B) (C)) D E F G)

(b) Fill in the gaps to make statements (i)–(iv) true. Be careful to write (, ), and ‘ just where they are needed!

(i) (________ '((A B) (C)) (cons '(D E) '(F))) => ((A B) (C) (D E) F)
(ii) (________ '(A (B C)) (list '(D) '(E F))) => ((A (B C)) ((D) (E F)))
(iii) (cons '(A B) (append __________ '(E F))) => ((A B) (C D) E F)
(iv) (________ '((A B) C) (cons 'D '(E F))) => (((A B) C) D E F)

Solutions to Part (b)

(i) (append '((A B) (C)) (cons '(D E) '(F)))
    => ((A B) (C) (D E) F)
(ii) (list '(A (B C)) (list '(D) '(E F)))
     => ((A (B C)) ((D) (E F)))
(iii) (cons '(A B) (append '((C D)) '(E F)))
      => ((A B) (C D) E F)
(iv) (cons '((A B) C) (cons 'D '(E F)))
     => (((A B) C) D E F)

F. Further Important Exercises

(Solutions are given in the Solutions-to-sections-E-&-F-of-Lisp-Asn-1 document on Brightspace.)

1. In this question f, g, and h are Lisp functions such that f takes 1 argument, g takes 2 arguments, and h takes 3 arguments.

   (i) A certain correct Lisp expression, which calls f, g, and h, is such that removal of the parentheses from the expression leaves this: h f 5 g f 3 5 g 4 f 2. What is the expression?

   Hint: Recall that the left parenthesis in a Lisp function call expression is always immediately before the name of the function that is to be called. So the left parentheses in the expression are as shown here: (h (f 5 (g (f 3 5 (g 4 (f 2

Solution (i)

(h (f 5) (g (f 3) 5) (g 4 (f 2)))

(ii) Another correct Lisp expression that calls f, g, and h is such that removal of the parentheses from the expression leaves this: g h 5 f 3 g 3 4 h 2 f 3 g 4 5. What is the expression?

Solution (ii)

(g (h 5 (f 3) (g 3 4)) (h 2 (f 3) (g 4 5)))

Read secs. 5.3 and 3.17 of Touretzky before doing exercises 2 and 3.

1. Suppose you have just entered the following three expressions at successive Clisp > prompts:

(setf 8*7 5)
(defun 8+7 (x y) (+ x y))
(defun 8*7 () 9)

If you enter (8+7 (* 8 7) (8+7 (8*7) 8*7)) at the next Clisp > prompt, what will be printed?

Solution

70

1. How can the expression ''(A) be written using QUOTE (and without using the ' character)?

Hint: The expression '(A) can be written (QUOTE (A)).

Solution

(QUOTE (QUOTE (A)))

1. (i) Write down the Lisp list whose cons cell representation is drawn on the right.

   (ii) Write down the Lisp list whose cons cell representation is drawn below.

Solutions

(i) ((D E) A (B))
(ii) ((A) (3 (C 4) (5) E) 2 (B))

1. For each of (a), (b), (c), and (d) below, suppose SETF has just been used to give the variable E the specified value. In each case, do the following:

   (i) Write an expression involving e that does not involve any numbers and calls no function other than first, second, and third, and that evaluates to the number 0.

   (ii) Write an expression involving e that does not involve any numbers and calls no function other than car and cdr, and that evaluates to the number 0.

   Note: The answer to (ii) can obtained from the answer to (i) and the following facts:

   • (first x) = (car x)
   • (second x) = (car (cdr x))
   • (third x) = (car (cdr (cdr x)))

   Hint: For a specified value of (1 2 (0 3)), you would be expected to write the expressions (first (third e)) and (car (car (cdr (cdr e)))) for (i) and (ii).

   • (a) (1 (0 2) 3)
   • (b) (1 (2 (0 3)))
   • (c) (((0)))
   • (d) (((1 (2 3 (0)))))

Solutions to Question 5

Part (i) - using first/second/third:

(a) (first (second e))
(b) (first (second (second e)))
(c) (first (first (first e)))
(d) (first (third (second (first (first e)))))

Part (ii) - using car/cdr:

(a) (car (car (cdr e)))
(b) (car (car (cdr (car (cdr e)))))
(c) (car (car (car e)))
(d) (car (car (cdr (cdr (car (cdr (car (car e))))))))

WARNING: For 5(ii), car and cdr are the only functions that can be used. Expressions using other c…r functions (e.g., cadr, caddr, or caar) are incorrect!

1. For each of the four lists in parts (a)–(d) of exercise 5, write an expression that involves only numbers and calls of LIST, and that evaluates to the list.

   Hint: (list 1 2 (list 0 3)) is an expression that involves only numbers and calls of LIST, and that evaluates to the list (1 2 (0 3)). Notice that (list 1 2 (list 0 3)) can be obtained from (1 2 (0 3)) by replacing each "(" with "(list "!

Solutions to Question 6

(a) (list 1 (list 0 2) 3)
(b) (list 1 (list 2 (list 0 3)))
(c) (list (list (list 0)))
(d) (list (list (list 1 (list 2 3 (list 0)))))

1. For each of the lists in parts (a)–(d) of exercise 5, we can write an expression that involves only numbers, NIL, and calls of CONS, and that evaluates to the list. In each of the four cases, say just how many calls of CONS occur in that expression. (Equivalently, say just how many cons cells there are in the cons cell representation of the list.)

   Hint: A call of LIST with k arguments is equal to k nested calls of CONS. Specifically, (list a₁ a₂ … aₖ) is equal to (cons a₁ (cons a₂ … (cons aₖ nil) … )). Bearing this in mind, it should not be hard to deduce the answers to this question from the answers to the previous question!

Solutions to Question 7

• (a) 5 calls of cons

  Comment: In the expression (list 1 (list 0 2) 3) from answer 6(a), the outer call of list has 3 arguments (equivalent to 3 nested calls of cons) and the inner call of list has 2 arguments (equivalent to 2 nested calls of cons). Total: 3 + 2 = 5 calls.

• (b) 6 calls of cons

  Comment: Each of the three calls of list in the answer to 6(b) has 2 arguments: 2 + 2 + 2 = 6 calls.

• (c) 3 calls of cons

  Comment: Each of the three calls of list in the answer to 6(c) has 1 argument: 1 + 1 + 1 = 3 calls.

• (d) 8 calls of cons

  Comment: The five calls of list in the answer to 6(d) (left-to-right) have argument counts of 1, 1, 2, 3, and 1: 1 + 1 + 2 + 3 + 1 = 8 calls.

Further Comment: Another way to arrive at the answers to 7(a–d) is to draw the cons cell representations of the four lists and count the number of cons cells in each representation.

1. Suppose E has been given a value as follows:

(setf e '((90 91 92 93 94 95 96 97 98 99) (+ 3 4 –) (9 19 29 39 49 59 69 79 89 99)))

Parts (i)–(iv) of this problem each ask you to write an expression that doesn’t involve numbers and has the specified value; the expression is expected to use the variable E. To illustrate how to write such expressions, suppose you want to write an expression that doesn’t involve numbers and that evaluates to (92 B (29 39 49 59 69 79 89 99 + 3 4 -)). Then three solutions would be:

1st SOLUTION:

(list (third (first e)) 'B (append (rest (rest (third e))) (second e)))

2nd SOLUTION:

(list (caddr (car e)) 'B (append (cddr (caddr e)) (cadr e)))

3rd SOLUTION:

(list (caddar e) 'B (append (cddr (caddr e)) (cadr e)))

(i) Write an expression that does not involve any numbers and that evaluates to:

(((90 91) 92 93 94 95 96 97 98 99) (A B 29 39 49 59 69 79 89 99))

Solution to Part (i)

Using first/rest:

(list (cons (list (first (first e)) (second (first e)))
            (rest (rest (first e))))
      (cons 'A (cons 'B (rest (rest (third e))))))

Using car/cdr:

(list (cons (list (caar e) (cadar e)) (cddar e))
      (cons 'A (cons 'B (cddr (caddr e)))))

(ii) Write an expression that does not involve any numbers and that evaluates to:

((90 A 92 93 94 95 96 97 98 99) 4 (29 39 49 59 69 79 89 99))

Solution to Part (ii)

Using first/rest:

(list (cons (first (first e)) (cons 'A (rest (rest (first e)))))
      (third (second e))
      (rest (rest (third e))))

Using car/cdr:

(list (cons (caar e) (cons 'A (cddar e)))
      (caddr (cadr e))
      (cddr (caddr e)))

(iii) Write an expression that does not involve any numbers and that evaluates to:

((90 91 92 93 94 95 96 97 98 99 3) (+ 3 4 – 29 39 49 59 69 79 89 99))

Solution to Part (iii)

Using first/rest:

(list (append (first e) (list (second (second e))))
      (append (second e) (rest (rest (third e)))))

Using car/cdr:

(list (append (car e) (list (cadadr e)))
      (append (cadr e) (cddr (caddr e))))

(iv) Write an expression that does not involve any numbers and that evaluates to:

((A 91 92 93 94 95 96 97 98 99) (90 (19 29) 39 49 59 69 79 89 99))

Solution to Part (iv)

Using first/rest:

(list (cons 'A (rest (first e)))
      (cons (first (first e))
            (cons (list (second (third e)) (third (third e)))
                  (rest (rest (rest (third e)))))))

Using car/cdr:

(list (cons 'A (cdar e))
      (cons (caar e)
            (cons (list (cadr (caddr e)) (caddr (caddr e)))
                  (cdddr (caddr e)))))

How to Submit Your Solutions to Lisp Assignment 1

Be sure to do all of 1–6 below! Step 6 is very important.

1. Handwrite your answers to the exercises on paper, and number the pages of your answers. The answers must appear in the same order as the problems.

2. Either: Use a document scanner or mobile scanning app to create a single PDF file that contains all the pages of your answers. The nth page of the file must contain the nth page of your answers. Name the file your_last_name_in_lowercase-asn1.pdf. For example, if your name is John Doe then you must create a single PDF file named doe-asn1.pdf that contains all the pages of your answers. View the PDF file to make sure it is easy to read all parts of your answers!

   Or: Take a separate photo of each page of your answers, and save jpg files of the photos to your computer. View the files to make sure it is easy to read all parts of your answers! Then rename each jpg file as your_last_name_in_lowercase-asn1-pg-nn.jpg (where nn is the number of the page that the file is a photo of). Example: If your name is John Doe, rename your jpg files to doe-asn1-pg-01.jpg, doe-asn1-pg-02.jpg, etc.

3. Login to your Brightspace account at https://brightspace.cuny.edu/ and click on Lisp-Assignment-1 in the red navigation bar for this course.

4. Submit your_last_name_in_lowercase-asn1.pdf or all the your_last_name_in_lowercase-asn1-pg-nn.jpg files that were created at step 2. For more on how to submit, see pages 6 and 7 of: https://www.cuny.edu/wp-content/uploads/sites/4/media-assets/Student-Brightspace-Guide.pdf

   Note: If you submit after 11:59 p.m. on the due date in October, then you will be making a late submission. Late submissions will be accepted until noon on Wednesday, Dec. 24, the deadline for late assignment submissions. See page 3 of the 1st-day announcements document for information regarding late submission penalties.

5. After submitting your pdf file or jpg files (see step 4), click on Lisp-Assignment-1-Declarations in the red navigation bar for this course.

6. In the Summary window that opens, click on the Start Quiz! button at the bottom and then submit responses to Questions 1 and 2 of the Declarations regarding your Lisp Assignment 1 submission.

   Note: Ignore “(6,400 points)” and “(64 points)” on the lines “Question 1 (Mandatory) (6,400 points)” and “Question 2 (Mandatory) (64 points)”, and also ignore the “Select 64 correct answer(s)” line above the “NONE: …” answer to each question.

Important: Step 6 is Very Important

If you don’t submit responses to Question 1 and Question 2 of the Declarations regarding your Lisp Assignment 1 submission, then there will be a penalty of at least 50% of the maximum credit, and you may very possibly receive no credit at all for Lisp Assignment 1!

You may make changes to your submission and resubmit at any time up to noon on Wednesday, Dec. 24, the deadline for late assignment submissions. You may resubmit more than once. (But if you make any resubmission after 11:59 p.m. on the due date in October, then you will be considered to have made a late submission. See p. 3 of the 1st-day announcements document for information regarding late submission penalties.)

IMPORTANT: You must redo step 6 when making any resubmission.

Warning

If you don’t do step 6 (i.e., if you don’t submit responses to Questions 1 and 2 of the Declarations regarding your Lisp Assignment 1 submission) then the maximum credit you will receive for Lisp Assignment 1 is 0.75%, and you may very possibly receive no credit at all for the assignment!

---

REMINDER: Lisp Assignment 2 (which was part G of this assignment in many previous semesters) will be due on October 10, 2025, which is just 2 days after the due date for this assignment (October 8)!

Note that Assignment 2 will have to be submitted in a different way from Assignment 1; be sure to carefully read the submission instructions for Assignment 2 after you submit Assignment 1.

This assignment will count 1.5% towards your grade if the grade is computed using Rule A.