=================[ LISP Readings ]============================ Unlike C, which compiles down to the semantics of CPU ISA instructions and raw memory bytes, LISP semantics is defined via a virtual machine that has symbols, a limited set of primitive data types such as integers, characters, and strings, and the one naturally recursive structure for building up more complex data types: the CONS cell. CONS cells are the one and only way of composing values in LISP---and, in fact, the only way of composing programs in LISP! Lists in LISP are simply sequences of CONS cells. A program in LISP is just such a list, intended to be fed to EVAL, a function that evaluates them. These resources serve as great introductions to LISP. Mix and match them depending on your learning style. No matter in what order you read them, have your LISP shell open, and try every command; this is the only way. https://www.robots.ox.ac.uk/~dwm/Courses/4AI_1995/lisp.pdf — The discussion of scoping in Section 6 is a bit dated: most modern LISPs including Emacs LISP have static scoping. Chapters 1 and 2 of Paul Graham's book "ANSI Common LISP": https://sep.turbifycdn.com/ty/cdn/paulgraham/acl1.txt https://sep.turbifycdn.com/ty/cdn/paulgraham/acl2.txt Paul Graham's book is definitely worth owning and very popular. Although there is no official free copy online on his website, his other book "On Lisp" is free: https://www.paulgraham.com/onlisp.html Read sections 2.1--2.3 carefully. There are plenty of free tutorials for Common Lisp, the most developed form of LISP. You can start here: https://lisp-lang.org/learn/getting-started/. (Note that Emacs' Lisp is not Common Lisp, but includes most of its elements). =================[ LISP History and Philosophy ]============== Chapter 3 in the Mitchell textbook covers LISP. Sections 3.1--2 cover LISP's history, but it should be noted that LISP lives on many shapes, including the programmable Emacs editor. Sections 3.3 and 3.4 give an overview of the language. You may skip the pieces about Scheme, a later dialect of LISP that cleaned up most of the historical inconsistencies and introduced awesome new optimizations. We'll revisit them later. Pay special attention to the abstract machine of CONS cells described in 3.4.3 and use the exercises in it to check yourself. Also pay special attention to 3.4.4 (programs as the fundamental data type, the list of cons cells) and 3.4.6 (recursion on the object's intended structure, also tied to cons cells). The idea that functions should use no loops or other iterators (such as pointers or references external to the data objects), but should rather use recursion over the object's own natural structure is very powerful, and drives modern languages such as Haskell and Rust, in the guise of 'pattern matching' style of coding (i.e., matching the object's structure). After you absorb this idea, the code that works on complex objects "practically writes itself". Moreover, this style drives you to think about the corner cases, such as getting atoms where you expect lists (i.e, a cons cell). Once noted, this developed into type-driven programming (ML, Haskell, Idris, Agda, etc.) Writing code that recurses on the object's own structure should become your second nature. Practice, practice, practice: go through the examples in Paul Graham's Chapter 2 of "ANSI Common LISP", Chapter 2 of "On Lisp", etc. =================[ LISP, the first steps in class ]==================== These examples use GNU Common Lisp, GCL. sergey@snowball cs59 % gcl GCL (GNU Common Lisp) 2.6.14 Fri Jan 13 10:47:56 AM EST 2023 ANSI git: Version_2_6_14 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. Temporary directory for compiler files: /var/folders/tp/17fq2kwj13bb2xj7s5hbr0ch0000gn/T/ >(cons 1 nil) (1) >(cons 3 5) (3 . 5) // <<-- the "dotted pair", something of an edge case in otherwise recursive use of CONS cells >(car (cons 3 5)) 3 >(cdr (cons 3 5)) 5 >(list 3 5) (3 5) >(cons 3 (cons 5)) // <<--- Oops, cons takes two arguments, not 1 Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by CONS. Condition in CONS [or a callee]: INTERNAL-SIMPLE-PROGRAM-ERROR: CONS [or a callee] requires more than one argument. Broken at CONS. Type :H for Help. 1 Return to top level. >> 1 >(cons 3 (cons 5 nil)) (3 5) >(list 3 5) // <<<---- exactly same structure as above (3 5) >(car (list 3 5)) 3 >(cdr (list 3 5)) (5) >car // <<---- in LISP, all symbols can have a value and a function value bound to them. CAR // has the latter, not the former (it's value is "unbound") 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 CAR: Unbound variable: Broken at EVAL. Type :H for Help. 1 Return to top level. >>1 Top level. >#'car // <<--- function value # // So, how can we bind a value to a symbol? There's a function called SET. But: >(set x 3) 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 SET. Type :H for Help. 1 Return to top level. >>1 // Oops, this function _evaluates_ X first, and can't, since it has no value bound to it yet. // So we want to hold off that evaluation. This is what the "special form" QUOTE does. // Special forms do not evaluate some of their arguments (unlike functions). IF is another, and also SETQ (see below) Top level. >(set (quote x) 3) 3 >x // x is now bound, it evaluates to 3 3 >(setq x 5) // SETQ is a special form equivalent to (set (quote ) ) 5 // The above (setq x 5) is also a list of CONS cells. Let's construct it, and pass it to EVAL. >(eval (cons setq (cons x (cons 5 nil)))) // Oops, what did I do wrong here? Ah, SETQ gets evaluated // and has no symbol value. We want the symbol, not the value, // so we need to quote it 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 SETQ: Unbound variable: Broken at CONS. Type :H for Help. 1 Return to top level. >>1 Top level. >(eval (cons (quote setq) (cons x (cons 5 nil)))) // Oops, X got evaluated too, so we got (setq 5 5) into EVAL. // But SETQ needs a symbol as its first argument, not 5. Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by SETQ. Condition in SETQ [or a callee]: INTERNAL-SIMPLE-TYPE-ERROR: 5 is not of type SYMBOL: Broken at SETQ. Type :H for Help. 1 Return to top level. >>1 Top level. >(eval (cons (quote setq) (cons (quote x) (cons 5 nil)))) // Finally. 5 >x 5 >(cons (quote setq) (cons (quote x) (cons 5 nil))) // Double check (SETQ X 5) /// The following are all the same forms of creating the same list the same way. 'x stands for (quote x). /// These abbreviations are known as "syntactic sugar". But make no mistake: it's just CONSes and /// nothing but the CONSes in the end. >(cons (quote setq) (cons (quote x) (cons 5 nil))) (SETQ X 5) >(cons 'setq (cons 'x (cons 5 nil))) (SETQ X 5) >(list 'setq 'x 5) (SETQ X 5) ////// Let's define some functions: >(defun plus1 (x) (+ x 1)) PLUS1 >(plus1 4) 5 >(plus1 x) 6 >x // Note that the value bound to X is unchanged! 5 >#'plus1 (SYSTEM:LAMBDA-BLOCK PLUS1 (X) (+ X 1)) // this is an "unnamed function that takes one argument" >#'+ # /// Before we write functions to work on lists, let's get some predicates to tell CONSes and ATOMs /// apart, and also to test for NIL. >(consp 1) NIL >(consp (list 3)) T >(atomp 1) // it's just ATOM 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 ATOMP: Undefined function: Broken at EVAL. Type :H for Help. 1 Return to top level. >>1 Top level. >(atom 1) T >(null nil) T >(null 1) NIL >(evenp 5) NIL >(evenp 6) T >(oddp 5) T >t // The special atom T for the boolean truth value evaluates to itself, and so does NIL T >nill // typo. Leaving it here so that you see what happens when a non-existent symbol is being evaluated 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 NILL: Unbound variable: Broken at EVAL. Type :H for Help. 1 Return to top level. >>1 Top level. >nil NIL >(consp 1) NIL >(consp (list 1 2)) T >(consp (cons 1 2 )) T >(null 1) NIL >(null nil) T >(null (cons 1 nil)) NIL >(null (cdr (cons 1 nil))) T >(null (car (cons 1 nil))) NIL /// IF is a special form. Either the 2nd or the 3rd argument is evaluated, but not both. >(if (oddp x) 1 2) 1 >x 5 >(plus1 x) 6 >x 5 /// Now we can write the list length function. A list is either a NIL (empty list, base case) or a CONS. /// If it's a CONS then the length of the list is 1 + the length of whatever hangs off the CONS' CDR: >(defun mylen (xs) (if (null xs) 0 (+ 1 (mylen (cdr xs))))) ^^^^^^^^^^^ ^^^^^^ // <<--- these parts _match_ the list's recursive definition MYLEN >(mylen nil) 0 >(mylen (cons 1 nil)) 1 >(mylen (list 1 2 3 4 5 56 6)) 7 >(mylen 1) /// What does it mean to measure the length of an integer? Where should be protect against it? /// These are really deep questions, as it turned out. Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by CDR. Condition in CDR [or a callee]: INTERNAL-SIMPLE-TYPE-ERROR: 1 is not of type LIST: Broken at CDR. Type :H for Help. 1 Return to top level. >>1 /// At least, we can create a custom error value. Top level. >(defun mylen (xs) (if (atom x) (error "not a cons") (if (null xs) 0 (+ 1 (mylen (cdr xs))))) ) MYLEN >(mylen 1) Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by MYLEN. SIMPLE-ERROR: not a cons // <<--- our own freshly defined error Broken at ERROR. Type :H for Help. 1 Return to top level. >>1 Top level. > ) ^C Correctable error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by SYSTEM::GCL-TOP-LEVEL. If continued: Type :r to resume execution, or :q to quit to top level. SIMPLE-ERROR: Console interrupt. Broken at SYSTEM::GCL-TOP-LEVEL. Type :H for Help. 1 (continue) Type :r to resume execution, or :q to quit to top level. 2 Return to top level. >> 1 //// Sum the list. The function has the same structure that repeats the recursive definition of a list of CONSes: >(defun mysum (xs) (if (null xs) 0 (+ (car xs) (mysum (cdr xs))))) ^^^^^^^^^^^^^ ^^^^^^^^ ^^^^^^^^ // <<-- all of these come from the definition MYSUM >(mysum nil) 0 >(mysum (cons 100 nil)) 100 >(mysum (list 100 200 300 400)) 1000 -------- We'll continue on Thursday ---------