From: c hore
Subject: Bounding Indices in Sequence Functions
Date: 
Message-ID: <ca167c61.0210210227.64db858c@posting.google.com>
Does the Common Lisp standard specify the behavior of sequence
functions when the bounding indices do NOT satisfy
    0 <= start <= end <= length
?

I could not find anything explicit in the HyperSpec on this
question, so I suppose the behavior is
implementation-dependent?

When end < start, I was surprised to see CMUCL give
    (find 'c '(a b c) :start 2 :end 1) ==> c

When length < start and/or length < end, CMUCL seems
to signal an error if the sequence is a vector, but
not if it is a list.  I don't know whether other
implementations behave the same way, or could be
counted on to behave the same way...
From: Tim Bradshaw
Subject: Re: Bounding Indices in Sequence Functions
Date: 
Message-ID: <ey3u1jgrrkt.fsf@cley.com>
* c hore wrote:

> When length < start and/or length < end, CMUCL seems
> to signal an error if the sequence is a vector, but
> not if it is a list.  I don't know whether other
> implementations behave the same way, or could be
> counted on to behave the same way...

I'm not sure what the spec says but I'd hope for errors in safe code
for easily detected problems.  In particular I think that if END and
START are both given and non-NIL, and END < START, then this should be
detected and an error signalled.

*However* not all problems are easily detected.  In particular, for a
list, if START < LENGTH, but END > LENGTH, but somehing is found after
START, then the only way to detect any problem would be to
gratuitously keep on looking down the list until you'd got past
END. This seems clearly to be an unreasonable thing to expect an
implementation to do!

An example:

    (find 'c '(a b c d) :start 0 :end 1000)

--tim
From: Jason Kantz
Subject: Re: Bounding Indices in Sequence Functions
Date: 
Message-ID: <I4Et9.1130$Fj6.74345@newsread1.prod.itd.earthlink.net>
Tim Bradshaw <···@cley.com> wrote in message
····················@cley.com...
> An example:
>
>     (find 'c '(a b c d) :start 0 :end 1000)
>
> --tim
>

here's an interesting interaction w/ ACL:

CL-USER(105): (defun foo (x) (find x '(a b c d) :start 0 :end 1000))
FOO
CL-USER(106): (compile 'foo)
FOO
NIL
NIL
CL-USER(107): (foo 'x)
NIL
CL-USER(108): (foo 'a)
A


CL-USER(109): (defun foo (x) (find x #(a b c d) :start 0 :end 1000))
FOO
CL-USER(110): (compile 'foo)
FOO
NIL
NIL
CL-USER(111): (foo 'a)
A
CL-USER(112): (foo 'x)
X
^-------!??
CL-USER(113): (foo 'y)
NIL


CL-USER(114): (defun foo (x) (find x #(a b c d) :start 0))
FOO
CL-USER(115): (compile 'foo)
FOO
NIL
NIL
CL-USER(116): (foo 'x)
NIL
CL-USER(117):


--
Jason Kantz
http://kantz.com/jason
From: Nils Goesche
Subject: Re: Bounding Indices in Sequence Functions
Date: 
Message-ID: <lkr8ej26sy.fsf@pc022.bln.elmeg.de>
·······@yahoo.com (c hore) writes:

> Does the Common Lisp standard specify the behavior of sequence
> functions when the bounding indices do NOT satisfy
>     0 <= start <= end <= length
> ?
> 
> I could not find anything explicit in the HyperSpec on this
> question, so I suppose the behavior is
> implementation-dependent?

I would say it is undefined behavior.  It is always undefined behavior
(1.4.2) when the type restrictions in the ``Arguments and Values''
section of a dictionary entry are not satisfied (1.4.4.3).  In the
case of FIND, it says that start, end should be ``bounding index
designators'', which denote ``bounding indices'', which are defined in
the Glossary as satisfying  0 <=istart <=iend <=n.  So, if your start
and end parameters do not satisfy this restriction, the implementation
is free to do whatever it likes.

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

PGP key ID 0x0655CFA0
From: Bruce Hoult
Subject: Re: Bounding Indices in Sequence Functions
Date: 
Message-ID: <bruce-FD9AB4.21151922102002@copper.ipg.tsnz.net>
In article <··············@pc022.bln.elmeg.de>,
 Nils Goesche <······@cartan.de> wrote:

> ·······@yahoo.com (c hore) writes:
> 
> > Does the Common Lisp standard specify the behavior of sequence
> > functions when the bounding indices do NOT satisfy
> >     0 <= start <= end <= length
> > ?
> > 
> > I could not find anything explicit in the HyperSpec on this
> > question, so I suppose the behavior is
> > implementation-dependent?
> 
> I would say it is undefined behavior.  It is always undefined behavior
> (1.4.2) when the type restrictions in the ``Arguments and Values''
> section of a dictionary entry are not satisfied (1.4.4.3).  In the
> case of FIND, it says that start, end should be ``bounding index
> designators'', which denote ``bounding indices'', which are defined in
> the Glossary as satisfying  0 <=istart <=iend <=n.  So, if your start
> and end parameters do not satisfy this restriction, the implementation
> is free to do whatever it likes.

I would *hope* that is boundedly undefined, namely that you might not 
get the answer you were expecting but the program shouldn't crash, your 
computer should not turn into a hyperspace gateway, etc.

-- Bruce
From: Barry Margolin
Subject: Re: Bounding Indices in Sequence Functions
Date: 
Message-ID: <hndt9.5$NV2.978@paloalto-snr1.gtei.net>
In article <···························@copper.ipg.tsnz.net>,
Bruce Hoult  <·····@hoult.org> wrote:
>In article <··············@pc022.bln.elmeg.de>,
> Nils Goesche <······@cartan.de> wrote:
>
>> ·······@yahoo.com (c hore) writes:
>> 
>> > Does the Common Lisp standard specify the behavior of sequence
>> > functions when the bounding indices do NOT satisfy
>> >     0 <= start <= end <= length
>> > ?
>> > 
>> > I could not find anything explicit in the HyperSpec on this
>> > question, so I suppose the behavior is
>> > implementation-dependent?
>> 
>> I would say it is undefined behavior.  It is always undefined behavior
>> (1.4.2) when the type restrictions in the ``Arguments and Values''
>> section of a dictionary entry are not satisfied (1.4.4.3).  In the
>> case of FIND, it says that start, end should be ``bounding index
>> designators'', which denote ``bounding indices'', which are defined in
>> the Glossary as satisfying  0 <=istart <=iend <=n.  So, if your start
>> and end parameters do not satisfy this restriction, the implementation
>> is free to do whatever it likes.
>
>I would *hope* that is boundedly undefined, namely that you might not 
>get the answer you were expecting but the program shouldn't crash, your 
>computer should not turn into a hyperspace gateway, etc.

There's nothing guaranteeing this.  It's not required to check that
end<=length, and if it doesn't check you can get a buffer overflow (like
the kind that have been the cause of so many security problems).

If you have high safety configured, I would expect implementations to
include bounds checks, so you shouldn't have a problem.  But I don't think
this is required by the standard, it's just common tradition.

-- 
Barry Margolin, ······@genuity.net
Genuity, Woburn, 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: Erik Naggum
Subject: Re: Bounding Indices in Sequence Functions
Date: 
Message-ID: <3244295761850806@naggum.no>
* Barry Margolin
| There's nothing guaranteeing this.  It's not required to check that
| end<=length, and if it doesn't check you can get a buffer overflow (like
| the kind that have been the cause of so many security problems).

  That does not follow strictly from the premises.  The test for an actual
  index < length may well be performed without testing that end <= length.
  Although some CPU cycles may conceivably be saved by testing once, the
  test may also be performed in parallel with the actual memory access
  instruction in such a way that a test at the head of the loop would only
  waste resources and be obnoxious if the purpose of the function were to
  be satisfied before the condition became relevant.

-- 
Erik Naggum, Oslo, Norway

Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.
comp.lang.lisp / 2002 / oct