# Hedonistic Learning

Learning for the fun of it

## Constructivist Motto

I don’t believe classical logic is false; I just believe that it is not true.

## The Mistake Everyone Makes with KnockoutJS

### Introduction

Knockout is a nice JavaScript library for making values that automatically update when any of their “dependencies” update. Those dependencies can form an arbitrary directed acyclic graph. Many people seem to think of it as “yet another” templating library, but the core idea which is useful far beyond “templating” is the notion of observable values. One nice aspect is that it is a library and not a framework so you can use it as little or as much as you want and you can integrate it with other libraries and frameworks.

At any rate, this article is more geared toward those who have already decided on using Knockout or a library (in any language) offering similar capabilities. I strongly suspect the issues and solutions I’ll discuss apply to all similar sorts of libraries. While I’ll focus on one particular example, the ideas behind it apply generally. This example, admittedly, is one that almost anyone will implement, and in my experience will do it incorrectly the first time and won’t realize the problem until later.

### The Problem

When doing any front-end work, before long there will be a requirement to support “multi-select” of something. Of course, you want the standard select/deselect all functionality and for it to work correctly, and of course you want to do something with the items you’ve selected. Here’s a very simple example:

Number selected:
Item

Here, the number selected is an overly simple example of using the selected items. More realistically, the selected items will trigger other items to show up and/or trigger AJAX requests to update the data or populate other data. The HTML for this example is completely straightforward.

``````<div id="badExample">
Number selected: <span data-bind="text: $data.numberSelected()"></span> <table> <tr><th><input type="checkbox" data-bind="checked:$data.allSelected"/></th><th>Item</th></tr>
<!-- ko foreach: { data: $data.items(), as: '$item' } -->
<tr><td><input type="checkbox" data-bind="checked: $data.selected"/></td><td data-bind="text: 'Item number: '+$data.body"></td></tr>
<!-- /ko -->

## High dimensional thought experiment from Hamming

This is a simple mathematical thought experiment from Richard Hamming to demonstrate how poor our intuition for high dimensional spaces is. All that is needed is some basic, middle school level geometry and algebra. Consider a 2x2 square centered at the origin. In each quadrant place circles as big as possible so that they fit in the square and don’t overlap. They’ll clearly have radius 1/2. See the image below. The question now is what’s the radius of the largest circle centered at the origin that doesn’t overlap the other circles. It’s clear from symmetry that the inner circle is going to touch all the other circles at the same time, and it is clear that it is going to touch along the line from the origin to the center of one of the outer circles. So the radius of the inner circle, r, is just the distance from the origin to the center of one of the outer circles minus the radius of the outer circle, namely 1/2. As an equation: `r = sqrt(1/2^2 + 1/2^2) - 1/2 = sqrt(2)/2 - 1/2 ~~ 0.207106781` Now if we go to three dimensions we’ll have eight circles instead of four, but everything else is the same except the distances will now be `sqrt(1/2^2 + 1/2^2 + 1/2^2)`. It’s clear that the only difference for varying dimensions is that in dimension n we’ll have n 1/2^2 terms under the square root sign. So the general solution is easily shown to be: `r = sqrt(n)/2 - 1/2` You should be weirded out now. If you aren’t, here’s a hint: what happens when n = 10? Here’s another hint: what happens as n approaches oo?

## Behavioral Reflection

The ultimate goal of behavioral reflection (aka procedural reflection and no doubt other things) is to make a language where programs within the language are able to completely redefine the language as it executes. This is arguably the pinnacle of expressive power. This also means, though, local reasoning about code is utterly impossible, essentially by design.

Smalltalk is probably the language closest to this that is widely used. The Common Lisp MOP (Meta-Object Protocol) is also inspired by research in this vein. The ability to mutate classes and handle calls to missing methods as present in, e.g. Ruby, are also examples of very limited forms of behavioral reflection. (Though, for the latter, often the term “structural reflection” is used instead, reserving “behavioral reflection” for things beyond mere structural reflection.)

### Very Brief History

The seminal reference for behavioral reflection is Brian Smith’s 1982 thesis on 3-LISP. This was followed by the languages Brown, Blond, Refci, and Black in chronological order. This is not a comprehensive list, and the last time I was in to this was about a decade ago. (Sure enough, there is some new work on Black and some very new citations of Black.)

