Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Programming Idioms

programming-idioms.org

Post reply on HN
Print view View original

51–60 of 99 posts

Re: Programming Idioms

#51

Post by Stratoscope »

pvtmert wrote: post #40
Stratoscope wrote: post #31

Earlier quoted context omitted.

That is one of the most confusing pieces of C code I have seen lately. And it fails on an empty string: I would expect it to set b to 1 for an empty string, but it sets it to 0. Of course that could easily be fixed by setting b to 1 at the top. Also, code like this should always be put inside a function that returns a value, not just written inline. Making it a function allows simpler and more understandable code too…

You do realize it returns 1 for an empty string right? I mean it doesn't have any digits in it... What about adding a check of str[0] == 0 -> return 0 Also, giving char str[] will make it char* str. Which can be null. This may cause reading a random memory location (possibly segfault or use-after-free) edit: I get the comments but empty string still contains no digits. Given the regex would be ^[0-9]+ (+ instead of *…

> You do realize it returns 1 for an empty string right? I mean it doesn't have any digits in it...

Yes, and that was deliberate on my part, as it meets my expectation of what such a function should do in this edge case.

The problem statement was "Set boolean b to true if string s contains only characters in range '0'..'9', false otherwise."

To my mind, the question "is every character in the string a digit" should be equivalent to "are there any non-digits in the string" (with the answer inverted, of course).

Returning 0 (false) for the empty string makes those questions not equivalent. It makes the empty string a special case.

Of course the real problem is that the problem is under-specified. It should call out specifically what should happen for an empty string, because as illustrated here, this is something where reasonable people may disagree.

> Also giving char str[] will make it char* str. Which can be null. This may cause reading a random memory location (possibly segfault or use-after-free)

Well yes, of course. The point of my comment wasn't to write bullet-proof library-ready code, it was only to illustrate two things: code like this should always go in a function, and the entire task can be accomplished in a single pass through the string.

Thanks for keeping me on my toes!

Re: Programming Idioms

#52

Post by ghoward »

remexre wrote: post #37
ghoward wrote: post #32

Earlier quoted context omitted.

> I’ve always found it interesting to consider the simplest possible spec you could give 100 programmers and receive no bugs in return. There is only one or two https://pubs.opengroup.org/onlinepubs/9699919799/utilities/t... and maybe https://pubs.opengroup.org/onlinepubs/9699919799/utilities/f... . Even "Hello, World!" is done wrong more often than not. An example: you should check for errors from `printf()`, as in…

Not even both of those; I thought there famously existed some way to make GNU true return non-zero. EDIT: Yep, https://github.com/coreutils/coreutils/blob/master/src/true....

Ha! So it is impossible!

Seriously, though, thank you for the link. That is good to know!

Re: Programming Idioms

#53

Post by andrepd »

foxfluff wrote: post #17
jstanley wrote: post #14

Earlier quoted context omitted.

The random idiom I got was: > Idiom #137 Check if string contains only digits > Set boolean b to true if string s contains only characters in range '0'..'9', false otherwise. char b = 0; for (int i = 0; i = '0' && s[i] I appreciate the funny assignment-and-test-and-early-break in one (although I'd hardly say it's idiomatic), but I could do without the quadratic strlen().

It's not unreasonable to assume the compiler will optimize it to a single call. Though I guess people who are capable of making that judgement won't need to look this idiom up on the internet.

But still, it will be two passes through the string when it could be only one.

Re: Programming Idioms

#54

Post by still_grokking »

josefx wrote: post #36
thethirdone wrote: post #20

Earlier quoted context omitted.

I just checked godbolt [0]. gcc only calls strlen once even with -O0. [0]: https://godbolt.org/z/j4o1915vE

For me the strlen call appears directly before loops backwards jump when set to -O0, resulting in a call every iteration as far as I can tell. However -O1 already seems to optimize it to a single call at the start of the function.

I find it every time funny that when using languages that want to give you "total control" over the execution of your code (mostly C/C++) you actually almost never know what code gets executed in the end.

It depends on the compiler, it's version, it's flags, and likely "the position of the moon".

Of course the compiler is only allowed to do transformations that the spec permits. But it's impossible for a human being to anticipate the exact outcome. It's more like: "Compiler, do something that has the same outcome as this code I show you here". The output can be than something that doesn't resemble the input even slightly!

There's obviously nothing wrong when the compiler is so smart that it sees some patterns and transforms your code into something much more efficient. Only that there's not much difference to what happens when you use a high level language. In both cases you in fact don't control the exact code that gets executed, and in both cases you rely on the smartness of your compiler to produce some efficient code, "whatever" you've written.

That's why I think it's mostly a function of the code-style how performant or efficient some language can be (to some extend of course). When you write low-level style code (even in a high level language) a smart compiler will (hopefully) create something like what you would get form writing your code in C/C++.

Re: Programming Idioms

#55

Post by foxfluff »

sokoloff wrote: post #39
foxfluff wrote: post #24

Earlier quoted context omitted.

strlen is a standard function (in a hosted environment). So it must do exactly what the standard says it does, and the standard doesn't say it has side-effects. The compiler could very well use a built-in implementation of strlen, or even omit the call entirely if it had another way to deduce its would-be return value. Object files are an implementation detail not known by the C standard.

