Growing pains: from script to full project

In my last post, I’d made a cyclic tag system simulator in Haskell, which I’ve taken to calling Cyts. To make Cyts useful, it would need a few things:

• CLI to take user input
• Find repeated states, identifying standard halt mechanics
• Capable of returning usable output

As I continued developing Cyts, it eventually grew from a script into a full cabal project. The features I added, how I added them, and the eventual cabal transition are documented here.

Step 1: Building a CLI #

First, I wanted to build a CLI for Cyts that can read in a cyclic tag simulator from the user somehow and have a few nice options to boot. I’d want Cyts to:

• Have default short output and optional verbose output, so it doesn’t always print the full machine output
• Specify number of steps
• Accept user input for custom systems, including empty productions
  • Take user input from stdin and file input, and allow multiple types of input or no input

Haskell is known to be particularly troublesome with “side effects” and usually dislikes taking input from outside the program. However, with use of the IO and Maybe monads and the applicative parsing interface that the optparse-applicative library provides, implementing these turns out to require relatively little code.

Functors, mathematically #

Most of the work was spent in learning how to use optparse-applicative, since it handles pretty much everything else. While it’s built to be very approachable and doesn’t require a knowledge of applicatives to use, it helps to know applicatives to understand what’s going on. Applicatives are a step above functors, so it helps to cover functors.

First, some math. Functors come from category theory, which studies math at a birds-eye level, abstracting above any one field. In category theory, categories are collections of objects with morphisms (basically arrows) between them. Objects represent any mathematical object, and morphisms For example, the category Grp has all groups as its objects and group homomorphisms as its morphisms. Grp contains all of classical group theory, and a category theorist studies categories like Grp from the “outside” instead of using group theory to study the “inside.” What functors are, then, are maps between categories that preserve morphisms: $$ A \overset{f}{\rightarrow} B \overset{F}{\implies} F(A) \overset{F(f)}{\rightarrow} F(B) $$ A functor needs to be able to map on both the objects in the category and the functions between the objects. So what does this mean for programmers?

In Haskell, functors are essentially typeclasses that have the same properties as their mathematical counterparts. Recall Haskell typeclasses are analogous to Java interfaces, in that they specify functions that a type must implement. So a type that implements the Functor typeclass needs to act like a category so that functors can be used to map on that category. The way Haskell does it is by requiring the type to implement fmap:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

fmap initially looks just a generalized map, but the name comes from when we partially apply fmap to some function func :: a -> b. The partially applied function fmap func now has a type signature f a -> f b. Considering the types f a and f b as categories, with f the type of category and a and b the objects, we’ve promoted func from a function a -> b to a functor that maps between the categories f a and f b. fmap func becomes a functor when we enforce that it preserves identity and composition:

fmap id = id
fmap (f . g)  ==  fmap f . fmap g

This is done mostly to make sure functors behave predictably.

How do applicatives factor into this? Put simply, they extend functors to functions that take more than one parameter. If we have some function func :: a -> b -> c, we can’t upgrade this into a functor with fmap. Attempting to gets a function with type signature f a -> f (b -> c), which has a partially applied version of func on the right side wrapped in the f type. Applicatives allow func to be upgraded to f a -> f b -> f c by translating the right side f (b -> c) to f b -> f c (which is done by the <*> function in the Applicative typeclass, which has a type signature of f (a -> b) -> f a -> f b). Since they’re extended off of functors, applicatives also behave predictably as well. optparse-applicative uses applicatives to handle input parsing with IO and Maybe without mandating sequential execution, which a monadic interface would force. That way, the commands -vr and -rv are parsed identically.

Implementing the CLI #

A mess of a main function #

Step 2: Detecting halts #

My State type that I originally coded was able to recognize when its register cleared and

Step 3: Compact mode #

Step 4: Moving to Cabal #