substring finding problem!

[blmblm]

[ snip ]

That manages to be rather snide, in my view.

It's a fair cop.

It would have been an improvement. But there are plenty of words such
as "correct" which have zero personal connotation.

But that wouldn't express my intended meaning.

[ snip ]

Whoa. I'm not sure. "Science" is about possibility as well as fact.

Well, my thinking is that it's not possible to write correct code --
indeed, the notion of "correct code" is meaningless -- if you don't
know what its output should be for any arbitrary input. Trying to
settle the matter by experiment .... I've never been entirely
comfortable with the idea of computer science as science in the
first place -- I mean, the thing being observed is not external
to the process as it is with the "real" sciences, but somehow
a creation of the same process used to do the observing. (I'm not
explaining that very well but perhaps the idea comes across.)

I guess I *can* imagine situations in which one would want to
try out different possibilities, particularly with regard to
user interface. Or, now that I think about it, I suppose if one
is simulating some sort of physical process one might want to
try different algorithms/approaches and find out which one gives
results that fit best with the thing being simulated. But to me
that seems vaguely unsound -- "we don't really know why this works,

However, I do think that for the same reason your notion of "concat"
is cool since it is independent of direction, I think that a "flat" or
one-time application of "replace" is one of those phony notions that
only seem useful. The basic notion is not replace once, it is replace
until no change, as in macro replacement. I think we can prove that
there's no instance of a replace that always changes the string when
applied.

Let us call an implementation of replace(master, target, replacement)
"kewl" when and only when it is "independent of left to right or right
to left order". I claim that the only form of replace that is "kewl"
is nondeterministic. To simulate it you'd have to apply the
replacement rule randomly. It would sometimes return bonona, and other
times it would return banono.

(Chorus of you say tomayto I say tomahto).

This is an interesting NEGATIVE point. It means that there are
probably bugs out there.

It's a CORRECT result without being, of course, a reasonable
SPECIFICATION for real code. But that don't mean it's not useful.
Turing's Halting Problem is True, and created software, but it's not a
spec.

How can a problem be True?

[ snip ]

For example, Peter didn't ask himself
what would be the case if %s was in the substitution string and would
probably consider the question so quirky as to make it safe to gravely
infer that the asker of the question is a nutbar, and to Call
Security.

No, he didn't ask that question *BECAUSE HE CONTROLLED THE INPUT*
and knew that it would not contain strings for which his approach
would not work.

[ snip ]

 

[Ben Bacarisse]

Oh my! I sure didn't spot that one. (So, what *was* that line
supposed to accomplish?)

You were right: it was *intended* to multiply by ten. Maybe I should
have said "yes" rather than "no" Presumably it should have been
(i << 3) + i + i.

<snip>

 

[Seebs]

As I understand things, based on descriptions I've read here of how
people come to be on the committee responsible for the C standard(s),
the same critique could be applied to any member of said committee --
anyone who pays the appropriate dues can attend meetings. (Perhaps
someone can confirm this, or correct me.)

That seems to be correct. In fact, I think it is probably possible
to attend such meetings without paying dues. I think a fair number of
people came to meetings to make presentations, without actually being
members per se.

The focus is on getting technical experts into place to discuss C, not
on arguing about qualifications. The dues are there because the standards
bodies are funded in no small part by dues. (I actually think it's a bit
of a rip-off that they charge us dues AND charge for the standards, but I
think the C committee is unusual in not really using any of the support
infrastructure.)

-s

 

[Seebs]

No, he didn't ask that question *BECAUSE HE CONTROLLED THE INPUT*
and knew that it would not contain strings for which his approach
would not work.

Exactly. The original offhand remark about this was referring to a program
which had exactly two strings, both known at compile time, into which a single
value not knowable until runtime must be interpolated. Both of the strings
were written specifically to work with that algorithm. It was not a general
solution to anything; I just liked the expressiveness of the snprintf loop.

(If you want to see bad performance, do it all with strcat!)

-s

 

[blmblm]

You might well think so;

I did and I do. However ....

