On Sunday 13 of March 2011 21:49:44 you wrote:
> Hi list,
>=20
> i don't dig dotted pairs. it's hard for me to reconcile the existence
> of a dotted pair when there's a more general representation of it (a
> plain list).


My very hairy take on it:

use dotted pair to express (KEY, VALUE) tuples.


=2D---
Example first ;-)

when emiting HTML, you can emit a <input> tag like:
(<input>)

you can pass extra attributes like:
(<input> ("class" . "menu-item"))

where the `class' is key (here -- HTML attribute name) and `menu-item' is=20
value (here -- HTML attribute value)

You can also, in principle, create a list of dotted pairs:
(<input> ( ("class" . "menu-item") ("name" . "foo") ("value" . "bar") ("typ=
e"=20
"hidden") ) )


=2D---
Theory  @_@


Lisp manages memory in units larger than bytes: `cells'. Each cell has two=
=20
fields: [CAR, CDR] in that order (in 32bit picoLisp, 32bit each).

By looking at the content of CDR picoLisp can tell right away if this=20
particular cell is part of a list, or if it's a dotted pair. This very easy=
 &=20
fast distinction (requires just some bitwise operation on register) lets yo=
u=20
express clearly what is follow-able (a list) and what is not (a pair). Thos=
e=20
two will never be mixed up; a list is clearly a list, a dotted pair is clea=
rly=20
a dotted pair.

A Lisp list is what C programmers call `linked list'; it may contain any=20
number of ORDINARY_VALUEs (which may be dotted pairs, strings, numbers etc).

A dotted pair is a tuple of two ORDINARY_VALUEs; it is used often to expres=
s=20
(KEY, VALUE) tuple.


A list consists of one or more memory cells:

1st cell: [CAR: ORDINARY_VALUE, CDR: NEXT_CELL]
2nd cell: [CAR: ORDINARY_VALUE, CDR: NEXT_CELL]
=2E..
last cell: [CAR: VALUE, CDR: NIL]

The important point is, in the last cell of a list the CDR is =3D=3D NIL, i=
n other=20
cells it points to the next cell.

(actually, the last one can refer to the first one rather than to NIL; that=
 way=20
you get a circualr, `infinite' list)


On the other hand, in dotted pair:
the only cell: [CAR: ORDINARY_VALUE, CDR: ORDINARY_VALUE]


A very fine point is, that Lisp distinguqishes between ORDINARY_VALUE point=
ers=20
and NEXT_CELL pointers -- they are picked specially so they never get mixed=
=20
up. More on it in [1]


((Actually, NIL is a `degenerate', zero-length list, so it counts as NEXT_C=
ELL=20
in a way, and won't be ever mistaken with an ORDINARY_VALUE))


To create a list, you do
(cons ORDINARY_VALUE 'SOME_LIST)
where `cons' returns a memory cell with the two values  specified , CAR and=
 CDR
In that way, you prepend ORDINARY_VALUE to the SOME_LIST.


To create a dotted pair, you do
(cons ORDINARY_VALUE ORDINARY_VALUE)
and there is alternative syntax to it to make it stand out:
(ORDINARY_VALUE . ORDINARY_VALUE)


To wrap it up:
(cons 1 2) creates [CAR: 1, CDR: 2], which is (1 . 2)

(cons 1 NIL) creates [CAR: 1, CDR: NIL], which is (1)
(cons 1 '(2)) creates [CAR: 1, CDR: '(2)], which is (1 2)
# the '(2) contains 2 and NIL, so one NIL is provided :D

(cons 1 '(2 3)) creates [CAR: 1, CDR: '(2 3)], which is (1 2 3)
# the '(2 3) contains 2, 3 and NIL, so one NIL is provided again


=2D---
Now to prove the dotted pair notation is just shortcut for (cons ...) you=20
can write (1 . NIL), which is [CAR: 1, CDR: NIL], which is just (1). But=20
that'd confuse everybody ;-)


You could also (1 . (2 . NIL)) which would be [CAR: 1, CDR: [CAR: 2, CDR:=20
NIL]], which is again (1 2)
And (1 . (2 . (3 . NIL))) which would be [CAR: 1, CDR: [CAR: 2, CDR: [CAR: =
3,=20
CDR: NIL]]], which is (1 2 3) in the end :P
etc. etc.


=2D---
If it's a list, it makes sense to follow it.
if it's a dotted pair, it does not make sense to follow it, because there i=
s=20
nothing to follow ;-)


=2D---
The practical stuff :3


If you want to create an associative structure, create a list of dotted pai=
rs:

'(dotted-pair   dotted-pair   dotted-pair  ...)

(the list will contain elements, with CAR pointing to a dotted pair and CDR=
 to=20
next element or NIL)

lookup of value associated with a MY_KEY is fast & easy:
 * list is traversed
   * for each element, get the dotted pair (from element's CAR)
      * dotted pair's CAR (holding KEY) is compared to MY_KEY
        *  if it matches, the CDR of the pair (holding VALUE) is returned

Nb., this mechanism is used internally in picoLisp for symbol properties=20
(aside of the general value of the symbol, each symbol can have any number =
of=20
(KEY . VALUE) properties associated with it). Access with (get) and (set).


=2D---
example of use: pick value from key B:
(asoc 'B '((A . 123) (B . 777) ("CCC" . "VVV")))
=2D> 777
(asoc "CCC" '((A . 123) (B . 777) ("CCC" . "VVV")))
=2D> "VVV"
(asoc 'Z '((A . 123) (B . 777) ("CCC" . "VVV")))
=2D> NIL=20
not found


=2D---
[1] http://www.software-lab.de/doc/ref.html#data


Cheers,
=2D-=20
dexen deVries

[[[=E2=86=93][=E2=86=92]]]

``In other news, STFU and hack.''
mahmud, in response to Erann Gat's ``How I lost my faith in Lisp''
http://news.ycombinator.com/item?id=3D2308816
-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

Reply via email to