From: Erick Lopez Carreon
Subject: Ansi Common Lisp chapter 3 exercise 6
Date: 
Message-ID: <1161817953.464168.226020@i3g2000cwc.googlegroups.com>
Hello:

I am doing the exercises of the chapter 3 of the Book Ansi Common Lisp,
have doubt if I interpreted correctly the problem 6. I will appreciate
very much his comments.
Next the problem and the solution that I implemented:

---------------------------------------------------------------------------------------------------------
;;6.- After years of deliberation, a government comission has decided
that
;;lists should be represented by using the cdr to point to the first
;;element and car to point to the rest of the list. Define the
;;government versions of the following functions:
;;cons  list length(for lists) member(for lists; no keywords)

(defun gov-car (lst)
  (cdr lst))

(defun gov-cdr (lst)
  (car lst))

(defun gov-cons (obj lst)
  (cons lst (cons obj nil)))

(defun gov-list (&rest objs)
  (if (null objs)
      nil
      (cons (gov-cdr objs) (gov-car objs))))

(defun gov-length (lst)
  (if (null lst)
      0
      (+ (gov-length (gov-car lst)) 1)))

(defun gov-member (obj lst)
  (if (null lst)
      nil
      (if (eql (gov-cdr lst) obj)
	  lst
	  (gov-member obj (gov-car lst)))))

From: Ken Tilton
Subject: Re: Ansi Common Lisp chapter 3 exercise 6
Date: 
Message-ID: <nDS%g.568$qD3.293@newsfe11.lga>
Erick Lopez Carreon wrote:
> Hello:
> 
> I am doing the exercises of the chapter 3 of the Book Ansi Common Lisp,
> have doubt if I interpreted correctly the problem 6. I will appreciate
> very much his comments.

I would would appreciate very much seeing your test results. :)

I suspect problems from gov-cons on.

kt

> Next the problem and the solution that I implemented:
> 
> ---------------------------------------------------------------------------------------------------------
> ;;6.- After years of deliberation, a government comission has decided
> that
> ;;lists should be represented by using the cdr to point to the first
> ;;element and car to point to the rest of the list. Define the
> ;;government versions of the following functions:
> ;;cons  list length(for lists) member(for lists; no keywords)
> 
> (defun gov-car (lst)
>   (cdr lst))
> 
> (defun gov-cdr (lst)
>   (car lst))
> 
> (defun gov-cons (obj lst)
>   (cons lst (cons obj nil)))
> 
> (defun gov-list (&rest objs)
>   (if (null objs)
>       nil
>       (cons (gov-cdr objs) (gov-car objs))))
> 
> (defun gov-length (lst)
>   (if (null lst)
>       0
>       (+ (gov-length (gov-car lst)) 1)))
> 
> (defun gov-member (obj lst)
>   (if (null lst)
>       nil
>       (if (eql (gov-cdr lst) obj)
> 	  lst
> 	  (gov-member obj (gov-car lst)))))
> 

-- 
Cells: http://common-lisp.net/project/cells/

"I'll say I'm losing my grip, and it feels terrific."
    -- Smiling husband to scowling wife, New Yorker cartoon
From: Erick Lopez Carreon
Subject: Re: Ansi Common Lisp chapter 3 exercise 6
Date: 
Message-ID: <1161820517.549216.279860@k70g2000cwa.googlegroups.com>
> I would would appreciate very much seeing your test results. :)
>
> I suspect problems from gov-cons on.

Yes, you're rigth:

CL-USER> (cons 'a 'b)
(A . B)
CL-USER> (gov-cons 'a 'b)
(B A)

CL-USER> (cons 'a '(b))
(A B)
CL-USER> (gov-cons 'a '(b))
((B) A)

CL-USER> (cons '(a d) '(b c))
((A D) B C)
CL-USER> (gov-cons '(a d) '(b c))
((B C) (A D))

