The Little LISPer by Daniel P. Friedman WILLIAM GEAR: The Little LISPer is a nonprogrammed text for the nonprogrammer or programmer who likes the feature that books used to have-one can curl up (near the refrigerator) and read it from front to back for a pleasurable introduction to LISP and its ideas. Evaluate it--you’ll quote it. MARK ELSON: Dan Friedman’s LISP primer...provides by far the finest intro- duction to LISP that I have seen. Its excellence emanates along two different dimensions: (1) The question-answer technique is beautifully exploited...Friedman blends development and redundancy, which the student needs for recall and logical guesswork, very effectively. Delicious juicy carrots seem to dangle at every step. (2) The book has style, but that of course is not enough. The order of development of topics is what allows the style to be effective. Large languages can be tutorially developed from many different directions; LISP evolves so much power from so few basic features that a very delicate chain of development is necessary to bring comprehension and appreciation of that power. The LISPer achieves this admirably. In short, the book is excellent in both coverage and style, a self-sufficient intro- duction to LISP for any logical human being from 8 to 80. HAROLD STONE: The Little LISPer by Daniel Friedman...is both informative and enjoyable. It is an unusual book that definitely has a place in computer science education and should...find wide acceptance as a supplement to a programming languages course or a course on LISP. It does not serve as a reference manual...On the other hand, it has characteristics that no other text on LISP has. It explains the essential features of the language in a manner that is easily digested, and it is done at just the right level for reaching students. INDEX PRINCIPLES COMMANDMENTS Page Principle Principle Principle Principle Principle No. No. No. No. No. 1 2 3 4 5 2 2 3 4 5 Commandment Commandment Commandment Commandment Commandment Commandment Commandment Commandment No. No. No. No. No. No. No. No. FUNCTIONS Page Page ADDVEC AND 28 42 MATPLUS MAXVEC 53 32 APPEND ATOM 57 4 BUILD 48 9 43 56 54 38 37 CAR 2 MEMBER MEMBER* MINIVEC MINSMAT MULTIINSERTL MULTLINSERTR CARTES 54 MULTIREMBER 36 CDR CDRVEX 2 57 MULTISUBST 38 COMPLEMENT 48 NOT 40 3 NULL 4 DEPTH 57 OCCUR 38 DIFFERENCE DIMENSIONS DISTRIB DOESINTERSECT 27 53 57 47 OCCUR* ONEP ONE-TO-ONE OR 41 38 50 42 CONS EQ EQUAN 4 43 PICK PLUS 33 27 EQN 26 47 44 QUOTIENT 30 EXPT 33 RAC RDC 56 56 FIRST 48 REMAINDER 33 EQSET EQUAL REMBER 16 GREATERP 26 REMBER* 40 INSERTL 23 REMPICK REVLAT 35 51 INSERTL* INSERTR INSERTR* - INTERSECT INTERSECTALL 42 23 40 48 55 REVREL 48 SCALMAT SCALVEC SECOND 52 57 48 ISFUN 49 SMALL 56 ISLAT ISPALIN ISSET ISZEROMAT 6 51 46 52 SNOC SORTUP SUBSET SUBST 56 53 47 23 ISZEROVEC 57 SUBST* 41 LEFTMOSTAT 40 TIMES 28 LENGTH LESSP 33 33 TRANSPOSE 56 UNION 48 MAKALAT MAKAVEC 35 35 VECPLUS 31 MAKESET 46 1 2 3 4 5 6 7 8 The Little LISPer by Daniel P. Friedman Indiana University Bloomington, Indiana with Phillip S. Blackerby Robert J. King Abraham Goldberg David L. Walrath DEDICATION To Patrick Suppes for the hours of pleasure his book, Introduction to Logic, has made ACKNOWLEDGMENTS Many thanks to John McCarthy, Mike Greenawalt, David Musser, William Gear, Mark Elson, Harold Juny Armus, comments Bob Wesson, about The and Marylin Little LISPer. Sealy John Howard, Terry Pratt, Stone, Jonathan Slocun, for their Grateful extremely appreciation helpful to Ben Shneiderman and Steve Mitchell for believing in this unorthodox approach to LISP. Thank you to Bill Cohagan who taught me LISP and to Ann and Frances Patterson for their careful typing and proofreading of this manuscript. I am greatly indebted to Patrick Mahaffey for his futuristic ideas of teaching LISP to public affairs graduate students and to John Gronouski, Dean of the Lyndon Baines Johnson School of Public Affairs, who was persuaded to try the experiment. I want to thank the four public affairs graduate students, Phillip S. Blackerby, Robert J. King, David L. Walrath, and Abraham Goldberg who not only were students in the “quickie” course but also persevered with me an additional week for the completion of the first draft. I especially want to thank Abraham Goldberg who contributed his editing talents and novice perspective for that week. Above all, I want to thank my wife Mary for her understanding, encouragement, and concern for my well-being during the completion of this manuscript. © 1974, Science the Research Printed in United Library of Congress ISBN: 0-574-19165-8 Associates, States Catalog Inc.- All of America Card Number: rights ' 73-91284 reserved. possible. TABLE OF CONTENTS PREFACE iv INTRODUCTION 1. TOYS 2. DO IT, DO IT AGAIN, AND AGAIN AND AGAIN... 3. THE MIGHTY CONS 14 4. NUMBERS GAMES 25 5. THE MULTICHAPTER CHAPTER 36 6. *OH MY GAWD* 40 7. FRIENDS AND RELATIONS 46 8. "HELP" IS ON THE WAY, OR WELCOME TO THE HAMMOCK 51 CONCLUSIONS 58 REFERENCES 58 PREFACE The fundamental structure of the LISP programming: language was derived from the abstract notions of lambda calculus and recursive function theory by John McCarthy. His goal was to produce a programming language with a powerful notation for defining and transforming functions. Instead of operating on numeric quantities, LISP was designed to manipulate abstract symbols, called atoms, and combinations of Simultaneously, the increased number of students doing advanced work in computer science has focused academic interest on LISP. Courses on programming languages (such as I2 in the ACM Curriculum 68) have become the regular diet of undergraduate and graduate computer science majors. In these courses the goal was to teach the concepts of LISP in an organized and appealing manner. Unfortunately, the symbols, called lists. The expressive power of the language was recognized by a small number of researchers who were primarily concerned with difficult symbolic manipulation problems in artificial intelligence. The unorthodox nature of LISP contributed to the development of a narrow cult of LISP enthusiasts among the artificial intelligentsia. Aithough compilers for LISP were available available for a wide variety of computers, early com puter scientists were mainly concerned with the numbercrunching aspect of machines. More recently symbolic manipulation problems have risen in importance and the increased complexity of the problem solving tasks assigned to the computer has prompted widespread interest in LISP. texts required a great deal of tedious finger exercises before the meat of the course was accessible. Dan Friedman's Little LISPer provides a thoroughly palatable introduction to LISP with ‘the emphasis on the elusive, but profound, concepts. The reader is continually challenged and is highly motivated to read on until the controlled confusion is resolved. By encouraging discovery, the author ensures that the student's interest is always at its peak. Finally, by providing instant feedback, the student's mastery of the material is guaranteed. Ben Shneiderman Department of Computer Science State University of New York at Stony Brook INTRODUCTION At an undergraduate curriculum design meeting two or three years ago, a professor of numerical analysis, Dr. Richard Bartels, expressed this opinion: "A student with an undergraduate degree in Computer Science who has not learned LISP is culturally deprived." Currently LISP is employed in a major proportion of all artificial intelligence research: computational linguistics, robotics, pattern recognition, generalized problem solving, theorem proving, game playing, algebraic manipulation, etc. While artificial intelligence comprises only one area of computer science, it is nevertheless a major subfield. Moreover, there is hardly any area in computer science which has been unaffected by LISP. The Little LISPer is a programmed text based on lecture notes from a two-week "quickie" introduction to LISP for students with no previous programming experience and an admitted dislike for anything quantitative; many were preparing for careers in public affairs. The purpose of the course, and therefore of this book, is to teach the student how to think "recursively." "Writing programs recursively in LISP is pattern recognition." Our attempt is to verify this statement within the covers of this book. Since our only concern is recursive programming, our treatment is limited to the why's and wherefore's of a few LISP functions, specifically, CAR, CDR, CONS, EQ, ATOM, NULL, NUMERP, COND. The Little ZEROP, LISP. In fact, ADD1, LISPer SUB1, is not the formal AND, OR, a complete statement NOT, and book on of the defini- tion of these functions can be given on two pages. Hence our promise to you the reader is two pages fion and technique. GUIDELINES FOR THE READER You should not rush through this book. Read carefully, because valuable hints are scattered throughout the text. Do not read the book in less than three sittings unless you are already familiar with LISP but are not a "LIiSPer." Read systematically. If you do not fully understand one chapter, you will understand the next one even less. The problems are arranged according to their difficulty; it will be difficult to solve later ones before you have solved those previous. DO NOT HESITATE TO CUESS. “This book is based on intuition, and yours is as good as anyone's. We expect before expect you to guess. Occasionally we make you guess giving the answer, either because we do not you to know an answer at a particular stage, or because we want you, in case you guessed wrongly, to slow down and look back for what you missed earlier. “No formal definitions are given in this book. We believe that you can form your own definitions and will thus remember them and understand them better than if we had written each one for you. But be sure you know and understand the Principles and Commandments thoroughly before passing them by. The key to learning LISP is "pattern recognition." The Commandments simply point out the patterns that you will have seen already. Early in the book, some concepts are narrowed for simplicity; later, they are expanded and qualified. You should also know that, while everything in the book is true LISP, LISP itself is more general and incorporates more than we could intelligibly cover in an introductory text. After you have mastered this book, you can read and understand the more advanced and complete books written on the subject.* We do.not tell you in this book how to get access to LISP on your local computer system or even suggest that you have a computer handy while you read it. If, however, you want to interact with a computer while you read, get in touch with the systems personnel at your local computation center. They will be happy to show you the procedures that are specific to their LISP. In spite of local variations, however, LISP is LISP and is basically the same throughout the world. Food appears in many of our examples for two reasons. First, food is easier to visualize than abstract symbols. (This book is not good to read while dieting.) We hope the choice of food will help you understand the examples and concepts we use. Second, we want to provide you with a little distraction. We know how frustrating the subject matter can be, and a little distraction will help you keep your sanity. DO _NOT GIVE UP EASILY. LISP operates on the "lightning principle." The concepts of LISP will strike you suddenly when you are almost ready to give up. Once you have been struck, everything will fall into place. Be sure you understand chapters 2 and 8. Once you fully understand the concepts of "Do it, do it again, and again, and again..."" and " 'Help' is on the way" or "Welcome to the hammock," you understand most of LISP. So you are ready to start. Good luck! We hope your brain will enjoy the exercises waiting for it on the following pages. Bon _appétit! *See references at the end of the book. CHAPTER Is it true ATOM that Is it true TURKEY that Is it true that this this this is an atom? TOYS Yes, because ATOM with an A. is an atom? is an atom? Is it true L is a string a letter. since 1492 is a string with a digit. Note: Numbers are not Is it true that 3TURKEYS this that this of characters beginning of characters No, is an atom? No, since with 1.5) is a string Yes, because TURKEY beginning with 1492 1.4) 1; is an atom? 3TURKEYS a digit. Yes, because of characters atoms is a string L is a string beginning yet. of characters of --one-- beginning characters beginning with a letter. 1.6) Is it true that this is a list? Yes > (ATOM) 1.7) because Is it true that this is'a list? (ATOM TURKEY (ATOM) is an atom enclosed by parentheses. Yes, OR) because it is a collection parentheses. of atoms enclosed by 1.8) Is it true that this is a list? (ATOM TURKEY) OR No, since this is only two S-expressions not enclosed by parentheses. The first one is a list containing two. atoms, and the second one is an atom. 1.9) Is it true that this is a list? ((ATOM TURKEY) OR) Yes, because the two by parentheses. Is it true XYZ Yes, because all Yes, because it is a list. 1.10) 1.11) 1.12) 1.13) 1.14) that this Is it true that (X ¥ 2) this Is it true this Is that is an S-expression? is an S-expression? is an S-expression? atoms are it true that this is a list? (HOW ARE YOU DOING SO FAR) Yes, because it is a collection enclosed by parentheses. are in the list SO FAR) 1.16) How many S-expressions are in the list (((HOW) ARE) ((YOU) (DOING SO)) FAR) and what are they? 3 ((HOW) Is it true Yes, () that this is a list? all lists 6 HOW, ARE, Is it true that this is a list? (((HOW) ARE) ( (YOU) (DOING SO)) FAR) enclosed Yes, because How many S-expressions (HOW ARE YOU DOING and what are they? are now S-expressions. ((X Y) Z) 1.15) 1.17) S-expressions YOU, are DOING, S-expressions. SO, and FAR. Yes, because it is a collection enclosed by parentheses. because ARE), of S-expressions of S~expressions, ((YOU) (DOING SO)), and FAR. it is a collection of zero S-expressions enclosed by parentheses. This special S-expression is called the null list. 1.18) Is it true that this €¢)6)90) is a list? Yes, 0)) because it is a collection of S-expressions i 1.19) What enclosed is the CAR of L, where L is the argument A> (A BC) 1.20) 1.21) 1.22) What What because A is the first atom of this non-null is the CAR of L, where L is the argument (A BC) ((A BC) because (A B C) is the first this non-null list. XY 2) is the CAR of L, where HOTDOG What L is the argument No answer, since you cannot ask for the CAR of an atom. No answer, since you cannot ask for the CAR of the null list. No. 1 CAR is only defined is the CAR of L, where for lists. L is the argument ((CHOTDOGS)) (AND) (PICKLE) ((HOTDOGS)) --Read RELISH) as: composed "The list of the list of the because ((HOTDOGS)) is the of this non-null list. 1.24) What is (CAR L), where L is the (CC(HOTDOGS) ) (AND) (PICKLE) 1.25) What of is the CAR of L, where L is the argument non-null What S-expression list. ¢) PRINCIPLE 1.23) by parentheses. is (CAR (CAR L)), where argument atom first HOTDOGS ean S-expression (CHOTDOGS)) RELISH) L is the argument (HOTDOGS) of -L, where L is the (BC), because is pronounced "couder". ((CHOTDOGS) ) (AND) ) 1.26) What is the CDR (A BC) Note: "CDR" 1.27) What 1.28) What argument is the CDR of L, where L is the argument ((A BC) XY Z) is (CDR L), where (B C) is the list L, without (CAR L). (YZ). L is the argument (TR), ((X) T R) since (CDR L) is just another way to ask for "The CDR of the list L". 1.29) 1.30) What What is (CDR A), where HOTDOGS A is the argument ’ No answer, since you cannot ask is L is the argument No answer, since you cannot ask for the CDR of the null (CDR L), where PRINCIPLE No. the CDR of an atom. 2 CDR is only defined for non-null the CDR of any is always list for lists; another list. 1.31) What is (CAR (CDR L)), where L is the argument (XY), ((B) & ¥)C(C))) because ((X Y)((C))) the of CAR (CDR L). is (CDR L), and (X Y) is list. 1.32) What is (CDR (CDR L)), where L is the argument €((C))), ((B)(KX Y)C(C))) 1.33) What is (CDR (CAR L)), where (A (B (C)) D) L is the argument because ((X Y)((C))) the of CDR is (CDR L), and (((C))) is (CDR L). No answer, since (CAR L) is an atom, _ an atom for an argument; and CDR wiil not take see 2. PRINCIPLE 1.34) What does (CAR L) take as an argument? (CAR L) takes any non-null list 1.35) What (CDR L) take as (CDR L) takes any non-null list as 1.36) What 1.37) 1.38) does as its argument, argument, (PEANUT because list. What is the CONS of S and L, where S is (MAYONNAISE AND), and ((MAYONNAISE because CONS AND) PEANUT BUTTER AND JELLY), sticks any S-expression onto the L is front list. What (PEANUT is (CONS BUTTER AND S L), where ((HELP) L is (IS VERY THIS), does 1.40) What is (CONS S L), where S is (AB (C)), and What () is (CONS the (((HELP) THIS) IS VERY ((HARD) front of a TO LEARN)). ((HARD) TO LEARN)) What CONS of the and 1.39) Lis JELLY) BUTTER AND JELLY) CONS sticks an atom onto its is the CONS of the atom A and the list L, where A is the argument PEANUT, and L is the argument (BUTTER AND JELLY) This can alternatively be asked (CONS A L), Read: "CONS the atom A onto the list L." S is 1.41) an argument? No. take as its arguments? (CONS S L) takes two arguments: the first one, S, is any S-expression; the second one, L, is any list. ((A B (C))), since ( ) is a list. S L), where (A) S is A, and L is 1.42) What () is (CONS S L), where S is (A B (C)), and tro answer, since the second argument, L, must be a list. L is B 1.43) What is (CONS S L), where S is A, and == tio answer, why? L is B PRINCIPLE No. 3 The second argument be a list, and the result of (CONS S L) must must also be a list. 1.44) What is (CONS S (CAR L)), where S is A, and L is ((B) C ¢C) (A B), why? 1.45) What is (CONS S (CDR L)), where S is A, and L is €(B) C D)- (ACD), why? Tha actual LISP systems (CONS S A) where A is any atom is well you from thinking about CONSing something onto an atom. defined. Our 4htention is to prevent L. L. 1.46) Is it true that the list, L, is the null Lis ( )? This question is alternatively list, where Yes, because read it is the list composed of zero S-expressions. as: (NULL L). 1.47) Is (NULL L) true, L is the 1.48) Is (NULL L) true, Lis or false, argument where False, (A B C) or false, because where because No. (NULL _L) is only for Is it true, or false, S is the argument that S is an atom, HARRY 1.51) Is Is (ATOM S) true, or false, where atom. HARRY is a string of characters beginning a letter. True, (ATOM S) true, or false, where S is (HARRY HAD A HEAP OF APPLES) Faise, since the argument, does ATOM 1.53) Is (ATOM (CAR L)) true, or false, L is (HARRY (ATOM (CDR L)) L is (HARRY Is (ATOM L is (CAR HAD A HEAP true HAD LOW take? or false, where L is (SWING (LOW SWEET) see where argument, intention which (CAR L) is HARRY, PRINCIPLE is to prevent ts any S-expression. and HARRY is an atom. No. 2. true, because or false, where (CDR L) (CDR L)) is (LOW SWEET is LOW, which CHERRY), and is an atom, False, CHERRY) because (CAR True or false: Al and A2 are Al is HARRY, and The False, CHERRY) ‘Is (ATOM (CAR (CDR L))) true, S, is a list. defined. one "Is True, where or false, takes because OF APPLES) true, SWEET is well ATOM OF APPLES) A HEAP (CDR L))) (SWING S-expression aton. (CAR 1.57) L) of an since (ATOM S) is just another way to ask: it true, or false, that S is an atom?" arguments they? 1.56) (NULL defined True, because where How many What are 1.55) ask S is HARRY 1.52) Is cannot lists. tha actual LISP systems (NULL S) where S is any you from thinking about (NULL A) where A is an 1.54) you 4 with 1.50) list. tyo answer, A PRINCIPLE 1.49) it is a non-null (CDR L) is True, because (EQ Al A2) is just another way “Are Al and A2 the same atom?" to ask: where False, since the arguments True, because (LOW SWEET), which and where and where is CHERRY), a list. atom, L)) ((LOW SWEET) is the same (CDR both Al and A2 are HARRY. A2 is HARRY 1.58) Is (EQ Al A2) true, or false, Al is the argument HARRY, A2 is the argument 1.59) Is HARRY (EQ Al A2) true, or false, Al is MARGARINE, and A2 Al and A2 are different atoms. is BUTTER 1.60) How many 1.61) Is arguments does EQ take, (EQ AL) true, or false, A is STRAWBERRY, and L is (STRAWBERRY) where and what are they? EQ takes two arguments, No answer, since néither argument both of which must of EQ can be a list. be atoms. PRINCIPLE (EQ Al A2) takes Both arguments of the atoms, 1.62) Is (EQ (CAR L) A) true, or false, where L is (MARY HAD A LITTLE LAMB CHOP), which Is (EQ (CDR L) A) true, L is (SOURED MILK), or false, and two 5 arguments. must begin with be letters. True, because (CAR L) is the atom MARY, argument A is also the atom MARY. and A is MARY 1.63) No. where No answer, See PRINCIPLES Nos. and the 2 and 5. A is MILK 1.64) Is (EQ (CAR L)(CAR (CDR L))) true, or false, where L is (BEANS BEANS ARE GOOD FOR YOUR HEART) Now go make yourself a PEANUT BUTTER True, This compares list. AND JELLY the first and second atoms space reserved for SANDWICH. This JELLY STAINS! in the CHAPTER 2: 2.1) 2.2) 2.3) True, or L is false: (ISLAT L), where (JACK SPRAT COULD EAT NO CHICKEN True, or false: (ISLAT L), where L is ((JACK) SPRAT COULD EAT True, because S-expression in L is an atom. FAT) since True, or false: (ISLAT L), where L is (JACK (SPRAT COULD) EAT NO CHICKEN FAT) False, since one of the S-expressions (ISLAT L), where 2.5) True, a LAT is a list or false: This help CDR, is the of the NULL, CONS, NULL, ATOM, function (ISLAT functions, CAR, CDR, and of atoms. and What in L is a list. with the LAT . is a list, but not every list relationships. question. Good True. The function (BACON (ISLAT AND the value Go on to the next luck. L), where L is EGGS) T --true-- because L is a LAT. (CDR L))) > »)) is the value of (ISLAT L), where L is the argument (BACON AND EGGS)? 2.8) How do you arrive at function (ISLAT L)? 2.9) What is the 2.10) What is the meaning ((NULL L) T), where L is first the answer question of the asked T for the by line (BACON AND EGGS) 2.11) What is the next 2.12) What is the meaning of the line ((ATOM (CAR L))(ISLAT (CDR L))), where L is What a list. necessary ATOM: ((ATOM (CAR L))(ISLAT is We did not expect you to know this, but we wanted you to realize that you are still missing some has (T F) L) True. Note: Every is a LAT. EQ. L), defined (ISLAT (LAMBDA (L) (COND ((NULL L) T) (CAR True, é because ( ) contains no lists, and because it does not contain any lists, it must be a LAT. Write the function (ISLAT L), using some, but not necessarily all, of the following functions: CAR, 2.13) each CHICKEN True, or false: Lis ( ) 2.7) FAT) . . False, NO 2.4) 2.6) DO IT, DO IT AGAIN, AND AGAIN, AND AGAIN. (BACON question? AND EGGS) is the meaning of (ISLAT (CDR L))? (ISLAT We don't expect you to know this one, either. ‘The answer is arrived at through asking the questions of (ISLAT L). HINT: Write down the function (ISLAT L) and refer to it for the next group of questions. L)? (NULL L) Note: "(COND" is only a necessary stem that you will have to learn to live with. Similarly, "(LAMBDA" is a necessary part of the scenery, but for our purposes, it is as useful as a screen door on a submarine sandwich. (NULL L) asks if the argument L is the null list. If it is, then the value of the function is T. If it is not, then we ask the next question. In this case, L is not the null list, so we ask the next question. (ATOM (CAR L)) (ATOM (CAR L)) asks if the first S-expression of the list, L, is an atom. If (CAR L) is an atom, then we want to know if the rest of L is also composed only of atoms. If (CAR L) is not an atom, then we ask the next question. In this case, (CAR L) is an atom, so the value of the function is (ISLAT (CDR L)). (ISLAT (CDR L)) finds out if the rest of the list, L, is composed only of atoms, by referring us back to the original function, but now with a new argument. 2.14) Now, what 2.15) What is the next 2.16) What is the meaning ((NULL L) T) is the argument, L, for ISLAT? Now the argument, (AND EGGS). question? 2.17) 2.18) What of the line Pe In this case, L is not the next question. question Ee pe What is the meaning ((ATOM that must be asked? ie OE of the line (CAR L))(ISLAT (CDR L))) (ATOM (CAR L)) (ATOM (CAR L)) asks if the null list, (AND EGGS)? so we ask (CAR L) is an atom. If it is an atom, then the value (ISLAT (CDR L)). where L is is (NULL L) asks if the argument, L, is the null list. If it is, then the value of the function is T. If it is not, then we ask the next question. (AND EGGS) is the next REE (CDR L), which (NULL L). where L is now L, is of the function If it is not an atom, then we ask the next question. In this case, (CAR L) is an atom, we want to find out if the rest of the. list, is composed only of atoms. so L, 2.19) What is the meaning of (ISLAT (CDR L)) (ISLAT (CDR L)) finds out if the rest of L is composed only of atoms, by referring us back again to the original function, (ISLAT L), but this time, with the argument (CDR L), which is (EGGS) . 2.20) What is the next (NULL L) 2.21) What is the meaning ((NULL L) T) where L is now question? of the line (NULL L) asks if the argument, L, is the null list. If it is, the value of the function is T -~ true. If it is not, then move to the next question. In this case, L is not null, so we ask the next question. (EGGS) 2.22) What is the next 2.23) What is the meaning of the line ((ATOM (CAR L))(ISLAT (CDR L))) (ATOM (CAR L)) asks if (CAR L) is an atom. If it is, then the value of the function is L is now If (CAR L) is not an atom, then ask the next question. In this case, (CAR L) is an atom, once again we look at (ISLAT (CDR L)). question that must be asked? (ATOM where What is the meaning 2.25) Now, what 2.26) What is the meaning ((NULL L) T) is the of (ISLAT argument of the for L is now (ISLAT L)? ISLAT? () line (NULL L) asks if the argument, L, is the null list. If it is, then the value of the function is T. If it is not the null list, then we ask the next question. In this case, ( ) is the null list. Therefore, the value of the function (ISLAT L), where L is (BACON AND EGGS), is T, or true. the problem about Probably not. The function (ISLAT L) has a value of T if the list, L, is a list (BACON AND EGGS). 2.28) Can you describe what in your own words? so (ISLAT (CDR L)) finds out if the rest of the list, L, is composed only of atoms, by referring us back to the original function, (ISLAT L), with L replaced by (CDR L). ( ) Do you remember (CDR L)). (CDR L))? where 2.27) (CAR L)) (ISLAT (EGGS) 2.24) is the function ISLAT does, of atoms, where L is Here are our words: "ISLAT looks at each S-expression, in turn, and asks if each S-expression is an atom, until it runs out of S-expressions. When it runs out without encountering a list, the function's value is T. As soon as it finds a list, the function value is F --false. To see how we could arrive at a value of "faise", consider the next few questions." 2.29) This is the (ISLAT function (LAMBDA (ISLAT L), again: : (L) False, since the list L contains ts a list. an S-expression that (COND ((NULL L) T) ((ATOM (CAR L)) (ISLAT (CDR L))) (T F) >)» What is the value L is now of (BACON 2.30) What is the first 2.31) What is the meaning (ISLAT L), where (AND EGGS) )? question to be asked? of the line (NULL L) asks (QNULL L) T) where L is 2.32) What 2.33) What (BACON is the next question: of the (CAR L)) (ISLAT 2.34) What {ATOM (CAR L)) line (ATOM (CAR L)) (CDR L))) If it is, the value : (BACON (ISLAT (AND EGGS)) What is the meaning of (ISLAT (CDR L))? is the meaning of the line. ((AND EGGS)) What is the next 2.37) What is the meaning of the line ((ATOM (CAR L))CISLAT (CDR L))) question? What is the next 2.39) What is the meaning 2.40) Is T true? (CDR if to (ISLAT L) with if L is the null the value of the function list. is T. (CAR L)) T of the question, T?. : T asks if T is true. Yes, the question T is always 2.41) T T 2.42) Why is T the last question? Because we do not need 2.43) What T asks if T is true. of the L replacedby (CDR L). (ATOM (CAR L)) asks if (CAR L) is an atom. If it is, then the value of the function is (ISLAT (CDR L)). If it is not, then we move to the next question. In this case, (CAR L) is not an atom, so we ask the next question. question? is the meaning is L)). (NULL L) asks because (T F) (CAR L) is an atom. of the function If it is null, (ATOM ((AND EGGS)) 2.38) asks If it is not null, we ask the next question. In this case, L is not null, so move to the next question. 2.36) where L is now If CISLAT (CDR L)) checks to see if the rest of. the list, L, is composed only of atoms, by referring CQNULL L) T) where L is now is T. Tf it is not, we ask the next question. In this case, (CAR L) is an atom, so we want to check if the rest of the list, L, is composed only of atoms. us back 2.35) list. L is not null, then move to the next question. In this case, it is not null, so we ask the next question. (AND EGGS)) where L is if L is the null If it is, the value of the function is the meaning ((ATOM (NULL L) line If T is true --as of the function true! to ask any more questions. it always is-- then the value is F -- false. 2.44) What is the meaning > of the These are just the closing parentheses which match "(COND", "(LAMBDA", and "(ISLAT" at the beginning of the description of the function. We call these line » "aggravation parentheses", and they are always put at the end of a function. 2.45) Can you describe (ISLAT how we arrived at the value F for L) where L is (BACON 2.46) Is it true, or (AND EGGS))? false, where that A is a member A is the argument TEA, and LAT is the argument (COFFEE 2.47) 2.48) Is (MEMBER A LAT) true, A is POACHED, LAT is (FRIED and EGGS This of LAT, ; is the function TEA OR MILK) or false, AND where SCRAMBLED. is the value of A is MEAT, and LAT is (MASHED 2.49) How do you arrive function? 2.50) What POTATOES AND at the value is the first question (MEMBER A LAT) MEAT What (MASHED POTATOES T for the above asked by atoms of the LAT. MEAT is one POTATOES of the AND MEAT atoms of GRAVY). The value is arrived at by asking the questions about (MEMBER A LAT). HINT: Write down the function (MEMBER A LAT), and refer to it while you work on the next group of questions. (NULL LAT) Note: (ISLAT This L). No. is also always ask NULL as the first question any in describing the first question asked by 1 Thou shalt AND MEAT the GRAVY) function. (NULL LAT) asks if the LAT is the null list. If it is, then the value of the function is F, false, since the atom MEAT was not found in the where is of where is the meaning of the line ((NULL LAT) F) LAT one True; because the atom the LAT, (MASHED COMMANDMENT 2.51) of the atoms of the LAT TEA OR MILK) as the atom A, TEA. EGGS) (MEMBER A LAT): (MEMBER A LAT), True, because one (COFFEE is the same False, since A is not (MEMBER (LAMBDA (A LAT) (COND ((NULL LAT) F) ((EQ (CAR LAT) A) T) (TZ (MEMBER A (CDR LAT))) >» What Here is one way to say it: “(ISLAT L) looks at each S-expression in its argument, to see if it is an atom. If it runs out of S-expressions before it finds a list, the value of (ISLAT L) is T. If it finds a list, as it did in the example (BACON (AND EGGS)), the value of (ISLAT L) is F," GRAVY) LAT. If it is not, then we ask the next question. In this case, it is not null, so we ask the next question. 2.52) What 2.53) What is the next (EQ (CAR LAT) A) question? is the meaning of the line ((EQ (CAR LAT) A) T) where A is MEAT, and LAT is (MASHED POTATOES AND MEAT GRAVY) (EQ (CAR LAT) A) asks if the CAR of LAT is the same as the atom A. If it is, then the value of the function is T. If it is not, then we ask the next question. In this case, it is not, so we ask the next question. 2.54) What 2.55) Is T really 2.56) Give is the next What tr a question? an example is contained 2.57) question? Yes, T is a question whose of a question to which the answer Here's in the question. is the meaning of the line Now is always true. ours: "What (T (MEMBER A (CDR LAT))) answer color is an orange?" that we know that we know that atom A, we want as the LAT is not the CAR of LAT is not to find out null, and the same if the atom A is somewhere in the rest of the LAT. The function does this by referring us back to the original function, with the argument LAT replaced by (CDR LAT). 2.58) 2.59) What are What the arguments is the next for MEMBER now? question? A is MEAT, and LAT (CDR is now LAT) -- (POTATOES (NULL LAT). Remember COMMANDMENT No. 17 2.60) Is 2.61) What 2.62) What is the next question? (EQ (CAR LAT) A). 2.63) What F -- 2.64) What do we do now? Ask the next 2.65) What is the next T 2.66) What is T? 2.67) What (NULL LAT) true, or false, where LAT is (POTATOES AND MEAT GRAVY) do we do now? is (EQ (CAR LAT) A), where A is MEAT, and LAT is (POTATOES AND MEAT GRAVY) question? of the line What are the arguments of MEMBER What is the next 2.70) What do we question. true. now? A is MEAT, question? is if A is a member us back to and (AND MEAT Ask the next since GRAVY). question, (NULL LAT) is false. 2.71) What is the next 2.72) What do we do now? Ask the next question, 2.73) What is the next question? T 2.74) What is the value of the line (MEMBER A (CDR LAT)) 2.75) What do we do now? Recurse -- refer new arguments. 2.76) What are A is MEAT, and LAT is (MEAT GRAVY) the new out (NULL LAT) do now? question? finds of the CDR of the LAT, by referring the original function. LAT 2.69) question. (MEMBER A (CDR LAT)) ? GRAVY). false. T -- is the meaning MEAT false. Ask the next (T (MEMBER A (CDR LAT))) 2.68) F -- AND 4 (EQ arguments? 10 (CAR LAT) A) to the origina] function, with 2.77) What is the next 2.78) What do we (NULL LAT) question? Ask the next do now? since 2.79) What 2.80) What is the next question? is the value of the What T, line is the value of the function (MEMBER A LAT) where A is MEAT, and LAT is (MEAT GRAVY) 2.82) What is the value (MEMBER of the is false. (EQ (CAR LAT) A) ((EQ (CAR LAT) A) T) 2.81) question, (NULL LAT) function A LAT) where because (CAR LAT), is MEAT, are the which same is MEAT, and A, which atom. T, because we have now of (MEAT GRAVY). found T, because MEAT (AND MEAT a member is also GRAVY). that MEAT is a member of the LAT A is MEAT, and LAT is (AND MEAT GRAVY) 4 2.83) What is the value of the (MEMBER A LAT)- where A is MEAT, and LAT is (POTATOES 2.84) What is the value (MEMBER function because MEAT is also a member of (POTATOES AND MEAT GRAVY). AND MEAT of the T, 2.85) is function T, because A LAT) and (MASHED POTATOES LAT GRAVY) where A is MEAT, LAT the MEAT (MASHED Of course, AND MEAT GRAVY) LAT. Just to make sure you have it right, run through it again quickly: What is the value of let's T. is also POTATOES a member of the LAT AND GRAVY). you noticed MEAT that this is our original HINT: Write down the function MEMBER and its arguments and refer to them as you go through the next bunch of questions. (MEMBER (LAMBDA (A LAT) (COND (QNULL LAT) F) ((EQ (CAR LAT) A) T) (7 (MEMBER A (CDR LAT))) ») » where A is MEAT, LAT 2.86) 2.87) 2.88) 2.89) is and (MASHED POTATOES AND MEAT GRAVY) (NULL LAT) No, (EQ (CAR LAT) A) T move to the next line. No, move to the line. Yes, recurse with A and (CDR LAT), where A is MEAT and (CDR LAT) is (POTATOES AND MEAT (NULL LAT) No, move 2.90) (EQ (CAR LAT) A) to the next line. to the next line. No, move 2.91) next Yes, recurse with A and A is MEAT, and | (CDR 11 LAT) is (CDR LAT), (AND MEAT where GRAVY) GRAVY). 2.92) (NULL LAT) No, move 2.93) (EQ (CAR LAT) A) line. to the next line. No, move 2.94) to the next T Yes, recurse with A and A is MEAT, and (CDR LAT) 2.95) (NULL LAT) No, move (CDR LAT), i is (MEAT to the next line. where GRAVY) 4 2.96) (EQ (CAR LAT) A) Yes, the value 2.97) What is the value of (MEMBER A is MEAT, and LAT is (MEAT GRAVY) A LAT), where T 2.98) What is the value of A is MEAT, and (MEMBER A LAT), where T LAT GRAVY) is the value of (MEMBER A LAT), A is MEAT, and LAT is (POTATOES AND MEAT GRAVY) where T is the value where T 2.99) What 2.100) What is (AND MEAT A is MEAT, LAT 2.101) What is is the value 2.102) is (MEMBER A LAT), (T sometimes (MASHED A is LIVER, LAT of and POTATOES AND MEAT GRAVY) of (MEMBER A LAT), where and (BAGELS (NULL LAT) appears as NIL) (EQ (CAR LAT) A) to the next line. to the next line. No, T Yes, with A and A is LIVER, (CDR LAT) (NULL LAT) (EQ (CAR LAT) A) is (AND next line. to the next line. T to the move Yes, recurse with A and A is LIVER, (CDR LAT) 2.108) (NULL LAT) (EQ (CAR LAT) A) T is (LOX) to the next line. to line. No, move 2.110) (CDR LAT), where and No, move 2.109) LOX) No, 7 2.107) (CDR LAT), where and No, move 2.106) as *T*). No, recurse 2.105) is T. LOX) move 2.104) appears (F sometimes AND function F move 2.103) of this Yes, recurse the next with A and A is LIVER, and (CDR LAT) is (CDR LAT), ( ) where 2.111) (NULL LAT) 2.112) What Yes. is the value of A is LIVER, and (MEMBER A LAT), where F of (MEMBER A LAT), where F LAT is ( ) 2.113) What is the value A is LIVER, and LAT is (LOX) 2.114) What is the value of A is LIVER, and LAT is (AND LOX) (MEMBER A LAT), where F 2.115) What is the value of A is LIVER, and (MEMBER A LAT), where F LAT is (BAGELS AND LOX) 13 CHAPTER 3.1) What is (REMBER A is MINT, LAT is A LAT), 3: THE MIGHTY where and (LAMB CHOPS AND MINT CONS (LAMB CHOPS REMBER stands AND JELLY) for REMove the memBER. JELLY) 3.2) (REMBER A LAT), where A is MINT, and LAT is (LAMB CHOPS AND MINT FLAVORED MINT JELLY) (LAMB CHOPS AND FLAVORED MINT JELLY) 3.3) (REMBER A LAT), where A is TOAST, and LAT is (BACON LETTUCE (BACON LETTUCE AND TOMATO) AND TOMATO) 3.4) (REMBER A LAT), where A is CUP, and LAT is (COFFEE CUP TEA CUP AND HICK CUP) (COFFEE 3.5) What does (REMBER A LAT) It takes an atom and a LAT as its arguments, and makes a new LAT with the first occurrence of the atom in the old LAT removed. 3.6) What steps will we use do? to do this? First, TEA CUP AND HICK CUP) we will will want 3.7) How do we ask if A is the same 3.8) What would be the value of (REMBER A LAT) A is the same as (CAR LAT)? 3.9) What 3.16) How do we of LAT? 3.11) Let do we do if A is not find out us now use the write the function the as same (CAR LAT)? A with a list, (CAR LAT). from left We to right. A) (CDR LAT) (CAR LAT)? We will want to keep (CAR LAT), but also find out if A is somewhere in the rest of the LAT. if A is somewhere in the rest (REMBER A (CDR LAT)) ideas far, to developed as (EQ (CAR LAT) if compare to build so REMBER: Obviously, Now, we have rewrite forgotten (REMBER COMMANDMENT No. 1! A LAT). (REMBER (LAMBDA (A LAT) (COND ((EQ (CAR LAT) A) (CDR LAT)) (tT (REMBER A (CDR LAT))) » »)) 3.12) What is missing Now, we think from here? that (REMBER (LAMBDA (COND this is the function REMBER: (A LAT) (LETTUCE AND TOMATO) HINT: Write down the function REMBER and its arguments, and refer to them as you go through the next sequence of questions. ((NULL LAT) ( )) ((EQ (CAR LAT) A)(CDR LAT)) ' (T (REMBER A (CDR LAT) )) ») »)) What is the value of (REMBER A LAT), where A is BACON, and LAT is (BACON LETTUCE AND TOMATO) 3.13) Now, What let's see if this function works. is the first question? (NULL LAT) 3.14) What do we Move do now? to the next line and ask the next question. 3.15) (EQ (CAR LAT) A) Yes, so the value of the function In this case, it is the list (LETTUCE 3.16) 3.17) Is this But the correct did we really value use of the function? Yes, because without a good example? Who But does (REMBER A LAT) 3.19) What steps will we 3.20) What is the value of (REMBER A LAT), where A is AND, and LAT is (BACON LETTUCE AND TOMATO) 3.21) Let us see if this function works. What is the first question asked by REMBER? (NULL LAT) 3.22) What Move 3.23) (EQ (CAR LAT) A) It takes an atom and a LAT as its arguments, and makes a new LAT with the first occurrence of the atom in the old LAT removed. to do this? First, we will compare each atom of the LAT with the atom A. Second, we want to build a list from left to right. (BACON LETTUCE ’ do now? What 3.26) is the meaning (T of the line (REMBER A (CDR LAT))) 3.27) What 3.28) (NULL LAT) to the next 3.30) What Is this of the line (REMBER A (CDR LAT))) the next question. and is (LETTUCE to the next line. No, so move to the next line. AND TOMATO) Recurse, where A is AND, and (CDR LAT) is (AND TOMATO) A) is the value (REMBER ask line. No, so move No, so move (EQ (CAR LAT) 3.31) A) is the meaning (tT 3.29) and T asks if T is true -- as it always is -- and the rest of the line says to recurse with A and (CDR LAT), where (NULL LAT) (EQ (CAR LAT) line, No, A is AND, (CDR LAT) 3.25) TOMATO) to the next so move 3.24) list of the pudding is in the eating, try another example. What do we TOMATO) knows? the proof 3.18) use (CDR LAT). the above list is the original the atom BACON. so let's do? AND is to the next line, and ask the next question. Yes, of the function (CDR LAT) -- (TOMATO). (TOMATO) is not A LAT) correct? No, since (BACON with 3.32) What 3.33) How can we keep from losing BACON and LETTUCE? did we do wrong? only A --AND-~ We dropped preceeding the atoms LETTUCE AND the list TOMATO) removed. AND, but we also AND. lost We use CONS "The Magnificent". Remember CONS, from Chapter One? 15 all the atoms COMMANDMENT Thou 3.34) Let's shalt use CONS No. 2 to build lists. (BACON LETTUCE just see what happens when we use CONS: TOMATO) Make a copy of this function with CONS and the arguments A and LAT, so you can refer to it for the following questions. (REMBER (LAMBDA (A LAT) (COND ((NULL LAT)( )) ((EQ (CAR LAT) A)(CDR LAT)) (T (CONS (CAR LAT) (REMBER A (CDR LAT)))) ») Now, what is the value of (REMBER A LAT), where A is AND, and LAT is (BACON 3.35) What is the 3.36) What do we do now? 3.37) first (EQ (CAR LAT) LETTUCE AND TOMATO) (NULL LAT) question? A) Move to the next next question. What is the meaning (T (CONS (CAR where A is AND, and LAT is (BACON of the function and ask the : No, so move 3.38) line of the A LETTUCE TOMATO) AND line. CONS (CAR LAT) --BACON-~ onto the value of (REMBER A (CDR LAT)). But since we don't know the value of (REMBER A (CDR LAT)) yet, we will have to find this value before we can CONS (CAR LAT) onto it. line LAT) (REMBER to the next (CDR LAT)))) 16 Draw a picture of "CONS The Magnificent" on this page. 3.39) What is the meaning of (REMBER A (CDR LAT)) This with refers us back to the original function, LAT replaced by (CDR LAT) -- (LETTUCE AND TOMATO) . 3.40) (NULL LAT) No, so move (£Q (CAR LAT) A) 3.41) What is the meaning (T (CONS line. to line. No, so 3.42) to the next of the line move CONS (CAR LAT) (REMBER A (CDR LAT)))) the next (CAR LAT) --LETTUCE-- to find that value onto our list. 3.43) What is the meaning 3.44) (NULL LAT) onto the value of (REMBER A (CDR LAT)). But since we don't know that value, of (REMBER A (CDR LAT))? before we can we will have CONS (CAR LAT) This refers us back to the original function with LAT replaced by (CDR LAT) -- (AND TOMATO). No, so move 3.45) (EQ (CAR LAT) 3.46) What A) to the next line. Yes. is the value of the line (CDR LAT) -- (TOMATO). Certainly not! So far we know what (CEQ (CAR LAT) A) (CDR LAT)) 3.47) Are we finished? is (AND TOMATO), is when LETTUCE 3.48) We now have a value where A is AND, and for (REMBER (CDR LAT) is (AND TOMATO) This value is (TOMATO). This value, so what must we do? 3.49) What is the result (TOMATO) when 3.50) What does TOMATO) (LETTUCE we A (CDR LAT)), is not CONS the LETTUCE LAT AND is when LAT but we don't yet know what (REMBER it is (LETTUCE TOMATO). A LAT) AND TOMATO) or (BACON Recall that we wanted to CONS LETTUCE onto the value of (REMBER A (CDR LAT)), where A was AND, and (CDR LAT) was (AND TOMATO). Now that we have this value, which LETTUCE onto this steps. final onto (LETTUCE represent? is (TOMATO), we can CONS value. Reread the last six TOMATO) It represents when A was AND, the value of (REMBER A (CDR LAT)). and (CDR LAT) was (AND TOMATO) 3.51) Are we finished yet? Not quite. So far we know what LAT is (LETTUCE but we don't LAT 3.52) is (REMBER A LAT) AND yet know what (BACON LETTUCE it is when AND TOMATO) We now have a value for (REMBER A (CDR LAT)) when A was AND, and (CDR LAT) was (LETTUCE AND TOMATO). This value was (LETTUCE TOMATO). This is not Recall that, at one time, we wanted to CONS BACON onto the value of (REMBER A (CDR LAT)), when A was AND, and (CDR LAT) was (LETTUCE AND TOMATO) the Now final value, so what must we do again? we that we have this value, which (LETTUCE TOMATO) , can CONS BACON onto this value. 7 3.53) is when TOMATO), What is the result when we (LETTUCE TOMATO) CONS BACON onto (BACON 18 LETTUCE TOMATO) is 3.54) What does (BACON LETTUCE TOMATO) represent? It represents the value of (CONS (CAR LAT) (REMBER A was AND, A (CDR LAT))), when (REMBER 3.55) Are we 3.56) Can you put in your own words at the final value (BACON LETTUCE TOMATO) finished yet? A and (CDR LAT)) was (LETTUCE TOMATO) Yes. how we arrived In our words: "REMBER checked each atom of the LAT, one at a time, to see if it was the same as the atom AND. If the CAR was not the same as the atom, we saved it to be CONS'd to the final value later. When REMBER found the atom AND, it dropped it, and CONS'd the previous atoms onto the rest of the LAT, in reverse order." 3.57) What is the (REMBER value (LAMBDA of the function (A LAT) (COND C(QNULL LAT) ( )) (BACON HINT: LETTUCE TOMATO) Write down the function arguments and refer the next sequence REMBER and its to them as you go through of questions. €(EQ (CAR LAT) A) (CDR LAT)) (T (CONS (CAR LAT) (REMBER A (CDR LAT)))) >») where A is AND, LAT is and (BACON 3.58) (NULL LAT) 3.59) (EQ (CAR LAT) 3.60) Tt LETTUCE AND TOMATO) No. A) No. T’ so 3.61) What is the meaning of ‘(CONS (CAR LAT) (REMBER A (CDR LAT))) the value is (CONS (CAR LAT) (REMBER This says to refer back to the original function REMBER, but with the argument LAT replaced by (CDR LAT), and that after we arrived at a value for (REMBER A (CDR LAT)) --BACON-~ onto it. 3.62) (NULL LAT) No. 3.63) (EQ (CAR LAT) A) No. 3.64) T T is the meaning (CONS of the value This (CAR LAT) (REMBER A (CDR LAT))) LAT) (REMBER 3.66) (NULL LAT) No. 3.67) (EQ (CAR LAT) A) Yes. 3.68) What 3.69) Now what? line (CAR LAT) recurse (CDR LAT) (CDR LAT))) to the original function argument LAT (CDR LAT), after we arrive at a value -- back A the with (REMBER A (CDR LAT)), --LETTUCE-- onto it. of the CONS is (CAR says we REMBER, and that is the value will = (CONS What we > so 3.65) A (CDR LAT))) replaced we will CONS by for (CAR LAT) (TOMATO) CONS (CAR LAT) answer #3.60 --LETTUCE-- forming onto (LETTUCE (TOMATO) TOMATO). --see 3.70) Now what? CONS (CAR LAT) see answer 3.71) Now ai we have completed REMBER, example: try this --BACON-- #3.64 (REMBER A LAT) onto forming is (LETTUCE TOMATO) (BACON LETTUCE (SOY. AND TOMATO -- TOMATO). SAUCE) (REMBER A LAT), where A is SAUCE, LAT is (SOY and SAUCE is L), where —_— 3.72) What (FIRSTS L is ((APPLE PEACH AND TOMATO SAUCE) (APPLE PUMPKIN) (PLUM PEAR PLUM GRAPE BEAN) CHERRY) (GRAPE RAISIN PEA) (BEAN CARROT EGGPLANT)) eee 3.73) What is (FIRSTS L is L), where ((A B)(C D)(E (A C EB) F)) se 3.74) What is (FIRSTS Lis () L), where ¢) "=" 3.75) What is (FIRSTS L), where L is 3.76) Tn your ((FIVE (FIVE FOUR ELEVEN) PLUMS) (FOUR) (ELEVEN GREEN own words, what does (FIRSTS ORANGES) ) L) do? We tried the following: "FIRSTS takes one argument, a list, which must either be a null list, or contain one or more It builds another list composed non-null lists. of the first S-expression SS i 3.77) See if you can write the functions Remember the COMMANDMENTS! FIRSTS. Believe it or not, following: you (FIRSTS (LAMBDA (COND (L) ((NULL L) ) (T (CONS list." of each internal eee can probably (FIRSTS write the (CDR L)))) >») 3.78) Why (FIRSTS (LAMBDA (L)? Because we "(LAMBDA", 3.79) Why (COND ? 3.80) Why ((NULL 3.81) Why (T ? 3.82) Why (CONS 3.83) Why (FIRSTS 3.85) Why ) then state the L) 7? COMMANDMENT No. function, the arguments Because it is a necessary and must always be used. part then of the function. of the function, 1. Because the last line always begins with The reason for this is clarified as more examples are considered. ? Because (CDR L)) ? )) ? Keeping in mind the definition of (FIRSTS L), what is a typical element of the value of (FIRSTS L), where L is ((A B)(C D)(E F)) we are building No. Because we can only look at one S-expression at In order a list (T. --COMMANDMENT atime. 3.84) always to do this, we must recurse. Because these are the matching parentheses for (COND and the first line, and they always at the end of a function definition. appear A 2. 3.86) 3.87) What is another Suppose typical there was a function What would be a typical of (SECONDS L), where Lis element? C, or E. (SECONDS L). element B, or D, or F. of the value ((A B)(C D)(E F)) 3.88) How do we describe (FIRSTS L) 3.89) As we find what do we a typical a typical element do with it? element of for (FIRSTS By taking the CAR of See Chapter 1. L), We CONS COMMANDMENT 3.90) 3.91) From COMMANDMENT No. 3, we line look like now? What does this function of the function (FIRSTS L). (FIRSTS (LAMBDA (COND ((NULL L) (T (CONS Thou shalt need only describe always CONS it onto the realize the No. when first building typical natural recursion. You have just read THE mast in this book. Please read it again. can fill in more a list, element, fi -~ (CAR L)). (FIRSTS (CDR L)). (CAR thou then statement (CAR L)) (FIRSTS (CDR L)))) ELEMENT RECURSION TYPICAL NATURAL (L) Nothing yet. We are still missing in our recipe. The one important ingredient line ((NULL L) ) needs a value for where ) We can, however, (CAR (CAR do? recursion and important (fT (CONS What does the last the (CAR 3 NOTE: now it onto (CAR L) -- L)) (FIRSTS (CDR the case L is the null proceed without list. it for now. L)))) ») »)) where Lis 3.92) ((A B)(C D)(E F)). (NULL L), where L is 3.93) What No, ((A B)(C D)(E F)) is the meaning (T (CONS (CAR so move of the line (CAR L)) (FIRSTS It saves (CDR L)))) when we (NULL L), where L is ((C D) 3.95) What 3.96) (NULL L), where Lis ((E F)) 3.97) 3.98) it (CAR finds recurse with 3.94) to the next to the new line. (CAR L)) to CONS it onto that value. To the original function, argument find (FIRSTS (FIRSTS (CDR L)), (CDR (FIRSTS L), L)), (CDR L). No, F)) is the meaning of the so move line Save to the next (CAR (CAR L)), line. and recurse with (FIRSTS (CDR L)). and recurse with (FIRSTS (CDR L)). (T (CONS (CAR (CAR L)) (FIRSTS (CDR L)))) What is the meaning of the line (T (CONS (CAR (CAR L)) (FIRSTS No, so move Save (CDR L)))) (NULL L) Yes, 21 ta the next (CAR (CAR L)), line. 3.99) Now, what is the value of the line There is no value; something is missing. ((NULL L) »/ ee 3.100) What do we need to CONS atoms onto? A list. Remember es PRINCIPLE No. 3 -- see Chapter 1. a 3.101) What value can we give the function in the that (NULL L) is true, for the purpose of CONSing? case Since the final value must be a list, use T or F as our value, so how about we cannot ( )? nD 3.102) With ( ) as a value, we now have three CONS steps (ACE). ‘to go back and pick up. I. We need to: or, alternatively, II. We need or, alternatively, III. We need In any 3.103) case, to: to: what With which of the most comfortable? 1. CONS E onto ( ). 2. 3. CONS CONS C onto A onto the value the value of 1. of 2. 1. 2. 3. CONS CONS CONS A onto C onto E onto the value the value ( ). of 2. of 3. CONS A onto the CONS of C onto the CONS of E onto ( ). is the final value of (FIRSTS three alternatives are you L) ? Correct! Now you use that one, 3.104) (ICE CREAM WITH OLD NEW LAT), where (INSERTR OLD is FUDGE NEW is TOPPING, and LAT is (ICE CREAM WITH FUDGE FOR DESSERT) eS FUDGE 3.105) (INSERTR OLD NEW LAT), where OLD is AND NEW is JALAPENO, and LAT is (TACOS TAMALES AND SALSA) 3.106) (INSERTR Re 3.107) 3.108) 2 ASR a OLD NEW LAT), OLD is NEW is E, and LAT is if you FOR DESSERT) (TACOS TAMALES AND JALAPENO SALSA) (ABCDEFGD&#) where D (A BC DF GD H) In our own words: the atoms OLD and NEW, "Tt needs three arguments: and a LAT. INSERTR builds a LAT with NEW inserted In your own words, what does (INSERTR OLD NEW LAT) do? See TOPPING can write (INSERTR OLD NEW the to the right of the first occurrence (INSERTR function LAT). (LAMBDA of OLD." (OLD NEW LAT) (COND ((NULL LAT)( )) ((EQ (CAR LAT) OLD) (T (CONS (CAR LAT) (INSERTR OLD NEW (CDR LAT)) (CDR LAT)))) ») If you were unable to write this much, you should review the PRINCIPLES and COMMANDMENTS. 3.109) What is the value OLD NEW LAT 3.110) is is is of the INSERTR we just wrote, FUDGE TOPPING, and (ICE CREAM WITH FUDGE FOR (ICE CREAM WITH FOR DESSERT) where DESSERT) Notice that so far, this is the same as REMBER; but for (INSERTR OLD NEW LAT), what do we do, When (CAR LAT) is the same insert NEW to the right. as OLD, we want where (EQ (CAR LAT) OLD) is true? ono —— OT ——_ ———————_———— SS 22 to 3.111) How is this done? a 3.112) Now we have Let's try CONS NEW onto (CDR LAT). (ICE CREAM WITH TOPPING FOR DESSERT) (INSERTR (LAMBDA (OLD NEW LAT) (COND ((NULL LAT)( )) ((EQ (CAR LAT) OLD) (T (CONS (CAR LAT) (INSERTR What 3.113) (CONS NEW (CDR LAT))) OLD NEW (CDR LAT)))) is (INSERTR OLD NEW LAT), where OLD is FUDGE NEW is TOPPING, and LAT is (ICE CREAM WITH FUDGE FOR DESSERT) Is this the list we wanted? No, we have only replaced 3.114) What still needs 3.115) How can we include 3.116) Now you should be able to write the function (INSERTR OLD NEW LAT) Do to be done? FUDGE with TOPPING. Somehow we need to include the same as OLD before the OLD before NEW? the atom which atom NEW. is Try CONSing OLD onto , (CONS NEW (CDR LAT)) the rest CINSERTR (LAMBDA (OLD NEW LAT) (COND ((NULL LAT)( )) of it. (CEQ (CAR LAT) OLD) (CONS OLD (CONS (T (CONS (CAR LAT) (INSERTR OLD NEW » Notice that, where OLD NEW (CDR LAT)))) (CDR LAT)))) )) is FUDGE, NEW is TOPPING, and LAT is (ICE CREAM WITH FUDGE FOR DESSERT), value of the (ICE If you 3.117) This of the CINSERTL first occurrence of the atom OLD. CREAM got Now try (INSERTL OLD NEW LAT). HINT: INSERTL inserts the atom NEW to the left function much WITH this FUDGE right, is trivial (LAMBDA the is TOPPING have -- FOR DESSERT). one. right? (OLD NEW LAT) (COND ((NULL LAT)( )). ({EQ (CAR LAT) OLD) (CONS NEW (CONS (CAR LAT) (CDR LAT)))) (T (CONS (CAR LAT) (INSERTL OLD NEW (CDR LAT)))) )_»)) 3.118) Did you think of a different way to do that? For example, ((EQ or even better, ((EQ since 3.119) Now try to write (SUBST OLD NEW LAT). HINT: NEW (SUBST OLD LAT) replaces the (ICE CREAM WITH TOPPING FOR line like (CAR LAT) (CONS OLD could OLD) (CONS have been: NEW (CONS OLD (CDR LAT)))) this: OLD) (CONS (CDR LAT)) NEW LAT)), is the same as LAT. Obviously: first occurrence of OLD in the LAT with the atom NEW. For example, where OLD is FUDGE NEW is TOPPING, and LAT is (ICE CREAM WITH FUDGE FOR DESSERT), the value is Now you have this (CAR LAT) (SUBST (LAMBDA (OLD NEW LAT) (COND (NULL LAT) ( )) ((EQ (CAR LAT) OLD) (CONS NEW (CDR LAT))) (T (CONS (CAR LAT) (SUBST OLD NEW (CDR LAT)))) ) » DESSERT) the idea. Notice at 23 that INSERTR. this is the same as our second attempt Now go CONS a piece of cake into your mouth. CHAPTER 4.1) Is 14 an atom? 4: NUMBERS GAMES Yes, it is, because we are expanding to include all numbers. the value of ATOM i 4.2) 4.3) Is (ATOM N) true Nis 14 or T> because false where 14 is an atom. This extends definition of what an atom can be. Is -3 a number? No, since 4.4) Is 3.1415 a number? negative 4.6) Are ~3 and What is 3.1415 (ADD1 values are not considered here. considered here. No, since 4.5) the numbers available in LISP only whole Yes, howéver, N), where 68 is (SUB1 N), where Nis 5 4 numbers only whole are numbers are considered here. N is 67 4.7) What 4.8) Is (ZEROP N) true, Nis 0 or false, where T. 4.9) Is (ZEROP N) true, N is 1492 or where F. 4.10) Can you write false, a function (GREATERP (ZEROP N), (ADDI N), and (SUB1 N)? (GREATERP Nl N2), Nl is 12, and N2 is 11, has where Nl is 6, and Nl N2), using where the value How about: (GREATERP (LAMBDA T: N2 is 45, has the value F. 4.11) Did we just violate (Ni N2) (COND ((ZEROP N2) T) ((ZEROP N1) F) (Tf (GREATERP (SUB1 ) COMMANDMENT No. 1? Yes, however, we can treat tests if a number list is empty. 4.12) Is the way we wrote (GREATERP Nl N2) correct? 4.14) 4.15) ZEROP NULL is empty like and NULL NI and N2 are No, so move to the next question. (ZEROP Ni), where Nl is 3, and N2 is 3 No, so move to the next question. What is the meaning (ZEROP N2), where Nl is 2, and N2 is 2 of the line (SUB1 N1)(SUB1 N2))) Recurse, but with both the arguments No, so move since tests to the next question. ZEROP if a the same Let Nl and N2 be 3. (ZEROP N2), where Nl is 3, and N2 is 3 (Tf (GREATERP 4.16) N2))) No; try it for the case where number. 4.13) N1) (SUB1 »)) reduced by one. 4.17) 4.18) 4.19) 4.20) (ZEROP Nl), where Nl is 2, and N2 is 2 No, so. move What Recurse, but with both is the meaning of the line (Tf (GREATERP (SUB1 N1)(SUB1 N2))) (ZEROP N2), where Nl is 1, and N2 is 1 No, so move (ZEROP Nl), where No, Ni is 1, and N2 is 1 4.21) What so move is the meaning (T (GREATERP 4.22) 4,23) 4,24) of the line question. arguments closer to the next question. to the next question. to zero by one. Recurse, (SUB1 N1)(SUB1 N2))) but with (ZEROP N2), where Nl is 0, and N2 is 0 Is this to the next both Yes,so the value correct? arguments closer to zero by one. of (GREATERP Ni N2) is T. because 3 is not greater than Switch the ZEROP statements, that is: No, What can we do to the function (GREATERP to take care of this subtle mistake? Ni N2) 3. : (GREATERP (LAMBDA (COND ((ZEROP N1) (Nl N2) F) ((ZEROP N2) T) (T (GREATERP (SUB1 N1)(SUB1 N2))) ))) 4.25) 4.26) True or false: atoms where Nl is 1492 N2 is 1492 Is (EQ Nl N2) Nl is the N2 is the Nl and N2 are the same numeric True, because both true or false, where argument 1492 and argument 1492 4.28) Is (EQN N1 N2) true or false, where Ni is the argument 1492 and N2 is the argument 1492 Can you write the function (ZEROP N), (ADDL N) (EQN Ni N2), where N1 is 12 and 4.29) and (EQN N1 N2), (SUB1 N2 is 12 has where Nl is 13 and N2 is 12 has the value T; the value F. What unusual is somewhat about using (EQN N)? What is Nl N2 4.31) What (DIFFERENCE Nl N2), line atom 1492. similarly extended. to ask (N1 N2) N2)(ZEROP N1) F) N1)) (SUB1 N1)(SUB1 ») ») N2))) Here, we ask if N2 is 0; if it is, then the value of EQN is True if Nl is 0 and False if Nl is not 0. In other words, we answered a question with a question. where 5 Nl N2), where 8 is 8, and is 3 is (DIFFERENCE Ni is 17, and N2 is 9 (LAMBDA (COND ((ZEROP ((ZEROP (T (EQN the EQ has not been True, because (EQN Nl N2) is just another way if Nl and N2 are the same numeric atom. ((ZEROP N2)(ZEROP N1)) 4.30) the numeric No answer, because EQ is only defined for literal atoms. Althouth the definition of atom has been extended, the function 4.27) Nl and N2 are and 26 4.32) Try to write HINT: Use (DIFFERENCE Nil N2) How about this: (SUB1 N). (DIFFERENCE (COND (LAMBDA (Nl N2) ((ZEROP N2) Ni) (T (DIFFERENCE (SUB1 N1) (SUB1 N2))) ) 4.33) Can you describe in your (DIFFERENCE N1 N2) own words how »)) It takes two numbers both of them by one, does what it does? Where Nl is 8, and as arguments, and reduces until the smaller --N2-- hits zero. When N2 hits zero, the function is the other number --3. value of the N2 is 5 4.34) 4.35) What What is (DIFFERENCE Nl is 3, and N2 is 8 would be a good value (DIFFERENCE N1.N2), where Nl N2 4.36) 4.37) Nl N2), where for you change DIFFERENCE the where case N2 is greater (DIFFERENCE case where Nl N2) N2 is greater to take care than to take of By including another ZEROP line (DIFFERENCE (LAMBDA (N1 N2) for M. N1? care of the than Nl. (COND ((ZEROP N2) N1) ((ZEROP N1) N2) (T (DIFFERENCE (SUB1 N1)(SUB1 4.38) What a number. There are a few alternatives: 1. O, since it is the smallest number, or 2. 5, This is the alternative we choose, because it is the difference between N1 and N2. . is 3, and is 8 How would Rewrite No answer, because (SUB1 N1), where Nl is 0 is not That is, -1 is not a number, here. is (PLUS Nl N2), where Nl is 46, and N2))) 58 N2 is 12 4.39) Try to write (PLUS N1 N2). HINT: It uses ZEROP, ADD], and {PLUS (LAMBDA (COND SUB1. ((ZEROP Ni) N2) d (T (PLUS (SUB1 Ni) (ADD1 N2))) >) Wasn't 4.40) Try to follow (N1 N2) (PLUS Nl N2), where Your that easy? answer should be 7. it is just vector. a list of atoms. Nl is 2, and N2 is 5 4.41) Is this a VEC? (1 28 4.42) No, xX 4 3) : ‘Is ‘this a VEC? Is this a VEC? (3 (7 4) 13 9) because it is a list of numbers. No, because it is not a list of numbers not 4,44) Is this VEC stands Yes, (2 11 3 79 47 6) 4.43) Note: a VEC? () Yes, ‘ it is a list of --zero-~ case is the null VEC. numbers. 4.45) What is (ADDVEC VEC), VEC is (3 5 2 7) where 17 4.46) What is (ADDVEC VEC), where VEC is (15 6 7 12 3) 43 27 -- (7 4) is This special a number. for 4.47) What does (ADDVEC VEC) do? It builds in the 4.48) What is the natural way to build numbers, just as CONS is the natural way to build lists? By using 4.49) When building lists with CONS, the value of the terminal condition is ( ). What should be the value of the terminal condition when building numbers? 0 4.50) What is the natural lists? terminal condition for (NULL L) 4.51) What terminal condition for is the natural 4.53) What to build a number from a list should the terminal condition is the terminal (ADDVEC VEC) line 4.54) What does CONS 4.55) What does (ADDVEC VEC) of line 4.57) What does of ((NULL do? What (ADDVEC CONS will (ADDVEC VEC) do? be the last (LAMBDA (VEC) (COND ((NULL VEC) ») »)) use line to build in the a number? function: 15 4.59) What is (TIMES Nl N2), Nl is 13, and N2 is 4 where 52 4.60) What does 4.61) What (TIMES Nl N2) do? is the terminal condition lists. a number by totaling PLUS, PLUS builds condition It builds for N1 N2) all the numbers numbers! (CAR LAT) (REMBER the A (CDR LAT)))) (ZEROP N2) is the terminal (TIMES N1 N2) up a number by adding Nl up N2 times. ((ZEROP N2) 0) . condition, must eventually be reduced to zero. function is used to do this? the terminal a VEC. (ZT (CONS Try to write )) is the 0) where 4.63) a ltst. (I (PLUS (CAR VEC) (ADDVEC (CDR VEC)))) Notice the similarity between this line, and last line of the function (REMBER A LAT): is (TIMES Nl N2), Nl is 5, and N2 is 3 Since is also 0) builds It uses because What 4.62) VEC) ADDVEC builds 4.58) (TIMES a VEC ((NULL VEC) 0), just as ((NULL L)( for lists. in 4.56) all the numbers PLUS. because When you want numbers, what look like? by totaling (NULL VEC), VECs? 4.52) a number VEC. N2 (SUB1 N2) What function (TIMES (LAMBDA (COND (N1 N2) ((ZEROP N2) 0) (T (PLUS Ni (TIMES Ni (SUB1 N2)))) 28 4.64) What is (TIMES N1 N2), where Nl is 12, and N2 is 3 4.65) (ZEROP 4.66) What 36, but let's follow through the see how we get this value. N2) is the meaning N1 of the line (TIMES N1 (SUB1 are the new arguments (TIMES Ni N2) It adds Nl --12---to N2)))) (TIMES What 4.68) (ZEROP N2) No. 4.69) What is the meaning of the line (T (PLUS N1 (TIMES N1 (SUB1 N2)))) It adds 4.70) What are Nl is 12, and the new arguments (TIMES of N1 4.67) (SUB1 the natural of Nl N2) N2 is Nl --12-- to (TIMES Ni (SUB1 N2)) (TIMES Nl (SUB1 N2)) 1. 4.72) What is the meaning of the line (Tf (PLUS Nl (TIMES N1 (SUB1 N2)))) It adds N1 --12-- to 4.73) What is the value of the ((ZEROP N2) 0) 0, because (ZEROP is now N2) No. 4.74) Are we 4.75) Why not? 4.76) What 4.77) What is (QUOTIENT Ni N2), Nl is 12, and N2 is 4 4.78) What is (REMAINDER Nl is 12, and N2 is 4 4.79) What finished line now? (QUOTIENT Nl is 7, and of the N2) true. No. Because is the value we still have three PLUS's to pick up. function? PLUS 12 to PLUS 12 to PLUS 12 to 0 --36. Notice that Nl has been PLUS'd N2 times. where 3 N1 N2), where 0 Nl N2), where 2 3 4.80) What is (REMAINDER Nl is 7, and N2 is 3 N1 N2), where 1 4.81) What is (QUOTIENT N1 N2), where N1 is 0, and N2 is 4 0 4.82) What is (REMAINDER Nl] N2), where Nl is 0, and N2 is 4 0 4.83) What is recursion: Nl is 12, and N2 is 2. (ZEROP (QUOTIENT N1 is N2 is time N2)) 4.71) N2 is one No. (T (PLUS is function Nl N2), where 0 3, and 7 4.84) What 4.85) Try to write the function (QUOTIENT N1 N2) is (REMAINDER Nl N2), Nl is 3, and N2 is 7 where 3 How about (QUOTIENT (COND (LAMBDA (N1 N2} ((ZEROP N1) 0) (T (ADD1 (QUOTIENT (DIFFERENCE Ni N2) N2))) )») 29 to 4.86) Does 4.87) (ZEROP N1) this work, where Nl is 5, and N2 is 2 Let's see. No, so move 4.88) What is the meaning of the line (T (ADDL (QUOTIENT (DIFFERENCE 4.89) What are the arguments of after we recursed once? 4.90) (ZEROP N1) We are adding (QUOTIENT Nl N2) N2))) (QUOTIENT to the next Nl N2), Nl N2)--, (T (ADD1 (QUOTIENT 4.92) What the 4.93) (ZEROP N1) (DIFFERENCE arguments of Nl N2) N2))) (QUOTIENT This N1 N2), now? to the next again adds line. one.to the natural (T (ADD1 (QUOTIENT 4.95) What the arguments 4.96) Is this what we wanted? (DIFFERENCE of Nl N2) N2))) (QUOTIENT This Nl N2), now? to the next again adds line. one to the recursion. Nl is 1 --(DIFFERENCE N2 is 2. No. Obviously, this will Nl N2)--, and never the terminal reach condition. 4.97) Do we need 4.98) When 4.99) So what 4.100) What should be the value condition is true? a different do we want terminal to stop is the correct condition? adding one terminal Yes. to the value? given when the a value terminal with COMMANDMENT No. a value with ADD] of the TIMES, VEC] VEC2), (3 6 9 11 4), and VEC2 is (8 5 2 0 7) N2 N1) 0 will not affect or PLUS, always building use 1 for the value of the 0 and 1 do not affect the of the function. with always consider ADD1. use line; when always final value When building first a value (_) for the value of line. When using ADD1, the terminal line value is 0. When using the terminal line value is 0. When using TIMES, the line where N1. because PLUS, When using CONS, is than 4 terminating line, the terminating (VECPLUS 0, because terminating CONS, N2 is greater (GREATERP 0 for the value VEC] When condition? When building is recursion. No, 4.94) What and Nl is 1, and N2 is 2. so move 4.101) recursion: N2) No, 4.91) are one to the natural (DIFFERENCE Nl N2) Nl is 3 --(DIFFERENCE N2 is 2. so move are line. terminal the terminal (11 value is 1. line value 11:11 «11 #11) is usually ( ). 4.102) What is (VECPLUS VEC1 VEC1 VEC2 is is does (VECPLUS VEC2), where (6 9) do? It adds the first number of VEC] to the first number in VEC2, then it adds the second number in VEC1 to the second number in VEC2, and so on, for the VECs of the same length. (2 3), and (4 6) 4.103) What 4.104) Can you write VEC] (VECPLUS VEC2) VEC] VEC2) ? (VECPLUS (LAMBDA (VECi VEC2) (COND ((NULL VECL)( )) (T (CONS (PLUS (CAR VEC1) (CAR VEC2))(VECPLUS (CDR VEC1) (CDR VEC2)))) > 4.105) What are the arguments of PLUS in the last line? 4.106) What are the of CONS in the last line? 4.107) What arguments is (VECPLUS VEC1 VEC2), VEC] is (3 7), and VEC2 is (4 6) 4.108) (NULL 4.109) (T (CONS (CAR VEC1) (PLUS where VEC1) (CAR VEC1) (CAR VEC2)) (VECPLUS Why does the natural recursion CDR of both arguments? 4.111) (NULL VEC1), where VEC] is now (7), VEC2 is now (6) (PLUS include VEC1) (CDR VEC2)). (7613), but let's see just how CONS the (CDR recursion: VEC1) (CDR VEC2)) Because the typical element of the final uses the CAR of both VECs, so now we are to consider the rest of both VECs. (CAR VEC1) (CAR VEC2)) (VECPLUS 4.114) What is the value of the line? 4.115) What is the value CONS of the function? 13 onto the natural recursion. q) (7 13), by CONSing problem (VECPLUS arises when VEC] VEC2), we want where to do through 7 onto the CONS of 13 onto which is wrong. (7 13 8 1) the function The final What trivial change can you make in the terminal condition line to get the correct final value? Change ((NULL VEC1)( )) to ((NULL VEC1) VEC2) 4.118) What No answer, since VEC2 4.119) 4.120) What What is do we where (4 6) need See to include (VECPLUS VEC1 VEC2) is the other terminal in our value should be with 4.117) is (VECPLUS VEC] VEC2), VEC] is (3 7 8 1), and ( ). When VEC1 eventually gets to be ( ), we quit, but that means the final value will be (7 13), is (3 7), and is (4 6 8 1) Try going arguments. VEC2 value ready Yes. . HINT: these the natural VEC1) (CDR VEC2)))) VEC1) VEC1 VEC2 7 onto No. (NULL What it works. and 4.113) 4.116) and (CDR (VECPLUS 4.110) (CDR (CAR VEC1) (CAR VEC2)), No. (PLUS (T (CONS (CAR VEC2) (VECPLUS (CDR VEC1) (CDR VEC2)))) 4.112) and »)) function PRINCIPLES Another line? ((NULL 31 F will become No.1 terminal VEC2) and null before No. condition. VEC1) 2. VEC1. 4.121) So now that we have expanded our definition so that VECPLUS works VECs, see if you can rewrite it. function for any two (VECPLUS (LAMBDA (VEC1 VEC2) (COND (QNULL VEC1) VEC2) ((NULL VEC2) VEC1) (T (CONS (PLUS (CAR VEC1) (CAR VEC2)) (VECPLUS (CDR VEC1) (CDR VEC2)))) 4.122) Does the matter? 4.123) What is (MAXVEC VEC), where VEC is (4 8 2 13 12) 13 4.124) What is (MAXVEC VEC), where VEC is (468 942 8 27 43) 942 4.125) What is 4> get order of the (MAXVEC VEC), two terminal conditions No. where VEC is (4) 4.126) in the idea? (MAXVEC (LAMBDA (VEC) (COND C(QNULL (CDR VEC)) (CAR VEC)) Can you write the function (MAXVEC VEC), which has as its final value the greatest number the VEC? ((GREATERP (T (MAXVEC (CAR VEC) (MAXVEC (CDR VEC))) (CDR VEC))) (CAR VEC)) )_)) This is the way we would write the it also could have been written as function, follows: but (MAXVEC (LAMBDA (VEC) (COND (CNULL (CDR VEC)) (CAR VEC)) ((GREATERP (CAR VEC) (CAR (CDR VEC))) (MAXVEC (CONS (CAR VEC)(CDR (CDR VEC))))) (Tf (MAXVEC (CDR VEC))) )») Try to follow through both ways until you are satisfied that you understand both of them. Use whichever makes more sense to you. 4.127) In the first (MAXVEC VEC) the meaning of the line ((GREATERP that we wrote, (CAR VEC) (MAXVEC what is (CDR VEC))) (CAR VEC)) ((GREATERP (CAR VEC) (MAXVEC (CDR VEC))) (CAR VEC)) asks if the first number in the VEC is greater than the biggest number in the rest of the VEC. If it is, then the first number is the one we want. 4.128) What 4.129) In the second (MAXVEC VEC) that we wrote, what is the meaning of the line ((GREATERP (CAR VEC) (CAR (CDR VEC))) (MAXVEC (CONS (CAR VEC) (CDR (CDR VEC))))) It means we ask if the first number is greater than the second number. If it is, we recurse after throwing away the second number. 4.130) How did we throw away (CONS 4.131) What would happen if we 4.132) is the meaning of the (T (MAXVEC (CDR VEC))) VEC is (6) How did we keep this the line second tried Since we know by now that the first number is not the greatest, then we throw it away, and start all over again. number? to do this where from ever happening? (CAR VEC) (CDR No answer. See PRINCIPLE The Go through VEC What 4.134) is the (MAXVEC VEC) both ways, VEC) where (4 9 13 2 13 12) answer? In the second final 4.135) is (MAXVEC VEC), which 13 is the (4 9 13 2 13 12) (MAXVEC VEC), which 13 is the (4 9 13 2 13 12) value? In the first final value? 2. terminal condition (NULL (CDR VEC)) instead of (NULL 4.133) No. (CDR VEC))) was 4.136) Now write (REMAINDER Nl N2) (REMAINDER (LAMBDA (Ni N2) (COND ((GREATERP N2 N1) N1) (T (REMAINDER (DIFFERENCE Nl N2) N2)) ) ») 4.137) What 4.138) (LESSP N1 N2), where Nl is 8, and N2 is 3 F 4.139) (LESSP Nl N2), where Nl is 6, and N2 is 6 F 4.140) Now is (LESSP Nl N2), Nl is 4, and N2 is 6 try to write where (LESSP T (LESSP (LAMBDA (N1 N2) N1 N2) (COND ((ZEROP N2) F) _ ((ZEROP N1) T) (T (LESSP (SUB1 N1)(SUB1 N2))) ) 4.141) (EXPT N1 N2), where Nl N2 is is 1 1, and 1 4.142) (EXPT Ni N2), where Ni is 2, and N2 is 3 8 4.143) (EXPT Nl N2), where Nl is 5, and N2 is 3 125 4.144) »)) Now write (EXPT Nl N2) HINT: See COMMANDMENT No. (EXPT (LAMBDA (COND 4. ((ZEROP (T (N1 N2) N2) 1) (TIMES Nl (EXPT N1 (SUB1 (CDR LAT)))) )_»)) 4.145) What is the value of (LENGTH LAT), where LAT 4.146) What is LAT 4.147) Now is (HOTDOGS WITH (LENGTH LAT), is (HAM AND try to write 6 MUSTARD SAUERKRAUT AND PICKLES) where CHEESE (LENGTH 5 ON RYE) LAT) (LENGTH (LAMBDA (LAT) (COND ((NULL LAT) 0) (T (ADD1 (LENGTH ) 4.148) What is (PICK N LAT), where Nis 4, and LAT 4.149) What is (LASAGNA SPAGHETTI MACARONI RAVIOLI MACARONI MEATBALL) is (PICK N LAT), where No answer. N is 0, and LAT is ( ) 4.150) Try to write (PICK N LAT) (PICK (LAMBDA (N LAT) (COND ((ZEROP (SUB1 N)) (CAR LAT)) (T (PICK (SUB1 N) (CDR LAT))) 33 N2)))) Wouldn't Don't a HAM AND CHEESE forget the mustard. ON RYE be good right now? 4.151) What is (REMPICK N is.3, and LAT *,.152) What is N LAT), (HOTDOGS is (REMPICK N is 0, and WITH where HOT (HOTDOGS WITH MUSTARD) MUSTARD) N LAT), where No answer. (REMPICK N LAT) (REMPICK (LAMBDA (N LAT) (COND ({ZEROP (SUB1 N)) (CDR LAT)) LAT is ( ) 4.153) Now try to write (T (CONS 4.154) Is (NUMBERP AT) true, or false, where (CAR LAT) (REMPICK (SUB1 N) (CDR LAT)))) F, AT is TOMATO 4.155) Is (NUMBERP AT) true, AT is 76 4.156) Can you write (NUMBERP A) which is True a numeric and False a literal atom or false, if A is where TT. if A is No, atom? this like ADD1, EQ and ATOM 4.157) Now using (NUMBERP AT), write a function (MAKALAT L), which gives a LAT as a final value, with all the numbers removed. For the 4.158) (MAKAVEC L), which gives a VEC ZEROP, CAR, CDR, (built-in) CONS, NULL function. (MAKALAT (LAMBDA (L) (COND (CNULL L)( )) example, where L is (5 PEARS 6 PRUNES 9 DATES) final value is (PEARS PRUNES DATES). Now write value. SUB1, is a primitive (CNUMBERP (CAR L)) (MAKALAT (CDR L))) (T (CONS (CAR L)(MAKALAT (CDR L)))) as a final (MAKAVEC (LAMBDA (COND (L) CQNULL L)( )) (C(NUMBERP (CAR L)) (CONS (T (MAKAVEC (CDR L))) ) 35 (CAR L)(MARKAVEC (CDR L)))) CHAPTER 5.1) Write the 5: THE MULTICHAPTER function CHAPTER (MEMBER (MEMBER A LAT) (LAMBDA (A LAT) (COND ((NULL LAT) F) ((EQ (CAR LAT) A) T) (T (MEMBER A (CDR LAT))) ) 5.2) Do you recall, MEMBER does. 5.3) Write the function (REMBER or can you see now, what »)) (MEMBER A LAT) checks each atom of the LAT to see if each is the same as the atom A. When it finds the first occurrence of A, it stops and gives a value of T, since A is a member of the LAT. (REMBER A LAT) (LAMBDA (A LAT) (COND ((NULL LAT)( )) (CEQ (CAR LAT) A) (CDR LAT)) (T (CONS (CAR LAT) (REMBER A (CDR LAT)))) ) 5.4) Do you REMBER recall, does? or can you see now, what (REMBER A LAT) looks at each atom see if it is equal to the atom A. REMBER saves the atom of the LAT to If it is not, and proceeds. When it finds the first occurrence of A, it stops and gives the value (CDR LAT), or the rest of the LAT, so that the final value is the same as the original LAT, but with only the first occurrence of A missing. Can you write a function called which gives as its final value occurrences HINT: What (EQ (MULTIREMBER of A removed? do we want as the value (CAR LAT) true? A) is Can you 5.7) (NULL 5.8) 5.9) (EQ see how MULTIREMBER does what is the meaning (CONS (CAR of the whole CUP) A A (CDR LAT))) (T A (CONS (CAR LAT) (MULTIREMBER (CDR LAT)))) ») b Notice that after the first occurrence of A, we now recurse with (MULTIREMBER A (CDR LAT)), in order to remove the other possible occurrences. The value for the function is (COFFEE TEA AND HICK). it does? Possibly not, so we will go through the steps necessary to arrive at the value (COFFEE TEA AND HICK). line LAT) (MULTIREMBER (A LAT) C(C(NULL LAT) ( )) (CEQ (CAR LAT) A) (MULTIREMBER )} A) (T (LAMBDA (COND LAT) (CAR LAT) What (MULTIREMBER when Consider the example where A is CUP, and LAT is (COFFEE CUP TEA CUP AND HICK 5.6) A LAT), the LAT with all No, so move to the next line. No, so move to the next line. Save (CDR LAT)))) (CAR LAT) to be CONS'd (MULTIREMBER A (CDR LAT)) (MULTIREMBER A (CDR LAT)). to the next onto Later. the value Now of find 5.10) (NULL LAT) No, so move 5.11) (EQ (CAR LAT) A) Yes, so forget (CAR LAT), and find (MULTIREMBER A (CDR LAT)). 5.12) (NULL No, so move to the next line. No, so move to the line. 5.13) (EQ LAT) (CAR LAT) A) 36 next line. 5.14) 5.15) 5.16) What is the meaning of the line (T (CONS (CAR LAT) (MULTIREMBER Save A (CDR LAT)))) (NULL LAT) No, so move (EQ (CAR LAT) A) 5.18) 5.19) 5.20) 5.21) 5.22) (NULL LAT) (EQ (CAR LAT) A) What is the meaning of the line (T (CONS (CAR LAT) (MULTIREMBER to be CONS'd to the next (CAR LAT), and No, so move to the next line. No, so move to the next line. (CAR LAT) --AND-- find (NULL No, so move to the next line. No, so move to the next line. Save A (CDR LAT)))) of LAT) A (CDR LAT)) (EQ (CAR LAT) A) to the next (NULL LAT) Are we value later. A (CDR LAT)). onto the value Now find later. Now find line. Yes, forget (CAR LAT), and find (MULTIREMBER A (CDR LAT)). Yes, so we have 5.26) find No, so 5.25) the Now (CAR LAT) --HICK-~ to be CONS'd onto the value (MULTIREMBER so move 5.24) onto (MULTIREMBER to be CONS'd (MULTIREMBER A (CDR LAT)). 5.23) later. line. of (MULTIREMBER A (CDR LAT)) (MULTIREMBER A (CDR LAT)). (EQ (CAR LAT) A) is the meaning of the line (Tf (CONS (CAR LAT) (MULTIREMBER forget Save A (CDR LAT)))) (NULL LAT) What -TEA- Yes, so 5.17) (CAR LAT) of (MULTIREMBER A (CDR LAT)) (MULTIREMBER A (CDR LAT)). finished? a value of ( ). No, since we still have several operations to pick up. 5.27) What do we do next? CONS onto the most ( ). recent 5.28) What do we do next? CONS AND onto (HICK). 5.29) What do we do next? CONS TEA onto (AND HICK). 5.30) What do we do next? CONS COFFEE 5.31) Are we 5.32) Now can you write finished now? (MULTIINSERTR Yes. onto saved up CONS (CAR LAT) we have --HICK-- (TEA AND HICK). = (MULTLINSERTR (LAMBDA (OLD NEW LAT) (COND ((NULL LAT) ( )) ((EQ (CAR LAT) OLD) (CONS (CAR LAT) (CONS NEW (MULTLINSERTR OLD NEW (CDR LAT))))) (T (CONS (CAR LAT) (MULTIINSERTR OLD NEW (CDR LAT)))) a function OLD NEW LAT) Try it. Note: place 37 It would also be correct to use of the underlined (CAR LAT). OLD in 5.33) Now try to write the function (MULTIINSERTL OLD NEW (MULTIINSERTL (COND LAT) (LAMBDA (OLD NEW LAT) (QNULL LAT)( )) ((EQ (CAR LAT) OLD) (CONS NEW (CONS (CAR LAT) (MULTIINSERTL OLD NEW (CDR LAT))))) (Tf (CONS (CAR LAT) (MULTIINSERTL OLD NEW (CDR LAT)))) Note: 5.34) Is this function sea asi ((NULL defined (LAMBDA correctly? (OLD NEW LAT) It would also be correct of the underlined (CAR LAT), Not quite. To find out why, go through OLD is FISH LAT) ( )) NEW is FRIED, to use OLD the function, in place where and LAT is (FISH AND CHIPS OR FISH AND FRIES) ((EQ (CAR LAT) OLD) (CONS NEW (MULTIINSERTL OLD NEW LAT))) (T (CONS (CAR LAT) (MULTIINSERTL OLD NEW (CDR LAT)))) 2 5.35) Was the terminal condition ever reached? No, because COMMANDMENT Thou shalt The changing endeavor condition(s) but 5.36) Now write (MULTISUBST OLD to argument and it change at should be should CDR with NULL SUB1 with ZEROP CONS with NULL ADDI with ZEROP be you never No. 5 least one the tested one changed argument to be while in the closer get past the first occurrence of OLD. recursing. termination to termination, e.g., and not (MULTISUBST (COND NEW LAT) (LAMBDA (OLD NEW LAT) CQNULL LAT) ( )) ((EQ (CAR LAT) OLD) (CONS NEW OLD NEW (CDR LAT)))) (Tf (CONS (CAR LAT) (MULTISUBST (MULTISUBST OLD NEW (CDR LAT)))) » 5.37) Now write (OCCUR 5.38) a function (OCCUR A LAT), which counts occurs in LAT. the number Write the function is True if Nis 1 (LAMBDA (A LAT) (COND of times the atom A ((NULL LAT) ((EQ (CAR (T (OCCUR (ONEP N) where the function 0) LAT) A) (ADDL (OCCUR A (CDR LAT))) » )) (ONEP (LAMBDA (COND (N) (ONEP (LAMBDA (COND (N) ((ZEROP N) F) (T (ZEROP (SUB1 N))) ))) (T (EQN N 1)) ») ») 38 A (CDR LAT)))) 5.39) The second definition of ONEP is called a "one-liner." Is there a simple way to write "one-liners?" Try to guess what changes occur By removing (COND (T in the we simplification of ONEP. ) get (ONEP (LAMBDA (EQN N 1) (N) ») 5.40) Now write a function (REMPICK (REMPICK N LAT), using (ONEP N) which removes the Nth atom of the Lat. LAT 5.41) Ie is function (N LAT) ((ONEP N) (CDR LAT)) For example, where Nis 3, and the (LAMBDA (COND (T (CONS (CAR LAT) (REMPICK »)» (LEMON MERINGUE has the value (LEMON MERINGUE REMPICK a "multi-" SALTY PIE), PIE). function? No. (SUB1 N) (CDR LAT)))) CHAPTER True 6.2) (NOT or false: (NOT (ATOM S is (HUNGARIAN (ATOM S is 6.3) (NOT where GOULASH) S)), where (ATOM S)), where S is (TURKISH ((COFFEE) 6.5) .(ISLAT L), where L is ((HOT) (TUNA 6.8) 6.9) AND) T. Get BAKLAVA) is (LEFTMOSTAT L), where L is ((HOT) (TUNA (AND)) CHEESE) (CAR L) an L is 6.7) F. ATOM What Is *OH MY GAWD* Ts S)), 6.4) 6.6) 6: What atom, is (LEFIMOSTAT (((4) Now see if you for (LEFIMOSTAT HOT CHEESE) where ((HOT)(TUNA L is No. (AND)) CHEESE) HAMBURGER (AND A) COKE)) L), where FOUR) idea? F. (AND)) is (LEFTMOSTAT L), where L is (( (HAMBURGER) FRENCH) (FRIES What the 17 4 (SEVENTEEN)) can write the function definition (LEFTMOSTAT L) (LAMBDA (L) (COND (QNULL L)( )) ((NOT (ATOM (CAR L)))(LEFIMOSTAT (CAR L))) (T (CAR L)) ») ») Use one of our previous examples as arguments, and try to follow through this to see how it works. Notice the 6.10) What is (REMBER* A is CUP, L is Note: 6.11) 6.12) What Now A L), where ((COFFEE) ((COFFEE) "REMBER*" write now we instead are of recursing the CDR down of the the CAR of (CAR L)) list. ((TEA)) (AND (HICK))) and CUP ((TEA) CUP)(AND is pronounced (REMBER* "*" means (HICK)) CUP) "REMBER-STAR". is (REMBER* A L), where A is SAUCE, and L is (((TOMATO SAUCE)) ((BEAN) ((FLYING)) SAUCE)) Note: that list, (( (TOMATO) ) ((BEAN)) (AND ((FLYING)))) SAUCE) (AND A L) (REMBER* "OH MY GAWD". (LAMBDA (A L) (COND ((NULL L)( )) ((NOT (ATOM (CAR L))) (CONS (REMBER* A (REMBER* A (CDR L)))) ((EQ (CAR L) A) (REMBER* A (CDR L))) (TE (CONS (CAR L) (REMBER* A (CDR L)))) 6.13) (INSERTR* OLD NEW L), where OLD is CHUCK NEW is ROAST, and L is (HOW (MUCH WOOD) COULD ((A WOOD (CHUCK) (IF (A) (WOOD CHUCK) COULD (HOW (MUCH WOOD) COULD ((A WOOD CHUCK ROAST) (CHUCK ROAST) (IF (A) (WOOD CHUCK ROAST) COULD ((CHUCK ROAST) WOOD) ))) CHUCK) ( (CHUCK) WooD)))) 6.14) Now write a function (INSERTR* OLD NEW L), which inserts the atom NEW to the right of OLD, regardless of where OLD CINSERTR* (COND occurs. (LAMBDA (OLD NEW L) C((NULL L)( )) ((NOT (ATOM (CAR L)))(CONS (INSERTR* OLD NEW (CAR L)) CINSERTR* OLD NEW (CDR L)))) ((EQ (CAR L) OLD) (CONS OLD (CONS NEW (INSERTR* OLD NEW (CDR L))))) (T (CONS (CAR L) (INSERTR* OLD NEW (CDR L)))) )_»)) 40 6.15) How are (INSERTR* similar? 6.16) How 6.17) How are (INSERTR* similar? 6.18) How are all *-functions similar? OLD NEW L), and does (REMBER* A L) differ (MULTIREMBER A LAT) ? from OLD NEW L), (LEFITMOSTAT and L) Both functions arguments. recurse with the CAR of their list REMBER* recurses with the CAR as well as with the CDR. It does not recurse with the CAR, however, until it finds out that the CAR is not an atom. (REMBER* --pronounced A L) "star-functions"-- COMMANDMENT Thou shalt as well always as with They both recur with the CAR as well CDR, whenever the CAR is a list. as with the They all recurse with CDR, whenever the CAR as with the No. recurse the the CAR as well is a list. 6 with CDR when the CAR writing *-functions. 6.19) (OCCURSOMETHING A L), where A is BANANA, L is 5 and ((BANANA) (SPLIT ((((BANANA ICE))) (CREAM (BANANA)) SHERBERT) ) (BANANA) (BREAD) (BANANA BRANDY)) 6.20) What is a better function (OCCURSOMETHING 6.21) Write 6.22) (SUBST* OLD NEW L), where OLD is BANANA NEW is ORANGE, and (OCCUR* name for (OCCUR* A L) A L) (OCCUR* (LAMBDA (A L) (COND ((NULL L) 0) ((NOT (ATOM (CAR L))) (PLUS (OCCUR* A (CAR L)) (OCCUR* A (CDR L)))) ((EQ (CAR L) A)(ADD1 (OCCUR* A (CDR L)))) (T (OCCUR* A (CDR L))) A L) ((ORANGE) (SPLIT ((((ORANGE ICE))) (CREAM (GRANGE) ) SHERBERT) ) (ORANGE) (BREAD) (ORANGE BRANDY)) L is ((BANANA) (SPLIT ((((BANANA ICE))) (CREAM (BANANA) ) SHERBERT) )(BANANA) (BREAD) (BANANA BRANDY) ) 6.23) Write (SUBST* OLD NEW L) (SUBST* (LAMBDA (OLD NEW L) (COND ((NULL L)( )) : C(NOT (ATOM (CAR L))) (CONS (SUBST* OLD NEW (CAR L)) (SUBST* OLD NEW (CDR L)))) ((EQ (CAR L) OLD) (CONS NEW (SUBST* OLD NEW (CDR L)))) (T (CONS ) 6.24) CINSERTL* OLD NEW L), where OLD is FRIED NEW is FRENCH L is (FRIED ((POTATOES (CAR L)(SUBST* OLD NEW (CDR L)))) »)) (FRENCH FRIED ((POTATOES ((FRENCH FRIED) ) (FISH) ) ((FRENCH FRIED))) EGG) ((FRIED))(FISH)) ((FRIED))) EGG) 41 6.25) Write (INSERTL* OLD NEW L) CINSERTL* (COND (LAMBDA (OLD NEW L) (NULL L)( )) ((NOT (ATOM (CAR L))) (CONS (INSERTL* OLD NEW (CAR L)) (INSERTL* OLD NEW (CDR L)))) (CAR L) OLD) (CONS NEW (CONS OLD (INSERTL* OLD NEW (CDR L))))) (T (CONS (CAR L)(INSERTL* OLD NEW (CDR L)))) ((EQ )_)) 6.26) (AND (ATOM (CAR L))(EQ (CAR L) X)), where X is PIZZA, and L is (MOZARELLA PIZZA) 6.27) Why F is it false? Since AND asks (ATOM (CAR L)), and it is, so then it asks (EQ (CAR L) X), and it is not; 6.28) What is (AND X is L is (ATOM (CAR L))(EQ PIZZA, AND ((MOZARELLA 6.29) Why is it 6.30) Give an example for 6.32) (OR (NOT X and L, where own words (CAR L)))(EQ X is CURRIED, and L is (CURRIED (SHRIMP what AND is the true. How function (CAR L) X)), where 6.35) Why (NOT (ATOM which is T, so (NOT (CAR L)))(EQ and L is WITH (SHRIMP (CAR L) X)), CURRIED Can you put in your own words what OR does? 6.38) True or false: It is possible arguments of AND and OR is not 6.39) (MEMBER* A L), where A is GRAPE, and L is ((GRAPEFRUIT where RICE) 6.32) function (EQ (CAR L) X), of OR is true. (ATOM (CAR L))) is T, so OR asks (NOT OR asks (EQ (CAR L) X), which the value of OR (ATOM of OR is (CAR L))), which is false, is also false, so so false. t,t because AND stops if the first argument has the value F, and OR stops if the first argument has the value T. F, since (AND) is F, so we ask value The function OR is either true or false. OR asks questions one at a time until it finds an argument the value of which is true. Then OR stops, making its value true. If it cannot find one true argument, then the value of OR is false. that one of the considered? (RAISINS)) (WINE the true. the value the (CAR L))) T. is (ATOM GOOD)) T; is it true? X is CURRTED it is not; WITH RICE)) (OR (NOT (ATOM (CAR L)))(EQ (CAR L) X)), where X is CURRIED, and L is ((CURRIED) SHRIMP WITH RICE) (NOT about, where X is PIZZA, and L is (PIZZA (TASTES and The function AND is either true or false. AND asks questions one at a time until it finds an argument the value of which is false. Then AND stops, making its value false. If it cannot find one false argument, then the value of AND is true. Why is it true? (OR F. PIZZA) 6.34) 6.36) the value Since AND asks (ATOM (CAR L)), so AND has the value F. Can you put in your AND does? (ATOM AND has F false? 6.31) 6.33) MUSHROOM) (CAR L) X)), where hence the atom GRAPE does not appear in the list GRAPES)) tconp is a function; 42 it also has this property. L. 6.40) (MEMBER* A L), where T, A is CHIPS, and L is ((POTATO) (CHIPS 6.41) Write because ((WITH) the atom CHIPS appears in the Llis= 2- FISH) (CHIPS))) (MEMBER* (LAMBDA (A L) (MEMBER* A L). (COND ((NULL L) F) ((NOT (ATOM (CAR L)))(OR (MEMBER* A (CAR <. (MEMBER* A (CDR L)))) ((EQ (CAR L) A) T) (T (MEMBER* A (CDR L))) )».)) 6.42) What is (MEMBER* AL), A is CHIPS, and L is where ((POTATO) (CHIPS 6.43) Which CHIPS did 6.44) Try to combine into one line. line. it T. ((WITH) FISH) (CHIPS) )) find? the last Rewrite 7 ((POTATO) (CHIPS two the lines of (MEMBER* A L) function using this ((WITH) (MEMBER2* (LAMBDA (COND ((NULL L) F) FISH) (CHIPS)) (A L) « ((NOT (ATOM (CAR L))) (OR (MEMBER2* (MEMBER2* A (CDR L)))) (T (OR (EQ (CAR L) A) (MEMBER2* ) 6.45) Try to write (MEMBER2* AL) without using NOT. (MEMBER3* A (CDR L)))) (LAMBDA (A L) (COND ((NULL L) ((ATOM (CAR L)) (OR (EQ (CAR L) A) F) ) Now, ,can you break up the last line (MEMBER3* A L) to form two lines. HINT: of (MEMBER4* (COND See (MEMBER* A L) (CAR L)) »)) (MEMBER3* A (CDR L)))) (T (OR (MEMBER3* A (CAR L)) (MEMBER3* 6.46) A A (CDR L)))) )) (LAMBDA (A L) ((NULL L) F) ((ATOM (CAR L))(OR (MEMBER4* (EQ (CAR L) A) A (CDR L)))) ((MEMBER4* A (CAR L)) T) (Tf (MEMBER4* A (CDR L))) )_»)) 6.47) What 6.48) Have we ever seen recursion on the left side Yes, of a line before A L) see 6.49) 6.50) is unusual Why does about (MEMBER4* (MEMBER4* A L) We are (EQ Nl N2), where recursing (MAXVEC Since in the question letters. Why does (EQN Al A2) where Al is HARRY and Since of a line. VEC). EQ is only defined Nl is 15, and N2 is 12 have no answer? side EQN is only defined for atoms beginning with for numeric atoms. A2 is HARRY have no answer? 6.51) Try to write a function (EQAN Al A2) which is True if Al and A2 (EQAN are the same (LAMBDA (COND (CAND atom. (Al A2) (NUMBERP (T (EQ Al A2)) 6.52) (EQUAL S1 S2), where $1 is BANANAS, S2 is (BANANAS) and Al) (NUMBERP A2)) (EQN Al A2)) ((OR (NUMBERP Al) (NUMBERP A2)) F) F. - 6.53) 6.54) (EQUAL S1 S2), where Sl is (STRAWBERRY S82 is (STRAWBERRY (EQUAL Sl S2 6.55) (EQUAL S1 S2), is is T. ICE ICE CREAM), CREAM) and ICE CREAM), CREAM ICE) and where F. (STRAWBERRY (STRAWBERRY S1 S2), where F, $1 is (BANANA ((SPLIT))), S2 is 6.56) (EQUAL 6.57) (EQUAL and ((BANANA) (SPLIT)) S1 82), where F, Sl is (BEEF ((SAUSAGE))(AND (SODA))), $2 is (BEEF ((SALAMI)) (AND (SODA))) $1 S1.S2), and where T, is (5 APPLE PIES), $2 is (5 APPLE PIES) 6.58) Can you write does? 6.59) Using EQAN, write in your and own words what (EQUAL S1 $2) EQUAL determines if the S-expression the same as the S-expression S2. (EQUAL $1 S2) (EQUAL (LAMBDA S1 is exactly (S1 $2) (COND ((AND (NOT (ATOM S1)) (NOT (ATOM $2))) (AND (EQUAL (CAR S1) (CAR $2)) (EQUAL (CDR S1) (CDR S2)))) ((AND (ATOM $1) (ATOM S2)) (EQAN S1 S2)) (T F) > 6.60) (EQUAL S1 S2), where Sl is (), and $2 is ( ) 6.61) Is EQUAL a "star-" How would REMBER 6.62) by EQUAL? ») Your response should be no answer. However, (ATOM S) where S$ is ( ) is True! Hence, (EQ S1 S2) and (EQUAL $1 S2) where Si is ( ) and S2 is ( ) are also True. The null list ( ) is also referred to as the atom NIL. function? change if we Yes. replaced EQ (REMBER (LAMBDA (S L) (COND ((NULL L)( )) ((EQUAL (CAR L) S)(CDR L)) (T (CONS (CAR L) (REMBER S (CDR L)))) Now REMBER removes the first S-expression § in the list L, instead of the first atom in the list of atoms L. 6.63) Is REMBER a “star-" function? No. 6.64) Why not? 6.65) Can we assume that all functions which were written using EQ and EQN can be generalized by replacing EQ and EQN by the function EQUAL. , Because REMBER only recurses with the (CDR L). Not quite, this won't work for EQAN or EQN, but will work for all others. In fact, disregarding the trivial examples of EQAN and EQN, that is exactly what we shall assume. . t ULL S) can actually be written ((ATOM S) (EQ S NIL)) (T F) )_)) 44 as If you got you need through that last function, a rest. This space for doodling. CHAPTER 7.1) 7.2) Is this a set? (APPLE PEACHES APPLE 7: FRIENDS (ISSET LAT), where (ISSET LAT 7.4) RELATIONS F, since PLUM) APPLE more than once. because no atom appears more LAT), where T, is because ( ) Try to write appears T, LAT is (APPLES PEACHES PEARS PLUMS), 7.3) AND (ISSET LAT) no atom appears than once. more than once. (ISSET (LAMBDA (LAT) (COND ((NULL LAT) T) ((MEMBER (CAR LAT) (CDR LAT)) F) (T (ISSET (CDR LAT))) ) »)) 7.5) Does this work (APPLE 7.6) Were for the you surprised appear example 3 PEAR 4 9 APPLE to see in the function Yes, 3 4) the function MEMBER ISSET? since MEMBER is now written of EQ. See 6.65. using EQUAL You we srould not (MEMBER A LAT) whenever 7.7) 7.8) What is (MAKESET LAT), where LAT is (APPLE PEACH PEAR PEACH LEMON PEACH) Try to write (MAKESET LAT), (APPLE PLUM APPLE we be, because already, instead have written and now we can use it Like. PEACH PEAR PLUM LEMON) ‘ « using MEMBER. (MAKESET (LAMBDA (COND (LAT) (PEAR PLUM APPLE LEMMON (MAKESET (LAT) (QNULL LAT)( )) ( (MEMBER (CAR LAT) (CDR LAT))(MAKESET (CDR LAT))) (T (CONS (CAR LAT) (MAKESET (CDR LAT)))) )_»)) 7.9) Using the function what is the result LAT is LEMON 7.10) Try to write (APPLE definition that you just wrote, of (MAKESET LAT), where PEACH PEAR PEACH PLUM PEACH) APPLE PEACH) (MAKESET LAT), using MULTIREMBER. (LAMBDA (COND CQNULL LAT) ( )) (T (CONS (CAR LAT) (MAKESET (MULTIREMBER (CAR LAT) (CDR LAT))))) 7.11) What is the result of (MAKESET LAT) using this second definition, where LAT is (APPLE PEACH PEAR PEACH PLUM APPLE (APPLE PEACH PEAR PLUM LEMON) LEMON PEACH) 7.12) Can you describe in your own words how the second definition of (MAKESET LAT) does what .it does? Here are our words: “MAKESET saves the first then recurses, of the 7.13) Does the second MAKESET work for the (APPLE 3 PEAR 4 9 APPLE 3 4) example 46 atom removing in the LAT, all and occurrences atom from the rest of the LAT". MULTIREMBER instead of EQ. is now written using Yes, since first after EQUAL 7.14) What is (SUBSET SET1 SET2), where SET1 is (5 CHICKEN WINGS), and SET2 7.15) What (5 HAMBURGERS 2 PIECES LIGHT DUCKLING WINGS) is (SUBSET SET1 SET2 7.16) is AND T, because FRIED each atom in SET] is also in SET2. CHICKEN SET1 SET2), where F. is (4 POUNDS OF HORSERADISH), and is (FOUR POUNDS CHICKEN AND 5 OUNCES HORSERADISH) Try to write (SUBSET SET1 SET2). (SUBSET (LAMBDA (SET1 (COND (NULL SET1) T) SET2) ((MEMBER (CAR SET1) SET2)(SUBSET (CDR SET1) SET2)) (T F) ») or, you could have written: (SUBSET (LAMBDA (SET1 SET2) (COND ((NULL SET1) T) (T (AND (MEMBER (CAR SET1) SET2) (SUBSET (CDR SET1) SET2))) ) »)) 7.17) What is (EQSET SET1 SET2 7.18) is is SET1 SET2), where (6 LARGE CHICKENS WITH (6 CHICKENS WITH LARGE T. WINGS) WINGS) Try to write (EQSET SET1 SET2). (EQSET (LAMBDA (SET1 SET2) (COND ((SUBSET SET1 SET2) (SUBSET SET2 SET1)) (T F) ») or, you could have written: (EQSET (LAMBDA (SET1 SET2) (COND (T (AND (SUBSET SET1 SET2) (SUBSET SET2 or, you could have written the "one-liner" (EQSET (LAMBDA (SET1 SET2) (AND (SUBSET SET1 SET2) (SUBSET 7.19) 7.20) (DOESINTERSECT SETI SET2), where SET1 is (STEWED SET2 is (MACARONI Try to write TOMATOES AND AND MACARONI), SET2 SET1)) ’ T, and SET1))) because at least CHEESE) one atom in SET1 is in SET2. i (DOESINTERSECT SET1 SET2). (DOESINTERSECT (LAMBDA (SET1 SET2) (COND ((NULL SET1) F) ((MEMBER (CAR SET1) SET2) T) (T (DOESINTERSECT (CDR SET1) SET2)) )_») or, you could have written: (DOESINTERSECT (LAMBDA (SET1 SET2) (COND ((NULL SET1) F) (T (OR (MEMBER (CAR SET1) SET2) (DOESINTERSECT (CDR SET1) SET2))) )»)) Note: Look back at (SUBSET compare for similarities. 47 SET1 SET2), and 7.21) 7.22) What is (INTERSECT SET] SET2), where SET1 is (STEWED TOMATOES AND MACARONI), SET2 is (MACARONI AND CHEESE) Try to write (INTERSECT SET1 (AND MACARONT) and SET2) (INTERSECT (LAMBDA (SETL SET2) (COND ((NULL SET1)( )) ((MEMBER (CAR SET1) SET2) (CONS (CAR SET1) (INTERSECT (CDR SET1) SET2))) (T (INTERSECT (CDR SET1) SET2)) ) or, you ») could have written (INTERSECT (LAMBDA (SET1 SET2) (COND ((NULL SET1)( )) ((NOT (MEMBER (CAR SET1) SET2)) (INTERSECT (CDR SET1) SET2)) (P (CONS (CAR SET1) (INTERSECT (CDR SET1) SET2))) 7.23) What is (UNION SET1 SET1 is (STEWED SET2), where TOMATOES AND MACARONI (STEWED TOMATOES CASSEROLE MACARONI AND CHEESE) CASSEROLE), and SET2 7.24) is (MACARONI Try to write (UNION AND SET1 CHEESE) SET2). (UNION (LAMBDA (SET1 SET2) (COND ((NULL SET1) SET2) ((MEMBER (CAR SET1) SET2) (UNION (CDR SET1) SET2)) (T (CONS (CAR SET1) (UNION (CDR SET1) SET2))) ) 7.25). What does this function do? (XXX (LAMBDA (SET1 SET2) (COND ((NULL SET1)( In our words: " The value of (XXX SET1 SET2) SET1 that are not in SET2." )) (STEWED ((MEMBER (CAR SET1) SET2)(Xxx (CDR SET1) SET2)) (T (CONS (CAR SET1) (XXX (CDR SET1) SET2))) 7.26) WO Is this a pair? TOMATOES ee is all the atoms in CASSEROLE) ort es SET2) caw bexcal ted T, (PEAR PEAR) because 7.27) Is this a pair? (3 7) T. 7.28) Is this T. a pair? it is a list with only two atoms. (3 PAIR) 7.29) How can you get a hold of the first atom of a pair? By taking the CAR of the pair. 7.30) How can you of the second atom of a pair? By taking the CAR of the CDR of the pair. do you You CONS the 7.31) If you make 7.32) are get a hold given two atoms, Al and A2, how them a pair? (FIRST (LAMBDA (COND (P) (SECOND (LAMBDA (P) (COND (T (CAR (CDR P))) )_)) BUILD (LAMBDA (Al A2) (COND (T (CONS Al (CONS A2 ( )))) What ») possible uses atom onto the CONS They will be used for convenience as you will soon see. , (T (CAR P)) )_)) » first of the second atom onto ( ). (CONS Al (CONS A2( ))) do these three functions have? 48 and readability, 7.33) 7.34) Is L a REL, where L is (APPLES PEACHES Is L a REL, where L is ((APPLES PUMPKIN PIE) PEACHES) (PUMPKIN PIE) (APPLES PEACHES) (PUMPKIN PIE)) F, since Note: L is not a list of pairs. REL stands for RELation. F, since L is not a set of pairs. PEACHES) ) 7.35) Is L a REL, where L is ((APPLES T. 7.36) Is L a REL, where L is ((4 3)(4 2)(7 6)(6 2)(3 4)) 7.37) Is REL 7.38) 7.39) What T. a FUN, where F, REL is ((4 3)(4 2)(7 6)(6 2)(3 4)) Note: is (ISFUN REL), where REL is ((12 3)(4 2)(7 6)(6 2)(3 4)) Tt, because Try to write (ISFUN REL). FUN stands for FUNction. (FIRSTS REL) How about is a set - see Chapter 3. this? (ISFUN (LAMBDA (REL) (COND ((NULL REL) T) ((MEMBER* (FIRST (CAR REL))(CDR REL)) F) -(T (ISFUN (CDR REL))) 7.40) When will that 7.41) Try again to write for the function description (ISFUN REL) for ISFUN work? When so it will work (DOESINTERSECT (ISFUN case where (LAMBDA (FIRSTS REL) (SECONDS REL)) is F. (REL) (COND REL is ((12 3)(4 2)(7 6)(6 2)(3 4)) C(NULL REL) T) ((MEMBER (FIRST (Tf CISFUN or, much (CDR REL)) (FIRSTS (CAR (CDR REL))) F) REL))) better (ISFUN (LAMBDA (REL) (COND (f (ISSET (FIRSTS REL))) ) )) 7.42) What is REL 7.43) (REVREL is REL), where ((8 A) (PUMPKIN PIE)(GOT ((A 8) (PIE PUMPKIN) (SICK GOT)) SICK)) Try to write (REVREL REL). (REVREL (LAMBDA (REL) (COND C(NULL REL)( )) (T (CONS (BUILD (SECOND (CAR REL)) (FIRST (CAR EEL): ~ (REVREL (CDR REL)))) )_)) or, the following would also be correct: (REVREL (LAMBDA (REL) (COND ((NULL REL)( )) (T (CONS (CONS (CAR (CDR (CAR REL))) (CONS (CAR (CAR REL))( )))(REVREL (COE I=. ) Note: Now you know what and readability. 49 we mean by cosvwemiemce 7.44) Can you guess why FUN is not a FULLFUN, where FUN is ((12 3)(4 2)(7 6)(6 2)(3 4)) FUN is not once as a second 7.45) Why does (ISFULLFUN FUN) have the value T, where FUN is ((12 3)(4 8)(7 6)(6 2)(3 4)) Because 7.46) What F, is FUN 7.47) 7.48) What (ISFULLFUN FUN), is RAISIN) (PLUM ((GRAPE where PRUNE) (STEWED PRUNE) ) GRAPE) ) is (ISFULLFUN FUN), FUN is RAISIN) (PLUM PRUNE) (STEWED Try to write ((GRAPE (ISFULLFUN where FUN) a FULLFUN, since the 2 appears more than atom of a pair. the list (3 8 6 2 4) is a set. the (RAISIN T, three different because ways. list (ISFULLFUN (LAMBDA PRUNE GRAPE) is a set. (FUN) (COND ((NULL FUN) T) ((MEMBER (SECOND (T (ISFULLFUN (CAR FUN)) (SECONDS (CDR FUN))) (ISFULLFUN (LAMBDA (FUN) (COND (Tf (ISSET (SECONDS FUN) )) (T (ISFUN (REVREL FUN))) ) ») 7.49) What is another function name for (ONE-TO-ONE FUN). (ISFULLFUN FUN) If the three ways you just wrote 1. Sitting down 2. Standing up 3. Standing on your head you were wrong! 50 that last function were: (CDR FUN))) FP) CHAPTER 8.1) Is this 8: “HELP IS ON THE WAY, a palindrome? (APPLE BANANA 8.2) (ISPALIN 8.3) (ISPALIN L), where APPLE) T. (A5 4MKM45 L is TO THE HAMMOCK Yes. BANANA L), where Lis OR WELCOME A) T. (HARRY) 8.4) (ISPALIN L), where Lis (HARRY) F. 8.5) (ISPALIN (LAMBDA (L) (COND ((NULL L) T) ((NULL (CDR L)) T) ((EQUAL (CAR L)(RAC L))(ISPALIN (I F) ) )) The function 8.6) What does this function What is (RAC L) 2 Have we used if L is a palindrome. (CDR (RDC L)))) do? (RAC L) is a help function. what it looks function list. 8.7) finds any help functions before in this book? Yes, every that will time we CONS, EQ, used We don't know ret but we know like, a function other Can you name some last chapter? 8.9) What is (RDC L) ? Note: "RDC" is pronounced help functions we used "Rudercouder". in the Shall we write RAC and RDC now? is (REVLAT LAT), where LAT is (A BUNCH OF COCONUTS) 8.12) Here is one way (REVLAT (LAMBDA (COND to write 8.13) What fumct:m all the atoms in the list, (COCONUTS LAT): is written. can write them We know what RAC amé EDC ao, later. OF BUNCH A) Yes. (LAT) ((NULL LAT)( )) (T (SNOC (REVLAT ) Is this (REVLAT another No. ISPALIN What = RDC is a help function. We don't know vee wrac it looks like, but we know it will be a Samctim so we 8.11) Caz. FIRST, SECOND, BUILD, FIRSTS, SECONDS, MEXGEZ, EQUAL, SUBSET, ISSET, and MULTIREMBER. Ca vrru name some other functions we failed to sewerima! that will give us without the RAC. 8.10) than ATOM, NULL, AND, OR, SOT, SC3ET?. ZEROP, ADD1, and SUB1 to define we were using help functions! 8.8) be 2 it will give us the last atom ia a (CDR LAT)) (CAR LAT))) correct? does the function 1 (SNOC L S) do? SNOC is a help function. We do not know what it looks like yet, but we know we need a function that sticks S-expression onto the end of a list, similar to the way CONS sticks S-expressions onto the front of a list. So for now, we will assume SNOC exists, and we will write it later. 8.14) Thou shalt does exist. does, then Is this a MAT? ((4 8 6 3)(12 4 86 2)(36 always COMMANDMENT No. assume any help If you use it, that can describe and you 7 what can write function you need the help function it Yes, because 1 7 6)) Note: 8.15) 8.16) 8.17) 8.18) it is a list of VECs. MAT stands for MATrix. No, Is this a MAT? ((16 3 2)(4 7. 6) (14 8)) since Is this a ZEROMAT? ((O 0 0)(0 1 0)(0 0 0) (0 0 0)) (ISZEROMAT not all the VECs are of the same not all the of every length. No, since (ISZEROMAT MAT), where MAT is ((000000)(000000)(00000 Try to write later. VEC are zero. Yes, 0)) because all (ISZEROMAT MAT). atoms the VECs (LAMBDA are ZEROVECs. (MAT) (COND (QNULL MAT) T) (T (AND (ISZEROVEC (CAR MAT))(ISZEROMAT >») or, you could (CDR MAT)))) have written (ISZEROMAT (LAMBDA (MAT) (COND ((NULL MAT) T) (CISZEROVEC (CAR MAT)) (ISZEROMAT (Tt F) 8.19) What is 8.20) What does 8.21) (ISZEROVEC VEC), where VEC is (0 0 0) 8.22) (ISZEROVEC (ISZEROVEC (ISZEROVEC VEC is 8.23) 8.24) VEC), VEC), VEC (0 0) is ? It is a help VEC) do? 8.26) What the atoms where where a MAT? No of since all (ISZEROMAT L), where the VECs are not of the same length. T, L is ((0 0 0)(0 0 0 0)(0 0)) because, even though L is not a MAT, ISZEROMAT only asks if each VEC is a ZEROVEC by considering each VEC in total isolation. is (SCALMAT ((18 9 6)(15 36 21)(9 6 18)) N is 3, and MAT 8.27) - if all T. What would be the value What function. It asks if a VEC is the ZEROVEC in the VEC are zero. ((0 0 0)(0 0 0 0) (0 0)) 8.25) )») (0 0 0 0) (ISZEROVEC Is this VEC) (CDR MAT))) is ((6 N MAT), 3 2)(5 where 12 7)(3 is (SCALMAT N MAT), N is 56, and where 2 6)) ((56) (112) (280) (392) (224)) MAT is ((1)(2) (5) (7) (4)) 8.28) Can you write (SCALMAT N MAT) ? (SCALMAT (LAMBDA (COND (N MAT) ((NULL MAT)( )) (T (CONS (SCALVEC N (CAR MAT))(SCALMAT N (CDR MAT)))) )_») 8.29) What is 8.30) What will 8.31) Is L a MAT, Lis 8.32) 8.33) What What (SCALVEC N.VEC) (SCALVEC ? It is a help N VEC) do? It will multiply each by the argument N. where Can you write VEC ((30 15 20)(40 10)(60 65 35)) L is not a MAT, but the help function (SCALVEC considers each VEC one at a time - in total isolation. is (MATPLUS MAT1 MAT2), where MATL is ((4 4 6)(3 12 15)(6 8 3)(4 4 6)), MAT2 is ((8 8 6)(9 O 3)(6 4 9)(8 8 6)) 8.35) in the argument 13 7)) is the value of (SCALMAT N L), where N is 5, and Lis ((6 3 4)(8 2)(12 13. 7)) What atom No. ((6 3 4)(8 2)(12 8.34) function. MAT1 MAT2) 12 18)(12 ((4 11 9 6)(11 14 4 12)) 12 12)(12 12 12)) and is (MATPLUS MAT1 MAT2), where MAT1 is ((0 5 6 4)(3 2 1 6)) MAT2 is ((4 6 3 2)(8 12 3 6)) (MATPLUS ((12 12 12)(12 N VEC) ? (MATPLUS (LAMBDA (MAT1.MAT2) (COND ((NULL MAT1)( )) (T (CONS (VECPLUS (CAR MAT1) (CAR MAT2)) (MATPLUS (CDR MAT1) (CDR MAT2)))) ) 8.36) What is (DIMENSIONS MAT), where MAT 8.37) 8.38) What What is (2 2) ((4 6)(8 3)) is (DIMENSIONS MAT), where MAT is ((6 9 3 4 12 2 37)(4 is »)) (DIMENSIONS MAT), (2 7) 12 6 7 84 3 172)) where ql 1) MAT is ((4) (6) (5) (4) (2) (9) (12) (14) (26) (3) (1)) 8.39) What 8.40) What is (DIMENSIONS MAT), where MAT is ((4 6 5 4 29 12 14 26 31)) is MAT 8.41) Try (DIMENSIONS is MAT), (1 9) where (7 0) (( )€)€)€)0€)00)00€)) to write (DIMENSIONS Use any help functions MAT). (DIMENSIONS you need. (LAMBDA (COND (T (BUILD (LENGTH ) or, you (MAT) ‘ MAT) (LENGTH could have written (DIMENSIONS (LAMBDA (MAT) (COND (T (CONS (LENGTH MAT) (CONS ) 8.42) What 8.43 What 8.44) is VEC (SORTUP VEC), where is (3 9 4 8 6) (3 4 6 8 9) is (SORTUP (2 229 VEC is Try to write you need. VEC), where (2 15 (CAR MAT)))) »)) (LENGTH (CAR MAT))( )))) )) 11 15) 9 2 11 2) (SORTUP VEC), using any help functions (SORTUP (LAMBDA (COND (VEC) ((NULL VEC)( )) "py (T (CONS 53 (MINIVEC VEC) (SORTUP (REMBER (MINIVEC VEC) 8.45) What does our help function (MINIVEC VEC) do? It finds the we have not smallest seen number later should be trivial Chapter 8.46) What is (MINSMAT MAT), where in the VEC. VEC) (MINIVEC yet, Although writing it in - remember MAXVEC 4? (3 0) MAT is ((3 6 9)(4 2 0)) 8.47) What is (MINSMAT MAT), where MAT is ((2 6 7 9)(11 8.48) Now try to write (211) 1 3 4)(1 9 12 15)) (MINSMAT MAT). (MINSMAT (LAMBDA (COND (MAT) ((NULL MAT)( )) (t acne ner ) 8.49) What does 8.50) Here is the (MINSMAT MAT) function my (MINSMAT MAT) builds a VEC composed number in each VEC of the MAT. (NONAME MAT); (NONAME (LAMBDA (MAT) (COND ((NULL (CAR MAT))( (f (CONS do? (MINIVEC what does it do? We are not sure, but let's (CDR MAT)))) of the smallest find out. )) (FIRSTS MAT)) (NONAME (CDRVEX 8.51) What does 8.52) What is (MINIVEC (FIRSTS MAT)), where MAT is ((4 8 2)(6 12 2)(3 6 8)) 8.53) What is the meaning (MINIVEC (CAR MAT)) (MINSMAT (FIRSTS MAT)) of (NONAME do? It finds the smallest atom in the list of the CAR of each VEC of the MAT. composed 3 (CDRVEX MAT)) ? The argument (CDRVEX MAT) should composed of the CDR of each this, recurse. we give us a list VEC of the MAT. With 8.54) What is (CDRVEX MAT), where MAT is ((4 8 3)(6 12 2)(3 6 8)) ((8 3)(12 8.55) What is (CARTES SET1 SET2), where SET] is (HOME MADE BREAD), and SET2 is (BROWN RICE) ((HOME BROWN) (HOME RICE) (MADE BROWN) (MADE RICE) (BREAD BROWN) (BREAD RICE)) 8.56) What is (CARTES SET] SET2), where SET1 is (A 5 9 CORN), and ((A HELP) (A 3)(A TIMES)(5 HELP)(5 3)(5 TIMES) (9 HELP)(9 3)(9 TIMES) (CORN HELP) (CORN 3) SET2 is (HELP 3 TIMES) (CORN 8.57) Can you write in your own words (CARTES SET1 SET2) does? 8.58) Now write (CARTES SET1 SET2). 8.59) What what , 2)(6 8)) TIMES)) Our words: “CARTES builds a REL composed of all possible choosing first elements from SET1 and second pairs elements from SET2." is LSET (INTERSECTALL is LSET), ((A B C)(C AD (CARTES (LAMBDA (SET1 SET2) (COND ((NULL SET1)( )) (T (APPEND (DISTRIB (CAR SET1) SET2) (CARTES (CDR SET1) SET2))) ) »)) where E)(E F GHA (A) B))) 8.60) What is LSET (INTERSECTALL LSET), where (6 AND) is ((6 PEARS AND) (3 PEACHES AND 6 PEPPERS) (8 PEARS AND 6 PLUMS) (AND 6 PRUNES WITH LOTS OF APPLES)) 8.61) Now, using whatever (INTERSECTALL help functions you need, write LSET). INTERSECTALL (LAMBDA (LSET) (COND ((NULL LSET)( )) (T (INTERSECT (CAR LSET)(INTERSECTALL ) ») 8.62) What is (TRANSPOSE MAT), where MAT is ((4 3 2. 1)(2 76 8)(9 1 4 3)(4 2 6 7)) ((4 29 8.63) What is (TRANSPOSE MAT), where MAT is ((1 2 3)(1 2 3)(2 2 3)(1.2 ((2121:1)(2 8.64) In your own words, what does 4)(3 71 2)(2 6 4 6)(1 8 3 7)) 2 2 2)(3 3 3 3)) 3)) (TRANSPOSE MAT) do? Our words, again: “TRANSPOSE builds a new MAT. this new MAT is (FIRSTS MAT); (SECONDS MAT), and so on." ‘ 8.65) Try to write (TRANSPOSE MAT). The first VEC in the second VEC is ‘ How about: (TRANSPOSE (COND (LAMBDA (MAT) ((NULL MAT)( )) (T (CONS (FIRSTS MAT) (TRANSPOSE ») »)) that (CDR LSET)))) correct? Well 8.66) Is 8.67) (NULL MAT), where MAT is ((3 2 4)(6 9 7)) No. 8.68) (T (CONS (FIRSTS MAT)(TRANSPOSE (CDRVEX MAT)))) CONS (3 6) onto (TRANSPOSE (CDRVEX MAT)) 8.69) What is (CDRVEX MAT) ? ((2 4)(9 7)) 8.70) (NULL MAT) No. 8.71) (T (CONS (FIRSTS MAT) (TRANSPOSE (CDRVEX MAT)))) CONS (2 9) onto (TRANSPOSE (CDRVEX MAT)) 8.72) What is (CDRVEX MAT) 2 ((4)(7)) 8.73) (NULL MAT) No. 8.74) (T (CONS (FIRSTS MAT) (TRANSPOSE (CDRVEX MAT)))) CONS (4 7) onto (TRANSPOSE (CDRVEX MAT)) 8.75) What is (CDRVEX MAT) (C)€)) 8.76) (NULL MAT) No. 8.77) What? | . . . let's (CDRVEX MAT)))) see. Since each VEC of the MAT is the same length, we have now considered all the atoms of each VEC, but the MAT is not null; it is composed of null VECs. We obviously need a terminal condition to test when the VECs of the MAT are null. 8.78) Can you come correct up with terminal something condition that would line? be a ((NULL (CAR MAT))( )) 8.79) 8.80) Now what is the correct (TRANSPOSE MAT) function definition Now can you rewrite (NONAME MAT) using (TRANSPOSE (MINSMAT as help MAT) that and more MAT) 8.81) Now was 8.82) This could he The End of the book, to give you all the help functions back to the functions that in order to write them? shalt, Write 1. 2. COMMANDMENT No. when writing a function of what the help function should the main which Make do. of the function 8 requires a note LATER, of one or more help functions, the arguments and a description write the help function in total function. Has a final value which is the S-expression in the list. (RAC (LAMBDA (L) (COND ((NULL (CDR L)) (CAR L)) (Tf (RAC (CDR L))) last (RDC (LAMBDA (COND (RDC L), which Takes a non-null list as an argument, and Has a final value which is the same L, but ((NULL (RAC L). arguments, MAT) )) refer functions (L) (CDR L))( )) (f (CONS (CAR L)(RDC ) )) (CDR L)))) (SNOC (LAMBDA (L S) (COND ((NULL L)(CONS § ( ))) (T (CONS (CAR L)(SNOC (CDR L)))) Write the description of the function (SNOC L S), which 1. Takes a list and an S-expression as its 2. 8.86) help first. without 8.85) these function the description (TRANSPOSE you must write the help functions in total isolation, that is, you need to know only two things: 1. The arguments of the help function; 2. What the help function should do. the main from (MAT) No, Write the description of the function (RAC L), which 1. Takes a non-null list as an argument, and 2. 8.84) but we decided we have not yet SNOC, MINIVEC, Do we need to used (CDRVEX MAT)))) Correct. complete isolation 8.83) (NONAME (LAMBDA (COND (T (MINSMAT functions? straightforward? defined. They are RAC, RDC, CDRVEX, APPEND, and DISTRIB. Thou (TRANSPOSE (LAMBDA (MAT) (COND ((NULL (CAR MAT))( )) (T (CONS (FIRSTS MAT) (TRANSPOSE >)» of and Builds a list by sticking its S-expression argument onto the end of its list argument. ) ») : (MINIVEC (LAMBDA (VEC) (COND ((NULL (CDR VEC)) (CAR VEC)) (T (SMALLER (CAR VEC) (MINIVEC ))) Write the description of the function (MINIVEC VEC) which 1. Takes a non-null VEC as its argument, and 2. Has as its final value the smallest atom in the VEC. Sometime we neéd to write (SMALLER Nl N2) the (CDR VEC)))) function which 1. 2. Takes two numbers as its arguments, and Has the value of the smaller of the two numbers: (SMALLER (LAMBDA (N1 N2) (COND ((LESSP Nl N2) Ni) (T N2) )_»)) 56 8.87) 8.88) Write a description of the function (CDRVEX MAT), which 1. Takes a MAT as its argument, and 2. Has as its final value a list of the CDRs of each VEC of the MAT. (CDRVEX (LAMBDA (MAT) (COND (CNULL MAT)( )) (T (CONS (CDR (CAR MAT))(CDRVEX ) »y Now write the description (APPEND (APPEND L2), Ll of the function which Takes two lists as its arguments, and Has as its final value one list containing all the S-expressions of L1 and L2, in their original orders. Example: where Ll is (APPLES BANANAS CHICKENS), and L2 is (DOGS EGGS FRUIT GRAPE) then Ll L2) is BANANAS CHICKENS description DOGS of the EGGS Now write the (DISTRIB A SET), which 1. Takes an atom and a set as 2. Builds a REL where each pair (CDR L1) L2))) a member Now write the description of the (ISZEROVEC VEC), which 1. Takes a VEC as its argument, (DISTRIB arguments, has A as of the set (LAMBDA and (C(NULL its (T (CONS as (A SET) F if the vector than 0. SET)( )) (BUILD A (CAR SET)) (DISTRIB A (CDR SET)))) its function . and some other GRAPE) function Has as its value number FRUIT (COND first atom, and second atom. 2. ((NULL L1) L2) (T (CONS (CAR L1) (APPEND ») » ; (APPEND (APPLES 8.90) (L1 L2) (COND 1. 2. 8.89) (LAMBDA (CDR MAT)))) (ISZEROVEC (LAMBDA (VEC) (COND ( (NULL VEC) T) contains ((ZEROP (CAR VEC))(ISZEROVEC (CDR VEC))) (T F) »» 8.91) Now write the description (SCALVEC N VEC), which of the function (SCALVEC (LAMBDA (COND 1. Takes a number and a VEC as its argument, 2. Builds by N. a VEC with each value and ((NULL VEC)( )) multiplied (T (CONS (TIMES N (CAR VEC)) (SCALVEC N (CDR VEC)))) Example: where N is 12, and VEC is (2 8 15) then 8.92 (SCALVEC N VEC) (24 180) 96 dy») is Now that you have come this far, brainteaser. Write the function here is a real (DEPTH L). (DEPTH (((B) L) is 3, where L is ((A) is 5, where L is ((((((A))))) This (N VEC) C)) (DEPTH (LAMBDA (COND D) CC(NULL L) 0) A ((B))) is 1, where L is ((ATE) TOO (MUCH)) is 0, where L is (A B C) is a hammock problem, so give yourself some (L) ((ATOM (CAR L)) (DEPTH (CDR L))) ((GREATERP (ADD1 (DEPTH (CAR L))) (DEPTH (ADD1 (DEPTH (CAR L)))) (T (DEPTH (CDR L))) time. >») 57 (CDR L))) CONCLUSIONS You have What should reached you have a major programming better prepared your time the end of your beginning with LISP. others learned? of the subject, problem in LISP’? than you realize, to develop a fuller capabilities in LISP. with computer programming about LISP, exception Are you now For the books of Suppes those in the of sophistication Maurer be worth about like with more [2] is the definitive work from which texts For evolved. to implement - but experience teaches on LISP language; as reviewers puts LISP) such you can be understood is one way this new elegant LISPer and powerful that (as one Berkeley, E. C., and Bobrow, D. G., (eds), The Programming Language LISP: Its Operation and Applications, Information International, Inc., Cambridge, Massachusetts, 1964. [2] McCarthy, J., et al., LISP Manual, The M.I.T. Press, Massachusetts, 1963. (3] Maurer, W. D., A Programmer's Introduction to LISP, American Elsevier, New York, New York, by "any logical human being 8 to 80." 1.5 Programmer's Cambridge, 1973. {4] Minsky, M., (ed), Semantic Information Processing, The M.1I.T. Press, Cambridge, Massachusetts, 1968. [5] Sikléssy, L. S., Let's Talk LISP, PrenticeHall, Englewood Cliffs, New Jersey, (in preparation). [6] Suppes, P., Introduction to Logic, Co., Princeton, New Jersey, 1957. {7] Weissman, C., LISP 1.5 Primer, Dickenson Publishing Co., Belmont, California, 1968. of the (and therefore REFERENCES [1] and and analyzing it is conceivable it) The Little is largely it is most important for approaching is a simple, and and solve language solution LISP tohe only function you must also be familiar with before you can interact with the computer is the function DEFINE. See page 15 of McCarthy [2] or page 67 of Weissman [6] for an example with DEFINE. to think about your problems. those and symbolic goal of this book as a programming of illustrations and McCarthy LISP technique interesting an easily it offers The powerful have some things As such processing. [1] and Minsky enjoyed guide aimed numeric the LISP Berkeley new study is a programmer's to computers because programmer. interesting introduction problems. of further hope you have digested for to LISP LISP LISPer to teach you a new way of to the understanding introduction have at the non-programmer. [5] offer computer these intrigued the a competent [4] The Little coverage [7], and Sikléssy [3] is a good are some any symbol manipulation. the to learn [6] offer a complete the next LISP. it would of all foresee certainly the book and learned references, Weissman we actually of you who and would to tackle do not You are understanding the subject. level but ready of you who Van Nostrand 58 456/54321 from tabs Ss ae ,ats eA