The Daily WTF: Curious Perversions in Information Technology

2008-03-12 Reply Admin

dcardani:
Everyone keeps saying it's bug free. I'm not sure I agree. I mean it does what it claims, but what it claims is very likely not intended. You could pass it a 4 Gig string of digits, and it would properly claim that it's an integer. However, you would probably not be able to extract or use that value. So in practice, it validates something you probably don't want it to.

good point!

now i challenge everyone to come up with a finite state automata that recognises only numbers less than or equal to 2147483647

bonus points if you manage it with less tan 30 states.

2008-03-12 Reply Admin

Claxon:
Beeblebrox:
vt_mruhlin:
I would have just made it a global variable.
That's not the right answer. There's a keyword I think you should meet. static, meet vt_mruhlin. vt_mruhlin, meet static. There, you've been introduced. Now it is your job to use static responsibly in your code.

And carefully, because as we know, if there's too much static you can get a shock as soon as you try to touch it!

And you're likely to blow out the gates in your MOSFETs that are part of your CMOS circuitry.

DaveK · 2008-03-12 Reply Admin

Stupidumb:
DaveK:
Stupidumb:
Is everyone here an expert in all aspects of computers?
Not since you turned up. ...
Stupidumb:
My biggest concern at work is
whether I want fries with my order. Now get back to work, bitch!
Wow, take it easy man. I wasn't angry and i wasn't yelling at you. Here are some references to help you understand what I was doing: http://dictionary.reference.com/browse/humor http://dictionary.reference.com/browse/exaggeration

Well, I thought you were up for a rumble. Here are some references to help you understand what I was doing:

http://dictionary.reference.com/browse/humor http://dictionary.reference.com/browse/exaggeration http://dictionary.reference.com/browse/Meow_meow_Matt_Bruce_meow_meow_Henrietta_Pussycat_meow_meow_Presidents_of_the_United_States_of_America_meow_Kitty?

Stupidumb:
But seriously, I wanted to know if some of you guys (especially the ones more vocal about the current story's technical stuff) actually have to employ/deal with things like FSA's and stuff in your jobs. Or maybe it's just something you guys research in spare time. I honestly don't have a problem with either.

Both. FSAs are very widely used in real apps because they are deterministic, reliable, and more easily proven correct than custom code. You don't use these theoretical concepts every single day of the week in a real world job, but the situations that they were designed to address do crop up very often, and your ability to do your job will be enhanced by having a wide variety of both simple and advanced tools at your fingertips, and the knowledge of which one to reach for in what situation. So you can get by in a real job without having a great theoretical understanding, but you can do better if you do study these heavy CS topics, and if you don't know what they are you won't know when you've run into the situation where there's one that is just right for your needs.

In that context, researching (or just playing with) these things in your spare time become part of being professional, like a carpenter sitting at home of an evening cleaning and polishing his tools so they'll perform better next time he's at work. Consider it revision, or homework; you don't have to stop just because you've graduated. It depends on how independently-motivated you are.

Stupidumb:
Please don't freak out and attack my intelligence. (It's rude and pitiful).

If only you had paid more attention in those classes you were talking about, maybe your intelligence wouldn't be so rude and pitiful!

Stupidumb:
The reason I wanted to know is that I would like to get a job that is a little more challenging than my current one. I thought that being funny Wouldn't hurt.

Heh, how wrong you were. Have you never heard of a painful joke?

Stupidumb:
misquoting DaveK:
Wow, you haven't realiZed that this is a website for computer programmers to submit WTFs?

Oh, look, you've mis-corrected what you thought was a typo based on your assumption that the entire world is exactly like America. Well done!

Stupidumb:
Also, the comment section is a great place to exchange ideas and make jokes. Though some of you like using it to insult others.

Yep, that's half the fun!

Stupidumb:
Have some class.

Thanks, don't mind if I do. <puff puff puff>

Oh, wait. You said class. My mistake!

DaveK · 2008-03-12 Reply Admin

Stupidumb:
DaveK:

Stupidumb:
My biggest concern at work is
whether I want fries with my order. Now get back to work, bitch!
You screwed that part up. I assume you wanted to insult me by implying that I worked at some fast food place.

Yes, it is indeed standard internet flame cliche #23.

Stupidumb:
Here is what you should have done:
DaveK:

Stupidumb:
"My biggest concern at work is
whether you want fries with your order." Now get back to work, bitch!

