|
|
 | | From: | Ed | | Subject: | Ambiguous SEARCH | | Date: | Sun, 9 Jan 2005 16:40:13 +1100 |
|
|
 | What should SEARCH return in the following instance?
S" fred" HERE 0 SEARCH
In Gforth and Win32Forth it returns a match while in
CHForth it fails. Other forths ???
Personally I've found the match result to be more useful.
Ed
|
|
| | From: | Coos Haak | | Subject: | Re: Ambiguous SEARCH | | Date: | Sun, 9 Jan 2005 15:42:34 +0100 |
|
|
| Op Sun, 9 Jan 2005 16:40:13 +1100 schreef Ed:
> What should SEARCH return in the following instance?
>
> S" fred" HERE 0 SEARCH
>
> In Gforth and Win32Forth it returns a match while in
> CHForth it fails. Other forths ???
>
> Personally I've found the match result to be more useful.
>
> Ed
You are using the publicized version of 1994!
Like Gforth and Win32Forth, CHForth succeeds now.
That is, in the current version, not available yet.
I've changed the behaviour some time ago, there
was a discussion about it here.
--
Coos
|
|
| | From: | Alex McDonald | | Subject: | Re: Ambiguous SEARCH | | Date: | 10 Jan 2005 10:37:09 -0800 |
|
|
|
Jeff wrote:
> Alex McDonald wrote:
>
> > Except that a zero length string is a valid string in all other
> > circumstances, and the effect of returning found on a SEARCH is
> > equivalent to the regexp ^ -- something that seems quite logical.
>
> However, searching for the regex ^ isn't the same as searching for an
> empty text string. You are searching for the beginning of a string
(or
> line in this case), which is different. And that should match.
Perhaps I wasn't clear enough; ^ matches on the null at the start of
the line. The effect of a null SEARCH and ^ are equivalent. The match
for ^ is on the null at the start of the line, btw, not the beginning
of the line. To match that would be ^. (caret dot).
--
Regards
Alex McDonald
|
|
| | From: | Michael Park | | Subject: | What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | 11 Jan 2005 13:07:41 -0800 |
|
|
|
Alex McDonald wrote:
> As for COMPARE (a test of equality will suffice to make the point,
> rather than less than, equal, greater than): A null string is equal
to
> itself (true of any string). A null string is equal to another null
> string (because they are indistinguishable; the address is not part
of
> the comparison). A null string is not equal to any non-null string
> (because the lengths differ).
I agree that SEARCHing for a null string should succeed, but what
should be the result of COMPAREing a null string and a non-null string?
|
|
| | From: | Jerry Avins | | Subject: | Re: What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | Tue, 11 Jan 2005 17:06:20 -0500 |
|
|
| Michael Park wrote:
> Alex McDonald wrote:
>
>>As for COMPARE (a test of equality will suffice to make the point,
>>rather than less than, equal, greater than): A null string is equal
>
> to
>
>>itself (true of any string). A null string is equal to another null
>>string (because they are indistinguishable; the address is not part
>
> of
>
>>the comparison). A null string is not equal to any non-null string
>>(because the lengths differ).
>
>
> I agree that SEARCHing for a null string should succeed, but what
> should be the result of COMPAREing a null string and a non-null string?
Not equal. How otherwise?
Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ
|
|
| | From: | Ed | | Subject: | Re: What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | Wed, 12 Jan 2005 15:09:53 +1100 |
|
|
|
"Michael Park" wrote in message
news:1105477661.731492.140880@c13g2000cwb.googlegroups.com...
>
> Alex McDonald wrote:
> > As for COMPARE (a test of equality will suffice to make the point,
> > rather than less than, equal, greater than): A null string is equal
> to
> > itself (true of any string). A null string is equal to another null
> > string (because they are indistinguishable; the address is not part
> of
> > the comparison). A null string is not equal to any non-null string
> > (because the lengths differ).
>
> I agree that SEARCHing for a null string should succeed, but what
> should be the result of COMPAREing a null string and a non-null string?
The Standard specifically rules it out (different string lengths).
Whether you'd want it to pass probably depends on the
facility gained (?) and whether other languages have it.
Ed
|
|
| | From: | rickman | | Subject: | Re: What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | Wed, 12 Jan 2005 02:07:22 -0500 |
|
|
| Ed wrote:
> "Michael Park" wrote in message
> news:1105477661.731492.140880@c13g2000cwb.googlegroups.com...
>
>>Alex McDonald wrote:
>>
>>>As for COMPARE (a test of equality will suffice to make the point,
>>>rather than less than, equal, greater than): A null string is equal
>>
>>to
>>
>>>itself (true of any string). A null string is equal to another null
>>>string (because they are indistinguishable; the address is not part
>>
>>of
>>
>>>the comparison). A null string is not equal to any non-null string
>>>(because the lengths differ).
>>
>>I agree that SEARCHing for a null string should succeed, but what
>>should be the result of COMPAREing a null string and a non-null string?
>
>
> The Standard specifically rules it out (different string lengths).
>
> Whether you'd want it to pass probably depends on the
> facility gained (?) and whether other languages have it.
17.6.1.0935 COMPARE STRING
( c-addr1 u1 c-addr2 u2 -- n )
Compare the string specified by c-addr1 u1 to the string specified by
c-addr2 u2. The strings are compared, beginning at the given addresses,
character by character, up to the length of the shorter string or until
a difference is found. If the two strings are identical, n is zero. If
the two strings are identical up to the length of the shorter string, n
is minus-one (-1) if u1 is less than u2 and one (1) otherwise. If the
two strings are not identical up to the length of the shorter string, n
is minus-one (-1) if the first non-matching character in the string
specified by c-addr1 u1 has a lesser numeric value than the
corresponding character in the string specified by c-addr2 u2 and one
(1) otherwise.
--
Rick Collins
rick.collins@XYarius.com
Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design http://www.arius.com
4 King Ave. 301-682-7772 Voice
Frederick, MD 21701-3110 GNU tools for the ARM http://www.gnuarm.com
|
|
| | From: | Ed | | Subject: | Re: What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | Thu, 13 Jan 2005 12:47:07 +1100 |
|
|
|
"rickman" wrote in message
news:WICdnfAM3oowUXncRVn-og@adelphia.com...
> Ed wrote:
>
> > "Michael Park" wrote in message
> > news:1105477661.731492.140880@c13g2000cwb.googlegroups.com...
> >
> >>Alex McDonald wrote:
> >>
> >>>As for COMPARE (a test of equality will suffice to make the point,
> >>>rather than less than, equal, greater than): A null string is equal
> >>
> >>to
> >>
> >>>itself (true of any string). A null string is equal to another null
> >>>string (because they are indistinguishable; the address is not part
> >>
> >>of
> >>
> >>>the comparison). A null string is not equal to any non-null string
> >>>(because the lengths differ).
> >>
> >>I agree that SEARCHing for a null string should succeed, but what
> >>should be the result of COMPAREing a null string and a non-null string?
> >
> >
> > The Standard specifically rules it out (different string lengths).
> >
> > Whether you'd want it to pass probably depends on the
> > facility gained (?) and whether other languages have it.
>
> 17.6.1.0935 COMPARE STRING
>
> ( c-addr1 u1 c-addr2 u2 -- n )
>
> Compare the string specified by c-addr1 u1 to the string specified by
> [..]
I misunderstood the question. I assumed Michael was asking
whether there would be any advantage in having it pass (even
though the Standard forbids it).
Ed
|
|
| | From: | BillCook | | Subject: | Re: What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | Tue, 11 Jan 2005 16:26:09 -0800 |
|
|
|
"Michael Park" wrote in message
news:1105477661.731492.140880@c13g2000cwb.googlegroups.com...
>
> Alex McDonald wrote:
>> As for COMPARE (a test of equality will suffice to make the point,
>> rather than less than, equal, greater than): A null string is equal
> to
>> itself (true of any string). A null string is equal to another null
>> string (because they are indistinguishable; the address is not part
> of
>> the comparison). A null string is not equal to any non-null string
>> (because the lengths differ).
>
> I agree that SEARCHing for a null string should succeed, but what
> should be the result of COMPAREing a null string and a non-null string?
This comment may not be on the same subject, but it is certainly related.
To the best of my recollection, in SQL, a NULL does not equal anything, not
even another null. An example is whether two people, neither of whom has a
middle name, can be said to have the SAME middle name.
Bill Cook
Kent WA USA
|
|
| | From: | Jerry Avins | | Subject: | Re: What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | Wed, 12 Jan 2005 12:45:02 -0500 |
|
|
| BillCook wrote:
> "Michael Park" wrote in message
> news:1105477661.731492.140880@c13g2000cwb.googlegroups.com...
>
>>Alex McDonald wrote:
>>
>>>As for COMPARE (a test of equality will suffice to make the point,
>>>rather than less than, equal, greater than): A null string is equal
>>
>>to
>>
>>>itself (true of any string). A null string is equal to another null
>>>string (because they are indistinguishable; the address is not part
>>
>>of
>>
>>>the comparison). A null string is not equal to any non-null string
>>>(because the lengths differ).
>>
>>I agree that SEARCHing for a null string should succeed, but what
>>should be the result of COMPAREing a null string and a non-null string?
>
>
> This comment may not be on the same subject, but it is certainly related.
>
> To the best of my recollection, in SQL, a NULL does not equal anything, not
> even another null. An example is whether two people, neither of whom has a
> middle name, can be said to have the SAME middle name.
>
> Bill Cook
> Kent WA USA
"Coffee, no milk, please."
"I'm sorry, Ma'am, we're out of milk, but I can give you coffee without
cream."
Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ
|
|
| | From: | Albert van der Horst | | Subject: | [OT] Joke Re: What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | 14 Jan 2005 00:36:27 +0100 |
|
|
| In article <34l60uF474cliU3@individual.net>, Jerry Avins wrote:
>
>"Coffee, no milk, please."
>
>"I'm sorry, Ma'am, we're out of milk, but I can give you coffee without
>cream."
The Dutch version:
"Can I have a coffee without sugar please?"
"Sorry, we haven't. We only have coffee without milk".
>
>Jerry
Groetjes Albert
--
Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS
To suffer is the prerogative of the strong. The weak -- perish.
albert@spenarnc.xs4all.nl http://home.hccnet.nl/a.w.m.van.der.horst
|
|
| | From: | Albert van der Horst | | Subject: | Re: What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | 12 Jan 2005 09:00:16 GMT |
|
|
| In article <2uSdnU7eXeE483ncRVn-3A@comcast.com>,
BillCook wrote:
>
>"Michael Park" wrote in message
>news:1105477661.731492.140880@c13g2000cwb.googlegroups.com...
>>
>>
>> I agree that SEARCHing for a null string should succeed, but what
>> should be the result of COMPAREing a null string and a non-null string?
>
>This comment may not be on the same subject, but it is certainly related.
>
>To the best of my recollection, in SQL, a NULL does not equal anything, not
>even another null. An example is whether two people, neither of whom has a
>middle name, can be said to have the SAME middle name.
That means that nothing has been filled in.
Such NULL should be compared to a NotANumber
in floating point package, i.e. something invalid. Now if you operate
on something invalid the result is invalid.
I'm sure that SQL allows to fill in an empty string for a middle
name.
>
>Bill Cook
>Kent WA USA
>
>
--
--
Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS
One man-hour to invent,
One man-week to implement,
One lawyer-year to patent.
|
|
| | From: | Michael Park | | Subject: | Re: What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | 11 Jan 2005 14:15:55 -0800 |
|
|
|
Jerry Avins wrote:
> Not equal. How otherwise?
I thought COMPARE also indicated whether the first string is "less
than" the second, so I wondered if "" is less than "nonnull". Maybe
I'm thinking of some other word?
|
|
| | From: | Coos Haak | | Subject: | Re: What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | Wed, 12 Jan 2005 01:19:57 +0100 |
|
|
| Op 11 Jan 2005 14:15:55 -0800 schreef Michael Park:
> Jerry Avins wrote:
>> Not equal. How otherwise?
>
> I thought COMPARE also indicated whether the first string is "less
> than" the second, so I wondered if "" is less than "nonnull". Maybe
> I'm thinking of some other word?
What about:
HERE 0 S" FRED" COMPARE .
-1
S" FRED" HERE 0 COMPARE .
1
HERE 0 HERE 0 COMPARE .
0
Isn't a string with length zero less than
a longer string?
--
Coos
|
|
| | From: | Jerry Avins | | Subject: | Re: What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | Wed, 12 Jan 2005 12:41:58 -0500 |
|
|
| Michael Park wrote:
> Jerry Avins wrote:
>
>>Not equal. How otherwise?
>
>
> I thought COMPARE also indicated whether the first string is "less
> than" the second, so I wondered if "" is less than "nonnull". Maybe
> I'm thinking of some other word?
Two messages earlier in the thread, Alex McDonald wrote:
>> As for COMPARE (a test of equality will suffice to make the point,
>> rather than less than, equal, greater than) ...
I responded in that spirit.
Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ
|
|
| | From: | rickman | | Subject: | Re: What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | Wed, 12 Jan 2005 13:07:31 -0500 |
|
|
| Jerry Avins wrote:
> Michael Park wrote:
>
>
>>Jerry Avins wrote:
>>
>>
>>>Not equal. How otherwise?
>>
>>
>>I thought COMPARE also indicated whether the first string is "less
>>than" the second, so I wondered if "" is less than "nonnull". Maybe
>>I'm thinking of some other word?
>
>
> Two messages earlier in the thread, Alex McDonald wrote:
>
>
>>>As for COMPARE (a test of equality will suffice to make the point,
>>>rather than less than, equal, greater than) ...
>
>
> I responded in that spirit.
That seems to be a typical Forth solution. If you can't solve the
problem easily, then change the problem to one you *can* solve easily. ;)
--
Rick Collins
rick.collins@XYarius.com
Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design http://www.arius.com
4 King Ave. 301-682-7772 Voice
Frederick, MD 21701-3110 GNU tools for the ARM http://www.gnuarm.com
|
|
| | From: | Jerry Avins | | Subject: | Re: What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | Wed, 12 Jan 2005 13:17:19 -0500 |
|
|
| rickman wrote:
> Jerry Avins wrote:
>
>> Michael Park wrote:
>>
>>
>>> Jerry Avins wrote:
>>>
>>>
>>>> Not equal. How otherwise?
>>>
>>>
>>>
>>> I thought COMPARE also indicated whether the first string is "less
>>> than" the second, so I wondered if "" is less than "nonnull". Maybe
>>> I'm thinking of some other word?
>>
>>
>>
>> Two messages earlier in the thread, Alex McDonald wrote:
>>
>>
>>>> As for COMPARE (a test of equality will suffice to make the point,
>>>> rather than less than, equal, greater than) ...
>>
>>
>>
>> I responded in that spirit.
>
>
> That seems to be a typical Forth solution. If you can't solve the
> problem easily, then change the problem to one you *can* solve easily. ;)
You pain me deeply! The question was asked with a stated constraint. I
respected that constraint when I answered. To call that ducking the
question is sheer calumny, Sir! :-)
Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ
|
|
| | From: | rickman | | Subject: | Re: What about COMPARE? (was Re: Ambiguous SEARCH | | Date: | Wed, 12 Jan 2005 14:46:08 -0500 |
|
|
| Jerry Avins wrote:
> rickman wrote:
>
>>That seems to be a typical Forth solution. If you can't solve the
>>problem easily, then change the problem to one you *can* solve easily. ;)
>
>
> You pain me deeply! The question was asked with a stated constraint. I
> respected that constraint when I answered. To call that ducking the
> question is sheer calumny, Sir! :-)
I didn't mean to offend. I was making a joke! Didn't you see the wink
at the end? And now you make matters worse by forcing me to pull a
dictionary off the shelf to look up 'calumny'... Jeeze...
--
Rick Collins
rick.collins@XYarius.com
Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design http://www.arius.com
4 King Ave. 301-682-7772 Voice
Frederick, MD 21701-3110 GNU tools for the ARM http://www.gnuarm.com
|
|
| | From: | Anton Ertl | | Subject: | Re: Ambiguous SEARCH | | Date: | Sun, 09 Jan 2005 07:46:14 GMT |
|
|
| "Ed" writes:
>What should SEARCH return in the following instance?
>
> S" fred" HERE 0 SEARCH
A match at the start of the "fred" string.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.complang.tuwien.ac.at/forth/ansforth/forth200x.html
|
|
| | From: | Alex McDonald | | Subject: | Re: Ambiguous SEARCH | | Date: | 13 Jan 2005 05:36:52 -0800 |
|
|
| rickman wrote:
> Alex McDonald wrote:
>
> > rickman wrote:
> >
> >
> >
> >>Can anyone give me a valid practical case
> >>where not having the search for a null string return
> >>true would hose up some solution to a problem?
> >>
> >
> >
> > WORDS
>
> Ok, now can you explain *why* this is a problem?
>
I was a little cryptic, sorry.
W32F extends the syntax of WORDS to be
WORDS filter
where the filter is optional. If there's no filter, then all words are
returned (SEARCH on a null), otherwise the words that contain the
filter are returned (SEARCH on filter). There's no requirement to check
for a null string; it's handled automtically as the null string matches
on all names.
[The implemntation of WORDS in W32F doesn't follow that exactly, due to
some vocabulary switching on filter presence, but the principle is the
same.]
--
Regards
Alex McDonald
|
|
| | From: | Alex McDonald | | Subject: | Re: Ambiguous SEARCH | | Date: | 12 Jan 2005 04:23:28 -0800 |
|
|
| rickman wrote:
> Can anyone give me a valid practical case
> where not having the search for a null string return
> true would hose up some solution to a problem?
>
WORDS
--
Regards
Alex McDonald
|
|
| | From: | rickman | | Subject: | Re: Ambiguous SEARCH | | Date: | Wed, 12 Jan 2005 13:04:09 -0500 |
|
|
| Alex McDonald wrote:
> rickman wrote:
>
>
>
>>Can anyone give me a valid practical case
>>where not having the search for a null string return
>>true would hose up some solution to a problem?
>>
>
>
> WORDS
Ok, now can you explain *why* this is a problem?
--
Rick Collins
rick.collins@XYarius.com
Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design http://www.arius.com
4 King Ave. 301-682-7772 Voice
Frederick, MD 21701-3110 GNU tools for the ARM http://www.gnuarm.com
|
|
| | From: | Ed | | Subject: | Re: Ambiguous SEARCH | | Date: | Thu, 13 Jan 2005 13:27:26 +1100 |
|
|
|
"rickman" wrote in message
news:oI6dnR6gOKwC-3jcRVn-qA@adelphia.com...
> Alex McDonald wrote:
>
> > rickman wrote:
> >
> >
> >
> >>Can anyone give me a valid practical case
> >>where not having the search for a null string return
> >>true would hose up some solution to a problem?
> >>
> >
> >
> > WORDS
>
> Ok, now can you explain *why* this is a problem?
If writing more code is not a problem then by all means.
The result will be longer and slower.
Rarely does one get the opportunity to add more facility
at *no cost* but that's exactly what this SEARCH does!
Not to take it would be perverse.
Ed
|
|
| | From: | Jeff | | Subject: | Re: Ambiguous SEARCH | | Date: | Sun, 09 Jan 2005 15:31:07 GMT |
|
|
| Ed wrote:
> What should SEARCH return in the following instance?
>
> S" fred" HERE 0 SEARCH
>
> In Gforth and Win32Forth it returns a match while in
> CHForth it fails. Other forths ???
SwiftForth fails. Looking at the first ASM line in SwiftForth shows why:
EBX EBX TEST 0<> IF
I know this is ambiguous, but I believe not matching to be the correct
behavior. For example, when matching large amounts of data in a loop, I
wouldn't want to accidently get stuck in an infinite loop just because
the length of my pattern was reduced to 0 length.
Jeff M.
--
http://www.retrobyte.org
mailto:massung@gmail.com
|
|
| | From: | Anton Ertl | | Subject: | Re: Ambiguous SEARCH | | Date: | Sun, 09 Jan 2005 18:46:42 GMT |
|
|
| "Jeff" writes:
>Ed wrote:
>
>> What should SEARCH return in the following instance?
>>
>> S" fred" HERE 0 SEARCH
>>
>> In Gforth and Win32Forth it returns a match while in
>> CHForth it fails. Other forths ???
>
>SwiftForth fails. Looking at the first ASM line in SwiftForth shows why:
>
>EBX EBX TEST 0<> IF
>
>I know this is ambiguous,
It is not ambiguous, it is clear what should happen.
Maybe something to convince you:
If a search with parameters c-addr1 u1 c-addr2 u2 (where u2>0)
succeeds, a search for c-addr1 u1 c-addr2 u2-1 must also succeed.
E.g., if you search in "abcdefg" for "cd", the search succeeds; if you
search in the same string only for "c", this also succeeds; and if you
search only for "", that also succeeds.
> but I believe not matching to be the correct
>behavior. For example, when matching large amounts of data in a loop, I
>wouldn't want to accidently get stuck in an infinite loop just because
>the length of my pattern was reduced to 0 length.
That does not make failing correct. Fix your program, or define a
word
: search-but-fail-on-empty ( c-addr1 u1 c-addr2 u2 -- c-addr3 u3 flag )
dup 0= if
nip exit
then
search ;
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.complang.tuwien.ac.at/forth/ansforth/forth200x.html
|
|
| | From: | Jeff | | Subject: | Re: Ambiguous SEARCH | | Date: | Mon, 10 Jan 2005 00:03:15 GMT |
|
|
| Anton Ertl wrote:
> "Jeff" writes:
>
> > I know this is ambiguous,
>
> It is not ambiguous, it is clear what should happen.
No. It isn't. What should be returned given the following regular
expression:
find /\s*/ in "Hello, world!"
Also, should the match succeed if u1 == 0?
What your particular desire is may not be the result someone else
desires given the context. Perhaps from an academic standpoint you're
correct, but com'on, if someone is searching for an empty string, there
is something else wrong.
Jeff M.
--
http://www.retrobyte.org
mailto:massung@gmail.com
|
|
| | From: | Anton Ertl | | Subject: | Re: Ambiguous SEARCH | | Date: | Mon, 10 Jan 2005 17:22:36 GMT |
|
|
| "Jeff" writes:
>Anton Ertl wrote:
>
>> "Jeff" writes:
>>
>> > I know this is ambiguous,
>>
>> It is not ambiguous, it is clear what should happen.
>
>No. It isn't. What should be returned given the following regular
>expression:
>
> find /\s*/ in "Hello, world!"
That's not Forth. I don't even know what programming language it is.
I am not sure that this has any relevance for our discussion.
In any case, here's what grep does:
[a4:/tmp:8715] wc dipl.ps
6852 19371 407944 dipl.ps
[a4:/tmp:8716] grep "" dipl.ps|wc
6852 19371 407944
[a4:/tmp:8717] grep "s*" dipl.ps|wc
6852 19371 407944
>Also, should the match succeed if u1 == 0?
If u2 is 0, too, yes.
>What your particular desire is may not be the result someone else
>desires given the context. Perhaps from an academic standpoint you're
>correct, but com'on, if someone is searching for an empty string, there
>is something else wrong.
Not necessarily. It may be a perfectly useful border case for some
algorithm (e.g., think of a loop that shortens the searched-for string
until there is a match).
Anyway, I guess some people say the same thing about 0, and it would
be right in some situations; e.g., for a comparable example, there may
be something wrong if 0 is the second argument of u<. That does not
mean that 0 u< is ambiguous and that the system is free to return true
as result of 0 u<.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.complang.tuwien.ac.at/forth/ansforth/forth200x.html
|
|
| | From: | Elizabeth D. Rather | | Subject: | Re: Ambiguous SEARCH | | Date: | Sun, 9 Jan 2005 17:14:12 -0800 |
|
|
| "Anton Ertl" wrote in message
news:2005Jan9.194642@mips.complang.tuwien.ac.at...
> "Jeff" writes:
> >Ed wrote:
> >
> >> What should SEARCH return in the following instance?
> >>
> >> S" fred" HERE 0 SEARCH
> >>
> >> In Gforth and Win32Forth it returns a match while in
> >> CHForth it fails. Other forths ???
> >
> >SwiftForth fails. Looking at the first ASM line in SwiftForth shows why:
> >
> >EBX EBX TEST 0<> IF
> >
> >I know this is ambiguous,
>
> It is not ambiguous, it is clear what should happen.
Well, I don't think it's at all clear. I agree with Marcel's direct answer
to your hypothetical, but will add that this example is an example of what
ANS Forth calls an "ambiguous condition" in that a zero-length string is a
meaningless and inappropriate argument, similar to dividing by zero. It's
possible that the past or a future standards body might prescribe an
interpretation of this case, but I would personally argue against doing so.
Trying to prescribe consistent results for nonsensical situations is a
thankless chore, there are better ways to expend bandwidth.
I'm perfectly happy with SwiftForth failing to find a zero-length string. I
think that answer is far more useful to an application than claiming to have
"found" something that cannot exist.
Cheers,
Elizabeth
--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310-491-3356
5155 W. Rosecrans Ave. #1018 Fax: +1 310-978-9454
Hawthorne, CA 90250
http://www.forth.com
"Forth-based products and Services for real-time
applications since 1973."
==================================================
|
|
| | From: | Ed | | Subject: | Re: Ambiguous SEARCH | | Date: | Wed, 12 Jan 2005 14:46:57 +1100 |
|
|
|
"Elizabeth D. Rather" wrote in message
news:10u3ln2f39dlfb0@news.supernews.com...
> "Anton Ertl" wrote in message
> news:2005Jan9.194642@mips.complang.tuwien.ac.at...
> > "Jeff" writes:
> > >Ed wrote:
> > >
> > >> What should SEARCH return in the following instance?
> > >>
> > >> S" fred" HERE 0 SEARCH
> > >>
> > >> In Gforth and Win32Forth it returns a match while in
> > >> CHForth it fails. Other forths ???
> > >
> > >SwiftForth fails. Looking at the first ASM line in SwiftForth shows why:
> > >
> > >EBX EBX TEST 0<> IF
> > >
> > >I know this is ambiguous,
> >
> > It is not ambiguous, it is clear what should happen.
>
> Well, I don't think it's at all clear. I agree with Marcel's direct answer
> to your hypothetical, but will add that this example is an example of what
> ANS Forth calls an "ambiguous condition" in that a zero-length string is a
> meaningless and inappropriate argument, similar to dividing by zero.
The Standard defines which conditions are ambiguous.
Luckily it has not yet done so for zero strings :)
Who can say that a zero string is "meaningless" ? No doubt
similar things were said when mathematicians proposed the
number zero. Intuitive responses frequently prove wrong.
The real question is whether zero strings are useful to the
programmer i.e. does it provide facility?
> I'm perfectly happy with SwiftForth failing to find a zero-length string. I
> think that answer is far more useful to an application than claiming to have
> "found" something that cannot exist.
Rather than being a "meaningless" condition that one should
never test; according to Jeff, Swiftforth's SEARCH actually
takes a position (the wrong one in my view).
The benefit of SEARCH passing a zero substring is that
exactly the same code can be employed to perform two
distinct functions. For example:
SEARCH'ing a list of strings, one may retrieve only
strings which contain a certain substring or else retrieve
every string. (I used this feature to implement WORDS
with optional pattern matching)
It would be interesting to know whether string-oriented
languages make use of zero strings (?)
Ed
|
|
| | From: | Anton Ertl | | Subject: | Re: Ambiguous SEARCH | | Date: | Mon, 10 Jan 2005 17:32:37 GMT |
|
|
| "Elizabeth D. Rather" writes:
>Well, I don't think it's at all clear. I agree with Marcel's direct answer
>to your hypothetical, but will add that this example is an example of what
>ANS Forth calls an "ambiguous condition" in that a zero-length string is a
>meaningless and inappropriate argument, similar to dividing by zero. It's
>possible that the past or a future standards body might prescribe an
>interpretation of this case, but I would personally argue against doing so.
>Trying to prescribe consistent results for nonsensical situations is a
>thankless chore, there are better ways to expend bandwidth.
>
>I'm perfectly happy with SwiftForth failing to find a zero-length string. I
>think that answer is far more useful to an application than claiming to have
>"found" something that cannot exist.
Empty strings exist, and they make sense. And they are substrings of
every other string, so SEARCH must return true if you search for an
empty string.
And the appropriate comparison is with comparison operators (which
return a flag result, just like SEARCH), not with division. Do you
say that comparison with 0 is meaningless and nonsensical, and that 0
does not exist?
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.complang.tuwien.ac.at/forth/ansforth/forth200x.html
|
|
| | From: | Albert van der Horst | | Subject: | Re: Ambiguous SEARCH | | Date: | 10 Jan 2005 20:58:46 GMT |
|
|
| In article <10u3ln2f39dlfb0@news.supernews.com>,
Elizabeth D. Rather wrote:
>
>Well, I don't think it's at all clear. I agree with Marcel's direct answer
>to your hypothetical, but will add that this example is an example of what
>ANS Forth calls an "ambiguous condition" in that a zero-length string is a
>meaningless and inappropriate argument, similar to dividing by zero. It's
No it is not. Take the context of regular expressions.
When is AS*B matched? "A, followed by zero or more times S, followed by B".
i.e "" "S" "SS" "SSS" "SSSS" etc.
Try to match AB. The answer should clearly be yes, because
"A" matches, then "" matches, then "B" matches.
>Cheers,
>Elizabeth
Groetjes Albert
--
--
Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS
One man-hour to invent,
One man-week to implement,
One lawyer-year to patent.
|
|
| | From: | Marcel Hendrix | | Subject: | Re: Ambiguous SEARCH | | Date: | Sun, 09 Jan 2005 19:25:56 GMT |
|
|
| anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Ambiguous SEARCH
[..]
> Maybe something to convince you:
[..]
> E.g., if you search in "abcdefg" for "cd", the search succeeds; if you
> search in the same string only for "c", this also succeeds; and if you
> search only for "", that also succeeds.
E.g., if you search in "abcdefg" for "xz", the search fails; if you
search in the same string only for "z", this also fails; and if you
search only for "", of course that also fails.
-marcel
:-)
|
|
| | From: | Anton Ertl | | Subject: | Re: Ambiguous SEARCH | | Date: | Sun, 09 Jan 2005 19:30:16 GMT |
|
|
| mhx@iae.nl (Marcel Hendrix) writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Ambiguous SEARCH
>[..]
>> Maybe something to convince you:
>[..]
>> E.g., if you search in "abcdefg" for "cd", the search succeeds; if you
>> search in the same string only for "c", this also succeeds; and if you
>> search only for "", that also succeeds.
>
>E.g., if you search in "abcdefg" for "xz", the search fails; if you
>search in the same string only for "z", this also fails; and if you
>search only for "", of course that also fails.
Ok, another example: E.g., if you search in "abcdefg" for "cdx", the
search fails; if you search in the same string only for "cd", this
succeeds.
Show me an example where shortening the searched-for string gets you
from success to failure.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.complang.tuwien.ac.at/forth/ansforth/forth200x.html
|
|
| | From: | Marcel Hendrix | | Subject: | Re: Ambiguous SEARCH | | Date: | Mon, 10 Jan 2005 06:40:01 GMT |
|
|
| anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Ambiguous SEARCH
>> E.g., if you search in "abcdefg" for "xz", the search fails; if you
>> search in the same string only for "z", this also fails; and if you
>> search only for "", of course that also fails.
> Ok, another example: E.g., if you search in "abcdefg" for "cdx", the
> search fails; if you search in the same string only for "cd", this
> succeeds.
> Show me an example where shortening the searched-for string gets you
> from success to failure.
If you search in "cdef" for "cdefg", the search fails; if you search
in the same string only for "cdef", this succeeds.
-marcel
|
|
| | From: | Anton Ertl | | Subject: | Re: Ambiguous SEARCH | | Date: | Mon, 10 Jan 2005 08:31:37 GMT |
|
|
| mhx@iae.nl (Marcel Hendrix) writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Ambiguous SEARCH
>
>>> E.g., if you search in "abcdefg" for "xz", the search fails; if you
>>> search in the same string only for "z", this also fails; and if you
>>> search only for "", of course that also fails.
>
>> Ok, another example: E.g., if you search in "abcdefg" for "cdx", the
>> search fails; if you search in the same string only for "cd", this
>> succeeds.
>
>> Show me an example where shortening the searched-for string gets you
>> from success to failure.
>
>If you search in "cdef" for "cdefg", the search fails; if you search
>in the same string only for "cdef", this succeeds.
You have shown me another example where shortening the string gets you
from failure to success. That's not what I asked for (and you won't
find what I asked for, because the substring relation is a partial
order and therefore transitive: if a is a substring of b and b is a
substring of c then a is a substring of c).
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.complang.tuwien.ac.at/forth/ansforth/forth200x.html
|
|
| | From: | Bernd Paysan | | Subject: | Re: Ambiguous SEARCH | | Date: | Mon, 10 Jan 2005 15:28:58 +0100 |
|
|
| Anton Ertl wrote:
> You have shown me another example where shortening the string gets you
> from failure to success. That's not what I asked for (and you won't
> find what I asked for, because the substring relation is a partial
> order and therefore transitive: if a is a substring of b and b is a
> substring of c then a is a substring of c).
Anton, if this thing isn't in the ANS Forth standard, can you dig out a
paper or course work that formally describes all these string relations,
and make a RfD out of it? It's beginner CS stuff, I know I've written it
all down, but it must be on the bottom of a paper stack. It's only a page
or so.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
|
|
| | From: | Anton Ertl | | Subject: | Re: Ambiguous SEARCH | | Date: | Mon, 10 Jan 2005 18:05:15 GMT |
|
|
| Bernd Paysan writes:
>Anton Ertl wrote:
>Anton, if this thing isn't in the ANS Forth standard, can you dig out a
>paper or course work that formally describes all these string relations,
>and make a RfD out of it?
No, for the following reasons:
1) It's not my job to write all RfDs. You all can do that, too. You
can ask for my help, but if you think something is worth an RfD, go
ahead and do it.
2) IMO the '94 standard is unambiguous here, as far as the flag result
is concerned, so there is no need for an RfD (however, the standard
does not specify which match to return; it might be worthwhile to
refine that).
3) If the standard was ambiguous on this issue, then we have a
situation with no consensus. And this time around Elizabeth Rather
did not wait until after the CfV to say so.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.complang.tuwien.ac.at/forth/ansforth/forth200x.html
|
|
| | From: | rickman | | Subject: | Re: Ambiguous SEARCH | | Date: | Sun, 09 Jan 2005 21:21:01 -0500 |
|
|
| Anton Ertl wrote:
> mhx@iae.nl (Marcel Hendrix) writes:
>
>>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: Ambiguous SEARCH
>>[..]
>>
>>>Maybe something to convince you:
>>
>>[..]
>>
>>>E.g., if you search in "abcdefg" for "cd", the search succeeds; if you
>>>search in the same string only for "c", this also succeeds; and if you
>>>search only for "", that also succeeds.
>>
>>E.g., if you search in "abcdefg" for "xz", the search fails; if you
>>search in the same string only for "z", this also fails; and if you
>>search only for "", of course that also fails.
>
>
> Ok, another example: E.g., if you search in "abcdefg" for "cdx", the
> search fails; if you search in the same string only for "cd", this
> succeeds.
>
> Show me an example where shortening the searched-for string gets you
> from success to failure.
But it is not that simple. Your result may continue to be TRUE until
the length of the searched for string is zero, the address will not be
the same. Comparing the search for a zero length string to the result
of a finite length string is not very useful in any way. I think of it
a bit like the result of a division as the denominator goes to zero.
The result is valid and tends to infinity as the value goes to zero. In
reality, there is no answer. I think the result of searching for a null
string likewise is undefined and should be avoided.
In other words, it makes no sense to search for a null string.
--
Rick Collins
rick.collins@XYarius.com
Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design http://www.arius.com
4 King Ave. 301-682-7772 Voice
Frederick, MD 21701-3110 GNU tools for the ARM http://www.gnuarm.com
|
|
| | From: | Bernd Paysan | | Subject: | Re: Ambiguous SEARCH | | Date: | Mon, 10 Jan 2005 15:44:48 +0100 |
|
|
| rickman wrote:
> But it is not that simple. Your result may continue to be TRUE until
> the length of the searched for string is zero, the address will not be
> the same. Comparing the search for a zero length string to the result
> of a finite length string is not very useful in any way. I think of it
> a bit like the result of a division as the denominator goes to zero.
> The result is valid and tends to infinity as the value goes to zero. In
> reality, there is no answer. I think the result of searching for a null
> string likewise is undefined and should be avoided.
>
> In other words, it makes no sense to search for a null string.
As I wrote, the semantics on strings are pretty well defined (this is CS
introduction stuff), and the empty string is the neutral element to string
addition. Searching for 0 is like subtracting 0, not like dividing 0. If
you define string multiplications (5*"ab"="ababababab"), the division by
the empty string ("how often is '' in 'ababababab'?"), you deserve your
division by zero. String multiplication is a scalar operation, you can't do
"abc"*"xyz", or what do you suggest would be the result?
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
|
|
| | From: | rickman | | Subject: | Re: Ambiguous SEARCH | | Date: | Mon, 10 Jan 2005 12:38:09 -0500 |
|
|
| Bernd Paysan wrote:
> rickman wrote:
>
>>But it is not that simple. Your result may continue to be TRUE until
>>the length of the searched for string is zero, the address will not be
>>the same. Comparing the search for a zero length string to the result
>>of a finite length string is not very useful in any way. I think of it
>>a bit like the result of a division as the denominator goes to zero.
>>The result is valid and tends to infinity as the value goes to zero. In
>>reality, there is no answer. I think the result of searching for a null
>>string likewise is undefined and should be avoided.
>>
>>In other words, it makes no sense to search for a null string.
>
>
> As I wrote, the semantics on strings are pretty well defined (this is CS
> introduction stuff), and the empty string is the neutral element to string
> addition. Searching for 0 is like subtracting 0, not like dividing 0. If
> you define string multiplications (5*"ab"="ababababab"), the division by
> the empty string ("how often is '' in 'ababababab'?"), you deserve your
> division by zero. String multiplication is a scalar operation, you can't do
> "abc"*"xyz", or what do you suggest would be the result?
If searching for a null string is like subtracting 0, what is
subtracting a null string like?
I think analyzing a forth search function as an algebraic operation to
determine what a search for a null string should return is a bit like
asking how many angels can dance on the head of a pin. It may be an
interesting question, but no one as provided much in the showing the
practicality in an answer. It seems very obvious that a search for a
null string can be dealt with by not doing it. Is that a hard thing to
do (or not do)?
--
Rick Collins
rick.collins@XYarius.com
Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design http://www.arius.com
4 King Ave. 301-682-7772 Voice
Frederick, MD 21701-3110 GNU tools for the ARM http://www.gnuarm.com
|
|
| | From: | Bernd Paysan | | Subject: | Re: Ambiguous SEARCH | | Date: | Tue, 11 Jan 2005 12:24:17 +0100 |
|
|
| rickman wrote:
> If searching for a null string is like subtracting 0, what is
> subtracting a null string like?
I said that searching for a null string is as valid as subtracting 0, not
identical to subtracting the null string. Subtracting the null string is a
no-op, since adding the null-string is, too. Searching for a substring is
asking the question "has this sub-string been added to the string
somewhere?". And for the empty string, the answer has to be: Yes.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
|
|
| | From: | Albert van der Horst | | Subject: | Re: Ambiguous SEARCH | | Date: | 10 Jan 2005 20:48:32 GMT |
|
|
| In article <8I-dndv5n4kZIH_cRVn-hw@adelphia.com>,
rickman wrote:
>Bernd Paysan wrote:
>
>> rickman wrote:
>>
>>>But it is not that simple. Your result may continue to be TRUE until
>>>the length of the searched for string is zero, the address will not be
>>>the same. Comparing the search for a zero length string to the result
>>>of a finite length string is not very useful in any way. I think of it
>>>a bit like the result of a division as the denominator goes to zero.
>>>The result is valid and tends to infinity as the value goes to zero. In
>>>reality, there is no answer. I think the result of searching for a null
>>>string likewise is undefined and should be avoided.
>>>
>>>In other words, it makes no sense to search for a null string.
>>
>>
>> As I wrote, the semantics on strings are pretty well defined (this is CS
>> introduction stuff), and the empty string is the neutral element to string
>> addition. Searching for 0 is like subtracting 0, not like dividing 0. If
>> you define string multiplications (5*"ab"="ababababab"), the division by
>> the empty string ("how often is '' in 'ababababab'?"), you deserve your
>> division by zero. String multiplication is a scalar operation, you can't do
>> "abc"*"xyz", or what do you suggest would be the result?
>
>If searching for a null string is like subtracting 0, what is
>subtracting a null string like?
>
>I think analyzing a forth search function as an algebraic operation to
>determine what a search for a null string should return is a bit like
>asking how many angels can dance on the head of a pin. It may be an
>interesting question, but no one as provided much in the showing the
>practicality in an answer. It seems very obvious that a search for a
>null string can be dealt with by not doing it. Is that a hard thing to
>do (or not do)?
Sorry but it isn't. This is one of the small exercises i do all the time,
making accurate description of small factors such that all implementation
decision follow as a result.
SEARCH
Wrong: old fashioned description, inaccurate
(s1 s2 -- address) return the address where s2 matches in s1.
good:
For string S1 and S2 return the first POSITION such that all characters
of ``S2'' match from that position on.
The second description answers the question about an empty S2.
We all know that all green cows that can swim over the Atlantic are
very good at math too. (Meaning all characters that are in S2, have all
properties we want, because there are none.)
Next time you write a mini-specification for a word, stand back,
and try to answer the question whether it is a watertight spec.
Now apply that to search. Any watertight spec that doesn't single out
the S2-empty case, is to be interpreted as that it should match.
Too easily something like (x -- sin(x) ) is written down, but a
specification is a statement and a commitment.
Groetjes Albert
>--
>
>Rick Collins
>
>rick.collins@XYarius.com
>
>Arius - A Signal Processing Solutions Company
>Specializing in DSP and FPGA design http://www.arius.com
>4 King Ave. 301-682-7772 Voice
>Frederick, MD 21701-3110 GNU tools for the ARM http://www.gnuarm.com
--
--
Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS
One man-hour to invent,
One man-week to implement,
One lawyer-year to patent.
|
|
| | From: | rickman | | Subject: | Re: Ambiguous SEARCH | | Date: | Mon, 10 Jan 2005 20:21:17 -0500 |
|
|
| Albert van der Horst wrote:
> In article <8I-dndv5n4kZIH_cRVn-hw@adelphia.com>,
> rickman wrote:
>
>>Bernd Paysan wrote:
>>
>>
>>>rickman wrote:
>>>
>>>
>>>>But it is not that simple. Your result may continue to be TRUE until
>>>>the length of the searched for string is zero, the address will not be
>>>>the same. Comparing the search for a zero length string to the result
>>>>of a finite length string is not very useful in any way. I think of it
>>>>a bit like the result of a division as the denominator goes to zero.
>>>>The result is valid and tends to infinity as the value goes to zero. In
>>>>reality, there is no answer. I think the result of searching for a null
>>>>string likewise is undefined and should be avoided.
>>>>
>>>>In other words, it makes no sense to search for a null string.
>>>
>>>
>>>As I wrote, the semantics on strings are pretty well defined (this is CS
>>>introduction stuff), and the empty string is the neutral element to string
>>>addition. Searching for 0 is like subtracting 0, not like dividing 0. If
>>>you define string multiplications (5*"ab"="ababababab"), the division by
>>>the empty string ("how often is '' in 'ababababab'?"), you deserve your
>>>division by zero. String multiplication is a scalar operation, you can't do
>>>"abc"*"xyz", or what do you suggest would be the result?
>>
>>If searching for a null string is like subtracting 0, what is
>>subtracting a null string like?
>>
>>I think analyzing a forth search function as an algebraic operation to
>>determine what a search for a null string should return is a bit like
>>asking how many angels can dance on the head of a pin. It may be an
>>interesting question, but no one as provided much in the showing the
>>practicality in an answer. It seems very obvious that a search for a
>>null string can be dealt with by not doing it. Is that a hard thing to
>>do (or not do)?
>
>
> Sorry but it isn't. This is one of the small exercises i do all the time,
> making accurate description of small factors such that all implementation
> decision follow as a result.
> SEARCH
> Wrong: old fashioned description, inaccurate
> (s1 s2 -- address) return the address where s2 matches in s1.
>
> good:
> For string S1 and S2 return the first POSITION such that all characters
> of ``S2'' match from that position on.
>
> The second description answers the question about an empty S2.
I don't agree. If there is nothing to match, then you can not determine
that it matches, unless you simply define it that way. Your analogy to
the line below shows that pretty well. You can create an infinite set
of statements about cows that don't exist. But they are of no value. I
know that there are no cows that are good at math. So your statement is
saying nothing other than 0 = 0.
Consider the case of searching for all non-overlapping matches of string
1 in string 2. When you get a match, you get the start of the string
where the match begins. The length of the match of taken off the front
of the string and the search continues. With a null string as string 1,
the process will loop without advancing. The case of a null string is a
unique case which does not fit in with non-null strings.
> We all know that all green cows that can swim over the Atlantic are
> very good at math too. (Meaning all characters that are in S2, have all
> properties we want, because there are none.)
>
> Next time you write a mini-specification for a word, stand back,
> and try to answer the question whether it is a watertight spec.
> Now apply that to search. Any watertight spec that doesn't single out
> the S2-empty case, is to be interpreted as that it should match.
> Too easily something like (x -- sin(x) ) is written down, but a
> specification is a statement and a commitment.
But you have not really shown any value for this. That is the point I
don't get. Why does this matter? It is very easy to deal with a null
string by not searching. To make your search return a TRUE for a match
on a null string requires that you implement that as a special case.
But then I don't really care a lot about this. It just seems like a
silly thing to spend time on when there are many other issues in Forth
that need to be resolved.
--
Rick Collins
rick.collins@XYarius.com
Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design http://www.arius.com
4 King Ave. 301-682-7772 Voice
Frederick, MD 21701-3110 GNU tools for the ARM http://www.gnuarm.com
|
|
| | From: | Anton Ertl | | Subject: | Re: Ambiguous SEARCH | | Date: | Tue, 11 Jan 2005 18:17:34 GMT |
|
|
| rickman writes:
>Consider the case of searching for all non-overlapping matches of string
>1 in string 2. When you get a match, you get the start of the string
>where the match begins. The length of the match of taken off the front
>of the string and the search continues. With a null string as string 1,
>the process will loop without advancing. The case of a null string is a
>unique case which does not fit in with non-null strings.
....
>But you have not really shown any value for this. That is the point I
>don't get. Why does this matter? It is very easy to deal with a null
>string by not searching.
Why don't you apply your advice to your contrived example?
> To make your search return a TRUE for a match
>on a null string requires that you implement that as a special case.
Not at all. Looking at <41e0c34d$1@news.alphalink.com.au>, it seems
that SwiftForth special-cases the empty-string case to return FALSE
for a SEARCH for an empty string.
In contrast, here's Gforth's SEARCH:
: string-prefix? ( c-addr1 u1 c-addr2 u2 -- f ) \ gforth
tuck 2>r min 2r> str= ;
: search ( c-addr1 u1 c-addr2 u2 -- c-addr3 u3 flag ) \ string
2>r 2dup
begin
dup r@ >=
while
2dup 2r@ string-prefix? if
2swap 2drop 2r> 2drop true exit
endif
1 /string
repeat
2drop 2r> 2drop false ;
No special-casing here.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.complang.tuwien.ac.at/forth/ansforth/forth200x.html
|
|
| | From: | Bernd Paysan | | Subject: | Re: Ambiguous SEARCH | | Date: | Wed, 12 Jan 2005 10:32:40 +0100 |
|
|
| Anton Ertl wrote:
> Not at all. Looking at <41e0c34d$1@news.alphalink.com.au>, it seems
> that SwiftForth special-cases the empty-string case to return FALSE
> for a SEARCH for an empty string.
>
> In contrast, here's Gforth's SEARCH:
>
> : string-prefix? ( c-addr1 u1 c-addr2 u2 -- f ) \ gforth
> tuck 2>r min 2r> str= ;
>
> : search ( c-addr1 u1 c-addr2 u2 -- c-addr3 u3 flag ) \ string
> 2>r 2dup
> begin
> dup r@ >=
> while
> 2dup 2r@ string-prefix? if
> 2swap 2drop 2r> 2drop true exit
> endif
> 1 /string
> repeat
> 2drop 2r> 2drop false ;
>
> No special-casing here.
bigFORTH special cases the search for the empty string for efficiency
reasons. I use SCAN to find the first matching character, and then apply
COMPARE with the remaining characters. This doesn't work with empty
strings, so I have to special case them.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
|
|
| | From: | Anton Ertl | | Subject: | Re: Ambiguous SEARCH | | Date: | Mon, 10 Jan 2005 17:52:04 GMT |
|
|
| rickman writes:
>Anton Ertl wrote:
>> Show me an example where shortening the searched-for string gets you
>> from success to failure.
>
>But it is not that simple. Your result may continue to be TRUE until
>the length of the searched for string is zero, the address will not be
>the same.
One step at a time. We are still discussing the flag result.
As for the other results, consider searching in "abccde" for "cd".
This produces a match. Now shorten the searched-for string to "c".
Now you get two matches, only one of them in the same position as that
from "cd". Of course, SEARCH can only return one match, typically the
first one, which is in a different position than the one from "cd".
So you don't need to search for the empty string to get this seeming
inconsistency.
Interestingly, ANS Forth does not specify which of the matches should
be returned. I think it would make sense to specify the first one.
> Comparing the search for a zero length string to the result
>of a finite length string is not very useful in any way. I think of it
>a bit like the result of a division as the denominator goes to zero.
>The result is valid and tends to infinity as the value goes to zero. In
>reality, there is no answer.
In contrast, for the substring relation, there is an answer; it is
true. And as you shorten the string, the answer tends to true.
That's because the substring relation on strings is more like
comparison among natural numbers, not like division. And comparison
is defined for all natural numbers.
Hmm, I wonder why this thread is getting so long when the same
question produced only a three-posting thread in 1996.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.complang.tuwien.ac.at/forth/ansforth/forth200x.html
|
|
| | From: | rickman | | Subject: | Re: Ambiguous SEARCH | | Date: | Mon, 10 Jan 2005 14:30:00 -0500 |
|
|
| Anton Ertl wrote:
> rickman writes:
>
>>Anton Ertl wrote:
>>
>>>Show me an example where shortening the searched-for string gets you
>>>from success to failure.
>>
>>But it is not that simple. Your result may continue to be TRUE until
>>the length of the searched for string is zero, the address will not be
>>the same.
>
>
> One step at a time. We are still discussing the flag result.
>
> As for the other results, consider searching in "abccde" for "cd".
> This produces a match. Now shorten the searched-for string to "c".
> Now you get two matches, only one of them in the same position as that
> from "cd". Of course, SEARCH can only return one match, typically the
> first one, which is in a different position than the one from "cd".
> So you don't need to search for the empty string to get this seeming
> inconsistency.
>
> Interestingly, ANS Forth does not specify which of the matches should
> be returned. I think it would make sense to specify the first one.
>
>
>> Comparing the search for a zero length string to the result
>>of a finite length string is not very useful in any way. I think of it
>>a bit like the result of a division as the denominator goes to zero.
>>The result is valid and tends to infinity as the value goes to zero. In
>>reality, there is no answer.
>
>
> In contrast, for the substring relation, there is an answer; it is
> true. And as you shorten the string, the answer tends to true.
> That's because the substring relation on strings is more like
> comparison among natural numbers, not like division. And comparison
> is defined for all natural numbers.
The result is true only because you want to define it as true. Other
than by comparing it to other math operations, you have not shown any
basis for the result being one thing or another.
How about if you consider the search in its own right? I say this gives
you no insight and so searching for a null string should be an invalid
operation, just like searching for a string with a negative length.
If you need it to return some particular result, you can always give it
a wrapper that detects a zero length and returns zero.
If this has no practical need (no one has asked for it because it
impacted their ability to solve a problem) then why bother with it?
--
Rick Collins
rick.collins@XYarius.com
Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design http://www.arius.com
4 King Ave. 301-682-7772 Voice
Frederick, MD 21701-3110 GNU tools for the ARM http://www.gnuarm.com
|
|
| | From: | Anton Ertl | | Subject: | Re: Ambiguous SEARCH | | Date: | Tue, 11 Jan 2005 17:45:13 GMT |
|
|
| rickman writes:
>Anton Ertl wrote:
>
>> rickman writes:
>>> Comparing the search for a zero length string to the result
>>>of a finite length string is not very useful in any way. I think of it
>>>a bit like the result of a division as the denominator goes to zero.
>>>The result is valid and tends to infinity as the value goes to zero. In
>>>reality, there is no answer.
What is your justification for that?
In reality, for n/0 with n!=0 there is no answer, because division is
the inverse operation of multiplication, and there is no number m such
that m*0=n.
What is your justification for claiming that the result of SEARCH is
undefined when the searched-for string is empty? Is it the inverse
operation of anything?
>Other
>than by comparing it to other math operations, you have not shown any
>basis for the result being one thing or another.
Ok, let's look at the definition:
|17.6.1.2191 SEARCH
|STRING
|
| ( c-addr1 u1 c-addr2 u2 -- c-addr3 u3 flag )
|
|Search the string specified by c-addr1 u1 for the string specified by
|c-addr2 u2. If flag is true, a match was found at c-addr3 with u3
|characters remaining. If flag is false there was no match and c-addr3
|is c-addr1 and u3 is u1.
So the question is, is there a match, or is there not? If u2<=u3 and
the string c-addr2 u2 is equal to the string c-addr3 u2, there is a
match. Now 0<=u3 for any u3 (that's trivial), and c-addr2 0 is
string-equal to c-addr3 0 (that's also trivial, all empty strings are
equal), so with u2=0, there is a match, and therefore flag must not be
false; therefore, flag must be true (tertium non datur).
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.complang.tuwien.ac.at/forth/ansforth/forth200x.html
|
|
| | From: | Alex McDonald | | Subject: | Re: Ambiguous SEARCH | | Date: | 10 Jan 2005 10:44:47 -0800 |
|
|
| Correction: "not the beginning of the line" should have read "not the
character beginning the line"
--
Regards
Alex McDonald
|
|
| | From: | Alex McDonald | | Subject: | Re: Ambiguous SEARCH | | Date: | 10 Jan 2005 18:41:28 -0800 |
|
|
| rickman wrote:
> Albert van der Horst wrote:
===snipped
>
> But you have not really shown any value for this. That is the point
I
> don't get. Why does this matter? It is very easy to deal with a
null
> string by not searching. To make your search return a TRUE for a
match
> on a null string requires that you implement that as a special case.
You're proposing a different special case; that is, conditionally not
searching. What route would your special case take? The TRUE (match) or
the FALSE (nomatch) branch? The undefined nature has to be resolved
somehow.
S" FRED" 2DUP SEARCH (found) is the eqivalent of S" FRED" 2DUP COMPARE
(equal). What you're proposing is that HERE 0 2DUP SEARCH (not found)
and HERE 0 2DUP COMPARE (equal) disagree. So how is COMPARE to work on
null strings? Special cases again?
--
Regards
Alex McDonald
|
|
| | From: | rickman | | Subject: | Re: Ambiguous SEARCH | | Date: | Tue, 11 Jan 2005 01:15:35 -0500 |
|
|
| Alex McDonald wrote:
> rickman wrote:
>
>>Albert van der Horst wrote:
>
> ===snipped
>
>>But you have not really shown any value for this. That is the point
>
> I
>
>>don't get. Why does this matter? It is very easy to deal with a
>
> null
>
>>string by not searching. To make your search return a TRUE for a
>
> match
>
>>on a null string requires that you implement that as a special case.
>
>
> You're proposing a different special case; that is, conditionally not
> searching. What route would your special case take? The TRUE (match) or
> the FALSE (nomatch) branch? The undefined nature has to be resolved
> somehow.
>
> S" FRED" 2DUP SEARCH (found) is the eqivalent of S" FRED" 2DUP COMPARE
> (equal). What you're proposing is that HERE 0 2DUP SEARCH (not found)
> and HERE 0 2DUP COMPARE (equal) disagree. So how is COMPARE to work on
> null strings? Special cases again?
Why does there only have to be two choices? If you are looking for
substrings, changing the length as you go, you will continue to search
when the string is not found, terminate with a TRUE found when it is
found and terminate with a FALSE if your length gets to zero.
I just don't see the need to consider null strings in searching or
comparing. I can't think of an example where I would need it.
Regardless, there is not much point to going on about this. We are not
getting anywhere with it. I would rather pick your brain when I am
stumped with something new I am trying to do :)
--
Rick Collins
rick.collins@XYarius.com
Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design http://www.arius.com
4 King Ave. 301-682-7772 Voice
Frederick, MD 21701-3110 GNU tools for the ARM http://www.gnuarm.com
|
|
| | From: | Ed Beroset | | Subject: | Re: Ambiguous SEARCH | | Date: | Tue, 11 Jan 2005 12:05:21 GMT |
|
|
| rickman wrote:
> I just don't see the need to consider null strings in searching or
> comparing. I can't think of an example where I would need it.
ISO standard 9989 (the standard for the C language) explicitly covers
this case for the similar function strstr(). Why? Because the notion
that "the null string is a substring of every string" is one that is
very familiar to many who have studied computer science, and it would be
counterintuitive for the language to differ. I think that the same
reasoning would be reasonably applied here.
Ed
|
|
| | From: | Ed | | Subject: | Re: Ambiguous SEARCH | | Date: | Wed, 12 Jan 2005 15:24:11 +1100 |
|
|
|
"Ed Beroset" wrote in message
news:5iPEd.4300$C52.3530@newsread2.news.atl.earthlink.net...
> rickman wrote:
> > I just don't see the need to consider null strings in searching or
> > comparing. I can't think of an example where I would need it.
>
> ISO standard 9989 (the standard for the C language) explicitly covers
> this case for the similar function strstr(). Why? Because the notion
> that "the null string is a substring of every string" is one that is
> very familiar to many who have studied computer science, and it would be
> counterintuitive for the language to differ. I think that the same
> reasoning would be reasonably applied here.
>
> Ed
Thanks for that (and for doing the research). It seems to answer
the question once and for all.
Ed (the other one)
|
|
| | From: | rickman | | Subject: | Re: Ambiguous SEARCH | | Date: | Wed, 12 Jan 2005 01:56:46 -0500 |
|
|
| Ed Beroset wrote:
> rickman wrote:
>
>> I just don't see the need to consider null strings in searching or
>> comparing. I can't think of an example where I would need it.
>
>
> ISO standard 9989 (the standard for the C language) explicitly covers
> this case for the similar function strstr(). Why? Because the notion
> that "the null string is a substring of every string" is one that is
> very familiar to many who have studied computer science, and it would be
> counterintuitive for the language to differ. I think that the same
> reasoning would be reasonably applied here.
I'm not trying to be argumentative, but this is not an example of how or
where it would be needed. Can anyone give me a valid practical case
where not having the search for a null string return true would hose up
some solution to a problem?
If this issue is important to anyone, that is fine with me. How it is
implemented does not matter to me. I am just trying to understand why
it is important to others.
--
Rick Collins
rick.collins@XYarius.com
Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design http://www.arius.com
4 King Ave. 301-682-7772 Voice
Frederick, MD 21701-3110 GNU tools for the ARM http://www.gnuarm.com
|
|
| | From: | Ed Beroset | | Subject: | Re: Ambiguous SEARCH | | Date: | Wed, 12 Jan 2005 11:45:48 GMT |
|
|
| rickman wrote:
> Ed Beroset wrote:
>
>> rickman wrote:
>>
>>> I just don't see the need to consider null strings in searching or
>>> comparing. I can't think of an example where I would need it.
>>
>>
>>
>> ISO standard 9989 (the standard for the C language) explicitly covers
>> this case for the similar function strstr(). Why? Because the notion
>> that "the null string is a substring of every string" is one that is
>> very familiar to many who have studied computer science, and it would
>> be counterintuitive for the language to differ. I think that the same
>> reasoning would be reasonably applied here.
>
>
> I'm not trying to be argumentative, but this is not an example of how or
> where it would be needed.
No, it isn't. I just thought I'd contribute what I know, and I use C a
lot more than I use Forth. I'm sorry that you didn't find it useful.
Ed
|
|
|
