The Ruby programming language has the notion of aHash. AHashis a dictionary-like collection of unique keys and their values. Ruby hashes have most of the semantics of an ES6Map, 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 that have not been set. In JavaScript, the default value is alwaysundefined.In this essay we will look at rolling our ownHashclass with Ruby-like semantics, and then we’ll examine one of the most interesting th ...继续阅读 (25)

…and two practical applications…TheY Combinatoris an important result in theoretical computer science.1In 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 theY 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 benefits of writing recursive functions in “why bird form” is that we can compose and decorate them easily.We’ll then derive the “Decoupled Trampoline,” a/k/a “Long-Tailed Widowbird.” The decoupled trampoline ...继续阅读 (37)

…and two practical applications…TheY Combinatoris an important result in theoretical computer science.1In 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 theY 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 benefits of writing recursive functions in “why bird form” is that we can compose and decorate them easily.We’ll then derive the “Decoupled Trampoline,” a/k/a “Long-Tailed Widowbird.” The decoupled trampoline ...继续阅读 (18)

Functions all the way downis a book aboutrecursion, a book aboutrecreational programming, and a book aboutJavaScript, in that order.Recursionhas an unusual place in the programming world. From a Computer Science perspective, it is one of the most important topics we study. Recursion makes it possible for simple systems like the Lambda Calculus and Combinatorial Logic to perform arbitrarily complex computations. Some problem domains include data that is inherently self similar, and recursive functions are the most natural way to work with these kinds of problems. Self-documenting or declarative ...继续阅读 (17)

This essay has been incorporated intoWhy Y? Deriving the Y Combinator in JavaScriptInTo Grok a Mockingbird, we explored themockingbird, a recursive combinator that decouples recursive functions from themselves. Decoupling recursive functions from themselves allows us to compose them more flexibly, such as with decorators.1This also separates the concern of the recursive algorithm to be performed from the mechanism of implementing recursion. This allowed us to implement the Jackson’s Widowbird, a variation of the mockingbird that uses trampolining to execute tail-recursive functions in constant ...继续阅读 (28)

Using recursive combinators to enhance functional composition, with special guests the Mockingbird, Widowbird, and Why BirdIn this essay we’re going to look atrecursive 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 tightly coupled to themselves.Recursive combinators have important theoretical implications, but for the working programmer they decouple recursive functions from the mechanism that implements recursion. Th ...继续阅读 (37)

Using recursive combinators to enhance functional composition, with special guests the Mockingbird, Widowbird, and Why BirdIn this essay we’re going to look atrecursive 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 tightly coupled to themselves.Recursive combinators have important theoretical implications, but for the working programmer they decouple recursive functions from the mechanism that implements recursion. Th ...继续阅读 (21)

A few weeks ago, I ordered a copy of the Sesquicentennial Edition ofThe 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 ofKnots 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 that I ever wrote from scratch, a program that searched for solutions to the eight queens puzzle.Prelude: 1972 – 1977This prelude is long on nostalgia and short on programming. If that does not interest yo ...继续阅读 (44)

A few weeks ago, I ordered a copy of the Sesquicentennial Edition ofThe 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 ofKnots 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 that I ever wrote from scratch, a program that searched for solutions to the eight queens puzzle.Prelude: 1972 – 1977This prelude is long on nostalgia and short on programming. If that does not interest yo ...继续阅读 (24)

InRecursion? 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 recursionThe shallow definition of a recursive algorithm is a function that directly or indirectly calls itself. For example, thefactorialof an integer:In mathematics, the factorial of a non-negative integern, denoted byn!, is the product ...继续阅读 (24)

