On Sunday 13 of March 2011 21:49:44 you wrote:
> Hi list,
> 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.

Example first ;-)

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

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=
"hidden") ) )

Theory  @_@

Lisp manages memory in units larger than bytes: `cells'. Each cell has two=
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=
fast distinction (requires just some bitwise operation on register) lets yo=
express clearly what is follow-able (a list) and what is not (a pair). Thos=
two will never be mixed up; a list is clearly a list, a dotted pair is clea=
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=
(KEY, VALUE) tuple.

A list consists of one or more memory cells:

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=
you get a circualr, `infinite' list)

On the other hand, in dotted pair:

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

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

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

To create a dotted pair, you do
and there is alternative syntax to it to make it stand out:

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

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: =
CDR: NIL]]], which is (1 2 3) in the end :P
etc. etc.

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=
nothing to follow ;-)

The practical stuff :3

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

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

(the list will contain elements, with CAR pointing to a dotted pair and CDR=
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 =
(KEY . VALUE) properties associated with it). Access with (get) and (set).

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

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

dexen deVries


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

Reply via email to