Confirming that timezones exist with minimal trust
I was listening to an episode of Oh No, Ross and Carrie! about Flat Earth and it struck me that if you believe the world is conspiring against you, it’s practically quite difficult to prove almost anything. Now one thing that most Flat Earthers do seem to accept is that when its day in one part of the planet, it’s night in another part.
However, let’s say someone denied this. How would you prove it, with the minimum amount of trust?
Can we do this while trusting nobody?
Let’s say that our experimenter only trusts their own senses. Can they prove that the day/night dichotomy exists? Well, one way they could do this would be to confirm that their watch is correct, then fly to the other side of the world, then confirm that their watch was off by 12 hours from the day/night cycle. However, this isn’t exactly right, it’s possible that someone could mess with your watch to cause it to run slightly fast or slow and cause it to be different when you alived as when you left.
With a fast enough plane, you might be able to confirm that day had turned to night in less than 12 hours, without the need to rely on a possibly manipulable watch. However, the very act of stepping on a plane might allow nefarious agents to manipulate your subjective experience of time, thus fooling you into thinking time zones exist. (Yes, this is a massively unproductive view of the world, but let’s try to work around it.)
Given these limitations, it’s clear that our prover needs a collaborator they can trust.
Basic protocol with a trusted collaborator
We now have two experimenters, who each trust each other and want to prove the existence of time zones: Alice and Bob. Consider the following protocol: Bob travels across the world while Alice stays behind. Alice and Bob then communicate with each other and confirm that one sees day and the other night.
This works right? Well, almost. The issue is that there’s no protection against a simulation attack: what if Alice speaks to a simulated version of Bob while Bob speaks to a simulated version of Alice, with the two conversations actually taking place 12 hours apart from each other?
Alice and Bob’s position is starting to look undisprovable. But is it?
Shared Password
Let’s say that before leaving, Alice and Bob come up with a shared password, \(p\), randomly. Then, the protocol is as such:
 Alice and Bob: agree on password \(p\)
 Alice: goes to other side of the world and confirms that its day
 Alice: sends \(p\) to Bob
 Bob: confirms that its night and that the received message is in fact \(p\)
But wait, the adversary could trap the password after Alice has sent it but before Bob has received it, thus delaying it 12 hours and allowing the protocol to go through, even if the world in fact has no time zones. The issue is that there’s no response from Bob. Bob just sending back the password doesn’t help, since the adversary could do that!
Different Passwords
OK, so now we have two different passwords \(p_a\) and \(p_b\). The protocol is now as follows:
 Alice and Bob: create passwords \(p_a\), \(p_b\) and share them with each other
 Alice: goes to other side of world and confirms that its day
 Alice: sends \(p_a\) to Bob
 Bob: confirms that its night and that the received message is \(p_a\)
 Bob: sends \(p_b\) to Alice
 Alice: confirms that it is still the same day and the received message is \(p_a\)
Now, Alice knows for sure that the world in fact has multiple time zones.
However, Alice and Bob might say that the adversary has the ability to read and edit their memories and thus steal their passwords. OK, this objection must make their claim undisprovable, right? In this case the answer is yes, because the adversary could always just convince them that the world had timezones by making arbitrary modifications to their memories.
However, if we give the adversary only read access to their memories, their position turns out not to be undisprovable!
Secure Time Synchronization
The issue that Alice and Bob are running into is that they can’t preagree on the passwords, because then they know the passwords ahead of time and thus the adversary knows the passwords ahead of time. However, they might be able to “postagree” on the passwords, as such:
 Alice and Bob: start on opposite sides of the world
 Alice: Confirms that its day
 Alice: Generates and sends \(p_a\) to Bob
 Bob: Confirms that its night
 Bob: Generates and sends \(p_b\) to Alice
 Alice: Confirms that it is still the same day
 Alice: meets with Bob
 Alice and Bob: check that all passwords transmitted were correct
