Long ago, on Svalbard, when you were a young witch of forty-three, your mother took your unscarred wrists in her hands, and spoke:
Vidrun, born of the sea-wind through the spruce
Vidrun, green-tinged offshoot of my bough, joy and burden of my life
Vidrun, fierce and clever, may our clan’s wisdom be yours:
Never read Hacker News
But Hacker News has read of you, in their snicker-slithing susurrential warrens, and word has spread...
susurrus or susurration is a very literary word for a whisper/whispering. The usual adjective would be susurrous or susurrant, rather than susurrential, but in any case it would mean “full of whispering sounds”.
In case folks miss the link at the top of the article, this is translated from an old 2017 post by Aphyr.
That post was in Haskell, where it's not too surprising that you can do serious computation inside the type system.
This new post translates the ideas to TypeScript, which is more widely known, and which I once heard described as having "accidentally Turing-complete" types:
The part about using the typescript language server to compute the solution, and the protagonist claiming the code is "concise" because only 4 lines of javascript were generated, was absolutely brilliant. Cracked me up at least.
Glancing at the actual code, I admit I'm with Criss in my ability to follow the logic, but it doesn't look like a direct translation from Haskel types to Typescript types either.
I know my mind is decidedly poisoned when I could follow the type definitions perfectly, and they reminded me of certain types I have written myself… ah, TypeScript, what have you done to me…
Deep diving into lib.d.ts and DefinitelyTyped dealing with the weird boundary space between poorly typed JS and strongly typed TS can teach a lot these days.
Also, being able to recognize the Peano S-function on sight (and thus uses of Church-Peano numbers) is a fun part of that wizardry. (Maybe not necessary to remind the usefulness of the Lambda Calculus canon on a site named after one of the most famous combinators.)
Here[0] is the open issue about TypeScript being Turing complete. The current most recent comment[1] is showing the type system parsing its own type syntax. Of course there have been many parsers written in the type system since template literal types landed, but I found this one particularly amusing.
This post also mentions "Vidrun," which features heavily in Aphyr's posts. And the interviewer in this post recognizing the situation they were in had me literally laughing out loud!
Were this true it would be terrible, because Turing-completeness necessarily includes non-termination. This would mean that a compiler would crash, or get stuck in an infinite loop.
It is true and it is terrible. Woe to be a programmer. The Church-Turing Theorem implies it is almost impossible for any languages exhibiting recursion to not be (Church-)Turing Complete. It is easy to forget how deeply, darkly, and deceptively simple the Lambda Calculus is. It is easy to forget that anywhere you may splice in something that even gently resembles the Lambda Calculus you may draw out the frightening runes of the many eldritch combinators many of which are indeed subject to accidental infinite recursion and The Halting Problem. (Including the infamous Y combinator.)
I have seen the Typescript "computing this type lead to what appeared to be infinite recursion and I gave up" errors. The compiler is well built, it mostly does not truly crash in an exceptional case like that, but it does have to use hard, practical heuristics to avoid getting stuck in infinite loops (including harsh stack depths and calculation timeouts for type checking).
https://3fx.ch/typing-is-hard.html is a neat summary, and yes the situation is worse than most programmers would guess:
Most industry languages, including "boring" reliable ones like C++, Java or Rust have _undecidable_ type systems;( and quite a few are unsound as well.)
This doesn't mean type systems are useless! But as GP said there are tradeoffs, and suspiciously many language designers gave up "clean" properties like guaranteed-terminating compiler, or you know actually guaranteeing run-time safety...
yes, all turing complete type systems make it possible to define type structures that would cause infinite loops, but typically they are able to detect this and refuse to compile
“Oh, right.” He blusters a non-termination argument at nobody in particular. “That’s why we usually think in subsets of Haskell where types don’t have bottom values.”
Yes, this is why unsafe exists. It tells the typing system to take a hike and let the natural Turing completeness of types happen. Trying to explain to people who don't understand higher order functions that types are the first rung of an infinite ladder of meta languages is like trying to explain the colour blue to nematodes.
If you want to see some more legs on TypeScript type-level logic, check out this SQL database as Typescript types: https://github.com/codemix/ts-sql:
import { Query } from "@codemix/ts-sql";
const db = {
things: [
{ id: 1, name: "a", active: true },
{ id: 2, name: "b", active: false },
{ id: 3, name: "c", active: true },
],
} as const;
type ActiveThings = Query<
"SELECT id, name AS nom FROM things WHERE active = true",
typeof db
>;
// ActiveThings is now equal to the following type:
type Expected = [{ id: 1; nom: "a" }, { id: 3; nom: "c" }];
I remember reading the original version and thinking "Ah, this would be so much more grokkable if only I knew Haskell"... Delusions of grandeur are a marvelous thing!
So he wrote all that for the typescript lsp to respond with the answer, but when it compiles down it's nothing? And we're using runes as variables just because?
That is pretty neat, and silly.
I also think it highlights my natural aversion to static type checking in dynamic languages. I know that I could get sucked into writing a bunch of code for the checker, instead of using my energy for making the application work.
The runes are mostly "just because", but there is a reason.
Ideally, I would have written:
type Nil = unique symbol
Which would ensure the Nil type wouldn't match with anything but itself. Unfortunately, the compiler doesn't allow unique symbol other than on const variables initialised with Symbol(). So I needed some meaningless symbols.
I could also have done
type Nil = "nil"
But then it would have looked like the string meant something.
> I know that I could get sucked into writing a bunch of code for the checker, instead of using my energy for making the application work.
“Making the application work” is only half the story. Making a large application stable and maintainable is only really possible with static type safety, IMHO.
brilliant article - the TS therein is type-hints basically, helping the coder program to chess spec. so yes, in that scenario it's not generating JS (functions etc) lol
this is why i love ts when not working for a megacorp. when the ts gets too cray i just nope out. throw an any or as in there and get on with my day. wouldn't pass a code review but i don't care
IMHO it’s worth learning to properly type those cases, otherwise you never really know which parts of your application are actually being type checked.
Personally I also find coming up with the correct types to be gratifying if they’re a little tricky.
This is a jab (insult), and I've flagged it, but I am also curious. If you could, please describe the qualities of a "bootcamp" grad by which you recognize them?
Edit: especially pertaining to type inference, I guess?
People who think code reviews are a thing imposed upon them by higher ups trying to make their job harder and not things designed to make their job easier don't understand how dev works at scale.
People who would do things that "wouldn't pass the code review" for smaller companies are a primary reason so many smaller companies get hard-fucked when they have to scale.
Arbitrarily deciding "this is too much work for me to do, so I'm going to take a shortcut" may not be the sign of a bootcamper, but it's certainly the sign of a shitty dev.
Either way, it's not someone I'll ever work next to. Elite teams don't hire people who think like that. We hire junior devs who are like "I write idempotent commits with good titles and descriptions, and I and use strict typing everywhere." Because it's easier to be teach them "actually, nobody's ever going to read your description. You can usually leave it out. You could use 'any' here. Just ticket it to be fixed so you can replace it later."
Point is 'any' shouldn't pass a code review without someone asking "why'd you use 'any' here." If you have a great answer, it will pass the code review.
FWIW I do both. I work for a top tier tech company and I write pretty commit messages, test my code, and all that jazz. But for the side-project I do at home? You bet I'm cutting corners.
I also think the guts of a TS function don't matter much though. Write a test to confirm the behavior is correct, and then make the return type and argument types correct so that people can call it without hassle. If you need to use 'any' or 'as' inside the function, then go for it.
I'm having trouble grasping what this has to do with bootcamps. Isn't that the totality of the value of your original comment, implying that you had some trick for identifying bootcamp graduates?
Pretty sad that computations on types look like C++98 in Typescript when C++ itself has moved on to have much more concise ways of performing computations on types in C++11 and 14 (see boost hana).
Interestingly TypeScript compiler doesn't use types for compilation (that's why you can have esbuild that compiles Typescript without understanding the type system). That is the end result of type computation is... Nothing, always, just like in OP.
Template metaprogramming is all about code generation. You would expect them to look different.
The way I think about this is that type computations can be used both for type constraint checking and for code generation. In that sense, C++s template metaprogramming system is a superset of TypeScript's, which can only do checks as you pointed out correctly.
I’d say generally the opposite is true. Most commercial software I’ve worked on typically contained only simple typing—discriminated unions are about as complex as it gets—and it’s more of a problem that people get lazy and start using “any” too much than they go overboard.
Where complex types can be a problem is when working with open source libraries, especially when the types are community-developed, separate to the library itself. The library API may not be particularly amenable to easy typing, and the community types can end up being rather confusing, especially to people who developed neither the types nor the original library.
I tell my fellow developers at work: "Any is banned. If you want any, use JavaScript, and we don't use JavaScript here. Perhaps you haven't heard about unknown?"
In my experience, 90% of the time when a developer uses any, they just don't know about unknown. 9% it's because they are lazy. 1% is because you are implementing something from an imported library, and they fell into the other 99%.
This is a good signal that foo maps over dict in some generic way that cares more about its dictionary-ness than its values. Sure, unknown works in that position too, but at least IMO the “doesn’t care” bit is more informative than “doesn’t know”. The latter might imply more type narrowing will happen than is the case.
The problem with that is that when consuming of the dictionary, “doesn’t know” is actually more appropriate. If you then access Object.values(foo) in your method you are given an iterable of anys which is unsafe.
If the function is doing something with the values which is unsafe, sure. My point was the more relaxed constrain on the type signature can be used to imply it’s only concerned with the dictionary’s keys.
Coming back to this after the other thread cooled down a bit lol - to me, unknown actually implies that the function doesn’t care about the values more than any, as the compiler will enforce that they’re unused.
And in any case, I’d almost always lean towards the option with stronger type safety guarantees. Especially in a team environment when someone else may be modifying your code later. As a convention, I almost never use any.
To me `unknown` signals an intent to know, as in “I don’t know yet” (or put another way, “I don’t have any prerequisites for accepting this value, I can and will narrow it as appropriate”). In a codebase that otherwise takes type safety seriously, `any` in a type parameter (again to me) means “I don’t have any type narrowing agenda for this thing, it’s along for the ride and coming out the other side the same way it showed up”.
I’m not being lazy? I am taking extra time and expending extra energy to make sure the metadata I put in code is as informative as possible. In this use case `any` carries more information. I use `unknown` in place of `any` exactly as it’s intended wherever I’m able.
Okay I'll stop being a jerk and engage in good faith. I'll assume you think this is a valid use case for any and it communicates something important.
My counterpoint is this: communication involves two things, someone stating a message and someone receiving a message. You are doing part one. Is part two occurring? It may be because of certain conventions in your codebase or team, but I've personally never seen any used in that manner ever, so I would not receive your intended message.
If I were in the same situation I would use unknown and add a comment stating that the type is of no importance since I'm only worried about the keys. That way my message is clear and I prevent future developers from having to debug code where they assume the value is of a certain type and start accessing parameters and methods that do not exist.
Valid feedback. I even thought of adding it myself, because implied stuff isn’t obvious. I felt it worth communicating because there’s value in what’s implied that isn’t available in the type system. To the extent I have team members consuming the same code, I would definitely communicate the intent. To the extent I have reviewers who read the code, I do discuss it.
To the extent this is in a type parameter position, the onus is on the person writing the function signature and… well if they don’t want a footgun, they have every opportunity to not gun their foot. But that’s entirely opt in by the time they’ve reached that point.
Completely aside from these details, thank you for stepping back and discussing this in good faith. It made a discussion that was going badly feel at least like communication. I appreciate that, and I’m glad to land at a place where we’re not necessarily on the same page but we’re at least recognizing we have similar priorities. Cheers!
That’s pretty much the intent of the constraint. I don’t have time to sit with a type checker right now, but I don’t think we disagree as much as you might think. I arrived at this from years of trying to find the best way to express types which are as strict as possible with as much clarity as possible.
Unfortunately the object type is basically any non-null value, as is {}. They both intuitively mean what I want. They also inherently allow PropertyKey keys, which is effectively Record<string | number | symbol, any>, which is looser than the “dictionary” type I often want to accept in these scenarios.
A better question (for me, and maybe you and maybe all of us who want type certainties) is why we even accept dictionaries in object shapes when Map is the obvious expression of that type. I’ve repeatedly wanted that and shied away from it because it requires too much change for very little gain.
I think with Map the answer is somewhere between momentum ("we've always used objects as dictionaries") and some misapprehensions easily shifted with basic caniuse statistics. Map still feels "too new" to some developers, despite being ES2015 (8 years old now!) and available in every browser that supports the arrow operator for functions has Map (and Set) out of the box (no need for polyfills in 2023, ever).
Probably the only other reason I've seen is "JSON interop" is "hard" because Map doesn't natively serialize. I think `new Map(Object.entries(oldDictionaryObject))` and `Object.fromEntries(someMap.entries())` are sufficient for most serializer boundary cases (even without feeling fancy and doing that as a true JSON revivifier/resolver pair).
As an addendum if the function only needs the keys I would possibly just have the parameter be a string[] that expected the user to call object.Keys to pass to.
That way the function isn't asking for parameters it doesn't really care about.
Though I do get the appeal of having the function call object.Keys if it's called frequently so as not to have to sprinkle that call everywhere.
Yeah unfortunately it’s ergonomically A Thing to just accept object as input even if you only care about keys. Otherwise I’d have the exact signature you describe.
The distinction is just because you "don't care" about the values right now, nothing stops the next developer (including future you) from needing the values.
So now you've gone from not caring to "enabling someone to shoot themselves in the foot" if they don't read the types of the parameters carefully. That's the difference.
The case I was trying to convey doesn’t narrow the actual type for anything outside its own function body. Any footgun that exists after the function call already existed before it. It just implies “I’m only looking at your keys not your values”.
This is a good example of how `never` is treated as `never`. Everything is assignable to the bottom type and intersecting with it will always be the bottom type, by definition. It’s also a good example of how the top type `any` casts to whatever you choose, because that’s also by design. Both types are vacant, the bottom type is infectious. That’s a good thing. And it works the same way with `unknown`, which it also should because once something is known to be part of the null set it should stay known as the null set.
Other way around: everything is assignable to the top type (`unknown`), and the bottom type (`never`) is assignable to everything.
> It’s also a good example of how the top type `any` casts to whatever you choose
Which is precisely why `any` isn't the top type: if you allow `any`, then types no longer form a lattice, and there is no bottom or top.
If you restrict yourself to a sound fragment, then `unknown` is the top type. Compare `(x: unknown) => boolean` (two inhabitants up to function extensionality) to `(x: any) => boolean` (infinitely many inhabitants).
> And it works the same way with `unknown`, which it also should because once something is known to be part of the null set it should stay known as the null set.
But `unknown` isn't the null set: it's the "set" (insofar as we're pretending that types are sets of values, which isn't quite true) of all terms.
> Other way around: everything is assignable to the top type (`unknown`), and the bottom type (`never`) is assignable to everything.
Yep, sorry that’s what I meant.
> Which is precisely why `any` isn't the top type: if you allow `any`, then types no longer form a lattice, and there is no bottom or top.
I’m not sure I understand.
> If you restrict yourself to a sound fragment, then `unknown` is the top type. Compare `(x: unknown) => boolean` (two inhabitants up to function extensionality) to `(x: any) => boolean` (infinitely many inhabitants).
Sure, but I was referring to an exception I make for ignored parts of a type, in a type param. This example would be more analogous as:
Which I hope makes my exception more clear, even if you don’t agree with it. It hopefully communicates that x is of interest and rest is not.
> But `unknown` isn't the null set: it's the "set" (insofar as we're pretending that types are sets of values, which isn't quite true) of all terms.
I was referring to never as the null set. Once you narrow anything—any, unknown, etc—to never, you can’t widen it to anything (without an unsafe cast of course).
I gathered what you meant. My point is what stops the next developer working on your codebase from adding code in the body of your function that accesses the values of the object in an unsafe way?
Use "unknown" and TS complains that you're treating something as an object.
Use Object.defineProperties and TS complains because that stuff is invisible to it after how many years?
I think you're right, of course, but TS is hardly perfect and treating its ways as gospel is not an improvement over JS. The "right ways" change over time and beliefs are not shared among everyone.
If you know what's in the object cast it as that type or be sure by saying if ('propertyName' in unknownObject).
TS is far from perfect. These aren't its ways (it provides any, so of course it's fine with it). These are my restrictions: if you're using a type system, actually use it. Don't lie to yourself and throw anys in your code.
This is "stunt programming," similar to shooting an arrow into a target from horseback in a rodeo. It has little to do with the real-life business of real-life cowboys.
In this case it's using the type system to calculate the answer to a problem, which is not useful because the type system can't output anything to the console or do other IO. The "answer" will only be visible in your IDE.
The type system is powerful and extremely capable because it had to support existing javascript patterns, like "this function takes a parameter that might be a string or might be a number or might be an array" and make them type-safe.
It’s a very beautiful language even despite being compatible with Javascript. The code here is delightfully absurd, please don’t think it is representative.
I’ve worked for TypeScript companies for a while now. Most devs I’ve met are fairly pragmatic and wouldn’t try something like this for production code, but I’ve definitely met a couple who have an exceedingly deep grasp of the type system and would appreciate the whimsy of it.
> The sea of confusing types to solve any problem?
Mostly in typings either provided by the library itself or via the 3rd party DefinitelyTyped project. Some typings have been made so complex, that it is hard to follow what kind of concrete type is exactly expected or allowed.
In my experience, even the more wild/exotic patterns in typescript tend to flatten into something rather readable at their usage site. 95% of the time when I use a library that does anything close to what is done in this article I write my code, hover over it, intellisense tells me its type and I say "wow, how was it able to do that? Cool!" And I carry on.
Why did they only solve for 7 Queens and not 8 Queens?
I'm reminded of https://github.com/type-challenges/type-challenges -- I've only looked at some of the more challenging problems, but one involves writing a JSON parser in the type system. The easy problems look reasonably useful to solve.
There's a recursion depth limit of 500 on the TypeScript compiler, which prevents this solution working for N > 7
Even Aphyr's original Haskell solution only demonstrates N = 6, so in some sense this is an improvement on the state of the art for type-level N Queens solutions /s
I don't think there's any way to do iteration in the type system (other than recursion), so there's no way around it.
I considered forking the compiler to set a deeper limit, but at some point Typescript itself is going to stack overflow. Also that probably goes a bit beyond what Criss is expecting in an interview...
I don't know about the typescript compiler, but the way around template recursion limits in "classic" C++ template metaprogramming is to figure out a way to make it O(log N) depth instead of O(N) (for some value of N). Like instead of linearly iterating through a range of types through recursion, you divide and conquer. Easier said than done, but possible in some cases.
I’m unfamiliar with TS. Could someone explain this part?
> Invoke the compiler
$ tsc *.ts --lib esnext --outFile /dev/stdout
var ᚾ = Symbol();
var ᛊ = Symbol();
var ᛚ = Symbol();
var ᛞ = Symbol();
Why is there so little output? Is that because the compiler removed the unneeded types? And the author is implying that the task was boilerplate and pointless?
This is what I mean when I search for "How to ______ in TypeScript": types! Too many blogs and Stack Overflow questions say "TypeScript" when they mean JavaScript, making it harder to find information on actual type problems.
There's a bug in the Solve "function" due to which you'll get the right answer only for 1x1, 5x5 and 7x7 (I checked till 8x8).
The base case makes a wrong assumption that there will always be a candidate available for the last row. If there are no candidates available, it should return Nil, and backtrack.
I've got a CS related degree, but I'm a mostly self-taught dev, and not understanding 90% of the code really makes me reevaluate my career choices. Where and how can I learn this stuff?
Do you want to learn it because it looks interesting, or because you think it's important for a Real Programmer to know?
If it's the former, go for it.
If it's the latter, don't worry about it. I have a CS degree, did 6 years on a team writing C++ at Microsoft, and only briefly flirted with understanding this stuff. A couple of the wizard devs on the (very large) team could do it, but they also knew that code needed to be simple above all else, so it was effectively banned in our code base.
There are 2 components here. One is the "type metaprogramming" - (mis)use of the type system to implement to do compile-time computation, mainly by using parametrized types as kinda-functions + type inference for kinda-pattern-matching.
The other is building up basic "data types" by pretty standard lambda calculus > LISP route.
"Understanding Computation" book has a great chapter 6 on that, which is available in blog & video forms on https://computationbook.com/extras
- Here, Church numerals were used to represent numbers.
- booleans & conditionals here didn't resort to the lambda representation you'll see in the book, but relied on type conditionals builtin to TypeScript.
- The names "Cons" & "nil" are a ringer for LISP-like building of lists, and recursive processing of lists, from a "pair" data type.
Sorry, i misspoke about "Church numerals". The book uses them to represent non-negative integers by lambdas but here that wasn't necessary, TypeScript allowed a simpler representation of N as a the type of an N-deep nested list.
What's common to both approaches to building arithmetic is starting from zero + a "successor" function T. That approach is called "Peano arithmetic".
I still recommend that post/video (and the book in general) but I have to admit there is no 1:1 correspondence to the TypeScript going on here.
Still, it'll teach you some general maneuvers for bootstrapping computation out of almost nothing , qnd once you're comfortable with those, you can read things like this TypeScript post, or aphyr's original Haskell post, which bootstrap computation out of sjighly different" almost nothings" and without following the details still have a high-level idea of where it's going (like the poor interviewer in the story ;-)
Yes it's mostly because it looks interesting and fun. I definitely agree these type-golf-esque solutions are not ideal in an enterprise project especially where we have juniors and fullstack devs committing a lot of FE code.
Don't worry. I assure you that many senior devs can't follow this article either without some further digging. This is a puzzle interview task, not something that matters in most peoples daily work.
As much as people complain about the TS type system’s complexity, it is just modeling real world JS. The vast majority of its complexity is hardly used in TS that doesn’t interop with existing JS, because you generally won’t write such highly dynamic code when you have to define its types. But it does allow for safer interop.
Even so, JS itself being so dynamic, TS still can’t claim full type safety.
And as much as people complain about the type system’s verbosity, many newer features are designed specifically to allow you to be much more terse while improving expressivity and safety. A great example: the satisfies operator lets you narrow a value’s type to conform to whatever it satisfies, and simultaneously widen it to whatever it adds (including anything optional in the narrower type). This is great for composition, only takes two words to accomplish. And its meaning should be immediately obvious at a glance once you know about the operator.
What I always say when someone complains about TS and we should just write JS is “When you write JS you ARE writing TS, you’re just compiling the types in your head.”
Yep, constantly. I used to do it and I honestly don’t know how I had 10% of that cognitive load capacity while I did.
(I still do it now because I inherited a huge highly dynamic set of projects, and just explaining the portion of the universe I remember at any given time is an exhausting majority of all of my weekly meetings.)
Having the type system this complicated is mostly for library builders, makes the developer experience of tools like tRPC, Zod and Prisma possible. An engineer writing business logic in TypeScript will probably never have to learn how to write (or even read tbh) complex TypeScript signatures, but benefit significantly from the solutions the type system complexity is a necessary precursor for.
It aims to be able to express the typing used in a bunch of pre-existing javascript libraries. Many/most of these were written in a "how would I solve this if the type system just let me do whatever I wanted" style (since that's what runtime dynamic typing actually does).
more or less. i wasn't asked n queens specifically, but i was asked to move a knight from one square to another.
but no, you're not supposed to solve it using the type system itself
Asking about setting a Queen on a chess board. Unless I’m being hired at a company that programs chess sets, it is a nonsense question. If you want to test someone’s problem solving skills, test them with a problem that actually reflects the real work they will be doing at your company.
The interview is to test for membership in a cult. There are other places you can be paid to code and design software that doesn't require (or even actively disrequires) being a cult member.
...or at least not a member of that particular cult.
> Backtracking is extremely important in today’s software interviews and almost always comes up in some form.
From TFA. Even the article struggles to explain how this is useful outside similar leetcode questions. Yes, backtracking is sometimes a useful approach for some real-life programming problems but leetcode questions neither test for the ability to recognize backtracking problems nor the general ability to solve them.
I’ve been hiring developers for decades at a Fortune 100 company and have never engaged in such nonsense. Unless you are hiring people to program chess sets, the question in the article is foolish. If you want to test their problem solving or coding skills, give them a problem from the actual work they will be doing at your company.
Sure. But do you know how often I’ve had to do backtracking in 25 years of professional programming? Zero times. Maybe the person is interviewing for a position where this kind of leetcode question is applicable, but in my experience this question is not abstracting real normal day to day problems.
I wish more companies thought that way. It seems like most of them are just cargo culting Google's hiring methods with the expectation that it will turn them into the next Google.
The second is a explanatory story, or "discovery fiction" as the article classifies itself: https://paulbutler.org/2022/what-does-it-mean-to-listen-on-a...
I love these humorous yet pedagogic technical writings, woven with a bit of literary eloquence and down-to-earth narrative. Thank you for this.