The last of LISPL COMP712 Programming
Languages AUT
1
You have learned how to write conditional statements using COND. An example:
(defun my-length (L) (cond ((null L) 0)
(t (1+ (my-length (cdr L))))))
2
12
You can also use more specific forms: if and unless. Examples:
(defun Q-sort (L) (unless (null L)
(append
(Q-sort (less-than-N (car L) (cdr L)))
(list (car L))
(Q-sort (greater-equal-N (car L) (cdr L))))))
(defun my-length (L)
(if L (1+ (my-length (cdr L))) 0))
3
LISP – iteration
Of course, you can write iterative solutions too and like conditional statements, you have a very general template and some specific ones.
For a general form:
(do (var1 var2) (
)
4
34
An Example:
(defun test (L) (do (x y)
LISP – DO
(do (var1 var2) (
)
Again, this code has a bug.
Variables are not initialised. How?
((null L) (+ x y))
(setf L (cdr L)) (setf x (1+ x)) (setf y (+ 2 y))))
Tell me how test works.
5
LISP – DO – allow initialisation of variables
Just like we could initialise optional variables,
(defun my-length (L &optional (cnt 0)) (cond ((null L) cnt)
(t (my-length (cdr L ) (1+ cnt))))))
We could do the same here:
(defun test (L)
(do ((x 0) (y 0) (L L))
((null L) (+ x y))
(setf L (cdr L)) (setf x (1+ x)) (setf y (+ 2 y))))
6
56
1
LISP – DO – allow initialisation of variables
(defun test (L)
(do((x0)(y0)(LL)) Butwhy(LL)?
((null L) (+ x y))
(setf L (cdr L))
(setf x (1+ x)) (setf y (+ 2 y))))
The code is still not elegant enough, why?
Need to do “housekeeping”
7
LISP – DO – allow updates of variables
(defun test (L)
(do ((x 0) (y 0) (L L))
((null L) (+ x y))
(setf L (cdr L)) (setf x (1+ x)) (setf y (+ 2 y))))
(defun test (L) (do ((x 0 (1+ x))
(y 0 (+ 2 y)) (L L (cdr L)))
; assignment is done ; in parallel
; body of do loop is ((null L) (+ x y)))) ; empty
8
78
LISP – DO – a note on the variables
What is the output of test when called (test ‘(a b c))?
(defun test (L)
(do ((x 0) (y 0) (L L))
((null L) (+ x y)) (setf L (cdr L))
(setf x (1+ x)) (setf y (+ 2 y))))
9
9
LISP – DO – a note on the variables
What is the output of test when called (test ‘(a b c)) and why?
(defun test (L)
(do ((x 0) (y 0) (L L))
((null L) (+ x y)) (setf L (cdr L)) (setf x (1+ x)) (setf y (+ 2 y)))
(print L))
(a b c) – This means variables declared are local variables
10
9 10
LISP – DO – a note on the variables
What is the output of the function when called (test ‘(a b c)) and why?
(defun test (L)
(do ((x 0) (y 0) (L L))
((null L) (+ x y)) (setf L (cdr L)) (setf x (1+ x)) (setf y (+ 2 y)))
L)
(a b c) – You don’t really need to use print.
11
LISP – DO – a note on the variables
What is the output of the function when called (test ‘(a b c)) and why?
(defun test (L)
(do ((x 0) (y 0) (L L))
((null L) (+ x y)) (setf L (cdr L)) (setf x (1+ x)) (setf y (+ 2 y)))
‘L)
L – don’t forget the quoteJ
12
11 12
2
LISP – DO – a note on the variables
What is the output of test when called (test ‘(a b c)) and why?
(defun test (L)
(do ((x 0) (y 0) (L L))
((null L) (+ x y)) (setf L (cdr L)) (setf x (1+ x)) (setf y (+ 2 y)))
(print x))
Error –x is local in the do-form
13
(defun test (L)
(do ((x 0 (1+ x))
(y 0 (+ 2 y))
(L L (cdr L)))
((null L) (+ x y))))
OK, back to the proper use of DO in this function test
LISP – DO
Now, using DO, write a function which given a list of numbers, return their sum
Ø (total-using-do ‘(1 2 3 4 5)) 15
14
13 14
LISP – DO
Using DO, write a function which given a list of numbers, return their sum
Ø (total-using-do ‘(1 2 3 4 5)) 15
(defun total-using-do (L) (do ((L L (cdr L))
(ans 0 (+ ans (car L)))) ((null L) ans)))
15
LISP – DO
Using DO, write a function car-list which given any number of lists will return a list of all the first element in each list.
> (car-list ‘(1 2 3) ‘(4 5 6) ‘(7 9)) (1 4 7)
An example function to remind you:
(defun total-using-do (L) (do ((L L (cdr L))
(ans 0 (+ ans (car L)))) ((null L) ans)))
16
15 16
LISP – DO
Using DO, write a function car-list which given any number of lists will return a list of all the first element in each list.
> (car-list ‘(1 2 3) ‘(4 5 6) ‘(7 9)) (1 4 7)
(defun car-list (&rest L) (do ((L L (cdr L))
(ans nil (cons (caar L) ans))) ((null L) (reverse ans)))
17
LISP – DO
Using DO, write a function, empty-lists, which given a number, n, will return a list of n empty lists.
Ø (empty-lists 5) (nil nil nil nil nil)
An example function to remind you:
(defun total-using-do (L) (do ((L L (cdr L))
(ans 0 (+ ans (car L)))) ((null L) ans)))
18
17 18
3
LISP – DO
Using DO, write a function, empty-lists, which given a number, n, will return a list of n empty lists.
Ø (empty-lists 5) (nil nil nil nil nil)
(defun empty-lists (n) (do ((n n (1- n))
(ans nil (cons nil ans))) ((zerop n) ans)))
19
LISP – DO*
Do* allows serial assignment of variables.
(defun total-using-do (L) (do* ((L L (cdr L))
(ans 0 (+ ans (car L)))) ((null L) ans)))
Ø(total-using-do ‘(1 2 3 4 5)) ? error
20
19 20
LISP – DO*
(defun total-using-do (L) (do* ((L L (cdr L))
(ans 0 (+ ans (car L)))) ((null L) ans)))
Modify the above to make it correct:
(defun total-using-do (L)
(do* ((ans 0 (+ ans (car L)))
(L L (cdr L)))
((null L) ans)))
21
LISP – DO & DO*
Both work; can you see why:
(defun total-using-do (L) (do ((L L (cdr L))
(ans 0 (+ ans (car L)))) ((null L) ans)))
(defun total-using-do (L)
(do* ((ans 0 (+ ans (car L)))
(L L (cdr L)))
((null L) ans)))
22
21 22
LISP – DO
(defun total-using-do (L)
(do* ((ans 0 (+ ans (car L)))
(L L (cdr L))) ((null L) ans)))
Write a recursive version for total-using-do.
(defun total (L) (cond ((null L) 0)
(t (+ (car L) (total (cdr L)))))) Which is better?
23
LISP – DO
(defun mysterious (L1 L2) (do ((L1 L1 (cdr L1)) (L2 L2 (cdr L2))
(ans nil (cons (+ (car L1) (car L2)) ans)))
((or (null L1) (null L2)) (reverse ans))))
What does this function return?
result
initialisation computations
24
23 24
4
LISP – DO
Using DO, write a function which given a non-empty list of numbers, returns its average.
(defun average-do (L) (do ((L L (cdr L))
(total 0 (+ total (car L)))) ((null L) (/ total (length L)))))
Problem? Division by zero
25
LISP – DO
The correct solution:
(defun average-do (L) (do ((L1 L (cdr L1))
(total 0 (+ total (car L1)))) ((null L1) (/ total (length L)))))
26
25 26
LISP – DOLIST
Can use a simplified DO:
(defun average (L)
(dolist (x L (/ total count))
(setf total (+ total x)) (setf count (1+ count))))
Problem? variables total and count are not initialised and declared as global
27
LISP – DOLIST
Try doing this:
(defun average (L)
(setf total 0) (setf count 0)
(dolist (x L (/ total count)) (setf total (+ total x)) (setf count (1+ count))))
But, total and count are still declared as global variables
28
27 28
LISP – LET
LET allows you to declare local variables (or do lexical scoping)
(defun average (L)
(let (total count)
(setf total 0) (setf count 0) (dolist (x L (/ total count))
(setf total (+ total x))
(setf count (1+ count)))))
Ugly, why?
Should initialise as you declare them
29
LISP – LET
We can initialise the variables in the same way as DO
(defun average (L)
(let ((total 0) (count 0))
(setf total 0) (setf count 0) (dolist (x L (/ total count))
(setf total (+ total x)) (setf count (1+ count)))))
30
29 30
5
LISP – LET
We can use LET* as well:
(defun average (L)
(let* ((total 0) (count 0))
(dolist (x L (/ total count)) (setf total (+ total x)) (setf count (1+ count)))))
Any problem with the use of let* above? no
31
LISP – LET*
Ø (defvar x 5) ; declare global var x 5
Ø(let* ((x 6) (y x)) y) ?
Ø(let ((x 6) (y x)) y) ?
Try this:
32
31 32
LISP – DOTIMES
Another simplified DO:
(defun average (L) (let ((total 0))
(dotimes (x (length L) (/ total x)) (setf total (+ total (car L))) (setf L (cdr L)))))
Note that x starts with 0 and count up to (length L) – 1 but it stops when x = (length L).
33
LISP – DOTIMES
Using dotimes, write a function, power-n, that given 2 numbers, n and m, return mn.
(defun power-n (n m) (let ((result 0))
(dotimes (count n result) (setf result (* m result)))))
However, there is an error!
34
33 34
LISP – FUNCALL & APPLY
Funcall and Apply allow you to give functions as arguments:
Ø(funcall ‘+ 1 2 3 4 5) 15
Ø(apply ‘+ ‘(1 2 3 4 5)) 15
Can you see the difference?
35
LISP – FUNCALL & APPLY
Ø(funcall ‘+ 1 2 3 4 5) 15
Ø(apply ‘+ ‘(1 2 3 4 5)) 15
Use FUNCALL when you specify individual arguments. Use APPLY when your arguments are specify in a list form.
36
35 36
6
LISP – FUNCALL & APPLY
However, the list form can vary:
Ø (apply ‘list ‘(1 2) ‘(3 4 5)) ((1 2) 3 4 5)
Ø (apply ‘list 1 2 ‘(3 4) ‘(5 6)) (1 2 (3 4) 5 6)
Ø(apply ‘list ‘(1 2) 3 4)
Error (last argument must be a list).
37
LISP – FUNCALL & APPLY
However, the list form can vary:
Put inside the list
(apply ‘list ‘(1 2) (3 4 5))
(list ‘(1 2) 3 4 5)
Read as transform to
(apply ‘list 1 2 ‘(3 4) ‘(5 6))
(list 1 2 ‘(3 4) 5 6)
Failed to put inside the list
(apply ‘list ‘(1 2) 3 4)
Error (last argument must be a list).
Put inside the list
38
37 38
LISP – FUNCALL & APPLY
Ø (funcall ‘+ 1 2 3 4 5) For funcall, you 15 specify individual
arguments.
Ø(apply ‘+ ‘(1 2 3 4 5)) 15
For apply, you specify its arguments as a list but, as you have seen, we only need the last argument to be a list. Why is this the case?
If not, you can only apply functions whose arguments must either be a list or ALL are list!
39
LISP – FUNCALL & APPLY
Ø(funcall ‘+ 1 2 3 4 5) 15
Ø(apply ‘+ ‘(1 2 3 4 5)) 15
If this is not the case, you can only apply a function whose arguments must ALL be a list
40
39 40
LISP – FUNCTION or #’
It is better to use #’ rather than ‘ to specify a function
Ø(funcall #‘+ 1 2 3 4 5) 15
Ø(apply #‘+ ‘(1 2 3 4 5)) 15
#’ specifically takes the function definition of the variable and also provides the correct environment for its evaluation (more later).
41
LISP – FUNCTION or #’
What is returned? Ø(funcall #‘cons ‘a ‘(b c))
(a b c)
Ø(apply #‘cons ‘a ‘(b c)) error
For apply: (apply #’cons ‘a ‘((b c)))
42
41 42
7
LISP
Write a function which given 4 arguments, returns a list consisting of all four arguments.
Ø(list-me2 ‘a ‘b ‘c ‘d) (a b c d)
(defun list-me2 (r s t u) (list r s t u)) Hopefully, no one tries to use funcall 😉
How about a function given any number of arguments, returns a list?
43
LISP
Write a function which given a list of numbers, returns a list with all the numbers increase by 1
Ø(add-1-all ‘(1 2 3 4)) (2 3 4 5)
(defun add-1-all (L) (cond ((null L) nil)
(t (cons (1+ (car L)) (add-1-all (cdr L))))))
44
43 44
LISP – MAPCAR
(defun add-1-all (L) (cond ((null L) nil)
(t (cons (1+ (car L)) (add-1-all (cdr L)]
1+ (1 2 3 4 5)
Use MAPCAR
(2 3 4 5 6)
(defun add-1-all (L) (mapcar #’1+ L))
Mapcar is like apply but it takes a function and apply to every element in the list
45
LISP – MAPCAR
Ø(mapcar #’list ‘(1 2 3 4) ‘(a b c d)) ?
Ø(mapcar #’list ‘(1 2 3 4) ‘(a b c)) ?
Ø(mapcar #’cons ‘(a b c) ‘(1 2 3 4)) ?
46
45 46
LISP – MAPCAR
Ø(mapcar #’list ‘(1 2 3 4) ‘(a b c d)) ((1 a) (2 b) (3 c) (4 d))
Ø(mapcar #’list ‘(1 2 3 4) ‘(a b c)) ((1 a) (2 b) (3 c))
Ø(mapcar #’cons ‘(a b c) ‘(1 2 3)) ((a.1) (b.2) (c.3))
47
What is the difference?
(defun add-1-all (L) (mapcar #’1+ L))
(defun add-1-all (L) (mapcar ’1+ L))
(defun add-1-all (L) (mapcar 1+ L))
‘1+ still works because quote suppresses evaluation of 1+ and so mapcar sees 1+ and takes its function definition which exists.
1+ does not work because LISP tries to evaluate 1+ and that has no value in it.
When LISP see #’1+, it evaluates it to return its function definition
48
47 48
8
LISP – MAPCAR
Using mapcar, write a function which given a list of lists will add e to the first of each list.
Ø (add-e ‘((a b) (c d) (e f))) ((e a b) (e c d) (e e f))
(defun add-e (L)
(mapcar #’add-e-aux L))
(defun add-e-aux (L) (cons ‘e L))
Again, this is not good, why?
49
LISP – LAMBDA
LISP allows you to create nameless function. Use lambda instead of defun
(defun add-e (L) (mapcar #’add-e-aux L)) (defun add-e-aux (L) (cons ‘e L))
(defun add-e2 (L)
(mapcar #’(lambda (x) (cons ‘e x)) L))
50
49 50
What is the difference?
(defun add-1-all (L) (mapcar #’1+ L)) (defun add-1-all (L) (mapcar ’1+ L)) (defun add-1-all (L) (mapcar 1+ L)) (defun add-e2 (L)
(mapcar #’(lambda (x) (cons ‘e x)) L))
(defun add-e2 (L)
(mapcar ’(lambda (x) (cons ‘e x)) L))
Again, the last one suppresses evaluation and so you get an error because it is just a list
51
LISP – LAMBDA
Using mapcar, write a function which given a number n and a list of numbers, will subtract n from each number in the list
Ø(subtract-n 5 ‘(9 10 11)) (4 5 6)
(defun subtract-n (n L)
(mapcar #’(lambda (x) (- x n)) L))
52
51 52
53 54
LISP – LAMBDA
What does this mean:
(setf x (lambda (y) (1+ y))
Evaluate this and return a function definition (setf x #’(lambda (y) (1+ y))
Evaluate this and return a function definition + its environment
(mapcar x ‘(1 2 3))à(2 3 4) in both cases
53
LISP – LAMBDA
But what about this:
(setf x ‘(lambda (y) (1+ y))
Evaluate this and return a list!
(mapcar x ‘(1 2 3))àerror! and:
(setf x #’(lambda (y) (1+ y))
> (x 5)
? Error because x has no function definition although its value is a function
54
9
LISP – LAMBDA
(setf x #’(lambda (y) (1+ y)) > (x 5)
The above doesn’t work but would any of these work?
(mapcar x ‘(1 2 3))à (2 3 4) (funcall x 5)à 6 (apply x 5)à error
Remember the last one needs a list as argument. (apply x ‘(5))à6
55
Recall this problem
Using mapcar, write a function which given a list of lists will add e to the first of each list.
Ø (add-e ‘((a b) (c d) (e f))) ((e a b) (e c d) (e e f))
(defun add-e (L) (mapcar #’add-e-aux L)) (defun add-e-aux (L) (cons ‘e L))
Again, this is not good, why?
56
55 56
The power of LAMBDA
Modify add-e (without using lambda) so that it can take 2 arguments, the list and the element to be added.
Ø (add-this ‘x ‘((a b) (c d) (e f))) ((x a b) (x c d) (x e f))
(defun add-this (a L) (mapcar #’add-aux L)) (defun add-aux (L) (cons a L))
Error!! Why?
57
The power of LAMBDA
Modify add-e (using lambda) so that it can take 2 arguments, the list and the element to be added.
Ø (add-this ‘x ‘((a b) (c d) (e f))) ((x a b) (x c d) (x e f))
(defun add-this (a L)
(mapcar #’(lambda (x) (cons a x)) L))
The above works beautifully! Why?
#’ provides the correct environment for evaluating the function
58
57 58
LISP – REMOVE-IF
Consider this expression: Ø(mapcar #’oddp ‘(1 2 3 4 5))
(t nil t nil t) ßugly result?
Ø(remove-if-not #’oddp ‘(1 2 3 4 5))
(1 3 5)
Ø(remove-if #’oddp ‘(1 2 3 4 5)) ?
59
LISP – REMOVE-IF
Write a function which given a list of numbers returns a list of two lists: one is a list of odd numbers and the other is a list of even numbers.
Ø(split-odd-even ‘(1 2 3 4 5) ((1 3 5) (2 4))
(defun split-odd-even (L) Comment on (list (remove-if #’evenp L) the code?
(remove-if #’oddp L)))
This is a clear example of an elegant algorithm (for humans) but inefficient for machines –
why?
60
59 60
10