Lisp InternalsA problem with listsPointersCAR and CDRS-expressionsAtomsListsExample IExample IIExample IIIExample IVDotted pairsLisp lists are implemented with dotted pairsExample VPrinting dotted pairsEfficiency of CDREfficiency of CAR and CONSSharing structureMemoryJava isn’t LispA possible Java implementationAnother possible implementationImplementing the functions IImplementing the functions IIThe EndLisp InternalsA problem with lists•In Lisp, a list may “contain” another list–For example, (A (B C)) contains (B C)•So, how much storage do we need to allocate for a list?–If any list can contain any other list, there is no limit to the size of storage block we may need–This is impractical; we need another solutionPointers•Instead of actually putting one list inside another, we put a pointer to one list inside another–A pointer is a fixed, known size•This partially solves the problem, but...–A list can contain any number of elements–For example, the list ((A)(B)(A)(C)) contains four lists–This still leaves us needing arbitrarily large blocks of storageCAR and CDR•We can describe any list as the sum of two parts: its “head” (CAR) and its “tail” (CDR)–The head is the first thing in the list–The head could itself be an arbitrary list–The tail of a list is another (but shorter) list•Thus, any list can be described with just two pointers•This provides a complete solution to our problem of arbitrarily large storage blocksS-expressions•In Lisp, everything is an S-expression•An S-expression is an atom or a list•You can think of these as using two different kinds of storage locations--one kind for atoms, another kind for the parts of a list–This is an oversimplification, but it will do for nowAtoms•An atom is a simple thing, and we draw it in a simple way:•Sometimes we don’t bother with the boxes:HELLOABC NILHELLOABC NILLists•A list has two parts: a CAR and a CDR•We draw this as a box , called a cons cell, with two compartments, called the car field and the cdr field•In each of these compartments we put an arrow pointing to its respective value:car field cdr fieldcar fieldvalue of car value of cdrExample I( A )ANILANILExample II( A B C )A(B C)B(C)CNILABCNILExample IIIBANIL NIL((A) B)Example IVBANILNILCNILD((A B) (C D))Dotted pairs•In a simple list, every right-pointing arrow points to a cons cell or to NIL•If a right-pointing arrow points to an atom, we have a dotted pair(A . B)ABLisp lists are implemented with dotted pairs•Therefore, (A) = (A . NIL)•All structures in Lisp can be created from atoms and dotted pairs( A ) =ANIL= (A . NIL)Example VABCD((A . B) . (C . D))Printing dotted pairs•A dotted pair is usually printed using parentheses and a dot: (A . B)•If the CDR of a dotted pair is NIL, the dot and the NIL are omitted: (A . NIL) = (A)•If the CDR is another cons cell, Lisp doesn’t print the dot or the parentheses–(A . (B . (C . NIL))) = (A B C)–(A . (B . (C . D))) = (A B C . D)Efficiency of CDR•Suppose L is the list (A B C D E)•Then (CDR L) is the list (B C D E)•Isn’t it expensive to create this new list?•Answer: NO! It’s incredibly cheap!•Lisp just copies a pointer:A (B C D E)L(CDR L)Efficiency of CAR and CONS•CAR is just like CDR; you just copy a pointer•CONS takes more work; you have to allocate and fill one cons cellAHere’s the atom ABNILHere’s the list (B)Here’s the cons cell we add to create the list (A B)Sharing structure•List L and list (CDR L) are said to share structure•But if L = (A B C D E) and M = (CDR L), then when you change L, won’t M be changed?•Yes, but...–this is where the real genius of Lisp comes in...•You never change L !•None of the basic functions ever change anything that’s already there•Only CONS adds anything•The result is an extraordinarily efficient language!Memory•If you only add structure, and never change or delete anything, won’t you run out of memory?•Lisp uses garbage collection to recover structures that you are no longer using–More convenient for the programmer–Safer (less subject to human error)–Extremely effective in generalJava isn’t Lisp•Although Lisp’s way of handling lists is elegant and efficient, it’s not the only way–Modifying the middle or end of a list is expensive•There are many ways we might implement lists in Java•Lisp’s implementation of lists is a great example, but not necessarily the final wordA possible Java implementation class Cell { } class Atom extends Cell {String value;Atom(String value) { // constructorthis.value = value;}} class ConsCell extends Cell {Cell car;Cell cdr;ConsCell(Cell car, Cell cdr) { // constructor this.car = car;this.cdr = cdr;}}Another possible implementation class Cell {boolean isAtom;String value;Cell car, cdr; Cell(String value) { // constructorisAtom = true;this.value = value;} Cell(Cell car, Cell cdr) { // constructorisAtom = false;this.car = car;this.cdr = cdr;}}Implementing the functions I class Lisp { static Cell car(Cell c) { return c.car;} static Cell cdr(Cell c) { return c.cdr;} static Cell cons(Cell c1, Cell c2) { return new Cell(c1, c2);}Implementing the functions II static boolean atom(Cell c) { return c.isAtom;} static boolean eq(Cell c1, Cell c2) { return c1.value.equals(c2.value);} }The
View Full Document
Unlocking...