This python code was part of the imaging, analysis, and simulation software for radio interferometry that led to the historical first 'image' of a black hole.
Oh my God, his Lisp interpreter in Python: amazing. At the time I was just getting a grip with Python and starting in Lisp, it came at just the right moment in my autodidaction.
Really really good, although for a lot of people here it might be a little elementary (but then, the best code always feels elementary even when doing something advanced!)
For me, the answer is - The code that never existed.
Not to sound cheeky but eliminating code, is a beautiful thing. Less code is easier to maintain, understand, and faster to run. So the less code you can achieve, the better overall the software will be.
Deleting code is a beautiful feeling. Python's new walrus operator has gotten a lot of hate recently, but a few days ago I was writing a script and realized I could get rid of a few lines (AND have my meaning be clearer) using the walrus operator. So satisfying.
> For me, the answer is - The code that never existed.
> Not to sound cheeky but eliminating code, is a beautiful thing. Less code is easier to maintain, understand, and faster to run. So the less code you can achieve, the better overall the software will be.
Unless you think compressed/ minified code is beautiful, there must be additional factors involved other than minimizing LoC.
To me it's removing lines of code without affecting readability (or even improving it). Like when you don't know about a language feature so you implement a hacky version, then find out there's already a very elegant standard way to do it so you get to lance that hideous monstrosity you made off your code
This brings me to a very nice regular expression. It is the one being recommended in
RFC3986 "Uniform Resource Identifier (URI): Generic Syntax"
by T. Berners-Lee, R. Fielding and L. Masinter
https://tools.ietf.org/html/rfc3986
to parse an URI. Having seen so many regular expressions, that try to match it all, this regex tries to match as little as possible, while, at the same time, matches any string, because it matches no string. It does not define what to match, but what not to match and making every match optional.
According part from the spec:
^(([^:/?#]+):)?(//([^/?#]*))?([^?#]*)(\?([^#]*))?(#(.*))?
12 3 4 5 6 7 8 9
The numbers in the second line above are only to assist readability;
they indicate the reference points for each subexpression (i.e., each
paired parenthesis). We refer to the value matched for subexpression
<n> as $<n>. For example, matching the above expression to
http://www.ics.uci.edu/pub/ietf/uri/#Related
results in the following subexpression matches:
$1 = http:
$2 = http
$3 = //www.ics.uci.edu
$4 = www.ics.uci.edu
$5 = /pub/ietf/uri/
$6 = <undefined>
$7 = <undefined>
$8 = #Related
$9 = Related
where <undefined> indicates that the component is not present, as is
the case for the query component in the above example. Therefore, we
can determine the value of the five components as
scheme = $2
authority = $4
path = $5
query = $7
fragment = $9
One of my favorite RFCs for sure, and it's a beautifully simple and useful regex. It's a shame RFCs seem to have fallen out of fashion, the WHATWG URL spec is an unreadable mess of a monster, not least the parsing section: https://url.spec.whatwg.org/#url-parsing
Reminds me of a saying I read from moderngpu library's wiki page, a highly optimized yet highly readable GPU basic primitive library: "Software is an asset, code a liability. On good days I'd add 200 or 300 lines to this repository. On great days I'd subtract 500."
source: https://github.com/moderngpu/moderngpu/wiki/Introduction
it's the antithesis of maintainable code. But given that one is unlikely to want to change from calculating the inverse square root to inverse cube root or any other variation....
I disagree strongly. This code is very maintainable: it does not have dependencies, it is trivial to test, it is wickedly short, and with the appropriate comment there is no confusion regarding its purpose. Also, its field of applicability is clear from the context: replace this code with a call to fsqrt if you happen to have a fast hardware implementation of it. It is the most easily maintainable code, ever!
the one maintainability metric, and i think is the most important one, is whether it's easy to modify (to make it do something slightly different).
You'd be hard pressed to write an inverse square cube without basically rewriting the whole function. There's nothing that can be reused. The only saving grace is that it is side-effect free, so replacement is trivial, unlike a lot of other code that's not maintainable.
The question is how likely are you to need it to do something different, and what are the different things it might need to do? This will depend on the domain, but making things too flexible hampers maintainability too.
Your metric is only applicable within the context of the problem domain. In 3-d graphics, the inverse square root (1 divided by the square root of x) is an extremely common operation (such as for normalizing vectors), but the inverse cube root pretty much isn't used, so it's safe to assume you will not need to extend it to arbitrary powers.
As the designer of the code, you would understand that the inverse square root is a standalone problem.
And it also made the guys a ton of money :) They found a way to take something useful in theory and other practical applications and use it to make something never before seen for the massmarket. That one magic number alone is responsible for a good portion of his net worth and of course his Ferrari
The most beautiful piece of code you've ever read contains a magic number with the comments "evil floating point bit level hacking" and "what the fuck?"... you're a madman.
It's a bit of a tricky question because you can have a beautiful snippet entangled in a mess of a codebase.
I think a much better question would be most beautifully structured codebase.
Code, as a snippet, or line, is constantly struggling between poetic conciseness and verbose clarity... To which I will always pick clarity (for "the next guy"), hence not necessarily elegant.
My first language was QBASIC and much of the first code I read (other than modifying PHP scripts I didn't really understand) was from Pete's QB Site. I'd hardly call it beautiful, but definitely nostalgic and cool.
The SQLite source tree and DRH code in general are truly piece of art. Almost every line of code is carefully commented. Despite the complexity of the project, you'll learn a lot of practical concepts including expression tree generation, bytecode execution, how to test your code and so forth.
This reminds me of Chuck Moore (inventor of Forth). He designs his own CPUs, using his own CAD package, written in the programming language he invented!
That depends on how large the misprediction penalty is and how many times the branch executes. Branch prediction isn't magic. It never makes branches beneficial. The best it can do, with perfect accuracy, is bring the amortized misprediction penalty down to zero. The key is that Duff's Device also relies on branching, and it's a less predictable branch that's more likely to be mispredicted. On the other hand, one BP miss is still cheaper than several hits plus one miss at the end. On the other other hand, there are issues to consider like code size and cache turnover (favors a loop), handling of special cases where larger loads/stores can be used (favors DD), processor extensions, etc. If you're really trying to write an optimal memcpy-like function, you'll probably end up using a hybrid of several approaches - including Duff's Device.
Another thing to note, is that loop unrolling can be harmful to performance, as it requires more instruction cache. Beyond branch prediction, modern compilers can also convert loops into vector / SIMD instructions, and other magic.
The Duff's device is still useful for creating co-routines though; a handy way of yielding, then returning to the yield point.
For me it's a BASIC one-liner which generates mazes
10 PRINT CHR$ (205.5 + RND (1)); : GOTO 10
I found this specific one via slashdot[1], but something similar, which I've never managed to find/replicate, was used to generate mazes on the Atari 800 XL at my school when I was a kid.
Oh wow this is a cool loop closure. I wrote a CHIP 8 emulator to learn stuff and my main test rom was this program. I walked through the bytecode very slowly as I learned and debugged and repeatedly wondered how the heck the program was so tiny.
1/2^n, I believe (where n is the number of lines after the first one, otherwise 1/2^n+1). So halved every time: 100% with 1 line, 50% with 2 lines, 25% with 3 lines, and so on. Width is irrelevant (you can do this in your head comparing w=1 n=2 to w=2 n=2 for example).
Also, I don't believe it doesn't depend on width. I think with constant height, the probability of completable one should increase with width, and become almost 1 for very large widths.
Hm, good points, looks like I need more sleep. Looking at the video again, a path is valid if two slashes follow each other, with the same pattern shifted by 1 the line below.
But I wasn't treating /\ as an invalid on the first line. Eg thinking of:
/\/\/\/\
\\//////
/\\\\\\\ … and so on
(Using the /\ pattern, paths can go back up and come back down, so this requires a lot more thought than I instinctively put into it)
Wow! This is really cool. I just entered it quickly in a C64 emulator and it ran, creating a maze. Not sure, whether it would be a solvable one, but it is interesting to note, that the paths are really connected!
The paths make sense. I.e. you got uninterrupted lines, surrounded by walls, so it is a real maze and not just a lookalike or partial maze. Oh, and it's a-maze-ing! :-)
No, a labarynth is a single twisting route without branches. A maze has branches and thus can have dead-ends. Both must have an entry and exit point (technically mazes may have more than one exit and entry, but most don't).
”Although early Cretan coins occasionally exhibit branching (multicursal) patterns
[…]
both logic and literary descriptions make it clear that the Minotaur was trapped in a complex branching maze
[…]
In English, the term labyrinth is generally synonymous with maze. As a result of the long history of unicursal representation of the mythological Labyrinth, however, many contemporary scholars and enthusiasts observe a distinction between the two.”
> One could argue that if the user perceives a X, then it produces a X.
This can be stretched to turn anything into anything else. For example, why can't this comment be a maze? In that case 10 REM; 20 END is my even shorter, more elegant maze program because I see a maze in it.
Some constraints that are typically implied when people say "computer generated mazes":
- They are solvable (have a start and end)
- OR they loop endlessly with no dead ends.
- Walls and spaces consume 1 element on the grid.
- No space on the grid is surrounded by all 4 NWSE walls.
>>One could argue that if the user perceives a X, then it produces a X.
>This can be stretched to turn anything into anything else. For example, why can't this comment be a maze?
Because unlike the one-liner nobody perceives it as a maze, so the "this can be stretched to turn anything into anything else" argument is tenuous...
> This can be stretched to turn anything into anything else. For example, why can't this comment be a maze?
Name one person who perceives your comment as a maze.
It must be perceived as a maze by people for it to apply.
As it stands, I’m not sure if people perceive your comment as a maze.
Maybe theoretically there’s a nonzero number of people who perceive the comment as a maze. But unless your audience is those few people, there wouldn’t be much utility in it. In the OP’s example this maze perception is not only highly widespread but it’s also leveraged for a particular intended effect.
Everything is an illusion. \s and /s are just liquid crystal pixels on the screen, filtering some light. However it's easier to say that if something has a name and you can identify it, then it's probably that thing. I see a maze it means it's a maze :)
Nice to see confusing a joke reference to a regional fact (as to things that can seem X but be Y) with transphobia. Anybody told you that merely referencing trans women in Thailand is opposing them? Projecting much?
First, you come blazing with accusations of transphobia, because of a joking mention of Thailand's ladyboy scene, to challenge the parents' notion that everything is WYSIWYG. Do you even know me? Or you have a hobby of randomly assuming things about people you don't know?
Second, when I don't take that quietly, you add the above comment about having the gal to defend myself, going for the "This animal is extremely vicious. When attacked, it defends itself" angle...
Perhaps you can go even lower against some stranger on the internet, but you wont be getting any replies from me in this thread.
Good on you for standing for what you say. I personally didn't see any transphobia in your comment, what you said is merely a joke on a fact of that part of the world. The "phobia" was added on by Zhyl
The transphobia isn't related to the 'fact' about Thailand. If anything, the fact that it's a reference point is the reason why the sentiment is distasteful. The implication/joke is:
* A person goes into a bar in Thailand, sees what they think is a girl and are surprised to find that things are not what they seem.
Broken down:
* Person sees a girl
* It is not a girl
* This is a bad thing
Now, it would be easy to claim (as indeed you and GP seem to be doing) that this isn't a slur on the second party in this encounter. It's a fact of the world. They exist. OP, the person who is saying that 'things are what they seem to be' would probably not want to find themselves in a situation where they making an assumption that the person is female.
The fact that this is negative can be seen in the 'I hope you don't' words which set the tone and are the basis of most of the sarcasm. I have to say that even if GP had picked a different example, I don't like this kind of comment anyway. It's a bitter, jabby comment that I don't think furthers discussion and overall makes HN a more negative and uncomfortable place to be.
So an assumption I made, which of course is debatable, is that the setting of 'bar' implies a romantic or sexual intent on the first party. GP will probably deny or refute this, but really without this implication there isn't much of a joke to speak of. "I spoke to this girl and it turned out she was a dude! What larks we had!".
GP seems to be making this claim in this comment:
>Nice to see confusing a joke reference to a regional fact (as to things that can seem X but be Y) with transphobia. Anybody told you that merely referencing trans women in Thailand is opposing them? Projecting much?
If it was 'merely referencing' then it wouldn't be a joke. 'Merely referencing' would we to reword the comment as:
"Things are not always what they seem, like commonly accepted phenomena of Thaiwanese ladyboys".
I mean, not much different, and still in poor taste for a thread that is about beautiful code, but the tone of the comment is completely changed. It's now no longer a jab at the PC, but using a counterexample to illustrate a point.
And why is suggesting that someone being shocked to discover a ladyboy transphobic anyway? Basically, it boils down to the fact that trans people have to suffer against stigma that they're somehow 'out to trick' people and that unassuming straight males need to 'watch out'. This comment is a prime example of this. It's literally a warning. Sure, it's mild transphobia, but it's perpetuating this stigma and I feel like Hackernews generally, and this thread specifically, are not really places for this kind of comment.
I normally wouldn't write this much out about this topic, but GP seemed very upset about their comment being called transphobic. Note, I didn't call them transphobic at all. I didn't actually make any comment about them, their person, their intent or anything. Just that the comment was 'casual transphobia' which I firmly believe that it is.
Let's break down the rest of their comment:
>Well, I am amazed that one can be so rude.
In both cases they use my own words back to me. I'm not sure why. It seems to be a mix of defensiveness and sarcasm. I don't actually think I was being rude - certainly no ruder than they were being to who they were commenting to. I felt that their original comment was snide.
>First, you come blazing with accusations of transphobia
I called the comment transphobic. Addressed above.
>to challenge the parents' notion that everything is WYSIWYG
Not very well.
>Do you even know me? Or you have a hobby of randomly assuming things about people you don't know?
This is incredibly defensive. Especially the second part. It's not enough to call out transphobia, they have to...
Somewhere I have a copy of a BASIC program I typed into my TRS-80 Color Computer as a kid, from an issue of K-Power magazine.
I don't recall if it was one of the full issues, or one of the "insert issues" found within Family Computing of the era.
It was a special kind of "snow fall" generator; IIRC, there were only a couple of versions, one for the Apple IIe and the other for the PCjr - I likely used the PCjr version for the conversion since the BASIC language was nearly identical between the PCjr and my CoCo 2.
What was special was that it managed to seemingly move hundreds of pixels relatively rapidly on the screen; now, this might not seem like such a feat, but it really was considering we're talking about a computer system running an interpreted BASIC program, with a max speed below 1 MHz in standard mode (0.89 MHz - there was a so-called "speedup poke" that "doubled" the speed - POKE 65495,0 if anyone cares).
I don't recall what trick it used - or if it really used anything special at all - but I do remember being impressed by that bit of code.
Now surely someone may come along and point out how this isn't a true quicksort[0] because it doesn't partition the elements in place, but it's more of the simplicity of the logic and its readability that showed me how beautiful functional code can be.
This may be an elegant piece of code at first glance except the niceties of quicksort such as cache locality and stability come entirely from the in-placeness of the partition procedure.
I won't comment on how quicksort-y this is, but the combination of pattern matching and recursion is bread-and-butter Haskell. A number of seemingly complex algorithms can be implemented in a similar way.
Having said that, it is elegant and clean and -- taken by itself -- does make Haskell very attractive.
I saw a similar version in erlang (in Joe Armstrong's Programming Erlang) and agree it beautifully illustrates the concept of quicksort. Apparently, Tony Hoare came up with it when he took a class teaching him recursion (i.e. he was a student).
But the flaw you note unfortunately undermines performance... the "quick" in "quicksort".
Thus, IMHO it's a compelling illustration of the profound strengths and weaknesses of fp.
Agreed that this is beautiful purely from the standpoint of how there is essentially no disconnect between the concept of the algorithm and the way it's expressed in code. It's almost the math/algo just translated directly into code (not commenting on the efficiency or other issues that may exist).
Quick sort comes with a steep penalty. Worst case is O(n^(2)). The reason quicksort is good is because it's in place. Once you throw away the in place aspect of quick sort, it's straight up bad.
This implementation of quicksort is actually a great example of why functional programming sucks. It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead.
Algorithms that are optimal under the mutable data assumption are different than algorithms that are optimal under the constant data assumption. So a normal programmer might sort via quicksort in Haskell because it's the optimal sort in imperative languages even though naive Haskell quicksort is objectively worse in every way than naive Haskell mergesort.
Performant programming in Haskell requires a much more intimate understanding of the underlying architecture than performant programming in, for instance, C++. And that's a very low bar.
> It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead.
Please tell me what imperative quicksort algorithm has O(1) space. All versions I've seen and could recall use recursion; although each recursive call uses O(1) space, in the worst case of bad pivot element selection each recursive call would only really sort one element resulting in a worst-case O(n) space. Use of randomization would result in a high probability of choosing a good pivot element, but even then you can expect approximately O(log n) space.
Also would like to see why you think the Haskell version has enormous constant time overhead. Where do you think this overhead comes from? If you are comparing to an equivalent program in C++ then sure allocations and stuff, but compared with the typical Haskell list-processing programs I don't see any significantly larger overhead.
I don't know that I would ever do this, since O(lgn) space is normally trivial, but couldn't you use a RNG that's based on like the depth and start position of a given "stack frame" of a recursion-less quicksort?
Like to "recurse" (not actually recurse, but pretend) you would increment depth, the update the start position, and calculate the new partition index based on the (depth, start) tuple?
And run that in reverse for going back up the stack.
edit:
Hah. This is fun. There's a variant where you do tricks with the elements of the array to get constant space.
The idea is that you partition the elements, but then instead of storing the bounds of the left and right sides, you switch the element from the start of the right side with the partition element of the "stack frame" above you. This later serves as a flag indicating the end of the right side, since the partition of the parent "stack frame" is greater than all elements on the right you know you've hit then end of the right side when you see a larger number than the parent "stack frame"'s pivot.
That link basically just simulates recursion by defining a stack in the function. It recognizes that in the recursive version among the stack variables only the two indexes need to be stored so it stores them. It is even less space efficient than the recursive version because it always allocates O(n) space.
The path towards O(1) space instead of O(log n) space is fraught with technicalities. At the bottom, you realize that no matter what algorithm you use, you always store the array size in lg(n) bits! So it makes more sense to say “less memory” rather than O(1) memory for sorts.
I don’t see how this is a great example of how functional programming sucks. It is easy in any programming language to build a slow sorting algorithm. The fact that you need to use different algorithms with immutable data is irrelevant. You need to use different algorithms for pretty much any type of data structure.
Functional programming makes a different set of tradeoffs than imperative programming. You have to work harder to get peak performance, but in many cases it is actually quite performant. Just look at how fast Elm is for web applications, and how that approach allows for a time-traveling debugger and virtually no crashes.
I remember on olympiads one trick that I though was brilliant out-of-the-box thinking was to shuffle input before sorting to avoid worst-case-prepared inputs.
If having to think a bit harder about your sorting algorithm is why functional programming sucks, can I give examples of every bullshit concurrency problem I’ve had in Java as an example of why imperative programming sucks?
Persistent data structures are a bit slower but largely become non issues if you deal with concurrency and avoid a lock that you would have otherwise required in C or Java.
It’s not like the people who wrote Haskell are idiots; most of these data structures end up sharing a lot of data, and a “new” structure is often only the diffs from the previous version. Not to mention that since you have a compile time guarantee that the data isn’t going to change, you effectively avoid any need for defensive copying.
I’m sure you can find some benchmark that proves C++ is faster in the most technical sense, but for network and multithreaded applications, it’s not even close; it’s so much easier to make sure a functional concurrent language is actually correct that the benchmarks become almost irrelevant.
I say this as a die hard FP fan: I agree with your parent comment. I think FP is generally good enough or sometimes even quite close. But I don't know how many times I ended up writing C in Haskell or scheme to make an algorithm really fast (once all other algorithms have been tried or discarded).
The quicksort example is a shitty quicksort, because it will be slow as molasses. A proper quicksort in Haskell will degrade you to writing C in Haskell (with the benefits of a large standard library)and then you have lost. C in C will always beat C in Haskell or any other language.
Is it a worthwhile tradeoff? I believe so. The few times I am limited by speed in that way are few and far between, and most often it was because I thought something like O(n2) would be good enough which is easily fixable. Sometimes I just need to make optimal code faster. By then I always wish I would be using an imperative language instead.
Is the level of my English lacking? The comment you're agreeing to clearly seems to argue that fp sucks as a whole because it's not as fast for tight looped algorithms, not that it sucks only for them.
I'm genuinely curious; how often do you actually end up writing sorts in Haskell? I just use the built-in sort function, which is fast enough.
Maybe your use-case is different than mine, but I typically use Haskell (or another functional language) for network applications, which typically don't benefit from tight-loops since the network is almost always the bottleneck anyway. For these kinds of applications, having proper concurrency and IO handling matters a lot more than worrying about whether your loops result in a cache-miss.
I have had a couple of times where the overhead of idiomatic Haskell warranted rewriting it in a mutable imperative way. Sorting was never a problem, but things like functional heaps (leftist or pairing heaps) will never be as efficient as mutable, cache aware ones.
The lower level mucking around when you have to do those kinds of optimizations is, IMO, much more pleasant in imperative languages.
Sure, I won't argue with that. I've never used Haskell for that low-level of work, so I can't speak with any kind of expertise on that; I've never found Haskell's FFI to be terribly hard to use though, so you could conceivably get the best of both worlds.
Also, have you tried Liquid Haskell? It uses refinement types to let you use the "unsafe" and fast versions of functions to guarantee correctness while also increasing performance.
> most of these data structures end up sharing a lot of data, and a “new” structure is often only the diffs from the previous version.
Like everything else in life, those data structures come with tradeoffs. Accessing an array element is an indexing operation into a continuous block of memory. The indexing is built into the instruction set as an addressing mode, the array's memory is continuous (so better locality of reference for caching), and if you're traversing it predictably, prefetch hardware can being it into cache before you issue the instructions that do the read.
The same operation in a persistent vector is a function call, several pointer dereferences, and a more complex on-memory structure with more overhead. It works elegantly, but it's a completely different (and likely slower) level of abstraction from a simple in-memory vector.
A few years ago, I switched a toy search program away from ImmutableJS and over to naive copying of raw JS data structures. I don't remember the exact performance delta, but it was something like an x10-100 speedup, for code that was otherwise structurally identical:
In this case, I had a goal to achieve, a timeline on which to achieve it, and it was the ability to switch to simpler, closer-to-the-metal data structures that made it happen. Had I needed more optimization, the most logical approach would have been to remove even more copying and rely even more heavily on mutation. This shouldn't come as a surprise, because at their core, these machines are fundamentally built on mutation, and there's a cost to pretending otherwise.
Now, in fairness to the persistent structures, this is something like a worst case scenario for their use - the algorithm is almost entirely dominated by manipulating relatively small data structures without much opportunity for sharing. It was also single threaded, small, and developed by a single developer in a small amount of time, so the organizational benefits of immutability were not apparent either.
If this was a huge redux state shared across a team of 100 developers and updated only a few times a second, I could probably tell a completely different story. It's easy to imagine (based on firsthand experience!) the kind of havoc that can be inflicted on a project with an erroneous update.
I get the enthusiasm for functional programming and persistant structures, etc., but at the end of the day it's just an engineering approach. One of many, and there's room to do the work to choose between them.
> I get the enthusiasm for functional programming and persistant structures, etc., but at the end of the day it's just an engineering approach. One of many, and there's room to do the work to choose between them.
I don't disagree with this but that's not what you said initially. You said "this is why FP sucks".
I definitely think that if your work is doing tight-loops where every micro-second matters, an imperative language will usually be the correct approach. I don't think anyone is (or would) argue against that point, including most Haskellers.
However, functional languages do simplify things with network/concurrent applications. There's a reason that something like MapReduce is popular. Something like Spark or Onyx is just simpler to do correctly and work with than trying to achieve something equivalent using C or C++; maybe this is just me.
EDIT: My bad, I was responding to the wrong person, this person never said FP sucks. I apologize!
> Quick sort comes with a steep penalty. Worst case is O(n^(2)). The reason quicksort is good is because it's in place. Once you throw away the in place aspect of quick sort, it's straight up bad.
That's why you shuffle the list before you sort it :)
> It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead.
It doesn't silently transform O(1) to O(n), the code is explicitly O(n^2) space worst-case. The only 'silent' transformation that could happen here is an optimization to improve performance. Also, I don't know where you got the 'enormous constant time overhead' part.
> Algorithms that are optimal under the mutable data assumption are different than algorithms that are optimal under the constant data assumption.
A normal programmer wouldn't be defining writing their own sort functions. A normal Haskell programmer would understand mutability in Haskell.
> Performant programming in Haskell requires a much more intimate understanding of the underlying architecture than performant programming in, for instance, C++.
It really depends on what you're writing and how much performance you actually need. Implementing a moderate-complexity parallel data processing algorithm in Haskell may result in a slightly slower but much simpler implementation than C++. An implementation of the same complexity in C++ may be slower than Haskell. Writing performant, parallel, safe code for a moderately complex algorithm in C++ is far from easy.
The problem with this piece of code is not that it doesn't do it in-place. The problem is, if the input list is (almost) constant, then this code will (almost) certainly take quadratic time to sort it, even if it is shuffled before being fed to this function.
However, I get what you mean. It really is beautiful!
Though it's not true quicksort, it's possible to explain the idea of this algorithm with code like this in just a few minutes while the truest implementation in C with Hoare partition looks really confusing
You are the second person to reference quicksort in Haskell in this thread. The other person even mentioned it not being true quicksort. Who knew quicksort in Haskell was such a beloved piece of code!
Back when HotOrNot was hot, there was a site like it for rating code snippets. The top-rated one, I think I remember, was a broken version of this sort function: it had left out the recursions or something (I don't remember exactly), which made it even more 'elegant'.
This wasn't the only case I noticed of highly-rated broken code there. It took me a long time to take this lesson to heart about especially slick-looking code of my own.
Curious why the comment about STL algorithms written by Alexander Stepanov was downvoted so hard it died? I’m not a C++ dev... is he hated or is the implementation that bad?
I was wondering too. His series of videos on YouTube from A9 on algorithms is excellent and has some very beautiful code but you have to work through the series to fully appreciate it.
// Dijkstra, Edgar. "Go To Statement Considered Harmful".
// Communications of the ACM. Vol. 11. No. 3 March 1968. pp. 147-148
if (neighboridx == target) {
goto OUTSIDE;
}
Exploit codes are often the most beautiful code I read, they are usually small and take some dazzling brilliance to push the computer and make it do what it wasn't.
I can remember the first code that showed how to exploit IFS, race conditions via symlink, the classic "smashing the stack", RTM's worm.
Beauty of a code to me has nothing to do with the formatting, comments, documentations, but everything to do with the mind that bent it into place. Most of the beautiful code I have ever seen would be classified as ugly, spaghetti, not production worthy.
I had absolutely no idea until now that RTM co-founded y-combinator. I remember him from mentioned in Bruce Sterling's The Hacker Crackdown and Clifford Stoll's The Cookoo's Egg as well as an occasional Phrack article.
I'm partly impressed by the tooling used; most of the coolness (to me) is the author's self-confidence in his hunch that the SoC _didn't_ have its MMU set up properly, and the way he followed his nose in determining that he was probably right.
I still wonder exactly how much was sunk into the project, before it was possible to determine that the MMU was indeed broken. Heh.
The conceptually same thing will also work on bourne shell. But as in the Windows case only as a script stored in file, the original with inline function definition is self-contained oneliner.
I don't know Windows scripting, but that looks like something you'd have to put in a file and call for it to work, instead of just running that on the command line. You can do the same thing on Unix systems. Writing
$0|$0
on a file and running it should also work as a fork bomb.
:( #sadface
:() #dopefish
{ : #smiling one-toothed vampire
{ :| #blank stare with hat
:| #blank stare without hat
|: #other blank stare without hat
|:& #blank stare with bow
}; #winking face with mustache
};: #winking four-eyed alien face with mustache
Only one of those was a smile, and you generally don't want a vampire smiling at you even if they're down a tooth! ;)
A good debuggable piece of code explains what it is trying to do by being clearly written and conforming to a consistent and logical model. I don’t think I would ever have invented this type of lexer pattern in Go by myself, but would be very grateful to come across it in a code base I had to fix. Like Duff’s Device mentioned in this thread, it has just the right amount of cleverness without becoming inscrutable.
Also, if you’ll excuse some avuncular pride, my niece and I wrote some code yesterday. She asked me how many times grandma’s clock chimes every day and we ended up with the following Ruby:
What’s quite elegant about Ruby (in and of itself, not in comparison to your examples) is how consistently it is implemented using its own simple set of core features, with very little magic or syntactic sugar. reduce, Enumerable, what the & operator is doing etc.
What’s so challenging about Ruby is how the language can be abused by library vendors to make all kinds of surprising magic and homegrown syntactic sugar.
> What’s quite elegant about Ruby is how consistently it is implemented using its own simple set of core features, with very little magic or syntactic sugar.
Honestly, I don't think this has much to do with Ruby. This a consequence of using reduce or any other higher-order functions, which come from functional programming, and are now available in almost all modern multi-paradigm programming languages (including Python and Haskell).
I you like this kind of constructs, you should definitely learn a functional programming language, you'll love it.
FYI, there's an effort at the moment to translate XeTeX and dvipdfmx into Rust. Started with c2rust, now we have a test suite checking regressions against the entire arXiv archive. Contributors welcome. https://github.com/crlf0710/tectonic
I've got a better code snippet: your exact same code snippet but for a language which will short circuit based on the lvalue of the assignment expression.
Then t would never be able to overflow s (nor even eat its null terminator)
At the time the code was written, the security ramifications were not quite the same as they are now. Even now, I would suggest that there are times where such a construction would be just fine.
This kind of code is cute, but awful for readability. The author could easily (more easily!) have written the function to be very readable, but went for the cute ultra-compact style instead.
The only reason it's at all readable is that it's solving such a simple problem. Write more complex functionality in that style, and you quickly get a nightmare.
I believe MISRA C outright bans this kind of thing (three assignments with no sequence point), as it has no place in a codebase of real consequence.
I understand that some C programmers pride themselves on being able to read this kind of code (far more impressive than being able to write it), but I see no reason for it in serious software work.
I remember seeing Maxwell's equations written in Lisp (I believe it was in the Structure and Interpretation of Programs). This made me feel something very profound, although I am still unable to put this feeling into words.
393 comments
[ 4.8 ms ] story [ 250 ms ] threadThis python code was part of the imaging, analysis, and simulation software for radio interferometry that led to the historical first 'image' of a black hole.
It's utterly digestable due to its use of meaningful variable names, logical breakdown of functions and absence of 'clever' nontrivial one-liners.
https://code.jsoftware.com/wiki/Essays/Incunabulum
Really really good, although for a lot of people here it might be a little elementary (but then, the best code always feels elementary even when doing something advanced!)
https://www.metalevel.at/lisprolog/ https://www.metalevel.at/lisprolog/lisprolog.pl
Not to sound cheeky but eliminating code, is a beautiful thing. Less code is easier to maintain, understand, and faster to run. So the less code you can achieve, the better overall the software will be.
I do, however, resent Python 3 for removing pattern matching on tuples in function heads.
> Not to sound cheeky but eliminating code, is a beautiful thing. Less code is easier to maintain, understand, and faster to run. So the less code you can achieve, the better overall the software will be.
Unless you think compressed/ minified code is beautiful, there must be additional factors involved other than minimizing LoC.
According part from the spec:
[0] https://unix.stackexchange.com/questions/419697/why-are-true...
"// what the fuck? "
You'd be hard pressed to write an inverse square cube without basically rewriting the whole function. There's nothing that can be reused. The only saving grace is that it is side-effect free, so replacement is trivial, unlike a lot of other code that's not maintainable.
You mean inverse cube root? I believe the geometry ain’t easily upgradeable this way.
As the designer of the code, you would understand that the inverse square root is a standalone problem.
About 10 years later you would find this stuff everywhere in boost but for the time this was spectacularly elegant for C++
I think a much better question would be most beautifully structured codebase.
Code, as a snippet, or line, is constantly struggling between poetic conciseness and verbose clarity... To which I will always pick clarity (for "the next guy"), hence not necessarily elegant.
That would be an interesting thread too! I think gorgeous snippets have a different kind of beauty that just generally well done projects.
To me, it's kind of like comparing the beauty of a gem to the beauty of a bridge.
PLAY "MBT180o2P2P8L8GGGL2E-P24P8L8FFFL2D"
https://gist.github.com/zabirauf/29c89a084901cab8bc6b
Parsing binary data can be...nontrivial. The beauty is in the code that doesn't exist.
Very elegant use of the fall-through behavior of the swtich statement.
Normal for-loops are much faster than they were when Duff's Device was invented, since they take advantage of modern branch prediction.
The Duff's device is still useful for creating co-routines though; a handy way of yielding, then returning to the yield point.
[1] https://developers.slashdot.org/story/12/12/01/1847244/how-d...
https://floooh.github.io/tiny8bit/c64.html?input=${wait:200}...
Expressed in terms of line width (w) and number of lines (n).
[0] Where there's a valid path from the first line to the last.
Edited for clarity and accuracy.
But I wasn't treating /\ as an invalid on the first line. Eg thinking of:
(Using the /\ pattern, paths can go back up and come back down, so this requires a lot more thought than I instinctively put into it)What do you mean by that?
This is the art of illusion.
I was today years old when I learned this.
”Although early Cretan coins occasionally exhibit branching (multicursal) patterns
[…]
both logic and literary descriptions make it clear that the Minotaur was trapped in a complex branching maze
[…]
In English, the term labyrinth is generally synonymous with maze. As a result of the long history of unicursal representation of the mythological Labyrinth, however, many contemporary scholars and enthusiasts observe a distinction between the two.”
This can be stretched to turn anything into anything else. For example, why can't this comment be a maze? In that case 10 REM; 20 END is my even shorter, more elegant maze program because I see a maze in it.
Some constraints that are typically implied when people say "computer generated mazes":
- They are solvable (have a start and end)
- OR they loop endlessly with no dead ends.
- Walls and spaces consume 1 element on the grid.
- No space on the grid is surrounded by all 4 NWSE walls.
Because unlike the one-liner nobody perceives it as a maze, so the "this can be stretched to turn anything into anything else" argument is tenuous...
Name one person who perceives your comment as a maze.
It must be perceived as a maze by people for it to apply.
As it stands, I’m not sure if people perceive your comment as a maze.
Maybe theoretically there’s a nonzero number of people who perceive the comment as a maze. But unless your audience is those few people, there wouldn’t be much utility in it. In the OP’s example this maze perception is not only highly widespread but it’s also leveraged for a particular intended effect.
I'd suggest to not go bar-hopping in Thailand with that mindset...
First, you come blazing with accusations of transphobia, because of a joking mention of Thailand's ladyboy scene, to challenge the parents' notion that everything is WYSIWYG. Do you even know me? Or you have a hobby of randomly assuming things about people you don't know?
Second, when I don't take that quietly, you add the above comment about having the gal to defend myself, going for the "This animal is extremely vicious. When attacked, it defends itself" angle...
Perhaps you can go even lower against some stranger on the internet, but you wont be getting any replies from me in this thread.
* A person goes into a bar in Thailand, sees what they think is a girl and are surprised to find that things are not what they seem.
Broken down:
* Person sees a girl
* It is not a girl
* This is a bad thing
Now, it would be easy to claim (as indeed you and GP seem to be doing) that this isn't a slur on the second party in this encounter. It's a fact of the world. They exist. OP, the person who is saying that 'things are what they seem to be' would probably not want to find themselves in a situation where they making an assumption that the person is female.
The fact that this is negative can be seen in the 'I hope you don't' words which set the tone and are the basis of most of the sarcasm. I have to say that even if GP had picked a different example, I don't like this kind of comment anyway. It's a bitter, jabby comment that I don't think furthers discussion and overall makes HN a more negative and uncomfortable place to be.
So an assumption I made, which of course is debatable, is that the setting of 'bar' implies a romantic or sexual intent on the first party. GP will probably deny or refute this, but really without this implication there isn't much of a joke to speak of. "I spoke to this girl and it turned out she was a dude! What larks we had!".
GP seems to be making this claim in this comment:
>Nice to see confusing a joke reference to a regional fact (as to things that can seem X but be Y) with transphobia. Anybody told you that merely referencing trans women in Thailand is opposing them? Projecting much?
If it was 'merely referencing' then it wouldn't be a joke. 'Merely referencing' would we to reword the comment as:
"Things are not always what they seem, like commonly accepted phenomena of Thaiwanese ladyboys".
I mean, not much different, and still in poor taste for a thread that is about beautiful code, but the tone of the comment is completely changed. It's now no longer a jab at the PC, but using a counterexample to illustrate a point.
And why is suggesting that someone being shocked to discover a ladyboy transphobic anyway? Basically, it boils down to the fact that trans people have to suffer against stigma that they're somehow 'out to trick' people and that unassuming straight males need to 'watch out'. This comment is a prime example of this. It's literally a warning. Sure, it's mild transphobia, but it's perpetuating this stigma and I feel like Hackernews generally, and this thread specifically, are not really places for this kind of comment.
I normally wouldn't write this much out about this topic, but GP seemed very upset about their comment being called transphobic. Note, I didn't call them transphobic at all. I didn't actually make any comment about them, their person, their intent or anything. Just that the comment was 'casual transphobia' which I firmly believe that it is.
Let's break down the rest of their comment:
>Well, I am amazed that one can be so rude.
In both cases they use my own words back to me. I'm not sure why. It seems to be a mix of defensiveness and sarcasm. I don't actually think I was being rude - certainly no ruder than they were being to who they were commenting to. I felt that their original comment was snide.
>First, you come blazing with accusations of transphobia
I called the comment transphobic. Addressed above.
>to challenge the parents' notion that everything is WYSIWYG
Not very well.
>Do you even know me? Or you have a hobby of randomly assuming things about people you don't know?
This is incredibly defensive. Especially the second part. It's not enough to call out transphobia, they have to...
perl -C -e 'print chr(9585.5+rand) while 1'
binmode(STDOUT);
To the front.
Unicode on languages made before it existed is...argh.
I remember being fascinated with Pascal program that makes snow fall.
Basically, it was white dots on a blue background in an infinite loop. :)
I don't recall if it was one of the full issues, or one of the "insert issues" found within Family Computing of the era.
It was a special kind of "snow fall" generator; IIRC, there were only a couple of versions, one for the Apple IIe and the other for the PCjr - I likely used the PCjr version for the conversion since the BASIC language was nearly identical between the PCjr and my CoCo 2.
What was special was that it managed to seemingly move hundreds of pixels relatively rapidly on the screen; now, this might not seem like such a feat, but it really was considering we're talking about a computer system running an interpreted BASIC program, with a max speed below 1 MHz in standard mode (0.89 MHz - there was a so-called "speedup poke" that "doubled" the speed - POKE 65495,0 if anyone cares).
I don't recall what trick it used - or if it really used anything special at all - but I do remember being impressed by that bit of code.
[0] https://stackoverflow.com/questions/7717691/why-is-the-minim...
Having said that, it is elegant and clean and -- taken by itself -- does make Haskell very attractive.
But the flaw you note unfortunately undermines performance... the "quick" in "quicksort".
Thus, IMHO it's a compelling illustration of the profound strengths and weaknesses of fp.
This implementation of quicksort is actually a great example of why functional programming sucks. It silently transforms an O(1) space algorithm into an O(n) space one, and adds an enormous constant time overhead.
Algorithms that are optimal under the mutable data assumption are different than algorithms that are optimal under the constant data assumption. So a normal programmer might sort via quicksort in Haskell because it's the optimal sort in imperative languages even though naive Haskell quicksort is objectively worse in every way than naive Haskell mergesort.
Performant programming in Haskell requires a much more intimate understanding of the underlying architecture than performant programming in, for instance, C++. And that's a very low bar.
Please tell me what imperative quicksort algorithm has O(1) space. All versions I've seen and could recall use recursion; although each recursive call uses O(1) space, in the worst case of bad pivot element selection each recursive call would only really sort one element resulting in a worst-case O(n) space. Use of randomization would result in a high probability of choosing a good pivot element, but even then you can expect approximately O(log n) space.
Also would like to see why you think the Haskell version has enormous constant time overhead. Where do you think this overhead comes from? If you are comparing to an equivalent program in C++ then sure allocations and stuff, but compared with the typical Haskell list-processing programs I don't see any significantly larger overhead.
Like to "recurse" (not actually recurse, but pretend) you would increment depth, the update the start position, and calculate the new partition index based on the (depth, start) tuple?
And run that in reverse for going back up the stack.
edit: Hah. This is fun. There's a variant where you do tricks with the elements of the array to get constant space.
https://link.springer.com/chapter/10.1007/BFb0016252
The idea is that you partition the elements, but then instead of storing the bounds of the left and right sides, you switch the element from the start of the right side with the partition element of the "stack frame" above you. This later serves as a flag indicating the end of the right side, since the partition of the parent "stack frame" is greater than all elements on the right you know you've hit then end of the right side when you see a larger number than the parent "stack frame"'s pivot.
Functional programming makes a different set of tradeoffs than imperative programming. You have to work harder to get peak performance, but in many cases it is actually quite performant. Just look at how fast Elm is for web applications, and how that approach allows for a time-traveling debugger and virtually no crashes.
If having to think a bit harder about your sorting algorithm is why functional programming sucks, can I give examples of every bullshit concurrency problem I’ve had in Java as an example of why imperative programming sucks?
Persistent data structures are a bit slower but largely become non issues if you deal with concurrency and avoid a lock that you would have otherwise required in C or Java.
It’s not like the people who wrote Haskell are idiots; most of these data structures end up sharing a lot of data, and a “new” structure is often only the diffs from the previous version. Not to mention that since you have a compile time guarantee that the data isn’t going to change, you effectively avoid any need for defensive copying.
I’m sure you can find some benchmark that proves C++ is faster in the most technical sense, but for network and multithreaded applications, it’s not even close; it’s so much easier to make sure a functional concurrent language is actually correct that the benchmarks become almost irrelevant.
The quicksort example is a shitty quicksort, because it will be slow as molasses. A proper quicksort in Haskell will degrade you to writing C in Haskell (with the benefits of a large standard library)and then you have lost. C in C will always beat C in Haskell or any other language.
Is it a worthwhile tradeoff? I believe so. The few times I am limited by speed in that way are few and far between, and most often it was because I thought something like O(n2) would be good enough which is easily fixable. Sometimes I just need to make optimal code faster. By then I always wish I would be using an imperative language instead.
Maybe your use-case is different than mine, but I typically use Haskell (or another functional language) for network applications, which typically don't benefit from tight-loops since the network is almost always the bottleneck anyway. For these kinds of applications, having proper concurrency and IO handling matters a lot more than worrying about whether your loops result in a cache-miss.
The lower level mucking around when you have to do those kinds of optimizations is, IMO, much more pleasant in imperative languages.
Also, have you tried Liquid Haskell? It uses refinement types to let you use the "unsafe" and fast versions of functions to guarantee correctness while also increasing performance.
Like everything else in life, those data structures come with tradeoffs. Accessing an array element is an indexing operation into a continuous block of memory. The indexing is built into the instruction set as an addressing mode, the array's memory is continuous (so better locality of reference for caching), and if you're traversing it predictably, prefetch hardware can being it into cache before you issue the instructions that do the read.
The same operation in a persistent vector is a function call, several pointer dereferences, and a more complex on-memory structure with more overhead. It works elegantly, but it's a completely different (and likely slower) level of abstraction from a simple in-memory vector.
A few years ago, I switched a toy search program away from ImmutableJS and over to naive copying of raw JS data structures. I don't remember the exact performance delta, but it was something like an x10-100 speedup, for code that was otherwise structurally identical:
https://github.com/mschaef/react-matchstick/commit/070802b69...
In this case, I had a goal to achieve, a timeline on which to achieve it, and it was the ability to switch to simpler, closer-to-the-metal data structures that made it happen. Had I needed more optimization, the most logical approach would have been to remove even more copying and rely even more heavily on mutation. This shouldn't come as a surprise, because at their core, these machines are fundamentally built on mutation, and there's a cost to pretending otherwise.
Now, in fairness to the persistent structures, this is something like a worst case scenario for their use - the algorithm is almost entirely dominated by manipulating relatively small data structures without much opportunity for sharing. It was also single threaded, small, and developed by a single developer in a small amount of time, so the organizational benefits of immutability were not apparent either.
If this was a huge redux state shared across a team of 100 developers and updated only a few times a second, I could probably tell a completely different story. It's easy to imagine (based on firsthand experience!) the kind of havoc that can be inflicted on a project with an erroneous update.
I get the enthusiasm for functional programming and persistant structures, etc., but at the end of the day it's just an engineering approach. One of many, and there's room to do the work to choose between them.
I don't disagree with this but that's not what you said initially. You said "this is why FP sucks".
I definitely think that if your work is doing tight-loops where every micro-second matters, an imperative language will usually be the correct approach. I don't think anyone is (or would) argue against that point, including most Haskellers.
However, functional languages do simplify things with network/concurrent applications. There's a reason that something like MapReduce is popular. Something like Spark or Onyx is just simpler to do correctly and work with than trying to achieve something equivalent using C or C++; maybe this is just me.
EDIT: My bad, I was responding to the wrong person, this person never said FP sucks. I apologize!
No, I did not.
That's why you shuffle the list before you sort it :)
It doesn't silently transform O(1) to O(n), the code is explicitly O(n^2) space worst-case. The only 'silent' transformation that could happen here is an optimization to improve performance. Also, I don't know where you got the 'enormous constant time overhead' part.
> Algorithms that are optimal under the mutable data assumption are different than algorithms that are optimal under the constant data assumption.
A normal programmer wouldn't be defining writing their own sort functions. A normal Haskell programmer would understand mutability in Haskell.
> Performant programming in Haskell requires a much more intimate understanding of the underlying architecture than performant programming in, for instance, C++.
It really depends on what you're writing and how much performance you actually need. Implementing a moderate-complexity parallel data processing algorithm in Haskell may result in a slightly slower but much simpler implementation than C++. An implementation of the same complexity in C++ may be slower than Haskell. Writing performant, parallel, safe code for a moderately complex algorithm in C++ is far from easy.
However, I get what you mean. It really is beautiful!
EDIT: grammar.
This wasn't the only case I noticed of highly-rated broken code there. It took me a long time to take this lesson to heart about especially slick-looking code of my own.
I can remember the first code that showed how to exploit IFS, race conditions via symlink, the classic "smashing the stack", RTM's worm.
Beauty of a code to me has nothing to do with the formatting, comments, documentations, but everything to do with the mind that bent it into place. Most of the beautiful code I have ever seen would be classified as ugly, spaghetti, not production worthy.
I had absolutely no idea until now that RTM co-founded y-combinator. I remember him from mentioned in Bruce Sterling's The Hacker Crackdown and Clifford Stoll's The Cookoo's Egg as well as an occasional Phrack article.
https://en.wikipedia.org/wiki/Robert_Tappan_Morris
My current favorite is the one that dumped the SecureROM out of the iPhone 6 via PCI-e: http://ramtin-amin.fr/#nvmedma, http://ramtin-amin.fr/#nvmepcie
I'm partly impressed by the tooling used; most of the coolness (to me) is the author's self-confidence in his hunch that the SoC _didn't_ have its MMU set up properly, and the way he followed his nose in determining that he was probably right.
I still wonder exactly how much was sunk into the project, before it was possible to determine that the MMU was indeed broken. Heh.
https://m.youtube.com/watch?v=HxaD_trXwRE
A good debuggable piece of code explains what it is trying to do by being clearly written and conforming to a consistent and logical model. I don’t think I would ever have invented this type of lexer pattern in Go by myself, but would be very grateful to come across it in a code base I had to fix. Like Duff’s Device mentioned in this thread, it has just the right amount of cleverness without becoming inscrutable.
Also, if you’ll excuse some avuncular pride, my niece and I wrote some code yesterday. She asked me how many times grandma’s clock chimes every day and we ended up with the following Ruby:
Python: 2 * sum([x for x in range(1, 13)])
Haskell: 2 * sum [1..12]
GPs example is perfect Python; every character has meaning, and it's extremely readable even for non-programmers.
What’s so challenging about Ruby is how the language can be abused by library vendors to make all kinds of surprising magic and homegrown syntactic sugar.
Honestly, I don't think this has much to do with Ruby. This a consequence of using reduce or any other higher-order functions, which come from functional programming, and are now available in almost all modern multi-paradigm programming languages (including Python and Haskell).
I you like this kind of constructs, you should definitely learn a functional programming language, you'll love it.
Then t would never be able to overflow s (nor even eat its null terminator)
The things you listed are general concerns in C which are unrelated to both the correct implementation and the suggested changes.
I wonder how much damage that code has caused.
This kind of code is cute, but awful for readability. The author could easily (more easily!) have written the function to be very readable, but went for the cute ultra-compact style instead.
The only reason it's at all readable is that it's solving such a simple problem. Write more complex functionality in that style, and you quickly get a nightmare.
I believe MISRA C outright bans this kind of thing (three assignments with no sequence point), as it has no place in a codebase of real consequence.
I understand that some C programmers pride themselves on being able to read this kind of code (far more impressive than being able to write it), but I see no reason for it in serious software work.