HN Explorer

Ask HN: What piece of code/codebase blew your mind when you saw it?

293 points by Decabytes ↗ HN
Mine was when I learned a subset of recursion called mutual recursion. It was for a pair of function to determine if a number was odd or even.

(define (odd? x)

  (cond


    [(zero? x) #f]


    [else (even? (sub1 x))]))
(define (even? x)

  (cond


    [(zero? x) #t]


    [else (odd? (sub1 x))]))

295 comments

[ 4.0 ms ] story [ 273 ms ] thread
pyjarrett
C++'s "Curiously Recurring Template Pattern"

     template <typename T>
     class Foo {};

     class Bar : public Foo<Bar> { ... };
https://en.cppreference.com/w/cpp/language/crtp
neeeeees
Good answer. OP didn’t specify “blew your mind in a good way”.
Turing_Machine
If "not in a good way" counts, my nominee would be discovering the hard way that a Windows C function declared as type BOOL can actually return 1,0, or -1.

Now, if it had been declared int, I would probably have been on the lookout for it using something other than 1 or 0 as an error condition, but why bother to explicitly invent a BOOL type and then abuse it that way?

jeffreyrogers
Arthur Whitney's compiler for a language "isomorphic to c": https://kparc.com/b/.

Amazing that someone can write correct, fast code like that.

v64
Arthur Whitney is like the Ramanujan of programming. This quote from Hardy about Ramanujan could easily apply to Whitney as well:

"The formulae... defeated me completely; I had never seen anything in the least like them before. A single look at them is enough to show that they could only have been written by a mathematician of the highest class. They must be true because, if they were not true, no one would have the imagination to invent them."

eb0la
A flight simulator called fly8 had an interesting C structure made of pointers to functions. It was a way to declare a device driver in C.

Years later I could tell my colleagues how a device driver/plugin actually worked (before COM/etc) just with this.

Phrodo_00
uefi's boot services are pretty much implemented this exact way.
tcgv
I was mind blown in college when learning recursive programming and being introduced to the recursive solution to the Tower of Hanoi problem:

- https://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_imple...

I remeber thinking "where's the rest of the code? It surely can't be just those lines!"

cyclotron3k
I had the exact same experience too. Really blew my mind.
ivan_ah
Wow this is beautiful. I love it when a complicated process can be simplified into such logical steps, that you know work in isolation, so you know the strategy will also work overall. Thx for sharing!
panda88888
I remember figuring out by myself the reclusive solution to tower of Hanoi back in high school AP comp sci class as extra credit. It was a shock that the solution is so simple and elegant.
trinovantes
Recursion finally clicked for me after learning induction where you assume you already have a working solution for all cases below n and your only job is to implement the nth case
ak217
Fascinating how many of these comments are about recursion. My mind was blown when I realized that recursion is almost never the right solution in practical applications due to memory and stack exhaustion concerns (and that introductory CS/programming courses usually do a disservice to students by treating it as a core concept without mentioning that caveat).

My mind is always blown by the tiny demoscene demos.

nequo
> never the right solution in practical applications due to memory and stack exhaustion

This is not true with a good compiler that does, e.g., tail call optimization, or is it?

ak217
TCO is not supported in most languages that are practical for large scale software engineering projects today. It's also not applicable in many recursion scenarios that they teach in school.

Even in languages where TCO is supported, it's usually not safe to rely on from an engineer's perspective because there is usually no way to reliably assert that TCO is actually applied to any given function.

And again, when they teach recursion in school, they don't normally tell you that it can be unsafe unless your compiler happens to apply TCO or your language explicitly supports tail recursion.

nequo
I see your point about education. Everything has its place and a for loop can sometimes be easier to read. But some algorithms are more naturally expressed recursively.

A lot of languages do support TCO. For example, Scala (used by Twitter), OCaml (used by Jane Street for everything, used as the host language for Coq, originally used to implement the Rust compiler), Kotlin, Haskell, Clojure, Lua (used as an embedded language in many places), Elixir, Perl. Not necessarily your popular bread and butter languages but definitely used in production and available if necessary.

Your point that it is generally difficult to know whether TCO is applied is also well-taken. But in OCaml, you can annotate the recursive function call with `[@tailcall]` to verify that the compiler performs TCO.[1] Likewise, you can annotate your functions in Scala.[2] In languages without such annotations, one can get a sense by memory profiling (possibly not emphasized enough in those intro CS courses).

[1] https://v2.ocaml.org/manual/tail_mod_cons.html

[2] https://www.scala-lang.org/api/2.12.1/scala/annotation/tailr...

ak217
Good points, hopefully this is educational to people reading this. I'd love to see more ergonomic TCO in more languages.
zaccusl
The only time I've ever ran into a stack limitation was real-time embedded systems with a tiny stack.

For modern computers/tablets I have never experienced an issue. Granted, what really matters is your data/recursion level, but even hundreds of recursive calls are not a problem for most applications.

Recursive solutions are usually so much easier to understand than stack/array based looping solutions that they are my go to for things like tree traversals or searching.

ak217
> for most applications

A very subjective statement. Yes, your data matters. Also, the scale and security model/trust boundary of your application matters.

Some actual problems with recursion based algorithms:

* They will break unexpectedly as you scale them up.

* They are not memory efficient, so you won't be able to process much in parallel if your data is non-trivial.

* They can make your service trivially DoSable, so now you have to worry about either sanitizing your input or monitoring your stack instead of just timeouts/rate limits.

I've lost track of the number of times I've had to tweak JVM settings, write up security issues, or just straight up tell people things won't work because an academic researcher decided to implement an algorithm with recursion, and then engineers were asked to productize it.

jansan
Euclidean algorithm as a one-line function:

    function gcd(a,b){ return b ? gcd(b, a%b) : a; }
FartyMcFarter
It also has the nice property that it's tail-recursive.
hinkley
That's brilliantly obnoxious or obnoxiously brilliant. I can't decide which.

If A is less than B it calls itself with the terms reversed.

Trufa
For me it was as simple as when I could start doing functional programming with javascript.

I was so surprised, since I had learned the other way first that it is actually easier to teach functional approaches with teenagers.

arr.map(x => x2) was abundantly clearer than

const newArr = [] for(let i, i < arr.length, i++) { newArr.push(arr[i]2) }

And to be perfectly honest, I might have goofed the for loop.

carl_dr
> I might have goofed the for loop.

Yeah, you did! It should have used semi-colons. (And HN has lost the carets …)

And I agree completely with you.

jansan
The javascript array functions and arrow functions are a gift from heaven.

And to be perfectly honest, I might have goofed the for loop.

You did, the commas must be semicolons :)

mikercampbell
Functional JavaScript has saved me so much. And I'm not talkin Ramda, just functional principles.

I can't tell you how much time I spent chasing a bug when it was a date that was passed by reference.

Rather than trying to keep track, I just return copies of arrays and objects and it's way easier.

Even a simple

``` function yeppers(input) => ({...input, x: 7}) ```

(An overly simple example)

has made things smoother.

dopidopHN
I miss that ability to just pass whatever around easily in JS.

Ok… it’s Footgun prone and callback hell is real.

But I still try to obtain that in other more boring language.

joshxyz
this is a huge milestone in my coding. i remember refactoring a bunch of my code as soon as i learned how to use map functions lol
Rapzid
Something I've started doing along with the functional is fallback assignments and relying on Set operations to be idempotent. This can tidy up by removing a lot of excess conditionals at the cost of some extra operations that are actually VERY fast so in a most cases prob won't be a problem.
fouronnes3
In python the inverse of the zip function is zip. You call it with with * to make list elements into function arguments. So a, b = zip(*c) is the inverse of c = zip(a, b).
[deleted]
(comment deleted)
tmh88j
I think it only works out that way when you're unpacking the same number of variables as there are elements in c, which is the same as (a,b) = c and c = (a,b).

If you tried something like c = (('d','e','f'),('g','h')) and then a,b = zip(*c) you'd get a = ('d','g') and b = ('e','h'). The 'f' that was originally at c[0][2] is dropped so you can't zip back to the original value of c, unless that's how inverses work for this scenario and my math is rusty.

PartiallyTyped
It works only because zip drops extra items. I explained how it works in the reply below.
PartiallyTyped
The expansion of c is a tuple of pairs, zip then creates an iterator (iirc zips get exhausted so iterator and not iterable); the unpack then calls dunder iter of the iterator. The iterator returns itself; and the destructing expands the iterator to exactly two items and binds them to a,b
pklausler
Haskell:

    primes = filterPrime [2..]
      where filterPrime (p:xs) = p : filterPrime [x | x <- xs, x `mod` p /= 0]
KerrickStaley
This uses trial division to find primes, which is not efficient, and I would not recommend using this implementation.

Instead you should use the Sieve of Eratosthenes algorithm. Unfortunately this algorithm is easier to implement in an imperative, eager fashion than in a lazy, functional fashion.

See the paper "The Genuine Sieve of Eratosthenes" for more details: https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

[deleted]
(comment deleted)
[deleted]
(comment deleted)
mikercampbell
Haskell is one of those that I want to get into, but don't have the bandwidth. I'm getting into elixir and even that has had to require a shift of perspective
plingbang
A version that should confuse people not familiar with Haskell even more:

    primes = 2 : filter isPrime [3..]
    isPrime x = all (\p -> x `mod` p /= 0) $ takeWhile (\p -> p * p <= x) primes
primes is a list of prime numbers. It is defined as number 2 and numbers 3,4,5... for which isPrime is True.

isPrime is a function that checks that x is a prime number by taking numbers whose squares don't exceed x from... primes list... and then making sure they all divide x with a reminder.

It only works because isPrime never touches an unevaluated element of primes list. Otherwise, the program would loop.

tromp
Binary Lambda Calculus [1] (produces an infinite list of booleans instead):

    λ(λ1 (1((λ1 1)(λλλ1(λλ1)((λ4 4 1((λ1 1)(λ2(1 1))))(λλλλ1 3(2(6 4)))))(λλλ4(1 3)))))(λλ1(λλ2)2)
[1] https://tromp.github.io/cl/cl.html
nanumbat
My first job in 1987 was porting all of Oracle's source code (entirely in C for 32 bit architectures) to a 64 bit Control Data mainframe.

So, that.

eigenvalue
Was it particularly well written or optimized in very clever ways? Bob Miner was supposedly a beast of a coder from what I've read, so wouldn't surprise me.
nanumbat
Oddly enough, I never met any of the coders. The entire code base turned up on mag tapes from Belmont, CA. I was working in Toronto. I was very much a newbie, so I didn't form an educated opinion on code quality. There were very few bugs, I do remember that.

There was a lot of code, about 1.5 million lines over two version of Oracle, which included a bunch of applications as well as the RDMS.

_whiteCaps_
https://en.wikipedia.org/wiki/Duff%27s_device

  send(to, from, count)
  register short *to, *from;
  register count;
  {
      register n = (count + 7) / 8;
      switch (count % 8) {
      case 0: do { *to = *from++;
      case 7:      *to = *from++;
      case 6:      *to = *from++;
      case 5:      *to = *from++;
      case 4:      *to = *from++;
      case 3:      *to = *from++;
      case 2:      *to = *from++;
      case 1:      *to = *from++;
              } while (--n > 0);
      }
  }
krylon
For a long time, I would at this about once a year and almost understand what it does, but never quite getting it. It felt like looking at a hypercube.

Then I read it was about loop unrolling, and suddenly it clicked.

taneq
And also the fact that C sometimes cares way less than you might think about what goes where. :)
krylon
Afterwards, I started to like Duff's description of his device as being a strong argument in the debate on switch's fallthrough behavior, but that he did not know if it was pro or con.
null0pointer
Another good example of this flexibility in C is the inverse array notation (I think that’s what it’s called, turns out it’s impossible to search because all the results are about reversing arrays).

arr[index] is equivalent to index[arr]

This works because arr points to the memory location of the zeroth index of the array and index is the offset from that memory location. Since addition is commutative so too is the array notation.

justinsaccount
Right, arr[index] is sugar for *(arr+index) which is then also *(index+arr) and index[arr]

edit: fixed escaped asterisks :-)

jbverschoor
That sounds soo dirty though
krylon
It is[0]. Duff's device, whether you like it or hate it, was a performance optimization at least, saying "idx[arr]" instead of "arr[idx]" does not help in any way and will make some people angry or sad.

Contestants in the International Obfuscated C Code Contest will (and probably already have) find delightful ways to use and abuse this syntactical curiosity.

[0] My one-track mind always wants to jump to pirate jokes.

EDIT: If you like to explore this area, I highly recommend "Expert C Programming - Deep C Secrets" (get the pun? There's a fish on the cover...) by Peter Van Der Linden. It's pretty old (it talks about DOS memory models, among other things), but it is a fun deep dive into the murky corners of C. I wish there was an updated version and/or books covering other languages in that style.

taneq
> Contestants in the International Obfuscated C Code Contest will (and probably already have) find delightful ways to use and abuse this syntactical curiosity.

The OCCC is where I learned about this in the first place!

Surely it counts as useful if it could be used to confuse The Enemy. ;)

bjconlan
Yeah the duffs device did it for me too. I remember reading it in some game programming book but shocked to see it used in qt/embedded for it's software rendering.

This is up there for me or there's also that amazing recursive template class for n-dimentional vectorspaces written by Tim Sweeney. I can't find the page anymore but there is reference to it in the archive https://www.flipcode.com/archives/Unrolling_Loops_With_Meta-...

Arcuru
Everybody mentions this, and what's great is that it is a pretty natural solution to a lot of problems. I remember coming up with a version of it while writing an optimized prime-sieve[1], and was surprised when I later learned that it was some named technique.

In addition to just the basic loop-unrolling (which I'm pretty sure you usually don't need to do by hand with modern compilers), it works really well when you need to jump into the middle of a pattern. Like if you're sieving primes in a wheel-factorized array.

[1] https://github.com/patricksjackson/primes-cpp/blob/master/pr...

  // Here we're only checking possible primes after wheel-factorization
  switch ((p.second/num)%30) do {
    case  1: target->set(n); n+=num*6;
    case  7: target->set(n); n+=num*4;
    case 11: target->set(n); n+=num*2;
    case 13: target->set(n); n+=num*4;
    case 17: target->set(n); n+=num*2;
    case 19: target->set(n); n+=num*4;
    case 23: target->set(n); n+=num*6;
    case 29: target->set(n); n+=num*2;
  } while(n <= high - range.first);
fractalb
Shouldn’t it be

*to++ = *from++;

jcranmer
In the original code, actually, no, incrementing "to" was not desired. The "to" was pointing to a hardware memory-mapped register, and it needed to copy to the same memory location each time.
johnthescott
amen. seems like back in the day that "reg1 = *pc++;" would have been the fastest op in a computer.
fferen
Data from functions:

(define (cons x y) (lambda (m) (m x y)))

(define (car z) (z (lambda (p q) p)))

(define (cdr z) (z (lambda (p q) q)))

mtlmtlmtlmtl
If you like the lambda cons, I recommend checking out Church numerals, representing numbers as functions in lambda calculus. I don't remember all the operations off the top of my head, but iirc calling one number with another is equivalent to multiplication, which I always found beautiful.

Then if you really want to go down the rabbit hole, there's SKI, which is lambda calculus without a lambda operator, just 3 named, curried functions(S, K and I, but I is techically definable in terms of S and K). Any function that can be expressed in lambda calculus can be expressed in terms of calling these various functions with eachother as arguments.

Assuming LAMBDA is automatically curried, to save myself some typing:

  (define (k x y)
    x)
  (define (s x y z)
    ((x z) (y z)))
  (define (i x)
    x)
Alternatively, I can be defined as follows:

  (define i (s k k))
SKI is implemented in the Unlambda esolang, with some additional functions defined for IO and convenience
sicp-enjoyer
This really surprised me, until I implemented a lisp.

If variable environments are implemented as hash tables, you're just making a pair out of a hash table. In other words, it's basically equivalent to:

    function cons(x, y) {
        return { "first": x, "second": y };
    }

    function car(x) { return x["first"]; }
    function cdr(x) { return x["second"]; }
ihaveabeardnow
I once saw a 20k line Java source file, being used in production... no it wasn't generated. that blew my mind.
marginalia_nu
Now that's job security!
intelVISA
Maybe they really liked inlining?
jansan
And loop unrolling. Performance must have been mindblowing.
tabtab
We have that in C#, it's call LINQ. In the wrong hands it kills kittens.
pawelduda
More of a shell snippet, but removing duplicate lines with awk is one that comes to my mind:

awk '!seen[$0]++'

fegu
The doom square root trick. Reducing an expensive function to almost nothing with low error. Many writeups on the web far better than I could give.
jesse__
I think you mean quakes fast inverse square root? Not aware doom had a clever sqrt routine, but I would be happy to be wrong!
pjscott
You’re right. Doom used fixed-point math; at the time, hardware floating-point units were far from ubiquitous on the computers people wanted to use to play it.
hinkley
Doom redefining a circle to be 256 degrees, so that the angle calculations fit into one byte.
[deleted]
(comment deleted)
fegu
Swapping two variables without a temporary using xor.
nicklaf
Also: zeroing a register by XORing it with itself.
Am4TIfIsER0ppos
Setting a register to all ones by comparing with itself. Much less needed but I've done it a few times.
bob1029
C# as of 7.0 makes this possible:

  (a, b) = (b, a);
sicp-enjoyer
How is it implemented?
Ferrotin
Generally speaking it will get compiled to something like SSA form and the outcome depends on the overall dataflow and what optimizations happen.
valleyer
Aw, that's an unsatisfying answer!

I'm a total .NET noob, but this attempt in Compiler Explorer shows it not using the xor trick.

https://godbolt.org/z/jhzqxEKzT

Maybe I need some extra compiler flags or something.

moonchild
The xor trick has no practical value. Sorry.
sicp-enjoyer
I agree it isn't normally helpful on a modern computer, but that's a strong statement. What if you need to swap large storage spaces with no extra memory? Isn't there still old hardware out there especially in aerospace that could benefit?
lscharen
It was useful in single accumulator processor architectures since it could avoid one memory store.
Ferrotin
That would just load each global variable into registers and write them back to memory, swapping them.

If the compiler had decided to put two locals located already in registers, and had the swap in a branch, like so:

    if (foo()) {
        bar();
        (a, b) = (b, a);
    }
Then the registers might get swapped with an xchg instruction or something, I don’t know. The compiler’s goal is to have pipelined execution be as fast as possible, so there’s no way it’s going to use bit-mangling operations that would get in the way of that.
Someone
> I’m a total .NET noob, but this attempt in Compiler Explorer shows it not using the xor trick.

It better not. The CLR trick introduces a data dependency that slows down the code on modern CPUs.

Compilers sometimes also can compile this down to zero instructions. Nothing says the variable-to-register mapping has to be constant in a single function.

throwamon
It's been possible in other languages for ages, and some of them don't even require parentheses or a semicolon!
djmips
humble brag. I had that on an interview once and I'd never heard of the technique but somehow a inspiration from the heavens and I was able to invent it on the spot. Sometimes knowing something is possible is a great motivator (plus the time pressure of the interview)

But I guess what really happened is that when you come up writing assembly code at a low level it's a lot more obvious when you've been neck deep in bits, shifts, and logic ops all day.

jph
The Legendary Fast Inverse Square Root with "Voodoo Black Magic"

https://medium.com/hard-mode/the-legendary-fast-inverse-squa...

KIFulgore
That one still kills me. By Carmack's comment, surprised him too.
[deleted]
(comment deleted)
aliswe
a tangential question is whether ID software actually had any right to license Q3A under GPL if they had not authored this piece of code
swyx
it isn't rocket science, but https://github.com/fkling/astexplorer significantly raised my standard of what a readable, modifiable, nontrivial react/redux codebase could look like. bonus that astexplorer is basically used by everyone in the js tooling ecosystem
[deleted]
(comment deleted)
treffer
For codenbases... Objectweb ASM blew my mind.

It's a library to read/write java class files. The core at that time would fit into 2 java files.

It was a reader and a writer built around a visitor pattern. At that time apache bcel was also big, a library to build in-memory class file representations which you would then manipulate. ASM allowed you to do many transformation without ever holding the whole file in memory.

ASM also had an in-memory representation as an add-on. It was all nicely layered and the core was just a marvelous small piece of code, with incredible low memory consumption.

pierrec
I've read and re-implemented a lot of stuff by Inigo Quilez. Much of it is ingenious but eventually straightforward once you get the hang of it. I still find this particular snippet magical:

https://www.shadertoy.com/view/MdB3Dw

Well, the code itself is simple GLSL. The math is (and I have not verified this) not that complex either, as I believe it's all about integrating the raytracing equation for a moving sphere over the time variable. I guess what I find most impressive is just the fact that it works and that someone even thought of doing that. I also think this is currently the only example of this method being used anywhere, and it might mostly stay that way because the method might not be super generalisable.

bob1029
> I believe it's all about integrating the raytracing equation for a moving sphere over the time variable

In all of the samples there is some iteration constant you can adjust. Take this below a certain threshold and things get really interesting. You can almost reason about how it's all working mathematically by plugging in different iteration counts.

djmips
It sounds similar to a technique we used in video games to solve collisions so you didn't miss the interval - using quadratics to solve the swept sphere.

In fact so much of what is on shadertoy looks very familiar to video game 'game physics' programmers because a lot of it is related to collision detection. See the Orange book on real-time collision detection (Christer Ericson) for a lot of good code.

pierrec
Thanks, your description of the technique is simpler and probably more accurate than what I guessed - no integration required. The author gives a similar hint in the comments.
mjfl
He's amazing.
davchana
Mine was super basic, one of many, that a 0 DAY can push an excel date a day behind, so DATE(2022, 10, 0) means Last Day of October. No need to keep an array of which month has 30, 31 or 28/29 days. Simple DATE(2022,3,0) gives the last day of February.
jesse__
Handmade Hero.

Before warching Casey program, it had not occurred to me you could sit down with a compiler and write an entire video game from scratch.

Then, I found out Jonathan Blow sat down and wrote his own compiler, followed by an engine, and now has a game in flight.

It's a truly incredible what these guys (and their teams) get done.

cloogshicer
Hey, could you recommend an episode of Handmade Hero to get started with? Should you just start at the very beginning or somewhere later in the process?
jesse__
Its a pretty big comittment at this point, but if youve got the time I'd recommend starting at the beginning. There's also an annotated episode guide if you wanted to learn about a specific topic in a more targeted way
gleenn
Reminds me of the author of the K programming language, Arthur Whitney, wrote is own language, then database, and now he's working on his own OS.
hoosieree
Speaking of K, a way to generate the first N+1 Fibonacci numbers is what made me take notice of the language:

    N(|+\)\1 1
I'm not sure where I first saw this snippet (maybe in the Kona documentation) but it stuck with me enough that I was able to recreate it from memory.
0xbadc0de5
Big fan of both Casey's and Jon's streams.
eps
Did Blow really finish the compiler? Got a link?

Last time I checked (a couple of months ago) there wasn't even a formal language spec yet.

jesse__
AFAIK it is done enough to be in closed beta
badpun
It's been in closed beta for a couple years now IIRC. His approach is very different from what's prevalent in the industry today - he prefers to only release a product that's reasonably well done, instead of frustrating his audience with a buggy moving target. That's why the language is in its seventh/eight year of closed development at this point.
adrift
Definitely this. Lots of good practical advice in his videos too.
thoughtFrame
I've been thinking a lot lately about those two examples related to experience in programming, domain knowledge and producing good work. Jon had written 12 compilers by the time he got to Jai, and many more games before his Sokoban, and he started making games as a contemporary to Abrash, in an era where you had to really learn what was going on to produce something good. That knowledge from constrained environments adapted really well to the increasing power of computers (both in terms of processing power and ergonomics), whereas coming at it from a modern programmer's POV you can get away with very little in terms of know-how (which is both good and bad)

I'm working on trying to reach their level (it is reachable) but I sometimes feel like I started with a handicap of comfort from modern OSs and tools

myself248
I'll see your Handmade Hero and raise you "But without a compiler".

Specifically, Roller Coaster Tycoon, hand-written in x86 assembler by Chris Sawyer.

jesse__
Damn is the source code for that available somewhere? I loved that game.

Edit: guess I could just download it and disassemble ;)

unsafecast
Not really. It's actually more difficult than disassembling a C codebase. Chris used a macro assembler and wrote _a lot_ of macros. You'd only see what the assembler expanded, but you'd have no idea how the code _actually_ looked like.
jesse__
Right, thats what I assumed. TIL!
musicale
Assembler is low-level C. Also probably easy to learn compared to Rust. ;-)

What impresses me though are old Atari games that were implemented in hardware without a microprocessor.