Common Lisp notes and thinkings (Part I: Functions)

1. (eq function object) ?
- 1.1. Three state of a function
- 1.2. Closure: those functions who have undefined variable
2. Functional programming principle
3. From Bottom to Top: another programming Strategy
- 3.1. Some abstraction examples of functions
- 3.2. Rethink Recursion

1. (eq function object) ?

Yes.

1.1. Three state of a function

We use (defun plus1 (x) (\+ x 1)) to define a function named 'plus1, and we can use (plus1 2) to get a result of 3. This is the most of operation in LISP, where we can summerize

three types of state for this function, as:

plus1: which is the funcall;
'plus1: which is the name of this function;
#'plus1: which is the data of this function, i.e. (x) (\+ 1)

1.2. Closure: those functions who have undefined variable

(setq w
(let ((a 3))
  (defun plus-a (x) (+ x a))
         (plus-a 5)
))

In this example, we have a as the free variable (which is undefined in function plus-a while we use a in the function body). Thus, we can use plus-a to produce different functions with different a. Here plus-a is a closure.

2. Functional programming principle

What is FPP?

FPP denotes: use the return value, instead of setted value.

For example, we want (+1 a) return the result "a+1" instead of change the value of a to "a+1".

FFP tell you "I want to do such things", while the instruction principle tell you "I have do such things".

Example:

(defun f (x)
  (list 'a (expt (car x) 2)))

(defun f2 (x)
  (let (y sqr)
    (setq y (car x))
    (setq sqr (expt y 2))
    (list 'a sqr)))

That's the main obstacle of learning LISP, if you have already know C++, JAVA, PYTHON, and so on.

3. From Bottom to Top: another programming Strategy

What we learn in courses or real-world encourage us to give a plan first, and then plan to divide a complex project into several simple parts, and finally solve these parts to obtain a final results.

That's a great idea. However, sometimes it is vital to begin with another direction, which argues that:

planning is difficult and complex, people are lazy;
we have no understanding of what we need to do, so the planning might be wroning most of the time;
the enthusim of one thing always takes 3 minutes, indicating the reward of what we do is quite important;

Therefore, I recommand another programming strategy, FBTT, after you have a thoroughly plan of what you need to do.

The functional-style programming is suitable to these kind of programming strategy, because we can test every function, and develope new language on our own fields.

3.1. Some abstraction examples of functions

(proclaim '(inline last1 single append1 nconc1 mklist)) ;; compile it

;; git last element
(defun last1 (ls) (car (last ls)))
;; if single or not
(defun single (ls) (and (consp ls) (not (cdr ls))))
;; append an element
(defun append1 (ls obj) (append ls (list obj)))
;; append an element and change the input parameter
(defun nconc1 (ls obj) (nconc ls (list obj)))
;; construct a list.
(defun mklist (obj) (if (listp obj) obj (list obj)))

;; whether len(x)>len(y) or not.
(defun longer (x y)
  (labels ((compare (x y)
                    (and (consp x) (or (null y) (compare (cdr x) (cdr y))))))
    (if (and (listp x) (listp_y))
        (compare x y)
      (> (length x) (length y)))))

;; record the result if true, else do not record.
(defun filter (fn ls)
  (let ((acc nil))
    (dolist (x ls)
      (let ((val (funcall fn x)))
        (if val (push val acc)))
      (nreverse acc))))

;; group source list into n numbers sub-lists.
(defun group (source n)
  (if (zerop n) (error "zero length"))
  (labels ((rec (source acc)
                (let ((rest (nthcdr n source)))
                  (if (consp rest)
                      (rec rest (cons (subseq source 0 n) acc)))
                  (nreverse (cons source acc)))))
    (if source (rec source nil) nil)))

(defun flatten (x)
  (labels ((rec (x acc)
                (cond ((null x) acc)
                      ((atom x) (cons x acc))
                      (t (rec (car x) (rec (cdr x) acc))))))
    (rec x nil)))

(defun prune (test tree)
  (labels ((rec (tree acc)
                (cond ((null tree) (nreverse acc))
                      ((consp (car tree))
                       (rec (cdr tree)
                            (cons (rec (car tree) nil) acc)))
                      (t (rec (cdr tree)
                              (if (funcall test (car tree))
                                  acc
                                (cons (car tree) acc)))))))
    (rec tree nil)))


(defun find2 (fn ls)
  (if (null ls)
      nil
    (let ((val (funcall fn (car ls))))
      (if val(values (car ls) val)
        (find2 fn (cdr ls))))))

(defun before (x y ls &key (test #'eql))
  (and ls
       (let ((first (car ls)))
         (cond ((funcall test y first) nil)
               ((funcall test x first) nil)
               (t (before x y (cdr ls) :test test))))))

(defun after (x y ls &key (test #' eql))
  (let ((rest (before y x ls :test test)))
    (and rest (member x rest :test test))))

(defun duplicate (obj ls &key (test #'eql))
  (member obj (cdr (member obj ls :test test))
          :test test))

(defun split-if (fn ls)
  (let ((acc nil))
    (do ((src ls (cdr src)))
        ((or (null src) (funcall fn (car src)))
         (values (nreverse acc) src))
      (push (car src) acc))))


(defun most (fn lst)(if (null lst)
(values nil nil)
(let* ((wins (car lst))(max (funcall fn wins)))
(dolist (obj (cdr lst))(let ((score (funcall fn obj)))
(when (> score max)(setq wins obj
max score))))(values wins max))))
(defun best (fn lst)(if (null lst)nil(let ((wins (car lst)))(dolist (obj (cdr lst))
(if (funcall fn obj wins)
(setq wins obj)))wins)))
(defun mostn (fn lst)(if (null lst)
(values nil nil)
(let ((result (list (car lst)))(max (funcall fn (car lst))))(dolist (obj (cdr lst))
(let ((score (funcall fn obj)))(cond ((> score max)
(setq max score
result (list obj)))((= score max)
(push obj result)))))(values (nreverse result) max))))

(defun map0-n (fn n)(mapa-b fn 0 n))
(defun map1-n (fn n)(mapa-b fn 1 n))
(defun mapa-b (fn a b &optional (step 1))(do ((i a (+ i step))
(result nil))
((> i b) (nreverse result))(push (funcall fn i) result)))
(defun map-> (fn start test-fn succ-fn)(do ((i start (funcall succ-fn i))
(result nil))
((funcall test-fn i) (nreverse result))(push (funcall fn i) result)))
(defun mappend (fn &rest lsts)
(apply #'append (apply #'mapcar fn lsts)))
(defun mapcars (fn &rest lsts)(let ((result nil))(dolist (lst lsts)(dolist (obj lst)
(push (funcall fn obj) result)))(nreverse result)))
(defun rmapcar (fn &rest args)
(if (some #'atom args)
(apply fn args)(apply #'mapcar
#'(lambda (&rest args)
    (apply #'rmapcar fn args))args)))

(defun readlist (&rest args)(values (read-from-string(concatenate 'string "("
(apply #'read-line args)")"))))
(defun prompt (&rest args)
(apply #'format *query-io* args)(read *query-io*))
(defun break-loop (fn quit &rest args)(format *query-io* "Entering break-loop.'~%")(loop
(let ((in (apply #'prompt args)))
(if (funcall quit in)
(return)
(format *query-io* "~A~%" (funcall fn in))))))

(defun mkstr (&rest args)
(with-output-to-string (s)(dolist (a args) (princ a s))))
(defun symb (&rest args)
(values (intern (apply #'mkstr args))))
(defun reread (&rest args)
(values (read-from-string (apply #'mkstr args))))
(defun explode (sym)(map 'list #'(lambda (c)
(intern (make-string 1:initial-element c)))(symbol-name sym)))

3.2. Rethink Recursion

while other languages use loop for a complicated object, lisp prefer recusion. Consider a function that returns the length of a list:

# similar to len(x)
def len(ls):
    i=0
    for x in ls:
        i+=1
    return i

In lisp we may write it as:

(defun len (ls)
  (if (null ls) 0 (1+ (len (cdr ls)))))

Unfortunately the second example code is not as effective as loop, because the first python example is the "flattened" version of the second one, where we should store the function call of different usages of len in the stack.

However, we can change such cdr recursion into a tail recursion (as we know, a tail-recursion is equvilent to a loop), by introduce two variables:

a accumulator (named acc) similar to i in python code;
another style of recursor function rec which is the same to len.

(defun len (ls)
  (labels ((rec (ls acc)
                (if (null ls)
                    acc
                  (rec (cdr ls) (1+ acc)))))
    (rec ls 0)))

noted that here the tail-recursion is also a cdr-recursion, and what we do is move the operation (here it is 1+) to the accumulator.

That's all for the "function" part. In next notes I will detail how to understand and use macro in common lisp.