[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Round 3 discussion & open issues
In article <199911220210.VAA04597@xxxxxxxxxxxxxxxxxx>,
>On reflection, I can't think of cases where people are really going to
>be dying to use CAPITALIZE-STRING[!]. Should I bag it? Eric says yes.
>I am leaning that way. Further opinions?
I think that you should remove it.
>OK, backwards compatibility takes this round. STRING-FOR-EACH is
>left-to-right. How about STRING-DO-EACH for the variant that doesn't specify
Do we really need such procedure?
>I could go with STRING-EMPTY? or STRING-NULL?. I'll stay with STRING-NULL?
>for the tiny tie-breaker reason that it's one column shorter. If I get more
>support for STRING-EMPTY?, I'll make the change. For now, I'll leave things
I think STRING-EMPTY? is better.
> From: d96-mst@xxxxxxxx (Mikael Ståldal)
> I think that the KMP searching procedures should be generalized to
> allow for other algorithms than KMP. But only to algorithms that have
> the same properties as KMP, i.e. scanning a stream without
> backtracking. This excludes Boyer-Moore, but allows for some recent
> algorithms that are said to be faster than KMP.
>Here's the price of admission. Someone has to
> - Send me working B-M Scheme code, under public domain, GPL,
> Berkeley-style license, something along these lines.
> - Explain in the comments or the email how B-M works, so I
> can understand the code.
>Then I'll do it. I'll humbly admit: I originally considered what you propose,
>but really don't know beans about string-search algorithms, besides KMP. So I
>didn't do it.
I don't think it's nessesary to include anything else than KMP in the
reference implementation. But the interface should allow other
implementations to use other algorithms. BTW, Boyer-Moore cannot be use
here since it doesn't process the search text strictly sequencially.
>There are some problems with this spec. The search-step function is an
>inner-loop kind of utility. That's why I made people pass in the string
>explicitly with KMP-STEP -- you don't have to unpack it from some record
But as I said, some algorithms doesn't need the pattern.
>and you can win better if you integrate/beta-substitute KMP-STEP.
What is beta-substitution?
>In spite of these tactical issues, your larger point is an excellent one. So
>I'll tackle this generalisation, if I can -- but not until I see Boyer-Moore.
I really don't see how this issue is related to Boyer-Moore.
What about this:
make-search-object c= s [start end] -> opaque "search object"
Returns an opaque "search object" that can be used to search
for S in a stream/string. The search object includes S itself
if nessesary (nessesary for KMP, but not for some other algorithms).
search-string search-object c= s [start end] -> bool or integer
Search the string S using the search object, returning the index where
the pattern is found or #f if it's not found.
search-stream search-object c= char-getter eos? -> bool
Search a stream of characters using the search object,
returning #t if the pattern could be found, #f otherwise.
char-getter is a procedure that returns the next char from the stream,
eos? is a predicate that indicate that the end of stream has been
reached. If the pattern is found, no more character after the pattern
Then all looping is encapsulated and can be properly optimized.
The Boyer-Moore algorithm is NOT suited for this, but can be used in
the STRING-CONTAINS procedure.