raganwald.com
Latest posts
Cryptographic techniques used by nCrypt Light in 1994
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 of implementing secure cryptography, so this is presented purely for nostalgia and amusement…
Mutual Recursion in Language
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 accommodate English orthography, but, in most cases, it is preserved in its original language. Résumé…
The Inner Osborne Effect
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 1995 by computer programmer Andrew Koening , was inspired by the book Design Patterns , which…
Remembering John Conway's FRACTRAN, a ridiculous, yet surprisingly deep language
On April 8, 2020, John Horton Conway developed symptoms of COVID-19. On April 11, 2020, he succumbed to the disease. 1 2 3 4 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 making important topics in mathematics engaging and interesting. One of the finest examples of that…
Exploring Regular Expressions, Part II: Regular Languages and Finite-State Automata
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, Computing Machines, and Pushdown Automata . It covers the concepts behind finite-state machines and the…
Exploring Regular Expressions and Finite-State Recognizers, Part I
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 regexen, but the exercise of implementing basic regular expressions is a terrific foundation for…
A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
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 Output Comment '' true the empty string is balanced '()' true '(())' true parentheses can nest '()()'…
Ayoayo and Linear Recursion
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 our functions decoupled from each other and themselves with dependency injection. We’ll then look at…
Structural Sharing and Copy-on-Write Semantics, Part II: Reduce-Reuse-Recycle
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 Structural Sharing to write code that avoids making copies of objects while still retaining the semantics…
Exploring Structural Sharing and Copy-on-Write Semantics, Part I
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 of a slice of an array. In Part II , we’ll consider the problem of resource ownership when…
Alice and Bobbie and Sharleen and Dyck
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 introductions and some basic behavioural questions, about half an hour to a basic programming problem, and…
Pattern Matching and Recursion
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 corresponding closing symbol and the pairs of parentheses are properly nested. For example: Input…
Ruby's Hashes and Perl's Autovivification, in JavaScript
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 have the notion of programmatically determine a default value to be returned when accessing keys…
Why Y? Deriving the Y Combinator in JavaScript
…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 of the mockingbird, but allows us to write more idiomatic JavaScript. We’ll see that one of the…
To Grok a Mockingbird
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 is recursive. Recursive combinators make it possible to create recursive functions that are not…
The Eight Queens Problem... and Raganwald's Unexpected Nostalgia
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 Unexpected Hanging . I nearly gasped out loud, savouring the memory of one of the earliest computer programs…
A Trick of the Tail
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 quick recap of what we explored in the previous post: recursion, see recursion The shallow definition…
Recursion? We don't need no stinking recursion!
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…” The good news is that every recursive algorithm can be implemented with iteration. Whether we…
More State Machine ❤️: From Reflection to Statecharts
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 sphere of knowledge, influence or activity (the “domain”) that need to be modelled in software. A…
How I Learned to Stop Worrying and ❤️ the State Machine
“Any sufficiently complicated model class contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of a state machine.”–former colleague 1 Domain models are representations of meaningful real-world concepts pertinent to a sphere of knowledge, influence or activity (the “domain”) that need to be modelled in software. Domain models can represent concrete real-word objects,…
Truncatable Primes in JavaScript
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 this essay, we’re going to write some code to generate truncatable primes. Along the way, we’ll…
Closing Iterables is a Leaky Abstraction
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 Plain Old JavaScript Object (or “POJO”) that has a done property. If the value of done is false , you…
A Sequence Problem
Here are the first sixteen elements of a sequence: . * (*) (*.) ((*)) (*..) (**) (*...) ((*.)) ((*).) (*.*) (*....) (*(*)) (*.....) (*..*) (**.) And the next sixteen: (((*))) (*......) ((*.)*) (*.......) (*.(*)) (*.*.) (*...*) (*........) (*(*.)) ((*)..) (*....*) ((*.).) (*..(*)) (*.........) (***) (*..........) What is the next element in the sequence? solving sequence problems Problems with this…
What's a Transducer?
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 approach for building composeable pipelines of transformations without incurring a memory penalty,…
Having our cake and eating it too: "Using iterators to write highly composeable code"
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 like this: 1a2ddc2, 5f2b932 f1a543f, 5890595 3abe124, bd11537 f1a543f, 5f2b932 f1a543f, bd11537…
foldl, foldr, and associative order
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 talking with people in the functional programming community, we often hear the term fold . Folding is…
Turing Machines and Tooling, Part I
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 mutation, we embrace it? What if we “turn mutation up to eleven?” We know the rough answer without even…
The Lumberjane Song
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, mentors youth She goes to the lavatory On Wednesdays she races bicycles Hers is espresso, if you please…
Time, Space, and Life As We Know It
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, more than on the performance of quadtrees. Today, we’ll take a closer look at taking advantage of…
Why Recursive Data Structures?
In this essay, we are going to look at recursive algorithms, and how sometimes, we can organize an algorithm so that it resembles the data structure it manipulates, and organize a data structure so that it resembles the algorithms that manipulate it. When algorithms and the data structures they manipulate are isomorphic , 1 the code we write is easier to understand for exactly the same reason that…
From Higher-Order Functions to Libraries And Frameworks
In this essay, we will take a look at some higher-order functions, with an eye to seeing how they can be used to make our programs more expressive, while balancing that against the need to limit the perceived complexity of our programs. introduction: expressiveness One of the most basic ideas in programming is that functions can invoke other functions. 1 When a function invokes other functions,…
Anamorphisms in JavaScript
Unfolded, © 2011 Regulla , Some rights reserved preamble: unfolds and folds Anamorphisms are functions that map from some object to a more complex structure containing the type of the object. For example, mapping from an integer to a list of integers. Here’s an anamorphism: function downToOne ( n ) { const list = []; for ( let i = n ; i > 0 ; -- i ) { list . push ( i ); } return list ; } downToOne…
From Mixins to Object Composition
In Why Are Mixins Considered Harmful , we saw that concatenative sharing–as exemplified by mixins–leads to snowballing complexity because of three effects: Lack of Encapsulation Implicit Dependencies Name Clashes We looked at some variations on creating encapsulation to help reduce the “surface area” for dependencies to grow and names to clash, but noted that this merely slows down the growth of…
Why Are Mixins Considered Harmful?
update : Part II, From Mixins to Object Composition is now available. In Mixins Considered Harmful , Dan Abramov wrote something that sounds familiar to everyone 1 who works with legacy applications: Some of our code using React gradually became incomprehensible. Occasionally, the React team would see groups of components in different projects that people were afraid to touch. These components…