Re: Challenge: tightest code to find-replace a string

From	Keith Thompson <kst-u@mib.org>
Newsgroups	comp.lang.c
Subject	Re: Challenge: tightest code to find-replace a string
Date	2014-06-09 11:25 -0700
Organization	None to speak of
Message-ID	<lnppiilz3y.fsf@nuthaus.mib.org> (permalink)
References	(3 earlier) <06565dc2-0168-425d-b32e-8db5d93e2a4d@googlegroups.com> <lnbnu3nio9.fsf@nuthaus.mib.org> <2f848f76-4008-414d-bf53-ace7ed92ec52@googlegroups.com> <lny4x6m5y4.fsf@nuthaus.mib.org> <1b3440e4-ede4-41dd-9fb9-9f083bc0c057@googlegroups.com>

Show all headers | View raw

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> On Monday, June 9, 2014 4:57:23 PM UTC+1, Keith Thompson wrote:
>> Are you perhaps assuming that it doesn't matter because 
>> search-and-replace is performed interactively, and therefore the
>> user can immediately see the results?  Are you familiar with sed?
>> 
> I'm familiar with the name but I've never used it.

It's a non-interactive tool, common (in fact, nearly universal) on
UNIX-like systems.  The name is derived from the phrase "stream editor".
It's commonly used in scripts (i.e., programs written in the language
implemented by a shell).

> If you're implementing see presumably you have to implement the quirks
> as well, to avoid breaking existing scripts.
> But if "search and replace" is called on overlapping input, then
> almost always it indicates that the caller didn't expect the pattern
> to be applied to that situation. There's no ideal behaviour with a
> "pattern / replacement" interface. Probably you should pass an extra
> parameter in to indicate whether to be greedy, non-greedy, or flag up
> an error.

I've been using sed for decades.  As far as I know, it has no flag to
indicate different semantics for overlapping input, and I've never
encountered a need for such a flag.

The POSIX specification is here:
http://pubs.opengroup.org/onlinepubs/9699919799/utilities/sed.html

The relevant command in this context would be:

    sed 's/foo/bar/g'

In the documentation, a BRE is a "Basic Regular Expression"; in this
case, we're considering a simple string.  The 'g' suffix causes it to
replace all non-overlapping instances of "foo"; by default it only
replaces the first on each line.

An example:

    $ echo banana | sed 's/ana/Anana/g'
    bAnanana

As far as I can tell, no other output would be consistent with the
specification (there are two occurrences of "ana", but they overlap so
only the first is replaced) -- and I would consider any other output
unacceptable.

Though I can't think of a concrete example, it's likely I've used sed on
text with overlapping occurrences of a substitution pattern and relied
on the way it behaves.

The problem you perceive with overlapping input is not a problem
in practice.  There is no real ambiguity in the behavior, and
therefore no need for extra flags to resolve it.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