however the thought that the lengths
should be the same presupposes that there are no overlaps. Here
is an issue: If you view the string sequentially then there is
only one substring in the overlap. Either the string decomposes
into <b> <ana> <na> or <ban> <ana> depending on the direction of
scan. However choosing a direction is an arbitrary asymetric
operation. The consistent way to view the string is
holistically, noting each occurrence of the substring. When we
do this the variation due to the choice of direction vanishes.

Yes the length of bxnoxno is greater than that of banana; that is
as it should be.

I don't find this very compelling, but I guess I can see how someone
else might.

Yes. So?

Well, but replacing "ana" with "xno" gives a longer string than
replacing "ana" with "xno", which to me seems -- weird in some way.
Maybe we have to agree to disagree here.

There are probably contexts in which some of the other choices
make sense. I'm just cataloging alternatives.

There was a study sometime in the last millennium in which the
authors were studying how software designers tackled problems.
They concluded that the better designers saw more alternatives
when they tackled a problem. Thus Joe Klutz only thought of one
or two alternatives and latched onto one immediately. On the
other hand Sam Slick saw a dozen or more ways to tackle a problem
and thought about the merits of each before choosing a method.

I'm not sure of the merits of the study but the conclusion makes
sense to me.

To me as well -- and I speak as someone who is not especially good
at that "thinking outside the box" thing. As perhaps I'm making
clear here. :-( or !

 

[Seebs]

The magic words do not protect us against the malignancy of
unstated presuppositions. In this problem an unstated assumption
is that the string should be scanned left to right. Behind that
is an unstated assumption that direction of scan doesn't matter;
the results will be the same.

I had the first assumption but not the second, probably for the same
reason that I'd expect strstr() to scan left-to-right.

It might be interesting to see how easy or hard it would be to
adapt the various replace_string() implementations to scan
right-to-left.

-s

 

[spinoza1111]

[ snip ]

That manages to be rather snide, in my view.

It's a fair cop.  

It would have been an improvement. But there are plenty of words such
as "correct" which have zero personal connotation.  

But that wouldn't express my intended meaning.

[ snip ]

Whoa. I'm not sure. "Science" is about possibility as well as fact.

Well, my thinking is that it's not possible to write correct code --
indeed, the notion of "correct code" is meaningless -- if you don't
know what its output should be for any arbitrary input.  Trying to
settle the matter by experiment ....  I've never been entirely
comfortable with the idea of computer science as science in the
first place -- I mean, the thing being observed is not external
to the process as it is with the "real" sciences, but somehow
a creation of the same process used to do the observing.  (I'm not
explaining that very well but perhaps the idea comes across.)

It does not.

I guess I *can* imagine situations in which one would want to
try out different possibilities, particularly with regard to
user interface.  Or, now that I think about it, I suppose if one
is simulating some sort of physical process one might want to
try different algorithms/approaches and find out which one gives
results that fit best with the thing being simulated.  But to me
that seems vaguely unsound -- "we don't really know why this works,



You've lost me here.  <shrug>

I don't know why, since nondeterministic algorithms are useful,
because they are generalizations, as in the case of automata, of
deterministic algorithms.

How can a problem be True?

Because Turing's negative result was proven to be true, and it allowed
computer science to avoid being alchemy, the search for an impossible
program that could determine whether any other program halted.

[ snip ]

For example, Peter didn't ask himself
what would be the case if %s was in the substitution string and would
probably consider the question so quirky as to make it safe to gravely
infer that the asker of the question is a nutbar, and to Call
Security.

No, he didn't ask that question *BECAUSE HE CONTROLLED THE INPUT*
and knew that it would not contain strings for which his approach
would not work.

We're not interested in this kind of code. We'd rather see a buggy
solution from Schildt that we can start with because Schildt's
examples don't control the input. Peter's submissions have been vanity
code to demonstrate that he's qualified (which he is not), but he uses
a programming form of the logical fallacy of "definition against
disproof" when he submits something like his %s farce which only works
if he "controls the input".

[ snip ]

 

[spinoza1111]

On Feb 26, 3:39 am, Seebs <[email protected]> wrote:

[ snip ]

Something is Wrong, all right. It's that you shit on people and pay
your way onto standards boards without any qualifications that are
independently verifiable of whatever makes your current employer a
quick buck.

As I understand things, based on descriptions I've read here of how
people come to be on the committee responsible for the C standard(s),
the same critique could be applied to any member of said committee --
anyone who pays the appropriate dues can attend meetings.  (Perhaps
someone can confirm this, or correct me.)

The problem wasn't that Dweebach paid. It was that it now appears that
commencing with the Schildt canard and his failure to take or complete
any computer science classes, he used unethical practices to make
himself out to be something he was not. If he can submit code here as
bad as his examples have been, code which demonstrates that the
failure to take classes was not compensated for by insight and craft,
my inference is that he's chosen to advance himself by paying his way
into meetings where he does not belong and, worse, the politics of
personal destruction.

[ snip ]

 

[blmblm]

On 6 Mar 2010 18:56:30 GMT, (e-mail address removed)
<[email protected]> wrote:

[snip]


To me as well -- and I speak as someone who is not especially good
at that "thinking outside the box" thing. As perhaps I'm making
clear here. :-( or !

One of the things that I was getting at in my little foray into
alternatives is that when we are presented with a problem there
are different ways of interpreting what it means and how to solve
it.

One all too common approach towards solving problems is to jump
right in with whatever algorithm or approach comes to mind. The
substring replacement problem and the various attempted solutions
are a good example.

First of all some people made several passes at the problem,
publishing a sequence of faulty solutions. Why is that? One
reason is the commonness of what I call the hack, slash, and burn
approach to programming. Picture a man in a jungle armed with a
machete hacking away as he heads for a destination and you have
the sense of it.

Hack, slash, and burn is not as bad as it sounds - quite often it
works. Simply proceeding towards a solution can be all that one
need do. And, of course, one can make a real mess.

Yes, there's a point at which I sometimes say to my students
"step away from the keyboard" .... Or "think first, THEN code."

Now, as I am confident you know, there are simple intellectual
technologies that eliminate most of the hack, slash, and burn
mess. I need only mention the magic words, preconditions,
postconditions, and invariants.

*Oh* yes. If you read my attempt at a (semi)formal specification
for this problem, weeks ago, you might guess that I find this kind of
approach attractive, even though I admit that I've been known to
break my own rule about thinking first.

The magic words do not protect us against the malignancy of
unstated presuppositions. In this problem an unstated assumption
is that the string should be scanned left to right. Behind that
is an unstated assumption that direction of scan doesn't matter;
the results will be the same. Behind that there is the
assumption that using a holistic decomposition is equivalent to a
linear scan.

I was more or less with you up to here, but I'm not following
this sentence.

As can be seen, the assumptions hold if there are
no overlaps and they break down if there are.

What I would say is that if there are overlaps then there are
multiple "solutions" that might be considered correct, so one
needs to be careful to define which one is wanted.

 

[blmblm]

[ snip ]

It does not.

I'm not sure which part isn't clear ....

One point I was trying to make was about whether "correct" has
any meaning in the absence of a formal specification. I think it
does not, though perhaps there are other criteria that are sometimes
more appropriate for evaluating programs, as mentioned in my earlier
post (quoted below).

The other point was about whether it even makes sense to regard
CS as a science, and I have mixed feelings about that: There
are some things one does in CS (programming/debugging is the
example that comes to my mind) in which the classical scientific
method (as I understand it) is useful. However, with the natural
sciences, the object of study is external to the study in a way
that I think is not the case in CS. I don't know how to say it

I don't know why, since nondeterministic algorithms are useful,
because they are generalizations, as in the case of automata, of
deterministic algorithms.

Still lost. Is this particular application of nondeterminism
useful?

[ snip ]

Because Turing's negative result was proven to be true, and it allowed
computer science to avoid being alchemy, the search for an impossible
program that could determine whether any other program halted.

I was being nitpicky about usage -- it's not the *problem* that's
true, in my usage (of "true"), but the claim (backed up by a proof)
that it has no solution. The *problem* can be interesting, or
meaningful, or deep, or .... But "true", no, not unless "true"
means something -- "rather different from what it means in STEM
fields" is the closest I can come to expressing my meaning.

[ snip ]