// Working with lists, lambda functions, scoping // This transcript contains errors (and typos). Make sure you // understand the cause of each error! // For specifications of functions, see the free Common Lisp book: // https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/clm.html // To look up specific functions and symbols: // https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/index.html $ gcl GCL (GNU Common Lisp) 2.6.12 ANSI Nov 27 2014 05:23:43 Source License: LGPL(gcl,gmp), GPL(unexec,bfd,xgcl) Binary License: GPL due to GPL'ed components: (READLINE UNEXEC) Modifications of this banner must retain notice of a compatible license Dedicated to the memory of W. Schelter Use (help) to get some basic information on how to use GCL. // We are looking to produce the configuration (cat1 (cat2)), inspired by // http://www.cs.dartmouth.edu/~sergey/cs59/lisp/lisp-cons-with-cats.png >(cons cat1 (cons cat2 nil)) Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by EVAL. Condition in EVAL [or a callee]: INTERNAL-SIMPLE-UNBOUND-VARIABLE: Cell error on CAT1: Unbound variable: Broken at CONS. Type :H for Help. 1 Return to top level. >>1 Top level. // This leaves the second cat without a box. Unhappy cat2. >(cons 'cat1 (cons 'cat2 nil)) (CAT1 CAT2) >(cons 1 2) (1 . 2) >(cons 1 (cons 2 nil)) (1 2) // Finally, both cats are happy. Purrrrr. >(cons 'cat1 (cons (cons 'cat2 nil) nil)) (CAT1 (CAT2)) // Quote is a symbol, bound to a special form. It does not // evaluate its argument; (quote X) evaluates to X for any // expression X, passed on verbatim. >(car ''x) QUOTE >(car (quote (quote x))) QUOTE >(cdr '(2 3 4)) (3 4) // NIL and () are, in fact, the same value! >(cdr ()) NIL >() NIL >(cdr '(1)) NIL >(cdr (cons 1 2))) 2 >(car (quote (quote x))) QUOTE // Eval is E of the EVAL; it is exactly what GCL's REPL calls to evaluate your prompt. // The following adds another evaluation to REPL prompt's one: >(eval 'x) Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by EVAL. Condition in EVAL [or a callee]: INTERNAL-SIMPLE-UNBOUND-VARIABLE: Cell error on X: Unbound variable: Broken at EVAL. Type :H for Help. 1 Return to top level. >>1 Top level. >(eval ''x) X >(eval '''x) 'X >(consp (eval '''x)) T // + and * have surprising bindings as symbols, beyond their function bindings. // + stands for the previous expression after "R" , * for it after "E" of the REPL. >+ (CONSP (EVAL '''X)) >* (CONSP (EVAL '''X)) // Some functions for working with lists: >(help 'member) ----------------------------------------------------------------------------- MEMBER [Function] (not found "gcl.info") From ((MEMBER . Lists) gcl-si.info): -- Function: MEMBER (item list &key (test #'eql) test-not (key #'identity)) Package:LISP Returns the tail of LIST beginning with the first ITEM. ----------------------------------------------------------------------------- >(member 6 '(1 2 3 4 5 6 7 8)) (6 7 8) >(help 'member-if) ----------------------------------------------------------------------------- MEMBER-IF [Function] (not found "gcl.info") From ((MEMBER-IF . Lists) gcl-si.info): -- Function: MEMBER-IF (test list &key (key #'identity)) Package:LISP Returns the tail of LIST beginning with the first element satisfying TEST. ----------------------------------------------------------------------------- >(ODDP 4) NIL >(ODDP 5) T // It should be clear why this doesn't work: >(member-if oddp '(1 2 3 4 5 6 7 8)) Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by EVAL. Condition in EVAL [or a callee]: INTERNAL-SIMPLE-UNBOUND-VARIABLE: Cell error on ODDP: Unbound variable: Broken at MEMBER-IF. Type :H for Help. 1 Return to top level. >>1 Top level. >(help 'oddp) ----------------------------------------------------------------------------- ODDP [Function] (not found "gcl.info") From ((ODDP . Numbers) gcl-si.info): -- Function: ODDP (integer) Package:LISP Returns T if INTEGER is odd; NIL otherwise. ----------------------------------------------------------------------------- // This works: >(member-if 'oddp '(1 2 3 4 5 6 7 8)) (1 2 3 4 5 6 7 8) // This works too: >(member-if (SYMBOL-FUNCTION 'oddp) '(1 2 3 4 5 6 7 8)) (1 2 3 4 5 6 7 8) >(member-if #'oddp '(1 2 3 4 5 6 7 8)) (1 2 3 4 5 6 7 8) // SYMBOL-FUNCTION retrieves the function binding of a symbol: // // #' is shorthand of a very similar function, called FUNCTION. // For symbols with a functional binding it works the same as SYMBOL-FUNCTION. // Inserted example: >(car (quote #'+)) FUNCTION // this also works (yay shorthand): >(car '#'+) FUNCTION // end inserted example, back to transcript >(SYMBOL-FUNCTION 'oddp) # >(member-if 'oddp '(1 2 3 4 5 6 7 8)) (1 2 3 4 5 6 7 8) >(member-if 'evenp '(1 2 3 4 5 6 7 8)) (2 3 4 5 6 7 8) >(remove-if 'evenp '(1 2 3 4 5 6 7 8)) (1 3 5 7) >(remove-if-not 'evenp '(1 2 3 4 5 6 7 8)) (2 4 6 8) >(help 'sort) ----------------------------------------------------------------------------- SORT [Function] (not found "gcl.info") From ((SORT . Sequences and Arrays and Hash Tables) gcl-si.info): -- Function: SORT (sequence predicate &key (key #'identity)) Package:LISP Destructively sorts SEQUENCE. PREDICATE should return non-NIL if its first argument is to precede its second argument. ----------------------------------------------------------------------------- >(sort '(1 2 3 4 5 6) #'<) (1 2 3 4 5 6) >(sort '(1 2 3 100 4 5 6) #'<) (1 2 3 4 5 6 100) >(sort '(1 2 3 100 4 5 6) '<) (1 2 3 4 5 6 100) >#'< # >#'> #> // List processing functions can take any user-defined functions, too: >(defun over3 (x) (> x 3)) OVER3 >(over3 4) T >(over3 3) NIL >(remove-if 'over3 '(1 2 3 4 5 6 7 8)) (1 2 3) >(remove-if-not 'over3 '(1 2 3 4 5 6 7 8)) (4 5 6 7 8) >over3 Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by EVAL. Condition in EVAL [or a callee]: INTERNAL-SIMPLE-UNBOUND-VARIABLE: Cell error on OVER3: Unbound variable: Broken at EVAL. Type :H for Help. 1 Return to top level. >>1 Top level. >#'over3 (LAMBDA-BLOCK OVER3 (X) (> X 3)) >(SYMBOL-VALUE 'over3) Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by SYMBOL-VALUE. Condition in SYMBOL-VALUE [or a callee]: INTERNAL-SIMPLE-UNBOUND-VARIABLE: Cell error on OVER3: Unbound variable: Broken at SYMBOL-VALUE. Type :H for Help. 1 Return to top level. >>1 Top level. >(SYMBOL-FUNCTION 'over3) (LAMBDA-BLOCK OVER3 (X) (> X 3)) // Creating and passing anonymous ("lambda") functions as needed is a very common LISP idiom. // All functions are first-class values in LISP, and can be passed as arguments, // bound to variables, and so on. >(remove-if-not (lambda (x) (> x 4)) '(1 2 3 4 5 6 7 8)) (5 6 7 8) // Lambda functions in the first position get evaluated on the arguments: >((lambda (x) (+ x 1)) 5) 6 // Another way to call them: >(funcall (lambda (x) (+ x 1)) 5) 6 >(funcall (lambda (x y) (+ x y)) 5 6) 11 // and another (this one needs the arguments to be in a list of their own): >(apply (lambda (x y) (+ x y)) (5 6)) Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by EVAL. Condition in EVAL [or a callee]: INTERNAL-SIMPLE-TYPE-ERROR: 5 is not of type FUNCTION: Broken at APPLY. Type :H for Help. 1 Return to top level. >>1 Top level. >(apply (lambda (x y) (+ x y)) '(5 6)) 11 >(FUNC FUNCALL FUNCTION FUNCTIONP // Funcall works with either a symbol bound to a function, or its symbol-function value: // You can think of sort, member-if, remove-if, and their kind as using FUNCALL. >(FUNCALL 'oddp 4) NIL >(FUNCALL #'oddp 4) NIL >(FUNCALL #'oddp 5) T // We looked at quicksort in LISP here (qs.lisp in the course dir) >^Z [1]+ Stopped gcl dhcp-212-243:lisp user$ v qs qs.lisp qsort.lisp dhcp-212-243:lisp user$ v qs.lisp [2]+ Stopped view +"syn on" qs.lisp dhcp-212-243:lisp user$ %gcl gcl // Back to GCL. There was some new syntax in qs: LET // LET creates symbol bindings that exist only within its expression, before the closing ")" >(let ((x 3) (y 5)) (+ x y)) 8 >x Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by EVAL. Condition in EVAL [or a callee]: INTERNAL-SIMPLE-UNBOUND-VARIABLE: Cell error on X: Unbound variable: Broken at EVAL. Type :H for Help. 1 Return to top level. >>1 Top level. >y Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by EVAL. Condition in EVAL [or a callee]: INTERNAL-SIMPLE-UNBOUND-VARIABLE: Cell error on Y: Unbound variable: Broken at EVAL. Type :H for Help. 1 Return to top level. >>1 Top level. >(setq l '(1 2 3 4 5 6 7)) (1 2 3 4 5 6 7) >(let ((c (car l)) (r (cdr l))) (+ c (car r))) 3 >c Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by EVAL. Condition in EVAL [or a callee]: INTERNAL-SIMPLE-UNBOUND-VARIABLE: Cell error on C: Unbound variable: Broken at EVAL. Type :H for Help. 1 Return to top level. >>1 Top level. // Global bindings of a symbol, if any, are shadowed inside a LET, but spring back after it: >(setq c 1000) 1000 >(let ((c (car l)) (r (cdr l))) (+ c (car r))) 3 >c 1000 // Yet LET scoping can be implemented in _TWO_ very different ways: // _dynamic_ and _lexical_. GCL uses lexical scoping by default, Emacs' ELISP uses dynamic scoping. // // The difference between these becomes important when the expression inside LET // yields a function (say, a lambda function), and that function is called again // outside of the LET. What happens to the value of variable that was bound in that LET? // // Under dynamic scoping, values of variables are looked up by name, in the global symbol table, // at the moment when the expression containing the variable is evaluated. Thus, the // variable will get whatever value it's bound to now, or none ("undefined variable" error). // Hence the name "dynamic": it depends on the runtime, and cannot be told based just on the // code that created the function. // // Lexical scoping is based on _closures_: a function made in a LET (or in another expression // that provides its own scope, such as LAMBDA) "closes" over the variables it references. // This means that copies of these variables are made, and their values are saved in // these copies; they will be accessed whenever that function is called, and all other // bindings and symbols will be ignored. // Hence the name "lexical": you can tell from the code that created the function what // values the "closed-over" variables will have. // GCL is lexically scoped: >(setq f (let ((x 1)) (lambda (y) (+ x y)))) (LAMBDA-CLOSURE ((X 1)) () () (Y) (+ X Y)) >f (LAMBDA-CLOSURE ((X 1)) () () (Y) (+ X Y)) // Note that X is not globally bound. This would break the following under dynamic scoping // (see the Elisp example below). But under lexical scoping it works; a private copy // of "x" with value 1 sticks around after the LET: >(funcall f 4) 5 >(setq x 100) 100 >x 100 // The closure doesn't care about the global value of x. It captured its own // copy when it was created, and it keeps it. >(funcall f 4) 5 //---------------------- Emacs LISP example ----------------------------- // This example has been evaluated in Emacs, in lisp-interaction-mode. // I added => in front of output lines. (setq f (let ((x 1)) (lambda (y) (+ x y)))) => (lambda (y) (+ x y)) f => (lambda (y) (+ x y)) (funcall f 4) => fails with "Symbol's value as variable is void: x" (setq x 100) => 104 (setq x 1000) => 1004 // As you can see, GCL & Elisp behave completely differently! // In Elisp, "x" behaves like a global configuration variable; // in GCL, it is captured and becomes a part of the function. //---------------------- end Elisp example ------------------------------ // ...and we are back to GCL: // Writing a length function: >(len ()) Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by EVAL. Condition in EVAL [or a callee]: INTERNAL-SIMPLE-UNDEFINED-FUNCTION: Cell error on LEN: Undefined function: Broken at EVAL. Type :H for Help. 1 Return to top level. >>1 Top level. // First attempt. I forgot something important :) >(defun len (lst) (cond ((null lst) 0) ((consp lst) (+ 1 (cdr lst))) (t "error"))) LEN // testing, so far so good: >(len ()) 0 // Oops: >(len '(1)) Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by +. Condition in + [or a callee]: INTERNAL-SIMPLE-TYPE-ERROR: NIL is not of type NUMBER: Broken at +. Type :H for Help. 1 Return to top level. >>1 Top level. // Take two: >(defun len (lst) (cond ((null lst) 0) ((consp lst) (+ 1 (len (cdr lst)))) (t "error"))) LEN >(len ()) 0 >(len '(1)) 1 >(len '(1 2 3) ) 3 >(len '(1 2)) 2 >(len 1) "error" // Yay! Let's be more LISP-y, and use a special keyword symbol that evaluates to itself // instead of a string: >(defun len (lst) (cond ((null lst) 0) ((consp lst) (+ 1 (len (cdr lst)))) (t :error))) LEN >(len 1) :ERROR // Keyword symbols are a special kind of symbol that evaluates to itself, and whose // binding cannot be changed. They also live in a special package namespace (we'll talk about these later). >:error :ERROR // Standard library symbols: >(SYMBOL-PACKAGE 'member) #<"LISP" package> // User-defined symbols: >(SYMBOL-PACKAGE 'len) #<"COMMON-LISP-USER" package> // Keyword symbols: >(SYMBOL-PACKAGE :error) #<"KEYWORD" package> >(SYMBOL-PACKAGE ':error) #<"KEYWORD" package> // Let's write some more recursive functions for lists: // Pasting from Emacs, which nicely shows matching parens and auto-indents: // A slightly fancier LEN: >(defun len (lst) (cond ((null lst) 0) ((consp lst) (let ((c (car lst)) (r (cdr lst))) (+ 1 (len r)))) (t :error))) LEN // Now let's do product. Note how * behaves on its lists of arguments: >(*) 1 >(* 1 2 3) 6 >(funcall '* 1 2 3 4) 24 >(funcall '* ) 1 >(apply '* '()) 1 >(defun prod (lst) (cond ((null lst) 1) ((consp lst) (let ((c (car lst)) (r (cdr lst))) (* c (prod r)))) (t :error))) // All functions that recursively process lists naturally follow this pattern. // Note that we need to pass in the return value for the base case of (), to // which recursion and CDR will eventually bring us down. >(defun proc (lst func baseval) (cond ((null lst) baseval) ((consp lst) (let ((c (car lst)) (r (cdr lst))) (funcall func c (proc r func baseval)))) (t :error))) PROC >(setq sum (lambda (lst) (proc lst '+ 0))) (LAMBDA-CLOSURE () () () (LST) (PROC LST '+ 0)) >(funcall sum '(1 2 3 4)) 10 >(funcall sum '(1 2 3 4 5)) 15 >(setq prod (lambda (lst) (proc lst '* 1))) (LAMBDA-CLOSURE () () () (LST) (PROC LST '* 1)) >(funcall prod '(1 2 3 4 5)) 120 // This pattern is actually even more general, the so-called FOLD functions. // We'll get to it next time. // Here is another very frequently used list-processing function: >(mapcar (lambda (x) (* 2 x)) '(1 2 3 4 5 6)) (2 4 6 8 10 12) >(map 'list (lambda (x) (* 2 x)) '(1 2 3 4 5 6)) (2 4 6 8 10 12) >(help 'mapcar) ----------------------------------------------------------------------------- MAPCAR [Function] (not found "gcl.info") From ((MAPCAR . Iteration and Tests) gcl-si.info): -- Function: MAPCAR (fun list &rest more-lists) Package:LISP Applies FUN to successive cars of LISTs and returns the results as a list. ----------------------------------------------------------------------------- >(help 'map) ----------------------------------------------------------------------------- MAP [Function] (not found "gcl.info") From ((MAP . Sequences and Arrays and Hash Tables) gcl-si.info): -- Function: MAP (result-type function sequence &rest more-sequences) Package:LISP FUNCTION must take as many arguments as there are sequences provided. The result is a sequence such that the i-th element is the result of applying FUNCTION to the i-th elements of the SEQUENCEs. -----------------------------------------------------------------------------