Thread

Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-06 00:08 -0400
  Re: Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-06 04:34 -0400
    Re: Challenge: tightest code to find-replace a string Jorgen Grahn <grahn+nntp@snipabacken.se> - 2014-06-06 10:04 +0000
    Re: Challenge: tightest code to find-replace a string Mark Storkamp <mstorkamp@yahoo.com> - 2014-06-06 07:27 -0500
    Re: Challenge: tightest code to find-replace a string Robert Wessel <robertwessel2@yahoo.com> - 2014-06-06 11:55 -0500
      Re: Challenge: tightest code to find-replace a string Johannes Bauer <dfnsonfsduifb@gmx.de> - 2014-06-06 20:47 +0200
  Re: Challenge: tightest code to find-replace a string Ike Naar <ike@iceland.freeshell.org> - 2014-06-06 06:05 +0000
    Re: Challenge: tightest code to find-replace a string Noob <root@127.0.0.1> - 2014-06-06 10:17 +0200
      Re: Challenge: tightest code to find-replace a string Ian Collins <ian-news@hotmail.com> - 2014-06-08 21:20 +1200
  Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-06 14:41 +0100
    Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-06 16:29 +0100
      Re: Challenge: tightest code to find-replace a string Jorgen Grahn <grahn+nntp@snipabacken.se> - 2014-06-06 17:27 +0000
      Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-06 22:16 +0100
        Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-06 23:26 +0100
          Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-06 23:38 +0100
    Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-06 08:31 -0700
      Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-06 22:12 +0100
    Re: Challenge: tightest code to find-replace a string Chad <cdalten@gmail.com> - 2014-06-07 12:19 -0700
      Re: Challenge: tightest code to find-replace a string Chad <cdalten@gmail.com> - 2014-06-07 13:38 -0700
        Re: Challenge: tightest code to find-replace a string raltbos@xs4all.nl (Richard Bos) - 2014-06-08 10:34 +0000
    Re: Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-07 18:30 -0400
      Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-08 13:09 +0100
        Re: Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-08 12:42 -0400
          Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-09 01:44 +0100
            Re: Challenge: tightest code to find-replace a string Siri Crews <chine.bleu@yahoo.com> - 2014-06-08 22:15 -0700
              Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-09 12:58 +0100
            Re: Challenge: tightest code to find-replace a string Ike Naar <ike@iceland.freeshell.org> - 2014-06-09 06:40 +0000
              Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-09 13:04 +0100
                Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-09 15:27 +0100
                Re: Challenge: tightest code to find-replace a string Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-06-09 16:22 +0100
                Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-09 18:06 +0100
                Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-09 22:38 +0100
      Re: Challenge: tightest code to find-replace a string Tim Rentsch <txr@alumni.caltech.edu> - 2014-06-10 00:57 -0700
  Re: Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-07 17:36 -0400
    Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-08 09:57 +0100
      Re: Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-08 12:43 -0400
        Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-08 15:27 -0700
        Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-09 10:02 +0100
          Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-09 08:03 -0700
    Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-08 04:43 -0700
      Re: Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-08 13:26 -0400
      Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-08 15:24 -0700
        Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-09 08:39 -0700
          Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-09 08:57 -0700
            Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-09 09:52 -0700
              Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-09 11:25 -0700
                Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-09 13:42 -0700
                Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-09 15:02 -0700
                Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-09 16:04 -0700
                Re: Challenge: tightest code to find-replace a string raltbos@xs4all.nl (Richard Bos) - 2014-06-10 10:23 +0000
          Re: Challenge: tightest code to find-replace a string raltbos@xs4all.nl (Richard Bos) - 2014-06-09 16:57 +0000
            Re: Challenge: tightest code to find-replace a string raltbos@xs4all.nl (Richard Bos) - 2014-06-10 10:06 +0000
  Re: Challenge: tightest code to find-replace a string "Chris M. Thomasson" <no@spam.invalid> - 2014-06-09 12:43 -0700
    Re: Challenge: tightest code to find-replace a string "Chris M. Thomasson" <no@spam.invalid> - 2014-06-09 14:32 -0700
      Re: Challenge: tightest code to find-replace a string "Chris M. Thomasson" <no@spam.invalid> - 2014-06-09 16:09 -0700
      Re: Challenge: tightest code to find-replace a string James Kuyper <jameskuyper@verizon.net> - 2014-06-09 21:35 -0400
    Re: Challenge: tightest code to find-replace a string DFS <nospam@dfs.com> - 2014-06-10 09:39 -0400
      Re: Challenge: tightest code to find-replace a string James Kuyper <jameskuyper@verizon.net> - 2014-06-10 11:26 -0400
      Re: Challenge: tightest code to find-replace a string raltbos@xs4all.nl (Richard Bos) - 2014-06-11 16:16 +0000
      Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-11 09:25 -0700
        Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-11 13:48 -0700
          Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-11 22:04 +0100
            Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-11 14:59 -0700
          Re: Challenge: tightest code to find-replace a string Ike Naar <ike@iceland.freeshell.org> - 2014-06-11 21:35 +0000
          Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-11 14:56 -0700
            Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-12 02:24 -0700
              Re: Challenge: tightest code to find-replace a string Keith Thompson <kst-u@mib.org> - 2014-06-12 09:09 -0700
                Re: Challenge: tightest code to find-replace a string Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-06-13 00:40 -0700
                Re: Challenge: tightest code to find-replace a string "BartC" <bc@freeuk.com> - 2014-06-13 09:17 +0100
  Re: Challenge: tightest code to find-replace a string "Chris M. Thomasson" <no@spam.invalid> - 2014-06-14 13:12 -0700

csiph-web