04_iteration and recursion

1 . Using Lisp  Lisp is a interactive system  You can files to be processed as a batch file, but more often than not the programmer is the “main program”  Every expression typed a the “>” prompt is “read” and “evaluated” unless it is prefixed with an apostrophe ‘  Typing (exit) at the “>” prompt terminates the xlisp program 

2 .Go to computer and play with interactive LISP  The best way to learn Lisp is to go to computer and just play with functions, as you see below.  Please do this. 

3 . Sample Output >(a b c) error: unbound function - a if continued: try evaluating symbol again 1> [ back to top level ] > '(a b c) (a b c) > 1 1 > 1.2 1.2 > a error: unbound variable - a if continued: try evaluating symbol again 1> [ back to top level ] 

4 .Sample Output > nil nil > t t > T t > '(a (b c) d) (a (b c) d) > (setq sam 'abc) abc > sam abc 

5 .Arithmetic Functions > (/ 2 3) 2/3 > (/ 1.0 2) 0.5 > (1+ 3) 4 > (mod 2 3) 2 > (mod 5 2) 1 > (+ (* 2 2) (/ 4.0 5) ) 4.8 

6 .car=first and cdr=rest > (car '(a b c)) a > (cdr '(a b c)) (b c) > (car nil) nil > (cdr nil) nil > (first '(a b c)) a > (car (cdr '(a b c))) b > (cadr '(a b c)) b 

7 .List Functions > (list 'a 2 'b) (a 2 b) > (list '(a b) '(c d)) sam had a value ((a b) (c d)) ‘abc assigned earlier > (list sam c) error: unbound variable - c if continued: try evaluating symbol again 1> [ back to top level ] > (list sam 'c) (abc c) > (cons 'a '(b c d)) (a b c d) > (cons '(a b c) 'd) ((a b c) . d) 

8 .List Functions > (append '(a b) '(c d)) (a b c d) > (reverse '(a b c d)) (d c b a) > (length '(a (b c) d))) 3 > > (last '(a b c d)) (d) Substitutes in list > (subst 'a 'b '(a b c)) the atom b for atom a (a a c) > (subst 'a 'b '(a b c b)) (a a c a) 

9 .eval and quote > (eval (cdr '(a + 2 3))) cdr creates list (+ 5 2 3) > (setq a 'b) b > a b > b error: unbound variable - b if continued: try evaluating symbol again 1> [ back to top level ] > (set 'a 'b) b > (eval (eval ''a)) b > 'a a 

10 .eval and quote > (eval (eval '(quote a))) b > 'a a > (eval '(list '* 9 6)) (* 9 6) > (eval (eval '(list * 9 6))) error: bad function - (* 9 6) 1> [ back to top level ] > (eval (eval '(list '* 9 6))) 54 First eval inside creates a “program with data”, second eval (outside) calculates the value of this “program” 

11 . Function Definition > (defun intro (x y) (list x 'this 'is y) ) Intro >; be careful not to quote the arguments when >; defining the function > (intro 2 3) (2 this is 3) > (intro 'stanley 'livingston) (stanley this is livingston) 

12 . Predicate Functions > (atom 2) t > (atom '(a b c)) nil > (listp 2) nil > (listp '(a b c)) t > (equal 2 3) nil > (= 2 3) nil > (equal 6 (* 2 3)) t 

13 .Predicate Functions > (setq a ‘(1 2)) (1 2) > (equal a ‘(1 2)) t > (eql a ‘(1 2)) nil > (null '()) t > (null 2) nil > nil nil > (null nil) t 

14 .Membership Functions > (member 'c '(a b c d)) (c d) > (member 'a '((a b) c d)) This nil member > (member '(d e) '((a b) c (d e) f)) was not using equal nil inside > (assoc 'c '((a b) (c d) (e f))) (c d) And now go to computer and check the following functions 

15 . Another look at recursion 

16 . Recursive Functions Our own definitions of functions member and length (defun my-member(element list) (cond ((null list) nil) ((equal element (car list)) list) (t (my-member element (cdr list))))) (defun my-length(list) (cond ((null list) 0) (t (+ (my-length(cdr list)) 1)))) 

17 . Recursive Functions Counts atoms at all levels of a nested list (defun count-atoms(list) (cond ((null list) 0) ((atom list) 1) (t (+ (count-atoms (car list)) (count-atoms (cdr list)))))) Compare this pattern with patterns of copy and equal functions; this is binary tree recursion 

18 . Linear or cdr recursion (length ‘((1 2) 3 (1 (4 (5))))) 3 + 1 (length (3 (1 (4 (5))))) + 1 (length ((1 (4 (5))))) + 1 (length ()) 0 

19 .Tree of recursion 

20 . Temporary Variable Scopes  LET is the Scheme mechanism for temporarily binding values to names – (LET ( – (name_1 expression_1) – (name_2 expression_2) – <S-expressions> – ))  Evaluate expression_i and bind result to name_i  Name_1 and name_2 can only be used in the <S- expressions> in the body of the LET – static scoping – name_i can’t have a different value assigned 

21 . More of important functions 

22 .let and let* 

23 .How to declare local variables (we are going to need this for iterative functions)? (LET ( ( <var1> <val1> ) ... ( <vark> <valk> ) ) <exp1> ... <expN> )  LET is your way to set up temporary variables. You can initialize each local variable to its value concurrently, then evaluates expressions sequentially. It returns the result of evaluating the last expression.  The default value of local variables declared by LET is NIL. 

24 . An Example of LET Is the situation of the party likely to be safe for you ? That is, are there more ‘friends’ then ‘enemies’ at the party! (defun is-safe-p ( guests ) (let ( (friendly-guests nil) (hostile-guests nil) ) ;; initializations (setq friendly-guests (identify-friends guests)) (setq hostile-guests (identify-enemy guests)) (> (length friendly-guests) (length hostile-guests) ) ;; are there more friendly than hostile )) 

25 . Let* Let* evaluates ALL of the expressions before ANY of the variables are bound. Let* allows you to evaluate things in the order that they are listed (this is not necessarily true of LET) Example of let*: (let* ((sum (+ 8 3 4 2 7)) ; sum needs value (mean (/ sum 5))) ;; calculate the mean value (* mean mean)) ;; return the mean square ***Most of the time it doesn’t matter, but check this if you keep getting errors. 

26 . loop  The simplest form of iteration is the – LOOP (loop (<test condition> ) (return <optional var/val>) [body] ) ;end loop 

27 . IF and IF-ELSE  We will explore the control forms later, here are four to get started – if and if-else: » (if (condition) then) » (if (condition) then else) •then – what to return if the condition is true •else – what to return if the condition is false » these will usually be function calls, but could be values to return •(if (/= y 0) (/ x y) 0) – divide x by y or return 0 if y = 0 

28 . Example Loop (let ((counter 1)) ; initializing my variable (loop (If (= counter 2) (return (+ counter 5)) (+ counter 1) ))) (loop 6 is returned. (<test condition> ) (return <optional var/val>) [body] ) 

29 .Another Example (defun test ( ) (let ((n 0) (lis nil)) ; initializing (loop (if (> n 10) (return lis) (setq lis (cons n lis))) ; this is end of if (setq n (+ n 1)) ))) (loop (<test condition> ) => (10,9,8,7,6,5,4,3,2,1,0) (return <optional var/val>) [body] )