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:[email protected]?subject=Unsubscribe
