#1. Transitions

We've got some sprites for a character in an RPG game that kp is working on for Ludum Dare, say, we have 27 of them for 27 states. Every state can transition to any other, and we have animations for each transition between sprites.

We are bound by memory on this particular project since the game should run on a MEGA65, to save space we've designed the game in such a way so that the reverse transition is the same as the transition animation played in reverse, so that we only have to store it once. (State A -> State B animation is the same as the animation State B -> State A played in reverse.)

Is it possible to find a sequence of consecutive states to store the animations so that every transition is stored exactly once?

Example:
5 States: ABCDE
All transitions to store: AB, AC, AD, AE, BC, BD, BE, CD, CE, DE
Example of a solution sequence: ABCEBDCAEDA

Think about the problem for a bit! Solution: https://i.fii.moe/1UYsl8R5tH46Uh.pdf

2. Parse XDDDD

Let's look at why regex is not a particularly good choice for parsers. Rob Pike has an argument with code style and practicalities, but let's look at it from the expressive power point of view, with an introduction to language theory.

An alphabet Σ is a set of symbols that can be used to form strings -- binary strings have the alphabet Σ={0,1}, for instance. English can be more or less written with ASCII character set, which we can also consider an alphabet.

Σ* denotes the set of all finite strings in the alphabet Σ. Every sequence of characters from Σ is in the set Σ* (in some sense this is the Library of Babel!). A language L over the alphabet Σ is any subset of Σ*. For example:

• L={1110101,101010101} is a finite language over Σ={0,1}.
• L={woomy, wooomy, woooomy, ...} is an infinite language over Σ={w,o,m,y}.

A recognizer R of the language L is a machine which, when given a string in L, is able to halt and tell you that the string is in fact in L. (R need not halt when given a string that is not in L!) Example: any parser is in fact a recognizer. A recognizer is a crippled parser that doesn't care to tell you the structure of the input!

Since we actually want our parser to terminate, let's only consider recognizers which must terminate (such machines are called deciders), in particular, let's look at the DFA (deterministic finite automaton) -- this is basically what people refer to when they say "state machine".

Here is a state machine over the alphabet Σ={f,l,a,s,h,i}. The machine takes an input string and enters the starting state, to continue the machine, it matches the next character in the input string against any of the arrows out of the current state. If there is no transition possible and the string is not completely consumed, then the machine halts and rejects. If the string is completely consumed and yet we are not at a state that is marked with a double circle (in this case just G), the machine also rejects. Only if the string is completely consumed and we are in a state with a double circle does the machine accept. Importantly, a DFA can only have finitely many states. Can you figure out the language which this machine accepts?

It accepts the language L={flashi, flashii, flashiii,...}, the machine will reject "flash", for example.

But lach why did you go through so many definitions and extra steps, when I can just parse this with \^flashi+$\. Here is a result from formal language:
Theorem. A language L is accepted by some state machine if and only if L is described by a regular expression. In such cases, L is called a regular language.

That is to say, the expressive power of regular expressions is equivalent to that of state machines. This is actually how most efficient regex engines work, they translate your expression into an equivalent state machine.

Well, I'm not saying that regex is bad and you shouldn't ever use them, but here is the problem: regular languages are a very limited set of languages.

Theorem. (Pumping lemma) If L is a regular language, then there exists some p ≥ 1 such that every string w in L of length at least p can be split into three parts as w=a + b + c (concatenation of strings a, b, c), where:

1. b is not the empty string
2. (a + b).length ≤ p
3. a + b + b + ... + b + c is in the language L. That is, we can repeat ("pump") the "b" part of w=a+b+c however many times we wish, and it will remain in the language.

For the regular language L={woomy, wooomy, ...}, we can set a='wo', b='o', c='my'. Then we can generate the entire language by pumping b='o'. Imagine what a state machine looks like for this language:

Notice how "pumping b='o'" is equivalent to going in circles on the self-transition on the state D. In other words, every regular language eventually turns into something like this. This is the main idea of the pumping lemma: since any DFA only has finitely many states, any sufficiently long string in the accepted language must visit some state twice, at which point we can just keep going in circles (the "pumping" action).

Let's look at a language that is not regular, a very simple and common one at that: let's try matching brackets. Our language is L={(), (()), ((())), ...} over the alphabet Σ={(,)}. It's easy to see that there is nothing we can pump here:

