Preface (2023) The following described the cryptographic protocol and algorithm used by nCrypt Light back in 1993-94. I wrote nCrypt Light in the hope of creating a strong cryptography app for the orginal Newton MessagePad 100. Rolling your own crypto is well-understood to be the complete opposite o...

This is not a programming post. loanwords A loanword is a term taken from another language and used without translation; it has a specific meaning that (typically) does not otherwise exist in a single English word. Sometimes the word’s spelling or pronunciation (or both) is slightly altered to accom...

In software development, we talk a lot about software anti-patterns, how to recognize them, and how to extricate yourself from them via refactoring. An anti-pattern is a common response to a recurring problem that is usually ineffective and risks being highly counterproductive. The term, coined in 1...

On April 8, 2020, John Horton Conway developed symptoms of COVID-19. On April 11, 2020, he succumbed to the disease.1234 Like so very, very many, I mourn Conway’s passing, and yet I also celebrate his life. I celebrate his accomplishments, I celebrate his curiosity, and I celebrate his skill at maki...

This is Part II of “Exploring Regular Expressions.” If you haven’t already, you may want to read Part I first, where we wrote a compiler that translates formal regular expressions into finite-state recognizers. You may also want another look at the essay, A Brutal Look at Balanced Parentheses, Compu...

Prelude In this essay, we’re going to explore regular expressions by implementing regular expressions. This essay will be of interest to anyone who would like a refresher on the fundamentals of regular expressions and pattern matching. It is not intended as a practical “how-to” for using modern rege...

As discussed in Pattern Matching and Recursion, a well-known programming puzzle is to write a function that determines whether a string of parentheses is “balanced,” i.e. each opening parenthesis has a corresponding closing parenthesis, and the parentheses are properly nested. For example: Input Out...

In this essay, we’re going to look at a game called Ayoayo. As we’ll read, Ayoayo is part of the Mancala family of games that has spread throughout Africa, and beyond. We’ll write some code that would be useful if we were implementing an Ayoayo game, and along the way, we’ll look at how we can keep ...

This is Part II of an essay that takes a highly informal look at two related techniques for achieving high performance when using large data structures: Structural Sharing, and Copy-on-Write Semantics. In Part I, we used recursive functions that operate on lists to explore how we could use Structura...

This essay takes a highly informal look at two related techniques for achieving high performance when using large data structures: Structural Sharing, and Copy-on-Write Semantics. In Part I, we’ll look at the background of Structural Sharing and start making a Slice class that abstracts the concept ...

Alice and Bobbie were comparing notes after interviewing interns for an upcoming work term with their company, HipCo. Their interview process, although often maligned on social media, worked reasonably well for their purposes: They spent an hour with each candidate, devoting twenty minutes to introd...

A popular programming “problem” is to determine whether a string of parentheses is “balanced:” Given a string that consists of open and closed parentheses, write a function that determines whether the parentheses in the string are balanced. “Balanced” parentheses means that each opening symbol has a...

The Ruby programming language has the notion of a Hash. A Hash is a dictionary-like collection of unique keys and their values. Ruby hashes have most of the semantics of an ES6 Map, but also have the syntactic conveniences of Plain-Old-JavaScript-Objects (“POJOs”). Interestingly, Ruby hashes also ha...

…and two practical applications… The Y Combinator is an important result in theoretical computer science.1 In this essay, after a brief review of the work we’ve already done on the Mockingbird, we’ll derive the Why Bird, known most famously as the Y Combinator. The why bird provides all the benefits...

Using recursive combinators to enhance functional composition, with special guests the Mockingbird, Widowbird, and Why Bird In this essay we’re going to look at recursive combinators. A recursive combinator is a function that takes another function that is not recursive, and returns a function that ...

A few weeks ago, I ordered a copy of the Sesquicentennial Edition of The Annotated Alice. As is their wont, Amazon’s collaborative filters showed me other books that might be of interest to me, and I spotted a copy of Knots and Borromean Rings, Rep-Tiles, and Eight Queens: Martin Gardner’s Unexpecte...

In Recursion? We don’t need no stinking recursion!, we looked at seven different techniques for turning recursive functions into iterative functions. In this post, we’re going to take a deeper look at technique #3, convert recursion to iteration with tail calls. Before we dive into it, here’s a quic...

Interviewer: “Please whiteboard an algorithm that Counts the leaves in a tree/Solves Towers of Hanoi/Random pet recursion problem.” Interviewee: “Ok… Scribble, scribble… That should do it.” Interviewer: “That looks like it works, but can you convert it to an iterative solution?” Interviewee: “Hmmmm…...

In “How I Learned to Stop Worrying and ❤️ the State Machine,” we built an extremely basic state machine to model a bank account. State machines, as we discussed, are a very useful tool for organizing the behaviour of domain models, representations of meaningful real-world concepts pertinent to a sph...

“Any sufficiently complicated model class contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of a state machine.”–former colleague1 Domain models are representations of meaningful real-world concepts pertinent to a sphere of knowledge, influence or activity (the “domai...

In number theory, a right-truncatable prime is a prime number which, in a given base, contains no 0, and if the last (“right”) digit is successively removed, then all resulting numbers are prime. 7393 is an example of a right-truncatable prime, since 7393, 739, 73, and 7 are all prime. –Wikipedia In...

iterators and iterables, a quick recapitulation In JavaScript, iterators and iterables provide an abstract interface for sequentially accessing values, such as we might find in collections like arrays or priority queues.1 An iterator is an object with a .next() method. When you call it, you get a Pl...

Here are the first sixteen elements of a sequence: . * (*) (*.) ((*)) (*..) (**) (*...) ((*.)) ((*).) (*.*) (*....) (*(*)) (*.....) (*..*) (**.) And the next sixteen: (((*))) (*......) ((*.)*) (*.......) (*.(*)) (*.*.) (*...*) (*........) (*(*.)) ((*)..) (*....*) ((*.).) (*..(*)) (*.........) (***) ...

In Using iterators to write highly composeable code, we saw that the staged approach to data transformation is decomposed, but duplicates the entire data set. Whereas, the single pass approach is more efficient, but the code was entangled and monolithic. Now we’re going to look at an interesting app...

Consider this problem: We have a hypothetical startup that, like so many other unimaginative clones of each other, provides some marginal benefit in exchange for tracking user locations. We want to mine that location data. For the purposes of this brief blog post, we might have a file that looks lik...

This essay originally appeared in 2017. Eagle-eyed readers pointed out that the original implementation of foldr had incorrect semantics. The essay has now been substantially revised to provide an implementation of foldr that is much closer to the one we find in lazy languages like Haskell. When tal...

Note well: This is an unfinished work-in-progress. Turing Machines and Tooling, Part I Much is made of “functional” programming in JavaScript. People get very excited talking about how to manage, minimize, or even eliminate mutation and state. But what if, instead of trying to avoid state and mutati...

SINGER I’m a lumberjane and I’m OK I sleep all night and I code all day NERD CHOIR She’s a lumberjane and she’s OK She sleeps all night and codes all day I write clean code, I mentor youth I go to the lavatory On Wednesdays I race bicycles Mine’s espresso, if you please She writes clean code, mentor...

In Why Recursive Data Structures? we used multirec, a recursive combinator, to implement quadtrees and coloured quadtrees (The full code for creating and rotating quadtrees and coloured quadtrees is below). Our focus was on the notion of an isomorphism between the data structures and the algorithms,...