// This is the in-class log of the first steps in Lisp. For assigned and suggested reading // about Lisp, please refer to https://cosc59.gitlab.io/lisp/lisp-intro-gcl.txt // We will use several Lisp implementations: Gnu Common Lisp (GCL) this time, but // also Emacs Lisp, SBCL, and Scheme. sergey@snowball lisp % 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/ // When started, a Lisp interpreter gives you a prompt to interact with its environment. // It is known as the REPL, Read-Eval-Print loop. Strings go in, are made into Lisp's // fundamental lists by READ; these lists are evaluated as Lisp programs by EVAL, // and the result is printed by PRINT. // NOTE: In Lisp, the program IS the fundamental data type and vice versa. Every program // is a list and is constructed as a list. More about this construction, a.k.a. CONS cells, // later. // Lisp has integers, including arbitrary length integers (Bignums). They all evaluate // to themselves. >1 1 >10000000000000000000000000000000000 10000000000000000000000000000000000 >10000000000079287589272987529878579857287539287352983752895729875287598753 10000000000079287589272987529878579857287539287352983752895729875287598753 // Lisp supports arbitrary precision arithmetic: >(+ 10000000000079287589272987529878579857287539287352983752895729875287598753 1) 10000000000079287589272987529878579857287539287352983752895729875287598754 // Lisp has True and False values, T and NIL. NIL doubles as an empty list. // These values also evaluate to themselves: >nil NIL >t T // All lists are sequences of CONS cells. There is no other way to make // a list or in fact any data structure (a tree, a tuple, a table, // anything at all that composes primitive values) other than via CONS cells! >(cons 1 (cons 2 nil)) (1 2) // These cons cells as ASCII art: car cdr car cdr +-----+-----+ +-----+-----+ | • | •--+--->| • | NIL + +--+--+-----+ +--+--+-----+ | | v v 1 2 >(cons 1 (cons 2 (cons 3 nil))) (1 2 3) // These cons cells as ASCII art: car cdr car cdr car cdr +-----+-----+ +-----+-----+ +-----+-----+ | • | •--+--->| • | •--+--->| • | NIL | +--+--+-----+ +--+--+-----+ +--+--+-----+ | | | v v v 1 2 3 // There is a LIST helper function, but it builds the same set of cons cells // as (cons 1 (cons 2 (cons 3 nil))) >(list 1 2 3) (1 2 3) // A list of exactly one element: >(cons 1 nil) (1) // This is an error: CONS expects two arguments, not one: >(cons 1 (cons nil)) 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 Top level. // Let's see the Read-Eval-Print loop explicitly. There are several ways to READ, // corresponding to different input channels. We'll use READ-FROM-STRING: >(READ READ READ-FROM-STRING READER-METHOD-CLASS READ-BYTE READ-LINE READTABLE READ-CHAR READ-PRESERVING-WHITESPACE READTABLE-CASE READ-CHAR-NO-HANG READ-SEQUENCE READTABLEP READ-DELIMITED-LIST READER-ERROR >(READ-FROM-STRING "(+ 1 2)") (+ 1 2) 7 // <-- Common Lisp functions can return multiple values. This is the position // in the input string where reading stopped, length of the string if // all of it was read. See (help 'read-from-string) >(eval (READ-FROM-STRING "(+ 1 2)")) 3 >(print (eval (READ-FROM-STRING "(+ 1 2)"))) 3 3 // <-- Print returns the value and prints it, so you see two "3"s // There is a confusing feature of Lisp that got removed in Scheme: // a symbol has two values, a symbol-value and a function-value. The // function value is the function to call if the symbol is the first // member in an evaluated list, like (+ ...). The symbol value is the // value it will have in an argument position, i.e., second in the list or // further down the list. // Somewhat confusingly, the symbol + in GCL will get you back the last form you typed: >+ (PRINT (EVAL (READ-FROM-STRING "(+ 1 2)"))) // If you want to see what kind of function + binds to, you need to use (FUNCTION +) // or shorthand for it, #': >#'+ # >(FUNCTION +) # // Calling this function can be done with >(+ 1 2) 3 // or with FUNCALL in a different position: >(FUNCALL #'+ 1 2 ) 3 // We can create new symbols with SET and new functions with DEFUN. // First, if a symbol is not bound, we'll get an error if we try to evaluate it: >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 // Evaluation is recursive: all arguments of normal functions are evaluated before the // function itself is called: Top level. >(+ (* 2 3) 10) 16 >(+ (* 2 3) (- 15 5)) 16 // However, we also have _special forms_ that do not evaluate their arguments. // One of the most important ones, QUOTE, does just that: does not evaluate its // argument, just simply returns it: >(quote x) X // To bind a symbol to a value, we use SET and QUOTE in combination. Note: without // QUOTE, we'd have X evaluated, because SET is a function: >(set (quote x) 100) 100 // So now X has a value: >x 100 >(+ x x) 200 >(* x 2) 200 // Writing (quote x) is tiresome, so there is a SETQ special form that doesn't evaluate // its first argument (but evaluates the second one): >(SETQ x 200) 200 >x 200 // There is also 'x, shorthand for (quote x) >(set 'x (+ 100 x)) 300 // We can test values to see what they are: >(consp x) // <<--- is this a cons cell? NIL >(atom x) // <---- is this an atom? T >(atom 100) T >(atom "foo") T >(atom (cons 1 nil)) NIL >(consp (cons 1 nil)) T // IF is a very important special form. We want only one of its arguments to be evaluated, not both! >(if (> x 10) "foo" "bar") "foo" >(if (> x 1000) "foo" "bar") "bar" // IF has a value: it's the value of the argument that got evaluated >(if (> x 10) (set 'y "foo") (set 'y "bar")) // <<-- could be (setq y ..) too "foo" >y "foo" >(if (> x 1000) (set 'y "foo") (set 'y "bar")) "bar" >y "bar" // ---------------------- Ridiculous Outtakes ------------------- // // Skip this at first reading. // OK, what did I do wrong here? I didn't notice it at first. >(if (> x 1000) (set (quote y "foo")) (set (quote y) "bar"))) "bar" >y "bar" // OK, now the tip-off: >(if (> x 10) (set (quote y "foo")) (set (quote y) "bar"))) Error: Fast links are on: do (si::use-fast-links nil) for debugging Signalled by QUOTE. Condition in QUOTE [or a callee]: INTERNAL-SIMPLE-PROGRAM-ERROR: Too many arguments. Broken at QUOTE. Type :H for Help. 1 Return to top level. >>1 // So I thought I fixed it, but in fact I just made it worse. // The output made no sense to me! Top level. >(if (> x 10) (set (quote y) "foo")) (set (quote y) "bar"))) "foo" > "bar" >y "bar" >x 100 // And then I noticed that I actually closed off my IF early: >(if (> x 10) (set (quote y) "foo")) (set (quote y) "bar")) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ "foo" > "bar" >y "bar" // So I fixed it, and it finally made sense: >(if (> x 10) (set (quote y) "foo") (set (quote y) "bar")) "foo" >(if (> x 1000) (set (quote y) "foo") (set (quote y) "bar")) "bar" >y "bar" >(if (> x 10) (set (quote y) "foo") (set (quote y) "bar")) "foo" >y "foo" // And the moral of this story is: always use an editor that shows you which // opening parenthesis your closing one matches! Use Emacs if you want // to be an old style programmer :) // Also, I should've used (set 'y ..) or (setq y ..) rather than being fancy. // The less you type, the less mistakes you'll make. //---------------------------- end outtakes ------------------------------ // We can define functions: >(defun plus1 (x) (+ x 1)) PLUS1 Top level. >(plus1 15) 16 // Functions don't have symbol values by default. They have function only values in DEFUN-ed: >plus1 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 PLUS1: Unbound variable: Broken at EVAL. Type :H for Help. 1 Return to top level. >>1 // They have function-values. >#'plus1 (SYSTEM:LAMBDA-BLOCK PLUS1 (X) (+ X 1)) // This LAMBDA-BLOCK is important! It makes functions first-class objects that // can be passed around as values, serve as arguments to other functions, and // get applied to lists of arguments. // FUNCALL needs a function-value. It won't work with a symbol-value: >(FUNCALL plus1 10) 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 PLUS1: Unbound variable: Broken at FUNCALL. Type :H for Help. 1 Return to top level. >>1 // FUNCALL will also work with the symbol (quoted, hence not evaluated): Top level. >(FUNCALL 'plus1 10) 11 >(FUNCALL (quote plus1) 10) 11 >(FUNCALL 'plus1 10) 11 // Remember: quoting gives you the symbol itself, without trying to evaluate it. >'x X // One more test function: testing for NIL, the empty list that doubles as FALSE: >(null nil) T >(null '()) T >(NULL 0) NIL >(NULL "nil") NIL >(NULL (cons nil nil)) NIL >() NIL // Let's practice CARs and CDRs. Note that the list argument is quoted. >(car '(1 2 3)) // A CAR of a list of atoms is an atom 1 >(cdr '(1 2 3)) // A CDR of a list is a list. More precisely, it's the cons cell that starts that list (2 3) >(cdr (cdr '(1 2 3))) (3) // <-- this is a cons cell with CAR of 3 and the CDR of nil // Let's walk these cons cells (see the ASCII art of cons cells above) >(car (cdr (cdr '(1 2 3)))) 3 >(car (cdr '(1 2 3))) 2 // There are even convenience functions for taking a few steps in sequence: >(cadr '(1 2 3)) 2 >(cddr '(1 2 3)) (3) >(caddr '(1 2 3)) 3 >(cadddr '(1 2 3 4 5 6 7 8 9)) 4 // But alas not CADDDDR with 4 Ds: >(caddddr '(1 2 3 4 5 6 7 8 9)) 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 CADDDDR: Undefined function: Broken at EVAL. Type :H for Help. 1 Return to top level. >>1 Top level. // Easy, we can DEFUN one ourselves. Remember what Alan Perlis wrote in his foreword to SICP: // a Lisp program is a living organism, we quickly create any functions we need, and they // immediately become parts of the environment: >(defun caddddr (x) (car (cdr (cdddr x)))) CADDDDR >(caddddr '(1 2 3 4 5 6 7 8 9)) 5 // We can now define functions on lists. So far you've seen no loops (unlike C, where // the loop was our starting example!). We don't need them either! // We assume the argument is a list, i.e., either a CONS or a NIL. In subsequent // strongly typed languages we will make this assumption explicit in the function // definition. >(defun len (x) (if (null x) 0 (+ 1 (len (cdr x))))) ^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^ base case, x is a CONS cell, x is () peel off 1 list element LEN >(len '()) 0 >(len '(1)) 1 >(len '(1 2)) 2 >(len '(1 2 3)) 3 >(len '(1 2 3 4)) 4 >(len '(1 2 3 4 5 3 3 4 6 8 3 2)) 12 ====== to be continued ========