> the standard doesn't say it has side-effects The relevant question is "does the standard say that it does not have side-effects?" (is a pure function). @skissane's sibling comment to yours provides the explanation of how the compiler can deduce that it's a pure function.

The compiler can deduce that it is a pure function using the same logic by which it can deduce it is free to replace the call with a builtin: the function is defined in the standard. Everything @skissane said is implementation details and not particularly relevant (the compiler can do the optimization without the attribute they mentioned).

I think the standard would fall apart if you read it under the assumption that anything not explicitly forbidden can happen. Instead, you should read and find out what the side effects are (and same for undefined behavior, unspecified behavior, implementation defined behavior, etcetra).

"Accessing a volatile object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment." (There are more details if you care to dig in)

Of course nothing stops you or me from making extensions to the standard, but analysing things from the perspective that some implementation might extend strlen to have visible side effects goes too far into whataboutism for my taste, unless there are real world examples to make it a relevant point.

Re: Programming Idioms

#56

Post by still_grokking »

duped wrote: post #50
still_grokking wrote: post #46

Earlier quoted context omitted.

That description doesn't apply for most programs though. * Not all programmers can understand all programs * Most programs don't describe the problem exactly * Almost no program describes the desired outcome exactly

It's a joke - the point behind it is that most of programming around specs is refining the spec until it is sufficiently well defined as a program.

It's frankly only a kind of joke.

People take it seriously, and you can hear it here and there as "argument" against proper specs.

Re: Programming Idioms

#57

Post by still_grokking »

jstanley wrote: post #47
still_grokking wrote: post #46

Earlier quoted context omitted.

That description doesn't apply for most programs though. * Not all programmers can understand all programs * Most programs don't describe the problem exactly * Almost no program describes the desired outcome exactly

I think the point is that the implementation of the program exactly describes the behaviour of the program. If you take the program as a description of what the program is supposed to do, then what it is supposed to do is pretty unambiguous! (Also debatable, for example if correct operation of the program depends on some property of its environment that can't always be relied upon.)

It's trivial to say that a program describes its behavior exactly (so it's its own spec).

But the whole point of a spec is to describe how a program should behave before writing it.

Also you usually want some verification that the program matches the spec. When the program IS the spec what do you match?

Re: Programming Idioms

#58

Post by jpxw »

still_grokking wrote: post #44
thom wrote: post #28

Surprisingly many failures of reading comprehension in the implementations here: https://programming-idioms.org/idiom/184/tomorrow I’ve always found it interesting to consider the simplest possible spec you could give 100 programmers and receive no bugs in return.

Hmm. There are more wrong implementations than correct ones as by now. The core of the problem was noted already: Obviously most people can't read. That's especially "funny" when thinking about all the fuss that is made about teaching children programming in school. They should start with teaching them reading. I don't even mean this snarky. The state of affairs is actually depressing and I would welcome it very much…

Also writing. I don’t believe that it’s possible for someone to be a clear and concise programmer unless they’re able to write their native language clearly and concisely.

This would likely require teaching students at least basic logic. This was entirely absent from my school experience.

It’s a hugely undertaught and undervalued skill, IMO. Before we start shoehorning CS into high school curriculums, we should consider laying these foundations first.

Re: Programming Idioms

#59

Post by Someone »

remexre wrote: post #37
ghoward wrote: post #32

Earlier quoted context omitted.

> I’ve always found it interesting to consider the simplest possible spec you could give 100 programmers and receive no bugs in return. There is only one or two https://pubs.opengroup.org/onlinepubs/9699919799/utilities/t... and maybe https://pubs.opengroup.org/onlinepubs/9699919799/utilities/f... . Even "Hello, World!" is done wrong more often than not. An example: you should check for errors from `printf()`, as in…

Not even both of those; I thought there famously existed some way to make GNU true return non-zero. EDIT: Yep, https://github.com/coreutils/coreutils/blob/master/src/true....

But that’s a complex program, with command-line parsing, locale usage, etc. No wonder it has bugs :-)

https://en.wikipedia.org/wiki/IEFBR14 was a one-byte program, but that had a bug, so it had to be doubled in size.

And yes, it still exists (https://www.ibm.com/docs/en/zos-basic-skills?topic=utilities...). I wouldn’t know how large it is nowadays.

Re: Programming Idioms

#60

Post by Stratoscope »

toxik wrote: post #43
Stratoscope wrote: post #33

Earlier quoted context omitted.

That is nice and simple, but it makes ten comparisons for each character in s, where only two are needed. Of course it would be a good approach if the set of characters you're testing against is not contiguous, unlike 0..9.

Good news then, it’s also linear time like the marginally faster but enormously grotesque for loop provided previously. I would take that clarity of intent a hundred times over squeezing a couple of comparisons out.

> it’s also linear time

You raise an interesting point. It got me thinking about how big-O notation has failed us in some ways: it teaches us to ignore constant factors.

In big-O, an algorithm that makes 1000 comparisons per element is no different from one that makes a single comparison per element. They are both linear time. But you can't deny that one of these will likely take 1000 times as long as the other.

Of course, like you, I favor simple and readable code over grotesque code that is hard to understand and mentally verify.

Post reply on HN