CL-USER> (cons 'a (cons 'b (cons 1 (cons 'c nil))))
(A B 1 C)
CL-USER> (gov-cons 'a (gov-cons 'b (gov-cons 1 (gov-cons 'c nil))))
((((NIL C) 1) B) A)


I believe that this represents well the doubt that I have about if I
interpreted correctly the problem,
I must do an exact clone of cons or gov-cons must invert the order of
the objects?

Regards
From: Ken Tilton
Subject: Re: Ansi Common Lisp chapter 3 exercise 6
Date: 
Message-ID: <H5_%g.611$qD3.342@newsfe11.lga>
Erick Lopez Carreon wrote:
>>I would would appreciate very much seeing your test results. :)
>>
>>I suspect problems from gov-cons on.
> 
> 
> Yes, you're rigth:
> 
> CL-USER> (cons 'a 'b)
> (A . B)
> CL-USER> (gov-cons 'a 'b)
> (B A)

OK, stop right here and figure this out, because I only saw one mistake 
in gov-cons and the rest of your tests just reflect the same mistake.

That mistake suggests to me that you have not fully grokked the normal 
Lisp version of cons. What you might want to try is:

  (defstruct mycons car cdr)

..and then use nothing but mycons, mycons-car, and mycons-cdr (along 
with (setf <same) on the last two) to implement /conventional/ list 
behavior, where the cdr is the possible continuation of a linked list. 
The fun part will be defining a print-object method for mycons so you 
can have a chain of these print out as if it were a normal list composed 
of Lisp conses.

By the time you have /that/ working you should be able to see what you 
did wrong in gov-cons. If that sounds like too much work, just stare at 
gov-cons and draw some pictures of gov-conses and their cars and cdrs 
and just figure out your mistake. It is pretty obvious (ie, you are not 
looking for something subtle).

kt


> 
> CL-USER> (cons 'a '(b))
> (A B)
> CL-USER> (gov-cons 'a '(b))
> ((B) A)
> 
> CL-USER> (cons '(a d) '(b c))
> ((A D) B C)
> CL-USER> (gov-cons '(a d) '(b c))
> ((B C) (A D))
> 
> CL-USER> (cons 'a (cons 'b (cons 1 (cons 'c nil))))
> (A B 1 C)
> CL-USER> (gov-cons 'a (gov-cons 'b (gov-cons 1 (gov-cons 'c nil))))
> ((((NIL C) 1) B) A)
> 
> 
> I believe that this represents well the doubt that I have about if I
> interpreted correctly the problem,
> I must do an exact clone of cons or gov-cons must invert the order of
> the objects?
> 
> Regards
> 

-- 
Cells: http://common-lisp.net/project/cells/

"I'll say I'm losing my grip, and it feels terrific."
    -- Smiling husband to scowling wife, New Yorker cartoon
From: Pascal Bourguignon
Subject: Re: Ansi Common Lisp chapter 3 exercise 6
Date: 
Message-ID: <87k62orlvz.fsf@thalassa.informatimago.com>
"Erick Lopez Carreon" <·····@fsl.org.mx> writes:

> Hello:
>
> I am doing the exercises of the chapter 3 of the Book Ansi Common Lisp,
> have doubt if I interpreted correctly the problem 6. I will appreciate
> very much his comments.
> Next the problem and the solution that I implemented:
>
> ---------------------------------------------------------------------------------------------------------
> ;;6.- After years of deliberation, a government comission has decided
> that
> ;;lists should be represented by using the cdr to point to the first
> ;;element and car to point to the rest of the list. Define the
> ;;government versions of the following functions:
> ;;cons  list length(for lists) member(for lists; no keywords)
>
> (defun gov-car (lst)
>   (cdr lst))
>
> (defun gov-cdr (lst)
>   (car lst))
>
> (defun gov-cons (obj lst)
>   (cons lst (cons obj nil)))

Wrong.
You want to keep the cons/car/cdr invariants:

(equal (gov-cons (gov-car x) (gov-cdr x)) x)
(equal (gov-car (gov-cons x y)) x)
(equal (gov-cdr (gov-cons x y)) y)

for any x, y.



> (defun gov-list (&rest objs)
>   (if (null objs)
>       nil
>       (cons (gov-cdr objs) (gov-car objs))))

Wrong.  
gov-list is exactly the same as list, only with gov-cons, gov-car  and gov-cdr.
Unless defun/call doesn't respect government edicts, of course, in which 
case you need a list->gov-list function to convert objs.


> (defun gov-length (lst)
>   (if (null lst)
>       0
>       (+ (gov-length (gov-car lst)) 1)))

Wrong. Once you've implemented the gov-cons, all the rest above is
implemented strictly the same.

> (defun gov-member (obj lst)
>   (if (null lst)
>       nil
>       (if (eql (gov-cdr lst) obj)
> 	  lst
> 	  (gov-member obj (gov-car lst)))))

Idem.

Instead of using these gov- names, you should shadow CL names, so you
can copy-and-paste the implementations of length, member and so on
from any CL implementation.


(defpackage "GOV"
  (:use "CL")
  (:shadow "CONS" "CAR" "CDR" "LIST" "LENGTH" "MEMBER")
  (:export "CONS" "CAR" "CDR" "LIST" "LENGTH" "MEMBER" "PRINT-LIST"))
(in-package "GOV")

(defun cons (a d) (cl:cons d a))
(defun car  (c)   (cl:cdr c))
(defun cdr  (c)   (cl:car c))



(defun cl-list->gov-list (cl-list)
  (if (null cl-list)
      '()
      (cons (cl:car cl-list) (cl-list->gov-list (cl:cdr cl-list)))))

(defun list (&rest args)
  ;; Ok, we haven't redefined defun and funcall/apply, so we'll have
  ;; to convert cl-list->gov-list first.
  (cl-list->gov-list args)        ; oops! We just copied the list so  
                                        ; nothing more needs to be done...
  )

;; All the rest is copy-and-paste of the source from any CL implementation.

(defun length (sequence)
  (etypecase sequence
    (vector (array-dimension sequence 0))
    (cl:cons (labels ((llength (list length)
                        (if (null list)
                            length
                            (llength (cdr list) (1+ length)))))
               (llength sequence 0)))))

(defun member (item list &key (key (function identity))
               (test (function eql))
               (test-not nil test-not-p))
  (cond
    ((null list) list)
    ((funcall (if test-not-p test-not test)
              item
              (funcall key (car list)))
     list)
    (t (apply (function member) item (cdr list) :key key :test test
              (when test-not-p (list :test-not test-not))))))

;; ...



(defun print-list (list &optional (stream *standard-output*))
  (princ "(")
  (when list
    (loop
       :for head = list :then (cdr head)
       :while (cdr head)
       :do (prin1 (car head)) (princ " ")
       :finally (prin1 (car head))))
  (princ ")")
  list)




GOV[73]> (print-list (list 1 2 3 4))
(1 2 3 4)
((((NIL . 4) . 3) . 2) . 1)
GOV[74]> (length (list 1 2 3 4))
4
GOV[75]> (print-list (member 3 (list 1 2 3 4 5)))
(3 4 5)
(((NIL . 5) . 4) . 3)
GOV[76]> (car (cons 1 2))
1
GOV[77]> (cdr (cons 1 2))
2
GOV[78]> (let ((x (cons 1 2))) (equal x (cons (car x) (cdr x))))
T
GOV[79]> (cons 1 2)
(2 . 1)
GOV[80]> 


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

Pour moi, la grande question n'a jamais �t�: �Qui suis-je? O� vais-je?� 
comme l'a formul� si adroitement notre ami Pascal, mais plut�t: 
�Comment vais-je m'en tirer?� -- Jean Yanne
From: Erick Lopez Carreon
Subject: Re: Ansi Common Lisp chapter 3 exercise 6
Date: 
Message-ID: <1161889172.260885.227010@e3g2000cwe.googlegroups.com>
Thanks for Pascal and KT for his comments.

The complete example from Pascal let me see what i was doing wrong :)

And complemented with KT response pointing i'm misunderstanding the
normal cons (and list) let me reach the following points:

- cons: Is a pair of pointers.
cons:
[a|nil] or [a|b] or [a| ] -> [b|nil]

So gov version of cons should behave:
[nil|a]  or [b|a] or [nil|b] <- [ |a]

The first pointer being the cdr and the second pointer being the car.

My first error was made the assumption that all the cons must end with
nil:

(defun gov-cons (obj lst)
  (cons lst (cons obj nil)))


- With cons i can construct lists, pairs and mixed lists (proper lists
or dotted lists)

'(a . (b . (c . nil)))
[a| ] -> [b| ] -> [c|nil]

Which prints:
(a b c)


'(a . (b . (c . d)))
[a| ] -> [b| ] -> [c|d]

Which prints:
(a b c . d)


Then gov list should be:

'((nil . c) . b ) . a)

However, must print the same as normal list, as Pascal show in their
example two functions are used.

To create the government version of list:

(defun cl-list->gov-list (cl-list)
  (if (null cl-list)
      '()
      (cons (cl:car cl-list) (cl-list->gov-list (cl:cdr cl-list)))))

And to print like normal list:

(defun print-list (list &optional (stream *standard-output*))
  (princ "(")
  (when list
    (loop
       :for head = list :then (cdr head)
       :while (cdr head)
       :do (prin1 (car head)) (princ " ")
       :finally (prin1 (car head))))
  (princ ")")
  list)

And for user friendliness:

(defun list (&rest args)
  ;; Ok, we haven't redefined defun and funcall/apply, so we'll have
  ;; to convert cl-list->gov-list first.
  (cl-list->gov-list args)        ; oops! We just copied the list so
                                        ; nothing more needs to be
done...
  )

For example:

#<PACKAGE "COMMON-LISP-USER">
CL-USER>  (list 1 2 3)
(1 2 3)
CL-USER>  (list 1 2 '(3 . 4))
(1 2 (3 . 4))
CL-USER> (in-package "GOV")
#<PACKAGE "GOV">
GOV> (print-list (list 1 2 3))
(1 2 3)
(((NIL . 3) . 2) . 1)
GOV> (print-list (list 1 2 '(3 . 4)))
(1 2 (3 . 4))
(((NIL 3 . 4) . 2) . 1)
GOV>

This two (cons and list) was where i had confusions.

Thank you again Ken and Pascal for your help

Regards 

P.S. If you think i'm still lost please tell me :)
From: Pascal Bourguignon
Subject: Re: Ansi Common Lisp chapter 3 exercise 6
Date: 
Message-ID: <87mz7irikn.fsf@thalassa.informatimago.com>
"Erick Lopez Carreon" <·····@fsl.org.mx> writes:
> P.S. If you think i'm still lost please tell me :)

You seem to get it.  Just to be sure, assume that now the government
wants to track the time of creation of government certified cons
cells, to be able to fight terrorism, so it specifies:

(gov2:creation-time (gov2:cons a d)) = universal-time of creation of gov2:cons
(gov2:car (gov2:cons a d)) = a
(gov2:cdr (gov2:cons a d)) = d
(let ((c (gov2:cons a d)))
   (sleep 4)
   (gov2:equal c (gov2:cons (gov2:car c) (gov2:cdr c)))) = T

Let implement it as a CL:CONS cell that contains the creation time in
its CL:CAR and the old GOV:CONS in its CL:CDR.


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

"You can tell the Lisp programmers.  They have pockets full of punch
 cards with close parentheses on them." --> http://tinyurl.com/8ubpf
From: Rob Warnock
Subject: Re: Ansi Common Lisp chapter 3 exercise 6
Date: 
Message-ID: <O4Gdnajpl_F9FNzYnZ2dnUVZ_rWdnZ2d@speakeasy.net>
Erick Lopez Carreon <·····@fsl.org.mx> wrote:
+---------------
| And complemented with KT response pointing i'm misunderstanding the
| normal cons (and list) let me reach the following points:
| - cons: Is a pair of pointers.
| cons:
| [a|nil] or [a|b] or [a| ] -> [b|nil]
+---------------

If you think that's an exhaustive partition of CONS then you're
still misunderstanding it a little (though maybe less than before).
Common Lisp CONS is *not* restricted to those three cases. *Both*
the CAR & CDR can point to other conses, which is how you get general
binary trees from CONS cells, as well as even more complex structures.
So in addition to the ones you've shown, you need to add this case,
and an infinity of similar ones:

  Start
    |
    |  +-------------------------------------------------+
    |  |                                                 |
    v  v                                                 |
    +---+   +---+   +---+   +---+                        |
    |*|*+-->|*|*|-->|*|*|-->|*|*|-->XYZ                  |
    ++--+   ++--+   ++--+   ++--+                        |
     |       |       |       |                           |
     |       |       |       v                           |
     |       |       |     +---+   +---+                 |
     |       |       |     |*|*+-->|*|*|-->#(17 35 26)   |
     |       |       |     ++--+   ++--+                 |
     |       |       |      |       |                    |
     |       |       |      v       v                    |
     |       |       v     789     "hello"               |
     |       |     +---+                                 |
     |       |     |*|*+-->"Bar"                         |
     |       |     ++--+                                 |
     |       |      |                                    |
     |       |      +------------------------------------+
     |       v
     |     +---+
     |     |*|*+-->FOO
     |     ++--+
     |      |
     |      v
     |    "qkwj"
     v
    +---+   +---+
    |*|*+-->|*|*+-->"bletch"
    ++--+   ++--+
     |       |
     v       v
    853    +---+
           |*|*+-->FOO
           ++--+
            |
	    v
	  191.25

Note: If you actually built that and printed it (with *PRINT-CIRCLE*
non-NIL, of course), it would print like this (I *think*, if I
haven't made a silly mistake somewhere):

    #1=((853 (191.25 . FOO) . "bletch") ("qkwj" . FOO) (#1# . "Bar")
	(789 "hello" . #(17 35 26)) . XYZ)

+---------------
| My first error was made the assumption that all the cons
| must end with nil...
+---------------

The other false assumption referred to above is that the CAR
of a cons is not itself a CONS. It can be. [Though you indirectly
show that you already know that at some level by describing
(CL-LIST->GOV-LIST '(a b c)) as (((NIL . c) . b ) . a).]

+---------------
| - With cons i can construct lists, pairs and mixed lists
|   (proper lists or dotted lists)
+---------------

And much, much more than that: arbitrary binary trees,
as well as general directed graphs of nodes with two
or fewer outgoing edges [a.k.a. binary directed graphs].


-Rob

p.s. Bonus problem: Write a function GRAPH-REVERSE that will
reverse the CAR & CDR of each cons cell in an arbitrary binary
directed graph -- *including* those with self-referential
or circular structure (as above) -- and return the resulting
"mirror" graph.

Bonus problem#2: Given such a GRAPH-REVERSE, does this suffice
for a definition of CL-LIST->GOV-LIST? If not, why not?

    (defun cl-list->gov-list (list)
      (graph-reverse list))

-----
Rob Warnock			<····@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607