### Core Idea

The core idea is simply to expose the state of the (potentially conceptual) interpreter and allow it to be manipulated.

## You know more about presheaves than you think

### The category of graphs as a presheaf

Here’s a small example of why people find category theory interesting. Consider the category, call it ccC, consisting of two objects, which we’ll imaginatively name 0 and 1, and two non-identity arrows s,t : 0 -> 1. The category of graphs (specifically directed multigraphs with loops) is the category of presheaves over ccC, which is to say, it’s the category of contravariant functors from ccC to `cc"Set"`. I’ll spell out what that means momentarily, but first think about what has been done. We’ve provided a complete definition of not only graphs but the entire category of graphs and graph homomorphisms given you’re familiar with very basic category theory1. This is somewhat magical.

Spelling things out, G is a contravariant functor from ccC to `cc"Set"`. This means that G takes each object of ccC to a set, i.e. G(0) = V and G(1) = E for arbitrary sets V and E, but which will represent the vertices and edges of our graph. In addition, G takes the arrows in ccC to a (set) function, but, because it’s contravariant, it flips the arrows around. So we have, for example, G(s) : G(1) -> G(0) or G(s) : E -> V, and similarly for t. G(s) is a function that takes an edge and gives its source vertex, and G(t) gives the target. The arrows in the category of graphs are just natural transformations between the functors. In this case, that means if we have two graphs G and H, a graph homomorphism f : G -> H is a pair of functions f_0 : G(0) -> H(0) and f_1 : G(1) -> H(1) that satisfy H(s) @ f_1 = f_0 @ G(s) and H(t) @ f_1 = f_0 @ G(t). With a bit of thought you can see that all this says is that we must map the source and target of an edge e to the source and target of the edge f_1(e)|. You may also have noticed that any pair of sets and pair of functions between them is a graph. In other words, graphs are very simple things. This takes out a lot of the magic, though it is nice that we get the right notion of graph homomorphism for free. Let me turn the magic up to 11.

## The three styles of category theory

### Introduction

Arguably (1-)category theory is the study of universal properties. There are three standard formulations of the notion of universal property which are all equivalent. Most introductions to category theory will cover all three and how they relate. By systematically preferring one formulation above the others, three styles of doing category theory arise with distinctive constructions and proof styles.

I noticed this trichotomy many years ago, but I haven’t heard anyone explicitly identify and compare these styles. Furthermore, in my opinion, one of these styles, the one I call Set-category theory, is significantly easier to use than the others, but seems poorly represented in introductions to category theory.

For myself, it wasn’t until I read Basic Concepts of Enriched Category Theory by G. M. Kelly and was introduced to indexed (co)limits (aka weighted (co)limits), that I began to recognize and appreciate Set-category theory. Indexed (co)limits are virtually absent from category theory introductions, and the closely related notion of (co)ends are also very weakly represented despite being far more useful than (conical) (co)limits. I don’t know why this is. Below I’ll be more focused on comparing the styles than illustrating the usefulness of indexed (co)limits. I may write an article about that in the future; in the mean time you can read “Basic Concepts of Enriched Category Theory” and just ignore the enriched aspect. Admittedly, it is definitely not an introduction to category theory.

## Differentiation under the integral

Here is a PDF with an informal proof of a very general form of differentiation under the integral.

It’s formulated using geometric algebra and provides a simple demonstration of using some of the basic identities in geometric calculus.

The end result is:

## A better way to write convolution

Normally discrete convolution is written as follows:

`(f ** g)(n) = sum_(k=0)^n f(k)g(n-k)`

It is not immediately obvious from this that f ** g = g ** f. Consider this alternate representation:

`(f ** g)(n) = sum_(j+k=n) f(j)g(k)`

This formula is obviously symmetric in f and g and it clarifies an important invariant. For example, to multiply two polynomials (or formal power series) we convolve their coefficients. This looks like:

Let `P(x) = sum_k a_k x^k and Q(x) = sum_k b_k x^k` then

`P(x)Q(x) = sum_(j+k=n) a_j b_k x^n`

This emphasizes that the nth coefficient is the product of the coefficients whose degrees sum to n#. (You may recognize this as the convolution theorem.)