• If you try to pump some number of '(' or ')', then the number of opening and closing brackets no longer match -- not in L.
• If you try to pump some number of '(' concatenated by some number of ')' -- as in the middle of any string in L, then we are not nesting brackets anymore -- a bracket is closed before all brackets have been opened, which is also not in L.

So L is not regular, NO REGEX will be able to parse it! This probably confirms your intuition about regex, that it is very "straight" or "flat". Here you see formally that the parse tree can only expand horizontally for repetitions, but never vertically to allow "nesting" in the traditional sense. (Side note: this simple "nesting" is an example of a "context-free grammar", and it is still a lot weaker than a general recursive grammar, but it still is a good illustration of a simple property a real-world grammar of interest will likely possess.)

Since regex alone is not powerful enough, if you would like to use regex to build a parser, it then must be interleaved with meticulously written control flow, pairing with what the regex describes. This is very brittle and error-prone -- extremely high coupling directly over an extremely barebones API boundary with respect to defining grammars (your programming language's control flow), leading into the arguments from Rob Pike -- since, as the programmer, parsing control flow and parsing regex are essentially two separate activities.

Well so what should we do instead? To directly address this specific problem, try to imagine something that allows your parser logic to be "self-contained" in such a way that you can parse all the logic without having to switch between "contexts". -- One such way is, as you probably have guessed, to write your grammar separately and then use a parser generator like yacc. Of course this works, but it's often really overkill for a lot of purposes. Writing so-called "recursive descent parsers" by hand is what most production compilers do. (It's what you'd naturally end up with if you just started writing a parser organically using basic C-style control flow and without advanced text processing tools like regex.) Contrary to how the name sounds, these things don't really have a very good definition. A slightly more structured way is to use "parser combinators" or "functional parsers", which are ultimately equivalent to "recursive descent parsers", but are a bit more structured from the code perspective by exploiting FP ideas for composability, at the cost of the ability to micro-optimize in more traditional "recursive descent parsers".

3. Monadic sequencing

I think this will forever be something that is completely incomprehensible when you don't yet understand what it is, but will seem really easy once you do understand and wonder how you were ever not able to see what it is. It's not scary or hard, let's get to it.

The most common monads you find in programming are error handling facilities. Let's take a look at how this is done classically.

function get_thing() {
  // do work
  if (goes well)
    return good value
  else
    return bad value
}

Hm so f returns either a good value or an error. In C this bad value is probably NULL when the good value is a pointer of sorts. The signature probably looks like this Thing * get_thing() and the fact that it can be invalid (e.g. NULL) is just implicit. In JavaScript you would just return null or undefined and the signature is f: () ⇒ Thing | null. This is a recurring theme in language evolution -- generally speaking we want to know and verify more at the static level before programs are running. The caller then has to do this:

thing = get_thing();
if (!thing) {
  get out
}
junk = do_stuff_with_thing(thing);
if (!junk) {
  get out
}
do_stuff_with_junk(junk);

Okay but wouldn't it be great if something like do_stuff_with_thing(get_thing()) just worked? But we don't want the functions we call to deal with the possibility of thing being null, and if you dereference a NULL you are just cooked.

Okay let's try to do this. Since we want this handling logic to be handled automatically, the behaviour could be embedded into types. Say. We want to encode the ability to say: "given something, then, go do this" in a well defined way (see below implementation of then) regardless of whether things went well. The thing that we want to then do next can return anything, it could be Junk or Garbage or whatever else. So our utility needs to be generic over the return value of do_stuff_with_thing as well:

interface Optional[Thing] {
  _thing: Thing | null
  function then[Junk](do_stuff: (Thing) ⇒ Optional[Junk]) {
    if (_thing == null) {
      return make_optional_thing[Junk](null) // get out
    }
    return do_stuff(_thing)
  }
}
function make_optional_thing[Thing](thing_or_null: Thing | null): Optional[Thing] {
  return { _thing: thing_or_null }
} 

Okay now we can write get_thing like this:

function get_thing(): Optional[Thing] {
  if (goes well)
    return make_optional_thing[Thing](thing)
  else
    return make_optional_thing[Thing](null)
}

So, the functions rewritten with the new signatures:

• get_thing: () ⇒ Optional[Thing]
• do_stuff_with_thing: Thing ⇒ Optional[Junk]
• do_stuff_with_junk: Junk ⇒ Optional[Garbage]

None of the functions need to think about handling errors from inputs since they aren't Optional. Now this works:

get_thing().then(do_stuff_with_thing).then(do_stuff_with_junk)

and it's clean. The .then is automatically taking care of the necessary error handling short-circuiting:

Okay if you've ever written JavaScript it's very obvious what's going on here. This entire thing looks suspiciously similar to the Promise interface:

interface Promise[T] {
  function then[S](do_stuff: (T) ⇒ Promise[S]): Promise[S]
  // Everything in here is implemented internally in the JS runtime
}
function make_promise[T](value: T): Promise[T] {
  return Promise.resolve(thing) or Promise.reject(thing) // depending on your mood
}

Indeed, Promise is another monad. Concretely speaking, M[T] is a monad in the functional programming sense if it is paired together with with M[T].then: ((M[T]) ⇒ [S]) ⇒ M[S] and make_M[T], as long as the following are true:

• make_M(value).then(do_stuff) produces the same result as do_stuff(value)
• for any variable m that is a M[T], m.then(make_M) is a noop, that is, it's equal to m itself.
• for any variable m that is a M[T], m.then(do_stuff).then(do_more_stuff) is the same as m.then(function (x) { return do_stuff(x).then(do_more_stuff) }). In other words, it doesn't matter which then() gets run first.

You can check that all of these are true with Optional and Promise. These rules are important because it's easy to imagine an interface not respecting these rules and then we would lose out on some of the equivalent transforms we can do on this interface. If you are feeling confused and happen to be familiar with Promise I suggest you try replacing the variables and functions above with the real JS interface. And that's really it, it's a specific type of interface that requires a function then as well as a constructor, subject to the three conditions above.

Other monads

In our Option[T] type we didn't really have to make thing: T | null. We could choose the internal representation to our liking. For example Rust has Result<Type, Error>, which behaves similarly to our Optional except that if there is an Error value you get a bit more information than null. This might come as a surprise, but arrays and lists are actually monads as well, with the expected implementation (flatMap as .then):

interface Array[T] {
  _array: JavaScript array
  function then[S](do_stuff: (T) ⇒ Array[S]): Array[S] {
    return make_array(_array.flatMap(do_stuff))
  }
}
function make_array[T](value: T): Array[T] {
  return { _array: [value] }
}

Take note here that we can get .map(f) where f: T ⇒ S back by doing .then(function (v) { return make_array(f(v)) }). This would have worked for Optional as well -- it works for all monads.

Not a revolutionary idea on its own I suppose, we could imagine someone coming up with this interface without knowing what a monad is. The history of why this concept became interesting for programming is in the programming language Haskell. A design requirement of the language is that no pure function in the language can modify the state of the world outside the program itself. So we can't technically print to the console on our own, or write to a file, etc.

From the other side in the code perspective we want to tag them somehow so all callers are also forced into propagating the tag, and the same to their callers, and so on, so that we can track the effects.

Notice how the implementation of Promise[T] is entirely opaque inside the runtime. No one ever said the internals must be exposed like it were with Optional! We can use an opaque structure with the monad shape to play a trick to get our tagging behaviour. This is the exact same mechanism that leads to the Promise/Async/Future function colouring problem (all callers can only return Promise<T>), but in our case with IO this is precisely desirable.

In Haskell, there is the IO monad. Roughly speaking:

interface IO[T] {
  function then(do_stuff: (T) ⇒ IO[S]): IO[S]
}
make_IO(value: T): IO[T] 

IO[T] doesn't mean T wrapped inside some box called IO you can find in the program's memory like a generic class in the C++/Java sense. The program ultimately gets encapsulated in a main: IO[void] object. The computer isn't thought to literally be performing each step of the way main is composed of your functions in IO.then. But rather this final object represents the abstract algorithm the computer should follow. Running the executable that the compiler produces can be thought of try making the computer follow the specifications in the IO[void] object. If the object promises to launch a nuke then the runtime better not have lied to you that it can, as the runtime is the place where meaning is injected into the IO object.

Of course in the real world there is no material bits on your hard drive of this supposed IO object. The Haskell compiler functions like any other and outputs code that a machine can run. Recall the graphic we drew for Optional. You can picture something similar with IO's .then as a huge graph sequencing all the effects your program needs to perform to be useful.