University of Toronto
Department of Computer Science
CSC324 - Principles of Programming Languages
September 1991
John Mylopoulos
Programming in Lisp: Tutorial Notes II
Prepared by Todd Kelley
;Here are three different implementations of bubble sort on integers.
; They are
; sort1 - functional implementation of bubble sort
; sort2 - fuctnional and tail-recursive implementation
; of bubble sort
; bad-sort - imperative (and destructive) implementation of
; of bubble sort, with side effects
;
;They are designed to illustrate the differences between functional
;programming and imperative programming. Also, the first two implementations
;illustrate the difference between non-tail-recursive functions and tail-
;recursive functions.
;
; *********IMPORTANT**********
; You will notice that all three of these functions are well documented.
; Your own code should also be documented this well.
; ****************************
;
; Read this code, then load it and try evaluating the following forms:
; >(setq my-list '(3 2 6 2 1))
; >my-list
; >(sort2 my-list)
; ; what does this evaluate to?
; >my-list
; ; what does THIS evaluate to?
; >(bad-sort my-list)
; ; what does this evaluate to?
; >my-list
; ; ACK!! Where did the list go?
; ; Will an imperative implementation always have
; ; side effects?
;
; ; Very brave persons might try the following forms:
; >(setq temp '(3 2 6 2 1))
; >(bad-sort temp)
; >temp
; ;What happened? Why didn't it happen when we evaluated (bad-sort my-list)?
;
;;;;;;;;;;;;;;;;;;;
;; FUNCTION
;; sort1 -- sort a list of integers in non-decreasing order using bubble sort
;;
;; USAGE
;; (sort1 list-of-int)
;;
;; SIDE EFFECTS
;; none
;;
;; DESCRIPTION
;; Returns a list of integers sorted in non-decreasing order.
;; The argument, list-of-int, must be a list of integers.
;; (Note -- this function is implemented using the functional paradigm)
;;
;; ALGORITHM
;; If the list is empty
;; return it (it's already sorted)
;; else if the list has only one element
;; return it (it's already sorted)
;; else if the first element is less than the second
;; recursively sort the cdr of the list (a smaller list)
;; attach the first element to the sorted cdr
;; (``check-done'' begins here)
;; if the first element of this list is still less than the second
;; return it (it's sorted)
;; else
;; (it is ``more sorted'' now)
;; recursively sort it again
;; else
;; swap the first two elements
;; recursively sort the cdr of this (a smaller list)
;; attach the first element (after the swap) to the sorted cdr
;; (``check-done'' begins here)
;; if the first element of this list is less than the second
;; return it (it's sorted)
;; else
;; (it is ``more sorted'' now)
;; recursively sort it again
;;
;; EXAMPLES
;; (sort1 '(3 2 1)) => (1 2 3)
;; (sort1 '(2 1 2 3)) => (1 2 2 3)
;;;;;;;;;;;;;;;;;;
(defun sort1 (list-of-int)
(cond ((null list-of-int) nil)
((= (length list-of-int) 1) list-of-int)
((<= (car list-of-int) (cadr list-of-int))
(check-done (cons (car list-of-int)
(sort1 (cdr list-of-int)))))
(t (check-done (cons (cadr list-of-int)
(sort1 (cons (car list-of-int)
(cddr
; list-of-int))))))))
; a helper function for sort1
(defun check-done (list-of-int)
(if (<= (car list-of-int) (cadr list-of-int))
list-of-int
(sort1 list-of-int)))
;;;;;;;;;;;;;;;;;;;
;; FUNCTION
;; sort2 -- sort a list of integers in non-decreasing order using bubble sort
;;
;; USAGE
;; (sort2 list-of-int)
;;
;; SIDE EFFECTS
;; none
;;
;; DESCRIPTION
;; Returns a list of integers sorted in non-decreasing order.
;; The argument, list-of-int, must be a list of integers.
;; (Note -- this function is implemented using the functional paradigm
;; AND it is tail-recursive.)
;;
;; ALGORITHM
;; In a bubble sort, we repeatedly traverse the list. Here we
;; maintain 3 variables:
;; 1. list-of-int : the part of the list traversed so far, initially nil
;; 2. current-list : the part of the list we have yet to traverse
;; 3. done-now : a boolean to indicate if no swaps were performed
;; : during the traversal, initially t (no swaps)
;; We are finished when done-now is t at the end of a traversal.
;;
;; loop
;; if current-list is empty
;; if done-now
;; return list-of-int
;; else ;(begin a new traversal)
;; current-list <- list-of-int
;; list-of-int <- nil
;; done-now <- t
;; else if current-list has only one element ;(begin a new traversal)
;; list-of-int <- (append list-of-int current-list)
;; current-list<- nil
;; done-now is unchanged
;; else if the first element of current-list is less than the second
;; ;add the first element of current-list to the end of list-of-int
;; list-of-int <- (append list-of-int (car current-list))
;; current-list <- (cdr current-list)
;; done-now is unchanged
;; else
;; ;perform a swap
;; ;add the second element of current-list to the end of list-of-int
;; list-of-int <- (append list-of-int (cadr current-list))
;; current-list <- (cons (car current-list) (cddr current-list))
;; done-now <- nil
;; endloop
;;
;; EXAMPLES
;; (sort2 '(3 2 1)) => (1 2 3)
;; (sort2 '(2 1 2 3)) => (1 2 2 3)
;;;;;;;;;;;;;;;;;;
(defun sort2 (list-of-int)
(do-sort nil list-of-int t))
;a helping function for sort2
(defun do-sort (list-of-int current-list done-now)
(cond ((null current-list)
(if done-now list-of-int (do-sort nil list-of-int t)))
((null (cdr current-list))
(do-sort (append list-of-int current-list) nil done-now))
((<= (car current-list) (cadr current-list))
(do-sort (append list-of-int (list (car current-list)))
(cdr current-list)
done-now))
(t (do-sort (append list-of-int (list (cadr current-list)))
(cons (car current-list) (cddr current-list))
nil))))
;;;;;;;;;;;;;;;;;;;
;; FUNCTION
;; bad-sort -- sort a list of integers in non-decreasing order (destructive)
;; using bubble sort
;;
;; USAGE
;; (bad-sort list-of-int)
;;
;; SIDE EFFECTS
;; The argument, list-of-int, may be destroyed (by permuting elements
;; in place).
;; The following symbols are bound to values, with any previous binding
;; destroyed:
;; done current-list temp
;;
;; DESCRIPTION
;; Returns a list of integers sorted in non-decreasing order.
;; The argument, list-of-int, must be a list of integers.
;; (Note -- this function is implemented using the imperative paradigm.
;; It is an example of the type of programming that is frowned
;; upon in LISP.)
;;
;; ALGORITHM
;; The algorithm is basically the same as for sort2 above, but
;; since the implementation of the algorithm is not functional,
;; unexpected results are possible.
;;
;; EXAMPLES
;; (bad-sort '(3 2 1)) => (1 2 3)
;; (bad-sort '(2 1 2 3)) => (1 2 2 3)
;;;;;;;;;;;;;;;;;;
(defun bad-sort (list-of-int)
(loop
(setq done t)
(setq current-list list-of-int)
(loop
(cond ((null current-list) (return))
((= (length current-list) 1) (return))
((> (car current-list) (cadr current-list))
;the following 3 lines exchange the first and second elements
(setq temp (car current-list))
(rplaca current-list (cadr current-list))
(rplaca (cdr current-list) temp)
(setq done nil)))
(setq current-list (cdr current-list)))
(if done (return)))
list-of-int)