"Mike" <mcu87
@bigpond.net.au> writes:
> [...]
> Some time ago I accidentally created a pair (a dot b)
> but can't figure out how I did it ...
(cons 'a 'b)
--> (a . b)
But (cons 'a '(b c d)) is printed as:
(a b c d)
But it's actually exactly the same data structure as the one returned
by the form:
(cons 'a (cons 'b (cons 'c (cons 'd '()))))
or:
(list 'a 'b 'c 'd)
that is: (a . (b . (c . (d . ()))))
'(a . (b . (c . (d . ())))) ; is also printed as:
--> (a b c d)
> (pair? '(a b c)) ==> #t
> (list? '(a b c)) ==> #t
This is like asking whether you are 72 kg of meat, or whether you are
a human. Two different levels of abstraction.
> Question 1 - After all of this what is an atom? I can answer the questions
> in the book but this is just pattern recognition on my part as opposed to
> understanding.
As answered by Jen, an atom is something that is not divisible, that
is "atomic". But like the physical atoms, it's been discovered they
can actually be divised into a nucleus and electron cloud, and the
nucleus itself can be divided into neutrons and protons, and these
nucleons themselves can be divided into quarks, etc.
Well, in lisp we got the same problem.
Atoms were historically defined as anything that is not a cons cell (a
pair). At the time, all that wasn't a cons cell was atomic. But
since then new kind of atoms have been introduced, like strings,
arrays, structures, etc and these new atoms are divisible into
components. So the word atom doesn't means what it meant anymore,
even if its definition is still valid and kept as always (atom = not a
cons cell).
That's why the designers of scheme who were teachers and wanted to
avoid hard questions on the part of the students decided not to define
atom? in scheme.
You could define in scheme atom? with the historical meaning:
(define (atom? object) (not (pair? object)))
Now the question is, is () a pair?
In most lisp, () is actually a symbol, the symbol NIL, and is not a
pair, it's an atom. In scheme () is defined to be not a pair? so it's
an atom? by the historical definition.
> Question 2 - What is a lat and what significance does it have? I can tell
> it is a list of items (atoms???) of which none are themselves lists.
A "List of AToms", as defined in the Little Schemer.
It is something that is very good to make nice exercises in a book to
teach lisp programming.
Well, you can imagine some real practical program where you have to
distinguish lists of atoms from lists containing at least one sublist,
because they'd mean something different in this program. But see next
answer.
> Question 3 - Lists are pairs and pairs are lists???
Yes and no, and no and yes.
Pairs are structures containing two objects held together. That's all.
What's interesting is that its the smallest data structure that allows
you to build any other data structure.
For example, you can make a record of 4 slots with 3 pairs:
(define (make-person first-name last-name age direction)
(cons (cons first-name last-name)
(cons age direction)))
(define person-first-name caar)
(define person-last-name cdar)
(define person-age cadr)
(define person-direction cddr)
Or you could make a singly-linked list:
(define (make-list first rest)
(cons first rest))
(define first car)
(define rest cdr)
; note we don't have to put necessarily the first element in the car
; and the rest in the cdr, it's only the way the standard lisp
; functions like lisp and display interpret pairs as lists.
Or you could make anything you want.
But while lists are implemented using pairs, they are not pairs. The
list abstract data type has a signature totally different than the
pair abstract data type.
> Question 4 - the book really goes to town on car and cdr. We use first and
> rest. Is there any difference between these operations or do people use
> first / rest because it is easier to understand? Just curious ... I'm
> unable to find any difference between them on the web or the help file.
For the list data type you have:
(list? object) -> boolean
(empty-list) -> list
(empty? list) -> boolean
(first list) -> item
(rest list) -> list
(last-item list) -> item
(list . items) -> list
(nth index list) -> item
(length list) -> integer
...
For the pair data type you have:
(pair? object) -> boolean
(cons item item) -> pair
(car pair) -> item
(cdr pair) -> item
So it would be theorically an error to use a pair function on a list.
Only that in lisp, we take here a shortcut, and implement lists as a
very thin layer over the pairs. Since in general we use these lists
from the head, we only need first and rest, and don't use often
last-item, or nth, so it's practical to implement our lists just as
chains of pairs, with the last being (). But it means that last-item
is O(length(list)) as well as several functions like append!, etc. If
we wanted to have last-item and length in O(1), like first, we could
do that by defining a list as a structure keeping references to the
first and last pair, as well as the length. (One thing that would be
more difficult then would be the sharing of tails of lists, so we
would need more memory, for the kind of things we usually do with
lists (eg. implement a lisp interpreter)).
So for historical and practical reasons, we like to just use chains of
pairs for lists, and this allows us to make puns, and use car, a pair
function on lists. (But if you consider your object to be a list, you
should use first instead of car).
By the way, you could take an electronic microscope and try to see a
pair inside your RAM or microprocessor. What would that tell you?
That you're right to name them car and cdr instead of describing them
as electronic states of some silicium atom. When you consider a pair,
you don't consider the electrons they're made of in your computer.
Then, when you consider a list, you shouldn't either consider the
pairs they're made of. And when you build higher level data structure
with lists, you shouldn't either consider them as lists!
Instead of using pairs to implement the person record above, we could
use lists:
(define (make-person first-name last-name age direction)
(list first-name last-name age direction))
(define (person-first-name p) (nth 0 p))
(define (person-last-name p) (nth 1 p))
(define (person-age p) (nth 2 p))
(define (person-direction p) (nth 3 p))
But it would be very wrong to use first to take the first-name of a person:
(first (make-person "White" "Snow" 26 "Dwarf Residence, Big Forest"))
you must write;
(person-first-name (make-person "White" "Snow" 26 "Dwarf Residence, Big Forest"))
even if both functions do exactly the same at the electron level.
> So ... atoms are objects in Scheme?
Yes. All the scheme objects that are not pairs are atoms. Even if
like physical atoms, most of them aren't atomic.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Litter box not here.
You must have moved it again.
I'll poop in the sink.