LispVersions of LISPRecursionInformal SyntaxRecursive functionsT and NILPredicatesFunction calls and dataQuotingBasic FunctionsOther useful FunctionsCARCDRCDR examplesCONSCONS examplesDotted PairsEQATOMCONDSpecial formsForm of the CONDIFDefining FunctionsExample: MEMBERRules for RecursionGuidelines for Lisp FunctionsExample: UNIONStill more useful functionsPrograms on fileCommentsThe End1Lisp2Versions of LISP•Lisp is an old language with many variants–LISP is an acronym for List Processing language•Lisp is alive and well today•Most modern versions are based on Common Lisp•Scheme is one of the major variants–We will use Lisp, not Scheme, in this class•The essentials haven’t changed much3Recursion•Recursion is essential in Lisp•A recursive definition is a definition in which–certain things are specified as belonging to the category being defined, and–a rule or rules are given for building new things in the category from other things already known to be in the category.4Informal Syntax•An atom is either an integer or an identifier.•A list is a left parenthesis, followed by zero or more S-expressions, followed by a right parenthesis.•An S-expression is an atom or a list.•Example: (A (B 3) (C) ( ( ) ) )5Recursive functions•A recursive function is one that calls itself–the problem to be solved is broken into cases–the simplest (base) cases are solved without recursion–more complex cases require•some work done without recursion•recursion to solve a simpler, but similar, subproblem•combining the above to produce a result6T and NIL•NIL is the name of the empty list, ( )•As a test, NIL means “false”•T is usually used to mean “true,” but…•…anything that isn’t NIL is “true”•NIL is both an atom and a list–it’s defined this way, so just accept it7Predicates•A predicate (in any computer language) is a function that returns either “true” or “false”•In Lisp,–“false” is represented by NIL, or ()–“true” is represented by anything that isn’t NIL•Hence, a Lisp predicate returns either NIL or non- NIL–Predicates often return “true” values other than T, especially if the returned value might be useful8Function calls and data•A function call is written as a list–the first element is the name of the function–remaining elements are the arguments•Example: (F A B)–calls function F with arguments A and B•Data is written as atoms or lists•Example: (F A B) is a list of three elements–Do you see a problem here?9Quoting•Is (F A B) a call to F, or is it just data?•All literal data must be quoted (atoms, too)–Except NIL, which does not need to be quoted•(QUOTE (F A B)) is the list (F A B)–QUOTE is not a function, but a special form–The arguments to a special form are not evaluated•'(F A B) is another way to quote data–There is just one single quote at the beginning–It quotes one S-expression10Basic Functions•CAR returns the head of a list•CDR returns the tail of a list•CONS inserts a new head into a list•EQ compares two atoms for equality•ATOM tests if its argument is an atom11Other useful Functions•(NULL S) tests if S is the empty list•(LISTP S) tests if S is a list•LIST makes a list of its (evaluated) arguments–(LIST 'A '(B C) 'D) returns (A (B C) D)–(LIST (CDR '(A B)) 'C) returns ((B) C)•APPEND concatenates two lists–(APPEND '(A B) '((X) Y) ) returns (A B (X) Y)12CAR•The CAR of a list is the first thing in the list•CAR is only defined for nonempty listsIf L is Then (CAR L) is(A B C) A( (X Y) Z) (X Y)( ( ) ( ) ) ( )( ) undefined13CDR•The CDR of a list is what's left when you remove the CAR•CDR is only defined for nonempty lists•The CDR of a list is always a list14CDR examplesIf L is Then (CDR L) is(A B C) (B C)( (X Y) Z) (Z)( ( ) ( ) ) ( ( ) )( ) undefined(X) ( )15CONS•CONS takes two arguments–The first argument can be any S-expression–The second argument is usually a list•The result is a new list whose CAR is the first argument and whose CDR is the second•Just move one parenthesis to get the result:CONS of A ( B C ) gives ( A B C )16CONS examplesL (CAR L) (CDR L) (CONS (CAR L) (CDR L))(A B C) A (B C) (A B C)( (X Y) Z) (X Y) (Z) ( (X Y) Z)( ( ) ( ) ) ( ) ( ( ) ) ( ( ) ( ) )( ) undefined undefined undefined(X) X ( ) (X)•CONS puts together what CAR and CDR take apart17Dotted Pairs•The second argument to CONS can be:–A list: the result is always another list–An atom: the result is a dotted pair•CONS of A and B is (A . B)•We will be using dotted pairs in this class, but not in the first programming assignment•Dotted pairs will be discussed in more detail in a later lecture18EQ•EQ tests whether two atoms are equal–Integers are a kind of atom•EQ is undefined for lists–it might work for lists, it might not–but it won't give you an error message•As with any predicate, EQ returns either NIL or something that isn't NIL19ATOM•ATOM takes any S-expression as an argument•ATOM returns “true” if the argument you gave it is an atom•As with any predicate, ATOM returns either NIL or something that isn't NIL20COND•COND implements the if...then...elseif...then...elseif...then... control structure•The arguments to a function are evaluated before the function is called–This isn't what you want for COND•COND is a special form, not a function21Special forms•A special form is like a function, but it evaluates the arguments as it needs them•COND, QUOTE and DEFUN are special forms•Lisp lets you define your own special forms•We won't be defining special forms in this course22Form of the COND(COND (condition1 result1 ) (condition2 result2 ) . . . (T resultN ) )23IF•In addition to COND, Lisp has an IF statement that does much the same thing•Please do not use IF in your assignments–You need fewer parentheses with COND than with IF –I want you to get familiar with COND24Defining Functions•(DEFUN function_name parameter_list function_body )•Example: Test if the argument is the empty list•(DEFUN NULL (X) (COND (X NIL) (T T) ) )25Example: MEMBER•As an example we define MEMBER, which tests whether an atom is in a list of atoms•(DEFUN MEMBER (A LAT) (COND ((NULL LAT) NIL) ((EQ A (CAR LAT)) T) (T (MEMBER A (CDR LAT))) )
View Full Document
Unlocking...