University of Toronto
Department of Computer Science
CSC324 - Principles of Programming Languages
Spring 1998 John
Mylopoulos
Programming in Lisp: Tutorial Notes 3
Prepared by Thodoros Topaloglou
Code, Runs and Traces of ToddUs Sorting Programs
;; sort1: sorts a list of integers using bubble sort, recursive implementation
(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-again (cons (car list-of-int)
(sort1 (cdr list-of-int)))))
(t (check-again (cons (cadr
list-of-int)
(sort1 (cons (car list-of-int)
(cddr list-of-int))))))))
(defun check-again (list-of-int)
(if (<= (car list-of-int) (cadr list-of-int))
list-of-int
(sort1 list-of-int)))
;; >(trace sort1)
;; (SORT1)
;;
;; >(sort1 '(2 1 3))
;; 1> (SORT1 (2 1 3))
;; 2> (SORT1 (2 3))
;; 3> (SORT1 (3))
;; <3 (SORT1 (3))
;; <2 (SORT1 (2 3))
;; <1 (SORT1 (1 2 3))
;; (1 2 3)
;;
;; >(sort1 '(3 2 1))
;; 1> (SORT1 (3 2 1))
;; 2> (SORT1 (3 1))
;; 3> (SORT1 (3))
;; <3 (SORT1 (3))
;; <2 (SORT1 (1 3))
;; 2> (SORT1 (2 1 3))
;; 3> (SORT1 (2 3))
;; 4> (SORT1 (3))
;; <4 (SORT1 (3))
;; <3 (SORT1 (2 3))
;; <2 (SORT1 (1 2 3))
;; <1 (SORT1 (1 2 3))
;; (1 2 3)
;; sort2: sorts a list of integers using bubble sort, tail-recursive impl.
(defun sort2 (list-of-int)
(do-sort nil list-of-int t))
(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))))
;; >(trace do-sort)
;; (DO-SORT)
;;
;; >(sort2 '(2 1 3))
;; 1> (DO-SORT NIL (2 1 3) T)
;; 2> (DO-SORT (1) (2 3) NIL)
;; 3> (DO-SORT (1 2) (3) NIL)
;; 4> (DO-SORT (1 2 3) NIL NIL)
;; 5> (DO-SORT NIL (1 2 3) T)
;; 6> (DO-SORT (1) (2 3) T)
;; 7> (DO-SORT (1 2) (3) T)
;; 8> (DO-SORT (1 2 3) NIL T)
;; <8 (DO-SORT (1 2 3))
;; <7 (DO-SORT (1 2 3))
;; <6 (DO-SORT (1 2 3))
;; <5 (DO-SORT (1 2 3))
;; <4 (DO-SORT (1 2 3))
;; <3 (DO-SORT (1 2 3))
;; <2 (DO-SORT (1 2 3))
;; <1 (DO-SORT (1 2 3))
;; (1 2 3)
;; >(sort2 '(3 2 1))
;; 1> (DO-SORT NIL (3 2 1) T)
;; 2> (DO-SORT (2) (3 1) NIL)
;; 3> (DO-SORT (2 1) (3) NIL)
;; 4> (DO-SORT (2 1 3) NIL NIL)
;; 5> (DO-SORT NIL (2 1 3) T)
;; 6> (DO-SORT (1) (2 3) NIL)
;; 7> (DO-SORT (1 2) (3) NIL)
;; 8> (DO-SORT (1 2 3) NIL NIL)
;; 9> (DO-SORT NIL (1 2 3) T)
;; 10> (DO-SORT (1) (2 3) T)
;; 11> (DO-SORT (1 2) (3) T)
;; 12> (DO-SORT (1 2 3) NIL T)
;; <12 (DO-SORT (1 2 3))
;; <11 (DO-SORT (1 2 3))
;; <10 (DO-SORT (1 2 3))
;; <9 (DO-SORT (1 2 3))
;; <8 (DO-SORT (1 2 3))
;; <7 (DO-SORT (1 2 3))
;; <6 (DO-SORT (1 2 3))
;; <5 (DO-SORT (1 2 3))
;; <4 (DO-SORT (1 2 3))
;; <3 (DO-SORT (1 2 3))
;; <2 (DO-SORT (1 2 3))
;; <1 (DO-SORT (1 2 3))
;; (1 2 3)
A Note on Documentation
|
| Here is an example of "good" documentation for "complex" Lisp functions.
| Only the complex and the major importance functions in your programs
| should be documented this way. Note, for instance, that a one line comments
| is enough for function "check-again", a helper function for sort1.
| The presentation of a major importance function should include:
| a) documentation (as shown bellow, algorithm included) b) code and c)
;; testing.
|
| Testing shouldn't be limited in the cases that are provided
| in the assignment handouts. You need to provide tests for boundary
| cases as well for complex input. For examplei, here are some cases that
| the following sorting program should handle:
|
| (sort1 '())
| (sort1 '(1))
| (sort1 '(1 2 3))
| (sort1 '(3 2 1))
| (sort1 '(1 2 1 2 1 2))
| (sort1 '(1 1))
|
| *** Please do not include traces in your assignment report except if
| *** it is explicitly requested.
|
| ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
| ;; FUNCTION
| ;; sort1: sorts a list of integers using bubble sort
| ;;
| ;; USAGE
| ;; (sort1 list-of-int)
| ;;
| ;; SIDE EFFECTS
| ;; none
| ;;
| ;; DESCRIPTION
| ;; returns a list of integers sorted in increasing order
| ;; the argument list-of-int must be a list of integers
| ;;
| ;; ALGORITHM
| ;; (trace sort1)
;; (SORT1)
;;
;; >(sort1 '(2 1 3))
;; 1> (SORT1 (2 1 3))
;; 2> (SORT1 (2 3))
;; 3> (SORT1 (3))
;; <3 (SORT1 (3))
;; <2 (SORT1 (2 3))
;; <1 (SORT1 (1 2 3))
;; (1 2 3)
;;
;; >(sort1 '(3 2 1))
;; 1> (SORT1 (3 2 1))
;; 2> (SORT1 (3 1))
;; 3> (SORT1 (3))
;; <3 (SORT1 (3))
;; <2 (SORT1 (1 3))
;; 2> (SORT1 (2 1 3))
;; 3> (SORT1 (2 3))
;; 4> (SORT1 (3))
;; <4 (SORT1 (3))
;; <3 (SORT1 (2 3))
;; <2 (SORT1 (1 2 3))
;; <1 (SORT1 (1 2 3))
;; (1 2 3)
;; bad-sort
(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))
(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)
;; >(load "bad-sort")
;; Loading bad-sort
;; Finished loading bad-sort
;; T
;;
;; >(bad-sort '(3 2 1))
;; (1 2 3)
;;
;; >(bad-sort '(3 2 6 2 1))
;; (1 2 2 3 6)
;;
;; >(setq my-list '(3 2 6 2 1))
;; (3 2 6 2 1)
;;
;; >(bad-sort my-list)
;; (1 2 2 3 6)
;;
;; >my-list
;; (1 2 2 3 6)
;;
;; >(setq temp '(3 2 6 2 1))
;; (3 2 6 2 1)
;;
;; >(bad-sort temp)
;; (1 2 2 3 6)
;;
;; >temp
;; 2
More Lisp recursive functions
| Hi everyone,
| Here is the code of the examples that we were discussing in the last
| tutorial. Due to time constraints, I talked only about flip2r, but as
| you can see in the code, flip2r uses flip2. Flip2 works with a flat
| list whereas flip2r works with a list containg sublists.
|
| ;; flip2 returns the list formed by re-arranging pairs of consecutive
| ;; elements of its input list, i.e., exchanging the first with the
| ;; second positions, the third with the fourth positions, etc.
|
| (defun flip2 (l1)
| (cond ((null l1) nil)
| ((null (cdr l1)) l1)
| (t (cons (car (cdr l1)) (cons (car l1) (flip2 (cdr (cdr l1)))))) ))
|
|
| ;; (flip2 '(1 2 3 4) )
| ;; (flip2 '(a b c) )
| ;; (flip2 '((a b) c) )
|
|
| ;; flip2r takes one argument, a list, and exchanges alternate elements
| ;; at top level, and also exchanges alternate elements in each embedded
| ;; list, recursively.
|
| (defun flip2r (l1)
| (cond ((atom l1) l1) ;; covers this case: ((null l1) nil)
| ((null (cdr l1)) (list (flip2r (car l1))))
| (t (cons (flip2r (car (cdr l1))) (cons (flip2r (car l1))
| (flip2 (cddr l1))))) ))
|
|
| ;; (flip2r '((a b) (c)) )
| ;; (flip2r '( (1 2) (((3 4 5)) a b) c d ) )
|
|
| ---
| Thodoros
Tutorial #3: Exercises from past midterm exams
Midterm Test, Fall94 -- Lisp
------------------------------------------------------------------------
>(setq dog 5)
5
>(defun bone (x) (setq dog (+ dog x)))
BONE
>dog
5
>(bone dog)
10
>(defun huh (d fn) (funcall fn d))
HUH
>(huh '(19 5) 'car)
19
>(setq dog 2)
2
>(let ((dog 10)) (huh 3 (quote (lambda (x) (* dog x))) ))
6
>(huh 3 (quote (lambda (x) (* dog x))))
6
>( (lambda (x) (* dog x)) 3)
6
------------------------------------------------------------------------
>(defun pairings (x y)
(cond ((null x) nil)
(t (cons (list (car x) (car y))
(pairings (cdr x) (cdr y))))))
PAIRINGS
>(PAIRINGS '(A B C) '(1 2 3))
((A 1) (B 2) (C 3))
------------------------------------------------------------------------
>(defun average (lst) (avHelp lst 0 0 ))
AVERAGE
>(defun avHelp (lst tot num)
(cond ((null lst) (cond ((eq 0 num) 0) (t (/ tot num))))
(t (avHelp (cdr lst) (+ tot (car lst)) (+ num 1))) ))
AVHELP
>(average '(1 2 3))
2
------------------------------------------------------------------------
(defun formP (s)
(cond ((or (atomP s)
(functionFormP s)
(macroP (car s))
(specialFormP (car s))) t)
(t nil) ))
(defun functionFromP (s)
(cond ((and (functionP (car s))
(formListP (cdr s))) t)
(t nil) ))
(defun formListP (s)
(cond ((null s) t)
(and (formP (car s))
(formListP (cdr s))) t)
(t nil) ))
Assume atomP, functionP, MacroP, SpecialFormP are existent functions
------------------------------------------------------------------------
;; mystery function -- x is any list of numbers
;; returns a pair of the smaller and larger elements
(defun mystery (x)
(let ((f (very-first x)))
(mys1 x (list f f))))
(defun mys1 (x mm)
(if (null x)
mm
(let ((a (car x))
(m1 (first mm))
(m2 (second mm)))
(if (listp a)
(mys1 (cdr x) (mys1 a mm))
(mys1 (cdr x) (list (if (< a m1) a m1) (if (> a m2) a
m2)))))))
(defun very-first (x)
(cond ((null x) nil)
((atom (car x)) (car x))
(t (very-first (car x)))))
;; median function -- takes as input a list with an odd number of distict ints
;; returns the median, i.e., a number m s.t. there are N numbers smaller than
;; m and N numbers larger than m.
(defun median (lst)
(medHelp lst lst))
(defun medHelp (lst aux)
(cond ((null lst) nil)
((medP lst (car aux)) (car aux))
(t (medHelp lst (cdr aux) ))))
(defun medP (lst at) (helpP lst at 0 0))
(defun helpP (lst at les mor)
(cond
((null lst)
(cond
((= les mor) t)
(t nil)))
((= (car lst) at) (helpP (cdr lst) at les mor))
((< (car lst) at) (helpP (cdr lst) at (+ les 1) mor))
(t (helpP (cdr lst) at les (+ mor 1)))))
;; unpair function
;; (unpair '((a 1) (b 2))) returns ((a b) (1 2))
(defun unpair (l)
((cond (null l) nil)
(t (h-unpair l nil nil))) )
(defun h-unpair (l a b)
(cond ((null l) (list a b))
(t (h-unpair (cdr l) (append a (list (caar l)))
(append b (list (cadar l))))) ))