Transcript *** 1

FUNCTIONAL PROGRAMMING
05 Functions
FUNCTIONS - GLOBAL FUNCTIONS

fboundp
Tells whether there is a function with a given symbol as its
name
 > (fboundp ‘+)
T
 > (symbol-function ‘+)
#<SYSTEM-FUNCTION +>


(setf (symbol-function ‘add2)
#’(lambda (x) (+ x 2)))

> (add2 1)
3
FUNCTIONS - GLOBAL FUNCTIONS

(setf func_name)





(defun primo (lst) (car lst))
(defun (setf primo) (val lst)
(setf (car lst) val))
> (let ((x (list ‘a ‘b ‘c)))
(setf (primo x) 480)
x)
(480 B C)
The first parameter : new value
The remaining parameters : the arguments of this setf
function
FUNCTIONS - GLOBAL FUNCTIONS

Documentation string
If you make a string the first expression in the body of a
function defined with defun, then this string will become the
function’s documentation string
 (defun foo (x)
“Implements an enhanced paradigm of diversity.”
x)
 > (documentation ‘foo ‘function)
“Implements an enhanced paradigm of diversity.”

FUNCTIONS - LOCAL FUNCTIONS

Functions defined via defun or setf of symbol-function
are global functions


You can access global functions anywhere
Local functions can be defined with labels, which is a
kind of let for functions

(labels ((add10 (x) (+ x 10))
(consa (x) (cons ‘a x)))
(consa (add10 3)))
(A . 13)
FUNCTIONS - LOCAL FUNCTIONS

> (labels ((len (lst)
(if (null lst)
0
(+ (len (cdr lst)) 1))))
(len ‘(a b c)))
3
FUNCTIONS - PARAMETER LISTS

&rest
Insert &rest before the last variable in the parameter list of a
function
 This variable will be set to a list of all the remaining
arguments
 (defun our-funcall (fn &rest args)
(apply fn args))

FUNCTIONS - PARAMETER LISTS

&optional
All the arguments after it could be omitted
 (defun philosoph (thing &optional property)
(list thing ‘is property))
 > (philosoph ‘death)
(DEATH IS NIL)
 The explicit default of the optional parameter

(defun philosoph (thing &optional (property ‘fun))
(list thing ‘is property))
 > (philosoph ‘death)
(DEATH IS FUN)

FUNCTIONS - PARAMETER LISTS

&key





A keyword parameter is a more flexible kind of optional
parameter
These parameters will be identified not by their position, but
by symbolic tags that precede them
> (defun keylist (a &key x y z)
(list a x y z))
KEYLIST
> (keylist 1 :y 2)
(1 NIL 2 NIL)
> (keylist 1 :y 3 :x 2)
(1 2 3 NIL)
FUNCTIONS – EXAMPLE: UTILITIES
> (single? ‘(a))
T
→ returns true when its argument is a list
of one element
 > (append1 ‘(a b c) ‘d)
(A B C D) → adds an element to the end of the
list
 > (map-int #’identify 10)
(0 1 2 3 4 5 6 7 8 9) → returns a list of the
results of calling the
function on the integers
from 0 to n-1

FUNCTIONS – EXAMPLE: UTILITIES
> (map-int #’(lambda (x) (random 100))
10)
(85 40 73 64 28 21 40 67 5 32)
 > (filter #’(lambda (x)
(and (evenp x) (+ x 10)))
‘(1 2 3 4 5 6 7)
(12 14 16) → returns all the non-nil values
returned by the function as it is
applied to the elements of the list
 > (most #’length ‘((a b) (a b c) (a)))
(A B C)
→ returns the element of a list with
3
the highest score, according to
some scoring function

FUNCTIONS – EXAMPLE: UTILITIES
(defun single? (lst)
(and (consp 1st) (null (cdr lst))))
(defun appendl (1st obj)
(append 1st (list obj)))
(defun map-int (fn n)
(let ((acc nil))
(dotimes (i n)
(push (funcall fn i) acc))
(nreverse acc)))
(defun filter (fn lst)
(let ((acc nil))
(dolist (x lst)
(let ((val (funcall fn x)))
(if val (push val acc))))
(nreverse acc)))
FUNCTIONS – EXAMPLE: UTILITIES
(defun most (fn 1st)
(if (null 1st)
(values nil nil)
(let* ((wins (car lst))
(max (funcall fn wins)))
(dolist (obj (cdr lst))
(let ((score (funcall fn obj)))
(when (> score max)
(setf wins obj
max score))))
(values wins max))))
FUNCTIONS – CLOSURES
(defun combiner (x)
(typecase x
(number #’+)
(list
#’append)
(t
#’list)))
 (defun combine (&rest args)
(apply (combiner (car args))
args))
 > (combine 2 3)
5
 > (combine ‘(a b) ‘(c d))
(A B C D)

FUNCTIONS – CLOSURES
When a function refers to a variable defined outside it, it
is called a free variable
 Closure

A function that refers to a free variable
 (defun add-to-list (num lst)
(mapcar #’(lambda (x)
(+ x num))
lst))


num is free
(defun make-adder (n)
#’(lambda (x)
(+ x n)))
→ returns a function
 n is free

FUNCTIONS – CLOSURES
(setf add3 (make-adder 3))
#<CLOSURE: LAMBDA (X) (+ X N)>
 > (funcall add3 2)
5
 (setf add27 (make-adder 27))
#<CLOSURE: LAMBDA (X) (+ X N)>
 > (funcall add27 2)
29

FUNCTIONS – CLOSURES

Make several closures share variables
(let ((counter 0))
(defun reset ( )
(setf counter 0))
(defun stamp ( )
(setf counter (+ counter 1))))
 > (list (stamp) (stamp) (reset) (stamp))
(1 2 0 1)
 You can do the same thing which a global counter, but this
way the counter is protected from unintended references

FUNCTIONS –
EXAMPLE: FUNCTION BUILDERS
(defun disjoin (fn &rest fns)
(if (null fns)
fn
(let ((disj (apply #’disjoin fns)))
#’(lambda (&rest args)
(or (apply fn args) (apply disj args))))))
FUNCTIONS –
EXAMPLE: FUNCTION BUILDERS
(defun conjoin (fn &rest fns)
(if (null fns)
fn
(let ((conj (apply #’conjoin fns)))
#’(lambda (&rest args)
(and (apply fn args) (apply conj args))))))
(defun curry (fn &rest args)
#’(lambda (&rest args2)
(apply fn (append args args2))))
(defun rcurry (fn &rest args)
#’(lambda (&rest args2)
(apply fn (append args2 args))))
(defun always (x) #’(lambda (&rest args) x))
FUNCTIONS –
EXAMPLE: FUNCTION BUILDERS
> (mapcar (disjoin #’integerp #’symbolp)
‘(a “a” 2 3))
(T NIL T T)
 > (mapcar (conjoin #’integerp #’oddp)
‘(a “a” 2 3))
(NIL NIL NIL T)
 > (funcall (curry #’- 3) 2)
1
 > (funcall (rcurry #’- 3) 2)
-1

FUNCTIONS – RECURSION

Recursion plays a greater role in Lisp than in most other
languages

Functional programming


Recursive algorithms are less likely to involve side-effects
Recursive data structure
Lisp’s implicit use of pointers makes it easy to have recursively
defined data structures
 The most common is the list: a list is either nil, or a cons whose cdr
is a list


Elegance
Lisp programmers care a great deal about the beauty of their
programs
 Recursive algorithms are often more elegant than their iterative
counterparts

FUNCTIONS – RECURSION

To solve a problem using recursion, you have to
Show how to solve the problem in the general case by
breaking it down into a finite number of similar, but smaller,
problems
 Show how to solve the smallest version of the problem - the
base case - by some finite number of operations


<Example1> Finding the length of a proper list
In the general case, the length of a proper list is the length of
its cdr plus 1
 The length of an empty list is 0

FUNCTIONS – RECURSION

<Example２> member
Something is a member of a list if it is the first element, or a
member of the cdr
 Nothing is a member of the empty list


<Example3> copy-tree
The copy-tree of a cons is a cons made of the copy-tree of its
car, and the copy-tree of its cdr
 The copy-tree of an atom is itself

FUNCTIONS – RECURSION

The obvious recursive algorithm is not always the most
efficient
E.g. Fibonacci function
1. Fib(0)=Fib(1)=1
2. Fib(n)=Fib(n-1)+Fib(n-2)
 (defun fib (n)
(if (<= n 1)
1
(+ (fib (- n 1))
(fib (- n 2)))))
 The recursive version is appallingly inefficient
 The same computations are done over and over

FUNCTIONS – RECURSION
(defun fib (n)
(do ((i n (- i 1))
(f1 1 (+ f1 f2))
(f2 1 f1))
((<= i 1) f1)))
 The iterative version is not as clear, but it is far more efficient
 However, this kind of thing happen very rarely in practice

FUNCTIONS

Homework (Due April 14)

Use the lambda function and closures to write a function
called our-complement that takes a predicate and returns the
opposite predicate. For example:
> (mapcar (our-complement #’oddp)
‘(1 2 3 4 5 6))
(NIL T NIL T NIL T)