No, that's way more screwed up. You have to pay attention to the quote markers to see who said what. The way I wrote it, I'm interrupting you midsentence and finishing it for you, but I'm still talking from my POV rather than yours. The way you've wrote it, it just doesn't make sense: I see what you've done with the quote marks there, but it still looks like the guy behind the counter is telling the customer to get back to work.

dpm · 2008-03-12 Reply Admin

Paolo G:
Obviously, there had to be a reason to avoid 'strtol', 'atoi'
There's a good reason to avoid both of these: pass a string that cannot be interpreted as a number, as you get back 0, the same as if you pass "0" (or "0.0", or anything similar).

True, strtol() returns zero when invalid input is discovered. However, you can use the second argument to determine that parsing failed.

real_aardvark · 2008-03-12 Reply Admin

AVF:
I'm sorry, but that rocks. It may not be the kind of code you want in production, but from a mathematical/CS point of view, it's just cool.

Fail, fail, and fail.

Terseness (and indeed re-usability, as in lemmas) is prized by mathematicians. See where this little gem fails?

Computer science (such as it is) leans towards abstraction and separation: in this case, understanding the underlying point of state machines, and the difference between the state machine and the tokenizer. I can't believe I'm about to do this, but, here goes:

#define D 1
#define S 2
#define X 666
unsigned char lexicals[256] = {
    X, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, S, 0, 0, 0, 0, D, D, D, D, D, D, D, D, D, D, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

enum { INIT, ACCUMULATE, DONE, ERROR } STATE;
struct { STATE        orig;
         unsigned int trigger;
         void (*)     action (void);
         STATE        next;
}    ENTRY;

unsigned int accumulator = 0;
unsigned int current_token;

void init (void)
{
  accumulator = current_token - '0';
}

void buggered (void)
{
  printf ("Are you sure you want to do this, Dave?\n");
  exit (-1);
}

void accumulate (void)
{
  accumulator = 10*accumulator + current_token;
}

ENTRY Entries[] = dimwit {
  { INIT, 0, NULL, INIT },
  { INIT, S, NULL, INIT },
  { INIT, D, init, ACCUMULATE },
  { INIT, X, NULL, DONE },
  { ACCUMULATE, S, buggered, ERROR },
  { ACCUMULATE, 0, buggered, ERROR },
  { ACCUMULATE, D, accumulate, ACCUMULATE },
  { ACCUMULATE, X, NULL, DONE },
  { ERROR, 0, die, ERROR },
  { ERROR, S, die, ERROR },
  { ERROR, D, die, ERROR }
  { ERROR, X, die, ERROR },
  { NULL, 0, NULL, 0}
};

unsigned int numEntries = sizeof (Entries) / sizeof (ENTRY);

etc biteme (etc etc char** arg somewhere)
{
    // State INIT is the initial state
    STATE curState = INIT;

    // If the string is empty, then it does not contain a float
    // WAIT A MINUTE! "A Float?" Why is this comment invisible to the WTF thread?
    // Let's carry on.  Why not?
    if(arg == NULL) return false; // For a very good reason, no doubt.

    // (orig) Evaluate the fsa for the entire string 
    // Proposed alternative: use the hand-crafted and pointless state machine.
    
    unsigned int i;
    while (curState != DONE && curState != ERROR)
      {
	ENTRY* go = &Entries [0];
	int    gotcha = FALSE;
	while (!gotcha && go->orig != NULL)
	  {
	    if (go->state != curState)
	      ++go;
	    else if (go->trigger == lexicals[*arg])
	      {
                current_token = *arg;
		(*(go->action)) ();
		curState = go->next;
		++arg;
		gotcha = TRUE;
	      }
	    else
	      ++go;
	  }
      }		

    // (originally) State 3 is accepting
    // Well, no, it's not, really, because the terminal state doesn't imagine overflow.
    // The best we can hope for is that the accumulator fits into ...
    // No, Wait! These WTFs are trickier than I thought!
    // We don't need to return the result.  We don't even need to store
    // the result anywhere! All we need to do is to return a bool!
    //
    // Woo-hoo!

    return curState == DONE;
}

I haven't tested it, and I know it won't work. Mens insana in corpore insana. This is, however, more or less the approved approach -- assuming you think the thing was worth doing in the first place, which it wasn't.

Please don't make me code in C again. My head hurts, mildly.

2008-03-12 Reply Admin

fsa[1]['w'] is 0, so the new current state would be 0. In state 0, all results are 0. It is therefore stuck in state 0 until the end of the string. Since 0 is not 3, it would return false.

2008-03-12 Reply Admin

Axel R.:
Nothing like a small contest, uh?
[code] static bool isArgReal(const char *arg)

{
[color=blue]static const char fsa[14][256] = { { // State 0 0 }, { // State 1 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 2, 9, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 }, { // State 2 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }, { // State 3 -1, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, (...)
int state = 1;

// If the string is null or empty, then it does not contain a Real

if (!arg || !*arg) return false;

// Evaluate the FSA

for (; (state = fsa[state][*arg]) > 0; arg++);

return state == -1;
}

How it works that your code doesn't crush despite arrays are smaller than 256? I though that trying to access 1-length array at 231 would end up in "access denied" system error.

dpm · 2008-03-12 Reply Admin

gaja:
Axel R.:
Nothing like a small contest, uh?
static const char fsa[14][256] = {
How it works that your code doesn't crush despite arrays are smaller than 256?

No shiny prize for you, m'lad. He explicitly declares all fourteen (!!) arrays as 256 chars each. He simply isn't as explicit in filling in the initial values. I'm sure that if anyone familiar with that section of the Standard is still reading these comments, they'll explain which section guarantees that the values he's "missing" will be zero.

2008-03-13 Reply Admin

This is another example of people going though University and not learning a single thing. It accomplishes the same as (with less memory):

[code] static bool isArgUnsignedInt(const char *arg){

if(arg == NULL) return false;

for (;*arg >= '0' && *arg <= '9';arg++);
return arg == '\0';

} [/quote]

2008-03-13 Reply Admin

Flying Spaghetti Monster code..? Seriously, it's not that bad!

2008-03-13 Reply Admin

ZiggyFish:
This is another example of people going though University and not learning a single thing. It accomplishes the same as (with less memory):
 
static bool isArgUnsignedInt(const char *arg){ 

if(arg == NULL) return false; 

for (;*arg >= '0' && *arg <= '9';arg++); 
return arg == '\0'; 

}

Yeah, right, and the empty string is an unsigned, too, while "+1" is not. Moreover, according to your function, unsigned ints do not exists.

University does not look so bad, after all :-)

ZiggyFish · 2008-03-14 Reply Admin

I agree with you that empty string would be a problem, but not +1. this function is for Unsigned integers and as such +1 is signed and should be discarded. Also why should i write correct code for others to copy?

2008-03-15 Reply Admin

First year student with a question. For this code:

for(; *arg != '\0'; arg++)

    curState = fsa[curState][(unsigned char)(*arg)];

Was the for loop used instead of a while loop to save a line of code? Is this okay to do, or would it be considered WTFey? Thanks.

2008-03-15 Reply Admin

IIRC, C89 guarantees static variables will be initialized to zero if not explicitly initialized. That's why the uninitialized values will be zero.

real_aardvark · 2008-03-15 Reply Admin

clev:
First year student with a question. For this code:
for(; *arg != '\0'; arg++)
    curState = fsa[curState][(unsigned char)(*arg)];
Was the for loop used instead of a while loop to save a line of code? Is this okay to do, or would it be considered WTFey? Thanks.

One line, two lines, three lines ... damn, sudden flashback to 1980s New York.

People will complain either way.

They'll complain even more if everything after that is totally and irretrievably broken. Control structures ain't everything. Use for-loops, while-loops, list comprehensions, even goto if you want. Just get the damn thing right.

The WTF is basically everything that happened before that. You do know how to use tokens and isdigit(), don't you?

2008-03-24 Reply Admin

Actually, it's worse: ZiggyFish's code never terminates*, except in the case that arg is NULL.

well, it will terminate fatally when it tries to access memory it's not allowed to.

2008-05-22 Reply Admin

Its months late of course, but did anyone consider the possibility that the author of this code has a hardware background? Using FSA type models and state machines is of course standard in hardware design and that code looks very much like one converted from VHDL or similar. A decent VHDL compiler would make easy work of those sparse tables and produce a pretty minimal set of logic.

2008-06-24 Reply Admin

dpm:
zip:
I'm pretty confident that whatever 8 bits represent -54 will make a perfectly good unsigned char.
Casting a negative value to an unsigned type is "undefined", meaning the compiler can do anything it likes.
Why on earth do you think the concept meaningful?

Vollhorst:
202, why?
That's two. Anyone else going to make that mistake?

Yeah, yeah, yeah, how many times do we have to hear that "the compiler can format c:, the compiler can eject all PCI boards, the compiler can get up and tap-dance, etc." for this so-called undefined behavior?!?

Is it not reasonable to expect that the bit pattern used for the signed value will simply be interpreted as unsigned by most (if not all) compilers used?

Dang language lawyers!

Finite State Arg

Leave a comment on “Finite State Arg”