Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!husc6!think!barmar From: barmar@think.COM (Barry Margolin) Newsgroups: comp.lang.lisp Subject: Re: pointers in Lisp Message-ID: <36345@think.UUCP> Date: 12 Feb 89 21:59:53 GMT References: <1710@cps3xx.UUCP> <33722@tut.cis.ohio-state.edu> <49734@yale-celray.yale.UUCP> <36238@think.UUCP> <624@internal.Apple.COM> <36318@think.UUCP> <1648@umbc3.UMBC.EDU> Sender: news@think.UUCP Reply-To: barmar@kulla.think.com.UUCP (Barry Margolin) Organization: Thinking Machines Corporation, Cambridge MA, USA Lines: 35 In article <1648@umbc3.UMBC.EDU> alex@umbc3.umbc.edu.UMBC.EDU (Alex S. Crain) writes: > Um, what exactly is a CRD-coded list? CDR-coding is a technique for reducing the storage taken up by lists. Cons cells, which are the normal building blocks of lists, are more general than is frequently needed; they can be used to build arbitrary trees, but many Lisp data structures are simply linear lists, and don't take advantage of this generality. In CDR coding, each list element is represented using a single CAR pointer plus a two-bit CDR-code field. The CDR-code indicates how to compute the CDR of the list, and has three possible values: CDR-NORMAL, CDR-NEXT, and CDR-NIL. CDR-NORMAL indicates that the word is the CAR of a normal cons cell, so the following word contains a pointer to the cdr. CDR-NEXT means that the following word IS the cdr. And CDR-NIL means that this word was the last list element, and the cdr is implicitly NIL. A list where all the elements are CDR-NEXT (except, of course, for the last, which is CDR-NIL) will take up half as much storage as one that is all CDR-NORMAL. However, CDR-coding in general requires some additional architectural features, most importantly invisible pointers. If you RPLACD a cons that is CDR-NEXT or CDR-NIL there is no cdr cell to store into. Instead, you allocate a new CDR-NORMAL cons, copy the original car to the new one's car, and replace the original car cell with an invisible pointer to the new cons. An invisible pointer is a word that automatically gets dereferenced when you try to read its contents. Invisible pointers require hardware support to prevent an enormous performance hit. Barry Margolin Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar