Last update: February 16, 2010Introduction to LispDana NauDana Nau 1Outline♦ I assume you know enough about computer languages that youcan learn new ones quickly, so I’ll go pretty fast♦ If I go too fast, please say so and I’ll slow downAssignment:1. Get a TerpConnect account if you don’t already have one2. Start reading one or more of the following (you’ll need to figure outwhich parts correspond to my lecture)• ANSI Common Lisp - available at the bookstore• Common Lisp the Language, 2nd edition (URL on the class page)• Allegro Documentation (URL on the class page)3. Read Norvig’s tutorial on Lisp programming style (URL on the class page)Dana Nau 2What does “LISP” stand for??Dana Nau 3What does “LISP” stand for??A speech defect in which you can’t pronounce the letter ‘s’?Dana Nau 4What does “LISP” stand for??A speech defect in which you can’t pronounce the letter ‘s’?Looney Idiotic Stupid Professor?Dana Nau 5What does “LISP” stand for??A speech defect in which you can’t pronounce the letter ‘s’?Looney Idiotic Stupid Professor?Long Incomprehensible String of Parentheses?Dana Nau 6What does “LISP” stand for??A speech defect in which you can’t pronounce the letter ‘s’?Looney Idiotic Stupid Professor?Long Incomprehensible String of Parentheses?LISt Processing?Dana Nau 7What is LISP?Originated by John McCarthy in 1959 as an implementation of recursivefunction theory.The first language to have:• Conditionals - if-then-else constructs• A function type - functions are first-class objects• Recursion• Typed values rather than typed variables• Garbage collection• Programs made entirely of functional expressions that return values• A symbol type• Built-in extensibility• The whole language always available – programs can constructand execute other programs on the flyMost of these features have gradually been added to other languagesDana Nau 8LISP’s influence on other languagesIt seems to me that there have been two really clean, consistent mod-els of programming so far: the C model and the Lisp model. Thesetwo seem points of high ground, with swampy lowlands between them.As computers have grown more powerful, the new languages being de-veloped have been moving steadily toward the Lisp model. A popularrecipe for new programming languages in the past 20 years has been totake the C model of computing and add to it, piecemeal, parts takenfrom the Lisp model, like runtime typing and garbage collection.– Paul Graham, The Roots of Lisp, May 2001We were after the C++ programmers. We managed to drag a lot ofthem about halfway to Lisp.– Guy Steele, co-author of the Java specMore quotes at http://lispers.org/Dana Nau 9LISP applicationsAI programs often need to combine symbolic and numeric reasoning.Lisp is the best language I know for this.♦ Writing SHOP (my group’s AI planning system) took a few weeks in Lisp♦ Writing JSHOP (Java version of SHOP) took several monthsLisp is less used outside of AI, but there are several well-known LISP appli-cations:♦ AutoCAD - computer-aided design system♦ Emacs Lisp - Emacs’s extension language♦ ITA Software’s airline fare shopping engine - used by Orbitz♦ Parasolid - geometric modeling system♦ Remote Agent software - deployed on NASA’s Deep Space 1 (1998)♦ Script-Fu plugins for GIMP (GNU Image Manipulation Program)♦ Yahoo! Merchant Solutions - e-commerce softwareDana Nau 10Why learn LISP?Several universities teach Scheme (a dialect of Lisp) in their introductoryComputer Science classesLISP is worth learning for a different reason — the profound enlighten-ment experience you will have when you finally get it. That experiencewill make you a better programmer for the rest of your days, even ifyou never actually use LISP itself a lot.– Eric Raymond, How to Become a Hacker, 2001Dana Nau 11More about Lisp and Enlightenment . . .From http://xkcd.com/224Dana Nau 12Common Lisp♦ Lisp’s uniform syntax makes it very easily extensibleJust write new functions and include them when launching Lisp♦ This led many groups to create their own Lisp dialects:BBN-Lisp, Franz Lisp, Interlisp-10, Interlisp-D, Le-Lisp, Lisp 1.5,Lisp/370, Lisp Machine Lisp, Maclisp, NIL, Scheme, T, ZetaLisp, . . .⇒ problems with incompatibility♦ Purpose of Common Lisp: to unify the main dialectsThus it contains multiple constructs to do the same thingsYou’ll be using Allegro Common Lisp on solaris.grace.umd.eduDocumentation: links on the class pageDana Nau 13Launching Allegro Common LispLogin to solaris.grace.umd.edu using your TerpConnect accountYou’ll be using Allegro Common Lisp. Here is how to launch it:tap allegro81alispTo avoid having to type tap allegro81 every time you login, put it into the.cshrc.mine file in your home directoryRunning Common Lisp elsewhere:♦ Allegro Common Lisp is installed on some of the CS Dept computerse.g., the junkfood machines♦ You can also get a Common Lisp implementation for your own computerCheck “implementations” on the class pageBut make sure your program runs correctly using alisp onsolaris.grace.umd.edu, because that’s where we’ll test it.Dana Nau 14Starting Out♦ When you run Lisp, you’ll be in Lisp’s command-line interpreter♦ You type expressions, it evaluates them and prints the valuessporty:~: alisp. . . several lines of printout . . .CL-USER(1): (+ 2 3 5)10CL-USER(2): 55CL-USER(3): (print (+ 2 3 5))1010CL-USER(4): (exit); Exiting Lispsporty:~:Some Common Lisps also have GUIs; check the documentationDana Nau 15Atoms♦ Every Lisp object is either an atom or a list♦ Examples of atoms:numbers: 235.4 2e10 #x16 2/3variables: foo 2nd-place *foo*constants: pi t nil :keywordstrings, chars: "Hello!" #\aarrays: #(1 "foo" A) #1A(1 "foo" A) #2A((A B C) (1 2 3))structures: #s(person first-name dana last-name nau)♦ For Lisp atoms other than characters and strings, case is irrelevant:foo = FOO = Foo = FoO = . . .pi = Pi = PI = pI2e10 = 2E10Dana Nau 16Lists(a1a2a3. . . ak) =⇒...a1 a2 a3 akNILa1, a2, . . . , akmay be atoms or other listsA list of one element: (a) =⇒aNILThe empty list is called () or NIL; it’s both a list and an atomExamples:(235.4 (2e10 2/3) "Hello, there!" #(1 4.5 -7))(foo (bar ((baz)) asdf) :keyword)Dana Nau 17Dot notationIf the last pointer points to something other than nil, it’s printed with a dotbefore it(a b c d . e) =⇒a b c de(a b c d . NIL) = (a b c d)(a . b) =⇒abExample:(235.4 (2e10 2/3)