conses and atoms

conses-and-atoms.txt

[16:51] <@_death> for starters, your definition of a linked list is wanky
[16:52] <@_death> first, you should split the universe in two: atoms and pairs
[16:53] <@_death> a pair has two cells, which in turn may be atoms or pairs
[16:53] <@_death> there exists an atom in this universe, let's call it NIL
[16:53] <@_death> to designate a pair, we can write (<cell1> . <cell2>)
[16:54] <@_death> so for example a pair containing the NIL atom in its cells would be (NIL . NIL)
[16:54] <@_death> now, we can represent an empty list as the atom NIL
[16:55] <@_death> a nonempty list is a pair whose second cell is a list, empty or nonempty
[16:55] <@_death> with these two rules, you've defined a linked list
[16:56] <@_death> examples of lists: NIL, (NIL . NIL), (NIL . (NIL . NIL)) with 0, 1, 2 elements
                  respectively
[16:56] <@_death> for old time's sake, we'll rename "pair" to "cons", call its first cell "car"
                  and its second cell "cdr"
[16:56] <@_death> and now, my friend, you know a little about lisp
[16:57] <@_death> with a little notational help, such lists may be circular (car-circular or
                  cdr-circular)
[16:57] <@_death> let us create a reference to a pair or an atom by prefixing it with #<n>=
[16:58] <@_death> let us refer to it using the notation #<n>#
[16:58] <@_death> so for example #1=(NIL . #1#) is a circular list, whose elements are all NIL
[17:01] <@_death> if the cdr cell is nonatomic (i.e. a cons), we can shorten the notation, so that
                  (<a> . (<b> . <c>)) is shortened into (<a> <b> . <c>)
[17:02] <@_death> and if a cdr cell is NIL, we can simply not write the ". NIL", so that (<a>
                  . (<b> . NIL)) can be shortened into (<a> <b>)
[17:02] <@_death> then it's easier to see that it's a list of two elements
[17:04] <@_death> we can use this structure to represent lists, trees, graphs (remember the
                  #<n>=/#<n># notation)..
[17:05] <@_death> and so, (1 2 3) is a bunch of conses and atoms, in long form (1 . (2 . (3
                  . NIL)))
[17:05] <@_death> (loop (sleep) (shit)) is also a bunch of conses and atoms
[17:06] <@_death> (loop . ((sleep . nil) . ((shit . nil)))) in long form
[17:07] <@_death> then we can manipulate this data, and this forms representing code in the same
                  way..
[17:07] <@_death> *these
[17:07] <@_death> and this allows lisp to transform itself into any kind of language
[17:09] <@_death> for efficiency we may want to add more kinds of atoms, say arrays or structures
[17:12] <@_death> now you can understand the topic of #lisp
[17:12] <@_death> "Common Lisp, the #1=(programmable . #1#) programming language"