rA/0* QCR}PmJ@kvO.HG2~=9$-<`XH",+s7[+`a>~ y+\[89+ڃ5.H\!)!)i+.`aJ|{@".L9\Kb\bv"=y\(gLI.H/"9G j08(i, if you're curious, but it's moderatly hairy). One advantage of programming in this way is that it lets you modify the program easily. I.e. if I change the shape of mumble, all I have to do is to change GET-FROB and my code still works. Another advantage is that (SETF (LEADING-COEFFICIENT POLY) 15) is much easier to understand (and to write) than (RPLACA (CDDDR POLY) 15). As to how to use macros, here's a brief overview: (DEFUN ( MACRO) (FORM) ). FORM will get bound to the ENTIRE form being called. I.e. (DEFUN (FOO MACRO) (FORM) (PRINT FORM) 6) (FOO BAR) will print "(FOO BAR)". If you want argument destructuring, you can use (DEFMACRO FOO (ARG1 ARG2 AR3 . REST-OF-THE-ARGS) ....) DEFMACRO is a macro which expands into a defun which defines a macro. Sounds a little incestuous, but macros have no cultural taboos against such things. Probably 90% of all macros in advanced code are defined by macros. (my GET-FROB and LEADINg-COEFFICIENT examples are typically defined automatically by macros used to define what a "structure" looks like). When FOO is called, ARG1 through ARG3 will get bound to the first 3 arguments, and REST-OF-THE-ARGS (which is the CDR of the argument list in the DEFMACRO) will get bound to all the rest. (CDR = REST) Now, a macro's sole purpose in life is to compute up a piece of code to be used instead. So a macro should return some code, which will then be used instead of the macro. For example, say I use the CADR of a list to mean the leading coefficient of a polynomial. I might write (DEFMACRO LEADING-COEFFICIENT (POLY) (LIST 'CADR POLY)) Thus (LEADING-COEFFICIENT (CAR POLY-LIST)) will expand into (CADR (CAR POLY-LIST)) Note that generally, hand-written code would be written (CADAR POLY-LIST), which is of course, an abortion, and neither is understandable. They both compile identically the same. Now (LIST 'CADR POLY) is a little odd looking. Really, what you want to end up with should look like (CADR POLY) except instead of actualy having POLY there, we want POLY's value (remember, poly was bound to (CAR POLY-LIST) in our example). The BACK-QUOTE character is designed to help this situation. Backquote is like QUOTE, but it allow's the character COMMA to have special meaning: Wherever there is a comma, the VALUE of the immediately following thing is substituted. I.e. instead of (LIST 'CADR POLY), we could write `(CADR ,POLY), which looks much more like what we want to end up with. I don't feel like writting any more on this right now; suggest you digest this and come up with questions.  ******************************************************************************* Thank you all very much for your responses - it's great having so many people who have good ideas about computer science EDUCATION. Brian ******************************************************************************* DISTRIB: *DM, *MC, *ML, *AI EXPIRES: 12/05/78 00:36:22 BNH@MIT-ML 11/27/78 00:36:22 Re: Does anyone have a good practical simple recursion example? I used the usual x-factorial example when trying to explain recursion to a novice, and have been told to get a more practical example, as the factorial was "some abstract math exercise, or something". But the practical examples all seem too complicated. Does anybody know of a good SHORT practical application?  ******************************************************************************* JBROWN@MIT-MC 11/28/78 20:46:26 HOW ABOUT THIS: YOU HAVE A DEVICE X, WHICH IS MADE UP OF 2 A'S, 3 B'S AND A C. THESE ARE IN TURN MADE UP OF OTHER PARTS...NOW ASSUMING THAT EACH BASE PART (NOT MADE UP OF SOMETHING ELSE) COSTS SOME AMOUNT, AND THE OTHER THINGS COST SOME AMOUTN TO PUT TOGETHER, WHAT IS THE TOTAL COST OF AN X? THE EASIEST WAY TO DO THIS IS TO WRITE A RECURSIVE PROCEDURE THAT TAKES AS INPUT A PART NAME AND TOTALS THE COST BY CALLING ITSELF ON ALL OF THE COMPONENTS...WHEN IT GGETS A BASE PART, IT JUST RETURNS THE COST OF THE BASE PART. IS THAT CLEAR?  ED@MIT-AI 11/28/78 18:00:30 Sorry to add to the infinite flamage you already have, but something that I really like is the "How many ways are there to change a dollar bill?" Hack. The function takes one argument for the value to be changed and a list of the atomic values of money. At each level the function calls itself recursively until you reach pennies. ALAN@AI has a pre- written function for this purpose. (It has the unusual feature that it takes almost twice as long if you list the values of money in reverse order!)  PONDY@MIT-AI 11/28/78 11:58:15 did you hear ed fredkins example of a recursive definition of a peeled onion? something like: a peeled onion is a thing which when it is peeled is either a peeled onion or nothing.  PRATT@MIT-AI 11/28/78 09:27:48 The code I use to implement Rabin's fast Monte Carlo prime testing algorithm has two recursive routines in it. The first, mexpt(a,j), simply raises a to the power j, mod n (n is global, sorry). Whether you write this routine iteratively or recursively makes no detectable difference in speed because the cost of operating on thousand-bit numbers dominates. Since results from this routine have been published in Martin Gardner's column (Aug. 1978), one can hardly accuse a component of it of not being "practical," unless you insist that any routine that works with numbers is irrelevant mathematics. The file is AI:PRATT;PRIME If you definitely need a non-numerical example, why not define APPEND?  RDR@MIT-ML 11/28/78 00:13:57 I think a nice partition sort is a good example of recursion. It is hard enough that it makes the person appreciate not having to do anything othe than recursively call the existing routine when one has partitioned the data to b sorted.  BAK@MIT-MC 11/27/78 22:56:53 This depends on what data structures you are allowing. If its just numbers then there isn't anything more "practical" (whatever that means) than factorial. If you allow lists then there's lots. Pattern matchers as required for the last 6.030 problem set are very simple and impressive to novices. There are all sorts of examples like this.  MSS@MIT-MC 11/27/78 20:34:12 If they are inclined towards language theory, you might try explaining recursive decent methods for parsing expressions.  ELBOW@MIT-ML 11/27/78 20:13:44 Try the Tower of Hanoi problem: not exactly practical, but not any more mathematical than a host of other puzzle-games. To move a stack of n+1 discs from peg A to peg B, move n discs from A to C, move the remaining one from A to B, and move n from C to B. This has the nice feature that two recursive calls are required in the so;lution, indicating that in fact the solution requires exponentially many steps.  KMP@MIT-MC 11/27/78 20:12:16 Joe Wiezenbaum uses on in beginning PL/1 course here that's pretty nice: Define CLIMB-STAIRS: [1] Go up one step. [2] If at top of stairs then done else CLIMB-STAIRS. This generalizes to any construct that one might normally view as a loop. It exemplifies the philosophy of 'living each day as you get to it'... If you get any other good ideas, can you send them to me or let me know where you are dumping the replies you get? We have a lisp teaching program here on MC that helps some in learning Lisp - but one of the hardest things is coming up with good simple problems. If you want a complex one - tho' very elegant - look in MC:TEACH;PROBLM HANOI for a description of the recursive solution to the tower of hanoi problem. --kmp  LOUI@MIT-MC 11/27/78 19:02:38 Hoare's QUICKSORT algorithm involves recursion in a simple, practical way. See page 94 of the text by Aho, Hopcroft, and Ullman.  RBR@MIT-AI 11/27/78 18:04:31 The Tower of Hanoi puzzle  Date: 27 Nov 1978 1712-EST From: MP at MIT-DMS (Mark A. Plotnick) Subject: Short recursion example that's not like the abstract" factorial: Message-id: <[MIT-DMS].93635> 1) Fibonacci numbers 2) n**2 or n**3 (ex: n**2 = (n-1)**2 + 2n - 1)  RIVEST@MIT-ML 11/27/78 16:50:21 My favorite example is perhaps too complicated for a real novice, but I've used it in an introductory programming class with real success. The example is good at something that most examples are not, which is showing where recursion can be really USEFUL, as opposed to just elegant (e.g. factorial, which can of course be done by iteration as easily). You are given an n x n matrix of 0's and 1's obtained from a digitized TV camera attached to a microscope. The zeros represent clear fluid and the 1's correspond to red blood cells. We want to count the number of red blood cells, where a "red blood cell" is a connected group of 1's. (only count vertical or horizontal connections). For simplicitiy assume the border M(i,j) where i or j is equal to 0 or n-1, is equal to zeros. DEFINE "BLOOD COUNT"; NEW COUNT; COUNT := 0; FOR I IN 0 TO N-1 DO FOR J IN 0 TO N-1 DO IF M(I,J) NE 0 THEN (COUNT:=COUNT+1; ERASE-CELL-AT(I,J)); COUNT $ DEFINE "ERASE-CELL-AT"(I,J); IF M(I,J) = 0 THEN RETURN; M(I,J):=0; ERASE-CELL-AT(I,J-1); ERASE-CELL-AT(I,J+1); ERASE-CELL-AT(I-1,J); ERASE-CELL-AT(I+1,J) $ The example is written in CGOL. It's a good introductory example since the recursion is easy to follow graphically on a sample "blood sample", and since it is rather difficult to program this in any other fasion. Comments appreciated. Ron Rivest  MASEK@MIT-ML 11/27/78 13:26:02 I think the best practical example is traversing a tree. This is something which is very difficult to do iteratively, but works much nicer recursively. bill masek  Date: 27 Nov 1978 1227-EST From: WJN at MIT-DMS (Wayne Noss) I like the Towers of Hanoi problem as an example of recursion, but a layman might consider it more obscure than factorials unless he's into that sort of game. A recursive definition of addition might do: (DEFUN PLUS (A B) (COND ((EQUAL B 0) A) (PLUS (SUCCESSOR A) (PREDECESSOR B)))) (DEFUN SUCCESSOR (X) (1+ X)) (DEFUN PREDECESSOR (X) (1- X)) I'd also be interested if anyone can suggest any really good examples of recursion understandable at an elementary level which do not seem contrived. Final suggestion: algebraic expression evaluation (for parenthesized expressions)--if the person knows algebra, chances are (s)he unconsciously uses recursion to understand the meaning of x*(y+z), etc. Wayne Noss  DOYLE@MIT-AI 11/27/78 11:52:54 How about "if you can't solve a problem (answer a complaint, etc.) yourself, pass it on to your superior" as an application of recursion in business management.  EF@MIT-AI 11/27/78 10:43:29 I have an example, a recursive definition of an onion, which is pretty good in english and which exists as a LISP function ONIONP, a predicate to tell if something is an onion.  RAM@MIT-MC 11/27/78 09:02:28 Most simple recursion is easily programmed iteratively, but maybe not by a novice. Here are some reasonably practical ones: 1. The Hermite polynomials: H(0,x) = 1 , H(1,x) =2x, h(n,x) =2xH(n-1,x)-2(n-1)H(n-2,x). Many solutions to D.E.'s are recursively defined and so more easily programmed that way(usually at hideous execution cost). 2. The Tower of Hanoi (see Grogono, Programming in Pascal, Addison Wesley). 3. the greatest common divisor gcd(m,n of two integers m and n is also the gcd of n and m mod n, giving : FUNCTION gcd(m,n); BEGIN if n=0 then gcd :=m else gcd := gcd(n, m mod n) END; Generally the power of recursion will not show its head before linked list traversal.  RBRN@MIT-AI 11/27/78 09:54:43 A good, simple recursion example is a depth-first tree search. If you don't like using data-structures, then you have to do math exercises.  RSTRAU@MIT-MC 11/27/78 07:26:19 sure- use the calculator example: you pass arguments to a procedure that will evaluate the sum of two terms, but one of the terms itself is composed of two terms. (You can polish it up though) Is quicksort really too difficult?... You wanted simple... randy  EAK@MIT-MC 11/27/78 03:34:41 A very pratical recursion example is a decimal no. printer: (defun print10 (n) (cond ((not (= (// n 10) 0)) (print10 (// n 10)))) (prin1 (\ n 10))) If he doesn't like computer examples, there is always the recursive solution of the Tower of Hanoi problem. Also Seymour Papert has a nice recursive description of juggling. Binary searching can be thought of recursively, and an everyday use of binary searching is looking up a word in a dictionary. In general recursion is most interesting when any iterative solutions require space proportional to the no. of iterations. For example the iterative solution to tree walking basically requires maintaining a stack (barring modification of the tree).  MRC@MIT-AI 11/27/78 06:47:54 Factorial is a perfectly good and simple example, as long as factorial itself is expressed simply. Another "practical" example is the standard way one outputs an integer in pdp10 assembly language programming. This routine outputs a signed integer in accumulator X. Accumulator Y is scratch and is also X+1 (ie, if X is AC4, Y is AC5). Accumulator P is a stack pointer pointing to a reasonable size stack: NUMOUT: JUMPGE X,NUMOU1 ; no minus sign if positive MOVMS X OUTUUO ["-] ; replace with appropriate output system call NUMOU1: IDIVI X,10. ; replace 10. with desired base HRLM Y,(P) SKIPE X PUSHJ P,NUMOU1 HLRZ X,(P) ADDI X,"0 ; convert to ASCII OUTUUO X POPJ P, In this case, each remainder is stored in the (unused) left half of the PC's saved on the stack. Digits are extracted in this way until a division by the base returns a quotient of 0. At that point it gets each digit back and outputs it. The return call at the end of each digit output "returns" to the beginning of the second part of the output routine. In Fortranese it might be something like (if Fortran allowed recursion): SUBROUTINE NUMOUT(X) Y=REMAINDER(X=X/10) IF (X.NE.0) CALL NUMOUT (X) WRITE, Y RETURN  RPOOR@MIT-MC 11/27/78 02:06:59 Another classic example for demontrating recursion is sorting a list, using quicksort. That is the first one I was shown. However, such simple things as counting, or the markings on a ruler (1/8, 1/4, 3/8, 1/2, etc) can be described as recursive procedures.  DUFFEY@MIT-AI 11/27/78 03:31:47 Here are my nominations for simple, short justifiable recursive examples. 1. APPEND (defun append (x y) (cond ((null x) y) (t (cons (car x) (append (cdr x) y))))) 2. ASSOC (defun assoc (key a-list) (cond ((null a-list) nil) ((equal key (caar a-list)) (car a-list)) (t (assoc key (cdr a-list))))) 3. GCD (defun gcd (x y) (cond ((greaterp x y) (gcd y x)) ((zerop (remainder y x)) x) (t (gcd x (remainder y x))))) This might be in the category of "an abstract math exercise" but you might point out its use in rational arithmetic, which some matrix packages use to increase precision. 4. MERGE (defun merge (item sorted-list) (cond ((null sorted-list) (list item)) ((lessp item (car sorted-list)) (cons item sorted-list)) (t (cons (car sorted-list) (merge item (cdr sorted-list)))))) 5. SORT (defun sort (lst) (cond ((null lst) nil) (t (merge (car lst) (sort (cdr lst)))))) 6. You can hair up 3 and 4 slightly to develop a complete tournament sort. 7. Depth-first or breadth-first search. 8. Simple ALGOL/60 aritmetic expression syntax checker. (Note: this would use several mutual recursive functions, rather than a self recursive one.) 9. Infix to Polish translation. 10. A function which symbolically multiplies 2 polynomials together. Good Luck! Roger Duffey  KS@MIT-MC 12/02/78 01:02:38 Re: Recursion example The complaint you received is a familiar one. I eventually switched to using the number printing example. If you are not familiar with the usual recursive implementation of a decimal integer printing routine on PDP-10's, it looks like this: proc decimalPrint(n); begin integer digit; digit _ n mod 10; n _ floor(n/10); comment I.e., usual integer divide; if n > 0 then decimalPrint(n); print("0"+digit); comment I.e., digit becomes ascii; return; end; This example of recursion is one that is much worse in iterative versions, and in fact is the implementation of choice. I believe it is simple and well motivated. No abstract data structures, such as trees, need be introduced; only the familiar integers and characters are involved. If you find better or comparable examples, I would appreciate your passing them on to me. -- Ken Shoemake  RAF@MIT-MC 12/01/78 21:03:19 Re: Does anyone have a good practical simple recursion example? Try defining the member function. also good is Replace Replace x y list will replace toplevel occurences of x with y in list. I am using these examples for a class... think they are simple enough.  SROSS@MIT-AI 11/30/78 23:46:02 Re: Does anyone have a good practical simple recursion example? I used the following example in an article about the lisp machine, just to give a flavor of how LISP looks. Use double-recursion to retrieve the fringe of a binary tree. Assume each non-fringe node has a plist giving its direct descendants. GET-FRINGE of any node returns the fringe of that subtree. The function is only about four lines long, and is prototypical of databases organized around generalization hierarchies. A variant is to use single recursion and a test for inequality ... making the tree behave as a binary index into a database. Hope you like this idea...let me know what else people send you. - Sandy  RWK@MIT-MC 11/30/78 05:40:55 Re: MC:TEACH;BNH REPLIE Anyway, I have a couple comments to add to all that. 1) Factorial is actually quite reasonable as a practical example. It is not an obscure mathematical example, it is VERY fundamental and practical. For example, if your friend plays poker, if he doesn't know about factorials, I'd LOVE to play poker with him. Factorials are fundamental to probablity theory. 2) One thing I'm really quite suprised that no-one mentioned (except for Roger Duffey's mention of infix-to-polish conversion) is the general class of parsers. Consider one of the simplest parsers; a parser for LISP. Here's a simplified LISP parser for you: (defun READ () (throw-away-spaces-and-comments) ;we can have spaces and comments anywhere (cond ((eq (look-at-next-significant-character) '|(|) ;start of a list? (input-next-character) ;throw away the close-paren (read-a-list)) (T (read-an-atom)))) (defun read-a-list () (throw-away-spaces-and-comments) ;we can have spaces and comments anywhere (cond ((eq (look-at-next-significant-character) '|)|) ;end of the list? (input-next-character) ;throw away the close-paren nil) ;then return NIL for the tail ((eq (look-at-next-significant-character) '|.|) ;dotted pair? (input-next-character) ;throw away the dot (read)) ;and return just what goes in the CDR (T ;otherwise we return a list, by recursing (cons (read) ;reading an item for the CAR (read-a-list))))) ;and for the CDR READ-AN-ATOM is easily defined, given a function to take a list of characters and give you an atom (IMPLODE in MACLISP). INPUT-NEXT-CHARACTER is TYI in MACLISP. The LOOK-AT-NEXT-SIGNIFICANT-CHARACTER and THROW-AWAY-SPACES-AND-COMMENTS are combined in the TYIPEEK function in MACLISP. But in general, parsers of any variety, not just for the simple syntax of LISP, require recursion. Also, compilers which understand and optimize the output of parsers need recursion to deal with the output of parsers--which are, of course, trees showing the structure of the expressions being input. I hope this helps somewhat. It really doesn't sound like your friend is open-minded to new ideas, but I hope he'll thaw to the idea of recursion. It really is one of the most powerful concepts in computer science.  RTo: SAM Re: Bibliography --Text follows this line-- The following are references that come to mind offhand on the subject of Lisp with which I have had first-hand experience and my impressions of each. (There are other references of which I have heard but that I have no way to comment so I will omit for now.) I hope you'll find this useful. -kmp John R. Allen: ``Anatomy of Lisp,'' McGraw-Hill, Inc., 1978. This is a not-unrespectable survey of Lisp issues, but to read it requires considerable sophistication in computer languages. Not for average consumption. Some of the things it seems to assume about the reader's background make one wonder why other parts of the text were included (like a second-year calculus text that begins with a review of high-school algebra -- only the beginner-level stuff is sort of mixed in throughout with the high-level stuff). It also uses meta-notation for lisp, where you say script-t for T, script-f for NIL, concat for CONS, [...; ...; ...;] for a COND form, etc. That notation is not implemented anywhere has no useful purpose in my opinion. Bernard Greenberg: ``Notes on the Programming Language Lisp,'' Student Information Processing Board, MIT, 1978. This is a not-really-professional quality but recommended work for beginners. It takes what I and many others advocate as the correct (strongly object-oriented) approach to what Lisp is all about. Just notes -- not a book, but takes one through a complete buildup. It also has the advantage of being explicitly about Maclisp. Despite its crude form, probably the best teaching text around. John McCarthy: ``Lisp 1.5 Programmer's Manual,'' MIT Press, Cambridge, MA, August, 1962 Obsolete. Most of the constructs described are out of date in one way or another. Useful to provide historical insight; interesting reading if you're a Lisp fanatic; but not really practical for anything else. David A. Moon: ``Maclisp Reference Manual,'' Laboratory for Computer Science, MIT, March 1974. Not organized in teaching form but useful from the point of view that it offers about all the documentation you're likely to find about Maclisp in so small a space. Laurent Siklossy: ``Let's Talk Lisp,'' Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1976. Not really recommended. The programming techniques taught are primitive and outmoded. The lisp referred to is pretty old. It uses EVALQUOTE notation all over the place which I don't think is a good formalism. It makes some attempt to distinguish between things that are likely to vary from system to system and things that are pretty standard. Indentation style is lousy. Treatment of newly evolving issues in macros, fexprs are poor to non-existent. Guy L. Steele, Jr. and Gerald J. Sussman: ``The Revised Report on SCHEME, A Dialect of Lisp,'' AI Memo 452, Artificial Intelligence Laboratory, MIT, January 1978. Recommended not for beginning programmers but for those having pretty much mastered most of the major aspects and looking for breadth. Scheme is quite a bit separated from `normal' Lisp dialects but is interesting in its own right. A number of other papers on Lisp- and Scheme-related topics have been published by Sussman/Steele as well, also as AI Memos. Warren Teitelman: ``Interlisp Reference Manual,'' Xerox Palo Alto Research Center, October 1978. Amazingly detailed report on an amazingly hairy language. I question whether the everything-but-the-kitchen-sink aspect of InterLisp is really the right way to go, but for those interested in Interlisp, this manual has quite a bit of detail. The manual explicitly states that it is not an introduction to Lisp, but rather a reference manual. Daniel Weinreb and David Moon: ``Lisp Machine Manual,'' Artificial Intelligence Laboratory, MIT, January 1979. A useful but becoming-more-and-more-incomplete-all-the-time description of Lisp Machine lisp. Much of the information in this manual also applies to some of the undocumented features of Maclisp, though it doesn't always say so where that is true, so it isn't as useful in that respect as it could be (that, of course, was not the authors' purpose). Fairly interesting also as a survey of what new things are available in state-of-the-art Lisp systems. Jon L. White: ``NIL---A Perspective'', 1979 Macsyma Users' Conference Proceedings; Washington, DC; June 20-22, 1979 The only existing paper on the language NIL, a direct Maclisp descendant intended to replace Maclisp on the Vax. Other documentation is available online on MC and will hopefully become a manual within time, but that is likely to be away off yet. This paper is a brief overview of proposed plans for NIL that make it distinct from Maclisp, but doesn't really go into much detail. Patrick Winston and Berthold K. P. Horn: ``LISP,'' Draft #3 Artificial Intelligence Laboratory, MIT, unpublished, 1979. This book is intended as a Lisp manual for beginning Lisp students on the college level with AI applications. The presentation which brings one from the 0-level to the level of programming I think is a little steep; and the presentation is about as far from the Greenberg approach as one can get -- being more abstract than it should be and not presenting uniqueness of identity and other useful issues in the way that Greenberg does (which I have said I prefer). The main redeeming feature of the book is its copious display of non-trivial applications in interesting domains. The coding style in the examples is primitive and not really exemplary of modern coding style, but that may improve in subsequent drafts as there has been some feedback received by Winston/Horn on these issues to which they have been responsive. rhaps it would go something lik! e this: Loop over all 20 items adding each item to the list. level 2: To add an item to the list, search down the ALIDS ST....etc... ok, now, questions? S:Yes, who in heavens name is in this 5 ways/// 4 way/// 5 way link? There is Me, Rwk, Hic, Hic0 and T45... But I think I understand what you just said... >H:ok, there is myself (hic), stever, rwk, a pty with a wallpaper file, and a decwriter in on this. s:but I thought that you couldn't wall paper a link... (or rwk gave me some exlanation of why you can not once) R: What I have going is a PTY which is remembering all the 8-buit ///bit codes ITS is sending it. I have a program which can interpret this back again.....it's al inda odd. But back to the discussion.... The idea (RWK still) here is that a representation.....////// cancel, a specific data structure has associated with it a set of algorithms, I! .e. abst/////operations on that data structurethat are somehow meaningful. (just a sec) Clearly an algorithm which added a randomly chosen number to each item in the table of inventory itmes would not be at all meaningful! But if that were a table with some other meaning, say in a monte-carlo simulation, it might be a meaningful opert/ation. But then you can operate on a different level, and make use of these basic operations (the ones deemed useful, like adding a number to a specifi ai///item) to do something useful. Like, if we use the ALIST representation: In LISP, we have the primitive data-type LIST.,... Lets say CONS, which has the operations CAR and CDR and RPLACD and we can take the ALIST and get a CONS by doing ASSQ, I.e. (ASSQ 'FUES inventory-list) and we can do ///set FOo the///to that result and do (RPLACD FOO (+ 100 (CDR FOO))) .... This correspons/ds to something meaningfull...I.e. we just got a shipment of fuses. ? (S) Ok, I know what assoc does but what does assq do? I assume it returns a list of some sort, maybe list///like assoc or something? >Exactly like ASSOC, except it uses EQ instead of EQUALS for the test. You may pretend I used ASSOC for now, ok? ok... OK. Now we have roughly defined an operaton on our INVENTORY-LIST data structure, using a lower level of abstraction (actually TWO of them, the CONS and the alist...) and we can use it to define an algorithm on even a higher levl, say we have another data structure wich looks like an inventory, but //(i.e. it shares the same representation and operations), but has the meaning of "SHIPPING PAPERS" i.e. it is an ALIST of items recieved and how many are in the shipment. With the ALIST operations and the add-to-tiem operation, we could easily figure out the algorithm (or rather any of several algorithms) to add this shipment to our inventory! This isn't a program, a program is a representation for an algorithm and it's data structures, possibly spaning several levl///levles. We're talking abstractly here, before a translation to a specification language, like LISP or ASSEMBLER or whatever. S:No comment, I am rather surprised how clear this seems to be (now) h: GOOD! (I hope what you think we said is what we think we said....) But,. I think we are really winning....ok, now, I think we should discuss the other question that RWK asked at the beginning....Why data structures? Why a particular structure rather than another one? >S:Because, as he said, an algorithm built for one type of structure will not work (correctly) on another type of c/structure. >Um...ok, well, why is it important at all to discuss it....that seemsto be clear...things written for numbers can't work on letters, right... but why ex >(S) who is now typing? >H: sorry, I am....but why explain things in terms of them explicitly...what is the importance...do you have any ideas? S:thinking...importance of what specifically? H:OK, I think I better explain some more....perhaps you don;t see what I'm getting at ... OK, well, we can simply say that the algorithm has to work with the data we have....we have names and numbers, so we say to our programmer! : Ok, we have names and numbers, go write some code to do this and do that eetc.... No thought as to whether to use an ALIST or arrays or anything like that.... do you have any ideas as to why such considerations are important? S:I would say for the easiest way of getting at the data (probably depending on the language). H:Hmmm...yes, the particular language is important at some lower level, also, at a higher level: We want to be able to understand what is going on. We don;t weant to sho chose a data-structure that obscures the meaning behind the thing we are repesenting. ALISTs are good to use with the inventory frob..why>/ ?? well, because they maintain the association between the names of the objects and the quantity...th! ey are inseperably tied together by the DATA STRUCTURE....ok so far? Any comments or additions?S:none by m3/e... R:?Hmm. OK, well, I'd like to hit at this from the other side, for balance. When Howard said "why is ///are such considerations important?" (as to whether to use an ALIST or ARRAYS), he let ///led you to look at some important points about data structures. Now, let me present a situation. Somebody says, "W//OK, we have names and numbers, go write some code to do this and do that, etc.". But he doesn't specify the data structure. H//Note that he didn't HAVE to specify the data structure for you to understand what it was that he wanted. Clearly at some point you have to deal with the data in some data structure, but we appear to be free to deal with it in whatever structure we chose. So he was talking about algorithms at a higher level of meaning, and leaving the "implementational details" to us, as a black box. Thus, data structures allow us to deal with things in large pice//pieces, he told us what was wanted without giving us a 20 page program! But at some point that program must be written, but nobody can undert/stand a 20 b/page program! T//Not at //all at one time, that is. But if the program is structure, /d in such a way that you can deal with large pieces as aw//a whole, and then ///the whole is of a simple enough form, then us mere humans can deal with it. and the pices //pieces may then be split up, and again, we can deal with them. The way I just described is refered to as "top-down", as in top down design, etc. There is also botom up, which is essentially the same idea, I.e. you deal with pices//pieces of a complexity you can handle, and don't look at the inards of things you aren't working with.Hence, we don't re-wro/ite our little ADD-TO-INVENTORY proceedure ever /y time we need it, it is a black box. (as)>dis//digesting...OK, well note that when///tour ADD-TO-INVENTORY proceedure is really a part of our INE////INVENTORY abstraction, and as such, it isn't very complex. It essentially has one operation and one data-type, wi//.... Thep/// The pieces are themselves also very simple. Just a couple of operations (CAR, CDR, ASSOC, RPLACD), (and +), and a single data/////3 data-types, symbols, numbers, and CONS's. We have creates/d something that is SIMPLER than what we started out with, an//ina very real sense! Got it! (ok, pause for HIC to catch up) (p oh, where is he? Wha//where WAS he?) >Talking to BKERNS. (he jusyt wandard away...he's back.) OK, I think we've about covered it. I think the way to go is to //for you to give us any questions you have, and we will try to cons up some homework for you and then we can talk about future agenda, ok? Ok... Sonds good... I have no real questions however. >Well, we aren't ready yet, so I'd recomend that you try to come up with 3 questions. I'm sure you can come up with some, perhaps on the fringes of what we have been talking about, perhaps a little specualtion? thing///thinking...hmm, I honestly can't think of anything right now. Do you know about complex numbers/ ? Yes, I do... I think, those are the numbers dealing with i? >Yes. Do you know how to add, subtract, multiply, divide them? No, all I know is what they are. I've never worked with them at all. >OK, well, we'll have to come up with another idea...HIC just did. Fractions. You know about them! Yes! OK, so what we'll do is give you a little homework problem involving adding, subtracting, dividing, multiply! ing fractions, ok? We're still working out the details of what the assignment is, but does that sound like something that you could handle if it were a little more specific? T hello? >OK. What we have decided on, is a trivial fraction-calculator. I'll give you the over-all goal first, so you s/have an idea what the whole think/g is for. The final program (actually there will be 3 of them, for 3 different kinds of data-structures) will read the name//////will read (via (READ) ), 2 of your data-stur/ctures and then the name ofan operation, ADD, SUBTRACT, MULTIPLY, DIVIDE, and EXPONENTIATE. It will then perform these operations on them and print the result. This is just the final goal, not the assignment, ok? ok... V/ >OK, now to the meat of the s//assignment. First off, LISP has a representatio! n for numbers call FIXNUM's, essentially, integers. That's one of the data-types! . Then////You are to design 2 data strucut///structures for representation of fractions , of your own chosing, (with the fractio///////. These representations should be in terms of LISP! Bu///// The ///? would you like to start over? With all these ///'s and sticking paper uou//you have managed to lose me. >Sorry. Where would you like me to start? Right after FIXNUMs >OK. You are to design two data structures for representation of FRAT/// FRACTIONS. The (getting distraction) OK. The co//choice of representation i/is your own, you have all of LISP at your disposal, but you should justify your choices. Part of the abstraction of fractions i//are the operations of additionand subraction. (and multiplication and division). You should write functions which perform these operations for each of the data-types. (for the fractio o nee:oAredi/efine PLUS, DIFiECE, etc...) Catem sozhng bezre PLUS, etc, I.e. name them such that woehPcn asse the;h the'aK tyPtey're for! Then, Ayou h=ultipqion, ;an deweAexponition!b an ;eer, tz s....8 t I h=o ide(4o to d3rction;xpone4ion>d< know7Ad (1/27  yD you know how to do (1/2)^4 ? ye:.]ok, i߾K, I figured yo2i nkow9eh/where, youbut just F toB UT>>! I do not know how I would do (1/2)^6/7 ˗Y}You missed something that I sa9.]."(Byw ntegeKtat is˗.])(/" I odon'th meanwAhave to do (1/276_7) ..E ok. continue.>OK, sowAdo unysand how to do that operation. $e the only thing remaining is to wr=2he top-level proceedure, that doesthing4 first number: and readh:h firs7uberse{dAnumbeNad ra/s it[e=4: and readh:heation0 so on ////does it, and printsh result (i4_//jusPINT ...) tPrsult, don't boty ryingoAdo an=4ig fance //fancy with represe/////printed representations, u//u//=last u4Ayou have the re}o it wg!!!! hmmph.t now4eAonly | can{e think of to represent fXwcions be w=4 n ali}o (... .S or a0ay (b don'5w arr>Phndling)... do i only haved one of them? >>>>>>>>>>>>>>>ϟ>}>>>>>> Do yAaboutyrys...wyay, something of the form ( )] is a two-l<. (nst nawgA////termin7...) oh'] Now how the heck wo2 hey input (3rction4ouldn'Ewnt to0 to take apart ;aPo3o>/M Yes, ex8l. The representations yo1yPmy tur7 to be raty zv< ince 2epresentation s f folAwhat 2eaning of what you're doing. But I'm sure yPcn come u //up with tsVat diٲnt data-structures that {eAthe same meanin놊 am dqtul... I am not that familiar with l<,Aall IAthinkW woub a cons or a n SAwell te bes1yu can, if you c;Athink notheKjst d4Afor one, and thw'll help you get another.' oke//whe4Ait "dQ? >Whe< get =dne! 2oonerwAget i2oe, etc. Where Hey, that's not too cool....I'd hate toAyou gito trouble andAbe abPt finish this! ) ecometat you coo4C Ok.AThe ry I am7g it is so thatPd not r so long... Today I {eA(2iferen9e{ or using #7...U4iylso, btw, the first time (4ae used thih7uber oH0 number other than #3 so I can stop as easily as (1 snap|ingers... >Well, I'll feel a lot b:e whenwAdo! Ok, I am going to imk foH0omentwdAz0e por.] >ok, the link will be here wP/_when ;et back... ok, tbbCEB#R*6a  LINh#RM SkE Bleep! This t<wll ncose the connect; hese |Aso I p wit)ver still logged in and when I logw {eyEAlreaPlgged ;s log you in as STEVE0", a it happened 2 times which is what happened ww you twkd me mysteZwW Pa{w[A;efore you gunned them down...but I guess you didn'Ese that! S;7O< log out before4onnecting!ߍ True, sigh...Pdnno, m(aybe I'l9i my init file t7o priay options but j o it because the reason i don't log out is mainly that my init file is long... I should change it, but whatever. Hmm,  >thing to do is :DETACH, then when you log bac k in, it'll do the --attach your! ...--- Ah, yes, i forgot... Ok, will do... Would you like to talk a bit more about this trip now that I have you in a link? >Not yet...We've still got a little giv//bit of unfinished busigness... I won't be here this weekend, Idon't think. (Going to Woods Hole again...) If you can't get parts of it to us this week, I'll look at it when I get back.But HIC will g HIC is going to be ca//gone this weekend too! And next week! I'll be back though, perhaps as late as tues, but probably monday afternoon. So do what you can, and that's our scheduals....comments? Not really, where is HIC goimg///going? >He's going to the arm-pit of the US, to visit his parents. Where's that? ?NJ Ah, I see... Hmm, next weekend's going to be boring... Whanotet ver//.not for m! E!!! For me it will be. >Well, yuou//you can do that assignment.... I doubt seriously that it'll take more than 2 much less 72 hours. >(BTW, I will no longer have net access after around May 1st. >Sniff<) >YEs, Well, May 1 is a ways away.... We'll see what happens then. Actually, talk about the trip can wat//wait a bit too, I'll f//set up my schedual around that too. Let's concentrate on the present! Anyway, All the details you've mentioned seem a-ok with me. Oh, BTW, I'd gues that it//this assignment may take around 4-5 hours, so do allow plenty of time! Best to do it early! (Don't forget comments in your program!) Yes, well, maybe I won't be getting a TTY next weekend too... We'll see... Ok, I'll do it sometime soon. Maybe ton//tomog/// tomorrow after school. >OK, whenever you get it done I'll have a look at it, HIC too. We'll try to be prompt in getting back to you with feedback (and a new assignment...) Ok... (Mumble) >ok, well HIC & I both have things to do, and n^tag LAMBDA Lesson LAMBDA, Version 1 Kent M. Pitman, 3/28/79 LAMBDA is not a function (unless you define it as one). It is used to describe a function. It represents a binding context in which a definition can be executed. A simple example should serve to make this clearer. A function which takes two args as inputs and adds them may be described in LAMBDA notation as follows: (LAMBDA (VALUE1 VALUE2) (PLUS VALUE1 VALUE2)) As we said, however, this is a functional description, hence it must be used as a function. Just saying something like (PRINT (LAMBDA (VALUE1 VALUE2) (PLUS VALUE1 VALUE2))) is as meaningless as saying (PRINT PLUS). eval (cond ((not (boundp 'b)) (setq B 3.))) () Functional operators must be applied. Thus the proper way to use LAMBDA is the same way as you would use any function. Since you would say (PLUS 7. B) you must also put LAMBDA expressions in the CAR of the list, like so: ((LAMBDA (VALUE1 VALUE2) (PLUS VALUE1 VALUE2)) 7. B) eval (cond ((not (numberp B)) (Cursorpos 'a tyo) (princ '|Don't use B in your tries since you haven't got it set| TYO) (terpri tyo) (princ '|to a number!| TYO))) () try A form which contains a LAMBDA expression (or LAMBDA operator as it may be called) applied to some arguments is called a LAMBDA combination. LAMBDA expressions have the general form: (LAMBDA ). LAMBDA combinations have the general form: ((LAMBDA ) ... ), where the number of 's must be equal to the number of elements in the bound variable list. What happens when a LAMBDA combination is executed in the following order and manner: (1) The actual args, ... in the above example, are evaluated in order from left to right. (2) When all values have been computed, the values are bound locally to each of the respective elements in the bound variable list. (3) The body of the LAMBDA expression is executed in a context in which the local variables are bound to these values. (4) The value returned by the last expression in a LAMBDA will be returned from a LAMBDA. Note that this means that there may be more than one statement in the LAMBDA body. eg, (CONS ((LAMBDA (X) (PRINT X) X) A) ((LAMBDA (X) (PRINT X) X) B)) is just like (CONS A B) but it will also print the value of A and B in the process. Lambda may have some use in another case, which is the MAP'ing functions. For example, if you wish to apply a function to every element of a list, you can do (MAPCAR 'CAR '((A) (B C) (D E F))) which returns (A B D). try If the function that you desired to map was not defined somewhere and was for single time application, you might just want to use a LAMBDA rather than giving the function a name. For example, to take a list and return a list which had 10 added to every element in the list, you might want to do: (MAPCAR '(LAMBDA (X) (+ X 10)) '(1 2 3)) which returns (11 12 13). Some lisp's define that LAMBDA is a self-quoting structure so that (LAMBDA (X) X) for instance would eval to itself. If you are more comfortable with it doing so, you may feel free to use the following incantation to make it be so: (DEFUN LAMBDA MACRO (X) (LIST 'FUNCTION X)) ^ Lambda may have some use in another case, which is the MAP'ing functions. For example, if you wish to apply a function to every element of a list, you can do (MAPCAR 'CAR '((A) (B C) (D E F))) which returns (A B D). try If the function that you desired to map was not defined somewhere and was for single time application, you might just want to use a LAMBDA rather than giving the function a name. For example, to take a list and return a list which had 10 added to every element in the list, you might want to do: (MAPCAR '(LAMBDA (X) (+ X 10)) '(1 2 3)) which returns (11 12 13). Some lisp's define that LAMBDA is a self-quoting structure so that (LAMBDA (X) X) for instance would eval to itself. If you are more comfortable with it doing so, you may feel free to use the following incantation to make it be so: (DEFUN LAMBDA MACRO (X) (LIST 'FUNCTION X)) HAmong the neater features of this version is the funcion FILE. to load in a file, say (FILE FOO). this will read in a function FOO from my directory (where you should keep your LISP files) where is the name you log in as.. Please do not put things other than your LISP files on my directory, as my directory is already rather full. Do not delete them when you are through--just send me mail telling me, and I will delete them after I have finish checking them out. If you want to keep them, you should copy them elsewhere, or have me retrieve them--everything will be moved to a safe place before deleting, and sometimes they may disapear before you are ready for them to. i Presumably the first N-1 forms if they exist are done for side-effect. For example, the LAMBDA operator (LAMBDA (X Y) (+ X Y) (* X Y)) would compute the sum of X and Y, then throw away its value -- essentially wasting your work computing it. Then it would compute the product of X and Y and since that is the last form in the list, would return that value. So we see that the operator (LAMBDA (X Y) (+ X Y) (* X Y)) is functionally equivalent to the operator (LAMBDA (X Y) (* X Y)) Closures - An Oversimplified View KMP, 7 Apr 80 A closure is a lambda that remembers the environment in which it was created. In ULisp, a closure is created by the function close-it. (close-it (lambda ...)) returns a closure. Currently, closures print as (closure (lambda ...) closure_environment) and have 2 components -- a lambda, and an environment which was the value that would have been returned by (getal) at the time of the closure's creation. To invoke a closure, just use it as a function. eg, (setq y 4) (setq my-fun (close-it (lambda (x) (+ x y)))) Note that lambda-expressions evaluate to themselves in ULisp. So if you say then (my-fun 3) you should get back 7. Even if you do ((lambda (y) (my-fun y)) 3) you should still get back 7. This is because after the evaluation of the arguments to y but before the closure which is the value of my-fun gets invoked, the environment in which the closure was created is resumed so the binding of y to 3 disappears for a while. OKMP 7:59am Thursday, 31 January 1980 (1) Need to write the following lessons (a) SYNTAX (b) MACRO (2) Need to make the following patches (a) Make the (...) => ( ...) handler check if is a valid function before opening its big mouth. (3) Error handlers for (a) PUTD (b) LAMBDA (c) NLAMBDA (d) DEFINE i Presumably the first N-1 forms if they exist are done for side-effect. For example, the LAMBDA operator (LAMBDA (X Y) (+ X Y) (* X Y)) would compute the sum of X and Y, then throw away its value -- essentially wasting your work computing it. Then it would compute the product of X and Y and since that is the last form in the list, would return that value. So we see that the operator (LAMBDA (X Y) (+ X Y) (* X Y)) is functionally equivalent to the operator (LAMBDA (X Y) (* X Y))