If this protocol goes through without Alice and Bob having any issues, then they know that it can be day and night at the same time in different parts of the world. The procedure works!
Assumptions and Proof
OK, so if we wanted to prove that the above scheme works, we would need a few assumptions. First, we assume Alice and Bob are trustworthy. Second, we need to assume that Alice can confirm that some entity is Bob in a facetoface conversation and vice versa (so that the Alice and Bob at the end are guaranteed to be the real Alice and Bob). Third, we need to assume that Alice and Bob can tell when night falls, that is, the adversary can’t somehow convince them that two points in time are on the same day when it was in fact night in between those points. Finally, the adversary cannot have time travel and cannot predict either Alice or Bob’s random number generators.
In this case, we can prove that Bob confirming that it is night where he is happened after Alice generated \(p_a\) and thus during some day D where Alice was, and before Bob generated and thus before Alice received \(p_b\) and thus before some point on the same day D. Since we assume days are continuous, this proves that Bob observed night during a time when Alice observed day, and thus this procedure is secure.
You can weaken the assumption that two specific trustworthy people are needed by repeating this procedure for every pair of people in some set of N people. Then the scheme proves that time zones exist assuming that 2/N of the people are trustworthy, at the cost of having to repeat the scheme \(O(N^2)\) times
Implications
N/A.
Less facetiously, I guess my general takeaway is that “your claim is undisprovable” shouldn’t be used as a synonym for “you’re making ridiculous, conspiratorial, assumptions”. Because even when someone is being paranoid, there might be a way to disprove their hypothesis, with enough effort.
Infix Notation in Scheme
Scheme is well known as a very simple programming language. The general concept behind scheme is that it is composed of Sexpressions, or expressions of the form (operator operand1 operand2 ... operandn)
, which can be nested.
This makes scheme relatively simple to parse and evaluate, however it does lead to some strange compromises on the style of programming. For example, rather than writing 12 * (2 + 3)
, you have to write (* 12 (+ 2 3))
. And in a way, this is elegant in its simplicity.
But simplicity is overrated.
Homoiconicity, or writing a scheme program to write a scheme program
Scheme has this cool property of being a homoiconic language. This means that you can write scheme code that writes and modifies scheme code.
For example, take this function, which replaces the first element form a scheme expression with a +
:
(define (replacewithplus code)
(cons '+ (cdr code)))
Note that we just treat the code like any other scheme list. To call this function, we can just run
scm> (replacewithplus '( 2 3))
(+ 2 3)
Now, if we want to actually run this program, we can wrap it in an eval
call as such:
scm> (eval (replacewithplus '( 2 3)))
5
Macros
You’ll note that in the above, we have to quote the arguments and then eval the result. It turns out that there’s a construct in Scheme that will do this for you! Using the same replacing with + function, we can define
(definemacro (replacewithplus code)
(cons '+ (cdr code)))
Note that this is the same definition, except that we have replaced define
with definemacro
. Now, Scheme handles the quoting of the arguments and the evaluation of the result for us as such:
(replacewithplus ( 2 3))
5
Pretty nifty, huh!
Infix notation
OK, but the post’s title is infix notation. Let’s say we want to be able to write (12 * (2 + 3))
in scheme and have it evaluate the way it would in Python. To accomplish this, let’s define a function (not a macro for now) that takes in (12 * (2 + 3))
and converts it into the scheme form (* 12 (+ 2 3))
. First off, we need to identify which things are in fact infix notation:
(define (infix? code)
(and
(list? code)
(= (length code) 3)
(member (cadr code) '(+ *  /, >, <, >=, <=, =))))
The idea here is that we check that the given piece of code is a list with 3 elements, and that its middle element is an operator. Now, let’s write the code to convert infix to prefix notation.
(define (rearrange code)
(list (cadr code) (car code) (caddr code)))
Where this code just places the elements in second, first, third order.
Now, we can put it together with a recursive function:
(define (toprefixfunc code)
(cond
((infix? code) (toprefixfunc (rearrange code)))
((list? code) (map toprefixfunc code))
(else code)))
The idea behind this code is that if something is infix, we should rearrange it, then call ourselves to finish up the task, if something is a call expression, we should just look at every element, and otherwise, we’re at a base case and can just return.
Let’s try this out on our example:
scm> (toprefixfunc '(12 * (2 + 3)))
(* 12 (+ 2 3))
It works!
Finally, what we really want is a macro. We can just define one directly:
(definemacro (toprefix code) (toprefixfunc code))
Sadly we can’t just (definemacro toprefix toprefixfunc)
because of a technicality in the scheme language. Anyway, now we can run our scheme code:
scm> (toprefix (12 * (2 + 3)))
60
And there you have it. Scheme’s power might be in its simplicity but with great power comes the ability to create complexity. Obviously, the usual disclaimer applies: don’t write code like this, but if you do, do it with macros!
The code
A fully runnable version of this is below: try copypasting it into 61A’s scheme interpreter and check it out! (There are a few helpful functions defined at the end that we just kinda assumed the existence of above).
(define (infix? code)
(and
(list? code)
(= (length code) 3)
(member (cadr code) '(+ *  /, >, <, >=, <=, =))))
(define (rearrange code)
(list (cadr code) (car code) (caddr code)))
(define (toprefixfunc code)
(cond
((infix? code) (toprefixfunc (rearrange code)))
((list? code) (map toprefixfunc code))
(else code)))
(definemacro (toprefix code)
(toprefixfunc code))
(define (member elem lst)
(cond
((null? lst) #f)
((eq? (car lst) elem) #t)
(else (member elem (cdr lst)))))
(define (cadr lst) (car (cdr lst)))
(define (cddr lst) (cdr (cdr lst)))
(define (caddr lst) (car (cddr lst)))
(Mini) Scheme in 50 Lines
The scheme language is a programming language that is unique for being easy to parse. Every construct in scheme is of the form
(keyword arg1 ... argn)
Our Subset
We will start with some standard scheme expressions, which you can think about as being analogous to certain patterns in Python. For example instead of writing a + b
, you write (+ a b)
, where +
is just the name of a function. Similarly, instead of writing lambda x: x * 2
for the doubling function, you write (lambda (x) (* 2 x))
. Just lambdas and function application are enough to perform any calculation, but we add a few more features for clarity: instead of x = y
we write (define x y)
, instead of x if y else z
we write (if y x z)
and instead of writing
x = f(y)
return x
we write (begin (define x (f y)) x)
. The real scheme language has many more constructs, including ones that simulate python’s def
statements, and some unique ones that allow you to assign variables in a local frame, simulate elif
trees, have shortcircuited and/or
constructs, or even define your own language constructs. For brevity, we will stick to this subset, which is still very powerful.
Lexing
The first step in processing a scheme program is to split it up into a list of tokens. What we do is take an expression like '(a b (c))'
and convert it into a list of tokens like '(', 'a', 'b', '(', 'c', ')', ')'
.
To accomplish this, we first pad all the parentheses with space and replace all spacelike characters with a space. We then split on spaces (and filter out empty tokens, which are produced when multiple spaces are consecutive).
def lex(text):
text = re.sub("([()])", r" \1 ", re.sub(r"\s", " ", text))
return [x for x in text.split(" ") if x]
Parsing
We now need to parse the string. If we have '(a b (c))'
, we want to parse it to ['a', 'b', ['c']]
so we can process it in Python. Parsing scheme is fairly simple using recursion. Whenever we see a symbol or number, we just return and move on. Otherwise, we recursively call parse until we see an end parenthesis. For example, if we have the current state of our input
(+ 2 (4) (* 5 3)) 2 3)
we parse by removing the (
from the front, then parse +
, 2
, (4)
, and (* 5 3)
before seeing the unmatched )
. Then we return, having removed everything but the 2 3)
. This is implemented as follows:
def parse(text):
text = lex(text)[::1]
def parse():
start = text.pop()
if start != '(':
return start
vals = []
while text[1] != ')':
vals += [parse()]
text.pop()
return vals
return parse()
The reason we reverse the text is so that pop()
pops from the end rather than the front of the input stream.
Frames
We need to define an environment diagram so that we can execute code. This is similar to a Python style environment diagram, which is a backwards pointing tree (children point towards the root via the parent annotation rather than the other way around).
To define a frame, we use the defaultdict
class from python, which is like a dictionary except that when it can’t find a key, instead of raising a KeyError
, it calls a 0 argument function you provide in the constructor and sets that as its value. We want to slightly modify this so that it calls a 1 argument function. Thus we define a frame as such:
class frame(defaultdict):
def __init__(self, f):
super().__init__(lambda: None)
self.__function = f
def __missing__(self, key):
return self.__function(key)
defaultdict
calls the __missing__
function when necessary, and in this case, it calls the parent function on a key. We can create a child frame for a given frame simply by saying frame(lambda v: parent[v])
. We can now create a global frame as such:
global_frame = frame(int)
global_frame.update({"+" : add, "" : sub, "*" : mul, "/" : floordiv, "=" : lambda x, y: x == y})
We do something a little hacky here by basically defining integers as just being variables that evaluate to the integer version of themselves via the function int
. (this works as int("123") == 123
).
Special Forms
Now we need to somehow handle our special keywords (define, lambda, begin, if).
Define
We assume that we already have a function seval
defined, which is the function that will eval a scheme expression. In scheme, define
returns the variable being assigned to, for reasons of tradition.
def define(exp, env):
env[exp[0]] = seval(exp[1])
return exp[0]
Lambda
A lambda expression has no side effects, but must return a function. First we create a new frame, then we assign the operator to the operands, and then we run the body of the function in that frame and return the last value:
def slambda(exp, env):
def do_lambda(*args):
local_env = frame(lambda x: env[x])
local_env.update(dict(zip(exp[0], args)))
return [seval(u, local_env) for u in exp[1:]][1]
return do_lambda
Begin
This is similar to lambda
except that we don’t have any arguments or a new frame, and this one is simple enough to just write as a Python lambda function.
lambda exp, env: [seval(u, env) for u in exp][1]
If
We can just directly map this to the equivalent Python construct.
lambda exp, env: seval(exp[1], env) if seval(exp[0], env) else seval(exp[2], env)
Putting it together
We create a dictionary of special forms for easy access:
def define(exp, env):
env[exp[0]] = seval(exp[1])
return exp[0]
def slambda(exp, env):
def do_lambda(*args):
local_env = frame(lambda x: env[x])
local_env.update(dict(zip(exp[0], args)))
return [seval(u, local_env) for u in exp[1:]][1]
return do_lambda
special_forms = {
"define" : define,
"lambda" : slambda,
"begin" : lambda exp, env: [seval(u, env) for u in exp][1],
"if" : lambda exp, env: seval(exp[1], env) if seval(exp[0], env) else seval(exp[2], env)
}
Eval Function
To evaluate a parsed scheme tree, what we need to do is dependent on whether the input is a list or not. If we have a list, then we need to check if its first element is a special form, and if so run its special form function. Otherwise, we evaluate the first item as a function, then evaluate the rest of the items as its arguments, then call the function. If we don’t have a list, we just look up the current element in the current frame.
def seval(tree, env=global_frame):
if isinstance(tree, list):
func, *args = tree
if func in special_forms:
return special_forms[func](args, env)
return seval(func, env)(*(seval(x, env) for x in args))
return env[tree]
We can then run scheme by running seval(parse(text))
.
The Entire Interpreter
The entire interpreter, which is just 50 lines, is as below:
from collections import defaultdict
from operator import *
import re
def lex(text):
text = re.sub("([()])", r" \1 ", re.sub(r"\s", " ", text))
return [x for x in text.split(" ") if x]
def parse(text):
text = lex(text)[::1]
def parse():
start = text.pop()
if start != '(':
return start
vals = []
while text[1] != ')':
vals += [parse()]
text.pop()
return vals
return parse()
class frame(defaultdict):
def __init__(self, f):
super().__init__(lambda: None)
self.__function = f
def __missing__(self, key):
return self.__function(key)
global_frame = frame(int)
global_frame.update({"+" : add, "" : sub, "*" : mul, "/" : floordiv, "=" : lambda x, y: x == y})
def define(exp, env):
env[exp[0]] = seval(exp[1])
return exp[0]
def slambda(exp, env):
def do_lambda(*args):
local_env = frame(lambda x: env[x])
local_env.update(dict(zip(exp[0], args)))
return [seval(u, local_env) for u in exp[1:]][1]
return do_lambda
special_forms = {
"define" : define,
"lambda" : slambda,
"begin" : lambda exp, env: [seval(u, env) for u in exp][1],
"if" : lambda exp, env: seval(exp[1], env) if seval(exp[0], env) else seval(exp[2], env)
}
def seval(tree, env=global_frame):
if isinstance(tree, list):
func, *args = tree
if func in special_forms:
return special_forms[func](args, env)
return seval(func, env)(*(seval(x, env) for x in args))
return env[tree]
Of course, a proper scheme interpreter, which has more features (see the section “Subset”), more possible types (like strings, symbols, lists, etc.), and better error handling (we crash on a lot of cases with IndexError
s and ValueError
s). In fact, that’s an entire project in 61a.
But I personally enjoy that you can get quite a few features in such a small amount of space.
Try it out on the following program!
(begin
(define factorial
(lambda (x) (if (= 0 x) 1 (* x (factorial ( x 1))))))
(factorial 40))
The Efficiency Gap Makes No Sense (but all metrics show Republicans are better at gerrymandering)
Cracking, Packing, and Wasted Votes
The efficiency gap is a technique for measuring the level of gerrymandering in a state. Gerrymandering generally takes the form of what’s known as “cracking and packing.” Cracking is the process of taking a district with a majority of the opposing party and splitting it into two in which the party has a minority in each, thus denying your opponent that seat. However, this isn’t always possible because your opponent might have too many votes in a given area. To reduce the remaining number of votes your opponent has while minimizing the number of seats they have, you can use a technique called packing, in which you create a district in which your opponent can win by a huge margin.
To measure both cracking and packing, we can use the concept of a wasted vote. A wasted vote is any vote that did not contribute to the victory. There are two kinds of wasted votes, cracked waste and packed waste. A cracked wasted vote for party X is any vote in a district party X has lost. A packed wasted vote is any vote for party X over 50% in a district party X has won.
For example, let’s say that there are just two parties^{1} and 1000 voters in a district. The number of wasted votes for X in terms of the number of votes for X is as such:

The United States has two political parties. A vote for the Green, Libertarian, or American Independent Party is a wasted vote. But if you’re voting for the AIP (the party that nominated Wallace), you should waste your vote, so I guess I’m fine if you vote for the AIP. ↩
How You Get Homeopathy
Homeopathy is a system that has two primary claims. The first is the law of similars. It says that a dilute solution of a substance cures the ailment caused by a concentrated solution of the same substance. The second is the law of dilution, which says that the more dilute a homeopathic preparation is, the stronger its effect.
The second theory is the one people tend to focus on because it is clearly incorrect. The antihomeopathy \(10^{23}\) campaign is named after the order of magnitude of Avogadro’s number, that is the number of molecules of a substance in a 1M solution of a substance (typically a fairly strong solution, 1M saltwater is 5 teaspoons of salt in a liter of water). If you dilute by more than that amount, and many “strong” homeopathic preparations do, then with high probability you literally have 0 molecules of the active ingredient in your preparation. As the \(10^{23}\) campaign’s slogan makes clear, “There’s nothing in it” and homeopathic medicines are just sugar pills.
What is NP?
What is P?
This seems like a silly question. This question seems easily answered by the surprisingly comprehensible explanation on P’s Wikipedia page:
It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time
OK, so it’s the set of all decision problems (yesorno questions) that are \(O(n^k)\) for some integer \(k\). For example, sorting, which is \(\Theta(n \log n)\) is P, since it’s also \(O(n^2)\).
But let’s go for an alternate definition. Let’s take a Clike language and get rid of a bunch of features: subroutine calls, while loops, goto, for loops with anything other than i < n
in the second field (where n
is the length of the input), and modifying the for loop variable within the loop. Effectively, this language’s only loping construct is for(int varname = 0; varname < n; varname++) {/* Code that never modifies varname */}
. Let’s call this language CFOR
.
Storing Data With the CircleTree
The Pair Abstraction
Computers need some way to store information. More specifically, we want to be able to store multiple pieces of data in one place so that we can retrieve it later. For now, we’ll look at the simplest way of storing data, a pair.
To express the concept of a “pair”, we need three machines.
 A way to put two things together (construction, or “C” for short)
 A way to get the first element (first, or “F” for short)
 A way to get the second element (second, or “S” for short)
CircleTree as a Calculator
Using CircleTree Drawings as a Calculator
So this isn’t just a procrastination game for doodling when you’re bored (and have a lot of colored pencils, for some reason). We can use circletree as a way to express math!
Numbers
For math, the first thing we need are numbers. I’m just going to draw some pictures which are defined to be the numbers. We don’t worry too much about whether they are “really” numbers or not in the way that we don’t worry about whether “102” or “CII” is a better way to explain the concept of “how many cents in a dollar plus how many hands a person has”ness.^{1}
So this is 0:

Although, off the record, for doing math CII is a terrible way of representing 102. ↩
Introducing the CircleTree System
If you want to follow along on paper, you’ll want some colored pencils. Like at least 5 colors, not including a pencil to draw links.
Circtrees
In any case, we’ll call the diagrams we’re interested in “circtrees.”^{1} Circtrees can be constructed in one of three ways.
1. Dots
A dot of any color is a circtree. Here are some examples^{2}:
Counting Monoids
What’s a Monoid?
A monoid is a set \(M\) with an identity element \(e : M\) and an operation \(* : M \to M \to M\), where we have the laws:
 \(x * e = x\)
 \(e * x = x\)
 \(x * (y * z) = (x * y) * z\)
We write a monoid as a tuple \((M, e, * )\). Some example monoids (written in pseudoHaskell) are
(Int, 0, (+))
(Int, 1, (*))
(Bool, True, ())
((), (), \x y > ())
([a], [], (++))
The Porus Mirror Problem, Part 2
Propagation
From last time, we know the quantity of light that escaped at each location and direction around the unit circle. We want to find how this translates into quantities of light at any point away from the circle. This situation can be modeled as so:
The Porus Mirror Problem, Part 1
The porus mirror problem
I’m pretty sure I came up with this problem on my own, but I’m not sure if its an existing problem under a different name. Anyway, the situation is as such:
 We have a very short cylindrical tube. In fact, we’ll ignore the third dimension and just use a circle. For simplicity, we’re using units such that the radius is 1.
 The tube is filled with a gas that emits corpuscles in one large burst. We assume a large enough number that we can model them continuously. We additionally assume that the emmissions are uniform in location and direction.
 The tube itself is semitransparent, with transparency determined by a function \(t: [0, 2\pi] \to [0, 1]\) of angle around the circle. Any light that does not pass through is reflected across the normal.
We wish to calculate at each point along the surface of the tube what is the total quantity of light emitted in each direction, from which we can easily calculate the light pattern this system will cast on any shape outside.
Dependent Types and Categories, Part 1
So I’ve been trying to go through Category Theory for Scientists by writing the functions as code. So I obviously decided to use Haskell. Unfortunately, I ran into a wall: Haskell is actually pretty bad at representing categories.
Haskell is a Category
Now, at first this was incredibly surprising. Frankly, I had started learning about category theory because of its association with Haskell. Unfortunately, I didn’t realize that Haskell isn’t category theory, it’s a category.
For instance, look at this definition of a category in math:
Chaos, Distributions, and a Simple Function
\(\newcommand{\powser}[1]{\left{ #1 \right}}\)
Iterated functions
The iteration of a function \(f^n\) is defined as:
\[f^0 = id\] \[f^n = f \circ f^{n1}\]
For example, \((x \mapsto 2x)^n = x \mapsto 2^n x\).
Most functions aren’t all that interesting when iterated. \(x^2\) goes to \(0\), \(1\) or \(\infty\) depending on starting point, \(\sin\) goes to 0, \(\cos\) goes to something close to 0.739. \(\frac{1}{x}\) has no well defined iteration, as \((x \to x^{1})^n = x \to x^{(1)^n}\) which does not converge.
Haskell Classes for Limits
OK, so the real reason I covered Products and Coproducts last time last time was to work toward a discussion of limits, which are a concept I have never fully understood in Category Theory.
Diagram
As before, we have to define a few preliminaries before we can define a limit. The first thing we can define is a diagram, or a functor from another category to the current one. In Haskell, we can’t escape the current category of Hask, so we instead define a diagram as a series of types and associated functions. For example, we can define a diagram from the category \(\mathbf 2\) containing two elements and no morphisms apart from the identities as a pair of undetermined types.
A diagram from the category \(\mathbf 2*\), a category containing two elements and an arrow in each direction (along with the identities), (this implies that the two arrows compose in both directions to the identitity):
Haskell Classes for Products and Coproducts
Product Data Structures
Product Types are a familiar occurrence for a programmer. For example, in Java, the type int
\(\times\) int
can be represented as:
class IntPair {
public final int first;
public final int second;
public IntPair(int first, int second) {
this.first = first;
this.second = second;
}
}
Monoids, Bioids, and Beyond
Two View of Monoids.
Monoids
Monoids are defined in Haskell as follows:
class Monoid a where
m_id :: a
(++) :: a > a > a
Monoids define some operation with identity (here called m_id
). We can define
the required laws, identity, and associativity, as follows:
monoidLaw1, monoidLaw2 :: (Monoid a, Eq a) => a > Bool
monoidLaw1 x = x ++ m_id == x
monoidLaw2 x = m_id ++ x == x
monoidLaw3 :: (Monoid a, Eq a) => a > a > a > Bool
monoidLaw3 x y z = (x ++ y) ++ z == x ++ (y ++ z)
Nontrivial Elements of Trivial Types
We know that types can be used to encode how to make useful data structures.
For example, a vehicle can be encoded as:
data Vehicle = Car { vin :: Integer, licensePlate :: String }
 Bike
In this case, valid values include cars with VINs and LPNs, or Bikes, which have neither of these data points.
However, some data types can seem far less useful.
The Autogeneration of Landscapes
OK, so a break from theory and CS, and to applications. How do we produce reasonably realistic landscapes using differential equations?
Mountains and Valleys
To simulate mountains and valleys, we can use a fairly simple algorithm that adds a random amount to a region, then recursively calls itself on each quadrant of the region. Afterwards, an image generally looks something like:
We can apply a Gaussian blur to the image to get a reasonably realistic depiction of mountains and valleys.
We can define the elevation as a function \(E(x, y, t)\). Representing this as a landscape:
CStyle Pointer Syntax Considered Harmful
Declaration Follows Use
In C, a pointer to int has type int*
, but really, this isn’t the right way of looking at it. For example, the following declaration:
int* x, y;
creates x
of type int*
and y
of type int
.
The Triviality Norm
Feynman famously said that to a mathematician, anything that was proven was trivial. This statement, while clearly a lighthearted dig at mathematics, it does have a striking ring of truth to it.
Logical Implication
In logic, there is the concept of implication. The idea is that if \(B\) is true whenever \(A\) is true we can say that \(A \implies B\). This makes sense for statements that depend on a variable. For example, we can say that \(x > 2 \implies x > 0\).
A Monadic Model for Set Theory, Part 2
\(\newcommand{\fcd}{\leadsto}\)
Last time, we discussed funcads, which are a generalization of functions that can have multiple or no values for each element in their input.
Composition of Funcads
The composition of funcads is defined to be compatible with the composition of functions, and it takes a fairly similar form:
\[f :: Y \fcd Z \wedge f :: X \fcd Y \implies \exists (f \odot g :: X \fcd Z), (f \odot g)(x) = \bigcup_{\forall y \in g(x)} f(y)\]
In other words, map the second function over the result of the first and take the union. If you’re a Haskell programmer, you probably were expecting this from the title and the name “funcad”: the funcad composition rule is just Haskell’s >=>
.
A Monadic Model for Set Theory, Part 1
\(\newcommand{\fcd}{\leadsto}\)
Solving an Equation
A lot of elementary algebra involves solving equations. Generally, mathematicians seek solutions to equations of the form
\[f(x) = b\]
The solution that most mathematicians come up with to this problem is to define left and right inverses: The left inverse of a function \(f\) is a function \(g\) such that \(g \circ f = \mathrm {id}\). This inverse applies to any function that is onetoone. There is also a right inverse, a function \(g\) such that \(f \circ g = \mathrm {id}\) For example, the left inverse of the function
\[x \mapsto \sqrt x :: \mathbb R^+ \rightarrow \mathbb R\]
is the function
\[x \mapsto x^2 :: \mathbb R \rightarrow \mathbb R^+\]
What is Category Theory?
\(\newcommand{\mr}{\mathrm}\) So, I was reading Category Theory for Scientists recently and kept having people ask me: What is category theory? Well, until I hit chapter 34, I didn’t really have an answer. But now I do, and I realize that to just understand what it is doesn’t really require understanding how it works.
Sets and functions
So, set theory is all about sets and functions. Why are we talking about set theory and not category theory, you may ask? I’ll get to category theory eventually, but for now, let’s discuss something a little more concrete.
Let’s look at subsets of the set \(\{a, b\}\). We have the possibilities, which we name Empty, A set, B set, Universal set:
\[E = \{\}, A = \{a\}, B = \{b\}, U = \{a, b\}\]
Stupid Regex Tricks
Regexes, the duct tape of CS
Regexes are truly amazing. If you haven’t heard of them, they are a quick way to find (and sometimes replace) some body of text with another body of text. The syntax, while it has its critics, is generally pretty intuitive; for example a zip code might be represented as
[09]{5}(\s*\s*[09]{4})?
which is read as “a five digit code optionally followed by a spaced dash and a four digit code”. Some whitespace and named groups might help the reading (use COMMENTS
mode when parsing)
(?P<main_code>
[09]{5}
)
( # optional extension
\s*\s* # padded dash
(?P<optional_extension>
[09]{4}
)
)?
Dictp Part 2
OK, so to continue the Dictp saga, some syntactic sugar.
References to local variables.
The parser can be enhanced by rewriting anything that isn’t a builtin command or a string with a lookup to __local__
.
E.g.,
a
\(\mapsto\)__local__['a']
0 = 1
\(\mapsto\)__local__['0'] = __local__['1']
0?
\(\mapsto\)__local__['0']?
'0'
\(\mapsto\)'0'
Dictp Part 1
So, a friend and I (I’m going to protect his anonymity in case he doesn’t want to be associated with the travesty that is what we ended up thinking up) were discussing ridiculous ideas for programming languages: you know the deal, writing C interpreters in Python, using only integers to represent everything, etc.
One idea, however, seemed a little less ridiculous to us (OK, just to me): a language in which there are two data types: Dictionary and String.
Infsabot Strategy Part 2
OK, so to continue our Infsaboting.
Correction
I made a mistake last time. I included SwitchInt
, a way to switch on values of ExprDir
, which is ridiculous since an ExprDir
can only be constructed as a constant or an if
branch to begin with.
So just imagine that I never did that.
Guess and Check
OK, so how should our AI construct these syntax trees? At a very high level, we want to be able to 1) assess trees against collections of trees and 2) modify them randomly. We can represent this as a pair of types:
asses :: [RP] > RP > Double
modify :: RP > StdGen > (RP, StdGen)
I think the implementation of asses
should be pretty clear: simply find the win rate (given that we can simulate an unlimited number of games).
Modify, on the other hand, is a little more complicated. There are a few ways a tree can be modified:
 Modify the value of a constant to be something else.
 Modify the value of a field to point to something else or a field
 Add leaves to the tree
 Remove leaves as a simplification step
Infsabot Strategy Part 1
OK, so what is this Infsabot? Infsabot is a game I designed for people to write programs to play. Basically, it’s like chess, except where each piece acts independently of each other.
The Game
There is a square board where each square is either empty or contains material. The game pieces, robots, require material to stay alive and perform tasks. At each turn, every robot reports which of the following it wants to do:
 Noop: The robot does nothing
 Die: The robot dies
 Dig: The robot digs to try to extract material
 Move: The robot can move in one of the four compass directions
 Fire: The robot can fire a quickmoving projectile (e.g., travel time = 0) in a compass direction
 Message: The robot can send a quickmoving message in a compass direction
 Spawn: The robot can create a new robot with its own initial material and appearance
To decide what to do, a robot has access to two things:
 A picture of the positions around it, to a given distance
 Whether or not the spot contains material
 Whether or not the spot contains a robot, and it’s appearance (not it’s team)
 A snapshot of its own hard drive, which is a massive relational database between Strings and Strings
 A list of all messages received
What's a number?
OK, so a bit of a silly question. Of course, we all know what numbers are. But humor me, and try to define a number without using “number”, “quantity”, or anything that refers back to a number itself.
But, before we learn numbers, we have to first understand something simpler: counting. Couldn’t we define numbers in terms of counting? Well, yes, otherwise I wouldn’t be writing this article.
Now, to not end up with a forty page book, I’m only going to go over how to define the whole numbers (I’m going to ignore negative integers, fractions, \(\pi\), etc.)
Recursivized Types
So, a short break from \(\varepsilon—\delta\).
Anyway, I’m going to look at Algebraic types in this section. Specifically, I am going to use Haskell types.
The provided code is all actual Haskell, in fact, I’m going to have to deimport the standard libraries because some of this is actually defined there. You can find all the code here
Who Needs Delta? Defining the HyperReal Numbers
\(\renewcommand{\ep}{\varepsilon}\) \(\renewcommand{\d}{\mathrm d}\)
In high school Calculus, solving differential equations often involves something like the following:
\[\frac{\d y}{\d x} = \frac{y}{x}\]
\[\frac{\d y}{y} = \frac{\d x}{x}\]
\[\int \frac{\d y}{y} = \int \frac{\d x}{x}\]
\[\log y = c + \log x\]
\[y = kx\]
Now, I don’t know about anyone else, but this abuse of notation really bothered me at first. Everyone knows that \(\d x\) isn’t an actual number by itself, but we seem to use it all the time as an independent variable.
Ancient Greek Abstract Algebra: Introduction
Note: I’ve put the Ancient Greek Abstract Algebra series on hold for now. Please take a look at some of my other post(s).
Modern constructions of
The natural numbers are taught to children as a basic facet of mathematics. One of the first things we learn is how to count. In fact, the name “Natural Numbers” itself implies that the natural numbers are basic.
However, modern mathematicians seem to have trouble with accepting the natural numbers as first class features of mathematics. In fact, there are not one but two common definitions of the naturals that can be used to prove the Peano Axioms (the basic axioms from which most of number theory can be proven).