[HN Gopher] Beautiful Binary Search in D
___________________________________________________________________
Beautiful Binary Search in D
Author : alex_muscar
Score : 55 points
Date : 2023-02-18 17:16 UTC (5 hours ago)
(HTM) web link (muscar.eu)
(TXT) w3m dump (muscar.eu)
| theodpHN wrote:
| Beauty is in the eye of the beholder. While clever, this is (IMO)
| far less understandable and more error-prone than say COBOL's
| positively ancient built-in SEARCH ALL binary search statement.
| Here's an example of a 3-key binary table search from IBM's COBOL
| documentation that includes options for found and not found
| conditions. SEARCH ALL TABLE-ENTRY AT
| END PERFORM NOENTRY WHEN KEY-1 (INDX-1) = VALUE-1 AND
| KEY-2 (INDX-1) = VALUE-2 AND KEY-3 (INDX-1) =
| VALUE-3 MOVE PART-1 (INDX-1) TO OUTPUT-AREA
| END-SEARCH
|
| https://www.ibm.com/docs/en/cobol-zos/6.1?topic=all-example-...
| alex_muscar wrote:
| That's right. The Cobol version has its own beauty because it's
| built into the language. Also, this is my TIL nugget of the
| day. Thanks :)
| 2h wrote:
| Agree. This just screams of being too clever. It's OK to repeat
| things sometimes. If you DRY to the point that the code is not
| even readable, is that really an improvement?
|
| Also I physically shuddered when I saw the word template. Did
| no one learn from C++ mistakes?
| mhh__ wrote:
| > Did no one learn from C++ mistakes?
|
| D was designed by Walter Bright (who played a large role in
| inflicting C++ on the world) and Andrei Alexandrescu so you
| could say that...
| ternaryoperator wrote:
| > D was designed by Walter Bright (who played a large role
| in inflicting C++ on the world)
|
| That's a rather unfair characterization. He wrote the
| Datalight/Zortech C++ compiler. He was never--that I recall
| --a big flag-waver for C++.
| mhh__ wrote:
| His company originally was a C++ toolchain shop.
|
| Anyway, I was joking -- Walter did one of the first (if
| not the first?) "Proper" C++ compilers, so the idea of
| not learning from C++ is rather ironic.
| wood_spirit wrote:
| Can Shar's unrolling be combined with Duff's device to work on
| any size of dynamic array? And how would it perform?
| gavinray wrote:
| D is the systems language I enjoy writing the most out of C++,
| Rust, and Go.
|
| It feels a lot like a mix between C# and JS, but at the low level
| access of C++.
|
| It has a lot of unique features but the "killer feature" by far
| for me is Contract Programming and Invariants
|
| https://tour.dlang.org/tour/en/gems/contract-programming
|
| Invariants changed my life, so much so that I built a GCC plugin
| to add them to C++
|
| It used to be the case that the developer tooling wasn't very
| good, but the "code-d" VS Code plugin has matured greatly in the
| last few years and has some features you won't find even in
| bigger languages
|
| (Like the ability to colorize source code lines with GC profiling
| info or test coverage status)
|
| ---
|
| Another useful bit of info is that AddressSanitizer and tools
| like LLVM libFuzzer work with the LDC compiler
| agumonkey wrote:
| Is your gcc plugin a personal project or something you built
| for a team ? I find the idea brilliant in itself but I wonder
| if other people felt the need, and uses / enjoy this kind of
| improvements.
|
| I want to add profile/coverage info in emacs now :)
|
| D is a strange point in PL landscape, it's been here for ages,
| never took off (for some value of taking off) even though it
| seems there's a lot to like.
| pjmlp wrote:
| D has suffered from lack of corporate sponsor, and there were
| a couple of reboots trying to chase the next big thing that
| would bring more people in, this allowed other language
| ecosystems to improve their shortcomings, thus reducing the
| distance in language features.
|
| From my point of view in systems programming, experience with
| Oberon back in the day and such, I would really like that we
| would be talking more about D and less about Rust and Go, but
| unfortunately it isn't how things went.
| shrimp_emoji wrote:
| > _D has suffered from lack of corporate sponsor_
|
| But Digital Mars is a company. D:
|
| > _From my point of view in systems programming, experience
| with Oberon back in the day and such, I would really like
| that we would be talking more about D and less about Rust
| and Go, but unfortunately it isn 't how things went._
|
| As someone who has no idea what Oberon is or does sorry and
| believes that using anything other than Rust is literally
| pouring blood on your hands and de facto proscribes you in
| the future inquisitions on digital harm through software,
| why?
| tmtvl wrote:
| Oberon is the language Niklaus Wirth designed after
| Pascal and Modula.
| dataflow wrote:
| D never took off IMO because you can't abstract away a GC.
| The moment your callees rely on a GC, you have no choice but
| to have one in your program. The idea that you can avoid it
| in practice just because the language doesn't mandate it is
| therefore an illusion, and so it's not surprising at all that
| it isn't replacing C++.
| suby wrote:
| This is the logic I personally used in deciding not to use
| D.
| dataflow wrote:
| Yeah, I'm pretty sure it's the reason many C++ folks
| reject it. It's kind of ironic that having the "wrong"
| useful feature can hurt you, but that seems to be what's
| happening here. I feel like they might actually have a
| shot at solving it by literally dropping GC support, but
| it's hard to say at this point. I don't know if the
| standard library still has anything that needs a GC, but
| making sure that's not the case might be a good first
| step if they're ever interested in going in this
| direction.
| funnymony wrote:
| Conveniences like closures depend on gc
| dataflow wrote:
| C++ has had closures without a GC for over a decade now.
| pjmlp wrote:
| As syntactic sugar for how C++ functors used to be
| implemented, and they also bring their own set of issues
| when interoperating with co-routines.
| Simon_O_Rourke wrote:
| > This is the logic I personally used in deciding not to
| use D.
|
| Good call - I was unfortunate enough that I had to use it
| professionally for a few years. As comic book guy in the
| Simpsons would say "Worst language ever!".
| christophilus wrote:
| I'm interested in hearing more. Also, I'm curious what
| language you use as a your daily driver?
| keldaris wrote:
| Can you elaborate on your experience? There's a lot of
| negative D opinions from people who've barely used it
| and, for obvious self-selection reasons, a lot of
| positive ones from long term true believers. It would be
| interesting to see a negative experience from someone who
| used it extensively nonetheless.
| layer8 wrote:
| I mean, the same is true for C++. If some C++ library you
| use employs GC, you can't abstract that away either. The
| actual difference is how frequent such libraries are in the
| respective ecosystem.
| dataflow wrote:
| I basically said as much
| https://news.ycombinator.com/item?id=34850130
|
| Though, I'm not sure you could even have a precise GC for
| C++ even if you wanted to, given the way most C++ is
| written.
| masklinn wrote:
| > The actual difference is how frequent such libraries
| are in the respective ecosystem.
|
| That's a difference without a distinction: people will
| use the defaults unless they can't.
|
| So in C++ libraries will avoid GCs unless their work
| basically requires it, whereas in D they'll require it
| unless the author is constrained to a nogc requirement.
| gavinray wrote:
| I'm not sure I follow
|
| Is this about D code that interops with C/C++?
|
| You have "extern (C++)" and @nogc for that
| dataflow wrote:
| No, it's about pure D code. Some (many) people just don't
| want a GC in their program and that's why they use C++.
| If they switch to D, they'll have to put up with a GC if
| _any_ of their dependencies needs one, and the
| probability of that being the case is... high.
| mhh__ wrote:
| @nogc eliminates that risk.
|
| The GC also doesn't run if you don't call it so
| mitigating it's downsides while keeping the good aspects
| isn't all that hard.
| dataflow wrote:
| You disable GC for the whole program? And what do you do
| when one of your dependencies relies on it? Just live
| with a memory leak?
|
| Bear in mind you're simply not going to convince anti-GC
| folks that you can have the "good aspects" of a GC
| without the bad ones, and they're the folks you're trying
| to market to. To many C++ programmers the only good GC is
| one that is absent. You can tell them they're wrong all
| you want, but regardless of who's right, it's always been
| a losing battle.
| mhh__ wrote:
| It won't compile.
|
| You can also make it so it will compile but won't collect
| unless you ask it to explicitly.
|
| We don't exclusively market to C++ developers. D replaced
| PHP and Java for quite a few D users.
| dataflow wrote:
| It won't compile, and... how is that a solution? You've
| basically told some users they can't use your language in
| that case. That's problem solved?
|
| If you see PHP and Java replacement as taking off, that's
| awesome. I was addressing those who want to see it
| replace C++.
| mhh__ wrote:
| The express purpose of the @nogc attribute is to enforce
| that code under it's influence doesn't use the GC.
|
| There is lots of @nogc code available to depend upon
| dataflow wrote:
| > There is lots of @nogc code available to depend upon
|
| That's not sufficient here. You can literally have a
| billion @nogc libraries, and even if there was one single
| GC-requiring library that many people want to use, the
| problem would be still there.
|
| The only way to make this work is to ensure _all of the
| libraries most people want to use_ work fine without a GC
| (or have @nogc alternatives that people would actually
| want to use). While not theoretically impossible,
| practically speaking, that 's incredibly hard to pull off
| when you have a shiny GC sitting there.
| dymk wrote:
| In practice, "lots" isn't good enough. The whole
| ecosystem should work, not just lots.
| mhh__ wrote:
| In practice (I.e. actual practice that pays my rent) it's
| been good enough for me
| dymk wrote:
| Then why did D get lapped by Rust if @nogc is good enough
| and the ecosystem is good enough?
|
| If the answer is along the lines of "corporate backing",
| why did Rust get corporate backing and D didn't?
| mhh__ wrote:
| Rust did memory safety better than D did, which was a
| very attractive prospect and then Rust was also lucky
| enough to get a following of people who very noisy about
| it.
|
| Also in a world where JavaScript (excel, even) is
| dominant let's not ascribe these things to purely
| rational factors.
| gavinray wrote:
| Aye, you can turn off GC entirely, for the whole program
|
| There's even a mode of D that operates this way by
| default, "-betterC" meant to be a C replacement
|
| The GC really is an entirety opt-in component.
|
| I'd encourage you/other folks to give D an honest try,
| you might be surprised
| dataflow wrote:
| You're not understanding my point unfortunately. I never
| said you can't turn it off. I said if you do, and any of
| your dependencies expect it to be on, then you have a
| problem. (Yes, I have tried D. That's how I know this.)
| mhh__ wrote:
| If you actually turn it off (as in GC.disable()) they
| won't know either way, it's just a memory allocator to
| them.
| gavinray wrote:
| Ohhh, fair enough, yeah I see what you're saying.
|
| Yeah you're boned in that case I think and that's a real
| problem that can pop up if you want full @nogc
|
| EDIT: Maybe not based on Max's comment
|
| D-Plug (Audio FX plugins) is one example of having to
| build up a dependency stack of @nogc compatible deps, a
| lot of that is in-house stuff.
|
| Not impossible but it's a commitment, at which point you
| may as well use something else unless you REALLY want to
| use D, for sure.
| dataflow wrote:
| > a lot of that is in-house stuff.
|
| That's exactly the issue. Having to reinvent every wheel
| you need just isn't a selling point.
| gavinray wrote:
| It was a small personal project, I posted about it here some
| months ago fwiw:
|
| https://news.ycombinator.com/item?id=34211482
|
| D has no (FAANG) corporate sponsor and it does all things
| well/has no particular speciality, these two things make it
| hard to compete with marketing of other languages I think
|
| There's a small but dedicated and active community
| agumonkey wrote:
| > does all things well
|
| a great feature IMO, helps communication in large teams I
| believe (in the imaginary world where teams use D :)
|
| thanks for the link,
|
| have the best day
| gavinray wrote:
| I mean to say it's sort of a solid general purpose
| language/jack of all trades, with no particular
| speciality or thing it's deficient at
| mhh__ wrote:
| This world is not imaginary
| [deleted]
| skocznymroczny wrote:
| Unless I am missing something, you can just use .length on a
| static array: int[5] a = [1,2,3,4,5];
| writeln(a.length); // 5
| alex_muscar wrote:
| Someone on the D subreddit pointed that out as well. I didn't
| know it was available at compile time. I'll update the post.
| Thanks.
| smcl wrote:
| Is that available at compile time, though?
| mhh__ wrote:
| Yes
| [deleted]
| Kukumber wrote:
| D is a refreshing language in the sea of "alternative to C
| languages", they didn't reinvent the syntax, so if you come from
| C, using D will feel very natural and at home! (and you'll be
| protected from most unsafe/ub quirks of C)
|
| When it comes to metaprogramming, it's excellent, but it is a
| double edged sword, it can be useful, but if abused it'll tank
| your build speed, so one must find a proper balance to avoid pain
| later
|
| One of the few languages that offers its own backend! (LLVM/GCC
| backends are also available)
|
| I love this level of independence, a real labor of love, one of
| the best better C, i'd even say this is the evolution C needed
| alex_muscar wrote:
| Where I use D's metaprogramming capabilities to generate a binary
| search function using Shar's algorithm.
| kazinator wrote:
| Reminds me of https://en.wikipedia.org/wiki/Successive-
| approximation_ADC
___________________________________________________________________
(page generated 2023-02-18 23:01 UTC)