From: Peter Seibel
Subject: Sequences other than list and vector
Date: 
Message-ID: <m3oev073ux.fsf@javamonkey.com>
The standard specically points out the LIST and VECTOR types are not
necessarily an exhaustive partition of SEQUENCE. Are there any
implementations that provide for other kind of sequences?

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp

From: Kent M Pitman
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <sfw1xrws4uc.fsf@shell01.TheWorld.com>
Peter Seibel <·····@javamonkey.com> writes:

> The standard specically points out the LIST and VECTOR types are not
> necessarily an exhaustive partition of SEQUENCE. Are there any
> implementations that provide for other kind of sequences?

Probably not.

But Maclisp had HUNKs, which were a kind of n-ary cons (specifically,
they had allocated sizes 2,4,8,16,32,64,128,256,512 (to address the
"bin packing problem") but they could have specially marked unfilled
elements (so a size 3 hunk was really a hunk4 with one element marked
unused).  CAR and CDR worked on any hunk, accessing the 1st and 0th
elements of the hunk, respectively.  (You needed CXR to get to the
other elements.)  But they could be linked together like car/cdr
chains with the 2nd to nth elements being somewhat invisible pieces of
extra state, so that you could make backwards lists, or conses with
property lists, or other kinds of things like that.  Maclisp was kind
of an implementation toolbox for making new languages, so it was also
possible to globally put it in a mode where hunks did something
completely different and did not behave like conses but instead
responded to a kind of message-passing that allowed for
experimentation with object-systems...  (This made it problematic to
load all possible libraries for Maclisp, since some required the
master switch set one way and some another, but then again, Maclisp
had a maximum fixed address space of 18bits, allowing only 256K 36-bit
words (about 1.25MB), so having everything pre-loaded was not the
usual thing one wanted anyway.)

The Lisp Machine also has a type of array that is a subtype of vector,
so is maybe not relevant in the issue of exhausitive partition but is
a kind of array that can also be a list (art-q-list arrays, I think?).
Using a function g-l-p (get list pointer) on the array, you can get a
pointer to the vector as a cdr-coded list so you can cdr down it.
This exploits cdr-codes heavily, of course, which are not part of CL.

But I assume that provision in the language is simply an attempt to
leave room for future needs, whether it be an implementation that
needs to make multi-d arrays or hash tables or b-trees be walkable
linearly, or whether it's a differently chunked chain similar to
hunks, but perhaps chained on n>2 elements per chunk (like cdr-coded
lists, only user-visible).  The space of such data structures is
richly available in the literature on algorithms, so it probably
seemed imprudent to say that CL forbid extensions in this area, which
was already well-known.

On the other hand, absent extension protocols for sequences such as
those provided by Dylan (and which could be added by implementations
of CL voluntarily as an addition), I don't see how to make the
introduction efficient.  In order for a portable program to use such
new types without knowing of them, it would have to use LENGTH and ELT
to iterate across them, there being no DOSEQ, and that wouldn't be
adequately efficient.
From: Erann Gat
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <gNOSPAMat-2511031115120001@k-137-79-50-101.jpl.nasa.gov>
In article <···············@shell01.TheWorld.com>, Kent M Pitman
<······@nhplace.com> wrote:

> In order for a portable program to use such
> new types without knowing of them, it would have to use LENGTH and ELT
> to iterate across them, there being no DOSEQ, and that wouldn't be
> adequately efficient.

What about MAP and MAP-INTO?

E.
From: Kent M Pitman
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <sfwfzgbnc5o.fsf@shell01.TheWorld.com>
·········@jpl.nasa.gov (Erann Gat) writes:

> In article <···············@shell01.TheWorld.com>, Kent M Pitman
> <······@nhplace.com> wrote:
> 
> > In order for a portable program to use such
> > new types without knowing of them, it would have to use LENGTH and ELT
> > to iterate across them, there being no DOSEQ, and that wouldn't be
> > adequately efficient.
> 
> What about MAP and MAP-INTO?

Heh.  I had the oddest feeling I was forgetting something when I sent
off that post, but I knew someone would come to the aid of my failing
brain if I just went ahead and posted it.  I had, indeed, momentarily
forgotten those two operators.  They're somewhat heavyweight ways
to go about it but they do accomplish the purpose...
From: Thomas F. Burdick
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <xcvk75op87a.fsf@famine.OCF.Berkeley.EDU>
(Very interesting post, btw)

Kent M Pitman <······@nhplace.com> writes:

> On the other hand, absent extension protocols for sequences such as
> those provided by Dylan (and which could be added by implementations
> of CL voluntarily as an addition), I don't see how to make the
> introduction efficient.  In order for a portable program to use such
> new types without knowing of them, it would have to use LENGTH and ELT
> to iterate across them, there being no DOSEQ, and that wouldn't be
> adequately efficient.

True, but we do have MAP.  From my own toolbox:

  (defmacro dosequence ((var sequence &optional result) &body forms)
    `(block nil
       (map nil (lambda (,var) ,@forms) ,sequence)
       ,@(when result (list `(let ((,var nil)) ,result)))))


