Beautiful Binary Search in D | Hacker News Reader

Beautiful Binary Search in D

muscar.eu

72 pointsalex_muscar59 comments

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-...

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?

> 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...

> 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++.

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.

> Also I physically shuddered when I saw the word template. Did no one learn from C++ mistakes?

While we might disagree on a lot of semantical things on this, I'd argue that D very much learned from those mistakes. There's a strong argument for D's templates to be "templates done right" (which C++'s most certainly aren't).

So I encourage you to read more into this topic. To me, this question seems just about as uninformed as someone complaining about a LISP tutorial on macros, asking "did no one learn from the mistake that is the C preprocessor?".

If/where there are other models better suited for metaprogramming would be another (interesting) discussion (full of tradeoffs, I'm sure), but the notion of proper (hygienic?) templates not being adequate anywhere can certainly not be inferred from C++'s implementation alone.

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 :)

Where I use D's metaprogramming capabilities to generate a binary search function using Shar's algorithm.

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

D isn't a good substitute for C due to its garbage collector.

Yes, people always chime in about how you can disable D's garbage collector, but then you're stuck with an awkward language that lacks support for basic things like exceptions, closures, strings, slices, and a host of other features not to mention pretty much any third party library.

If you are willing to accept a GC then D might be a good choice, if you find it fun then by all means go for it, but it's no longer so clear cut at that point given the wealth of GC'd programming languages available.

That's 100% bullshit

You can ignore the GC or totally suppress it with @nogc or even not even link it with -betterC flag

Having the GC optional is nice since you no longer need to use a scripting language to do your cli tools or utilities, it's there and well integrated

If you are a proper developer who care about speed and fast code, you'll want to develop your own STL anyways, just like C/C++ are already doing, just like Rust people are also doing to get faster compile speed, D gives C/C++ interop as well as full C11 compiler

So it's the perfect evolution of C, since it can compile and consume its ecosystem

You can even consume python and rust libraries, wgpu works great with D

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

Is that available at compile time, though?

Yes

Oh neat, I'm still a dlang noob and only used it in Crafting Interpreters :)

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.

Reminds me of https://en.wikipedia.org/wiki/Successive-approximation_ADC

Can Shar’s unrolling be combined with Duff’s device to work on any size of dynamic array? And how would it perform?

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

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.

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

> 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

This world is not imaginary

Even better then :)

Maybe it's like some languages that don't chase growth/viral/visibility but exist calmly doing work.

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

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.

>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?

Oberon is the language Niklaus Wirth designed after Pascal and Modula.

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++.

This is the logic I personally used in deciding not to use D.

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.

Conveniences like closures depend on gc

C++ has had closures without a GC for over a decade now.

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.

If anything that's a statement about coroutines, not closures. And even then, not every coroutine has problems. I don't see a logical implication from that to a GC requirement.

That's not true

https://dlang.org/spec/function.html#function-pointers-deleg...

> 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!".

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.

I’m interested in hearing more. Also, I’m curious what language you use as a your daily driver?

I'm not sure I follow

Is this about D code that interops with C/C++?

You have "extern (C++)" and @nogc for that

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.

@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.

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.

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.

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++.

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

> 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.

In practice, "lots" isn't good enough. The whole ecosystem should work, not just lots.

In practice (I.e. actual practice that pays my rent) it's been good enough for me

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?

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.

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

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.)

If you actually turn it off (as in GC.disable()) they won't know either way, it's just a memory allocator to them.

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.

> 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.

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.

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.

> 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.

Reply on news.ycombinator.com