Lecture Notes: Destructive Operations

1. Goal: Call by value semantics without copying overhead

2. Lisp Internals

A. Everything is a pointer (setq X Y) means have X point to where Y did.

B. Cons cell diagrams (cons cell is generic record type with two fields in which anything can be stored. Usually used to represent lists.) [Draw for (setq Foo '(A B C D))]

• Aside: a cons instead of a list for (x,y) points takes half the space and is twice as fast!

  C. Copying:

  i. First/Rest: Just return the pointers in the car/cdr field. second, etc. are just composed first/rest calls.

  ii. CONS creates one new cons cell. LIST creates N new cells. APPEND copies the entire first list!

  D. Destructive operations (non-copying)
  i. Usually indicated by (setf (f x) y)

  ii. Example

           (setq Foo '(A B C D))
           (setq Bar (cons 'A (rest Foo)))
           (setq Baz (append '(A B) (rest (rest Foo))))
           (defun Hackit (List)
             (setf (second List) (third List))
             (setf List (rest List)) )
           (Hackit Foo)
           Foo --> (A C C D)
           Bar --> (A C C D)
           Baz --> (A B C D)
           

E. Warning: do not confuse abstract ideas (lists) with implementation (pointers/cons cells)

F. Fast-Append

           (defun Fast-Append (List1 List2)
             (setf (rest (last List1))
                   List2))

Avoids copying the first list, but still O(N) where N is length of List1. How can we do repeated appends? Use C approach: keep pointer to tail of list.

G. Various versions of First-N

Goal: efficient implementation of the following, assuming "collecting" not built-in

;;;==============================================================================
;;; Various methods of accumulating a list of the first N integers. Assume for the
;;; sake of argument that we can not simply loop in the reverse direction. Use
;;; (time (First-N-Vxx 1000)) to test.

;;;------------------------------------------------------------------------------
;;; Version1: If compiler is smart, this should be the best method, and should be
;;; O(N) time and space.  0.01 seconds, 8,288 bytes

(defun First-N-V1 (N)
  (loop for I from 1 to N collecting I))

;;;------------------------------------------------------------------------------
;;; Version 2. This naive method takes O(N^2) time and space since APPEND copies
;;; its first argument each time. Code like this appears surprisingly often :-(.
;;; 1.95 seconds, 4,020,304 bytes

(defun First-N-V2 (N)
  (let ((Nums NIL))
    (loop for I from 1 to N do
      (setq Nums (append Nums (list I))))
    Nums))

;;;-------------------------------------------------------------------------------
;;; Version 3. Put the numbers on the front, which is an O(1) operation, instead of on
;;; the back, which is an O(N) operation. Then reverse the list at the end. This is
;;; O(N) time and space, but has an extra constant factor of 2 in both time and space
;;; to reverse the list. 0.01 seconds, 16,288 bytes

(defun First-N-V3 (N)
  (let ((Nums NIL))
    (loop for I from 1 to N do
      (push I Nums))
    (reverse Nums)))

;;;------------------------------------------------------------------------------------
;;; Version 4, which should be as good as the built-in way. Keep a pointer to the tail
;;; of the list as you build it, and just tack the next cons cell onto this tail.
;;; 0.01 seconds, 8,288 bytes.

(defun First-N-V4 (N)
  (let* ((Nums (list 1))              ; You need something in the list to get a cons cell
         (Tail (last Nums)))
    (loop for I from 2 to N do
      (setf (rest Tail) (list I))
      (setq Tail (last Tail)))
    Nums))

• See Norvig section on queues: data structure with both a list and a tailpointer.

  H. SPLICE

;;;===================================================================================
;;; Idea from J. Paul McNamee, JHU/APL, paul_mcnamee@jhuapl.edu

(defun Splice (N New List)
  "Stick New in between Nth and N+1st elements of list, allocating only 1 new cons cell"
  (let ((Temp (nthcdr N List)))
    (setf (cdr Temp)
          (cons New (cdr Temp)))
    List))

;;;===================================================================================