-- 
           /|_     .-----------------------.                        
         ,'  .\  / | No to Imperialist war |                        
     ,--'    _,'   | Wage class war!       |                        
    /       /      `-----------------------'                        
   (   -.  |                               
   |     ) |                               
  (`-.  '--.)                              
   `. )----'                               
From: Steven E. Harris
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <q6765h8w1jx.fsf@raytheon.com>
···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:

>   (defmacro dosequence ((var sequence &optional result) &body forms)
>     `(block nil
>        (map nil (lambda (,var) ,@forms) ,sequence)
>        ,@(when result (list `(let ((,var nil)) ,result)))))

Why does var have to be set to nil before evaluating the result form?

-- 
Steven E. Harris        :: ········@raytheon.com
Raytheon                :: http://www.raytheon.com
From: Kent M Pitman
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <sfwbrqznbtx.fsf@shell01.TheWorld.com>
"Steven E. Harris" <········@raytheon.com> writes:

> ···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> 
> >   (defmacro dosequence ((var sequence &optional result) &body forms)
> >     `(block nil
> >        (map nil (lambda (,var) ,@forms) ,sequence)
> >        ,@(when result (list `(let ((,var nil)) ,result)))))
> 
> Why does var have to be set to nil before evaluating the result form?

What would you set it to?  The form is to evaluate in the scope of var,
if you're going to make it symmetric with, for example, DOLIST. From
CLHS's DOLIST dictionary entry:

  The scope of the binding of var does not include the list-form, 
  but the result-form is included. 

and the only other really obvious choice of a value is:

  (defmacro dosequence ((var sequence &optional result) &body forms)
    (let ((temp (gensym)))
      `(block nil
          (let ((,var nil))
            (map nil #'(lambda (,temp)
                         (setq ,var ,temp)
                         ,@forms)
                     ,sequence)
            ,@(when result `(,result))))))

I'm not sure I really like this better, since (ignoring even the issue of
the presence of the SETQ) var is then bound to something relatively random.
Making it a boring value like NIL discourages the use of it for any purpose,
(since NIL already has a name if it's needed), and that's all to the good.
From: Thomas F. Burdick
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <xcvznejo80n.fsf@famine.OCF.Berkeley.EDU>
Kent M Pitman <······@nhplace.com> writes:

> "Steven E. Harris" <········@raytheon.com> writes:
> 
> > ···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> > 
> > >   (defmacro dosequence ((var sequence &optional result) &body forms)
> > >     `(block nil
> > >        (map nil (lambda (,var) ,@forms) ,sequence)
> > >        ,@(when result (list `(let ((,var nil)) ,result)))))
> > 
> > Why does var have to be set to nil before evaluating the result form?
> 
> What would you set it to?  The form is to evaluate in the scope of var,
> if you're going to make it symmetric with, for example, DOLIST. From
> CLHS's DOLIST dictionary entry:
> 
>   The scope of the binding of var does not include the list-form, 
>   but the result-form is included. 

For any newbies looking on (y'all the reason I posted the code in the
first place, since I *know* that Kent knows how to write DOSEQUENCE),
this is a glaring exception in my personal toolbox.  Normally, my
DO... macros don't have a result argument.  It makes them a little
more obnoxious to write, and makes them much more difficult to read --
I tend to miss the result argument when looking at a DO... form,
especially if it has a more complicated syntax, like, eg,
DO-SPLITTING-VECTOR:

  http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&safe=off&threadm=xcvvghhpw95.fsf%40conquest.OCF.Berkeley.EDU&rnum=1&prev=/groups%3Fselm%3Dxcvvghhpw95.fsf%2540conquest.OCF.Berkeley.EDU

[it's called DO-VECTOR-SPLIT in the above message]

With a syntax like:

  DO-VECTOR-SPLIT (start-var end-var (vector splitter) &key start end test)

There's not really any room for a result argument.  I guess it could
be another keyword arg, but if you're debuggin and just trying to look
backwards through some forms to see where the result came from, that
sucks:

  (let ((list ()))
    (do-vector-split (start end (some-vector #\X)
                            :start (1+ pos) :test #'char-equal
                            :result list)
      ... (push foo list) ...))

Yuck.  I'd much rather see:

  (let ((list ()))
    (do-vector-split (start end (some-vector #\X)
                            :start (1+ pos) :test #'char-equal)
      ... (push foo list) ...)
    list)

-- 
           /|_     .-----------------------.                        
         ,'  .\  / | No to Imperialist war |                        
     ,--'    _,'   | Wage class war!       |                        
    /       /      `-----------------------'                        
   (   -.  |                               
   |     ) |                               
  (`-.  '--.)                              
   `. )----'                               
From: Steven E. Harris
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <q67znejj5d4.fsf@raytheon.com>
Kent M Pitman <······@nhplace.com> writes:

> What would you set it to?

Uh, I wouldn't set it to anything, per my argument that follows.

> The form is to evaluate in the scope of var, if you're going to make
> it symmetric with, for example, DOLIST. From CLHS's DOLIST
> dictionary entry:
>
>   The scope of the binding of var does not include the list-form, 
>   but the result-form is included. 

I just read the HyperSpec DOLIST entry and I don't understand the
sentence quoted above. Does it mean that var is visible during the
evaluation of the result-form, but not during evaluation of the
list-form?

But earlier in the same DOLIST entry, we find

,----[ DOLIST Description ]
| At the time result-form is processed, var is bound to nil.
`----

But why go to this length to ensure that var is visible to the
result-form, and then promise that var will be nil? That means that
var will never be of any use to the result-form.

Wouldn't it be easier to just say something like, "It is
implementation-dependent whether var is visible to the result-form,
and if so the value of var is implementation-dependent?" The wording
isn't great, but meant to be equivalent to "undefined" in C++ standard
terms: the variable may contain garbage, so don't try to use its
value.

I've never used the result-form in DOLIST, so maybe I'm missing some
essential dependency between var and the result-form.

-- 
Steven E. Harris        :: ········@raytheon.com
Raytheon                :: http://www.raytheon.com
From: Kent M Pitman
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <sfwisl6vpvk.fsf@shell01.TheWorld.com>
"Steven E. Harris" <········@raytheon.com> writes:

> Kent M Pitman <······@nhplace.com> writes:
> 
> > What would you set it to?
> 
> Uh, I wouldn't set it to anything, per my argument that follows.
> 
> > The form is to evaluate in the scope of var, if you're going to make
> > it symmetric with, for example, DOLIST. From CLHS's DOLIST
> > dictionary entry:
> >
> >   The scope of the binding of var does not include the list-form, 
> >   but the result-form is included. 
> 
> I just read the HyperSpec DOLIST entry and I don't understand the
> sentence quoted above. Does it mean that var is visible during the
> evaluation of the result-form, but not during evaluation of the
> list-form?

Yes, it means that it's like

 (LET ((#1=#:LIST-VAR list-form))
   (LET (VAR)
     (LOOP ; null block + iteration
       (WHEN (NULL #1#) 
         (RETURN result-form)) ; in re-used VAR scope, but not in tagbody
       (SETQ VAR (POP #1#))
       (TAGBODY . body)))) ;explicit tagbody

or

 (LET ((#1=#:LIST-VAR list-form))
   (PROG (VAR)  ; tagbody + null block
     #2=#:TOP
     (WHEN (NULL #1#)
       (RETURN result-form)) ; in re-used VAR scope, in tagbody
     (SETQ VAR (POP #1#))
     ...body...
     (GO #2#))) ; explicit iteration

depending on how you read the part about the tagbody, and whether it
spans the result-form, though I've posted separate email saying why
I prefer the first of these expansions.  Note that there is enough
implementation leeway to also do:

 (LET ((#1=#:LIST-VAR list-form))
   (LOOP ; null block + iteration
     (LET (VAR)
       (WHEN (NULL #1#)
         (RETURN result-form)) ; in new VAR scope each time, not in tagbody
       (SETQ VAR (POP #1#))
       (TAGBODY . body)))) ; explicit tagbody

which differs from the first form above only in what happens when you
collect closures over the var since you get a new binding each time.
But, in particular, you are forbidden by the sentence you ask about
from doing:

 (LET ((#1=#:LIST-VAR list-form))
   (LOOP ; null block + iteration
     (WHEN (NULL #1#)
       (RETURN result-form)) ; not in tagbody nor any VAR scope
     (LET ((VAR (POP #1#)))
       (TAGBODY . body)))) ; explicit tagbody

which is the point of your question.

> But earlier in the same DOLIST entry, we find
> 
> ,----[ DOLIST Description ]
> | At the time result-form is processed, var is bound to nil.
> `----
> 
> But why go to this length to ensure that var is visible to the
> result-form, and then promise that var will be nil? That means that
> var will never be of any use to the result-form.

Right.  Exactly.  Because some people would otherwise want it bound,
for example, to the last element seen or something like that.  It
would also require us to say what it is when there is no iteration
(null list to traverse).  And that would tie the hands of the
implementation in getting the most efficient expansion.  If you want
to hold onto the last element, you can easily do that.
 
> Wouldn't it be easier to just say something like, "It is
> implementation-dependent whether var is visible to the result-form,
> and if so the value of var is implementation-dependent?"

NO!  That is NEVER a good thing.  You always want to know what variable
you are referring to.  This would be the source of endless porting bugs
even more subtle than the kinds of things you're already worried about.

> The wording
> isn't great, but meant to be equivalent to "undefined" in C++ standard
> terms: the variable may contain garbage, so don't try to use its
> value.

But if you side-effect it, the question is whether you are side-effecting
someone else's data. Consider:

 (let ((foo (something-else)))
   (dolist (foo bar (if foo (rplacd foo 'zing))) ...)
   ...)

You don't even know whether the thing you're rplacd'ing is one of the things
in bar or something else.

> I've never used the result-form in DOLIST, so maybe I'm missing some
> essential dependency between var and the result-form.

I don't use it either.  But that's not the point.  The point is to make the
language be at least slightly well-formed.  Not saying what's in a variable
is not as bad as not saying what cell the variable name refers to.  Those
are two utterly different kinds of ambiguity.
From: james anderson
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <3FC50BF2.C27CABE6@setf.de>
"Steven E. Harris" wrote:
> 
> Kent M Pitman <······@nhplace.com> writes:
> 
> > What would you set it to?
> 
> Uh, I wouldn't set it to anything, per my argument that follows.
> 
> > The form is to evaluate in the scope of var, if you're going to make
> > it symmetric with, for example, DOLIST. From CLHS's DOLIST
> > dictionary entry:
> >
> >   The scope of the binding of var does not include the list-form,
> >   but the result-form is included.
> 
> I just read the HyperSpec DOLIST entry and I don't understand the
> sentence quoted above. Does it mean that var is visible during the
> evaluation of the result-form, but not during evaluation of the
> list-form?
> 
> But earlier in the same DOLIST entry, we find
> 
> ,----[ DOLIST Description ]
> | At the time result-form is processed, var is bound to nil.
> `----
> 
> But why go to this length to ensure that var is visible to the
> result-form, and then promise that var will be nil? That means that
> var will never be of any use to the result-form.

the result form could set it to something else.
> 
> Wouldn't it be easier to just say something like, "It is
> implementation-dependent whether var is visible to the result-form,
> and if so the value of var is implementation-dependent?" The wording
> isn't great, but meant to be equivalent to "undefined" in C++ standard
> terms: the variable may contain garbage, so don't try to use its
> value.

where would that leave anything which closed over it?

...
From: Steven E. Harris
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <q67n0aikhc2.fsf@raytheon.com>
james anderson <··············@setf.de> writes:

> the result form could set it to something else.

Can you give an example?

> where would that leave anything which closed over it?

Again, I'd like to see a motivating example. I'm not claiming to be
right, just uninformed.

-- 
Steven E. Harris        :: ········@raytheon.com
Raytheon                :: http://www.raytheon.com
From: Björn Lindberg
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <hcsekvups32.fsf@fnatte.nada.kth.se>
james anderson <··············@setf.de> writes:

> > ,----[ DOLIST Description ]
> > | At the time result-form is processed, var is bound to nil.
> > `----
> > 
> > But why go to this length to ensure that var is visible to the
> > result-form, and then promise that var will be nil? That means that
> > var will never be of any use to the result-form.
> 
> the result form could set it to something else.

But since that variable goes out of scope upon leaving the DOLIST
form, that is not very useful, right?


Bj�rn
From: james anderson
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <3FC5BC6D.F08A3EB@setf.de>
Bj�rn Lindberg wrote:
> 
> james anderson <··············@setf.de> writes:
> 
> > > ,----[ DOLIST Description ]
> > > | At the time result-form is processed, var is bound to nil.
> > > `----
> > >
> > > But why go to this length to ensure that var is visible to the
> > > result-form, and then promise that var will be nil? That means that
> > > var will never be of any use to the result-form.
> >
> > the result form could set it to something else.
> 
> But since that variable goes out of scope upon leaving the DOLIST
> form, that is not very useful, right?

without in any way qualifying the utility, one must allow that something could
have closed, or could close, over the binding. that the presense of a result
form would cause the bound value to be undefined makes no sense.

> 
> Bj�rn
From: Björn Lindberg
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <hcsk75mqeiu.fsf@knatte.nada.kth.se>
james anderson <··············@setf.de> writes:

> Bj�rn Lindberg wrote:
> > 
> > james anderson <··············@setf.de> writes:
> > 
> > > > ,----[ DOLIST Description ]
> > > > | At the time result-form is processed, var is bound to nil.
> > > > `----
> > > >
> > > > But why go to this length to ensure that var is visible to the
> > > > result-form, and then promise that var will be nil? That means that
> > > > var will never be of any use to the result-form.
> > >
> > > the result form could set it to something else.
> > 
> > But since that variable goes out of scope upon leaving the DOLIST
> > form, that is not very useful, right?
> 
> without in any way qualifying the utility, one must allow that
> something could have closed, or could close, over the binding.

Could you give an example of this? I can't really see how that would
happen.

> that
> the presense of a result form would cause the bound value to be
> undefined makes no sense.

I certainly agree with this. I am just trying to understand how the
nil bound variable introduced by the dolist form could be of any use
whatsoever in the result form.


Bj�rn
From: james anderson
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <3FC5F8B4.455A2BEE@setf.de>
if you look back at pitman's posts, "the binding", as the spec terms it, may
not have been "introduced" by the result clause, but may well be the same
binding as was apparent in the body.

Bj�rn Lindberg wrote:
> 
> james anderson <··············@setf.de> writes:
> 
> > Bj�rn Lindberg wrote:
> > >
> > > james anderson <··············@setf.de> writes:
> > >
> > > > > ,----[ DOLIST Description ]
> > > > > | At the time result-form is processed, var is bound to nil.
> > > > > `----
> > > > >
> > > > > But why go to this length to ensure that var is visible to the
> > > > > result-form, and then promise that var will be nil? That means that
> > > > > var will never be of any use to the result-form.
> > > >
> > > > the result form could set it to something else.
> > >
> > > But since that variable goes out of scope upon leaving the DOLIST
> > > form, that is not very useful, right?
> >
> > without in any way qualifying the utility, one must allow that
> > something could have closed, or could close, over the binding.
> 
> Could you give an example of this? I can't really see how that would
> happen.
> 
> > that
> > the presense of a result form would cause the bound value to be
> > undefined makes no sense.
> 
> I certainly agree with this. I am just trying to understand how the
> nil bound variable introduced by the dolist form could be of any use
> whatsoever in the result form.

again, without qualifying the utility

Welcome to Macintosh Common Lisp Version 4.3.1!
? (mapcar #'funcall
        (let ((funlist nil))
          (dolist (a '(a s d) (progn (setf a :done) (push #'(lambda () a) funlist)))
            (push #'(lambda () a) funlist))))
(:DONE :DONE :DONE :DONE)
? 

as one runtime implements the operator.

...
From: Björn Lindberg
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <hcsfzg9rgof.fsf@knatte.nada.kth.se>
james anderson <··············@setf.de> writes:

> if you look back at pitman's posts, "the binding", as the spec terms it, may
> not have been "introduced" by the result clause, but may well be the same
> binding as was apparent in the body.
> 
> Bj�rn Lindberg wrote:
> > 
> > james anderson <··············@setf.de> writes:
> > 
> > > Bj�rn Lindberg wrote:
> > > >
> > > > james anderson <··············@setf.de> writes:
> > > >
> > > > > > ,----[ DOLIST Description ]
> > > > > > | At the time result-form is processed, var is bound to nil.
> > > > > > `----
> > > > > >
> > > > > > But why go to this length to ensure that var is visible to the
> > > > > > result-form, and then promise that var will be nil? That means that
> > > > > > var will never be of any use to the result-form.
> > > > >
> > > > > the result form could set it to something else.
> > > >
> > > > But since that variable goes out of scope upon leaving the DOLIST
> > > > form, that is not very useful, right?
> > >
> > > without in any way qualifying the utility, one must allow that
> > > something could have closed, or could close, over the binding.
> > 
> > Could you give an example of this? I can't really see how that would
> > happen.
> > 
> > > that
> > > the presense of a result form would cause the bound value to be
> > > undefined makes no sense.
> > 
> > I certainly agree with this. I am just trying to understand how the
> > nil bound variable introduced by the dolist form could be of any use
> > whatsoever in the result form.
> 
> again, without qualifying the utility
> 
> Welcome to Macintosh Common Lisp Version 4.3.1!
> ? (mapcar #'funcall
>         (let ((funlist nil))
>           (dolist (a '(a s d) (progn (setf a :done) (push #'(lambda () a) funlist)))
>             (push #'(lambda () a) funlist))))
> (:DONE :DONE :DONE :DONE)
> ? 

But relying on that behaviour is not conforming AFAIU, since DOLIST is
allowed to introduce a new binding for each element in the list, as
well as for the final nil. Cmucl does this, and so the expression
cmucl produces for the above is

(:DONE D S A)

The macroexpansion for the DOLIST in the above is

(DO ((#:G1006 '(A S D) (CDR #:G1006)))
    ((ENDP #:G1006)
     (LET ((A NIL))
       A
       (PROGN (SETF A :DONE) (PUSH #'(LAMBDA () A) FUNLIST))))
  (LET ((A (CAR #:G1006)))
    (PUSH #'(LAMBDA () A) FUNLIST)))

This would give the same result if the closed over variable was
introduced in the result form itself. Or am I missing your point?


Bj�rn
From: james anderson
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <3FC6183F.53616491@setf.de>
> >
> > again, without qualifying the utility
> >
> > Welcome to Macintosh Common Lisp Version 4.3.1!
> > ? (mapcar #'funcall
> >         (let ((funlist nil))
> >           (dolist (a '(a s d) (progn (setf a :done) (push #'(lambda () a) funlist)))
> >             (push #'(lambda () a) funlist))))
> > (:DONE :DONE :DONE :DONE)
> > ?
> 
> But relying on that behaviour is not conforming AFAIU, since DOLIST is
> allowed to introduce a new binding for each element in the list, as
> well as for the final nil. Cmucl does this, and so the expression
> cmucl produces for the above is
> 
> (:DONE D S A)
> 
> The macroexpansion for the DOLIST in the above is
> 
> (DO ((#:G1006 '(A S D) (CDR #:G1006)))
>     ((ENDP #:G1006)
>      (LET ((A NIL))
>        A
>        (PROGN (SETF A :DONE) (PUSH #'(LAMBDA () A) FUNLIST))))
>   (LET ((A (CAR #:G1006)))
>     (PUSH #'(LAMBDA () A) FUNLIST)))
> 
> This would give the same result if the closed over variable was
> introduced in the result form itself. Or am I missing your point?
> 
> Bj�rn

i read pitman's posts. they explained in detail matters which have been the
subject of discussions here in the past. my point was

> > But why go to this length to ensure that var is visible to the
> > result-form, and then promise that var will be nil? That means that
> > var will never be of any use to the result-form.
> 
> the result form could set it to something else.
> >
> > Wouldn't it be easier to just say something like, "It is
> > implementation-dependent whether var is visible to the result-form,
> > and if so the value of var is implementation-dependent?" The wording
> > isn't great, but meant to be equivalent to "undefined" in C++ standard
> > terms: the variable may contain garbage, so don't try to use its
> > value.
> 
> where would that leave anything which closed over it?
> 
> ...

which apply whether the binding is a single binding or a distinct binding for
each iteration. to which i added

> ... that the presense of a result
> form would cause the bound value to be undefined makes no sense.


...
From: Björn Lindberg
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <hcsbrqxrewz.fsf@knatte.nada.kth.se>
james anderson <··············@setf.de> writes:

> > This would give the same result if the closed over variable was
> > introduced in the result form itself. Or am I missing your point?
> > 
> > Bj�rn
> 
> i read pitman's posts. they explained in detail matters which have been the
> subject of discussions here in the past. my point was
> 
> > > But why go to this length to ensure that var is visible to the
> > > result-form, and then promise that var will be nil? That means that
> > > var will never be of any use to the result-form.
> > 
[1] > > the result form could set it to something else.
> > >
> > > Wouldn't it be easier to just say something like, "It is
> > > implementation-dependent whether var is visible to the result-form,
> > > and if so the value of var is implementation-dependent?" The wording
> > > isn't great, but meant to be equivalent to "undefined" in C++ standard
> > > terms: the variable may contain garbage, so don't try to use its
> > > value.
> > 
> > where would that leave anything which closed over it?
> > 
> > ...
> 
> which apply whether the binding is a single binding or a distinct binding for
> each iteration. to which i added
> 
> > ... that the presense of a result
> > form would cause the bound value to be undefined makes no sense.

I see. I misunderstood you then, sorry. I interpreted your first
response to me such that you implied that it could be useful to
close over the variable in question, and I just didn't see what that
would be. Now I see you just mentioned the possibility of the variable
being closed over as an argument for not leaving its value undefined,
which I agree with.

I'm still not clear on why the variable is in scope in the result form
at all though, since it is not supposed to be used anyway. To that
question you replied above[1], which to me implied that "setting it to
something else" in the result form could be useful somehow. I just
don't see how?


Bj�rn
From: Kent M Pitman
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <sfw1xrtjuet.fsf@shell01.TheWorld.com>
·······@nada.kth.se (Bj�rn Lindberg) writes:

> I see. I misunderstood you then, sorry. I interpreted your first
> response to me such that you implied that it could be useful to
> close over the variable in question, and I just didn't see what that
> would be. Now I see you just mentioned the possibility of the variable
> being closed over as an argument for not leaving its value undefined,
> which I agree with.

I sometimes speak of closures not to say "people should do this" but to 
merely say "the variable is in scope here" or "someone might close over it"
and they do need to know what they are doing.
 
> I'm still not clear on why the variable is in scope in the result form
> at all though, since it is not supposed to be used anyway. To that
> question you replied above[1], which to me implied that "setting it to
> something else" in the result form could be useful somehow. I just
> don't see how?

The answer is that there are expansions in which you want to insert
the result form in the middle, and it's just simpler to allow it than
to contrive some complicated way of getting out of scope.  It's an ease
of implementation issue, not a "the programmer wants it this way" issue.
From: Wolfhard Buß
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <m3llq0u0bs.fsf@buss-14250.user.cis.dfn.de>
* Bj�rn Lindberg:
> I'm still not clear on why the variable is in scope in the result form
> at all though, since it is not supposed to be used anyway.

Kent Pitman: `ease of implementation'

 (defmacro dolist ((var list &optional result) &body body)
   (let ((rest (gensym)))
     `(do* ((,rest ,list (rest ,rest))
            (,var (first ,rest) (first ,rest)))
           ((null ,rest) ,result)
       ,@body)))

The result form is in the scope of the binding of var.  When the result
form is evaluated var is bound to nil. 


-- 
"Hurry if you still want to see something. Everything is vanishing."
                                       --  Paul C�zanne (1839-1906)
From: Nils Goesche
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <r7zvnbto.fsf@cartan.de>
"Steven E. Harris" <········@raytheon.com> writes:

> ···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>
>>   (defmacro dosequence ((var sequence &optional result) &body forms)
>>     `(block nil
>>        (map nil (lambda (,var) ,@forms) ,sequence)
>>        ,@(when result (list `(let ((,var nil)) ,result)))))
>
> Why does var have to be set to nil before evaluating the result form?

As this is what's generally done.  See the dictionary entry for DOLIST
in the HyperSpec, for instance.

Regards,
-- 
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."

PGP key ID #xD26EF2A0
From: Lars Brinkhoff
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <854qwsuls1.fsf@junk.nocrew.org>
···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>   (defmacro dosequence ((var sequence &optional result) &body forms)
>     `(block nil
>        (map nil (lambda (,var) ,@forms) ,sequence)
>        ,@(when result (list `(let ((,var nil)) ,result)))))

Perhaps throw in a tagbody too.

-- 
Lars Brinkhoff,         Services for Unix, Linux, GCC, HTTP
Brinkhoff Consulting    http://www.brinkhoff.se/
From: Kent M Pitman
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <sfw7k1nnb2f.fsf@shell01.TheWorld.com>
Lars Brinkhoff <·········@nocrew.org> writes:

> ···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> >   (defmacro dosequence ((var sequence &optional result) &body forms)
> >     `(block nil
> >        (map nil (lambda (,var) ,@forms) ,sequence)
> >        ,@(when result (list `(let ((,var nil)) ,result)))))
> 
> Perhaps throw in a tagbody too.

Ick.

My immediate thought was - where?

I rushed back to CLHS, just knowing I probably left this vague.  The
wording "The body of dolist is like a tagbody." can, I suppose, be
construed to imply "and the result-form doesn't get injected into it."
but that's a pretty lousy way for me to have written it.  Then again,
maybe it was always vague. (Anyone got CLTL handy?  Mine's packed.)

The interesting test case is:

  (block done  ;; Bad style, but useful test case for scope
    (tagbody
        (dolist (x '(1) (go foo))
            (go over)
          foo
            (return-from done 'inner)
          over)
        (return-from done 'broken)
      foo
        (return-from done 'outer)))

LispWorks 4.2.7 returns OUTER, which I suspect is the best thing,
but I wouldn't want to be telling an implementation that returned
INNER that they were wrong.  I'd rather just tell users not to lean
to heavy on being able to do GO in that context...
From: Lars Brinkhoff
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <85vfp7tpnw.fsf@junk.nocrew.org>
Kent M Pitman <······@nhplace.com> writes:
> Lars Brinkhoff <·········@nocrew.org> writes:
> > ···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> > >   (defmacro dosequence ((var sequence &optional result) &body forms)
> > >     `(block nil
> > >        (map nil (lambda (,var) ,@forms) ,sequence)
> > >        ,@(when result (list `(let ((,var nil)) ,result)))))
> > Perhaps throw in a tagbody too.
> My immediate thought was - where?

Around ,@forms was my idea, but after reading your reply, I guess
that's not the only possibility.

> I rushed back to CLHS, just knowing I probably left this vague.  The
> wording "The body of dolist is like a tagbody." can, I suppose, be
> construed to imply "and the result-form doesn't get injected into it."
> but that's a pretty lousy way for me to have written it.  Then again,
> maybe it was always vague. (Anyone got CLTL handy?  Mine's packed.

"The body of the loop is implicitly a tagbody construct; it may
contain tags to serve as the targets of go statements."

I can't see anything about whether the result form should be inside or
outside the implicit tagbody.

-- 
Lars Brinkhoff,         Services for Unix, Linux, GCC, HTTP
Brinkhoff Consulting    http://www.brinkhoff.se/
From: james anderson
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <3FC4A6BC.1116B241@setf.de>
Lars Brinkhoff wrote:
> 
> ...
> 
> I can't see anything about whether the result form should be inside or
> outside the implicit tagbody.
> 
> --
> Lars Brinkhoff,         Services for Unix, Linux, GCC, HTTP
> Brinkhoff Consulting    http://www.brinkhoff.se/


Kent M Pitman wrote:
> 
> "Steven E. Harris" <········@raytheon.com> writes:
> 
> > ···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> >
> > >   (defmacro dosequence ((var sequence &optional result) &body forms)
> > >     `(block nil
> > >        (map nil (lambda (,var) ,@forms) ,sequence)
> > >        ,@(when result (list `(let ((,var nil)) ,result)))))
> >
> > Why does var have to be set to nil before evaluating the result form?
> 
> What would you set it to?  The form is to evaluate in the scope of var,
> if you're going to make it symmetric with, for example, DOLIST. From
> CLHS's DOLIST dictionary entry:
> 
>   The scope of the binding of var does not include the list-form,
>   but the result-form is included.
> 
> and the only other really obvious choice of a value is:
> 
>   (defmacro dosequence ((var sequence &optional result) &body forms)
>     (let ((temp (gensym)))
>       `(block nil
>           (let ((,var nil))
>             (map nil #'(lambda (,temp)
>                          (setq ,var ,temp)
>                          ,@forms)
>                      ,sequence)
+             (setf ,var nil)
>             ,@(when result `(,result))))))
> 
> I'm not sure I really like this better, since (ignoring even the issue of
> the presence of the SETQ) var is then bound to something relatively random.
> Making it a boring value like NIL discourages the use of it for any purpose,
> (since NIL already has a name if it's needed), and that's all to the good.

wouldn't this be preferred to the decimated bindings of the original example
in order to better parallel the behaviour of do &company? the spec does say
"the binding". the tagbody question remains, however, a riddle. i can imagine
ways to formulate expansions such that one could transfer into the body, but
i'm at a loss as to how to arrange that one could transfer into the "single
form" which constitutes the result form. which argues against an intention
that it be included in the tagbody.

(defmacro dosequence ((var sequence &optional result) &body forms)
  (let ((end-p (gensym))
        (fun (gensym)))
    `(block nil
       (flet ((,fun (,var ,end-p)
                (tagbody
                  (when ,end-p (go ,end-p))
                  ,@forms
                  (return-from ,fun nil)
                  ,end-p
                  (return-from ,fun ,result))))
         (map nil #'(lambda (element) (,fun element nil))
              ,sequence)
         ,@(when result `((,fun nil t)))))))

...
From: Peter Seibel
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <m3r7zw5kho.fsf@javamonkey.com>
Kent M Pitman <······@nhplace.com> writes:

> Peter Seibel <·····@javamonkey.com> writes:
> 
> > The standard specically points out the LIST and VECTOR types are not
> > necessarily an exhaustive partition of SEQUENCE. Are there any
> > implementations that provide for other kind of sequences?

[snip good stuff]

> On the other hand, absent extension protocols for sequences such as
> those provided by Dylan (and which could be added by implementations
> of CL voluntarily as an addition), I don't see how to make the
> introduction efficient.

That's sort of what I was thinking--an implementation could provide a
provide an appropriate GFs that are used by ELT, LENGTH, and the other
sequence functions allowing users to make anything they wanted look
like a sequence.

> In order for a portable program to use such new types without
> knowing of them, it would have to use LENGTH and ELT to iterate
> across them, there being no DOSEQ, and that wouldn't be adequately
> efficient.

Right, so the extension protocol would ideally provide other GFs that
allow the user to provide more efficient iteration for the new type
and the standard sequence functions would use those GFs where
appropriate.

Thanks.

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp
From: Bruno Haible
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <bq0b2e$2qn$1@laposte.ilog.fr>
Peter Seibel <·····@javamonkey.com> wrote:
> The standard specically points out the LIST and VECTOR types are not
> necessarily an exhaustive partition of SEQUENCE. Are there any
> implementations that provide for other kind of sequences?

GNU clisp has a primitive for defining new types of sequences. It's
called sys::%defseq and documented at the top of clisp/src/sequence.d.
I used this interface once to turn AVL trees into sequences. Binary
trees viewed as sequences, or string "filaments", it's all essentially
the same idea: split big sequences into small chunks so that random
access and insert/remove are both fast.

Bruno
From: Peter Seibel
Subject: Re: Sequences other than list and vector
Date: 
Message-ID: <m34qws5ipg.fsf@javamonkey.com>
Bruno Haible <·····@clisp.org> writes:

> Peter Seibel <·····@javamonkey.com> wrote:
> > The standard specically points out the LIST and VECTOR types are not
> > necessarily an exhaustive partition of SEQUENCE. Are there any
> > implementations that provide for other kind of sequences?
> 
> GNU clisp has a primitive for defining new types of sequences. It's
> called sys::%defseq and documented at the top of clisp/src/sequence.d.
> I used this interface once to turn AVL trees into sequences. Binary
> trees viewed as sequences, or string "filaments", it's all essentially
> the same idea: split big sequences into small chunks so that random
> access and insert/remove are both fast.

Cool.

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp