Hacker News Books

I learned functional programming many years ago, by reading the book COMMON LISP: A Gentle Introduction to Symbolic Computation by David S. Touretzky [1]. Incredible book, super beginner friendly; the chapter on Recursion in particular is one of my favourites. :)

[1] https://www.cs.cmu.edu/~dst/LispBook/book.pdf

This is basically the plot of the new Blake Crouch novel Recursion - except the "device" requires you to die while reliving a past memory (after which you travel back in time to the moment the memory occurred).

Recursion by Blake Crouch! Biggest mindf* of the 2010's, hands down.

I really enjoyed this SciFi book - Dark Matter: A Novel

In this world he’s woken up to, Jason’s life is not the one he knows. His wife is not his wife. His son was never born. And Jason is not an ordinary college physics professor, but a celebrated genius who has achieved something remarkable. Something impossible.

https://www.amazon.com/dp/1101904224/ref=cm_sw_r_cp_api_i_HY...

Another good one from the same author - Recursion: A Novel https://www.amazon.com/dp/1524759783/ref=cm_sw_r_cp_api_i_G0...

"Recursion", Blake Crouch: That’s what New York City cop Barry Sutton is learning as he investigates the devastating phenomenon the media has dubbed False Memory Syndrome-a mysterious affliction that drives its victims mad with memories of a life they never lived.

"Daisy Jones & The Six", Taylor Jenkins Reid: Everyone knows Daisy Jones & The Six: The band's album Aurora came to define the rock 'n' roll era of the late seventies, and an entire generation of girls wanted to grow up to be Daisy. But no one knows the reason behind the group's split on the night of their final concert at Chicago Stadium on July 12, 1979 . . . until now.

"The Silent Patient", Alex Michaelides: Alicia Berenson’s life is seemingly perfect. A famous painter married to an in-demand fashion photographer, she lives in a grand house with big windows overlooking a park in one of London’s most desirable areas. One evening her husband Gabriel returns home late from a fashion shoot, and Alicia shoots him five times in the face, and then never speaks another word. Alicia’s refusal to talk, or give any kind of explanation, turns a domestic tragedy into something far grander, a mystery that captures the public imagination and casts Alicia into notoriety.

> Recursion Fairy

I mentioned this elsewhere but figured I'd bring it up here since you're the author.

I've tried explaining recursion in a lot of ways like this, such as "just assume it will work", "trust yourself", and "turn off your brain". (The first two are paraphrases from Matthew Flatt, the latter is from Will Byrd.)

I think "Recursion Fairy" is my favorite way to phrase the same idea. I think there's something about the nature of invoking a sense of magic in the phrasing that might help people really believe that it's okay to just let the recursion do its thing and not think about it too much. I'll definitely be using "Recursion Fairy" when (if) I end up explaining recursion again.

Thanks for making your material available for free! Cheers!

Gosh, I have a few!

Fistly, wavelet trees! Wavelet trees with something like RRR encoding for the bit vectors lets you work with massive datasets in positively tiny space and constant time. They're not even expensive to construct! My favorite introduction to the whole space of rank/select-friendly structures is Alex Bowe's tutorial: https://alexbowe.com/wavelet-trees/

I constantly agitate for people to realize that we now have an algorithm for O(n) generalized sorting. It's called discrimination sort, and while it's a complex subject its quite elegant once you internalize the algorithm. There's a talk by Prof. Henglein here: https://www.youtube.com/watch?v=sz9ZlZIRDAg

2017 saw the recommendation of a truly phenomenal approach to indexing data, using simple leaning structures. These indexes are poorly explored, there's still a ton of headroom here, but the paper is an incredibly cool read and very approachable: https://arxiv.org/abs/1712.01208

Another really cool family of algorithms and associated structures in distributed systems is CRDTs. They're poorly understood, but in research they have largely superseded operational transforms. The Wikipedia page branches off into lots of good research: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...

