Scott Hanselman, the Microsoft VP for developer community outreach and general all around good guy was kind enough to ask me to be on his podcast, HanselMinutes, to talk about my upcoming book. I was delighted to spend a few … Continue reading →
Eric Lippert
https://ericlippert.com/ · 110 posts · history since 2019 · active
22 Jan
17 Nov 2025
Hey everyone, I first want to say a heartfelt thank you so much for the warm comments and supportive feedback I’ve gotten since I announced that I’m in process of writing Fabulous Adventures In Data Structures And Algorithms. It means … Continue reading →
30 Oct 2025
Hey everyone, I’ve finally turned this blog into a book! Or, rather, I am deep in the process of turning this blog into a book. Yes, it’s about 20 years, give or take, after I first thought of doing so, … Continue reading →
21 Mar 2023
I wanted to implement concise “pattern matching” in Python, a language which unlike C#, F#, Scala, and so on, does not have any pattern matching built in. Logically a pattern is just a predicate: a function which takes a value … Continue reading →
23 Feb 2023
Before getting into the details of how my combinator-inspired source code transformation system works, I should say first, what is a general overview of the system? and second, why did I build it at all? In my experience, a typical … Continue reading →
8 Feb 2023
How do we write a compiler in a typical general-purpose line-of-business OO programming language such as Python, C#, Java, and so on? Compilers are programs, so we could make the question more general: how do we write programs? The basic … Continue reading →
3 Feb 2023
The European starling is a lovely looking bird, though territorial, noisy and aggressive up close. Unfortunately, they are very invasive in North America. Most of the hundreds of millions of European starlings now living in the Americas can be found … Continue reading →
1 Feb 2023
In the autumn of last year my friend Joan and I went on a little trip up to the Skagit valley north of Seattle to photograph birds of prey; I managed to get a blurry but recognizable shot of this … Continue reading →
30 Jan 2023
Reader “Joel” had an insightful comment on the first part of this series which I thought deserved a short episode of its own. Recall that we proved the theorem “if a compositional forest contains a mockingbird then every bird in … Continue reading →
17 Jan 2023
For the next part in my Bean Machine retrospective to make sense I’ll need to make a short digression. In looking back on the almost 20 years I’ve been blogging, it is surprising to me that I’ve only briefly alluded … Continue reading →
5 Jan 2023
Happy New Year all! Last time I briefly described the basic strategy of the Beanstalk compiler: transform the source code of each queried or observed function (and transitively their callees) into an equivalent program which partially evaluates the model, accumulating a graph as it goes. … Continue reading →
20 Dec 2022
Let’s take another look at the “hello world” example and think more carefully about what is actually going on: There’s a lot going on here. Let’s start by clearing up what the returned values of the random variables are. It … Continue reading →
14 Dec 2022
I’ll get back to Bean Machine and Beanstalk in the next episode; today, a brief diversion to discuss a general principle of language design and congratulate some of my former colleagues. Back when we were all at Waterloo, a bunch … Continue reading →
9 Dec 2022
Did I actually build a compiler? Yes and no. Traditionally we think of a compiler as a program which takes as its input the text of a program written in one language (C#, say), and produces as its output an … Continue reading →
7 Dec 2022
Introducing Beanstalk Last time I introduced Bean Machine Graph, a second implementation of the PPL team’s Bayesian inference algorithm. We can compare and contrast the two implementations: In short, the BMG user experience is comparatively not a great experience for … Continue reading →
5 Dec 2022
Introducing Bean Machine Graph Bean Machine has many nice properties: I’m not going to go into details of how Bean Machine proper implements inference, at least not at this time. Suffice to say that the implementation of the inference algorithms … Continue reading →
2 Dec 2022
As I mentioned in the previous episode, the entire Bean Machine team was dissolved; some team members were simply fired, others were absorbed into other teams, and some left the company. In this series I’m going to talk a bit … Continue reading →
30 Nov 2022
It’s been almost two years since my last update here. A lot has happened. I hope you all are continuing to weather the ongoing multiple global pandemics and other anthropogenic crises. Apologies that this is so long; I didn’t have … Continue reading →
17 Feb 2021
Here we go again! Fellow BASIC enthusiast Jeff “Coding Horror” Atwood, of Stack Overflow and Discourse fame, has started a project to translate the programs in the 1978 classic BASIC Computer Games into more modern languages. I never had a … Continue reading →
9 Feb 2021
What regular work activity has the highest impact on the organization in the least amount of time and effort? I haven’t done any science on this, but anecdotally it sure feels like recruiting, interviewing and mentoring are all huge impact-per-time … Continue reading →
15 Dec 2020
Since I’m staying home all day due to the ongoing pandemic emergency, I’ve decided to document all the different species of birds that arrive in my yard. I am not a great bird photographer but I am enjoying practicing every … Continue reading →
29 Oct 2020
Earlier this week I was looking for an old photo, and while browsing I came across a photo I took of my whiteboard in my office at Microsoft in 2004. Or rather, it was two photos; I’ve crudely stitched them … Continue reading →
12 Oct 2020
All right, let’s finish this thing off and finally answer the question that I’ve been asking for a while: are there any Life patterns that have unbounded quadratic growth? (Code for this final episode is here.) The answer is yes; … Continue reading →
6 Oct 2020
This was supposed to be the last episode of this series, but while writing it I discovered a bug in my implementation of Hensel’s QuickLife algorithm. It’s a small defect, easily fixed, but I thought it might be interesting to … Continue reading →
23 Sept 2020
The final part of my Life series is still in the works but I need to interrupt that series with some exciting news. The new programming language I have been working on for the last year or so has just … Continue reading →
14 Sept 2020
Last time we implemented what looked like Gosper’s algorithm and got a disappointing result; though the quadtree data structure is elegant and the recursive algorithm is simple, and even though we memoize every operation, the time performance is on par … Continue reading →
10 Sept 2020
All right, we have our quad data structure, we know how to get and set individual elements, and we know how to display it. We’ve deduplicated it using memoization. How do we step it forward one tick? (Code for this … Continue reading →
8 Sept 2020
Episode 34 will be delayed again — sorry! — because once again the time I had set aside for writing this weekend got consumed by a real-world task that could not wait. (I will try for Thursday of this week.) … Continue reading →
31 Aug 2020
Episode 34 of my ongoing series will be slightly delayed because I spent the time on the weekend I normally spend writing instead rebuilding one of my backyard fences. I forgot to take a before picture, but believe me, it … Continue reading →
26 Aug 2020
Last time in this series we learned about the fundamental (and only!) data structure in Gosper’s algorithm: a complete quadtree, where every leaf is either alive or dead and every sub-tree is deduplicated by memoizing the static factory. Suppose we … Continue reading →
21 Aug 2020
Part 33 of my ongoing series is coming but I did not get all the code written that I wanted to this week, so it will be delayed. In the meanwhile: Living in Canada as a child, of course I … Continue reading →
17 Aug 2020
All right, after that excessively long introduction let’s get into Gosper’s algorithm, also known as “HashLife” for reasons that will become clear quite soon. Since the early days of this series I’ve mostly glossed over the code that does stuff … Continue reading →
14 Aug 2020
Normally this time of year I would be visiting friends and family in Canada, but obviously that’s impossible right now. Instead we took a long weekend at a rental on Bainbridge Island and strolled around some parks in a socially … Continue reading →
13 Aug 2020
Today we will finish off our implementation of Hensel’s QuickLife algorithm, rewritten in C#. Code for this episode is here. Last time we saw that adding change tracking is an enormous win, but we still have not got an O(changes) … Continue reading →
5 Aug 2020
Holy goodness, we are on part 30; I never expected this to go for so long and we have not even gotten to Gosper’s algorithm yet! We will finish up Hensel’s QuickLife algorithm soon I hope. Code for this episode … Continue reading →
3 Aug 2020
We’ve built the foundation of the QuickLife algorithm; now let’s make it go fast. This is going to be a longer episode than usual because we have a large volume of code to get through to perform a relatively straightforward … Continue reading →
30 Jul 2020
We now have enough gear to make a naïve “proto-QuickLife” implementation as a test to see (1) does it work at all? and (2) what is the performance compared to our other implementations at various levels of sophistication? Code for … Continue reading →
27 Jul 2020
We’re continuing with our deep dive into Alan Hensel’s QuickLife algorithm, rewritten in C# with an emphasis on clarity. When last we left off we had the following established: A Quad2 is an immutable wrapper around a ushort A Quad3 … Continue reading →
23 Jul 2020
Last time on FAIC we saw how we could start with nine 2-quads — a 12×12 grid of cells — and with only a handful of ands, ors and table lookups we could get an 8×8 grid of cells of … Continue reading →
20 Jul 2020
Let’s crisp up the problem from last episode. The problem for today’s episode is to write a method that takes these nine 2-quads: Computes these sixteen 1-quads: And returns these four 2-quads: Those four 2-quads form a 3-quad; I haven’t … Continue reading →
16 Jul 2020
When last we left off we had representations for 0-quads — a single bit — 1-quads — four bits in a row — and 2-quads — a wrapper data structure around an unsigned short that could extract single cells or … Continue reading →
15 Jul 2020
I went out to Shilshole Bay Marina Tuesday night to get a few photos of the comet; it is quite spectacular! If you’re going stargazing this week, bring binoculars, look to the northwest about an hour after sunset, below the … Continue reading →
13 Jul 2020
This series is getting much longer than I expected, but I’m having a great time, so let’s keep it going. I want to look at two more algorithms; for the next few episodes we’ll look at the brilliant and subtle … Continue reading →
9 Jul 2020
Code for this episode is here. So far in this series every algorithm we’ve attempted has been either O(cells) or O(changes) in time, and O(cells) in space. Going with a straightforward “big square with dead cells surrounding it” approach tends … Continue reading →
6 Jul 2020
Last time on FAIC I said that we were done with Stafford’s algorithm, but right after that went up I received a thoughtful email from David Stafford himself; he then introduced me to Michael Abrash and Terje Mathisen, who was … Continue reading →
2 Jul 2020
In today’s episode I want to again pause for a moment — this time, to verify that our allegedly O(change) implementation of Stafford’s algorithm really does have its performance gated on the number of cells changing in a tick. Here’s … Continue reading →
29 Jun 2020
Code for this episode is here. Today we can finish off our C# implementation of Stafford’s algorithm. Last time we turned the first pass into a table lookup; it might be a bit harder to optimize the second pass. Let’s … Continue reading →
25 Jun 2020
Code for this episode is here. A couple episodes back we did a first cut at implementing Stafford’s algorithm using the triplet data structure to store the current and upcoming states of three cells and their living neighbour counts, all … Continue reading →
22 Jun 2020
Code for this episode is here. We’ll take a short break from getting to our C# version of Stafford’s algorithm; in this episode I want to talk about some improvements to the UI, and also talk about some more fundamental … Continue reading →
18 Jun 2020
Source code for this episode is here. We are continuing with our project to gradually morph Abrash’s “remember the living neighbour counts” algorithm into Stafford’s algorithm. I’m going to start today by adding two very small bit-twiddling optimizations to the … Continue reading →
15 Jun 2020
Code for this episode is here. Where were we? I was gradually changing Abrash’s “remember the neighbour counts” into Stafford’s algorithm from an early 1990s optimization contest. In this series I’m going to illustrate the algorithm in C#, and we’ll … Continue reading →
11 Jun 2020
Source code for this episode is here. Before we get into today’s episode proper, a quick note. I’ve updated the client so that it now supports the ability to load a pattern off disk, execute that pattern, and “reset” back … Continue reading →
2 Jun 2020
First off, a brief programming note: now is not the right time to continue with the usual topic of this blog: a lighthearted exploration of algorithmic complexity and optimization. We’ll get back to that at a later date. I have … Continue reading →
28 May 2020
Source code for this episode is here. Just as a reminder: I am developing my C# version of Stafford’s “QLIFE” algorithm by taking Abrash’s “keep the neighbour counts around” algorithm and gradually adding optimizations. That’s much easier to understand than … Continue reading →
26 May 2020
Code for this episode can be found here. Exciting news for the client; I have added a play/pause button. I suppose I could have added that single line of code earlier, but hey, better now than later. Last time on … Continue reading →
21 May 2020
Source code for this episode is here. I’ve added a panel to the UI that moves as the UI is resized; I’ll add some controls to it in future episodes. Back in 1994 I made a photocopy of an article … Continue reading →
18 May 2020
Last time on FAIC I discussed a technique for parallelizing computation of Life grids by using SIMD instructions to handle 256 bits worth of grid state truly in parallel. Today I’m going to not present an implementation, but rather discuss … Continue reading →
14 May 2020
Code for this episode can be found here, which — unusually — is not my GitHub repo. Last time on FAIC I mentioned that there were two basic techniques for improving raw performance: keep the algorithm the same but find … Continue reading →
11 May 2020
Last time on FAIC we took a look at Scholes’ extremely concise Life algorithm, which treats a grid as an array that you can treat as a mathematical value with some unusual but entirely straightforward manipulations. We didn’t get the … Continue reading →
7 May 2020
Code for today’s episode can be found here. I’ve added drag scrolling to the user interface, so if you click and hold, you can move around the grid much the same way that you’d move around an online map site. … Continue reading →
4 May 2020
Code for this episode can be found here. The only interesting change I’ve made to the client is that if you press “P”, it pauses the simulation and runs 5000 steps of the “acorn” pattern, and then dumps the number … Continue reading →
30 Apr 2020
Code for this episode can be found here. I have not added any more code to the engine, but the client now has two features of great use to me; pressing space toggles whether the simulation is running or paused, … Continue reading →
27 Apr 2020
Code for this episode can be found here. I have not updated the Life algorithm, but I have added a new feature to the client, namely, you can now resize the form and the display box will resize along with … Continue reading →
23 Apr 2020
Code for this episode can be found here. All right, let’s get into it. Since I want this series to concentrate on the algorithms and not the user interface, what I will probably do is make incremental improvements to the … Continue reading →
20 Apr 2020
Code for this episode can be found here. There are literally fifty years of articles explaining Conway’s Game of Life, starting with the one that introduced it to me: the October 1970 issue of Scientific American. Seems like a great … Continue reading →
13 Apr 2020
The mathematician John Horton Conway has died, apparently due to the covid-19 epidemic, at the age of 82. I never met him but by all accounts, he was a delightful person and brilliant mathematician; his charming book on introductory game … Continue reading →
10 Apr 2020
Welcome to yet another working-from-home pandemic episode of Fun For Friday Fabulous Adventures. Over the past while I’ve gradually been looking for music, movies and games I enjoyed as a teenager and seeing how they hold up. So I am … Continue reading →
27 Mar 2020
A student who I used to tutor in CS occasionally sent me a meme yesterday which showed “NEW GRAD vs SENIOR DEVELOPER”; the new grad is all caps yelling NO! YOU CAN’T JUST USE BRUTE FORCE HERE! WE NEED TO … Continue reading →
24 Mar 2020
I don’t enjoy politics, I don’t know enough about it, and my privilege greatly insulates me from its negative effects, and so I don’t talk about it much on this blog. My intention in creating the blog lo these decades … Continue reading →
20 Mar 2020
Good Friday afternoon all and welcome to this working-from-home-and-obsessively-washing-hands edition of FAIC. I am posting today from my recently-transformed spare room which is now apparently my office. Scott Hanselman started a great twitter thread of techies showing off their home … Continue reading →
10 Mar 2020
Here’s an interesting question I saw on StackOverflow recently; it was interesting because the answer seems obvious at first, but making a small change to the question makes the answer very different. The original question was: suppose we have an … Continue reading →
27 Feb 2020
My manager and I got off on a tangent in our most recent one-on-one on the subject of the durability of design mistakes in programming languages. A particular favourite of mine is the worst of the operator precedence problems of … Continue reading →
24 Feb 2020
Well this is a first. Twitter user Plazmaz brought a scam github repository and web site to my attention; see his thread on Twitter for details. It’s a pretty obviously fake site, and there is some evidence in the metadata … Continue reading →
24 Jan 2020
While watching the first episode of the new Star Trek series just now I noticed a nice little Easter egg: Admiral Picard (retired) apparently has the same 1982 science fiction book club edition of The Complete Robot handy on his … Continue reading →
30 Dec 2019
One last post for this decade. There has been some discussion on tech twitter lately on the subject of whether it is possible to be “successful” in the programming business without working long hours. I won’t dignify the posts which … Continue reading →
11 Dec 2019
You might recall that before my immensely long series on ways we could make C# a probabilistic programming language, I did a short series on how we can automatically computed the exact derivative in any direction of a real-valued function … Continue reading →
8 Nov 2019
Source code for this episode is here. Welcome to this special bonus episode of Fixing Random, the immensely long blog series where I discuss ways to add probabilistic programming features into C#. I ran into an interesting problem at work … Continue reading →
16 Aug 2019
My friend Larry from the previous episode mentioned to me that a group of several male and female belted kingfishers had been spotted at the river; I’d never seen kingfishers at our little river before and I wanted to get … Continue reading →
15 Aug 2019
I enjoy photographing dragonflies and damselflies; this year I got some pretty reasonable shots of common blue damselflies, white-faced meadowhawks, a twelve-spotted skimmer, and my favourite, ebony jewelwings. It can be hard to get these little guys in focus, but … Continue reading →
14 Aug 2019
Today, I have a Mystery Of The Unknown for you to solve. Unlike most of the puzzlers on this blog, I don’t know the answer. UPDATE: Mystery solved! See below. On August 4th at about 20 minutes past 10 PM … Continue reading →
13 Aug 2019
I’m back from my annual vacation where I fly south to Canada and take way too many photos. As with all my hobbies, I’m not a very good nature photographer but I do enjoy it, and this year was particularly … Continue reading →
27 Jul 2019
All right, let’s finish this thing off! First, I want to summarize, second I want to describe a whole lot of interesting stuff that I did not get to, and third, I want to give a selection of papers and … Continue reading →
15 Jul 2019
Let’s sum up the last few episodes: Suppose we have a distribution of doubles, p, and a function f from double to double. We often want to answer the question “what is the average value of f when it is given samples … Continue reading →
8 Jul 2019
Last time on FAIC we were attacking our final problem in computing the expected value of a function f applied to a set of samples from a distribution p. We discovered that we could sometimes do a “stretch and shift” of … Continue reading →
1 Jul 2019
Last time on FAIC we finally wrote a tiny handful of lines of code to correctly implement importance sampling; if we have a distribution p that we’re sampling from, and a function f that we’re running those samples through, we can compute … Continue reading →
24 Jun 2019
One more time! Suppose we have our nominal distribution p that possibly has “black swans” and our helper distribution q which has the same support, but no black swans. We wish to compute the expected value of f when applied to samples … Continue reading →
17 Jun 2019
Last time on FAIC we deduced the idea behind the “importance sampling” technique for determining the average value of a function from double to double — call it f — when it is applied to samples from a possibly-non-normalized weighted distribution of … Continue reading →
10 Jun 2019
Last time on FAIC we implemented a better technique for estimating the expected value of a function f applied to samples from a distribution p: Compute the total area (including negative areas) under the function x => f(x) * p.Weight(x) … Continue reading →
3 Jun 2019
Last time on FAIC I showed why our naïve implementation of computing the expected value can be fatally flawed: there could be a “black swan” region where the “profit” function f is different enough to make a big difference in … Continue reading →
30 May 2019
I’m continuing with my project to port over, reformat and update a decade of old blog posts. Today, a few days in mid-October 2003; this is still my second month of blogging and I am writing at what I would … Continue reading →
28 May 2019
Last time on FAIC we reviewed the meaning of “expected value”: when you get a whole bunch of samples from a distribution, and a function on those samples, what is the average value of the function’s value as the number … Continue reading →
20 May 2019
Last time in this series we saw that we could compute a continuous posterior distribution when given a continuous prior and a discrete likelihood function; I hope it is clear how that is useful, but I’d like to switch gears … Continue reading →
16 May 2019
We’ll get back to stochastic programming soon; I wanted to do a quick post about some updates to my earlier series on anti-unification. As I noted in the final part of that series, I spent a few months in 2018 … Continue reading →
13 May 2019
Last time on FAIC I posed and solved a problem in Bayesian reasoning involving only discrete distributions, and then proposed a variation on the problem whereby we change the prior distribution to a continuous distribution, while preserving that the likelihood … Continue reading →
10 May 2019
[It is] a spectacular vindication of the principle that each individual coin spun individually is as likely to come down heads as tails and therefore should cause no surprise that each individual time it does. Thus Guildenstern (or is it … Continue reading →
6 May 2019
Last time on FAIC we implemented a technique for sampling from a non-normalized target PDF: Find an everywhere-larger helper PDF that we can sample from. Sample from it. Accept or reject the sample via a coin flip with the ratio … Continue reading →
2 May 2019
Last time on FAIC we went through a loose, hand-wavy definition of what it means to have a “weighted” continuous distribution: our weights are now doubles, and given by a Probability Distribution Function; the probability of a sample coming from … Continue reading →
1 May 2019
I’m continuing in my efforts to move and update all my old content from my MSDN blog to ericlippert.com. Today, posts from early October of 2003. In, out, in-out, make up your mind already The late-binding code designed for OLE … Continue reading →
29 Apr 2019
We’ve been mostly looking at small, discrete distributions in this series, but we started this series by looking at continuous distributions. Now that we have some understanding of how to solve probability problems on simple discrete distributions and Markov processes, … Continue reading →
26 Apr 2019
Last time on FAIC we implemented the Markov process distribution, which is a distribution over state sequences, where the initial state and each subsequent state is random. There are lots of applications of Markov processes; a silly one that I’ve … Continue reading →
23 Apr 2019
[Code for this episode is here.] So far in this series we’ve very briefly looked at continuous distributions on doubles, and spent a lot of time looking at discrete distributions with small supports. Let’s take a look at a completely … Continue reading →
17 Apr 2019
So… I’ve got good news and bad news. The good news is: I’ve described an interface for discrete probability distributions and implemented several distributions. I’ve shown how projecting a distribution is logically equivalent to the LINQ Select operator. I’ve shown … Continue reading →
15 Apr 2019
[Code for this episode is here.] Last time in this series I left you with several challenges for improving our DSL for imperative probabilistic workflows. But first, a puzzle: Question One: You are walking down the street when you see … Continue reading →
12 Apr 2019
I’m continuing my efforts to port over and update my old blog content. The previous episode is here. We’re still in the first few weeks of me blogging; I was pumping out articles at a rate I now consider to … Continue reading →
11 Apr 2019
Last time in this series I proposed a stripped-down DSL for probabilistic workflows. Today, let’s see how we could “lower” it to ordinary C# 7 code. I’ll assume of course that we have all of the types and extension methods that … Continue reading →
9 Apr 2019
Thanks again to the good people at Microsoft who have kept my old blog alive for now; my plan is to port the articles from the old site over, and then they will redirect from the old URLs to the … Continue reading →
8 Apr 2019
Without further ado, here’s my proposed stripped-down C# that could be a DSL for probabilistic workflows; as we’ll see, it is quite similar to both enumerator blocks from C# 2 and async/await from C# 5. (Code for this episode can … Continue reading →
4 Apr 2019
I’ve got no code for you this time; instead here are some musings about language design informed by our discussion so far. One of the most important questions to ask when designing a language feature is: what should the balance … Continue reading →
2 Apr 2019
Before that silly diversion I mentioned that we will be needing the empty distribution; today, we’ll implement it. It’s quite straightforward, as you’d expect. [Code for this episode is here.] public sealed class Empty<T> : IDiscreteDistribution<T> { public static readonly Empty<T> Distribution = new Empty<T>(); private Empty() { } public T Sample() => throw new Exception(“Cannot sample from empty distribution”);…
1 Apr 2019
I just thought of a really cute application of the stochastic workflow technology we’ve been working on; most of the series has already been written but it fits in here, so I’m going to insert this extra bonus episode. We’ll … Continue reading →