From: Kenneth P. Turvey
Subject: There has got to be a better way...
Date: 
Message-ID: <slrn7i2s0b.oj4.kturvey@pug1.sprocketshop.com>
As part of another project I had need of a function to collapse a
possibly nested list into an unnested version containing the same atoms.
After finishing my first hack at it I thought, "There has got to be a
better way".  I was hoping some of you Lisp experts (I'm mediocre in
this language, at best) would be able to help me out.  I am not
particularly concerned with performance.  I would like to see a simple
and elegant solution. 

(defun collapse-list (l)
  "This function takes a list with that potentially contains nested
  elements and returns a list that contains all of the atoms contained
  in the original (and in the same quantities), but no nested lists.
  The atoms will be in their printing order in the returned list."
  (let ((result))
       (do ((temp_list (reverse l) (rest temp_list)))
           ((eq temp_list nil) result)
           (if (atom (first temp_list))
               (setf result (cons (first temp_list) result))
               (setf result
                     (append (collapse-list (first temp_list))
                             result)))))


-- 
Kenneth P. Turvey <·······@SprocketShop.com> 

  The world is full of fools and faint hearts; and yet everyone has
  courage enough to bear the misfortunes, and wisdom enough to manage
  the affairs, of his neighbor.  -- Benjamin Franklin

From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfw676ml1o6.fsf@world.std.com>
·······@pug1.sprocketshop.com (Kenneth P. Turvey) writes:

> As part of another project I had need of a function to collapse a
> possibly nested list into an unnested version containing the same atoms.
> After finishing my first hack at it I thought, "There has got to be a
> better way".  I was hoping some of you Lisp experts (I'm mediocre in
> this language, at best) would be able to help me out.  I am not
> particularly concerned with performance.  I would like to see a simple
> and elegant solution. 
> 
> (defun collapse-list (l)
>   "This function takes a list with that potentially contains nested
>   elements and returns a list that contains all of the atoms contained
>   in the original (and in the same quantities), but no nested lists.
>   The atoms will be in their printing order in the returned list."
>   (let ((result))
>        (do ((temp_list (reverse l) (rest temp_list)))
>            ((eq temp_list nil) result)
>            (if (atom (first temp_list))
>                (setf result (cons (first temp_list) result))
>                (setf result
>                      (append (collapse-list (first temp_list))
>                              result)))))

The problem with this solution is that the recursive call to collapse-list
conses a result value which you then have to copy (for the append) in
order to add to the list.  I don't have time to write it, but the
conventional way of avoiding this is to pass a seed list.  Something like:
 (defun collapse-list (l)
   (labels ((collapse (l seed)
              ... your main function ..
           )) 
      (collapse l '())))
where you find (append (collapse ...) result)
and replace it with something of the general shape 
  (collapse (car l) (collapse  (cdr l) seed)))
or something like that.  That's tree recursion.  You might need
list recursion and that's slightly different.  But the point is you
have to carry the result stack with you if you want to avoid the copy.
Dunno if that'll help.  Gotta run.  Early meeting.  (Yes, on a Saturday.)

 
From: Tim Bradshaw
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <ey3pv4ub79w.fsf@lostwithiel.tfeb.org>
* Kenneth P Turvey wrote:
> As part of another project I had need of a function to collapse a
> possibly nested list into an unnested version containing the same atoms.
> After finishing my first hack at it I thought, "There has got to be a
> better way".  I was hoping some of you Lisp experts (I'm mediocre in
> this language, at best) would be able to help me out.  I am not
> particularly concerned with performance.  I would like to see a simple
> and elegant solution. 

I wouldn't actually write it like this.

(defun collapse-tree (tree)
  (labels ((walk (tr acc)
	     (typecase tr
	       (cons (walk (car tr)
			   (walk (cdr tr) acc)))
		 (null acc)
		 (t (cons tr acc)))))
    (walk tree '())))

--tim
From: Vassil Nikolov
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7fuja6$nan$1@nnrp1.dejanews.com>
In article <···············@lostwithiel.tfeb.org>,
  Tim Bradshaw <···@tfeb.org> wrote:
> * Kenneth P Turvey wrote:
(...)
> > a function to collapse a
> > possibly nested list into an unnested version containing the same atoms.
(...)
> > I am not
> > particularly concerned with performance.  I would like to see a simple
> > and elegant solution.
(...)
> (defun collapse-tree (tree)
>   (labels ((walk (tr acc)
>              (typecase tr
>                (cons (walk (car tr)
>                            (walk (cdr tr) acc)))
>                (null acc)
>                (t (cons tr acc)))))
>     (walk tree '())))

(By the way, I think your post contained tab characters which screwed
up indentation somewhat for me.)

While I can't see a more elegant solution, I wonder if it would
be clearer to use explicit collecting (by means of WITH-COLLECTOR^1)
and left-to-right traversal (instead of right-to-left traversal
with the accumulator serving as an implicit collector).
__________
^1 non-standard, but free implementations are available, and very useful

--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: Tim Bradshaw
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <ey3lnfhng6i.fsf@lostwithiel.tfeb.org>
* Vassil Nikolov wrote:
> In article <···············@lostwithiel.tfeb.org>,
> (By the way, I think your post contained tab characters which screwed
> up indentation somewhat for me.)

Probably, emacs does deep weirdness with tabs and untabifying and
stuff.

> While I can't see a more elegant solution, I wonder if it would
> be clearer to use explicit collecting (by means of WITH-COLLECTOR^1)
> and left-to-right traversal (instead of right-to-left traversal
> with the accumulator serving as an implicit collector).

I might use that in real life.  I'd certainly try to use something
that didn't eat stack recursing on the CDRs which mine does.  And it
was a question about lists not trees so I wasn't really answering it.

But I wouldn't use a collecting macro if I was teaching this (and this
looks like some kind of semi-homework question).  The reason I
wouldn't is that, I think, it is hard enough for students to
understand how lists work, in particular what is fast and slow,
without burdening them with clever tricks like keeping tail pointers,
let alone hiding it behind nice syntax.  The danger is that they fail
to realise that lists are not arrays.

--tim
From: Lyman S. Taylor
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <372378CA.FF0CCF79@mindspring.com>
Tim Bradshaw wrote:
...
> 
> I might use that in real life.  I'd certainly try to use something
> that didn't eat stack recursing on the CDRs which mine does.  And it
> was a question about lists not trees so I wasn't really answering it.

  But nested lists are trees. :-)   At least you can look at them that 
  way in this context, removing the nesting. 

   (  ( a  b )  ( c d ) )

                    -----
                    |*|*|
                    -----
                    /   \
                   /     \
              -----      -----
              |*|*|      |*|\|
              -----      -----
              /  |        |
             a   |        |
                -----    -----
                |*|\|    |*|*|
                -----    -----
                /        /   \
               b        c    -----
                             |*|\|
                             -----
                             /
                            d

  While usually presented in a more horizontal fashion, the above is
  more conducive to illustrating the "treeness". 


  I'm not sure how you do this without a stack. You can explicitly
  manage your own or by recursion implicitly use the funcall call stack. 
  Once you go "down" one side of this "tree" how do you know how to get
  to the "other" branch? That has to be "recorded" somewhere... it might as
  well be the call stack. 


> ......  The danger is that they fail
> to realise that lists are not arrays.

   From experience this is a common way for newbies to deal with lists
   in right to left fashion. 

--

Lyman
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfw90bg8a32.fsf@world.std.com>
"Lyman S. Taylor" <············@mindspring.com> writes:

> Tim Bradshaw wrote:
> ...
> > 
> > I might use that in real life.  I'd certainly try to use something
> > that didn't eat stack recursing on the CDRs which mine does.  And it
> > was a question about lists not trees so I wasn't really answering it.
> 
>   But nested lists are trees. :-)   At least you can look at them that 
>   way in this context, removing the nesting. 
> 
>    (  ( a  b )  ( c d ) )
> 
>                     -----
>                     |*|*|
>                     -----
>                     /   \
>                    /     \
>               -----      -----
>               |*|*|      |*|\|
>               -----      -----
>               /  |        |
>              a   |        |
>                 -----    -----
>                 |*|\|    |*|*|
>                 -----    -----
>                 /        /   \
>                b        c    -----
>                              |*|\|
>                              -----
>                              /
>                             d

There is a "standard bug" in algorithms that try to do tree-recursion
on lists, and that comes with the ambiguity of recognizing NIL.

This code, contributed by someone (Tim?) has that bug:

> (defun collapse-tree (tree)
>   (labels ((walk (tr acc)
>              (typecase tr
>                (cons (walk (car tr)
>                            (walk (cdr tr) acc)))
>                (null acc)
>                (t (cons tr acc)))))
>     (walk tree '())))

(collapse-tree '((a b) (c d (e f nil g nil) h i) j))

loses the NILs.
From: Vassil Nikolov
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7g2cdf$sv7$1@nnrp1.dejanews.com>
In article <···············@world.std.com>,
  Kent M Pitman <······@world.std.com> wrote:

> There is a "standard bug" in algorithms that try to do tree-recursion
> on lists, and that comes with the ambiguity of recognizing NIL.
>
> This code, contributed by someone (Tim?) has that bug:
>
> > (defun collapse-tree (tree)
> >   (labels ((walk (tr acc)
> >              (typecase tr
> >                (cons (walk (car tr)
> >                            (walk (cdr tr) acc)))
> >                (null acc)
> >                (t (cons tr acc)))))
> >     (walk tree '())))
>
> (collapse-tree '((a b) (c d (e f nil g nil) h i) j))
>
> loses the NILs.

This is an issue every Lisp programmer _must_ be aware of.

Could be considered `a standard feature,' though...

Depends on the exact formulation of the problem, which on
its turn depends on the application (or the teacher's approach).
Absent that, both of these can be argued to be the right thing:

(collapse-tree '((a b) (c d (e f nil g nil) h i) j)) =>
  (a b c d e f nil g nil h i j)

(collapse-tree '((a b) (c d (e f  () g  ()) h i) j)) =>
  (a b c d e f g h i j)

Is #<the only object of type NULL> more an atom than a list,
or vice versa?

(Johnie, who do you love more: mommy or daddy?)

(Given that the Lisp printer prefers NIL to (), it appears that
Johnie loves mommy more...)

--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: Tim Bradshaw
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <ey31zh7w6d3.fsf@lostwithiel.tfeb.org>
* Lyman S Taylor wrote:
> Tim Bradshaw wrote:
>   But nested lists are trees. :-)   At least you can look at them that 
>   way in this context, removing the nesting. 

Yes, they are, but you get a choice over which side (car or cdr) you
recurse on and which you iterate over.  Quite apart from being just
wrong (sigh), my answer recurses on the cdr and iterates (assuming the
system does TRO, which before anyone picks me up, I know is not a safe
assumption) on the car.  So if I want something which deals with
things I'm thinking of as `lists' -- ie things which are probably
deep in the cdr direction but not in the car direction then that's a
bad choice, because I'd like my program not to blow up however long
the list is.

--tim

(I think what I'd write is actually something like

    (defun collapse-list (list)
      (let ((a '())
	    (at nil))
	(labels ((collect (x)
		   (if at
		       (setf (cdr at) (list x)
			     at (cdr at))
		       (setf a (list x)
			     at a)))
		 (clist (l)
		   (dolist (e l a)
		     (if (atom e)
			 (collect e)
			 (clist e)))))
	  (clist list))))

Except I'd write it as:

    (defun collapse-list (list)
      (collecting
       (iterate clist (l)
	 (dolist (e l)
	   (if (atom e)
	       (collect e)
	       (clist e))))))

And the point of showing that is that it's using DOLIST to go along
the lists and DOLIST shouldn't eat stack).
From: Tim Bradshaw
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <ey3yajfuh3h.fsf@lostwithiel.tfeb.org>
* I wrote:

>     (defun collapse-list (list)
>       (collecting
>        (iterate clist (l)
> 	 (dolist (e l)
> 	   (if (atom e)
> 	       (collect e)
> 	       (clist e))))))

Sigh.

     (defun collapse-list (list)
       (collecting
        (iterate clist ((l list))
 	 (dolist (e l)
 	   (if (atom e)
 	       (collect e)
 	       (clist e))))))

--tim
From: Vassil Nikolov
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7g61uv$6lk$1@nnrp1.dejanews.com>
In article <···············@lostwithiel.tfeb.org>,
  Tim Bradshaw <···@tfeb.org> wrote:
(...)
> Quite apart from being just
> wrong (sigh), my answer
(...)

Why?

--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: Tim Bradshaw
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <ey3btg9b2lc.fsf@lostwithiel.tfeb.org>
* Vassil Nikolov wrote:
> In article <···············@lostwithiel.tfeb.org>,
>   Tim Bradshaw <···@tfeb.org> wrote:
> (...)
>> Quite apart from being just
>> wrong (sigh), my answer
> (...)

> Why?

Why was it wrong?  Because it didn't deal with NIL right as Kent
pointed out.  I make this mistake all the time.

--tim
From: Vassil Nikolov
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7gatt7$h91$1@nnrp1.dejanews.com>
In article <···············@lostwithiel.tfeb.org>,
  Tim Bradshaw <···@tfeb.org> wrote:
> * Vassil Nikolov wrote:
> > In article <···············@lostwithiel.tfeb.org>,
> >   Tim Bradshaw <···@tfeb.org> wrote:
> > (...)
> >> Quite apart from being just
> >> wrong (sigh), my answer
> > (...)
>
> > Why?
>
> Why was it wrong?  Because it didn't deal with NIL right as Kent
> pointed out.  I make this mistake all the time.

Thanks for replying.  I thought I had missed some real bug.  The
way your solution dealt with NIL may or may not be wrong---depends
on the purpose.  And it is not difficult to change it from one
functionality to the other.

--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: Vassil Nikolov
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7g2cev$svl$1@nnrp1.dejanews.com>
In article <···············@lostwithiel.tfeb.org>,
  Tim Bradshaw <···@tfeb.org> wrote:
> * Vassil Nikolov wrote:
(...)
> > While I can't see a more elegant solution, I wonder if it would
> > be clearer to use explicit collecting (by means of WITH-COLLECTOR^1)
> > and left-to-right traversal (instead of right-to-left traversal
> > with the accumulator serving as an implicit collector).
(...)
> But I wouldn't use a collecting macro if I was teaching this (and this
> looks like some kind of semi-homework question).  The reason I
> wouldn't is that, I think, it is hard enough for students to
> understand how lists work, in particular what is fast and slow,
> without burdening them with clever tricks like keeping tail pointers,
> let alone hiding it behind nice syntax.  The danger is that they fail
> to realise that lists are not arrays.

I meant `clearer for the programmer already trained' (though on the
other hand _everything_ should be clear to the _really_ trained
programmer...).  You are quite right that `clear to trainees' implies
some very specific requirements.  It also depends on what the
teacher is actually trying to teach---besides tree traversal, this
problem might be considered in a context of recursively nested
streams (like the way the C preprocessor `linearises' nested
#includes), which is my favourite generalisation of the
collapse-tree/flatten problem.  (In that latter case, right-to-left
traversal doesn't look good because each nested stream can be
arbitrarily long, and the collect operations transforms into a
stream output operation.)

--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: Chris Croft-White
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <372341D6.908859AD@cam.ac.uk>
Vassil Nikolov wrote:

> In article <···············@lostwithiel.tfeb.org>,
>   Tim Bradshaw <···@tfeb.org> wrote:
> > * Kenneth P Turvey wrote:
> (...)
> > > a function to collapse a
> > > possibly nested list into an unnested version containing the same atoms.
> (...)
> > > I am not
> > > particularly concerned with performance.  I would like to see a simple
> > > and elegant solution.
> (...)
> > (defun collapse-tree (tree)
> >   (labels ((walk (tr acc)
> >              (typecase tr
> >                (cons (walk (car tr)
> >                            (walk (cdr tr) acc)))
> >                (null acc)
> >                (t (cons tr acc)))))
> >     (walk tree '())))
>
> (By the way, I think your post contained tab characters which screwed
> up indentation somewhat for me.)
>
> While I can't see a more elegant solution, I wonder if it would
> be clearer to use explicit collecting (by means of WITH-COLLECTOR^1)
> and left-to-right traversal (instead of right-to-left traversal
> with the accumulator serving as an implicit collector).

I think there may be a slightly more elegant method,

(defun collapse-list (list)
    (if (null list)
        nil
        (if (consp (car list))
            (append (collapse-list (car list))
                (collapse-list (cdr list)))
            (if (atom (car list))
                (cons (car list) (collapse-list (cdr list)))))))

I think this can be made more elegant, using a case/typecase structure, but this
gives a fairly clear idea of how it works, all you do is check if you are at the
end of a list, if so, return nil, if not, check the car of the list, if this is
an atom, return it, it it is a list, collapse that list, and append the
collapsed cdr to it.   This works, as the only things the car of a list can be
are nil, an atom, or a list.

I hope this is of use

Chris Croft-White
From: Lyman S. Taylor
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <37236EDB.C527DBF3@mindspring.com>
Chris Croft-White wrote:
...
> 
> I think there may be a slightly more elegant method,
> 
> (defun collapse-list (list)
>     (if (null list)
>         nil
>         (if (consp (car list))
>             (append (collapse-list (car list))
>                 (collapse-list (cdr list)))
>             (if (atom (car list))
>                 (cons (car list) (collapse-list (cdr list)))))))
> 

  Errr, you've missed the duality of NIL.   It is both a list and an atom!!!

 USER(15): (collapse-list '(a ( b c d)  ( () e)   f ))
(A B C D NIL E F)

  Additionally, you can do without the the extra predicate ( If something is 
  not nil and not  a cons then it is by definition an atom. There's no way to
  take the implicit "else" of that last if.  )

   (defun collapse-list ( list )
     (if (null  list )
          nil 
         (if (listp (car list ))
             (append (collapse-list (car list)) 
                     (collapse-list (cdr list)))
             ;;else (car list) is a  non-nil atom 
             (cons (car list ) (collapse-list (cdr list))))))


   or if you'd like to avoid the "right drift" of that code.... 

(defun collapse-list ( list )
  (cond ((null list ) nil )
        ((listp (car list)) 
           (append (collapse-list ( car list)) (collapse-list (cdr list))))
        (t  ; (car list ) must be non-nil atom
           (cons (car list) (collapse-list (cdr list))))))


 Since the predicates are used to determine three different cases, a cond
 works.  I suspect the cond macro will expand into the equivalent of 
 the original nested if, including the "extra" if.  It doesn't have the
 "extra" predicate though.  Ditto with typcase... it will likely expand into
 cond and that into a series of nested ifs. 

 I've usually seen this function in most textbooks under the name "flatten". 
               
 The "seed" method works  right-to-left over the tree which avoids the
 the garbage producing effect embedding an APPEND in a recursive process
 entails.    You could replace that with NONC and you'd get rid of the
 garbage problem.  [ There is still some "rewalking" of the subtree.
 However, avoiding that means staying at the end of original and the
 accumlated result.... which will require a macro to hide the mess. ]

--

Lyman
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfw7lr08a1m.fsf@world.std.com>
"Lyman S. Taylor" <············@mindspring.com> writes:

>   Errr, you've missed the duality of NIL.   It is both a list and an atom!!!

Oops. I just sent this same message.
From: Stig Hemmer
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <ekvbtgb489a.fsf@kallesol.pvv.ntnu.no>
Kent M Pitman <······@world.std.com> writes:
> "Lyman S. Taylor" <············@mindspring.com> writes:
> >   Errr, you've missed the duality of NIL.   It is both a list and an atom!!!
> Oops. I just sent this same message.

Not exactly.

As far as I could see, Lyman complained that a piece of code treated
() as NIL, whereas you complained that another piece of code treated
NIL as ().

Given that (EQ NIL ()), it is impossible to do this right without
defining what "right" means in this context.

So, to the original poster: How should NIL be treated? As an atom and
included, or as an empty list and flattened away?

Stig Hemmer,
Jack of a Few Trades.
From: Kenneth P. Turvey
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <slrn7ia0qm.r0h.kturvey@pug1.sprocketshop.com>
On 26 Apr 1999 19:11:13 +0200, Stig Hemmer <····@pvv.ntnu.no> wrote:
[Snip]
>
>Given that (EQ NIL ()), it is impossible to do this right without
>defining what "right" means in this context.
>
>So, to the original poster: How should NIL be treated? As an atom and
>included, or as an empty list and flattened away?
[Snip]

For my purposes, NIL should be treated as an atom.  I can see how this
would depend on the application though. 

I must admit, I had no idea what a can of worms I was opening with this
question.  It has been quite educational.


-- 
Kenneth P. Turvey <·······@SprocketShop.com> 

  In America, any boy may become president and I suppose that's just one
  of the risks he takes.
	-- Adlai Stevenson
From: Marco Antoniotti
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <lwiuaizdrb.fsf@copernico.parades.rm.cnr.it>
ENDP ?

Cheers


-- 
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa
From: Steve Gonedes
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <m2btgcrlfn.fsf@KludgeUnix.com>
·······@pug1.sprocketshop.com (Kenneth P. Turvey) writes:

< As part of another project I had need of a function to collapse a
< possibly nested list into an unnested version containing the same
< atoms.

You can use an accumulator instead of append; makes the code smaller.
This is from Norvigs AIP book.

(defun flatten (l)
  (flatten2 l ()))

(defun flatten2 (l accumulator)
  (cond ((null l) accumulator)
        ((atom l) (cons l accumulator))
        (t (flatten2 (car l)
                     (flatten2 (cdr l) accumulator)))))


You can use an optional parameter or a local function as well.

(defun flatten (l &optional accumulator)
  (cond ((null l) accumulator)
        ((consp l)
         (flatten (car l)
                  (flatten (cdr l) accumulator)))
       (t (cons l accumulator))))

I saw a version that uses pointers in cl-http, maybe it's worth
checking out...
From: Nick Levine
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <37244A99.60649A61@harlequin.co.uk>
This is my vote:

CL-USER 51 >
(defun collapse-list (l)
  (loop for x in l nconc
        (if (atom x)
            (list x)
          (collapse-list x))))
COLLAPSE-LIST

CL-USER 52 > (collapse-list +)
(DEFUN COLLAPSE-LIST L LOOP FOR X IN L NCONC IF ATOM X LIST X COLLAPSE-LIST
X)

CL-USER 53 >


 Kenneth P. Turvey wrote:

> As part of another project I had need of a function to collapse a
> possibly nested list into an unnested version containing the same atoms.
> After finishing my first hack at it I thought, "There has got to be a
> better way".  I was hoping some of you Lisp experts (I'm mediocre in
> this language, at best) would be able to help me out.  I am not
> particularly concerned with performance.  I would like to see a simple
> and elegant solution.
>
> (defun collapse-list (l)
>   "This function takes a list with that potentially contains nested
>   elements and returns a list that contains all of the atoms contained
>   in the original (and in the same quantities), but no nested lists.
>   The atoms will be in their printing order in the returned list."
>   (let ((result))
>        (do ((temp_list (reverse l) (rest temp_list)))
>            ((eq temp_list nil) result)
>            (if (atom (first temp_list))
>                (setf result (cons (first temp_list) result))
>                (setf result
>                      (append (collapse-list (first temp_list))
>                              result)))))
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfwaevvoa5d.fsf@world.std.com>
Nick Levine <····@harlequin.co.uk> writes:

> This is my vote:
> 
> CL-USER 51 >
> (defun collapse-list (l)
>   (loop for x in l nconc
>         (if (atom x)
>             (list x)
>           (collapse-list x))))
> COLLAPSE-LIST
> 
> CL-USER 52 > (collapse-list +)
> (DEFUN COLLAPSE-LIST L LOOP FOR X IN L NCONC IF ATOM X LIST X COLLAPSE-LIST
> X)

Uh, just to be clear, Nick's code is fine but, cute as it is for
example purposes, programmers are ill-advised to do anything like his
example in production code.  Doing a destructive side-effect on
anything you've given to EVAL or COMPILE other than a quoted literal
could have undefined consequences.  For example, if the system had
kept a pointer to that very code to execute interpreted, it could find
its own datastructure falling apart as it executed.
From: Nick Levine
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <37245A1F.105CE48C@harlequin.co.uk>
Kent M Pitman wrote:

> Uh, just to be clear, Nick's code is fine but, cute as it is for
> example purposes, programmers are ill-advised to do anything like his
> example in production code.



Hang about! This code only destructively-modifies conses it has built itself. (Or
is Nick even deeper asleep than usual this morning? What did I miss?)

CL-USER 52 > (COLLAPSE-LIST +)
(DEFUN COLLAPSE-LIST L LOOP FOR X IN L NCONC IF ATOM X LIST X COLLAPSE-LIST X)

CL-USER 53 > ++
(DEFUN COLLAPSE-LIST (L) (LOOP FOR X IN L NCONC (IF (ATOM X) (LIST X)
(COLLAPSE-LIST X))))

CL-USER 54 >



> Doing a destructive side-effect on
> anything you've given to EVAL or COMPILE other than a quoted literal
> could have undefined consequences.  For example, if the system had
> kept a pointer to that very code to execute interpreted, it could find
> its own datastructure falling apart as it executed.

  Oh, absolutely. I didn't think I had.

- nick
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfwwvyzqxwl.fsf@world.std.com>
Nick Levine <····@harlequin.co.uk> writes:

> Kent M Pitman wrote:
> 
> > Uh, just to be clear, Nick's code is fine but, cute as it is for
> > example purposes, programmers are ill-advised to do anything like his
> > example in production code.
> 
> Hang about! This code only destructively-modifies conses it has built 
> itself. 

Oops.  You're right.  Ignore me.

(I wish I could say I make these big errors once in a while just to make sure
no one takes everything I say as always right, but it turns out there wasn't
nearly so much planning behind this one.)
From: ··········@scientia.com
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7g1qht$b9v$1@nnrp1.dejanews.com>
In article <···············@world.std.com>,
  Kent M Pitman <······@world.std.com> wrote:
> Nick Levine <····@harlequin.co.uk> writes:
>
> > This is my vote:
> >
> > CL-USER 51 >
> > (defun collapse-list (l)
> >   (loop for x in l nconc
> >         (if (atom x)
> >             (list x)
> >           (collapse-list x))))
> > COLLAPSE-LIST
> >
> > CL-USER 52 > (collapse-list +)
> > (DEFUN COLLAPSE-LIST L LOOP FOR X IN L NCONC IF ATOM X LIST X COLLAPSE-LIST
> > X)
>
> Uh, just to be clear, Nick's code is fine but, cute as it is for
> example purposes, programmers are ill-advised to do anything like his
> example in production code.  Doing a destructive side-effect on
> anything you've given to EVAL or COMPILE other than a quoted literal
> could have undefined consequences.  For example, if the system had
> kept a pointer to that very code to execute interpreted, it could find
> its own datastructure falling apart as it executed.
>

So, for variations on the same theme

(defun flatten (lyst)
   (mapcan
     #'(lambda (x) (if (atom x) `(,x) (flatten x)))
     lyst))

or, replace mapcan with mapappend for a non-destructive version.

[where mapappend could be:
   (defun mapappend (fn lists)
       (apply #'append (mapcar #'fn lists)))
]

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfwvhejqxj8.fsf@world.std.com>
··········@scientia.com writes:

After being rightly rebuked by Nick for my last comment on destructiveness
I'm going to blunder ahead to another, hoping I don't repeat the feat.

> (defun flatten (lyst)
>    (mapcan
>      #'(lambda (x) (if (atom x) `(,x) (flatten x)))
>      lyst))

This illustrates one of the great stylistic puzzles of destructive
wisdom.  Technically, backquote-generated structure is not guaranteed
to be "fresh", but it is hard to imagine how this could be non-fresh.
Even so, I recommend (list x) for clarity.  [If you have a lisp machine,
(ncons x) is better because of cdr coding.]

> or, replace mapcan with mapappend for a non-destructive version.
> 
> [where mapappend could be:
>    (defun mapappend (fn lists)
>        (apply #'append (mapcar #'fn lists)))
> ]

Not only is this unnecessarily cons-wasteful (MAPCAN really was find
because, as Nick points out, the structure being modified was all
structure made by the flatten function in the first place and not
freshly consed) but also: This has a bug in that #'fn is not the right
way to funcall a bound variable.  You want #'(lambda (x) (funcall fn x))
in situations like this.  [Or if you have the lisp machine's circular-list
function, (mapcar #'funcall (circular-list fn) lists).  Admittedly
obscure, but some use it idiomatically--almost to the point that I think
the compiler should have had an optimizer for it that turned it back
into something that didn't waste the single cons needed to make the circular
list.]
From: Bernhard Pfahringer
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7g1uif$48rg$1@www.univie.ac.at>
In article <···············@world.std.com>,
Kent M Pitman  <······@world.std.com> wrote:
>> 
>> [where mapappend could be:
>>    (defun mapappend (fn lists)
>>        (apply #'append (mapcar #'fn lists)))
>> ]
>
>freshly consed) but also: This has a bug in that #'fn is not the right
>way to funcall a bound variable.  You want #'(lambda (x) (funcall fn x))
>in situations like this.  [Or if you have the lisp machine's circular-list
>function, (mapcar #'funcall (circular-list fn) lists).  Admittedly

What's wrong with the simpler (mapcar fn lists) ?

Bernhard
-- 
--------------------------------------------------------------------------
Bernhard Pfahringer
Austrian Research Institute for  http://www.ai.univie.ac.at/~bernhard/
Artificial Intelligence          ········@ai.univie.ac.at 
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfwn1zvpe0n.fsf@world.std.com>
········@hummel.ai.univie.ac.at (Bernhard Pfahringer) writes:

> (mapcar #'funcall (circular-list fn) lists).  Admittedly
> 
> What's wrong with the simpler (mapcar fn lists) ?

Uh....

Nothing.

Blush.

It's weird how sometimes you get caught thinking about a certain problem
a certain way that obscures the obvious and someone has to point it out.
Thanks.

I took vacation to work on my scifi novel this week.  I'll take this
second correction of of the day as an omen that I should be doing more of
that and less of this for a few days. :-)
From: ··········@scientia.com
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7g2323$jnk$1@nnrp1.dejanews.com>
In article <···············@world.std.com>,
  Kent M Pitman <······@world.std.com> wrote:
> ··········@scientia.com writes:

[]

> Not only is this unnecessarily cons-wasteful (MAPCAN really was find
> because, as Nick points out, the structure being modified was all
> structure made by the flatten function in the first place and not
> freshly consed)

Yes, I just made the comment about mapappend in response to the comments about
destructive version.

At the risk of rehashing old ground: what is "unnecessary" waste is partly a
matter of opinion. The space and/or time efficiency of lots of code can be
improved on. The question is how much effort one wants to invest in doing so.
For toy examples it's  obvious that using a destructive function is best, but
sometimes the cost of figuring out whether its ok do this is potenitally
greater than the cost of allowing a less effecient piece of code to be used.



>                         This has a bug in that #'fn is not the right
> way to funcall a bound variable.

Yes, a typo on my part I'm afraid.




-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: Erik Naggum
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <3134139360212576@naggum.no>
* ··········@scientia.com
| At the risk of rehashing old ground: what is "unnecessary" waste is
| partly a matter of opinion.  The space and/or time efficiency of lots of
| code can be improved on.  The question is how much effort one wants to
| invest in doing so.

  I can understand why you cons up new articles with the same old defense
  for the same old unskilled Lisp style rather than reuse existing defenses
  by reference...

#:Erik
From: Vassil Nikolov
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7g2ccl$suv$1@nnrp1.dejanews.com>
In article <···············@world.std.com>,
  Kent M Pitman <······@world.std.com> wrote:
> ··········@scientia.com writes:
(...)
> > (defun flatten (lyst)
> >    (mapcan
> >      #'(lambda (x) (if (atom x) `(,x) (flatten x)))
> >      lyst))
>
> This illustrates one of the great stylistic puzzles of destructive
> wisdom.  Technically, backquote-generated structure is not guaranteed
> to be "fresh", but it is hard to imagine how this could be non-fresh.

Not that hard, perhaps.  What if, by the law of perverse solutions,
the backquote construct is implemented so that for `(,x) it does
a REPLACA on the cons produced by the reader when it processed the
opening parenthesis.  I'd like to be corrected that this is illegal.

> Even so, I recommend (list x) for clarity.  [If you have a lisp machine,
> (ncons x) is better because of cdr coding.]

Not just for clarity.  It may be a matter of personal attitude, but
for me backquoted lists are `semi-literal' and it bugs me if they
are destructively modified, almost like it would bug me to see

  (mapcan #'(lambda (x) (if (atom x) '(atom) '(list))) atoms/lists)

--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: ··········@scientia.com
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7g3pnt$63j$1@nnrp1.dejanews.com>
In article <············@nnrp1.dejanews.com>,
  Vassil Nikolov <········@poboxes.com> wrote:
> Not that hard, perhaps.  What if, by the law of perverse solutions,
> the backquote construct is implemented so that for `(,x) it does
> a REPLACA on the cons produced by the reader when it processed the
> opening parenthesis.  I'd like to be corrected that this is illegal.
>

No I think you're right; a quick look at Steele suggests that anything EQUAL
to (list x) would be OK here.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfwiuaigmgi.fsf@world.std.com>
··········@scientia.com writes:

> In article <············@nnrp1.dejanews.com>,
>   Vassil Nikolov <········@poboxes.com> wrote:
> > Not that hard, perhaps.  What if, by the law of perverse solutions,
> > the backquote construct is implemented so that for `(,x) it does
> > a REPLACA on the cons produced by the reader when it processed the
> > opening parenthesis.  I'd like to be corrected that this is illegal.
> >
> 
> No I think you're right; a quick look at Steele suggests that anything EQUAL
> to (list x) would be OK here.

The critical thing is that (list x) conses fresh structure.
(eq (list x) (list x)) is guaranteed to yield false.
Not so for (eq (rplaca x 'a) (rplaca x 'b)), which yields true.

Further, if you changed the car of the cons which was (,x), where
would you remember the ,x part in case the form was evaluated
a second time?
From: ··········@scientia.com
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7g4op6$11e$1@nnrp1.dejanews.com>
In article <···············@world.std.com>,
  Kent M Pitman <······@world.std.com> wrote:
> ··········@scientia.com writes:
>
> > In article <············@nnrp1.dejanews.com>,
> >   Vassil Nikolov <········@poboxes.com> wrote:
> > > Not that hard, perhaps.  What if, by the law of perverse solutions,
> > > the backquote construct is implemented so that for `(,x) it does
> > > a REPLACA on the cons produced by the reader when it processed the
> > > opening parenthesis.  I'd like to be corrected that this is illegal.
> > >
> >
> > No I think you're right; a quick look at Steele suggests that anything EQUAL
> > to (list x) would be OK here.
>
> The critical thing is that (list x) conses fresh structure.
> (eq (list x) (list x)) is guaranteed to yield false.
> Not so for (eq (rplaca x 'a) (rplaca x 'b)), which yields true.


I think we're at cross purposes: by "OK here" I was meant to say that any
such value would be a valid implementation for the result of the backquote
form, not that it would neccessarily be the right thing in the oringinal
function defn.

As you say, if mapcan is being used it is desirable that you have fresh lists.
My error was that I hadn't appreciated that the precise identity of the object
constructed by `(,x) is implementation dependent, provided it's EQUAL to
(list x).









-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: Vassil Nikolov
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7g634k$7l7$1@nnrp1.dejanews.com>
In article <············@nnrp1.dejanews.com>,
  Vassil Nikolov <········@poboxes.com> wrote:
> Not that hard, perhaps.  What if, by the law of perverse solutions,
> the backquote construct is implemented so that for `(,x) it does
> a REPLACA on the cons produced by the reader when it processed the
> opening parenthesis.  I'd like to be corrected that this is illegal.

In article <···············@world.std.com>,
  Kent M Pitman <······@world.std.com> wrote:
> The critical thing is that (list x) conses fresh structure.
> (eq (list x) (list x)) is guaranteed to yield false.
> Not so for (eq (rplaca x 'a) (rplaca x 'b)), which yields true.

Yes, but what in the language definition specifically implies that
`(,x) must be fresh?  (Apart from the fact that everybody knows
it is the Wrong Thing if it is not fresh.)

> Further, if you changed the car of the cons which was (,x), where
> would you remember the ,x part in case the form was evaluated
> a second time?

`(,X) must be read as a form which, when evaluated, produces a list
of one element which is the value of X, right?  (The canonical such
form is (LIST X).)  I had in mind reading that as the following form

  (progn (replaca #1=#:the-cons-the-reader-made x) #1#)

or something like that.  Evaluating this form evaluates X and
returns a list whose car is the value of X thus produced.

Once again: I am not advocating such a perverse way of doing it
(and can't think of a reason that would justify it); I just want
to learn if and how this is illegal (and not just ugly and
counterproductive).

--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: Stig Hemmer
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <ekv4sm1t4n5.fsf@ra.pvv.ntnu.no>
Vassil Nikolov <········@poboxes.com> writes:
> `(,X) must be read as a form which, when evaluated, produces a list
> of one element which is the value of X, right?  (The canonical such
> form is (LIST X).)  I had in mind reading that as the following form
> 
>   (progn (replaca #1=#:the-cons-the-reader-made x) #1#)
> 
> or something like that.  Evaluating this form evaluates X and
> returns a list whose car is the value of X thus produced.

Well, I can't say wether such an implementation would be technically
legal or not, but it sure would break a lot of existing code.

The problem is that a second call to this form would destroy the
result of the first one.  People tend to rely on this not happening.

If you read back you will find that Kent wasn't talking about
_legality_ but about _clearity_.

Consider `(,X Y).

An implementation could rewrite that as (CONS X '(Y)), with the '(Y)
being a shared constant.

In this case, a call to the form would not destroy previous results,
but it would still be a bad thing to give this to NCONC.

While it is hard to imagine `(,X) giving that sort of problems, it is
still good to use (LIST X) to make it clear to _human_ readers that we
want new structure.

Stig Hemmer,
Jack of a Few Trades.
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfwbtg88w8j.fsf@world.std.com>
Stig Hemmer <····@pvv.ntnu.no> writes:

> Consider `(,X Y).
> 
> An implementation could rewrite that as (CONS X '(Y)), with the '(Y)
> being a shared constant.
> 
> In this case, a call to the form would not destroy previous results,
> but it would still be a bad thing to give this to NCONC.
> 
> While it is hard to imagine `(,X) giving that sort of problems, it is
> still good to use (LIST X) to make it clear to _human_ readers that we
> want new structure.

This is exactly what I meant, yes.
Thanks for holding the fort while I'm working on my scifi novel...
Back to the grind.
From: Vassil Nikolov
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7gats9$h86$1@nnrp1.dejanews.com>
In article <···············@ra.pvv.ntnu.no>,
  Stig Hemmer <····@pvv.ntnu.no> wrote:
> Vassil Nikolov <········@poboxes.com> writes:
> > `(,X) must be read as a form which, when evaluated, produces a list
> > of one element which is the value of X, right?  (The canonical such
> > form is (LIST X).)  I had in mind reading that as the following form
> >
> >   (progn (replaca #1=#:the-cons-the-reader-made x) #1#)
> >
> > or something like that.  Evaluating this form evaluates X and
> > returns a list whose car is the value of X thus produced.
>
> Well, I can't say wether such an implementation would be technically
> legal or not, but it sure would break a lot of existing code.
>
> The problem is that a second call to this form would destroy the
> result of the first one.  People tend to rely on this not happening.

I did write `perverse,' `ugly,' *and* `counterproductive,' didn't I?

> If you read back you will find that Kent wasn't talking about
> _legality_ but about _clearity_.

Indeed he wasn't; it was me who took the occasion to ask about
legality.

> Consider `(,X Y).
>
> An implementation could rewrite that as (CONS X '(Y)), with the '(Y)
> being a shared constant.

A literal constant that may be shared, you mean, of course.

> In this case, a call to the form would not destroy previous results,
> but it would still be a bad thing to give this to NCONC.
>
> While it is hard to imagine `(,X) giving that sort of problems, it is
> still good to use (LIST X) to make it clear to _human_ readers that we
> want new structure.

Absolutely.  Now, back to my question:

Can you or anyone confirm or contradict that the above RPLACA implementation
is legal?  If it is, it might break people's code, but people should
not rely on implementations not doing legal things, shouldn't they?
Please understand me correctly: I'd rather have that illegal, but I
can't see it illegal in the language specification.

--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: Stig Hemmer
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <ekvn1zqma22.fsf@iq.pvv.ntnu.no>
Vassil Nikolov <········@poboxes.com> writes:
> Can you or anyone confirm or contradict that the above RPLACA implementation
> is legal?  If it is, it might break people's code, but people should
> not rely on implementations not doing legal things, shouldn't they?
> Please understand me correctly: I'd rather have that illegal, but I
> can't see it illegal in the language specification.

From section 2.4.6:

[description of possible implementation]
: An implementation is free to interpret a backquoted form F1 as any
: form F2 that, when evaluated, will produce a result that is the same
: under equal as the result implied by the above definition, provided
: that the side-effect behavior of the substitute form F2 is also
: consistent with the description given above. The constructed copy of
: the template might or might not share list structure with the
: template itself. As an example, the above definition implies that
[example]

As far as I can see, the RPLACA version would _not_ have side-effect
behavior consistent with the description given above this quote.

Stig Hemmer,
Jack of a Few Trades.
From: Vassil Nikolov
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7gcnfe$29d$1@nnrp1.dejanews.com>
In article <···············@iq.pvv.ntnu.no>,
  Stig Hemmer <····@pvv.ntnu.no> wrote:
> Vassil Nikolov <········@poboxes.com> writes:
> > Can you or anyone confirm or contradict that[ `(,X) being
    read as (PROGN (RPLACA #1=#:THE-CONS-THE-READER-MADE X) #1#) ]
> > is legal?
(...)
>
> From section 2.4.6:
>
> [description of possible implementation]
> : An implementation is free to interpret a backquoted form F1 as any
> : form F2 that, when evaluated, will produce a result that is the same
> : under equal as the result implied by the above definition, provided
> : that the side-effect behavior of the substitute form F2 is also
> : consistent with the description given above. The constructed copy of
> : the template might or might not share list structure with the
> : template itself. As an example, the above definition implies that
> [example]
>
> As far as I can see, the RPLACA version would _not_ have side-effect
> behavior consistent with the description given above this quote.

Thanks for noting this, but I guess I need a language lawyer to say
what `consistent' means in this case.

I wonder if there could be a situation where it would be important
to (drastically) minimise consing by backquote forms (which is the
only virtue I can see of the RPLACA approach).

(Once again: I am not advocating such an approach, just want to
know if an implementation could get away with it.)

--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: Barry Margolin
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <DHlW2.222$jw4.20931@burlma1-snr2>
In article <············@nnrp1.dejanews.com>,
Vassil Nikolov  <········@poboxes.com> wrote:
>In article <···············@iq.pvv.ntnu.no>,
>  Stig Hemmer <····@pvv.ntnu.no> wrote:
>> As far as I can see, the RPLACA version would _not_ have side-effect
>> behavior consistent with the description given above this quote.
>
>Thanks for noting this, but I guess I need a language lawyer to say
>what `consistent' means in this case.
>
>I wonder if there could be a situation where it would be important
>to (drastically) minimise consing by backquote forms (which is the
>only virtue I can see of the RPLACA approach).

One thing I like to consider in this discussion is the distinction made
between ',@' and '.,' in backquoted expressions.  When ',.' is used,
explicit license is given to destroy the list that follows it.  I infer
that the intent is that all other forms do *not* allow destruction, they
only allow sharing.

-- 
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Vassil Nikolov
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7gl11k$js8$1@nnrp1.dejanews.com>
In article <···················@burlma1-snr2>,
  Barry Margolin <······@bbnplanet.com> wrote:
> In article <············@nnrp1.dejanews.com>,
> Vassil Nikolov  <········@poboxes.com> wrote:
> >In article <···············@iq.pvv.ntnu.no>,
> >  Stig Hemmer <····@pvv.ntnu.no> wrote:
> >> As far as I can see, the RPLACA version would _not_ have side-effect
> >> behavior consistent with the description given above this quote.
> >
> >Thanks for noting this, but I guess I need a language lawyer to say
> >what `consistent' means in this case.
> >
> >I wonder if there could be a situation where it would be important
> >to (drastically) minimise consing by backquote forms (which is the
> >only virtue I can see of the RPLACA approach).
>
> One thing I like to consider in this discussion is the distinction made
> between ',@' and '.,' in backquoted expressions.  When ',.' is used,
> explicit license is given to destroy the list that follows it.  I infer
> that the intent is that all other forms do *not* allow destruction, they
> only allow sharing.

Yes, that's a good point I had overlooked.  It does indirectly
show that destruction is not allowed for "," and ",@".

Also Tim Bradshaw's post (which doesn't show up in DejaNews, so
I can't respond to it directly) gives another line of thought.
Since destructive modification of backquote templates would
lead to destructive modification of conses that are part of
Lisp code, and that is illegal, backquote could not be used in
macros.  Since this is absurd, it can be inferred, again indirectly,
that destructive modification is not allowed.

Still, I would be happier with a more explicit prohibition.
Such as: the evaluation of a backquote form (with the exception
of ",.") may not lead to destructive modification of conses/vectors
that are parts of structure returned by a backquote form.

(It is an overkill to prohibit any destructive modification
whatsoever---backquotes should be able to use NCONC, for
example, if appropriate.)

--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfw676996qu.fsf@world.std.com>
Vassil Nikolov <········@poboxes.com> writes:

> Still, I would be happier with a more explicit prohibition.
> Such as: the evaluation of a backquote form (with the exception
> of ",.") may not lead to destructive modification of conses/vectors
> that are parts of structure returned by a backquote form.

It probably should say.  But really, there is just no rational way that it
could be meaningful to do what you're suggesting.  The only language
constructs I know that have the kind of bizarre properties you're talking
about all plainly identify that they do what they do:

 * Restarts are defined only to have dynamic extent.
   That is, they are potentially aggressively recycled
   (prior to GC proof of non-use).

 * Dynamic-extent objects (created by things declared with
   the declaration of the same name) may be aggressively
   recycled.

 * Many people make resource pools with this kind of stern
   reuse property.

 * The Lisp Machine has a :line-in operation for streams which is
   like what read-line does but gives you the *same* (EQ) line every
   time.  You must copy its contents elsewhere before calling the :line-in
   operation anew, so the line is a "buffer" not a result "object".

But as a rule, the situation you're saying goes without saying because 
it would be utterly devastating to code if it were not so.

Can + return a pointer to a number that is rplac'd on subsequent additions?
Can gensym return an object that, while unique, is possibly the same unique
object as it has returned before?  How many places would we have to put the
requirement?

The whole concept of "identity" is about the idea that the individual matters.
When you have a pointer to something with properties of any kind, it can only
be said to have such properties if you can rely on them to be true absent a
change.  When objects are shared, a change to one changes the other, and any
reasoning you did about one destroys the other, completely undercutting any
kind of monotonicity of truth you might have assembled about your knowledge
of objects in the world.

I think this is a truth that is, to paraphrase Tom Jefferson slightly out
off context, self-evident.  (Remember, Tom did speak of all men [sic] being
created "equal".  He didn't mean to say they were all created eq.  I'm sure
in his heart he knew that would lead to later trouble of the most profound
kind.)
From: Vassil Nikolov
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7grgbn$96o$1@nnrp1.deja.com>
In article <···············@world.std.com>,
  Kent M Pitman <······@world.std.com> wrote:
> Vassil Nikolov <········@poboxes.com> writes:
>
> > Still, I would be happier with a more explicit prohibition.
> > Such as: the evaluation of a backquote form (with the exception
> > of ",.") may not lead to destructive modification of conses/vectors
> > that are parts of structure returned by a backquote form.
>
> It probably should say.  But really, there is just no rational way that it
> could be meaningful to do what you're suggesting.  The only language
> constructs I know that have the kind of bizarre properties you're talking
> about all plainly identify that they do what they do:
(...)  ;list of cases
>
> But as a rule, the situation you're saying goes without saying because
> it would be utterly devastating to code if it were not so.
(...)  ;other instructive remarks omitted for brevity
>
> I think this is a truth that is, to paraphrase Tom Jefferson slightly out
> off context, self-evident.
(...)

You are right.  In fact, since I found it hard to formulate such
a prohibition, I did hesitate a little before posting that sentence
above.  I really should have listened to my inner voice better, and
thought twice.  (But there was a silver lining, in your coming up
with an instructive post and a list of cases that I did not have
in my mind.)  Perhaps I am the kind of person who likes explicitness
too much (and it is indeed plain impossible to formulate _everything_
explicitly), but even I _would_ have been happier if the illegality
of a `destructive backquote-comma' could be inferred from the rest
of the language spec.  Thanks to the responses there were in this
thread, I can now see that it indeed can reasonably well be inferred
that way.

If I may reuse the analogy between language descriptions (such as
the ANSI CL spec) and laws, I wonder about the following.  In my
country at least (I have no idea about the way it is elsewhere),
the passing of a law often leads to the publication of a book or
books that provide commentaries on the law.  Such books clarify
various points of the law, and also show what can be inferred from
the various articles and paragraphs without actually being written
there explicitly.  Besides, in many countries rulings by courts of
law provide, among other things, a similar function.  (In many
countries there is also a court of law specialised just in such
activity, e.g. a constitutional court whose sole job is to say
what follows from the constitution regarding a specific matter.)
Now, what is there in the Lisp world that would be analogous to
(i) books commenting on the language spec (Paul Graham's books?
CLtL and CLtL2 provide some commentaries, but not very much), or to
(ii) a `constitutional court' that clarifies with some authority
the standard (the collective wisdom of experts that post in
comp.lang.lisp?).

--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
   LEGEMANVALEMFVTVTVM  (Ancient Roman programmers' adage.)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfw7lqm41r0.fsf@world.std.com>
Vassil Nikolov <········@poboxes.com> writes:

> In my
> country at least (I have no idea about the way it is elsewhere),
> the passing of a law often leads to the publication of a book or
> books that provide commentaries on the law.

We were specifically advised against this by ANSI at the first X3J13
meeting to avoid exposure to lawsuits, with which ANSI members have
apparently had some experience.  The issue is, as I recall, that if
someone has a bizaree interpretation, they may build a business on it.
To say that it's invalid if it's a possible interpretation is to
remove their legitimate credential.  The marketplace, not an appeal to
standards, is intended to weed out such issues.  If people flock to
such a Lisp, that is the proper indication that it's got the right idea.

In the small, this is probably not a big deal.  I doubt anyone will
sue anyone over a statement about a specific operator.  But making a 
book full of opinions, especially if accompanied by self-serving 
conclusions from one vendor about how another vendor's Lisp is wrong
is not a good idea.  And having several vendors team up outside the 
ANSI (or other standards body) process is also not a good idea for
anti-trust reasons.

One is better writing books that just say "I think this is the right thing"
than books that say "I think Fred's way is wrong".  But what you're asking
for is not a "style" thing but a "rule" thing, and I think you can only
get that from the committee itself.

> Besides, in many countries rulings by courts of
> law provide, among other things, a similar function.

Although the band of us who do this are sometimes called language
lawyers, there is no court process in standards work, and that's
not accidental.  The marketplace is the court.

The ANSI subcommittees, of course, can issue corrections and opinions.
But never as individuals.  Only as a collective committee action.
From: Howard R. Stearns
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <3725C0B2.2AE8C99B@elwood.com>
Kent M Pitman wrote:
> ...  You want #'(lambda (x) (funcall fn x))
> in situations like this.  [Or if you have the lisp machine's circular-list
> function, (mapcar #'funcall (circular-list fn) lists).  Admittedly
> obscure, but some use it idiomatically--almost to the point that I think
> the compiler should have had an optimizer for it that turned it back
> into something that didn't waste the single cons needed to make the circular
> list.]

What is circular-list?
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfwg15mgm6a.fsf@world.std.com>
"Howard R. Stearns" <······@elwood.com> writes:

> Kent M Pitman wrote:
> > ...  You want #'(lambda (x) (funcall fn x))
> > in situations like this.  [Or if you have the lisp machine's circular-list
> > function, (mapcar #'funcall (circular-list fn) lists).  Admittedly
> > obscure, but some use it idiomatically--almost to the point that I think
> > the compiler should have had an optimizer for it that turned it back
> > into something that didn't waste the single cons needed to make the circular
> > list.]
> 
> What is circular-list?

(defun circular-list (&rest x)
  (nconc x x))
From: Nick Levine
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <37244AA1.D8EA1FD2@harlequin.co.uk>
This is my vote:

CL-USER 51 >
(defun collapse-list (l)
  (loop for x in l nconc
        (if (atom x)
            (list x)
          (collapse-list x))))
COLLAPSE-LIST

CL-USER 52 > (collapse-list +)
(DEFUN COLLAPSE-LIST L LOOP FOR X IN L NCONC IF ATOM X LIST X COLLAPSE-LIST
X)

CL-USER 53 >


 Kenneth P. Turvey wrote:

> As part of another project I had need of a function to collapse a
> possibly nested list into an unnested version containing the same atoms.
> After finishing my first hack at it I thought, "There has got to be a
> better way".  I was hoping some of you Lisp experts (I'm mediocre in
> this language, at best) would be able to help me out.  I am not
> particularly concerned with performance.  I would like to see a simple
> and elegant solution.
>
> (defun collapse-list (l)
>   "This function takes a list with that potentially contains nested
>   elements and returns a list that contains all of the atoms contained
>   in the original (and in the same quantities), but no nested lists.
>   The atoms will be in their printing order in the returned list."
>   (let ((result))
>        (do ((temp_list (reverse l) (rest temp_list)))
>            ((eq temp_list nil) result)
>            (if (atom (first temp_list))
>                (setf result (cons (first temp_list) result))
>                (setf result
>                      (append (collapse-list (first temp_list))
>                              result)))))
From: ey15
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7g4cj3$3q7$1@news.liv.ac.uk>
In article <······················@pug1.sprocketshop.com>, ·······@pug1.sprocketshop.com 
says...

>particularly concerned with performance.  I would like to see a simple
>and elegant solution. 

I can't say if this one is simple or eligant, but it seams to work...


(defun collapse-list (l)
  (loop with result = (list nil)
        with result-tail = result
        for item in l
        if (atom item)
        do (rplacd result-tail (list item))
           (setq result-tail (cdr result-tail))
        else
        do (rplacd result-tail (collapse-list item))
           (setq result-tail (last result-tail))
        end
        finally return (cdr result)))


(setq l '((nil a nil (((((((((((nil))))))))))) s d nil) q w r (d f (4 r t 6 (h j s l) r k l 
(d g)) sv) s f j c ()))

CL-USER 76 > (collapse-list l)
(NIL A NIL NIL S D NIL Q W R D F 4 R T 6 H J S L R K L D G SV S F J C NIL)

BTW, I came up with this solution after looking at the results of
(pprint (macroexpand '(loop for item in l collect item)))

Marcus.
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfwhfq2gm8j.fsf@world.std.com>
····@liv.ac.uk (ey15) writes:

> I can't say if this one is simple or eligant, but it seams to work...
> 
> (defun collapse-list (l)
>   (loop with result = (list nil)
>         with result-tail = result
>         for item in l
>         if (atom item)
>         do (rplacd result-tail (list item))
>            (setq result-tail (cdr result-tail))
>         else
>         do (rplacd result-tail (collapse-list item))
>            (setq result-tail (last result-tail))
>         end
>         finally return (cdr result)))

(defun collapse-list (list)
  (loop for item in list
        when (atom item)
         collect item
        else
         nconc (collapse-list item)))

does pretty much the same thing and with a good deal more perspicuity.
From: David D. Smith
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <dds-2704991635220001@p070.bit-net.com>
In article <······················@pug1.sprocketshop.com>,
·······@pug1.sprocketshop.com (Kenneth P. Turvey) wrote:

> As part of another project I had need of a function to collapse a
> possibly nested list into an unnested version containing the same atoms.
> After finishing my first hack at it I thought, "There has got to be a
> better way".  I was hoping some of you Lisp experts (I'm mediocre in
> this language, at best) would be able to help me out.  I am not
> particularly concerned with performance.  I would like to see a simple
> and elegant solution. 

...

Here is an iterative form to complement all the elegant recursive
solutions.  It  is pontentially less efficient.

(defun flatten (x)
  (do ((result nil)
       (last nil)
       (this (copy-list x)))
      ((null this) result)
    (if (listp (car this))
      (setq this (append (car this) (cdr this)))
      (setq last (if last
                   (setf (cdr last) this)
                   (setq result this))
            this (cdr this)))))



d
From: Juanma Barranquero
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <37366da1.82045004@news.mad.ttd.net>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

>I am not particularly concerned with performance. I would like
>to see a simple and elegant solution. 

OTOH, I tried to find a good one, performance-wise...

Of the solutions posted 'round here, the fastest (in my ACL 5.0 for
Windows, and with appropriate settings of optimize) was Pitman's:

(defun collapse-list (tree)
  (loop
      for item in tree
      when (atom item)
        collect item
      else
        nconc (collapse-list item)))


Mine, loosely based on Tim Bradshaw's code, is

(defun flatten-tree (tree &key preserve-nil (depth -1))
  (labels ((walk (branch level accum)
	     (dolist (item branch accum)
	       (if (atom item)
		   (when (or item preserve-nil)
		     (push item accum))
		 (if (zerop level)
		     (push (copy-tree item) accum)
		   (setq accum (walk item (1- level) accum)))))))
    (nreverse (walk tree depth '()))))

used as:

> USER(84): (setq *test* '(((a) nil) b (((c) d) (e (f (g nil))) nil (h (i)) nil)))
> (((A) NIL) B (((C) D) (E (F (G NIL))) NIL (H (I)) NIL))
> USER(85): (flatten-tree *test*)
> (A B C D E F G H I)
> USER(86): (flatten-tree *test* :preserve-nil t)
> (A NIL B C D E F G NIL NIL H I NIL)
> USER(87): (flatten-tree *test* :preserve-nil t :depth 1)
> ((A) NIL B ((C) D) (E (F (G NIL))) NIL (H (I)) NIL)
> USER(88): (flatten-tree *test* :preserve-nil nil :depth 1)
> ((A) B ((C) D) (E (F (G NIL))) (H (I)))
> USER(89): (flatten-tree *test* :preserve-nil t :depth 3)
> (A NIL B C D E F (G NIL) NIL H I NIL)
> USER(90): 

which, in my tests (and using ":preserve-nil t" to be able to compare
it), is about 15-20% *slower* than Pitman's, but conses almost 40%
less.

All in all, it's been a lot of fun :)

                                                       /L/e/k/t/u

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.0.2i

iQA/AwUBNyhjTf4C0a0jUw5YEQLTqgCgywtJeJYkZkGomZ5fmAuG8cSoGnUAoJUx
TLlJhJWtPorBW+5REBaae61P
=DvuH
-----END PGP SIGNATURE-----
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfweml3tprt.fsf@world.std.com>
···········@laley-actualidad.es (Juanma Barranquero) writes:

> in my tests (and using ":preserve-nil t" to be able to compare
> it), is about 15-20% *slower* than Pitman's, but conses almost 40%
> less.

Uh, you should talk to Franz about why mine would not do optimal consing.
I don't see any gratuitous consing in the source code.  I see no reason
LOOP shouldn't be able to do a completely optimal job on that part.

And make sure you don't use keyword argument passing when doing any of
this, because that's going to potentially dwarf the time spent doing
the other parts.  I haven't seen how Franz compiles them, and I'm just
speaking generally about the language, but while keyword calls buy
important flexibilty in non-mission-critical interfaces, and some
people (e.g. Paul Graham) are big fans of their use in a great many
situations, they are real potentials for slow code in tight loops and
the decision to use them for code maintenance reasons has to be traded
against the potential difficulty of compiling them efficiently.  Most
compilers I've used could do a lot better than they do in compiling
keyword calls than they do, too, so you're often not even seeing
optimal treatment.  I'm pretty sure CLIM, for example, has massive
numbers of compiler macros to try to get those keyword calls out of
the runtime code because it's such a potential bottleneck.  Compiler
macros were added to CL specifically to help in such cases.
From: Juanma Barranquero
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <372a71f2.60523658@news.mad.ttd.net>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Thu, 29 Apr 1999 15:22:46 GMT, Kent M Pitman <······@world.std.com>
wrote:

>Uh, you should talk to Franz about why mine would not do optimal
>consing. I don't see any gratuitous consing in the source code.  I
>see no reason LOOP shouldn't be able to do a completely optimal job
>on that part.

Well, there's definitely a difference in consing between the two
functions.

I've now tested with:

; my function, simplified to have the same interface as yours
(defun flatten-tree (tree)
  (labels ((walk (branch accum)
	     (dolist (item branch accum)
	       (if (atom item)
		   (push item accum)
		 (setq accum (walk item accum))))))
    (nreverse (walk tree '()))))

; your function
(defun collapse-list (tree)
  (loop
      for item in tree
      when (atom item)
        collect item
      else
        nconc (collapse-list item)))

and the following test data (not very significative, I know):

nil
(nil)
((((((((((((((((((((a))))))))))))))))))))
(a b c d e f g h i j k l m n o p q r s t u v w x y z)
((((((((((a) b) c) d) e) f) g) h) i) j)
(a (b (c (d (e (f (g (h (i (j))))))))))
(((((((((((a)))))))))) ((((((((((b)))))))))))
(a (b (c (d (e (f (g (h (i) j) k) l) m) n) o) p) q)
(a nil (b ((c d (nil) e (f (g) h) nil) (i j) k) l) (((m))) nil)
((j u a n m a) (b a r r a n q u e r o)))

in a 1,000,000 iterations loop. The results I get, with

(optimize (speed 3) (space 1) (safety 0) (debug 0))

are:

USER(30): (time (test-fun1))  ;; flatten-tree
; cpu time (non-gc) 92,738 msec (00:01:32.738) user, 0 msec system
; cpu time (gc)     10,621 msec user, 0 msec system
; cpu time (total)  103,359 msec (00:01:43.359) user, 0 msec system
; real time  103,358 msec (00:01:43.358)
; space allocation:
;  101,001,351 cons cells, 0 symbols, 4,928 other bytes, 0 static
bytes

USER(34): (time (test-fun2))  ;; collapse-list
; cpu time (non-gc) 92,904 msec (00:01:32.904) user, 0 msec system
; cpu time (gc)     19,808 msec user, 0 msec system
; cpu time (total)  112,712 msec (00:01:52.712) user, 0 msec system
; real time  112,712 msec (00:01:52.712)
; space allocation:
;  188,000,000 cons cells, 0 symbols, 5,312 other bytes, 0 static
bytes

so they're about equal in speed but mine consed 54% of what yours did.
I sure don't know why. Maybe Duane Retting is reading us and can offer
any hint?

>And make sure you don't use keyword argument passing when doing any
>of this, because that's going to potentially dwarf the time spent
>doing the other parts.

Thanks for your informative post about keyword arguments. I didn't
know any of that.

                                                       /L/e/k/t/u


-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.0.2i

iQA/AwUBNyl3Jv4C0a0jUw5YEQIPZACglxjTRVDwnSHwAT/4gHJk9MLaI8YAoL5X
Bh0m1l5Mjsm9ocCcuhW0JG4y
=t6Jc
-----END PGP SIGNATURE-----
From: Duane Rettig
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <4ogk5oo9v.fsf@beta.franz.com>
···········@laley-actualidad.es (Juanma Barranquero) writes:

> so they're about equal in speed but mine consed 54% of what yours did.
> I sure don't know why. Maybe Duane Retting is reading us and can offer
> any hint?

Yes, I am reading, but have unfortunately not had much time to answer
anything, let alone do any research on it or other issues.

What Bernhard Pfahringer said about the extra cons in loop is
probably correct, though I haven't researched it.  A macroexpansion
may also shed some light on it.

> >And make sure you don't use keyword argument passing when doing any
> >of this, because that's going to potentially dwarf the time spent
> >doing the other parts.
> 
> Thanks for your informative post about keyword arguments. I didn't
> know any of that.

Kent is right; keywords offer great flexibility at definitely non-trivial
time cost, though not in consing.  Keywords are stored in a table on
the stack, and an out-of-line primitive call is made to sort out the
argument specification and fill in the table.  It is fairly fast, but
definitely not function-entry speed.

If you don't want to back all the way off to required arguments only,
you can still use optionals.  This takes some flexibility away, but
allows the options, and testing for the presence of optionals are
only an instruction or two for each optional.  In fact, for n arguments
of which at least n-k are optionals, if the compiled code decides that
the kth argument is not present, it can go ahead and assign the default
values to the kth through nth arguments.

-- 
Duane Rettig          Franz Inc.            http://www.franz.com/ (www)
1995 University Ave Suite 275  Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253   ·····@Franz.COM (internet)
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfw4slxdddf.fsf@world.std.com>
Duane Rettig <·····@franz.com> writes:

> Kent is right; keywords offer great flexibility at definitely non-trivial
> time cost, though not in consing.  Keywords are stored in a table on
> the stack, and an out-of-line primitive call is made to sort out the
> argument specification and fill in the table.  It is fairly fast, but
> definitely not function-entry speed.

It doesn't have to work this way, btw.  You could arrange for there to
be multiple entry points for a keyword call, relating to how they were
called.  Consider:

 (defun foo (&key x y) ...)

could be compiled as:

 (defun foo (&rest args) ;hopefully rarely called, so ok to be slow
   (destructuring-bind (&key x y) args
     (internal-foo x y)))
 (defun internal-foo (x y) ...)

with additional bookkeeping so that

 This...                    Compiles to...
 (foo :x (f))               (internal-foo!x-* (f))
 (foo :x (f) :x (g))        (internal-foo!x-x (f) (g))
 (foo :x (f) :y (g))        (internal-foo!x-y (f) (g))
 (foo :y (g) :x (f))        (internal-foo!y-x (g) (f))

where you then made sure the appropriate positional stubs were
present at load time, and where all each stub did was shuffle the
args and call the central entry point.  You could punt to the
general purpose entry point if you were exceeding a stub limit or
if apply had been used. 

It would be nice if there was a simple way to request this stuff of
the compiler.  I've ended up writing stuff like this for special
purpose use from time to time, but I lament that most compilers aren't
committed to doing it for me.  Yes, it involves a proliferation of
symbols, but for heavily used interfaces, it's what you need.

It's pretty similar to the way "number calling" used to work (for
functions in Maclisp that were declared to take or return fixnums or
flonums).  The public entry point did not assume special stuff, but
people who had special knowledge of what was going on knew the secret
way to enter the function bypassing the general prolog.

(Really far afield: The trick was in Maclisp that the general purpose
function entry point had a "pushj" to another function as the first
instruction that would unpack the gneral purpose args into number args
and add an additional return frame to the stack so that on the way
out, the number-called internal function would have its args re-packed
into a general purpose call form that the caller expected.  so
number-called functions always blindly entered at the second
instruction, bypassing both the unpacking and the prep for the later
re-packing.  This sometimes led to "fun" cases where people
number-declared functions that weren't number functions and the wrong
thing happened, so you have to be careful.  Once I heard of it
happening deliberately: I remember some bug report from George
Carrette with the subject line "crowbar in head" where he'd finally
tracked down a case of brain damage where someone trying to get past
an error checking instruction ("skipe *rset", in pdp10-ese, if I
recall) by declaring the function a number function.  But the function
code changed and that was no longer the first instruction.  The joys
of cheating.  Life was interesting back then.)

> If you don't want to back all the way off to required arguments only,
> you can still use optionals.  This takes some flexibility away, but
> allows the options, and testing for the presence of optionals are
> only an instruction or two for each optional.  In fact, for n arguments
> of which at least n-k are optionals, if the compiled code decides that
> the kth argument is not present, it can go ahead and assign the default
> values to the kth through nth arguments.

You mean thecompiler works by calling the function with the full
complement of args and skipping (or minimizing) the optional code setup
work?
From: Juanma Barranquero
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <372fc511.30545321@news.mad.ttd.net>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 30 Apr 1999 13:18:36 -0700, Duane Rettig <·····@franz.com> wrote:

>Kent is right; keywords offer great flexibility at definitely
>non-trivial time cost, though not in consing.

Yes, I've now realized that. Thanks.

>If you don't want to back all the way off to required arguments only,
>you can still use optionals.

Finally I've settled to using a variation of Bernhard Pfahringer's
function, with an argument &optional (preserve-nil t). It's
still pretty fast.


                                                       /L/e/k/t/u


-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.0.2i

iQA/AwUBNy23zf4C0a0jUw5YEQJn+wCgtlasi4Et3eN9vQqY9i6olLi6SKIAoKc/
qPKTimjrbmv1uvXxS4ukextw
=eAwC
-----END PGP SIGNATURE-----
From: Bernhard Pfahringer
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7gcaq5$3ork$1@www.univie.ac.at>
In article <·················@news.mad.ttd.net>,
Juanma Barranquero <···········@laley-actualidad.es> wrote:
>
>Well, there's definitely a difference in consing between the two
>functions.
>
>(defun collapse-list (tree)
>  (loop
>      for item in tree
>      when (atom item)
>        collect item
>      else
>        nconc (collapse-list item)))
>

The difference in consing is probably explained by the way (I suppose)
loop COLLECTs values without doing nreverse. It probably destructively
modifies the tail of the result list, which itself is initialized using
one cons-cell to simplify the update code. Consequently, you'd get an
overhead of one additional cons-cell per call. Depending on the details,
the overhead could as well be more than one cell. Looking at the
macro-expanded code might further clarify this issue. But anyway, the
additional consing seems worth (cf. runtimes). There once was this
slogan "Consing is cheap", which I think should be rephrased into
"Consing can be cheap" (given you know what you do and have a well-
implemented generational garbage collector at your disposal).

A problem with all solutions proposed so far is recursion over the
substructures which is not tail-recursive. So the call stack might overflow
for deep enough structures. The following iterative version manages its own 
stack (including tail-recursion optimization). As only each non-last-position
substructure necessitates a stack-push, this version will never cons more than
the original loop-based one.

(defun collapse-list (list)
  (loop with stack = nil
	for item = (cond (list (pop list))
			 (stack (setq list (pop stack))
				(pop list))
			 (t (loop-finish)))
	if (atom item)
	 collect item
	else
	 do (when list
               (push list stack))
            (setf list item)))

Bernhard
-- 
--------------------------------------------------------------------------
Bernhard Pfahringer
Austrian Research Institute for  http://www.ai.univie.ac.at/~bernhard/
Artificial Intelligence          ········@ai.univie.ac.at 
From: Juanma Barranquero
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <372bb980.78839915@news.mad.ttd.net>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 30 Apr 1999 13:22:13 GMT, ········@hummel.ai.univie.ac.at (Bernhard
Pfahringer) wrote:

>But anyway, the additional consing seems worth (cf. runtimes).

Not in my example, as both routines were approx. equal in speed.

>A problem with all solutions proposed so far is recursion over the
>substructures which is not tail-recursive. So the call stack might
>overflow for deep enough structures.

Yes, you're right. I tried an iterative version, but it wasn't half as
clever as yours (nor half as obscure, OTOH ;)

>The following iterative version manages its own stack (including
>tail-recursion optimization). As only each non-last-position
>substructure necessitates a stack-push, this version will never cons
>more than the original loop-based one.

It stills conses (in my Allegro) about 36% more than my best recursive
version, but is also 44% faster, and as you say it doesn't have to
worry about stack depth. Pretty impressive. Thanks.

                                                       /L/e/k/t/u

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.0.2i

iQA/AwUBNym0of4C0a0jUw5YEQJZPgCdG8XfZCB2M8adHE4sv1wn9dFhw1EAoObT
UrZR6WgQFRHip8eUPKoArsk6
=zEDG
-----END PGP SIGNATURE-----
From: Bernhard Pfahringer
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7gd4js$els$1@www.univie.ac.at>
In article <·················@news.mad.ttd.net>,
Juanma Barranquero <···········@laley-actualidad.es> wrote:
>
>It stills conses (in my Allegro) about 36% more than my best recursive
>version, but is also 44% faster, and as you say it doesn't have to
>worry about stack depth. Pretty impressive. Thanks.
>

Hi again,

if you thought the previous iterative solution was obscure, 
the following will be worse :-)
It, too, is iterative and it does NOT cons a single cell more
than necessary. Enjoy:


(defun collapse-list-iteratively (tree)
  (when (consp tree)
    ;;; just make sure TREE is really a list
    (loop with result = (if (rest tree)
			    (list (car tree) (rest tree))
			    (list (car tree)))
	  with point = result
	  for value = (first point)
	  while point
	  do
	  (cond ((consp value)
	         ;;; lift sub-structure by moving up its "first" part
		 (setf (first point) (first value))
		 ;;; and, if present, create a place-holder for its "rest" part 
		 (when (rest value)
		   (setf (rest point) (cons (rest value) (rest point)))))
		(t
	         ;;; first value is atomic, simply advance pointer
		 (setq point (rest point))))
	  finally
	  (return result))))


Bernhard
-- 
--------------------------------------------------------------------------
Bernhard Pfahringer
Austrian Research Institute for  http://www.ai.univie.ac.at/~bernhard/
Artificial Intelligence          ········@ai.univie.ac.at 
From: Juanma Barranquero
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <373815ea.182299582@news.mad.ttd.net>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 30 Apr 1999 20:42:36 GMT, ········@hummel.ai.univie.ac.at (Bernhard
Pfahringer) wrote:

>if you thought the previous iterative solution was obscure, 
>the following will be worse :-)

Oh, well... :)

But, seriously, the only "complain" I have is that I prefer to use

(if (atom tree)
    nil
  ...else part...)

instead of (when (consp tree) ...)

because the function is returning a (valid) value in both cases.

>It, too, is iterative and it does NOT cons a single cell more
>than necessary. Enjoy:

Your new version works like a charm, just so *very* slightly slower
than the previous one and consing a great deal less. Have you more
tricks up your sleeve? :)

                                                       /L/e/k/t/u

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.0.2i

iQA/AwUBNzAODv4C0a0jUw5YEQKMYwCfeT6GEDkCK+4mpna0Z2bp7P+QargAnRYJ
5v+qfHAVp/bZ8hmIIpuav428
=Sb7m
-----END PGP SIGNATURE-----
From: Bernhard Pfahringer
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <7gpeej$r1c$1@www.univie.ac.at>
In article <··················@news.mad.ttd.net>,
Juanma Barranquero <···········@laley-actualidad.es> wrote:
>
>But, seriously, the only "complain" I have is that I prefer to use
>
>(if (atom tree)
>    nil
>  ...else part...)
>
>instead of (when (consp tree) ...)
>
>because the function is returning a (valid) value in both cases.
>

Well I think this is mostly a stylistic question, so you are free
to choose whatever suits you best. But the return value is clearly
defined for WHEN as well. Citing from the Hyperspec:

 In a when form, if the test-form yields true, the forms are evaluated
 in order from left to right and the values returned by the forms are
 returned from the when form. Otherwise, if the test-form yields false,
 the forms are not evaluated, and the when form returns nil. 
                                  ^^^^^^^^^^^^^^^^^^^^^^^^^^

BTW, I had the same suspicious feeling about WHEN until I looked it up
in the Hyperspec.
                                       
>
>Your new version works like a charm, just so *very* slightly slower
>than the previous one and consing a great deal less. Have you more
>tricks up your sleeve? :)
>

Sure, but not in this particular case. Besides, some tricks might
necessitate a consultancy fee :-)

cheers, Bernhard

PS: Version 3.0 of the HyperSpec has a serious bug on the very same
page describing UNLESS. Can you spot it:

 In an unless form, if the test-form yields false, the forms are evaluated
 in order from left to right and the values returned by the forms are
 returned from the unless form. Otherwise, if the test-form yields false,
 the forms are not evaluated, and the unless form returns nil.

Is this bug present in the hardcopy as well (can't check, don't own it)?
-- 
--------------------------------------------------------------------------
Bernhard Pfahringer
Austrian Research Institute for  http://www.ai.univie.ac.at/~bernhard/
Artificial Intelligence          ········@ai.univie.ac.at 
From: Nick Levine
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <37303EAC.B5DD7A09@harlequin.co.uk>
Bernhard Pfahringer wrote:

> PS: Version 3.0 of the HyperSpec has a serious bug on the very same
> page describing UNLESS. Can you spot it:
>
>  In an unless form, if the test-form yields false, the forms are evaluated
>  in order from left to right and the values returned by the forms are
>  returned from the unless form. Otherwise, if the test-form yields false,
>  the forms are not evaluated, and the unless form returns nil.
>

That would be a "bug" in the ANSI spec, not in CLHS. See Kent's posting on the
subject.

- n
From: Juanma Barranquero
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <373e42b6.193767813@news.mad.ttd.net>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 5 May 1999 12:44:03 GMT, ········@hummel.ai.univie.ac.at (Bernhard
Pfahringer) wrote:

>Well I think this is mostly a stylistic question, so you are free
>to choose whatever suits you best. But the return value is clearly
>defined for WHEN as well.

Yes, I know WHEN is defined in both cases. It's just a personal taste;
I like using WHEN and UNLESS for side-effect forms and IF for
value-returning tests.

>Sure, but not in this particular case. Besides, some tricks might
>necessitate a consultancy fee :-)

I'm referring to this case; your take on it has been *very*
interesting :)

>PS: Version 3.0 of the HyperSpec has a serious bug on the very same
>page describing UNLESS. Can you spot it:
>
> In an unless form, if the test-form yields false, the forms are
> evaluated in order from left to right and the values returned by
> the forms are returned from the unless form. Otherwise, if the
> test-form yields false, the forms are not evaluated, and the unless
> form returns nil.

The pair "if the test-form yields false / Otherwise, if the test-form
yields false".

Both in WHEN and UNLESS, shouldn't it be "the values returned by the
last form are returned from the (when|unless) form" instead of the
values "returned by the forms"?

                                                       /L/e/k/t/u



-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.0.2i

iQA/AwUBNzA2Ff4C0a0jUw5YEQKNtQCgi07GtZGw6dP57/4R4+BuOkKm8IEAoL6A
kIoPOvdavyScibUlY+5fJ6hZ
=nxgY
-----END PGP SIGNATURE-----
From: Stig Hemmer
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <ekv1zgv8nm1.fsf@gnoll.pvv.ntnu.no>
···········@laley-actualidad.es (Juanma Barranquero) writes:
> Both in WHEN and UNLESS, shouldn't it be "the values returned by the
> last form are returned from the (when|unless) form" instead of the
> values "returned by the forms"?

Earlier the forms are described as an implict progn, with a link to
the following glossary entry:

: implicit progn n. an ordered set of adjacent forms appearing in
: another form, and defined by their context in that form to be
: executed as if within a progn.

"as if within a progn", which means that the last forms return value
is used.

The examples also bear this out.

Stig Hemmer,
Jack of a Few Trades.
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfwk8unnqvp.fsf@world.std.com>
Stig Hemmer <····@pvv.ntnu.no> writes:


> ···········@laley-actualidad.es (Juanma Barranquero) writes:
> > Both in WHEN and UNLESS, shouldn't it be "the values returned by the
> > last form are returned from the (when|unless) form" instead of the
> > values "returned by the forms"?
> 
> Earlier the forms are described as an implict progn, with a link to
> the following glossary entry:
> 
> : implicit progn n. an ordered set of adjacent forms appearing in
> : another form, and defined by their context in that form to be
> : executed as if within a progn.
> 
> "as if within a progn", which means that the last forms return value
> is used.
> 
> The examples also bear this out.

This came up too often to leave to chance.  I made short terminology and
a definition to match.  The better reference is 1c in "values":

value n. 1. a. one of possibly several objects that are the result of
an evaluation. b. (in a situation where exactly one value is expected
from the evaluation of a form) the primary value returned by the
form. c. (of forms in an implicit progn) one of possibly several
objects that result from the evaluation of the last form, or nil if
there are no forms. 2. an object associated with a name in a
binding. 3. (of a symbol) the value of the dynamic variable named by
that symbol. 4. an object associated with a key in an association
list, a property list, or a hash table.
From: Juanma Barranquero
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <37354852.260730690@news.mad.ttd.net>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 05 May 1999 18:53:10 +0200, Stig Hemmer <····@pvv.ntnu.no> wrote:

>"as if within a progn", which means that the last forms return value
>is used.

Yes, I know that. I'm just saying I find the way it is written to be
slightly confusing, specially for total newbies.

                                                       /L/e/k/t/u

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.0.2i

iQA/AwUBNzE6hv4C0a0jUw5YEQIbKACfSzE8/ZmA60y36OlTibPKRbPVNXEAnjYW
Crkbfasw+wZ/cSqM/MWcOcRg
=msFx
-----END PGP SIGNATURE-----
From: Stig Hemmer
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <ekvr9ou9syo.fsf@ra.pvv.ntnu.no>
···········@laley-actualidad.es (Juanma Barranquero) writes:
> Yes, I know that. I'm just saying I find the way it is written to be
> slightly confusing, specially for total newbies.

Indeed it is.  If the ANSI standard were written in a way that was not
confusing to total newbies it would be at least four times as long.
At least.

It is a dense document, with a lot of meaning put into few words.

The Hyperspec, with its cross references, makes this managable for a
semi-newbie like myself.  But you need to _use_ those crossreferences.
And you need to think.

By using the phrase 'implicit progn', the standard underlines the
similarities between WHEN and all the other constructs that have
implict progns.  If it had instead been spelled it out in each and
every instance, this similarity would have been lost.

For example: Kent Pitmans reply to my previous article stated the
value returned by an implicit progn with no forms in it was NIL.

From this I know that (WHEN T) and (FUNCALL (LAMBDA ())) both return
NIL, as will any similar form using implicit progns.  If I hadn't had
the 'implicit progn' concept to hang this information on, I would have
had to learn this from scratch for each and every form.

The net result would have been that the 'newbie-friendly' document
would have been less 'expert-friendly'.  This is a common trade-off,
and you shouldn't be surpriced a standard document is on the
expert-friendly end of the scale.

Stig Hemmer,
Jack of a Few Trades.
From: Juanma Barranquero
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <3734b282.17936521@news.mad.ttd.net>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 06 May 1999 16:24:31 +0200, Stig Hemmer <····@pvv.ntnu.no> wrote:

>Indeed it is.  If the ANSI standard were written in a way that was
>not confusing to total newbies it would be at least four times as
>long. At least.
>
>It is a dense document, with a lot of meaning put into few words.

You're right, of course. And I didn't meant to suggest that it was
badly (or carelessly) written.

>The Hyperspec, with its cross references, makes this managable for a
>semi-newbie like myself.

Or myself.

>But you need to _use_ those crossreferences. And you need to think.

Yes, I do that (or so I'd like to believe :)

>From this I know that (WHEN T) and (FUNCALL (LAMBDA ())) both return
>NIL, as will any similar form using implicit progns.  If I hadn't had
>the 'implicit progn' concept to hang this information on, I would
>have had to learn this from scratch for each and every form.

Of course. But I'm not discussing that. If I'm learning CL and I read
that the body of WHEN is an "implicit progn", after checking that in
the glossary I *know* that WHEN returns NIL if there aren't any form
(or if they aren't executed). Then I read that the results of WHEN are
"the values of the forms" etc. and I start to wonder if they're
talking about multiple values, or the collected values of all the
forms executed, or what. Then I go back and check, and I see that
"forms" is a placeholder for the function argument, and that is
defined as "an implicit progn", so yes, eventually I'll conclude that,
since it is an implicit progn, only the last form supplies value(s).
Correct, but not very direct. 

>The net result would have been that the 'newbie-friendly' document
>would have been less 'expert-friendly'.  This is a common trade-off,
>and you shouldn't be surpriced a standard document is on the
>expert-friendly end of the scale.

I've read my deal of standards and know what trade-offs are accepted,
so I'm not surprised. But you're right again.

And no, I'm not suggesting standards should be written as "gentle
introductions" to the matter at hand.

                                                       /L/e/k/t/u



-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.0.2i

iQA/AwUBNzGqDf4C0a0jUw5YEQLX+ACgjnx9u1Ja/XTrIJd2tEZkYEnAUfkAnjIk
UdfAiN8Y1Toz55mAk33xOWSV
=dJNP
-----END PGP SIGNATURE-----
From: Kent M Pitman
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <sfw676641ft.fsf@world.std.com>
···········@laley-actualidad.es (Juanma Barranquero) writes:

> Of course. But I'm not discussing that. If I'm learning CL 

Explicitly not a goal of the standard.  We're happy it supports this
activity as well as it does, but it wasn't the goal of the writing.
There is no substitute for good tutorial text.  Fortunately, such are
available and hopefully more on the way.

> and I read
> that the body of WHEN is an "implicit progn", after checking that in
> the glossary I *know* that WHEN returns NIL if there aren't any form
> (or if they aren't executed). Then I read that the results of WHEN are
> "the values of the forms" etc. and I start to wonder if they're
> talking about multiple values, or the collected values of all the
> forms executed, or what. Then I go back and check, and I see that
> "forms" is a placeholder for the function argument, and that is
> defined as "an implicit progn", so yes, eventually I'll conclude that,
> since it is an implicit progn, only the last form supplies value(s).
> Correct, but not very direct. 

If you thought NIL would be returned if there weren't any forms and you
thought all the forms might contribute values, you had a conflicting
thought.  The only possible consistent reading if you thought forms
were contributing values would be that (progn) returns what (values)
does,  not what (values NIL) does.  But also, expressing this in terms
of the last form was painful because there is not always a form.  It
would have to have said "the value of the last of the forms or NIL if
there are no forms".  This comes up enough that it was bad modularity
to keep repeating since it might be wrong someplace.
From: Juanma Barranquero
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <37369f84.78603175@news.mad.ttd.net>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Thu, 6 May 1999 16:17:58 GMT, Kent M Pitman <······@world.std.com>
wrote:

>It would have to have said "the value of the last of the forms or
>NIL if there are no forms".  This comes up enough that it was bad
>modularity to keep repeating since it might be wrong someplace.

OK, I see the reason now. Thanks.

                                                       /L/e/k/t/u

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.0.2i

iQA/AwUBNzKRqv4C0a0jUw5YEQLz1ACfUAJim7DYKG9/VbGFCwKJ9KNYOt0AoNr8
LWPfm6IfHsfs9Wg4joNEowTM
=ropO
-----END PGP SIGNATURE-----
From: Juanma Barranquero
Subject: Re: There has got to be a better way...
Date: 
Message-ID: <373cf823.109147816@news.mad.ttd.net>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sat, 01 May 1999 02:40:41 -0400, ···@flavors.com (David D. Smith)
wrote:

>Your examples have 101 atoms but the 87 calls to COLLAPSE-LIST
>each cons a "collection header".

Very interesting. Thanks.

                                                           Juanma

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.0.2i

iQA/AwUBNy7qMf4C0a0jUw5YEQJYrACgyP2VaDNOjNG+/RgOBCRiQ8PHo2oAn3Vd
rizeknr9pJUIqHlpxPcBn+ky
=QCB5
-----END PGP SIGNATURE-----