If we slightly broadened the lens of what is an algorithm, my favoriate category-theoretic approaches to solving problems include Recursion Schemes which are a technique to totally separate the specification of recursive algorithms over data structures from both the structures and the code that the algorithm runs to compute a result (Patrick from Github has a great series on them here: https://blog.sumtypeofway.com/). I also love the modern and rapidly growing "Ghosts of Forgotten Proofs" as a way to let the compiler assert you've properly built and/or terminated values: https://github.com/matt-noonan/gdp-paper/releases/download/j...

Below list are some of my favorite books overall that I didn't see mentioned.

---Non-software related

How to win friends and influence people -Dale Carnegie (The definitive guide to helping you work better with people, truly great book, should be required reading)

Blink- Malcolm Gladwell

Godel Escher, Bach - (Recursion, but not from a software perspective. Its a glorious book that will change the way you think about recursion.)

Hitch Hiker's guide to the galaxy, - Douglas Adams (Glorious book that is a fun read, when you need a break pick this up and laugh hard)

Foundation Series - Assimov (Great stories from one of the best sci-fi writers ever)

-------------------Software related
Code Complete
Concrete Mathematics
The Art of Computer Programming
The Design of the Unix Operating System
Introduction to Algorithms -Cormen
Design Patterns Elements of Resusable OO Design -Gang of Four

> 2) Recursion & Tail Call Elimination: How would one solve this problem in any other language with a stack? Memory concerns don't just exist in the browser.

Be honest now, did you actually read the article ;-) because it answers that exact question.

---

> Languages with Tail Call Elimination will recognize this situation and basically rewrite the function into a while loop. Since this is a low-level function, we should do the same, but sometimes it's hard to know when you're recurring dangerously.

---

> but it won't go away just because you don't like it.

I didn't like it and it go away. Out came Dart. I like Dart. All worked out well so far.

> You can implement matrix exponentiation recursively however.

And tail recursively, and – going full circle – you can convert that tail recursion into iteration (see [1] for example, using techniques described in [2]).

[1] Iterative fast-power implementation in Python
https://github.com/tmoertel/practice/blob/master/libraries/t...

[2] Recursion to Iteration, Part 1: The Simple Method, secret features, and accumulators
http://blog.moertel.com/posts/2013-05-11-recursive-to-iterat...

I am confused, modern Science Fiction has gone way beyond Cyberpunk. It takes into consideration what having real AI might mean for the world, or what a post-scarcity society might look like, or how horrible/painful the transition to that post scarcity society might be, as all the current holders of power do everything they can to maintain their grip on the world.

Modern science fiction describes worlds where people can clone their consciousness 50 times over, where it is possible to adjust the perception of time, and where plans take millennia to come to fruition.

Accelerando by Charles Stross. Recursion by Tony Ballantyne. Down and Out in the Magic Kingdom by Cory Doctorow.

Yes, these are all evolutions of previous ideas, but Science Fiction has always built on itself.

So, it's been more than half of your sentient life since you tried reading a book that was written 200 years ago... and you're prepared to write off all of fiction as a waste of time? I am begging you to see if perhaps you might have a better experience today with a more contemporary book that frankly isn't kind of dull.

I urge you to try audiobooks. There still exists a stigma that it's not "real" reading, but that is like discussion of "real" men - absurd. Audiobooks are a joy.

My personal favourite is Cryptonomicon by Neil Stephenson, but heck, Ready Player One, Recursion, Delta-V, Walkaway by Cory Doctorow... just give it a shot.

Like learning about the physics of the very large and very small, the study of computational extremes will change your intuitive sense of the laws governing the universe -- especially if you are a working programmer and used to interacting primarily with tractable problems.

At U Maryland I took a course from Bill Gasarch on computation. The first thing he said to the class, famously, was "I'm going to show you that there are problems that are impossible to solve. Then I'm going to show you some problems even harder than those. And by the end of the class, you will no longer laugh at that joke." He went on to show us the Halting Problem (an impossible-to-solve problem), then problems that one still can't solve even given an oracle for the halting problem. In other words: even if you could solve the Halting Problem, you still couldn't solve these other problems. And even if you could solve some of those problems, there are others you still couldn't solve, etc. Ultimately, we learned about Recursion Theory, which examines this implied infinite hierarchy of "impossibility".

Another interesting -- and, really, somewhat devastating -- conclusion one can draw from Recursion Theory is that tractable problems are incredibly rare. From a cardinality standpoint, the set of solvable problems is vanishingly small compared to the universe of unsolvable problems. It just so happens that many problems we actually care about are solvable and tractable. But, numerically speaking, this is incredibly unlikely. (In other words, if the distribution of problems we cared about were actually uniform, we'd be able to solve basically nothing we cared about.)

Exact exponential algorithms -- those "right at the edge of tractability" -- open one's eyes in similar ways. Why do we end up with magic numbers x, where the known lower bound seems to be O(x^n) where 1 < x < 2? Will we find underlying mathematical constants here that we don't yet know about? I think every day working developers would do well to learn about these tractability "edge cases".