InRecursion? 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 recursionThe shallow definition of a recursive algorithm is a function that directly or indirectly calls itself. For example, thefactorialof an integer:In mathematics, the factorial of a non-negative integern, denoted byn!, is the product ...继续阅读 (23)

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 thateveryrecursive algorithm can be implemented with iteration. Whether weshouldimplement a recursive algorithm with iteration is, as they say, “an open problem,” and the factors going into that decision are so varied that there is no absolute “Always favour recursion” or “Never use r ...继续阅读 (34)

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 thateveryrecursive algorithm can be implemented with iteration. Whether weshouldimplement a recursive algorithm with iteration is, as they say, “an open problem,” and the factors going into that decision are so varied that there is no absolute “Always favour recursion” or “Never use r ...继续阅读 (25)

In “How I Learned to Stop Worrying and ❤️ the State Machine,” we built an extremely basicstate machineto model a bank account.State machines, as we discussed, are a very useful tool for organizing the behaviour ofdomain 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 state machine is an object, but it has a distinctive “behaviour.” It is always in exactly one of a finite number of states, and its behaviour is determined by its state, right down to what methods it has in eac ...继续阅读 (38)

In “How I Learned to Stop Worrying and ❤️ the State Machine,” we built an extremely basicstate machineto model a bank account.State machines, as we discussed, are a very useful tool for organizing the behaviour ofdomain 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 state machine is an object, but it has a distinctive “behaviour.” It is always in exactly one of a finite number of states, and its behaviour is determined by its state, right down to what methods it has in eac ...继续阅读 (22)

“Any sufficiently complicated model class contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of a state machine.”–former colleague1Domain modelsare 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, or more abstract things like meetings and incidents.My colleague’s insight was that most domain models end up having a representation of various states. Over time, they build up a lot of logic around how ...继续阅读 (35)

“Any sufficiently complicated model class contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of a state machine.”–former colleague1Domain modelsare 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, or more abstract things like meetings and incidents.My colleague’s insight was that most domain models end up having a representation of various states. Over time, they build up a lot of logic around how ...继续阅读 (26)

In number theory, aright-truncatable primeis 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.–WikipediaIn this essay, we’re going to write some code to generate truncatable primes. Along the way, we’ll get some practice working with JavaScript generators implmenting lazily generated lists, we’ll get a chance to look at some of the ways a naïve algorithm might have terrible runtime performance, and we’ll ge ...继续阅读 (23)

In number theory, aright-truncatable primeis 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.–WikipediaIn this essay, we’re going to write some code to generate truncatable primes. Along the way, we’ll get some practice working with JavaScript generators implmenting lazily generated lists, we’ll get a chance to look at some of the ways a naïve algorithm might have terrible runtime performance, and we’ll ge ...继续阅读 (26)

iterators and iterables, a quick recapitulationIn JavaScript, iterators and iterables provide an abstract interface for sequentially accessing values, such as we might find in collections like arrays or priority queues.1An iterator is an object with a.next()method. When you call it, you get a Plain Old JavaScript Object (or “POJO”) that has adoneproperty. If the value ofdoneisfalse, you are also given avalueproperty that represents, well, a value. If the value ofdoneistrue, you may or may not be given avalueproperty.Iterators are stateful by design: Repeatedly invoking the.next()method usually ...继续阅读 (32)

iterators and iterables, a quick recapitulationIn JavaScript, iterators and iterables provide an abstract interface for sequentially accessing values, such as we might find in collections like arrays or priority queues.1An iterator is an object with a.next()method. When you call it, you get a Plain Old JavaScript Object (or “POJO”) that has adoneproperty. If the value ofdoneisfalse, you are also given avalueproperty that represents, well, a value. If the value ofdoneistrue, you may or may not be given avalueproperty.Iterators are stateful by design: Repeatedly invoking the.next()method usually ...继续阅读 (24)

Here are the first sixteen elements of a sequence:. * (*) (*.) ((*)) (*..) (**) (*...) ((*.)) ((*).) (*.*) (*....) (*(*)) (*.....) (*..*) (**.)And the next sixteen:(((*))) (*......) ((*.)*) (*.......) (*.(*)) (*.*.) (*...*) (*........) (*(*.)) ((*)..) (*....*) ((*.).) (*..(*)) (*.........) (***) (*..........)What is the next element in the sequence?solving sequence problemsProblems with this rough form appear regularly in “intelligence” tests. To solve them, you need a couple of different things:First, you need some facility with manipulating abstract relationships and patterns. You need a mod ...继续阅读 (20)

