Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

Scheme Programming Language

Newbie: problem understanding a lat and an atom (The Little Schemer)


Hi,

I'm working my way through the Little Schemer (excellent book) and am
already stuck.

I haven't heard the term 'lat' until reading the book.  And up until now
thought that an atom was an item in a list (wrong apparently).

The book gives examples of an atom:
atom
turkey
1492
u
*abc$
(atom)

And this (atom turkey or) is a list because it is a collection of atoms
enclosed in parentheses.
And ( ) is an empty list but not an atom.

The authors go on to talk about something called a lat.
(jack sprat could eat no chicken fat) is a lat because each S-expression (S
= Scheme???) is an atom
((Jack) Sprat could eat no chicken fat) is not a lat because its car is a
list.
( ) is a lat because it does not contain a list.

They define a procedure lat? as follows:
(define lat?
  [lambda (x)
    (cond
      [(null? x) #t]
      [(not (pair? (car x))) (lat? (cdr x))]
      [else #f ] )] )

I'm using DrScheme and the procedure atom? generates an error but the word
does appear in help.  Perhaps this is not implemented in DrScheme - it gives
an alternative (not (pair? v)) that makes some sense.  I believe a pair is
an object produced by (cons list1 list2) ;==> (list1 list2) but apparently
it is also a list.  Some time ago I accidentally created a pair (a dot b)
but can't figure out how I did it ...
(pair? '(a b c)) ==> #t
(list? '(a b c)) ==> #t

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.

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.

Question 3 - Lists are pairs and pairs are lists???

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.

Thanks in advance,

Mike

So ... atoms are objects in Scheme?

Mike skrev:

> I'm working my way through the Little Schemer (excellent book) and am
> already stuck.

> I haven't heard the term 'lat' until reading the book.  And up until now
> thought that an atom was an item in a list (wrong apparently).

The word "atom" stems from greek and means something that can not
we divided (into smaller pieces). A list is therefore not an atom,
since it consists of smaller parts.

> The book gives examples of an atom:
> atom
> turkey
> 1492
> u
> *abc$
> (atom)

The examples show that symbols are atoms.

> And this (atom turkey or) is a list because it is a collection of atoms
> enclosed in parentheses.
> And ( ) is an empty list but not an atom.

Here I must admit, that haven't got a copy of the book. I'd call
the empty list an atom - but if they do otherwise, they can. The term
atom isn't defined in the Scheme standard.

> The authors go on to talk about something called a lat.

I bet, they use lat as short for "List of-AToms".

> (jack sprat could eat no chicken fat) is a lat because each S-expression (S
> = Scheme???) is an atom

The S in S-expression stands for symbolic. The word S-expression is
older than Scheme.

<http://en.wikipedia.org/wiki/S-expression>

> ((Jack) Sprat could eat no chicken fat) is not a lat because its car is a
> list.

In other words: It is not a list of atoms, since the first element
in the list is (Jack), which is not an atom.

> ( ) is a lat because it does not contain a list.

In other words: All elements of the empty list are atoms.

> They define a procedure lat? as follows:
> (define lat?
>   [lambda (x)
>     (cond
>       [(null? x) #t]
>       [(not (pair? (car x))) (lat? (cdr x))]
>       [else #f ] )] )

> I'm using DrScheme and the procedure atom? generates an error but the word
> does appear in help.  

You can define it youself:

(define atom?
   (lambda (x)
     (cond
       [(symbol? x) #t]
       [(pair? x)   #f]
       <other cases here>)))

> Perhaps this is not implemented in DrScheme - it gives
> an alternative (not (pair? v)) that makes some sense.  I believe a pair is
> an object produced by (cons list1 list2) ;==> (list1 list2) but apparently
> it is also a list.  

The empty list is a list:  '()
The cons of an element and a list is a list: (cons 1 a-list).

Since '() is a list, (cons 1 '()) is a list. Normally printed as (1).

Since (cons 1 '()) is a list, (cons 2 (cons 1 '())) is a list.
Normally printed as (1 2).

That is, lists are built by conses and the empty list.

> Some time ago I accidentally created a pair (a dot b)
> but can't figure out how I did it ...
> (pair? '(a b c)) ==> #t
> (list? '(a b c)) ==> #t

Probably (cons 1 2). This is a pair, but not a list, since
2 is not a list.

> 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.

Are there no definition in book?

> 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.

My guess is, that is just a list-of-atoms.

> Question 3 - Lists are pairs and pairs are lists???

Almost, see above.

> 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.

Car is the same as first. Cdr is the same as rest.
Some people use first and rest, when they work with lists,
and use car and cdr when they work with non-lists built with pairs.

It is mostly a matter of taste.

--
Jens Axel Sgaard

Mike writes:
> 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.

Don't take it too seriously.

There is no official definition. Scheme has things called symbols,
which some might call atoms. Or symbols and numbers might be atoms.
Or symbols and numbers and the two booleans and maybe the empty list
might be atoms. Strings and vectors, who knows. It's up to the user of
the term to tell what they mean.

But non-empty lists are definitely not atoms. Not sure about pairs
that are not lists.

> 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.

I'm pretty sure the word is short for List of AToms.

> Question 3 - Lists are pairs and pairs are lists???

There is one list that is not a pair.

There are plenty of pairs that are not lists. A pair is a list just
when its cdr is a list.

> 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.

Scheme reports do not define first and rest. They define car and cdr.

There are two reasons car and cdr have persisted. One is that they
don't really mean anything, as words, so they still make the same
amount of sense when the pair is not used as a list. (They were
acronyms on the computers where LISP was originally developed.) The
other is that they form a nice basis for equally obscure names for
their compositions: (cadar x) is (car (cdr (car x))), and so on.

...

> So ... atoms are objects in Scheme?

The term is not defined in the Scheme reports, but once you define it,
yes. I think the book mostly uses symbols as atoms. I forget if
numbers are atoms in it, or if the empty list is.

"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.

Thank you everyone,

I am very grateful for the depth of the answers and that was precisely what
I was looking for BTW.

I need to digest what everyone said because it is useful & clarifies why I
run into problems - I just need to look more closely at the structure and
what it is that I'm trying to do.

And yes - I missed where Lat was defined in 'The Little Schemer' - my bad,
RTFM much more closely :)

Although I am still learning, it seems new data structures are capable of
being defined by anyone (data abstraction for example) that might make
discussion of an atom moot.  However, so far as I can tell, the authors are
attempting to drill the concept into my head so I have a better grasp of
basic of programming concepts and models.

For a short book, it packs a deceptive amount of learning and discovery into
each chapter.

Now to kill a dragon, save the universe and figure out how to hammer
procedures as params into my head.  The first two look easy.

Once again, thanks.

Mike

"Mike" wrote:
> 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 I see it, atoms can be understood in the context of symbolic expressions.

- - - - - - - - - -
Here is a definition of the natural numbers 0,1,2...

1. 0 is a number.
2. The successor of a number is a number.

1 is a name for succ 0. 2 is a name for succ 1. etc.

- - - - - - - - - -
Here is a definition of symbolic expressions.

1. Atoms are S-expressions.
2. The cons of any two S-expressions is an S-expression.

An atom is an indivisible data object. Atoms are notated as strings of
letters and digits. The cons of two S-expressions a and b is notated (a .
b). The empty list, notated as (), is an atom.

1978

***Compare the role of 0 in natural numbers and atoms in S-expressions.
- - - - - - - - - -
Here is another definition of symbolic expressions.

1. Atomic symbols are S-expressions.
2. If e1 and e2 are S-expressions, so is (e1 . e2)

S-expressions are formed by using the special characters .  (  ) and an
infinite set of distinguishable atomic symbols. Atomic symbols are strings
of letters and digits.

1960
- - - - - - - - - -
Here is the same definition of the set of natural numbers using BNF notation

<number> := 0
<number> := succ <number>

The notation <number> means a *set* of numbers.

- - - - - - - - - -
Here is a definition of a list of symbols.

<slist> := ()
<slist> := ( <symbol-expression> . <slist> )
<symbol-expression> := <symbol> | <slist>

<symbol> is a Scheme symbol.

2001

- - - - - - - - - -
Thus, atoms (represented as symbols in Scheme) start the inductive
definition of symbolic expressions.

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc