Lecture of 11/30/95 The Conclusion Today: o Course Evaluation o Administrivia o Course Summary -- Big Picture -- Syntax -- Process/Data Abstraction -- Problem Solving of Interesting Problems -- Non Functional Paradigm and Adv. Topics. o Q&A Session o What Next? Guest Lecturer NOTE: The following is more of an outline of the topics discussed. It certainly doesn't read like a book. Or like the normal course notes. 0.0 Course Evaluation Timeout for course evaluation. 1.0 Administrivia A lab evaluation form will show up on the newgroup named lab 10. Purely optional... 3.0 Course Summary 3.1 Big Picture You just started work at Yoyodyne Propulsion Systems. Your boss, Mr. John Bigboote (that's big-boot-tay, not big-booty ) , has tasked you with improving the program that implements the Oscillation Overthruster Control System of the spacecraft Yoyodyne is building. What kinds of properties would you expect ( hope ) to see in this program? What kinds of properites would you dread to see in this program? Abstraction / Problem Decompostion / Code written for Humans (or other sentient beings as the case may be )... why are these good things. Abstract Data Types ... what are they. Marvin Minsky once made a comment to the effect of a person doesn't really know a topic until they can describe it in more than one way ( or solve it in more than one fashion ). I guess a collorary would be folks who only have "hammers" and turn every problem they see into a "nail", 1). don't know enough about the world at large and 2) don't really know what a "hammer" is. for if they did they'd know what it was good for. In this like most of the programming in this class was done in the functional paradigm. 3.2 Syntax & Evaluation 3.2.1 Atoms and S-expressions 3.2.1.1 Atoms Symbols, Numbers, Strings, etc. Self evaluating things. 3.2.1.2 S-Expresions Left Paren. zero or more S-expressions and Right Paren. or An Atom. To evaluate. Get fcn. bound to first S-expression. Evalute the the other S-expressions. and pass those values to the function derived in step1. Repeat as neccessary. 3.2.3 Declaring functions and Special Forms Special Forms Some S-expression aren't evaluated using the normal evaluation rules. ( with rules and laws come exceptions ). There are some expressions in which evaluating all of the arguments would cause problems. Quote The special form QUOTE returns a value that represent the "print form" that is passed to it. Obviously QUOTE can't evaluate it's arguments. Defun Defun is a special form. Defun is used to create functions that may be invoked. (defun foo ( x y ) ( * x 2 y )) Note that in code that follows the functional paradigm each function is composed of ONE S-expression. That S-expression may have "sub" s-expression, but when the outermost one has finished evaluating then the function's value has been determined. 3.2.4 Control Without flow of control you can't write very interesting program. In Lisp you have a variety of mechanisms. The following are the basic ones. COND, IF , WHEN, etc. cond is really all you need. When there are only two conditions you can use IF. Under conditions where there is only one branch you can use WHEN and UNLESS ( not one branch usually implies some sort of side effect or non local flow of control is about to happen. This shouldn't appear in "normal" code that follows in the functional paradigm. 3.2.5 Recursion Decompose your problem into a smaller problem and some simple increment work. Tail, Augmenting , Car/Cdr (tree). (defun recur ...before work ... ( ....after work .... (recur ....before work .. .) ... after work ... ) ) Tail -- No "after work". After the recusive call returns no other function invocations need be done. The recursive call returns "the answer", at this point just return it. Here "the answer" is incrementally derived and form as the recursion progresses. Augmenting -- contains "after work". This "after work" involves augumenting the partial solution that the recursive call passes back with some incremental "stuff" to form a solution to the whole problem. This augmented solution is returned as the answer. Car/Cdr -- here the problem is divided into two ( or more ) subcomponents. This subcomponents are each targets of recursion. [ So is this tail or augmenting recursion ? ] 3.3 Process/Data Abstraction Since where are programming in the functional paradigm using a functional language, we can take advantage of functions being first class data. ( first class meaning you can create them. pass them as arguments, operate on them list any other datatype. ) Applicative Programming invoking functions apply , funcall applying a transformation to every item on a list mapcar Creating your own functions on the fly. Creating lexical closures... Creating "no name" special purpose functions .. some of whose components are determined a runtime ( i.e. dynamically ). Lambda 3.4 Problem Solving / Interesting Tasks Adv Datastructures. Heir. Data structures Graphs/Trees/ DFS, BFS. Best First and other Hueristic Searching. Minimax Adversarial search. 3.5 NonFunctional Paradigm and Adv. Topics o Destructive Binding.( or rebinding ) (set 'foo 3 ) (setq foo 3 ) special form for "nicer" syntax. (setf foo 3 ) Symbols are "bound" to values. Not assigned. In Algol/Pascal/C foo := bar The above copies the value from memory location lablel bar and places it into memory location label foo. Lisp don't copy anything. Symbols are "bound" ( or made to "refer to" ) values. You may think of Symbols as being in some sort of Symbol Table in the current package. This symbols can have an associated "mapping" to some value ( i.e. object, data structure ). These symbols themselves are objects. So SPACE-GHOST and DAVE-LETTERMAN can both point bound to TALK-SHOW-HOST. Or you could have the following DAVE-LETTERMAN ---> ( TALK-SHOW-HOST cbs ) ( i.e. (setf dave-letterman (list 'talk-show-host 'cbs ) ) ) Then make SPACE-GHOST refer to the same value. ? (setf space-ghost dave-letterman ) remember the second argument gets evaluated. So not we have SPACE-GHOST as a talk show host on CBS..... Ooops SPACE-GHOST's show is on the CARTOON-NETWORK. This won't do. ? (setf (nth 1 space-ghost ) 'cartoon-network) CARTOON-NETWORK So now SPACE-GHOST ---> ( TALK-SHOW-HOST CARTOON-NETWORK) But so does Dave!!! ? dave-letterman ( TALK-SHOW-HOST CARTOON-NETWORK ) Of course, with CBS in a ratings slump this may be a future move of "the Late Show" ! :-) o Lexical/Dynamic Scoping o Local Variables (let ( (var value ) (var2 value2 ) ) .... ) (let* ( (var value ) (var2 value2 ) ) ... ) LET* is really short form of (let ( (var value ) ) (let ( ( var2 value2 ) ) .... ) ) o Lexical Closures making/using functions that return functions. When the created function is dynamically invoked then it will evaluate in the same lexical environment in which it was created. Not in which it executes. o Iterative Constructs do , dotimes, dolist, The Loop Macro. o Macros add your own "special forms" to the language. Backquote can help you build expressions. Quote turns what is quoted into an expression. Backquote allows you to splice things into that expression. ? (setf test '(null foo ) ) (NULL FOO ) ? `(when ,test (print "yabba dabba doo" )) (WHEN (NULL FOO) (PRINT "yabba dabba doo")) ? When writing a macro start with when you want it to expand into. Put a backquote around it. replace the spots with the variables that refer to them. And then put a comma in front of the variable name to slice that value in. o Languages on Languages... read/print/eval loop. interpreting code. write a new language to solve the problem at hand in a more expressive fashion ( probably will need some macros or interpreters ). You should pick/design an ADT that helps you solve the problem at hand. The functions that comprise the interface are components of a "language" that can be used to express a solution. Sometimes just having these functions isn't enough and to make things cleaner you'd like to describe/construct a new language to solve the problem. At this point creating an interpreter would be nice. For instance ( someone contrived ). You could have a pattern language that when a pattern is matched code is executed. It would be interpreted by a function called pat-interp. Lets say that patterns are some symbols between two parens. And that '*' matched any symbol. and that ':m' and ':o" are variables that stand for some other sybmols. So the language could look like. (match pattern (case ( ( :m :m :m ) 3 ) ( ( * * :m) 1 ) ( ( * * * ) 0 ))) so that if the :m where bound to 'z and the then (pat-interp (match ( z z z) (case ( ( :m :m :m ) 3 ) ( ( * * :m) 1 ) ( ( * * * ) 0 ))) ) it would return 3. and if the pattern where ( x x z ) it would return 1. NOTE: You should know how the scheme interpreter works... o Declarative Programming "Just the facts Mam" as Joe Friday would put it. Encode the knowledge about you problem in general. Let the "environment" manipulate these facts to solve a specific problem. 4.0 What Next? Classes: "Lisp" 3361 AI 4344 (?) Natural Language "Abstraction/ADTs" every other 3XXX , 4XXXX , 5XXXX, 6XXX, 7XXX class you might take. Books: [FTP] means that code associated with the book is available via ftp. < blah blah > commentary about the book. Written in Scheme and quite good. Structure and Interpretation of Computer Programs Abelson and Sussman < One of those "classics of Computer Science" books. Like Knuth's Art of Programming, The "Dragon Book" , etc. Something that everyone should read at some point. > Essentials of Programming Languages Friedman , Wand , and Haynes < A whole book about build a very sophicated version(s) of the interpreter(s). Reams of code to read and understand. > The following Books Talk about Common of Lisp On Lisp Paul Graham [FTP] < Now that I know Lisp what can I do with it that I can't do in most other languages. > Common Lisp (??) Paul Graham [FTP] < brand new... probably a good book. > Object-Oriented Programming in Common Lisp: A Programmer's Guide to CLOS Sonya Keene < good intro to CLOS and what can do with it. > The following Books Talk about more AI kinds of applications of Lisp Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp. Peter Norvig [FTP] < Fully grok what's going on in this book and you should be able to read/write most any kind of lisp program. > Lisp, 3rd edition Winston and Horn. [FTP] On the WEB: Lisp Guildhall ( see class page). Association of Lisp Users: http:/www.cs.rochester.edu/u/miller/alu.html