Here are the first sixteen elements of a sequence:. * (*) (*.) ((*)) (*..) (**) (*...) ((*.)) ((*).) (*.*) (*....) (*(*)) (*.....) (*..*) (**.)And the next sixteen:(((*))) (*......) ((*.)*) (*.......) (*.(*)) (*.*.) (*...*) (*........) (*(*.)) ((*)..) (*....*) ((*.).) (*..(*)) (*.........) (***) (*..........)What is the next element in the sequence?solving sequence problemsProblems with this rough form appear regularly in “intelligence” tests. To solve them, you need a couple of different things:First, you need some facility with manipulating abstract relationships and patterns. You need a mod ...继续阅读 (26)

InUsing iterators to write highly composeable code, we took a look at a data transformation and analysis algorithm, and saw that the obviousstaged approachwas highly decomposed, but presented a performance problem in that it created excess duplicates of the entire data set.Whereas thesinge pass approachwas much more memory-efficient, but the code was entangled and monolithic. On a problem small enough to fit in a blog post this isn’t a massive problem, but it’s easy to see how such an approach in production leads to highly coupled, fragile code that cannot be easily factored or decomposed.We c ...继续阅读 (22)

InUsing iterators to write highly composeable code, we saw that thestaged approachto data transformation is decomposed, but duplicates the entire data set. Whereas, thesingle pass approachis 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,transducers.Let’s start with a review of reducing (a/k/a “folding”):reducersAreduceris a function that takes an accumulation and a value, and folds the value into the accumulation. For example, if[1, 2, 3]is an ...继续阅读 (18)

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 f1a543f, 5890595 1a2ddc2, bd11537 1a2ddc2, 5890595 3abe124, 5f2b932 f1a543f, 5f2b932 f1a543f, bd11537 f1a543f, 5890595 1a2ddc2, 5f2b932 1a2ddc2, bd11537 1a2ddc2, 5890595 ...The first column is a pseudo-anonym ...继续阅读 (18)

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 f1a543f, 5890595 1a2ddc2, bd11537 1a2ddc2, 5890595 3abe124, 5f2b932 f1a543f, 5f2b932 f1a543f, bd11537 f1a543f, 5890595 1a2ddc2, 5f2b932 1a2ddc2, bd11537 1a2ddc2, 5890595 ...The first column is a pseudo-anonym ...继续阅读 (18)

Note well: This is an unfinished work-in-progress.Turing Machines and Tooling, Part IIMuch 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, weembraceit? What if we “turn mutation up to eleven?”We know the rough answer without even trying. We’d need a lot of tooling to manage our programs. Which is interesting in its own right, because we might learn a lot about tools for writing software.So with that in mind, we began inPart Iby look ...继续阅读 (20)

InA quick look at reduce, foldl, foldr, and associative order, we discussedfoldlandfoldr, and we said thatfoldlleft-associatedits function, whilefoldrright-associatedits function.These expressions sound familiar. In high school (perhaps sooner!), we learned that some mathematical operators, such as plus and multiply, areassociative, or have theassociative property. Is this the same thing?The answer is short, and would fit in a footnote. They are not the same thing. But let’s take our time, we can write some interesting code to demonstrate that they are not the same thing.the associative proper ...继续阅读 (34)

JavaScript has a method on arrays calledreduce. It’s used for “reducing” a collection to a value of some kind.For example, we can use it to “reduce” an array of numbers to the sum of the numbers:[1,2,3,4,5].reduce((acc,n)=>acc+n)//=> 15Another way to put it is to say that reducefoldsthe array into a single value.If all we saw was stuff like summing the elements of arrays, we might think that “folding” is about taking a collections of things and turning it into just one of those things. Like turning an array of numbers into a number. But not so! Folding can produce any arbitrary value.For examp ...继续阅读 (25)