Table of Contents
- 1. PENDING
- 2. LISP
- 3. Comments
- 4. Symbols, forms, operators…
- 5. Character Syntax
- 6. Scope
- 7. Recursion
- 8. ASDF
- 8.1. To begin working with ASDF, you need:
- 8.2. To print current ASDF version:
- 8.3. Put all of your systems in one of the standard locations, subdirectories of
- 8.4. If you are installing software in a non standard location,
- 8.5. To load a system:
- 8.6. You can reset the source-registry configuration with:
- 8.7. Before dumping your Lisp image, you should:
- 8.8. Where object files are stored?
- 8.9. The following snippet, clear the ASDF configuration automatically
- 8.10. Other operations:
- 8.10.1. clear-system clears the entry for a system in the database of systems
- 8.10.2. compile-system
- 8.10.3. find-system
- 8.10.4. load-system applies operate with the operation from load-system-operation
- 8.10.5. loaded-systems return a list of the names of loaded systems
- 8.10.6. operate generic function usually abbreviated as oos
- 8.10.7. require-system same as load-system but skips to update systems that are
- 8.10.8. test-system
- 8.11. find asdf version
- 9. Quicklisp
- 10. Interesting packages
- 11. Exercises
- 12. Quines
- 13. Code
- 14. Papers
- 15. Common Lisp
- 15.1. REPL (Read-Eval-Print Loop)
- 15.2. Read tables
- 15.3. Comments
- 15.4. Objects
- 15.4.1. Special Forms
- 15.4.2. Symbols
- 15.4.3. Types
- 15.4.4. Keywords
- 15.4.5. Booleans
- 15.4.6. Numbers
- 15.4.7. Characters
- 15.4.8. Strings
- 15.4.9. Lists
- 15.4.10. Bitvectors
- 15.4.11. Vectors
- 15.4.12. Arrays
- 15.4.13. Sequences
- 15.4.14. Date & time
- 15.4.15. Predicates
- 15.4.16. Math
- 15.4.17. Conses
- 15.4.18. Lists
- 15.4.19. Sets
- 15.4.20. Mappings
- 15.4.21. Flow control
- 15.4.22. Loop
- 15.4.23. Printing
- 15.4.24. Format
- 15.5. Functions
- 15.6. Anonymous Functions
- 15.7. Generic Functions
- 15.8. User-defined functions
- 15.9. Constants
- 15.10. Variables
- 15.11. Assigments
- 15.12. Conditions
- 15.13. Classes
- 15.14. Macros
- 15.15. Packages
- 15.16. System
- 15.17. Features
- 15.18. Sintactic sugar
- 15.19. Enviroments
- 15.20. OS
- 16. Hints
- 17. Links
- 17.1. http://www.gnu.org/software/gcl/gcl.html
- 17.2. http://hyperpolyglot.org/lisp"
- 17.3. http://stackoverflow.com/questions/2353353/how-to-process-input-and-output-streams-in-steel-bank-common-lisp
- 17.4. http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html
- 17.5. http://www.informatimago.com/toc.html
- 17.6. https://blog.jeaye.com/2015/09/27/parenscript-ajax/
- 17.7. http://www.cliki.net/ParenscriptTipsAndTricks
- 17.8. https://github.com/aarvid/SmackJack/blob/master/demo/demo.lisp
1. PENDING
check-type readtable-case do-symbols do-external-symbols with-gensyms ldiff tree-equal copy-tree subst subst-if
2. LISP
List Processor
3. Comments
;;;; Four semicolons are used for a file header comment. ;;; A comment with three semicolons will usually be a paragraph ;;; comment that applies to a large section of code that follows,
(defun foo (x) (dotimes (i x) ;; Two semicolons indicate this comment applies to the code ;; that follows. Note that this comment is indented the same ;; as the code that follows. (some-function-call) (another i) ; this comment applies to this line only (and-another) ; and this is for this line;
4. Symbols, forms, operators…
self evaluating symbol A symbol that evaluates to itself like t, nil or any keyword
A lisp form is a lisp datum that is also a program, that is, it can be evaluated without an error.
(3 4 1) Is a lisp datum, it's a list of 3, 4 and 1. This is not a form however as trying to evaluate it does not result into another datum. But rather an error.
3 Is a datum, and a form, also called a normal form or a self-evaluating datum, it evaluates to itself.
(+ 3 4 1) Is a compound form, evaluating it results into the normal form 8. Apart from normal forms and compound forms, compound forms can be subdivided into procedure calls and special forms (also called syntax) but more properly, the head of a special form is the syntax, as in: (if (oddp 2) (print "me") (print "or me")) This is a special form because it's head is syntax, and not a procedure, the only difference between procedure calls and special forms is that procedure calls see all of the arguments of the form as forms in itself and try to evaluate it first and special forms not necessarily do that. As we understand, only the second and fourth member of this compound form get evaluated, the first member is syntax, and the third is discarded in this case. As we know for instance: ((a 1) (b 2)) Is not a form in Common Lisp, it could be a valid form in Scheme, but only if the form (a 1) evaluates to a procedure datum. So: (let ((a 1) (b 2)) (+ a b)) Is a special form, it does not evaluate its second member, and evaluates its third member in a different fashion than what would be expected if it was not a special form. That is, a and b as subforms of its third form have a different binding. let in this case is a syntactic keyword that signals the special form. Note that it's quite possible that special forms still evaluate all of their arguments, they are still not procedure calls then, because their head is syntax, and procedures can be passed to other functions as arguments, syntax cannot, thus: (func arg1 #'let) Is an error, likewise: (funcall let ((a 1) (b 2)) (+ a b)) Is an error, showing that it's different to a procedure call. one preceding semi-colon for in-line comments, inside code blocks
special forms list, other than a macro form, which is a form with special syntax or special evaluation rules or both, possibly manipulating the evaluation environment or control flow or both. The first element of a special form is a special operator.
special operators one of a fixed set of symbols that may appear in the car of a form in order to identify the form as a special form. block let* return-from catch load-time-value setq eval-when locally symbol-macrolet flet macrolet tagbody function multiple-value-call the go multiple-value-prog1 throw if progn unwind-protect labels progv let quote
special variable n. Trad. a dynamic variable. dynamic variable n. a variable the binding for which is in the dynamic environment
lists proper list is either nil or ends in a cons whose cdr is nil dotted list ends in something that is not of type NULL circular list has cycles association list propery list
5. Character Syntax
; One line comment :symbol Keyword. Symbol evaluates to itself (foo …) List "" String ` Unevaluate , evaluate ' Unevaluate n/d ratio m.n Float read-eval If NIL, a reader-error is signaled at #. #| |# Multi line comment #\c Character #B Binary integer #O Octal #X Hexa #rRn r 2 <= r <= 36 #C(a,b) (complex a b) #' (function foo) #nAsequence N-Dimensional array #[n](foo*) Vector of some (or n) foos filled with last foo if necessary #[n]*b* Bit vector of some (or n) bs filled with last b if necessary #S(type {slot value}*) Structure of type #Pstring Pathname #:foo Uninterned symbol foo #.form Read time value of form #integer=foo Give foo the label integer #integer# Object labelled integer #< Have the reader signal reader-error #+feature when-feature #-feature unless-feature feature is a symbol from features
| c* | ;\c Treat arbitrary characters c as alphabetic preserving case |
6. Scope
* Code taken form Let Over lambda as an example of lexical scope * #include <stdio.h>
int global=0;
void dosomething() { printf("global: %d\n", global); }
void whatever() { int global=1; dosomething(); }
int main() { whatever(); }
;; Code taken from On Lisp by Paul Graham ; Here x is bound an y is free (let ((y 7)) (defun scope-test (x) (list x y))) ; In a dynamic scoped lisp to find the value of a free variable ; when evaluating scope-test we look back through the chain of ; functions that called it. When we find an environment where y ; was bound, that binding will be the one used in the evaluation (let ((y 5)) (scope-test 3)) (3 5) ; In a lexically (static) scope lisp instead of looking back ; through the chain of calling functions, we look back through ; the containing environments at the time the function was defined. (let ((y 5)) (scope-test 3)) (3 7) ; In Common Lisp the default scope is static, though you can ; declare a variable special in which case it is dynamically ; scoped
7. Recursion
Iteration vs Recursion
Iteration: (def + (x y) (if (= x 0) y (+ (-1+ x) (1+ y)))) Time = O(x) Space = O(1)
Linear Recursion: (def x (x y) (if (= x 0) y (1+ (+ (-1+ x) y)))) Time = O(x) Space = O(x)
Recursion types: Linear Mutual
; Linear (defun factorial1 (n) (if (/= n 1) (* n (factorial1 (1- n))) 1))
; Tail recursion (defun factorial2a (n) (labels ((f (n acc) (if (/= n 1) (f (1- n) (* n acc)) acc))) (f n 1)))
(defun factorial2b (n &optional (res 1)) (if (/= n 1) (factorial3 (1- n) (* n res)) res))
8. ASDF
8.1. To begin working with ASDF, you need:
(require "asdf")
8.2. To print current ASDF version:
(or #+asdf2 (asdf:asdf-version) #+asdf :old)
8.3. Put all of your systems in one of the standard locations, subdirectories of
~/common-lisp/ or ~/.local/share/common-lisp/source/. Symlinks are allowed
8.4. If you are installing software in a non standard location,
you have to tell ASDF where the software is:
8.4.1. The simplest way to add a path (say home/user.asd-link-farm) to
your search path is to create the directory ~/.config/common-lisp/source-registry.conf.d/ and there, create a file with any name of your choice, with type 'conf', for instance: 42-asd-link-farm.conf, containing the line: (:directory "home/luser.asd-link-farm/")
8.4.2. If you want all directories under home/luser/lisp to be
recursively scanned for .asd files, add the line: (:tree "home/luser/lisp")
8.5. To load a system:
(asdf:load-system :foo) (require :foo)
8.6. You can reset the source-registry configuration with:
(asdf:clear-source-registry)
8.7. Before dumping your Lisp image, you should:
(asdf:clear-configuration)
8.8. Where object files are stored?
The simplest way to add a translation, say from foo/bar/baz/quuz to where/i/want/my/fasls is to create the directory ~/.config/common-lisp/asdf-output-translations.conf.d/ and there create a file with any name of your choice, with type 'conf', for instance: 42-bazquux.conf containing the line: ("foo/bar/baz/quuz" "where/i/want/my/fasls") To disable output tranlations for source under a given directory say toto/tata you can create a file 40-disable-toto.conf with the line: ("toto/tata") To wholy disable output tranlations for all directories, you can create a file 00-disable.conf with the line: (t t) In abscense of any configuration the default is to redirect everything under implementation dependent directory of ~.cache/common-lisp/ You can reset with (asdf:clear-output-translations)
8.9. The following snippet, clear the ASDF configuration automatically
as you dump an image: #+(or cmu sbcl scl) (pushnew 'clear-configuration #+(or cmu scl) ext:*before-save-initializations* #+sbcl sb-ext:save-hooks)
8.10. Other operations:
Output of operation are sent to standard-output
8.10.1. clear-system clears the entry for a system in the database of systems
previously loaded. Note that this does NOT in any way cause the code of the system to be unloaded.
8.10.2. compile-system
8.10.3. find-system
8.10.4. load-system applies operate with the operation from load-system-operation
which is by default load-op, the system and any provided key arguments.
8.10.5. loaded-systems return a list of the names of loaded systems
8.10.6. operate generic function usually abbreviated as oos
'asdf:load-op :package :force (t|nil)
8.10.7. require-system same as load-system but skips to update systems that are
already loaded. Calls load-system with keyword argument :force-not (loaded-systems)
8.10.8. test-system
8.11. find asdf version
(when (find-package :asdf) (let ((ver (symbol-value (or (find-symbol (string :*asdf-version*) :asdf) (find-symbol (string :*asdf-revision*) :asdf))))) (etypecase ver (string ver) (cons (with-output-to-string (s) (loop for (n . m) on ver do (print n s) (when m (princ ". " s))))) (null "1.0"))))
9. Quicklisp
9.1. Look up for system: (ql:system-apropos "vecto")
9.2. Install system: (ql:quickload "vecto")
9.3. Uninstall system: (ql:uninstall "vecto")
9.4. Add config to init file: (ql:add-to-init-file)
9.5. Update systems: (progn (ql:update-dist "quicklisp") (ql:update-client))
10. Interesting packages
(ql:quicklisp :computable-reals) (setq cr:*print-prec* 50) (cr:sqrt-r 2) Database: Postmodern Routing and middleware: Easy-routese JSON: ST-JSON Templates: Djula Testing: fiveAM Logging: Verbose Password hashing: cl-passed CLI parameters: unix-opts
11. Exercises
;; Define (has-number-p s-exp) to return true if the s-expression ;; is or contains a number. (defun has-number-p (sexp) (if (and (atom sexp) (numberp sexp)) t (if (atom sexp) nil (some #'has-number-p sexp))))
(has-number-p '(a (b (c d) ((3)))))
;; Define the macro key-if to have the form ;; (KEY-IF test ;; :THEN exp1 exp2 … ;; :ELSE exp3 exp4 …) (defun a(&key (par 0)) (princ par))
(defmacro key-if (test &optional &key &rest then &key &rest else) `(cond (,test (and ,then (progn ,then))) (t (and ,else (progn ,else)))))
;; > (key-if (> 3 1) :then 'ok) ;; OK ;; > (key-if (< 5 3) :else 'ok) ;; OK ;; > (key-if (> 3 1) :else 'oops) ;; NIL ;; > (key-if (> 3 1) :then) ;; NIL ;; > (key-if (> 3 1) :else 'oops :then 'ok) ;; OK ;; > (key-if (> 3 1) :else 'oops :then (print 'hi) 'ok) ;; HI ;; OK
(defun make-balance (initial-balance) (let ((balance initial-balance)) (labels ((f (&optional n) (if (null n) balance (setq balance (+ balance n))))) f)))
;; Define function SUBSTOP same as SUBST but only at first level ;; (SUBSTOP 5 'A '(A (A B) A)) —> (5 (A B) 5)
(defun substop (newitem item seq &optional (test #'eql)) (or (and seq (cons (or (and (funcall test item (car seq)) newitem) (car seq)) (substop newitem item (cdr seq)))) ()))
;; Define function REV like REVERSE but reversing al levels ;; (REV '(A (B C) (D (E)))) —> (((E) D) (C B) A)
(defun rev (seq &optional (acc ())) (let ((head (car seq))) (cond ((null seq) acc) ((atom head) (rev (cdr seq) (append (list head) acc))) (t (rev (cdr seq) (append (list (rev head)) acc))))))
;; Define a function PRIMN which evaluates to the first n values of a sequence ;; (PRIMN 2 '(A B C)) —> (A B)
(defun primn (n l &optional (acc ())) (or (and (= (length acc) n) acc) (primn n (cdr l) (append acc (list (car l))))))
;; Define a function ULTN which evaluates to the n last elements of a list ;; (ULTN 2 '(A B C)) —> (B C)
(defun ultn (n l &optional (acc nil)) (cond ((null l) acc) ((<= (length l) n) (ultn n (cdr l) (append acc (list (car l))))) (t (ultn n (cdr l) acc))))
;; Define a function QUITA which evaluates to a list without item at pos n ;; (QUITA 2 '(A B C)) —> (A C)
(defun quita (n seq &optional (acc ())) (cond ((null seq) acc) ((= n (1+ (length acc))) (quita 0 (cdr seq) acc)) (t (quita n (cdr seq) (append acc (list (car seq)))))))
;; Define a function ROTAR-DER which evaluates to a list with last element ;; in first place ;; (ROTAR-DER '(A B C)) —> (C A B)
(defun rotar-der (seq &optional (acc ())) (or (and (= (length seq) 1) (cons (car seq) acc)) (rotar-der (cdr seq) (append acc (list (car seq))))))
;; Define a function PASA-1-A-N which evaluates to a list with the first ;; element placed at position N ;; (PASA-1-A-N 3 '(A B C D)) —> (B C A D)
(defun pasa-1-a-n (n seq &optional (acc ()) (first nil) (inc nil)) (cond ((null seq) acc) ((null inc) (pasa-1-a-n n (cdr seq) acc (car seq) t)) ((= n (1+ (length acc))) (pasa-1-a-n n (cdr seq) (append acc (list first) (list (car seq))) first t)) (t (pasa-1-a-n n (cdr seq) (append acc (list (car seq))) first t))))
;; Define a function LINEALIZA which removes all parens of a list excluding () ;; (LINEALIZA '(A (B (C)) () ĕ)) —> (A B C NIL E)
(defun linealiza (seq &optional (acc ())) (let ((head (car seq))) (cond ((null seq) acc) ((atom (car seq)) (linealiza (cdr seq) (append acc (list (car seq))))) (t (linealiza (cdr seq) (append acc (linealiza head)))))))
;; Define a function CUENTA-ATOMOS which evaluates to the number of atoms of ;; a list ;; (CUENTA-ATOMOS '(A (B (C)) () E) —> 5
(defun cuenta-atomos (seq) (labels ((f (x) (or (and (atom x) 1) (cuenta-atomos x)))) (apply #'+ (linealiza (mapcar #'f seq)))))
;; Define a function MISMA-FORMA which evaluates to T if two expressions ;; have the same estructure ;; (MISMA-FORMA '(A (B C)) '(1 (2 3))) —> T
(defun misma-forma (e1 e2) (cond ((and (atom e1) (atom e2)) t) ((and (listp e1) (listp e2) (= (length e1) (length e2))) (and (misma-forma (car e1) (car e2)) (misma-forma (cdr e1) (cdr e2)))) (t nil)))
;; Define a function MEM same as MEMBER but checks all levels ;; (MEM 'A '((A B) C)) —> T
(defun mem (item seq) (cond ((null seq) nil) ((atom (car seq)) (or (eql item (car seq)) (mem item (cdr seq)))) (t (or (mem item (car seq)) (mem item (cdr seq))))))
;; Define a function SEPARA wich splits numbers from letters ;; (SEPARA '(A (1 2) ((B)) (C (3)))) —> ((A B C) (1 2 3))
(defun separa (seq &optional (sym ()) (num ())) (cond ((null seq) (cons sym (list num))) )
;; Define a function DOBLA-EL which doubles all atoms in a list in the ;; level the atom is found ;; (DOBLA-EL '(A B)) —> (A A B B) ;; (DOBLA-EL '((A) B) —> ((A) (A) B B)
;; Define a function AGRUPA which groups the contiguous elements of two lists ;; (AGRUPA '(A B C) '(1 2 3)) —> ((A 1) (B 2) (C 3)) ;; (AGRUPA '(A B) '(1 2 3)) —> ((A 1) (B 2) 3) ;; (AGRUPA '(A B C) '(1 2)) —> ((A 1) (B 2) C)
;; SETS: We represent sets here as lists with no duplicated elements. For ;; instance, (A B C) is a set, but (A B A C) is not. Besides, the order ;; of the elements does not matter so (A B C) and (A C B) represent the ;; same set.
;; Define a function REDUCE-CONJUNTO which takes a list and remove all ;; duplicated elements. That is, convert the list to a set ;; (REDUCE-CONJUNTO '(A B A C)) —> (B A C)
;; Define a function UNION which evaluates to the union of two sets ;; (UNION '(0 3 6 9 12) '(0 4 8 12)) —> (3 6 9 0 4 8 12)
;; Define a function INTERSECCION which evaluates to the intersection of ;; two sets ;; (INTERSECCION '(0 3 6 9 12) '(0 4 8 12)) —> (0 12)
;; Define a function DIF which evaluates to the difference of two sets, ;; that is, the elements of the first set that are not elements of the ;; second set ;; (DIF '(0 3 6 9 12) '(0 4 8 12)) —> (3 6 9) ;; Define a function DIF-SIM which evaluates to the symmetric difference ;; of two sets, that is, the elements that only are in one of the sets ;; (DIF-SIM '(0 3 6 9 12) '(0 4 8 12)) —> (3 6 9 4 8)
;; Define IGUAL-CONJ that evaluates to T if both sets contains the same ;; elements and NIL if not ;; (IGUAL-CONJ '(A B C) '(C A B)) —> T
;; Matrices
;; Define the determinant of a square matrix developing its first row ;; Define the adjugate of an element of the first row using the definition ;; of determinant. Use mutual recursion
;; Combinatorics
;; Define the following functions: ;; (LINEA N) –> The nth row of the Pascal's triangle ;; (COMBINACIONES N M) –> Combination number N, M ;; (INSERTA E L) that inserts the E element in L in all possible ways: ;; (INSERTA 'A '(B C)) –> ((A B C) (B A C) (B C A)) ;; (PERMUTACIONES L) that returns a list of all possible permutations of ;; the list L
;; P-Lists
;; Bibliographic database. Assume we have a list: ;; LIBROS = (LIBRO-1 LIBRO-2 …) ;; being LIBRO-I a P-list with the form: ;; (SETF (SYMBOĿ-PLIST 'LIBRO-1) ;; (AUTOR "Farreny" TITULO "Programmer en LISP" EDITORIAL "Masson")) ;; Define the function: ;; (ADD-LIBRO REFERENCIA AUTOR TITULO EDITORIAL) –> REFERENCIA ;; which adds the book to the database. ;; Define the function (BUSCAR-POR PROPIEDAD VALOR) which searches in the ;; database and returns the list of the references of the books that verify ;; the conditions. For instance: ;; (BUSCAR-POR 'AUTOR "FARRENY") —> (LIBRO1 …)
;; Data driven programming ;; Define the function (CALCULAR OP1 OPR OP2) ;; in a way that OP1 and OP2 can be real numbers y the usual format or ;; complex numbers in the format (a b). OPR can be 'MAS' 'MENOS' 'POR' ;; or 'DIV'. The function must return the correct result for the operation. ;; For instance: ;; (CALCULAR 2 'MAS' 3) –> 5 ;; (CALCULAR '(1 2) 'MAS' '(3 4) –> (-5 10)
;; Nets ;; Suppose we define a road net described by: ;; (SETF (SYMBOL-PLIST 'RED) ;; '(H ((SE . 90)) CA ((SE . 100)) ;; CO ((SE . 130)) J ((GR . 150)) AL ((MA . 200)) ;; MA ((AL . 200) (GR . 150) (SE . 200)) ;; SE ((H . 90) (CO . 130) (GR . 220) (MA . 200) (CA . 100)) ;; GR ((SE . 220) (J . 150) (MA . 150)))) ;; Define the following functions: ;; (MODIFICAR C1 C2 D) that updates the distance D between cities C1 and C2 ;; (SUPRIMIR C1 C2) that removes the road that connects C1 and C2 ;; (ANADIR C1 C2 D) that adds the road to the net ;; (DISTANCIA C1 C2) that evaluates to the distance between C1 and C2 if they are ;; directly connected or gives us a message indicating there is no direct connection
;; Define functions SET-UNION and SET-INTERSECTION that performs the ;; union and intersection between a list of (at least) two sets expressed ;; as lists
(defun set-union (s1 s2 &rest sl) (labels ((my-remove-duplicates (l &optional (acc nil)) (cond ((null l) acc) ((not (member (car l) acc)) (my-remove-duplicates (cdr l) (append acc (list (car l))))) (t (my-remove-duplicates (cdr l) acc))))) (my-remove-duplicates (append s1 s2 (apply #'append sl)))))
(defun set-intersection (s1 s2 &rest sl) (labels ((my-member (e l) (and (mapcar (lambda (e x) (member e x)) l)))) (
(defun seti (l1 l2 &optional (acc nil)) (cond ((null l1) acc) (t (seti (cdr l1) l2 (append acc (list (list (car l1) l2)))))))
(defun flatten (l) (let ((a (car l)) (b (cdr l))) (cond ((null a) ()) ((atom a) (append (list a) (flatten b))) (t (append (flatten a) (flatten b))))))
(flatten '(a b (1 (8 9) 2) (1 2 (7 8) 3 )))
12. Quines
;Language: LISP (or Scheme)
;Author: Unknown ;Notes: There are several silly examples like this.
T
;Author: Steven M. Haflich ;Note common LISP only
#1=(WRITE '#1# :CIRCLE T)
;Author: Unknown ;Note: only works if print-circle is defined
#1='#1#
;Author: Peter Norvig
#1=(setq print-circle '#1#)
;Author: Peter Norvig ;Note: common LISP, self evaluating
#1=((lambda () (setq print-circle '#1#)))
;Author: Chris Hruska
((LAMBDA (X) (LIST X (LIST 'QUOTE X))) '(LAMBDA (X) (LIST X (LIST 'QUOTE X))))
;Author: Dave Seaman (ags@seaman.cc.purdue.edu)
(let ((p "(let ((p ~s)) (format t p p))")) (format t p p))
;Author: Sam Steingold
(let ((a '(list 'let (list (list 'a (list 'quote a))) a))) (list 'let (list (list 'a (list 'quote a))) a))
;Author: Sam Steingold
(let ((a '(list 'let (list (list 'a (list 'quote a))) a))) `(let ((a (quote ,a))) ,a))
;Author: Unknown
((lambda (x) (list x x)) (lambda (x) (list x x)))
;Author: Joe Miller ;Notes: In Common Lisp this should actually evaluate to the above list. In some dialects, however, it evaluates to itself.
((LAMBDA (X) `(,X ',X)) '(LAMBDA (X) `(,X ',X)))
;Author: Peter Norvig
((lambda (x) (list `',x)) '(lambda (x) (list x `',x)))
;Author: Unknown ;Note: common LISP
((lambda (list) (list list `',list))
'(lambda (list) (list list `',list)))
;Author: John McCarthy and Carolyn Talcott
((lambda (x) (list x (list (quote quote) x))) (quote (lambda (x) (list x (list (quote quote) x)))))
;Author: John Burger, David Brill, Filip Machi
(PRINTME (LAMBDA NIL (PROG (A B) (SETQ A (QUOTE (PRINTME (LAMBDA NIL (PROG (A B) (SETQA (QUOTE FOO)) (SETQ B (COPY A)) (RPLACA (CDADDR (CADDAR (CDDADR B)))A) (SETQ B (COPY A)) (RPLACA (CDADDR (CADDAR (CDDADR B))) A) (RETURN B))))
;Author: Louise Hay ;Note: Result of her quine-generating program
((LAMBDA NIL ((LAMBDA (Y) (LIST (LIST (QUOTE LAMBDA) NIL (LIST Y (LIST (QUOTE QUOTE) Y))))) (QUOTE (LAMBDA (Y) (LIST (LIST (QUOTE LAMBDA) NIL (LIST Y (LIST (QUOTE QUOTE) Y)))))))))
;Author: Pekka P. Pirinen
;Notes: This is a self-printing expression in the format sublanguage. ;It works by using the ~:* directive to back up in the argument list ;and reuse the previous argument; this is how it manages to use the ;same string to format the new expression and print a copy of itself ;inside the new expression. Some CLs have a bug in the ~@? ;recursive format directive that prevents backing up beyond the ;control string argument, but the standard implies it ought to work. ;Tested in LispWorks 4.2 on Unix.
(format t "~@?" "(format t \"~~@?\" ~:*~S)")
;Authors: Paul Bratley and Jean Millo
define(( (c (prog (a) (print (quote define)) (print (list(list(list(quote c) (get(quote c) (quote expr)))))) (print (quote c)) (print (list a)) (print (quote stop)) (print (quote fin)))))) c(nil) stop fin
;Author: Olin.Shivers@cosmos.vlsi.cs.cmu.edu
((lambda (lambda) `(,lambda ',lambda)) '(lambda (lambda) `(,lambda ',lambda)))
13. Code
; This code appears at the end of Let Over Lambda by Doug Hoyte (defmacro! sortf (comparator &rest places) (if places `(tagbody ,@(mapcar #`(let ((,g!a #1=,(nth (car a1) places)) (,g!b #2=,(nth (cadr a1) places))) (if (,comparator ,g!b ,g!a) (setf #1# ,g!b #2# ,g!a))) (build-batcher-sp (length places))))))
14. Papers
14.1. McCarthy's 1960 paper
; The Lisp defined in McCarthy's 1960 paper, translated into CL. ; Assumes only quote, atom, eq, cond, cons, car, cdr ; Bug reports to lispcode@paulgraham.com.
(defun null. (x) (eq x '()))
(defun and. (x y) (cond (x (cond (y 't) ('t '()))) ('t '())))
(defun not. (x) (cond (x '()) ('t 't)))
(defun append. (x y) (cond ((null. x) y) ('t (cons (car x) (append. (cdr x) y)))))
(defun list. (x y) (cons x (cons y '())))
(defun pair. (x y) (cond ((and. (null. x) (null. y)) '()) ((and. (not. (atom x)) (not. (atom y))) (cons (list. (car x) (car y)) (pair. (cdr x) (cdr y))))))
(defun assoc. (x y) (cond ((eq (caar y) x) (cadar y)) ('t (assoc. x (cdr y)))))
(defun eval. (e a) (cond ((atom e) (assoc. e a)) ((atom (car e)) (cond ((eq (car e) 'quote) (cadr e)) ((eq (car e) 'atom) (atom (eval. (cadr e) a))) ((eq (car e) 'eq) (eq (eval. (cadr e) a) (eval. (caddr e) a))) ((eq (car e) 'car) (car (eval. (cadr e) a))) ((eq (car e) 'cdr) (cdr (eval. (cadr e) a))) ((eq (car e) 'cons) (cons (eval. (cadr e) a) (eval. (caddr e) a))) ((eq (car e) 'cond) (evcon. (cdr e) a)) ('t (eval. (cons (assoc. (car e) a) (cdr e)) a)))) ((eq (caar e) 'label) (eval. (cons (caddar e) (cdr e)) (cons (list. (cadar e) (car e)) a))) ((eq (caar e) 'lambda) (eval. (caddar e) (append. (pair. (cadar e) (evlis. (cdr e) a)) a)))))
(defun evcon. (c a) (cond ((eval. (caar c) a) (eval. (cadar c) a)) ('t (evcon. (cdr c) a))))
(defun evlis. (m a) (cond ((null. m) '()) ('t (cons (eval. (car m) a) (evlis. (cdr m) a)))))
14.2. Roots of LISP
The Roots of Lisp Paul Graham
Draft, January 18, 2002.
In 1960, John McCarthy published a remarkable paper in which he did for something like what Euclid did for geometry. (Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Communications of the ACM 3:4, April 1960, pp. 184-195). He showed how, given a handful of simple operators and a notation for functions, you can build a whole programming language. He called this language Lisp, for "List Processing," because one of his key ideas was to use a simple data structure called a list for both code and data. It's worth understanding what McCarthy discovered, not just as a landmark in the history of computers, but as a model for what programming is tending to become in our own time. It seems to me that there have been two really clean, consistent models of programming so far: the C model and the Lisp model. These two seem points of high ground, with swampy lowlands between them. As computers have grown more powerful, the new languages being developed have been moving steadily toward the Lisp model. A popular recipe for new programming languages in the past 20 years has been to take the C model of computing and add to it, piecemeal, parts taken from the Lisp model, like runtime typing and garbage collection. In this article I'm going to try to explain in the simplest possible terms what McCarthy discovered. The point is not just to learn about an interesting theoretical result someone gured out forty years ago, but to show where languages are heading. The unusual thing about Lisp - in fact, the defining quality of Lisp - is that it can be written in itself. To understand what McCarthy meant by this, we're going to retrace his steps, with his mathematical notation translated into running Common Lisp code.
1 Seven Primitive Operators To start with, we define an expression. An expression is either an atom, which is a sequence of letters (e.g. foo), or a list of zero or more expressions, separated by whitespace and enclosed by parentheses. Here are some expressions:
foo () (foo) (foo bar) (a b (c) d)
The last expression is a list of four elements, the third of which is itself a list of one element.
In arithmetic the expression 1 + 1 has the value 2. Valid Lisp expressions also have values. If an expression e yields a value v we say that returns v. Our next step is to define what kinds of expressions there can be, and what value each kind returns. If an expression is a list, we call the first element the operator and the remaining elements the arguments. We are going to define seven primitive (in the sense of axioms) operators: quote, atom, eq, car, cdr, cons, and cond.
1.1. (quote x) returns x. For readability we will abbreviate (quote x) as 'x.
> (quote a) a > 'a a > (quote (a b c)) (a b c)
1.2. (atom x) returns the atom t if the value of x is an atom or the empty list. Otherwise it returns (). In Lisp we conventionally use the atom t to represent truth, and the empty list to represent falsity.
> (atom 'a) t > (atom '(a b c)) () > (atom '()) t
Now that we have an operator whose argument is evaluated we can show what quote is for. By quoting a list we protect it from evaluation. An unquoted list given as an argument to an operator like atom is treated as code:
> (atom (atom 'a)) t
whereas a quoted list is treated as mere list, in this case a list of two elements:
> (atom '(atom 'a)) ()
This corresponds to the way we use quotes in English. Cambridge is a town in Massachusetts that contains about 90,000 people. "Cambridge" is a word that contains nine letters.
Quote may seem a bit of a foreign concept, because few other languages have anything like it. It's closely tied to one of the most distinctive features of Lisp: code and data are made out of the same data structures, and the quote operator is the way we distinguish between them.
1.3. (eq x y) returns t if the values of x and y are the same atom or both the empty list, and () otherwise.
> (eq 'a 'a) t > (eq 'a 'b) () > (eq '() '()) t
1.4. (car x) expects the value of x to be a list, and returns its first element.
> (car '(a b c)) a
1.5. (cdr x) expects the value of x to be a list, and returns everything after the first element.
> (cdr '(a b c)) (b c)
1.6. (cons x y) expects the value of y to be a list, and returns a list containing the value of x followed by the elements of the value of y.
> (cons 'a '(b c)) (a b c) > (cons 'a (cons 'b (cons 'c '()))) (a b c) > (car (cons 'a '(b c))) a > (cdr (cons 'a '(b c))) (b c)
1.7. (cond (p1 e1) … (pn en)) is evaluated as follows. The p expressions are evaluated in order until one returns t. When one is found, the value of the corresponding e expression is returned as the value of the whole cond expression.
> (cond ((eq 'a 'b) 'first) ((atom 'a) 'second)) second
In five of our seven primitive operators, the arguments are always evaluated when an expression beginning with that operator is evaluated. Expressions beginning with the other two operators, quote and cond, are evaluated differently. When a quote expression is evaluated, its argument is not evaluated, but is simply returned as the value of the whole quote expression. And in a valid cond expression, only an L-shaped path of subexpressions will be evaluated. We will call an operator of that type a function.
2 Denoting Functions Next we define a notation for describing functions. A function is expressed as (lambda (p1 .. pn) e), where p1 … pn are atoms (called parameters) and e is an expression. An expression whose first element is such an expression
((lambda (p1 … pn) e) a1 … an)
is called a function call and its value is computed as follows. Each expression is evaluated. Then e is evaluated. During the evaluation of e , the value of any occurrence of one of the pi is the value of the corresponding ai in the most recent function call.
> ((lambda (x) (cons x '(b))) 'a) (a b) > ((lambda (x y) (cons x (cdr y))) 'z '(a b c)) (z b c)
If an expression has as its first element an atom f that is not one of the primitive operators
(f a1 .. an)
and the value of f is a function (lambda (p1 .. pn) e) then the value of the expression is the value of
((lambda (p1 … pn) e) a1 .. an)
In other words, parameters can be used as operators in expressions as well as arguments:
> ((lambda (f) (f '(b c))) '(lambda (x) (cons 'a x))) (a b c)
There is another notation for functions that enables the function to refer to itself, thereby giving us a convenient way to define recursive functions. Logically we don't need to define a new notation for this. We could define recursive functions in our existing notation using a function on functions called the Y combinator. It may be that McCarthy did not know about the Y combinator when he wrote his paper in any case, label notation is more readable.
The notation
(label f (lambda (p1 … pn) e))
denotes a function that behaves like (lambda (p1 … pn) e), with the additional property that an occurrence of f within e will evaluate to the label expression, as if were a parameter of the function. Suppose we want to define a function (subst x y z), which takes an expression x, an atom y, and a list z, and returns a list like z but with each instance of y (at any depth of nesting) in z replaced by x.
> (subst 'm 'b '(a b (a b c) d)) (a m (a m c) d)
We can denote this function as (label subst (lambda (x y z) (cond ((atom z) (cond ((eq z y) x) ('t z))) ('t (cons (subst x y (car z)) (subst x y (cdr z)))))))
We will abbreviate f = (label f (lambda (p1 … pn) e)) as
(defun f (p1 … pn) e)
so
(defun subst (x y z) (cond ((atom z) (cond ((eq z y) x) ('t z))) ('t (cons (subst x y (car z)) (subst x y (cdr z))))))
Incidentally, we see here how to get a default clause in a cond expression. A clause whose first element is 't will always succeed. So
(cond (x y) ('t z))
is equivalent to what we might write in a language with syntax as
if x then y else z
3 Some Functions Now that we have a way of expressing functions, we define some new ones in terms of our seven primitive operators. First it will be convenient to introduce some abbreviations for common patterns. We will use cxr, where x is a sequence of as or ds, as an abbreviation for the corresponding composition of car and cdr. So for example (cadr e) is an abbreviation for (car (cdr e)), which returns the second element of e.
> (cadr '((a b) (c d) e)) (c d) > (caddr '((a b) (c d) e)) e > (cdar '((a b) (c d) e)) (b)
Also, we will use (list e1 … en) for (cons e1 … (cons en '()) … ).
> (cons 'a (cons 'b (cons 'c '()))) (a b c) > (list 'a 'b 'c) (a b c)
Now we define some new functions. I've changed the names of these functions by adding periods at the end. This distinguishes primitive functions from those defined in terms of them, and also avoids clashes with existing Common Lisp functions.
3.1. (null. x) tests whether its argument is the empty list.
(defun null. (x) (eq x '()))
> (null. 'a) () > (null. '()) t
3.2. (and. x y) returns t if both its arguments do and () otherwise.
(defun and. (x y) (cond (x (cond (y 't) ('t '()))) ('t '())))
> (and. (atom 'a) (eq 'a 'a)) t > (and. (atom 'a) (eq 'a 'b)) ()
3.3. (not. x) returns t if its argument returns (), and () if its argument returns t.
(defun not. (x) (cond (x '()) ('t 't)))
> (not (eq 'a 'a)) () > (not (eq 'a 'b)) t
3.4. (append. x y) takes two lists and returns their concatenation.
(defun append. (x y) (cond ((null. x) y) ('t (cons (car x) (append. (cdr x) y)))))
> (append. '(a b) '(c d)) (a b c d) > (append. '() '(c d)) (c d)
3.5. (pair. x y) takes two lists of the same length and returns a list of two element lists containing successive pairs of an element from each.
(defun pair. (x y) (cond ((and. (null. x) (null. y)) '()) ((and. (not. (atom x)) (not. (atom y))) (cons (list (car x) (car y)) (pair. (cdr x) (cdr y))))))
> (pair. '(x y z) '(a b c)) ((x a) (y b) (z c))
3.6. (assoc. x y) takes an atom and a list of the form created by pair., and returns the second element of the first list in whose first element is x.
(defun assoc. (x y) (cond ((eq (caar y) x) (cadar y)) ('t (assoc. x (cdr y)))))
> (assoc. 'x '((x a) (y b))) a > (assoc. 'x '((x new) (x a) (y b))) new
4 The Surprise So we can define functions that concatenate lists, substitute one expression for another, etc. An elegant notation, perhaps, but so what? Now comes the surprise. We can also, it turns out, write a function that acts as an interpreter for our language: a function that takes as an argument any Lisp expression, and returns its value. Here it is:
(defun eval. (e a) (cond ((atom e) (assoc. e a)) ((atom (car e)) (cond ((eq (car e) 'quote) (cadr e)) ((eq (car e) 'atom) (atom (eval. (cadr e) a))) ((eq (car e) 'eq) (eq (eval. (cadr e) a) (eval. (caddr e) a))) ((eq (car e) 'car) (car (eval. (cadr e) a))) ((eq (car e) 'cdr) (cdr (eval. (cadr e) a))) ((eq (car e) 'cons) (cons (eval. (cadr e) a) (eval. (caddr e) a))) ((eq (car e) 'cond) (evcon. (cdr e) a)) ('t (eval. (cons (assoc. (car e) a) (cdr e)) a)))) ((eq (caar e) 'label) (eval. (cons (caddar e) (cdr e)) (cons (list (cadar e) (car e)) a))) ((eq (caar e) 'lambda) (eval. (caddar e) (append. (pair. (cadar e) (evlis. (cdr e) a)) a)))))
(defun evcon. (c a) (cond ((eval. (caar c) a) (eval. (cadar c) a)) ('t (evcon. (cdr c) a))))
(defun evlis. (m a) (cond ((null. m) '()) ('t (cons (eval. (car m) a) (evlis. (cdr m) a)))))
The definition of eval. is longer than any of the others we've seen before. Let's consider how each part works. The function takes two arguments: e, the expression to be evaluated, and a, a list representing the values that atoms have been given by appearing as parameters in function calls. This list is called the environment, and it is of the form created by pair.. It was in order to build and search these lists that we wrote pair. and assoc.. The spine of eval. is a cond expression with four clauses. How we evaluate an expression depends on what kind it is. The first clause handles atoms. If e is an atom, we look up its value in the environment:
> (eval. 'x '((x a) (y b))) a
The second clause of eval. is another cond for handling expressions of the form (a …), where a is an atom. These include all the uses of the primitive operators, and there is a clause for each one.
> (eval. '(eq 'a 'a) '()) t > (eval. '(cons x '(b c)) '((x a) (y b))) (a b c)
All of these (except quote) call eval. to find the value of the arguments. The last two clauses are more complicated. To evaluate a cond expression we call a subsidiary function called evcon., which works its way through the clauses recursively, looking for one in which the first element returns t. When it finds such a clause it returns the value of the second element.
> (eval. '(cond ((atom x) 'atom) ('t 'list)) '((x '(a b)))) list
The final part of the second clause of eval. handles calls to functions that have been passed as parameters. It works by replacing the atom with its value (which ought to be a lambda or label expression) and evaluating the resulting expression. So
(eval. '(f '(b c)) '((f (lambda (x) (cons 'a x)))))
turns into
(eval. '((lambda (x) (cons 'a x)) '(b c)) '((f (lambda (x) (cons 'a x)))))
which returns (a b c).
The last two clauses in eval. handle function calls in which the first element is an actual lambda or label expression. A label expression is evaluated by pushing a list of the function name and the function itself onto the environment, and then calling eval. on an expression with the inner lambda expression substituted for the label expression. That is,
(eval. '((label firstatom (lambda (x) (cond ((atom x) x) ('t (firstatom (car x)))))) y) '((y ((a b) (c d)))))
becomes
(eval. '((lambda (x) (cond ((atom x) x) ('t (firstatom (car x))))) y) '((firstatom (label firstatom (lambda (x) (cond ((atom x) x) ('t (firstatom (car x))))))) (y ((a b) (c d)))))
which eventually returns a. Finally, an expression of the form ((lambda (p1 … pn) e) a1 … an) is evaluated by first calling evlis. to get a list of values (v1 … vn) of the arguments a1 … an, and then evaluating e with (p1 v1) … (pn vn) appended to the front of the environment. So
(eval. '((lambda (x y) (cons x (cdr y))) 'a '(b c d)) '())
becomes
(eval. '(cons x (cdr y)) '((x a) (y (b c d))))
which eventually returns (a c d).
5 Aftermath Now that we understand how eval works, let's step back and consider what it means. What we have here is a remarkably elegant model of computation. Using just quote, atom, eq, car, cdr, cons, and cond, we can define a function, eval., that actually implements our language, and then using that we can define any additional function we want. There were already models of computation, of course|most notably the Turing Machine. But Turing Machine programs are not very edifying to read. If you want a language for describing algorithms, you might want something more abstract, and that was one of McCarthy's aims in defining Lisp.
The language he defined in 1960 was missing a lot. It has no side-effects, no sequential execution (which is useful only with side effects anyway), no practical numbers (It is possible to do arithmetic in McCarthy's 1960 Lisp by using e.g. a list of n atoms to represent the number n) and dynamic scope. But these limitations can be remedied with surprisingly little additional code. Steele and Sussman show how to do it in a famous paper called "The Art of the Interpreter." (Guy Lewis Steele, Jr. and Gerald Jay Sussman, The Art of the Interpreter, or the Modularity Complex (Parts Zero, One, and Two), MIT AI Lab Memo 453, May 1978.) If you understand McCarthy's eval, you understand more than just a stage in the history of languages. These ideas are still the semantic core of Lisp today. So studying McCarthy's original paper shows us, in a sense, what Lisp really is. It's not something that McCarthy designed so much as something he discovered. It's not intrinsically a language for AI or for rapid prototyping, or any other task at that level. It's what you get (or one thing you get) when you try to axiomatize computation. Over time, the median language, meaning the language used by the median programmer, has grown consistently closer to Lisp. So by understanding eval you're understanding what will probably be the main model of computation well into the future.
Notes In translating McCarthy's notation into running code I tried to change as little as possible. I was tempted to make the code easier to read, but I wanted to keep the flavor of the original. In McCarthy's paper, falsity is represented by f, not the empty list. I used () to represent falsity so that the examples would work in Common Lisp. The code nowhere depends on falsity happening also to be the empty list nothing is ever consed onto the result returned by a predicate. I skipped building lists out of dotted pairs, because you don't need them to understand eval. I also skipped mentioning apply, though it was apply (a very early form of it, whose main purpose was to quote arguments) that McCarthy called the universal function in 1960 eval was then just a subroutine that apply called to do all the work. I defined list and the cxrs as abbreviations because that's how McCarthy did it. In fact the cxrs could all have been defined as ordinary functions. So could list if we modified eval, as we easily could, to let functions take any number of arguments. McCarthy's paper only had five primitive operators. He used cond and quote but may have thought of them as part of his metalanguage. He likewise didn't define the logical operators and and not, but this is less of a problem because adequate versions can be defined as functions. In the definition of eval. we called other functions like pair. and assoc., but any call to one of the functions we defined in terms of the primitive operators could be replaced by a call to eval.. That is,
(assoc. (car e) a)
could have been written as
(eval. '((label assoc. (lambda (x y) (cond ((eq (caar y) x) (cadar y)) ('t (assoc. x (cdr y)))))) (car e) a) (cons (list 'e e) (cons (list 'a a) a)))
There was a small bug in McCarthy's eval. Line 16 was (equivalent to) (evlis. (cdr e) a) instead of just (cdr e), which caused the arguments in a call to a named function to be evaluated twice. This suggests that this description of eval had not yet been implemented in IBM 704 machine language when the paper was submitted. It also shows how hard it is to be sure of the correctness of any length of program without trying to run it. I encountered one other problem in McCarthy's code. After giving the definition of eval he goes on to give some examples of higher-order functions| functions that take other functions as arguments. He defines maplist:
(label maplist (lambda (x f) (cond ((null x) '()) ('t (cons (f x) (maplist (cdr x) f))))))
then uses it to write a simple function diff for symbolic differentiation. But diff passes maplist a function that uses x as a parameter, and the reference to it is captured by the parameter x within maplist (Present day Lisp programmers would use mapcar instead of maplist here. This example does clear up one mystery: why maplist is in Common Lisp at all. It was the original mapping function, and mapcar a later addition.) It's an eloquent testimony to the dangers of dynamic scope that even the very first example of higher-order Lisp functions was broken because of it. It may be that McCarthy was not fully aware of the implications of dynamic scope in 1960. Dynamic scope remained in Lisp implementations for a surprisingly long time - until Sussman and Steele developed Scheme in 1975. Lexical scope does not complicate the definition of eval very much, but it may make compilers harder to write.
(cond (a b c))
14.3. Y-Combinator
;;; Show the Y combinator ;;; Taken from http://mvanier.livejournal.com/2897.html
;; (defun give-me-an-f-for-factorial (f) (lambda (n) (if (= n 0) 1 (* n (funcall f (- n 1))))))
;; this factorial does the job (defun factorialGOOD (n) (reduce #'(lambda (x y) (* x y)) (loop for i from 2 to n collecting i) ))
; This works (factorialGOOD 3) (setf (symbol-function 'factorialA) (give-me-an-f-for-factorial #'factorialGOOD)) (factorialA 4)
; Why shouldn't this work? ;(defun factorialA (n) n) (defun id (x) x) (defun factorial0 (give-me-an-f-for-factorial #'id)) (factorial0 0) ;;(setf (symbol-function 'factorialB) (give-me-f-for-factorial #'factorialB)) ;;(factorialB 4)
15. Common Lisp
15.1. REPL (Read-Eval-Print Loop)
Last three results are stored in:
* * **
+
++
/
/
//
- Form currently evaluated in the REPL
15.2. Read tables
#. Read macro. The following is evaluated by the reader
15.3. Comments
; this is a comment #| This is a comment of more than one line |#
(documentation 'foo 'function) ; returns doc string of function foo
15.4. Objects
15.4.1. Special Forms
- Controlling evaluation
(quote ) ; Prevents evaluation (if ) ; Boolean choice (progn ) ; Sequence a number of forms (progv ) (eval-when ({situation}*) {form}* ; allow pieces of code to be executed only at ; compile time (load-time-eval ) (locally ) (multiple-value-call ) (multiple-value-prog1 ) (the ) (with-added-methods )
- Manipulating the Lexical Enviroment
(let ((var1 val1) ; Introduce new lexical bindings for variables (var2 val2) …) body)
(let* …) ; Same as let but the initial variable forms can refer ; to variables introduced earlier in the variable list.
(setq ) ; Set variables whose bindings where created with let and let* (defun ) ; Define a function (flet ) ; Define functions (labels ) ; Define functions (generic-flet (generic-labels (macrolet ) ; Define local macros (symbol-macrolet ) ; Define local symbol macros (can't take arguments) (define-symbol-macro ) ; Define global symbol macros (can't take arguments) (function ) ; Gets the function object (declare )
- Local Flow of Control
(block <name> <form>*) (return-from <name> [<return-form>]) (tagbody <tag or compound-fomr>*) (go )
- Unwinding the stack
(catch ) (throw ) (unwind-protect )
15.4.2. Symbols
| symbol respecting spaces and case |
#: the symbol is not interned (gensym)
(find-symbol ) (intern ) (symbol-name )
(type-of )
15.4.3. Types
array
atom
base-character
extended-character
bignum
bit
bit-vector
character
compiled-function
complex
cons
double-float
fixnum
float
function
hash-table
integer
keyword
list
long-float
nil
null
number
package
pathname
random-state
ratio
rational
readtable
sequence
short-float
signed-byte
simple-array
simple-bit-vector
simple-string
simple-vector
single-float
standard-char
stream
string
symbol
t
unsigned-byte
vector
+
SEQUENCE (make-sequence type numels :initial-element val) (concatenate type el1 el2 …) SUBTYPE: LIST (list ) '() (cons el el) (append l1 l2 …) (car ) Contents of Address Register (first ) (second )… (tenth) (cdr ) Contents of Decrement Register (rest (last ) (caddar ) … (nth pos list ) (nthcdr pos list) SUBTYPE: ARRAY (make-array '(dim1 dim2 …)) #NA( ) where N is the dimension of the array (aref array coord1 coord2 …) SUBTYPE: VECTOR #(el1 el2 …) (vector el1 el2 …) SUBTYPE: STRING "this is a \"string\"" (search substring string) (string-trim list-of-chars string) (string-upcase string) (string-equal :start1 :end1 :start2 :end2 (string-greaterp :start1 :end1 :start2 :end2 (string-lessp :start1 :end1 :start2 :end2 (string-not-equal :start1 :end1 :start2 :end2 (string-not-greaterp :start1 :end1 :start2 :end2 (string-not-lessp :start1 :end1 :start2 :end2 (string/= :start1 :end1 :start2 :end2 (string< :start1 :end1 :start2 :end2 (string<= :start1 :end1 :start2 :end2 (string= :start1 :end1 :start2 :end2 (string> :start1 :end1 :start2 :end2 (string>= :start1 :end1 :start2 :end2
NUMBER SUBTYPE: FLOAT Short s S Single f F Double d D Long l L Default e E 1.7e-12 1.7d-12 SUBTYPE: RATIONAL SUBTYPE: INTEGER 10 #b1010 #B1010 #o12 #O12 #xa #xA #3R101 #3r101 (R for bases from 2 to 36) SUBTYPE: RATIO 2/7 SUBTYPE: COMPLEX #c(r i) #C(r i)
CHARACTER #\A #\B … #\Space #\Newline #\Return #\Tab #\Backspace #\Tilde #\Colon #\Page #\Linefeed #\Rubout SYMBOL STRUCTURE (defstruct foo bar baaz quux) This example defines a data type called foo which is a structure containing 3 fields. It also defines 4 functions which operate on this data type: make-foo, foo-bar, foo-baaz, and foo-quux. The first one makes a new object of type foo; the others access the fields of an object of type foo. Here is how to use these functions:
> (make-foo) #s(FOO :BAR NIL :BAAZ NIL :QUUX NIL) > (make-foo :baaz 3) #s(FOO :BAR NIL :BAAZ 3 :QUUX NIL) > (foo-bar ) NIL > (foo-baaz *) 3
FUNCTION HASH-TABLE (make-hash-table &key :test :size :rehash-size :rehash-threshold) (gethash index hashtable) (remhash key hashtable) (maphash function hashtable) (hash-table-count hashtable) (hash-table-size hashtable) (clrhash hashtable) (with-hash-table-iterator (iterator-name hashtable) body)
(multiple-value-setq (var1 var2 …) function)
15.4.4. Keywords
Evaluates to themselves t nil :<symbol>
15.4.5. Booleans
(and {form}*) (or {form}*) (not
15.4.6. Numbers
15.4.7. Characters
(code-char code) (char-code char)
15.4.8. Strings
(string ) (elt string index (char str pos) (schar str pos)
15.4.9. Lists
Function calls Lists
Association Lists (ALists) (assoc (parlis Property Lists (PLists) (list :p1 val1 :p2 val2…) (getf plist prop) (destructuring-bind )
Macros Operators
15.4.10. Bitvectors
#*1010101
15.4.11. Vectors
(vector el1 el2 …) #(c1 c2 c3 …) (vector-push ) (vector-push-extend ) (vector-pop )
15.4.12. Arrays
(make-array number :initial-elemnt :fill-pointer :adjustable :element-type)
15.4.13. Sequences
(length sequence) (count item sequence) (count-if) (count-if-not) (find item sequence ) (find-if item sequence) (position item sequence) (subst newitem item sequence) (substitute newitem item sequence) (every f l1 l2 … (some f l1 l2 … (notany (notevery (nsubstitute n comes from non-consing Function keyword arguments :test :key :start :end :from-end :count (sort (subseq (mismatch (map (map-into (reduce (remove
15.4.14. Date & time
(get-universal-time) ; returns current time as integer (decode-universal-time) (get-decoded-time) (encode-universal-time) internal-time-units-per-second (get-internal-real-time) (get-internal-run-time)
15.4.15. Predicates
(null object) (atom object) (symbolp object) (consp object) (listp object) (numberp object) (integerp object) (rationalp object) (floatp object) (realp object) (complexp object) (characterp object) (stringp object) (bit-vector-p object) (vectorp object) (simple-vector-p object) (simple-string-p object) (simple-bit-vector-p object) (arrayp object) (packagep object) (functionp object) (compiled-function-p object) (common-p object) (boundp variable) (fboundp variable)
(/= (< (<= (= (> (>= (char-equal (char-greaterp (char-lessp (char-not-equal (char-not-greaterp (char-not-lessp (char/= (char< (char<= (char= (char> (char>=
(eq e1 e2) ; t if e1 and e2 are the same identical object . NEVER use eq to ; compare values that may be numbers or characters. Tells whether ; two objects are implementationally the same > (eq 'a 'a) T > (eq 'a 'b) NIL > (eq '(a b c) '(a b c)) NIL
(eql e1 e2) ; t if e1 and e2 represents the same value. Tells whether two ; objects are conceptually the same. > (eql 'a 'a) T > (eql 3 3) T > (eql '(a b c) '(a b c)) NIL
(equal e1 e2) ; t if e1 and e2 are isomorphic objects (structurally similar). ; Two objects are equal if and only if their printed ; representation are the same. > (equal '(a b c) '(a b c)) T
(equalp e1 e2) ; t if e1 and e2 are equal. Two objects are equalp if they are ; equal; if they are characters and satisfy char-equal, which ; ignores alphabetic case and certain other attributes of ; characters; if they are numbers and have the same numerical ; value, even if they are of different types; or if they have ; components that are all equalp
(evenp (minusp number) (oddp (plusp number) (typep exp type) (subtypep type1 type2) (zerop number)
15.4.16. Math
(1+ number) (1- number) (+ n1 n2 …) (- (* (/ (floor (ceiling (truncate (round (mod (rem (+ (* (floor (/ x y)) y) (mod x y)) ≡ x (+ (* (truncate (/ x y)) y) (rem x y)) ≡ x (min (max/ (sqrt (isqrt (sin (cos (tan (asin (acos (atan (sinh (cosh (tanh (asinh (acosh (atanh (log (exp x) (expt base exponent) (random val) (ash (logior (logand (byte size position) (ldb bytespec integer)
15.4.17. Conses
(cons ; Avoid using: (rplaca) (rplacd)
15.4.18. Lists
(append l1 l2 …) (nconc n comes from non-consing (tailp (butlast (nbutlast (ldiff (reverse l (nreverse l n comes from non-consing (subst e1 e2 l (remove e l (copy-list
15.4.19. Sets
(adjoin (pushnew (member e l :test #'pred (member-if (member-if-not (intersection (union (set-difference (set-exclusive-or (subsetp
15.4.20. Mappings
(maplist #'f l1 l2 …) (mapcar #'f l1 l2 …) > (mapcar #'not '(t nil t nil t nil)) (NIL T NIL T NIL T) (mapcan (mapcon (mapc (remove-if #'f l) (remove-if-not #'f l) (sort list predicate
15.4.21. Flow control
(exit code) (sleep seconds) (return-from) (when) (unless) (if s S1 S2) (cond (test1 form*) (test1 form*) …) (case (value value) (l2 value) (otherwise value) (typecase (return) (trace func (untrace func (showstack
(while s S1 S2 … (do (variable-definition*) (end-test-form result-form*) statement*) variable-definition (var init step) > (do ((x 1 (+ x 1)) (y 1 (* y 2))) ((> x 5) y) (print y) (print 'working)) 1 WORKING 2 WORKING 4 WORKING 8 WORKING 16 WORKING 32
(do* ; same as do but assigns each variable its value before evaluating the step-form in variable-definition (dolist (var list-form) body-form*) > (dolist (x '(a b c)) (print x)) A B C NIL (dotimes (var count-form) body-form*) (dotimes (i 4) (print i))
15.4.22. Loop
(loop body-form*)
(loop for i from a to b by s …
(loop for i in sequence …
(loop for i on conscells …
(loop for i across vector|string …
(loop for i below x and expression finally expression)
(loop for i being the things in hash-or-package using (thing t) …
(loop for i = initial-value [ then step-form ]
things: hash-keys | hash-values symbols | present-symbols | external-symbols
(loop l1 l2 ..) until return
verb form [ into i ] append appending and as/for below by #'function collect collecting count counting do doing finally from/downfrom/upfrom on maximize maximizing minimize minimizing nconc nconcing return sum summing then to/upto/below/downto/above when with var [ = value-form ]
N*** Other
(form) argument is interpreted as a function rather than being evaluated. (eval
15.4.23. Printing
(print <string> <stream>) (write-line <string> <stream>)
15.4.24. Format
(format <destination> <control-string> <arguments>) <destination> t output to the terminal. nil return a string containing the output. stream can specify a file, or the terminal, or another program. <control-string> ~<begin>,<group>,<end>,<char><type> <begin> Pad with spaces <group> Pad in groups of spaces <end> Pad at the end of argument <char> Char to use to pad @ Do it from the left
<type> ( Start case @ Capitalizes the first letter of first word
Capitalizes the first letter of each word
:@ Capitalizes all letters of all words @: Capitalizes all letters of all words ) End case [ Start conditional ~; Conditional clause ~:; Default clause (must be the last one) #[ Start conditional. Clause selected by using a prefix parameter :[ Start conditional. First clause selected if argument is NIL, second clause is selected otherwise. @[ Start conditional. Only have one clause. If argument is non NIL processes the clause after backing up to make the argument available to be consumed again. ] End conditional { Start iteration. Argument must be a list ~^ Causes iteration to stop immediately ~# Refers to the number of items remaining to be processed in the list rather than the number of remaining arguments. ~* Skips one element of the list ~:* Move backwards one element of the list @{ Processes the remaining arguments as a list } End iteration. < Start justifying <number> Number of characters to justify ; Justification item :; The control string preceding this sequence will be triggered only if the current cursor position is beyond a certain point as specified by the second parameter. > End justifying
- Skips next argument
:* Move one argument before the current one ? Takes snippets of control string from the arguments / Call an arbitrary function to handle the next argument $ Currency % New line (like terpri) <number> Number of new lines to be created & New line if needed (like fresh-line) <number> Number of new lines to be created :@ Align a Print without delimiters (aesthetic). Same as princ b Print binary value c Character
output character by its name
@ output character in Lisp literal syntax d Integer :d Integer comma separated f Floating point <fit>,<decimal-fit>,<scaled-by-factor-of-10> <fit> Fits whole number <decimal-fit> Fits only decimal part <scaled-by-factor-of-10> Number is multiplied by 10factor g Floating point n p Plurals
reproduces previous argument
@ plurals for words (y -> ies) r Print number in letters
Ordinal
@ Roman s Print with appropriate delimiters (same as prin1) t Print at position <pos> Position in line v v is taken from arguments x Print hexadecimal value ~ single ~
15.5. Functions
(funcall #'f p1 p2 …) > (funcall #'+ 3 4) 7 (apply #'f opt l) > (apply #'+ 3 4 '(3 4)) 14
15.6. Anonymous Functions
((lambda (parameters*) S1 … Sm) val1 … valn)
15.7. Generic Functions
(defgeneric name(pars) (:documentation "This function does…."))
(defmethod method ((pars par)))
15.8. User-defined functions
(defun name (parameter*) "Optional documentation string" bodyform*)
Naming conventions more-than-one-word value->another Converts a value to another
Parameters Required Optional &optional Keyworded &key ((:tag par) default supplied-p) Rest &rest
Default (p val) Supplied (par val par-supplied-p)
15.9. Constants
(defconstant name initial-value-form [doc-string])
Naming convention for constants: name
15.10. Variables
Binding symbols: (get 'property 'list) (set 'symbol value) (setq symbol value) Instead of (let ((a nil) (b nil)) …), you can write (let (a b) …). let* is just like let except that it allows values to reference variables defined earlier in the let*.
Scope and extent are complementary notions. scope refers to space extent refers to time
15.10.1. Lexical variables
Lexical variables have lexical scope but indefinite extent, meaning they stick around for an indefinite interval, determined by how long they are needed.
> (set 'regular 5) 5 > (defun check-regular () regular) CHECK-REGULAR > (check-regular) 5 > (let ((regular 6)) (check-regular)) 5
15.10.2. Dynamic or special variables
Dynamic variables, by contrast, have indefinite scope since they can be referred to from anywhere, but they have dynamic extent
(defparameter var [value] [doc-string]) ; always assign value to var (defvar var value [doc-string]) ; only assign value to var if var is ; undefined
Naming convention for global variables: name
> (defvar special 5) SPECIAL > (defun check-special () special) CHECK-SPECIAL > (check-special) 5 > (let ((special 6)) (check-special)) 6
15.10.3. Closures
"Closes over" a binding The key thing to understand about closures is that it’s the binding, not the value of the variable, that’s captured. Thus, a closure can not only access the value of the variables it closes over but can also assign new values that will persist between calls to the closure. For instance, you can capture a closure in a global variable like this: (defparameter fn (let ((count 0)) #'(lambda () (setf count (1+ count))))) Then each time you invoke it, the value of count will increase by one. CL-USER> (funcall fn) 1 CL-USER> (funcall fn) 2 CL-USER> (funcall fn) 3
15.11. Assigments
(setf name1 val1 name2 val2 …) (getf (remf (makunbound ; Avoid using (incf name [step]) (decf name [step]) (push e l) (pop l) (rotatef) (shiftf)
15.12. Conditions
(define-condition <condition-name> (error) ((text :initarg :test :reader test)))
(make-condition
(error
(handler-case <expression> (<condition-type> ([<var>]) <code>)*)
(restart-case
(handler-bind (<binding>*) <form>*)
(invoke-restart
15.13. Classes
(class-of instance)
(defclass class-name (direct-superclass-name*) (slot-name slot-option*) class-option*)
slot-option :accessor function-name :initform expression :initarg symbol :reader function-name :writer function-name :alloctation {:instance | :class}
(defclass person() ((name :accessor person-name :initform 'bill :initarg :name) (age :accessor person-age :initform 10 :initarg :age)))
(make-instance class {initarg value} * (initalize-instance (slot-value (print-object (with-slots (with-accessors
15.14. Macros
(defmacro name (parameter*) "Optional documentation string" body-form*) (macroexpand expression) (macroexpand-1 expression) print-pretty parameter &body
15.15. Packages
COMMON-LISP or CL COMMON-LISP-USER or CL-USER KEYWORD PACKAGE
(defpackage (in-package (find-package (package-name (package-use-list (symbol-package (use-package
15.16. System
15.16.1. Files
(open :direction :if-does-not-exist :if-exists :element-type (read (read-byte (read-char (read-line (read-sequence sequence stream :start :end (write-byte (write-char (write-line (write-string (wirte-sequence (terpri) Start a newline (fresh-line) Start a newline if needed (force-output) (print (prin1 (princ (close (with-open-file
15.16.2. Filesystem
(directory (probe-file (rename-file (delete-file (ensure-directories-exist (file-write-date (file-author (file-length stream) (file-position stream :position-designator)
15.16.3. Pathnames
(make-pathname :host :device :directory :name :type :version :directory can be set to: '(:absolute "pathname") '(:relative "pathname") (pathname (pathname-host (pathname-device (pathname-directory (pathname-name (pathname-type (pathname-version (namestring (directory-namestring (file-namestring (parse-namestring) #p is a shorthand for #.(parsenamestring) (merge-pathnames #p"path1" [#p"path2"]) -> path2/path1 or default-path/path1 (enough-namestring DEFAULT-PATHNAME-DEFAULTS
15.16.4. Sockets
(resolve-host-ipaddr "www.someplace.org")
15.17. Features
15.18. Sintactic sugar
Quote operator: prevents argument for being evluated (quote symbol) ' Sharp quote operator (Mapping of names to actual function objects) (function name) #' Backquote separator `expression ,expression ,@expression expression is not expanded ,expression is expanded ,@expression is a list, and its spliced: (l1 l2 …) -> l1 l2 l3
(symbol-value)
(symbol-function)
;;; Example
;; (setf (symbol-function 'identidad) (lambda (x) x))
The four following sentences have the same effect:
(+ 1 2)
(apply #'+ '(1 2))
(apply (symbol-function ') '(1 2))
(apply #'(lambda (x y) ( x y)) '(1 2))
(apply #'+ 1 '(2))
15.19. Enviroments
15.19.1. Portacle
15.19.2. Roswell
15.20. OS
15.20.1. Mezzano
16. Hints
16.1. Comments
;;;; four preceding semi-colons for file headers, copyright and license information ;;; three preceding semi-colons for descriptive text ;; two preceding semi-colons for commentary on the immediately following text ;
16.2. Avoid using the following (they have side effects)
decf incf let* nreverse nstring-capitalize nstring-downcase nstring-upcase pop psetf psetq push pushnew remf remhash remprop rotatef rplaca rplacd set setf setq shiftf