LISP IntroductionLisp Data Structures/- numbers e.g., 16, 3.14, -3//- atoms-/ \/ \- symbols e.g., +, foo, appleS-EXPs /Expressions -(symbolic) \\\\- lists ( S-EXP )ATOMS LISTS----- -----3 (3)a (a b c)"hi there" (hi (there 3) a (b (c)))1Symbols and ListsWhen a symbol is introduced in Lisp, a structure is created in the Lispsymbol table. Every Lisp symbol has five parts:• print name• value• function definition• property list• packageLisp functions can be used to set, update, or extract these parts of asymbol.SymbolsIf you type a symbol into the interpreter, it will return the value of thesymbol (it returns the value of any expression you type in).If that symbol does not have a defined value, you will get an errormessage.> aFatal error in function SYSTEM::INTERPRET (signaled with ER-ROR). Symbol has no value: AThere are two special symbols, T and NIL, that have predefined values.All other symbols have no predefined value. t has the value T, nil has thevalue NIL (Lisp is not case-sensitive).> tT2> nilNIL> TT> 11> (1 2 3)ERRORExpressionsA LISP interpreter interprets each “expression” that is entered.If you type a symbol into the interpreter, it will return the value of thesymbol.If you type in an expression that begins with a ”(”, Lisp• evaluates the non-leading arguments (no guaranteed order),• looks up the function definition of the first argument (symbol), and• applies the function to the argumentsEvaluating Expressions in LISPPREFIX notation (Lisp): (operator arg1 arg2 ... argn)3INFIX notation (C, sometimes): arg1 operator arg2 operator ... opargnC is inconsistent. For built-in operators such as +, -, *, /, %, it usesinfix notation. For function calls, it uses prefix notation quicksort(array,size).LISP always uses infix notation. Furthermore, the syntax is(operator arg1 arg2 ... argn)and NOToperator(arg1, arg2, ..., argn)Evaluating Expressions in LISPWhenever the interpreter sees ”(”, it expects the next symbol to representa function name, and the following symbols to represent arguments upuntil the corresponding ”)”. The function name and all arguments areseparated by white space (blank, new line).(+ 1 2 3) -> 6(* 5 6) -> 30(- 6 5) -> 1(- 12 5 3) -> 4Function calls can be embedded inside other function calls.(+ 1 (* 2 3)) -> 7LISP evaluates each argument (the other is implementation-dependent),and then applies the function to the evaluated arguments.4(+ 5 (- 7 4) (* 2 1)) -> 10Whenever you enter an expression to the Lisp interpreter, theinterpreter EVALUATES the input and returns the value of the expression.ExamplesLet "<" represent our Lisp interpreter prompt.Assume that the symbol ’a has the value 3, and a function definition thatreturns the sum of its arguments.>a3>(a 1 2 3)6>(a a a 2)8QuoteSometimes we want to PREVENT evaluation of an expression. To do this,we can use the built-in function QUOTE. For example, we may want tobuild a list and not have the interpreter treat the list like a function call.(QUOTE x)This returns the print name x.5> (QUOTE a)A> (QUOTE t)T> (QUOTE hi)HI> (QUOTE (1 2 3 a b c))(1 2 3 A B C)> (1 2 3 a b c)ERRORWe will use QUOTE very often. Therefore, we will use a short-handrepresentation for QUOTE, that does the same thing. This is to just usethe quote symbol ’. We don’t need parentheses around the short-handversion.Examples>(a a a 2)8>’(a a a 2)(A A A 2)6Building and Manipulating Lists• One way to build a list: use QUOTE• Another way to build a list: use the LIST function(list a1a2· · · an) returns a list of the arguments Remember: thearguments are evaluated first!> (list 1 2 3)(1 2 3)> (list a b c)ERROR> (list 1 ’a 2 ’b)(1 A 2 B)> (list 1 (list 2 (list 3)))(1 (2 (3)))Building and Manipulating Lists• We can extract parts of a list using FIRST (or CAR) and REST (orCDR)FIRST returns the first element of a list (it may be an atom or a list).REST returns everything BUT the first element of the list. Almostas though we just cut out the first element.7> (first ’(a b c))A> (first ((((a))) ((b)) (c)))ERROR> (first ’((((a))) ((b)) (c)))(((A)))REST returns everything BUT the first element of the list.Almost as though we just cut out the first element.> (rest ’(a b c))(B C)> (rest ’((((a))) ((b)) (c)))(((b)) (c))Building and Manipulating Lists• How do our special symbols, T and NIL, fit in?T is an atom and not a list.NIL is both and atom AND a list. NIL is equivalent to the empty list.They can both be used as elements of a list.8Car and cdrOlder, equivalent terms to first and rest(developed for IBM 709, which had 2 registers)car (like first, Contents of Address Register)cdr (like rest, Contents of Decrement Register) +---+---+| * | * |+-|-+-|-+| |car cdrExamples>(first ’(a a a 2))A>(list a ’a a 2)(3 A 3 2)>(first (rest (list ’a ’a ’a 2)))A ; This looks like a "second" function!Conditionals• The most basic type of conditional is the IF function(IF condition9then-actionelse-action)The condition is evaluated. If the value is non-NIL (anything butNIL), then the then expression is evaluated and returned as the valueof the IF function.If the value of the condition is NIL, then the else expression is evalu-ated and returned as the value of the IF function.Remember, there is only one expression for then, and one for else.Conditionals• Easy condition functions for numbers:– (= x y) returns T if they are equal, returns NIL otherwise– (¿ x y) returns T if x ¿ y, returns NIL otherwise– (¡ x y) returns T if x ¡ y, returns NIL otherwise(if (= 1 (+ 2 3))(* 4 2)(/ 4 2))FunctionsThe command ”defun” stands for ”define function”. The format is asfollows:10(defun function-name (parameters)"comment describing this function"exp-1exp-2...exp2-n)When the function is called, the value returned for the function is thevalue returned by the last expression in the function.Example(define test (x y)"This is a sample function for class"(+ x (* 5 y)))>(test 3 5)28Example(define summation (x)"This function computes the summation of integers 1 to x."(if (= x 1)1(+ x (summation (- x 1)))))11ExampleNow write a recursive function that computes n!(defun factorial (n)(if (= n 1)1(* n (factorial (- n 1)))))List ManipulationCONS is a function that adds a new “first” item to a list.CONS takes two arguments (cons x y)The first of the new cell will be x, and the rest of the new cell will be y.(cons 3 ’(a b))(3 A B)The value of this expression is the NEW created list.(first (cons newitem list)) returns