I read an article where a software engineer was about to go on a long plane flight, so he downloaded a file of all english words and tried to write a spell checker during his flight, with no internet access, just as an exercise. And when he landed, he had finished, and his algorithm was beautiful, simple, elegant, easy to understand, and never something I'd have come up with in a million years.
It was actually a little depressing - it made me realize that some people just have a "something" that I'm not going to get through hard work or whatnot.
To be fair, Peter Norvig [0] isn't just another software engineer, he's a hardcore CS researcher, co-authored the most popular (pre-DL) AI textbook, was head of NASA's Computational Sciences Division, etc.
I think what they're saying is that some people are Peter Norvig and got lucky, and other people won't get there with any amount of study or practice. He's definitely not an average engineer, and as a result most people shouldn't expect to have the same level of ability
I had the same thought - read the URL and then said "Oh well that's Peter Norvig he's just weird in a cool way"
I’m conflicted on calling him “lucky”, and I don’t think you mean to discredit him, but yeah he’s had genetic and societal gifts but I’m sure his work ethic is what makes him exceptional
> I’m conflicted on calling him “lucky”, and I don’t think you mean to discredit him,
I don't think saying he was "lucky" is discrediting him - simply because there's many people who got 'lucky' but didn't push themselves to fully capitalize on it the way he did.
Basically he's both "lucky" but also extremely driven and uses it to his fullest potential.
For a measured response - yes I agree, it's a combo of luck and effort, but the effort can't compensate for the luck.
For my true response that probably isn't as popular - he may have an amazing work ethic but that's also just coming from how he was raised, so it's still luck, the same person born in a different environment wouldn't have done the same things - both nature and nurture are external forces
It's funny how you say you have a natural ability to do great things while simultaneously saying that people should stop making excuses and just gain your natural ability.
And I'm not someone who is a stranger to hard work; most of my loved ones have complained with great sadness for years that I work way too hard.
In my experience, most of us hard workers didn't spend years training ourselves to work hard; we just wake up, work hard, and wonder how the hell the past decade of our lives just slipped through our fingers without any meaningful memories besides work.
It’s amazing how hard the majority of poor people work. If effort was all that counted then the slums of the world would be overflowing with billionaires.
> It’s amazing how hard the majority of poor people work.
I've pontificated over and over here that it isn't really about working hard, it is about working smart. I.e. choosing the right things to work on. Digging a hole and filling it in again is hard work, but it isn't going to get anyone anywhere.
However, it does take some effort. Upgrading your job skills is a common way to work smarter.
What exactly do you mean with "improving one's job skills"? What can a janitor do to improve their job skills? Learn to code in their free time? I have no idea what exactly you're suggesting.
I certainly wouldn't phrase it that way, but the best software developer I've met was not only very smart but really passionate about software. Like, _really_ passionate. His entire online persona revolves around it, and in person you could surely talk to him about other topics, but you could tell software stuff was his preferred one.
So he worked really hard, but he was _enjoying_ it to the point it wasn't really a chore to him. Others who are not so passionate about stuff can and will work hard towards some goal, but it will absolutely be a chore to them.
So I think the guy I'm talking about is lucky, or gifted, or whatever you want to call it, compared to others.
On the other hand, at some point I guess it becomes an addiction? For example I, like most, enjoy sex, and having sex a few times per week is great and there's nothing wrong with that, but if you _must_ have it 5 times per day maybe you have a problem.
I wonder sometimes what effect all this has on young smart kids.
Image two kids who show an interest in science or engineering and show some talent in those areas. One is a white kid from a well off community, and one is a Black kid from a less well off area.
The Black kid is going to be told several things, all of which are true. There is significant systematic racism in the US and the kid will find it affecting him. His school won't be as good as those in better off areas. His family won't be able to afford extracurricular activities that would help make up for the poor school.
If people are not careful in how they tell the kid those things, it would be easy for the kid to get the idea that the odds are too stacked against him and give up on pursuing science or engineering.
The white kid, on the other hand, might have his accomplishments partly or wholly dismissed as due to his better school, his family having more money, and his not having to deal with racism. That too could easily convince a kid to not bother. If everything you do is dismissed as just the inevitable outcome of things you were given and not as something you accomplished, then screw it...why not just spend your time playing games or on social media or partying?
Personality psychometrics are well established and more scientific than people realise. You likely have a high nature and nurtue tilt towards trait Conscienciousness (OCEAN model), which is largely in part due to your experience of life before the age of six
I have no problem working hard. I can grind for hours on a problem when I’m engaged with it.
My problem is constant distraction. It’s really bad. And blocking out everything else doesn’t help. I even get distracted by the thing I’m working on. I’ll see something new and go off and research that.
From everything I gather, we’re living in a pandemic of distraction. I think people had a lot easier time focusing on their tasks before the internet came along.
It matters where you set the achievement bar. Sure, if the goal is "internationally recognized expert," perhaps luck is a stronger factor.
But if the goal is, "strong enough programmer to write a spell-check algorithm from first principles," then work-effort might very well compensate for a lack of advantages in upbringing or other "luck-factors."
Yeah, if you completely ignore people who are born in destitute and corrupt countries. How is someone supposed to gain access to a computer when they can't even feed themselves?
They are pretty interesting because it establishes limits from which you can work to understand the validity of your model (idk about you but that's how I was trained to create models in my physics degree).
I mean, from there you can move on to similar cases where bad luck trumps any amount of ability. For example, what sucks about being impoverished? Not having good access to a computer, right? From there it's not hard to draw on other things (e.g. abuse, bad culture, poverty) that make having good computer access a huge challenge. It becomes pretty apparent that luck plays a huge factor in success.
So obvious that a lot of successful people here think they did it all on their own with very little luck involved. So obvious that there is an entire political party whose foundation is built around, "if I could do it, so can you."
As Stephen Jay Gould said: "I am, somehow, less interested in the weight and convolutions of Einstein’s brain than in the near certainty that people of equal talent have lived and died in cotton fields and sweatshops."
I don't think his work ethic comes from his upbringing - our parents didn't push us that hard and my work ethic is average. It may come from the fact that he found what he loves to do early in his career, it may come from my Dad's genes (his work ethic was pretty good), or a combo of both
IMHO the proliferation of "lucky" does more harm than good. It's factually correct but bad policy to emphasize it if you want the most people to avoid learned helplessness.
Some might be motivated knowing the only thing that separates them from greatness is luck, but more often I saw students feel defeated.
It is not factually correct that free will is an illusion. It is just a difficult subject to discuss.
Why difficult?
Discussion that is considered rational culturally descends from argument techniques rooted in Aristolean ideas about logic. However, as shown by Kurt Gödel formal systems break down under self-reference. Through Turing we see can see this type of thing starting to happen when two Turing Machines need to predict the output of each other.
Through John Von Nuemann and Nash we can get a proof of non-determistic policy functions in multi-agent decision problems being optimal. So we find an analogous concept to free will and we find it justified in this abstract domain not on the basis of some wishy washy concept, but on the basis of analogical reasoning (logic) and causal outcome modeling (dynamic functions).
So what do we reject to claim it is an illusion? Logic? Or causality?
It’s often difficult to discuss free will, among other reasons, because it’s ultimately a philosophical concern and people today tend to lack philosophical literacy—they unquestionably adopt whatever belief is a nail to the hammer of their education and upbringing: the STEM crowd here will by default go with physicalist monism; those with more religious upbringing will adopt dualism; and in the end all will be easily aggravated by questioning how they got there and asserting that alternatives are equally possible (and in case of STEM perfectly compatible with natural sciences, being entirely outside their scope through Gödel’s incompleteness if nothing else).
I think philosophical literacy is probably higher now than at any point in the past. For one, a greater deal of the philosophical writing is now existent than was in the past. For another, the selection effects have weeded out much of the writing that was bad. For yet another, a far greater percentage of the population is literate than in the past. For yet another, the population is healthier, wealthier, and generally better able to apply themselves to the material than they were in the past. For yet another, being after rather than before the Enlightenment, questioning of assumption is actually a much more prevalent reflex now than it was in the past. For yet another, our information retrieval systems help us do a better job of organizing the and discovering the relevant writing.
I also think philosophical literacy is less relevant than it was in the past. For example, we are talking about how an agent's decision making algorithm is in actuality. Is philosophy the best subject to discuss this? Control theory, learning theory, game theory, scientific investigation into the brain's processes are all mature enough that their usage produces more rewarding outcomes.
So lets say we see what at first glance appears to be degenerate twitch chat zoomer spam about philosophy sus no cap? Are they really philosophically unsophisticated? Or were they raised in a world of such greater philosophical sophistication that self-replicating knowledge structures - like, say, memes, were something they had extreme and constant exposure to? What if they are engaging in some sort of coordinated omegalul gambit?
I often find that explaining observed incompetence with genius works better than explaining observed incompetence with incompetence. So I'm more fond of claiming a problem is hard for good reasons then that people just weren't educated - which is also often true, by the way, just explaining why I ended up putting the emphasis somewhere else.
> For example, we are talking about how an agent's decision making algorithm is in actuality.
What is “agent”? If a deterministic universe without free will is considered, whatever “agent” means is likely nonsensical so if you are discussing whether or not the universe is deterministic then presuming existence of an agent (with agency) is a mistake. So no, in a discussion on whether the universe is deterministic we would not be talking about that, whatever that is, if apparently presumes existence of an agent.
> Are they really philosophically unsophisticated? Or were they raised in a world of such greater philosophical sophistication that self-replicating knowledge structures - like, say, memes, were something they had extreme and constant exposure to? What if they are engaging in some sort of coordinated omegalul gambit?
I didn’t mean just newer generations by “people today”. Discussing this with older people is as difficult and they tend to equally just make assumptions instead of reasoning. I like discussing topics like these the most with a gen Z philosophy professor a few years younger than me.
Not arguing nondeterministic universes. Within a universe agents see computationally irreducible phenomenon. It is just game theory decision problems embedded in cellular automata. The agent which says they could have decided another way is correct - their modeling of the problem did in fact have that property. The agents which thinks this insane and improper modeling are suffering from a hindsight fallacy.
Try considering a Turing Machine which is running several Turing Machines within it. Call it A. Within it are B and C. B gets an input state that is the entire Turing Machine. Meanwhile C gets the output of B. There are multiple B and multiple BC. So we get something like this when we write it out:
A = B + B + B + BC + BC + BC
You might be tempted to say that A = A, therefore A is deterministic. This would even be logically true. However, it is actually far more dangerous than it appears. Why? Well, you aren't A. You are within A. Lets say you are B within A. Does it matter that you know the dynamics function? It is deterministic, but does it follow from it being deterministic that it is deterministic? No! Even though B is within the deterministic system A, B cannot claim that A is deterministic, because B cannot claim that C is deterministic, because C is indeterminable by B through self-reference.
Now the standard mistake is to let B run then let C run then to pretend B could determine C, because now obviously we can tell that A was determined by B because C was determined by B. Which sounds really compelling, but ask yourself this to see why it isn't as great as you think it is: is the universe still subject to a deterministic dynamics function right now? If so, can you tell me what C is, not in the toy problem, but in the real world?
Like, I realize this is an impossible problem: I'm asking you for the current configuration over the course of the next second for all matter in our universe even the parts you can't model because you haven't observed it. But that is kind of my point. The universe hasn't stopped running yet. You can't determine C from the information context of B.
Now lets say you try to counter, ah, but A so therefore all the other stuff is meaningless.
It seems like it works, but lets talk about the parable of the time you were given a deterministic dynamics function and you computed it according to what it was because you wanted to claim it was deterministic by treating it as what it was.
So you start calculating B + B + B + BC + BC + BC. And you see me looking at the same problem and idiotic like I am, you see me write down A = A' = BC. Then I get ready to solve it. And you are like, pfft, what an idiot. He isn't even talking about, like, actual reality.
unfortunately, in the calculations that follow, you realize something strange: Though you may B, I C you. And because I see you before you be such that I can determine what C should be such that you cannot see C while you B be, I choose a C for your B so that your B doesn't see C.
Basically, in choosing the slowest path, you also choose to be determinable, but in choosing being determinable, you implicitly make yourself vulnerable to an A' that makes your context - during the process - undecidable.
You thought choosing A saved you, but actually it was your curse:
You let me set A = B + B + B + A' because you didn't want to claim that we could divide A into the pieces which it was in actuality composed. But because it was in actuality composed of those pieces BC is now calculatable by A' such that your conceit is actually what traps you in the non-deterministic perspective. If B was calculated, not via A's conception of B, but A' then now it isn't just B that can't predict C. C probably can't predict B either.
So lets escape this! Lets say the process ends! Now B has fully determined itself such that C is determined and now A is determined as well.
Is A now deterministic? No, A isn't anything anymore.
Nothing is happening.
A isn't now deterministic; A was determined and now our physics is stopped. Where is the determinism at? Not within A, because clearly during A B wasn't deterministic because of self-reference to C. Not afterward either, because now it isn't doing anything.
It really isn't a problem. The analogical congruence holds.
Typically free will is defined according to the action being taken without the constraint of necessity based on a person's own desire.
In the game theoretic model that Nash showed optimal the decision making act that the agent has to do isn't about deciding over actions. It is over strategies. That might be a bit confusing so lets just use an example.
If you play rock paper scissors in the agent's modeling of the problem it isn't modeling it as an action choice of rock, paper, or scissors. It is actually modeling it as an action choice over probability vectors. The action choice of rock corresponds with the probability vector of [1 0 0], paper with [0 1 0], and rock with [0 0 1]. There are an infinite number of different policies, but it turns out that the rational one to pick is [1/3 1/3 1/3] playing each option with equal probability.
Notice that here the agent is taking an action, but not one that is constrained by necessity. Notice that the choice of it is due to the modeling of what is in the preference of the agent. Compare that with the definition of free will. The same thing is happening.
So the congruence does hold, but what makes it appear to not hold is that most people rejecting free will neglect computationally irreducible phenomenon. In actuality, computationally irreducible functions which allow for stochastic signals show up in cellular automata without the requirements of dualism. Selection and variation are then much more then enough to show that surviving agents will protect these information sources so as to make them unobserved, because failure to do that isn't optimal and so agents which don't aren't selected for.
> Ah, this is where the problem starts.
We could try and reject, not the analogical congruence which holds, but the system of using analogical reasoning in the first place, but this goes badly. The first big problem is that all of our knowledge comes via theory-laden proxies and removing analogical validity removes the validity of evidence in general. A stranger result is that compression is justified through analogical congruence. So you can no longer claim to have knowledge over the state and dynamics function, because you have knowledge over the compressed form of it. To claim knowledge, you now need to physically be it.
> Ah, this is where the problem starts.
There are many invisible octopuses. Fish are going to encounter decision problems wherein these camouflaged predators are both on their right and left yet the decision context shows them the exact same thing in both cases. So which should they pick? Always left? Then they always die. Always right? Then they always die. The only winning solution is to pick both, because then sometimes the agent lives to reproduce. How do we pick both? Well, if we do it in a way that is computationally reducible then the octopus which observes the fish invisibly can anticipate it. So now it is wherever the fish decides to go. So it has to decide to do both, but it has to do so in a way that is unobservable. This decision problem doesn't go away when someone chants the magic word of dualism. The agent still needs to decide in an unpredictable manner or is going to die. So when optimization processes build things? They end up approximating a solution to this problem.
This type of decision problem has played out billions of times. It has played out over billions of years. I don't know which time it happened which was the first, but where it was, that is where the problem really starts. And since that problem and onward a filter has been killing the things that answer incorrectly.
You make an interesting point, and I think which side of it is correct depends what the end goal is. It definitely doesn't help people, particularly children, to tell them they're "lucky" or "gifted" in a particular ability. Early in life it means that they can downplay the effort needed to develop that ability, and later in life when they hit the actually difficult bits it can result in them assuming they must just not be as good at it as everyone says, rather than applying themselves to understanding.
There is also value in people understanding that not everything is down to innate ability and application though. That road leads to people looking down on impoverished people because they should have just put more effort in. Get a better job, learn a skill, regardless of the fact their situation means they're already working 3 jobs just to make enough money to ensure their kids can eat tonight.
As with so many things people have polarised. You're either in Camp Skill & Dedication or Camp Luck & Circumstance. In reality it's always a bit of both, with luck giving some people an advantage when it comes to having the time and space to dedicate themselves to developing their skills.
You can be lucky and hardworking, and have both of these factors be individually necessary but insufficient contributors to your success.
People get weirdly defensive about luck being a major factor in their success, but it always is. It doesn't mean you didn't work hard, it doesn't mean that your decisions didn't contribute to your success. It means that, if you were born a little bit less smart, you would have achieved less. And if you were born in North Korea or medieval Europe in the peasant underclass, you would probably have achieved nothing of note and may have died of the plague before reaching adulthood.
I'd estimate that just the sheer luck to be born in a wealthy, free country without debilitating handicaps in the late 20th century or early 21st century already puts you in something like the top 1% lucky people in human history.
You can argue that being hardworking is a talent, and as such luck. Not everyone has the force of will to be hardworking some people are naturally lazy and some can put hard work without it feeling like hardwork and others can feel the hard work, but have the will to overcome it, etc.
I say that success is 100% luck and of that 100% of luck, some of it can be composed of hardwork, as the ability to perform hard work is in itself, a part of luck.
everything in your sentence can be traced back to luck in some way. Genetic gifts I'm sure contribute to work ethic, but also the families, societies, you're born into. The teacher you met in 1st grade that encouraged you to keep trying etc. Luck is in everything IMO
While of course the choice to apply effort and enact effort exists, but being able to successfully do so, and to have he psychological directive to do so effectively, is largely based on personality, which is largely established by age six. (Conscientiousness - OCEAN)
Inherent motivational energy is a roll of the genetic/environment die just as much as every other trait like height or engineering intelligence capacity.
Perhaps his epic work ethic is partially the result of a genetic trait and/or the influence of good parenting at an early age… which would be pretty lucky for him.
Luck is like 5% of any equation. He had the gift and he was disciplined enough to execute on it.
That 5% luck probably got him an extra 10-20% further than anyone else. However, in a room with equally disciplined individuals you wouldn't be able to discern the lucky from the hard working.
So in this case, the special "something" he has is quite literally the amount of hard work he put in to learn this stuff. And if you take this opportunity to learn about edit distance, you'll be one step closer to that special someone you want to be.
You know how there is that joke about reasoning about multi-dimensional structures?
"To deal with hyper-planes in a 14-dimensional space, visualize a 3-D space and say 'fourteen' to yourself very loudly. Everyone does it."
– Geoffrey Hinton, A geometrical view of perceptrons
Well, you actually can come up with Norvig's spellchecker very easily with a similar trick. Just tell yourself: to deal with a really hard problem, just argmax with an okayish heuristic. Everyone does it.
Solutions like this seem impossibly elegant because they tolerate a whole lot of error, but they are actually extremely obvious when you tolerate error.
If it makes you feel any better the original is not the same as what is displayed now[0] so it did not take just one flight to achieve elegance, and also included some bugs which were mentioned in the errata later[1].
It's really nice and I'm a fan of the man but... Even back then it was a really simple spellchecker. Back then stuff like the "metaphone" and "double metaphone" algorithms already existed (suggesting candidates based on similarly sounding words). Fun algorithms 'em metaphones I'd say. Relatively easy to implement/port (been there, done that).
I'm sure there's better stuff now.
Also it's possible to better ranks candidates to fix typos by taking into account the layout of the keyboard (e.g. on a QWERTY keyboard is you see "wery" it is, despite having an edit distance of 1, highly unlikely the person typing meant to type "very". "weary" is much more likely). So just sorting by edit distance and then suggesting the most common word often doesn't result in the best candidate being shown first.
And then context. Ah, context. I type this and my browser isn't aware I'm talking about algorithms and not only says "metaphone" is incorrect but suggests "megaphone".
So... The matter still isn't settled if you ask me.
This kind of feat is the exact opposite of what the article is about.
This code is very simple, very short, very unoptimized and done in a few hours, free solo. The kind of code the article could have linked as an example of how simple it is now to write a spellchecker, in fact it explicitly talks about how you can do it in a few lines of Python, i.e. this.
What the article is about is complex, highly optimized code that took months to do, because computers at the time didn't even have enough space to store the complete word list uncompressed, neither in storage nor in memory, and even with compression, you had to be clever.
so a question that could be asked today is: what could be achieved, if only the same cleverness was applied to the utilization of the massive resources available today?
One potential answer is indeed the recent developments in AI (generative stuff like GPT & stable diffusion etc).
The prowess here is greatly overstated. His implementation would be pretty obvious for anyone that had read an Information Retrieval textbook any time in the couple decades between when these methods were devised and when he wrote that post.
That's kind of like watching someone use Red-Black Trees and assuming that they intuited them out of thin air. It's just remembering a basic algorithm that would be familiar to anyone in his particular field.
These ideas are extremely powerful. I built a spell-checker largely based on this article, by parsing English Wikipedia. At scale it needs a trie and a distance metric with better-scaling performance metric, but it works really well. These go together: your error metric is a priority-based multi-headed traversal of your trie -- this emulates comparing your word to every word in your dictionary; you can compare against a few million words very quickly.
Because it's based on Wikipedia, it can correct proper names too. It's very extensible: by changing the error model, you can get fuzzy auto-complete that can look at "Shwarz" and suggest "Schwarzenegger" (even though you missed the 'c'). You can extend it to looking at multiple words instead of just letters, for correcting common word-use issues as well.
Unfortunately I did this for work so I can't open-source the code without some awkward conversations (which may be possible and worth it, but I haven't yet). I'm sure I could write a blog post on it, but I don't have a blog, so ... sorry. Peter Norvig's post plus my point about tries and an efficient comparison algorithm at least give you a head start.
Norvig wrote a similar expansion in his chapter for the book Beautiful Data (along with several other small programs to do fun things with natural language corpus data).
You can find it with a web search.
(His version didn't use a trie, because Python's built-in dicts are much more efficient than a trie in Python, even with the extra redundancy that a trie eliminates.)
I recently realised I've been missing my "something" for a while.. ya I've not had a dopamine free moment since doom scrolling became a thing.
Not comparing somethings, I probably couldn't write a spell checker much less a beautiful one, but my creative juices are much less clogged up since allowing myself to get bored.
I believe it's being able to combine a learned skillset with raw creativity (boredom) that gives a person that something you refer to.
For me it's largely "the joy of finding things out". If I know there's a standard solution to a problem, I'll avoid the "spoilers" because I want to see how far I can get on my own. (And yeah, sometimes I just get bored of doomscrolling... Building things is a much more satisfying way to spend my time!)
I often avoid things because I think they'll be hard, but then discover that they turn out to be easy. "Why didn't anyone tell me how easy this was! I could have done this ages ago!" was a running theme for me for a good while.
Of course, sometimes things are actually harder than you thought. But they're still doable! Whereas I have this cognitive bias where "difficult" is (emotionally) equivalent to "impossible", which is just really unfortunate. I'm sort of starting to see through that, that everything's made of atoms, and once you break a task down far enough, the individual steps are trivial.
At least in my career so far all of the tasks I've been told are "impossible" just need another 5 minutes of thought - to the point I'm wondering if people do it on purpose so that I take over the task haha
Worth noting he did not perform the "major feat of software engineering" like the OP says (given 256k ram or lower). He just put all the words into a hash. The main key is knowing about edit distance, if you know that, you can probably write the solution.
So yes he's very talented, but if you study enough computer science, you can also do it. Or don't. It's totally fine to be interested in other parts of engineering instead.
Don't get me wrong, Peter Norvig is awesome, but if you're already familiar with levenshtein or even hamming distances, it's pretty straightforward to hack together a spellchecker.
The idea was to set up an auto-reply to my email that looked automated, but surely couldn't be because it messed up the sender's name. Not nearly as clever as Peter Norvig's program and even less useful.
I'd say the bias toward common American names is a bug, but given that the goal of the project is to be obnoxious it's probably a feature.
The hard part in the early spellcheckers wasn't figuring out that you want to find a set of words with a minimum edit distance from the input.
The hard part was fitting the dictionary in memory, and then searching all possible strings 1 and 2 edits away from the input to find the candidates.
The progress is that we don't have to care about storing 2.5MBytes (they ran on machines with 640k!) in RAM, or searching it 100,000 times (e.g. edits2('something')).
It is a bit strange to me that it would be surprising that there are people way better at programming than you. The chance that you would be at the far right of the bell curve for any skill is pretty small, by definition. Almost everyone is going to not be the best at your thing. I don’t know why it would be depressing to not be the best.
I challenge this, especially the "by definition" part. It depends on how many skills you recognize.
The chance of being the best artist (to the extent that such a statement is reasonable) might be one in eight billion.
The chance of being the best automotive sharpie artist is, similarly, one in eight billion.
The chance of being the best artist /of some particular skill set/ is, then, much higher -- if you recognize only a few thousand distinct skills here, you're already at one in a million.
Then realize that those who are likely to be surprised that there are better programmers than them are /not/ likely to be surprised that there are better artists than them. So we're assessing across all skills.
The chance of being on the far right of the bell curve of a specific skill is pretty small. The chance of being on the far right of the bell curve for /any/ skill is quite high, with only eight billion people around.
Find what you do better than anyone else, embrace it, and enjoy it.
I've come to accept the fact that there are millions of people better than me at something. It's depressing and hopeless trying to be the best, there isn't even an objective measure. My goal is instead to be useful.
That "something" is basically passion and motivation, a child-like fascination with computers and the powers they can give you. People like this are so valuable and great to work with not because they have some innate power to understand algorithms, but because they sell a brand of optimism reminiscent of the "old" tech industry, the American postwar optimism of the 90s, where new things actually were revolutionary.
Let's be real, in 5-6 hours he designed a very nice, simple algorithm to produce likely words from a dictionary based on frequency analysis, and produced 30 lines of Python code implementing it. A lot of engineers today could have done this.
The "specialness" was that he did it on his own time and enjoyed it.
I’d bet you have a “something” that isn’t obvious to you, or that people don’t compliment you on. And even if you don’t, comparing one’s self to anyone is sure to be depressing.
Peter Norvig is at god-tier, comparable perhaps to Torvalds, van Rossum, Wozniak, Stallman, ESR, Kernighan, Ritchie, Gates, Cormen, and many others I've left out.
The guy making revenue is a better developer than the guy making elegant algorithms
Very few of us actually want to be the guy accumulating accolades for their engineering, we want to take flights to things we actually want to be doing, not opening our laptop once or even bringing it
I added "When you are spell-checking, please take extreme care when picking the corrected versions of each word." to my instructions and it got it completely right.
Language models like ChatGPT seem to "remember" paragraphs of text in a highly compressed form which is not always fully accurate when reproduced - so a mistake does not tell us whether the text is from memory.
It still blows my mind that when growing up I had a Commodore 64 word processor with spell check. To run the spell checker you had to hit the button to start the spell checker and then turn the floppy upside down while it ran through the document.
This means you had to store in a measly 64kb not only the code for the spell checker, the entire contents of the document, KERNAL overhead, and enough data for the spell checker to run. Remember that the Commodore 64 had an incredibly slow disk drive (300bps) and the disks only supported 160kb of data. Any scheme that required a lot of disk access would be terribly slow. Yet somehow it worked and wasn't outrageously slow. I suspect the program was unloading big chunks of its own program to aggressively reuse the memory space but even then it seems like magic.
Way back when I wrote a DOS file manager that fit in 32K of assembly language. As I recall, at one point I upgraded it to use two different 64K segments when running by putting the code and in-memory information about the files in different segments.
There were several spell checkers for the TRS-80 model 100, which maxed out at 32K of RAM. More typically, it has 24K, because the weird RAM chips were so expensive.
Plus, few people had floor drives for the 100 —you had to operate from a cassette tape.
I was going to point out my Panasonic W1030 word processor as probably even more impressive since it's not even really a PC.
But then I found specs and its dictionary uses 384kB [1]. Then again it's from the latter 80s, maybe previous word processors attempted more constrained spellcheckers.
If you think this is great and/or immediately thought of using a trie to reduce storage costs, then let me introduce you to https://blog.burntsushi.net/transducers/ which pushes storage reuse over the edge to almost competing with compression like gzip while still allowing you to consider edit distance while finding possible alternatives.
typeaheads/autocomplete and spellchecking both need this so worth a read.
Great stuff, I never deal with stuff like this in my day job and was pleasantly surprised at how easy it was to follow what was going on, which means the author did a great job.
Yes, sad that we don't get to work on actual algorithms/leetcode-like problems in the job. Instead it's just hundreds of cocoapods, gems, npm packages, and build tools to make a contact form or profile page.
Honestly sometimes it feels like it takes more time to untangle the web of build tooling and libraries than it does to write code.
After months of setting up a new app, I've finally written a component in the past week. It's just a list item, icon, text and a chevron, but to get to that point took ages.
I just hope it was worth it. Probably not, I fully expect this code to be thrown away again in favor of whichever consultant comes next and/or because a designer says so within five years or so. At least I get paid monthly I guess.
1980s memory models especially dos-era PC was a nightmare but you could at great effort work around it. The C / unix memory model is actually quite luxurious compared to programming on dos 3.3.
In the old days non-English support was pretty complicated. Now you rely on the OS to support UTF-8 and call it good, more or less. Was a bigger problem 'back in the day'.
In the old days you'd run a spell checker as a batch process, possibly not even part of the editor itself. The point I'm making is WRT speed, now a days speed doesn't matter, not because processors are faster (although they are, software always expands faster than hardware) but because we have integrated app with threading, so instead of saving this into a file, then exiting my browser and running a separate spell check app then exit and start the browser again and load this file back into it, the browser simply has a thread doing spell checking "on the fly". So in the old days it was VERY important WRT labor costs to spell check a 10000 word essay as fast as possible, and on a 8 mhz XT that was a trick indeed. But today my multi core multi ghz desktop merely needs to spell check on the fly as I'm typing and I can't be faster than 100 wpm or so. My desktop had "like one second or so" to decide that ghz and mhz are not words and put red squigglies under them whereas in the old days you'd have to spell check like 1000 words/second to keep the users happy.
So simple ineffective code survives in 2023 because it can lean on the OS, its not just that hardware is faster or larger.
A good one still is. When I got my most recent phone (Galaxy 22, but I jumped several versions in the upgrade so I don't know when the change happened), the spellcheck engine regressed massively from previous editions.
I'd be so curious to hear what the change was. It's absolutely awful to use!
Is it not based on your history? I know the suggestions seem to be. If so and it's stored locally it could just be that it's having to start again from scratch?
It used to be very clearly based on history, so every time I restarted my phone I'd get the classic "duck" correction.
Now I couldn't tell you what it's doing, but it doesn't appear to be using history. For instance, the same technical terms get autocorrected again and again.
He's got a point: increase in minimum memory and increase in CPU performance means that superior programming isn't always necessary.
People regularly produce for fun what used to be a masters thesis level of work these days. I'll cite that YouTube video of someone making a reaction wheel system that can get an inverted Lego pendulum to stand up, and stay up under perturbations. The Lego part isn't the main work. The main work is software, a PID controller of the reaction wheel.
Something else has happened. There's enough people who know enough that the knowledge is just sloshing around, waiting for others to do cool things with it.
> He's got a point: increase in minimum memory and increase in CPU performance means that superior programming isn't always necessary.
Fun part about this is that it might actually make it slower! Between cache misses, pre-fetchers and branch mispredictions the more naive search may make things significantly more predictable for the out of order execution on modern processors that the result is actually faster when you don't try to be clever with some of this.
You still have to benchmark and not do things completely wacky but it's kind of interesting how things have changed because of the scale of the pieces.
The really mind blowing thing about that 2 meg dictionary, is that it can completely fit in cache for many computers nowadays. Just mind blowing that the optimized linear scan search today is competitive with faster methods from yesteryear. (Heck, the unoptimized scan is probably more than competitive.)
It's kind of amazing how many hard computer problems from the olden days were solved by having more memory. When I got started in computer graphics, there was a lot of research work on how to render images a scanline at a time, since that's all the memory you had. Once you could get enough memory to hold the entire image, you could use a Z-buffer and rendering became kind of trivial.
Another example is the post on HN yesterday about old videogames and how they used a bunch of different hacks such as sprites and tiles because there wasn't enough memory for the whole screen.
https://nicole.express/2023/yes-popeye-the-sailor-man.html
...but a really good grammar checker is still, to this day, a major feat.
Even Grammarly can't write sentences for you as good as a native speaker. ChatGPT and language models can, but ironically, they still require way more memory than fits on a desktop. Simple cases like conjugation can certainly be handled but there is a lot of nuance to make a sentence "flow".
The “current hotness” for spellcheck would be to use a large language model (LLM) like GPT-3 that can use several paragraphs of context to disambiguate between alternatives.
However usefully accurate LLMs are still too big to work locally in a laptop or PC, so once again we’re back to having to liberally apply black magic to squeeze the models into something an integrated GPU can run in its “tiny” VRAM that’s actually gigabytes in size.
The more things change, the more they stay the same.
PS: Spell check is a trivially solved problem for most languages, but not all! Hungarian is notoriously difficult, and there are ongoing projects to improve this: https://en.m.wikipedia.org/wiki/Hunspell
In some ways, I think computational linguistics has missed a mark. We have dictionaries, lexicons, grammar engines, spell checkers, pluralization rules, tries, quotation disambiguation, sentiment analyzers, word segmentation, and more. You'd think we could roll all these into a unified, standard definition format.
I was looking at integrating LanguageTool[0] for grammar and realized that it has partial functionality for KeenQuotes (lexing and tokenization), duplicates the SymSpell algorithm used by KeenSpell, and because it offers grammar corrections it likely can pluralize words, as well.
Unifying those for English alone would be a massive undertaking. At present, KeenWrite parses prose in multiple, redundant passes. While this works, I think it'd be great to start with a basic lexer/tokenizer that can emit tokens at blazing speeds[1], which feeds into higher-level abstractions.
And still is for most. I'm a horrible speller, but fairly consistent in my mistakes. Usually I use the wrong vowel with a similar sound in the middle of a word. It's amazing how few spell checkers can handle that. The google search bar is the undisputed king in spell checking in my experience. Microsoft word, even from way back, has been good. Thunderbird from about a decade ago was the most infuriatingly bad spellchecker I have ever encountered. I always recognize the correct spelling when I see it. So, in Thunderbird it would commonly refuse to suggest the word I was looking for but would often give me the "un" version of that word. I mean, come on. I can get the first letter right 9,999 times out of 10,000 and that is probably a gross underestimation. And the few I would get wrong are a handful of edge cases...
Now be French like me and have words spelled with an E en English and A in French (I recommend/je recommande), and try telling Google that, despite them forcing themselves to guess that you are French despite having set the browser to English, the Google Settings, the OS, and using a VPN to ensure to get all ads and search results in English, you really, really want to be recommended the English spelling of words so that you don’t do en/an mistakes ever again…
Random story. I was a young kid in the 90's and my dad took me by the biggest house I'd seen at that point in my life for some work party or something. Really nice landscaping, etc. It was clear the owner had A Lot Of Money.
I asked him afterwards how the guy got so rich and he told me that he wrote Microsoft's spellchecker.
Actually there's way more to it than loading /usr/share/dict/words into a perl hashtable and calling it done. A good spellchecker from scratch is still a massive engineering effort in 2023.
Now it’s just a major pain in my butt. At least the ones on phones. Half the time they replace a legitimate word with the one they thought I actually meant. They’re almost always wrong.
I dunno, there was an article in Creative Computing magazine circa 1984 about how to code one up in BASIC that required a little creativity but made it look pretty easy. If you sort the words in the document it is pretty quick to check them against a dictionary on disk.
Turbo Lighting, though, took advantage of the comparably large memory of the IBM PC to do something that really blew people away
I remember using Turbo Lightning. It was incredible. You type a word in some DOS program, and when you hit the spacebar, a beep would sound if the word was spelled wrong. Back then Peter Norton was all the rage, so if you typed "Norton" TL would beep and suggest spellings like "notion, nothing, etc." to correct Norton. The suggestions felt so AIish and futuristic to me. Wow a "suggestion" for how to spell something? If you selected a replacement, it would stuff the keyboard buffer with backspaces, to erase the word, and retype the correction. Borland made incredible software back then. Great times.
Yet in 2022 spell checking is still not good, at least when it comes to ordinary software. It checks with dictionaries, it seems that recently Google Chrome became a little bit better at it, but still I can completely write gibberish random with order words of and it wud no car as long as separate words are present in the dictionary. And that's while there's AI which generates awesome texts around.
I don't know English well, but one single thing that immensely helps me memorizing English is instant feedback when I'm writing texts with errors. I bet that good spell checker in Chrome would do much more to the world than many English courses (also helps with any other language, of course, but English is special as it's world's lingua franca nowadays).
It feels like spell checking was better in the 2000s than it is today. It probably wasn't, but it didn't feel so annoying because it was not that prevalent.
With the spellcheckers Google and Apple are using, it's rare that I can write a full paragraph of Finnish without them flagging something incorrectly. Whatever methods they are using, they seem to be incapable of handling cases, conjugation, and compound words. Which is ironic, since early Finnish spellcheckers were surprisingly good. There was a lot of research on those topics in Finland in the 80s and 90s, and early spellcheckers took advantage of that.
I think Chrome uses a Google service by default. FWIW I have found Google Search's spell checker fantastic. (At least for English) It seems to have a better concept of sound similarity or something that means it almost always guesses the word I mean (extra impressive because on Google Search it only shows you one suggestion). I frequently find myself in a situation where Firefox's (local) checker can't figure out what word I meant so I put it into Google Search and it nearly always knows what I meant.
In it he demos the UI of a word processor of that era on a green screen monitor. As I had a CGA screen/PC at the time word processing was pretty novel to me ... in white and black, but most of my friends did not own computers and those that did had Commodore 64s[0].
[0] I sat jealous despite sitting before a $3,000 8088 w/FPU, 10MB HDD and 640k of RAM that took 2 minutes before it started booting from the hard drive (I learned to count in powers of two up to 640 that way).
As a person with dysgraphia I can assure you that it still is a major feet. The algorithms are fast, but they still do a bad job of turning the semi-random sequence of letters I come up with into real words.
There are still "hard" problems to solve when it comes to spellchecking. For example predictive text and correct typo detection. Notice what suggestions the Firefox and chrome spellcheckers give you versus what happens when you use google or mobile phone autocorrect. There are still differences in spellchecking speed, quality, and UX.
It's still pretty bad in some fairly common languages like French. For instance "'" really trips spellchecker, as well as some tense (subjunctive). For instance "que je n'embête".
I remember that the early CPM edition of WordStar didn't have an interactive spell-checker, but you could run it in batch mode and get a report.
One way to implement that is to store say a paragraph or more of your document at a time in RAM, then do a sequential read of the dictionary file on disk, compare to the stored paragraph words, and save any non-finds to the misspell report.
Saving the position could allow one to bring the editor back up and have the misspelled words highlighted, which is what WordStar did as I remember it.
I spent some years working as a freelance proofreader and copyeditor, and came to regard writers' use of spellcheckers as basically a guarantee of my future employment.
In 1988, I had a friend in my computer science program who got some local notoriety when he made a spell checker for DOS. It was a terminate and stay resident program and it used a tiny bit of the available 640K of RAM.
We were all pretty amazed by it. He got some seed money to start a business and then was crushed like a year later when it was just built into wordstar.
It's probably easy mode compared with the original constraints in the article, but the problem is still somewhat challenging. It took me a sleepless night to get it right.
Perhaps that’s a good thing. There’s so much computing hardware these days that some things are basic “free”. Liberating (but also scary) implication is that we’re limited more by our ideas than the hardware, so go out there and create something cool, there’s little stopping you other than the ideas in your head.
This reminds me of an article on the JoS blog where Joel describes how hard/impossible it is to do real-time spell checking on the web with red underlines on the typos.
It really is mind blowing for those of us who remember spacer.gif and are still hacking today. The web has really grown up.
Word processors in the 70s had this as well. I remember the CPT 8100 having this as a selling point in their literature. There was no inline correction. Run the program, correct your issues then continue!
Anyone else remember Shift+F7? Bring out your Wordperfect templates.
Spellcheckers still blow my mind and Gmail's autocomplete(still the best out there imo), I still marvel when they work even though I know how they work and have used them for a while.
It was actually a little depressing - it made me realize that some people just have a "something" that I'm not going to get through hard work or whatnot.
*edit: ah, found it. https://norvig.com/spell-correct.html