Project Serpent, Day I-lost-track

On day 8 (which I believe was Sunday), I announced that I was happy with the progress I was making, and that I was confident enough in my ability to finish that I would treat the end of this next week as a deadline.

And then the next day I went to work, and realized that perhaps my pronouncement was premature.

It turns out it’s really hard to work on anything after coming home from a full day of work. Luckily, I still find it pretty easy to get some work done on Serpent before I leave in the morning, but even so that’s much less time than the four hours I told myself I’d spend. I’m no longer sure I can finish by the end of this week, and even writing up daily progress reports is kind of hard. Some concessions are due.

I will not give up on Serpent, but I’ll make the following modifications to my challenge:

  1. I will work on Serpent for a minimum of 30 minutes each day.
  2. My deadline (which is once again a soft deadline, like the one I set for the first week and unlike the one I meant to set for this week) is December 30.
  3. I will no longer require myself to post progress updates every day, though I’ll still try to do it every couple of days and I will still require myself to stick to my pre-Serpent schedule of one post per week.

Now that the unpleasant concession is out of the way, here is an actual progress update.

This morning I wrote up an abstract effect and handler for operations depending on user keyboard input. This is the next step of my “make everything interactive, thereby increasing my motivation” project: I have a snake that moves around at reasonable speeds, but right now it just plods inexorably toward the right edge of the screen until finally it crosses the threshold, never to be seen again. I don’t even get to see whether I’ve correctly handled cases of the game state evolution and drawing functions for when the snake does not consist of a single segment.

Over the next couple days (hopefully by the end of this week), I’m not going to work on actual collision with walls and eating food, but I hope to have the snake respond to the arrow keys by turning around!


The Skill of Finishing Things

In my last post I mentioned that one of the reasons I did my little game jam was social pressure: I felt my programming skills and ideology were under fire, and wished to renew my confidence in them.

But there’s another motivation behind the game jam, one that has been stewing at the edges of my mind for much longer. It’s about the Skill of Finishing Things.

One of my favorite things to do in my free time is to just play with ideas. I just sit around and mull over something in my mind: maybe a game idea, or a mathematical curiosity, or an imagined scenario of the future, or a conlang idea, or some fictional setting or conceit or sometimes even a plot. But (and this seems to be a very common problem) I have a hard time seeing these things through to completion. I realize that it’s okay not to turn every cool idea into a finished product; that would be impossible. But I really wish I could pick, say, one idea per month, or even every six months or every year, and stick with it (even if I consider other things in my free time) until I have something to show for it.

And my Pong jam was one small step in that direction. I had done game jams in the past, but never finished one before — I’ve always been too ambitious. I just desperately needed to have something to my name that I could call complete, so I set my sights as low as possible and gave myself a deadline short enough that I could stand to spend almost every waking hour working until it was done. And that worked, and now I have a shiny thing to show off that’s actually complete. Great!

But where does this leave me? I found a way to finish small, unambitious things. That’s better than nothing. Certainly it’s a hugely important symbolic step — the pride and confidence I felt when I finished were immense, and now if I ever want to develop any small ideas I know a way to do it. But setting a close deadline and spending every waking moment working is not a scalable approach. I can neither repeat this procedure to finish many small projects in rapid succession, nor can I extend the deadline to finish a larger project in this way — that’s just too much strain, especially since I’ll be starting work at an actual job soon. So I need to find another way.

I think the next step is to try to find a way to extend this “game jam” model to a slightly longer project: commit to dedicating at least a particular proportion of my time to the project, and set a deadline after which I’ll call the project finished. This will be inherently more difficult with a longer deadline, but sometimes there’s no way around difficulty — I’ll just have to develop the discipline to do it.

I think my next attempt will be “work four hours a day and finish in a week”. I’ll post again when I decide what to work on and when to begin.

Algebraic Data Types, pt 2: Case analysis is not a nested conditional

In the previous post in this series, I gave an example of trees in Python and Haskell:

class Tree:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right= right
    def preorder(self):
        if self.value is None: return []
            if self.left is None: left_pre = []
            else: left_pre = self.left.preorder()
            if self.right is None: right_pre = []
            else: right_pre = self.right.preorder()
            return left_pre + [self.value] + right_pre
data Tree = Empty | Branch Int Tree Tree
preorder Empty = []
preorder (Branch val left right) = preorder left ++ [val] ++ preorder right

It’s probably possible to capture some of the clarity of the Haskell version in our Python (perhaps by making the __init__ code a bit more complex, but that’s okay since most users of the class won’t have to modify __init__):

class Tree2:
    def __init__(self, value=None, left=None, right=None):
        if value is None and left is None and right is None:
            self.shape = 'empty'
        elif (value is not None and left is not None
              and right is not None):
            self.shape = 'branch'
            self.value = value
            self.left = left
            self.right = right
            raise SomeKindOfError
# finally, the actual function
def preorder(tree):
    if tree.shape == 'empty':
        return []
    elif tree.shape == 'branch'
        # We know the left and right subtrees are not None
        return preorder(tree.left) + [tree.value] + preorder(tree.right)
        raise ValueError("%s is not a valid tree!" % tree)

Indeed, this captures some of the clarity of the Haskell code: instead of writing preorder as a series of nested binary tests that interleave detective work (figuring out what shape our data has) with application logic (actually computing the preorder of the tree), we hide all the detective work in the Tree constructor, and all preorder has to do is query the information that’s already there. To someone reading preorder (and who knows what a Tree is), it’s immediately obvious what we’ve learned in each branch of the conditional: either the tree is 'empty' or we’re looking at a 'branch'.

But clarity is only one of the things that case analysis buys us. I can immediately think of two other things that you don’t get by simulating case analysis with a series of conditionals:

First, they’re easier for the compiler to understand, and more things the compiler understands means fewer things the programmer has to remember. For example, in our Python code above, it’s up to the programmer to remember that tree.shape == 'branch' means that tree has left, right, and value attributes that are not None. In Haskell, the compiler knows what attributes each constructor has, and if the programmer tries to use an attribute that isn’t present, the compiler will catch that mistake. Also, the compiler knows how many cases there are and can issue a warning if you miss any — this can be very helpful with more complex patterns or with data types have more constructors. For example, consider the following type for representing mathematical expressions (perhaps we’re implementing a calculator and we want to echo the expression back to the user instead of just displaying its result):

data Exp = Add Exp Exp | Sub Exp Exp | Mult Exp Exp | Neg Exp | Constant Int
eval :: Exp -> Int
eval (Constant x) = x
eval (Add x y) = eval x + eval y
eval (Sub x y) = eval x - eval y
eval (Mult x y) = eval x * eval y
eval (Neg x) = - (eval x)

That’s kind of a lot of constructors, and it’s easy to imagine extending this type with even more (variables are an obvious next step). Translating this into a Python class would be kind of tedious, and users of the class would need to remember what “shapes” to test and what data each shape contains. In Haskell, though, the compiler will immediately tell you whether you’ve handled every case correctly!

Second, case analysis can be compiled into more efficient code than a series of conditionals. In Python, the entire logic of “We know this data type has one of the following shapes:” is handled in user-level code. In this implementation, that means repeatedly fetching a string attribute and comparing it to one of the alternatives. But in a language where the compiler knows about case analysis, we can hide all of this dispatching logic away from the programmer, and that means that we can make all kinds of optimizations that would make the Python less readable. For example, in GHC, each data constructor is represented as just part of an integer (it only needs to be a couple bits, so it’s stored alongside some other pieces of data that only need to be a couple bits), and in many cases a pattern match can be compiled as a jump table lookup instead of sequentially testing alternatives.

Finally, in case this isn’t immediately obvious: boolean conditional branching can be implemented as a special case of case analysis. First, case analysis isn’t just a top-level function definition thing: we could rewrite our earlier tree functions with a so-called “case expression” instead.

preorder tree = case tree of
  Empty -> []
  Branch val left right -> preorder left ++ [val] ++ preorder right

So now we see that doing case analysis on a boolean is pretty much the same as an if expression:

if cond then trueVal else falseVal
-- is the same as
case cond of
  True -> trueVal
  False -> falseVal

Taking case analysis as a language primitive and deriving boolean branching from there is much nicer than taking boolean branching as primitive and trying to derive case analysis from that.

Algebraic Data Types, pt 1: What are they?

In Python, every data type you can define is a class. This class will usually have one or more attributes and some methods that know how to use those attributes (though in Python sometimes you take the less object oriented route and use the attributes directly). Usually there’s a specific set of attributes that you want every member of the class to have — for example, a Point class might have attributes x and y (which should be numbers) or a Matrix class might have data (a list of lists, or something), width, and height (more numbers) — but Python doesn’t really provide any way to enforce this except convention.

C has structs, which if you squint are kinda-sorta vaguely similar to Python’s classes. A struct has some set of attributes (in C you’d call them fields), though unlike Python a struct definition contains a specification of what fields can and must exist. Structs also can’t have methods defined, but you can kind of fake it by not exposing the struct definition so that people can only manipulate the struct by using your functions.

C has another thing, though, to which Python doesn’t really have an equivalent: the enumeration type. In C, you can declare a new type (call it TrafficLight, since that’s what a lot of tutorials seem to do) and say just that it contains three distinct values: red, yellow, and green. These are a bit like lisp keywords in that they can be compared in constant time and contain no data other than which value they are.1 Unlike keywords, each enumeration type has its own set of values — you can’t use a TrafficLight in a place that expects a FileMode (whose values are probably read, write, and append, and maybe rw and some other things). Enums are a very good solution to the problem of “there are exactly seven possibilities for this piece of information and I’d like to distinguish between them”, and it can be kind of frustrating when you want them and you’re working in a language that doesn’t have them. But enums are limited in their own way: they can’t store any data. So for example, if you wanted your FileMode data type to have a field for the encoding of the text you’re working with… you have to add a lot of different enum values, like rw_ascii and rw_utf8 and append_ascii and append_utf8 and so on.

Algebraic data types are a bit like a combination of the two approaches. An ADT definition looks a bit like this:

data FilePosition = Start | End | Offset Int

where the |s separate different alternative forms for values of this type to take. Within each alternative, the first word is called a “constructor” which is a bit like an enum, and all following words are pieces of data that that specific constructor holds — in this case, our Offset constructor holds a single piece of Int data. So a FilePosition is either Start (the beginning of the file), End (the end of the file), or Offset x (which is x characters into the file). Like an enum, if you have a FilePosition you can determine in constant time what constructor it uses, and every FilePosition will use exactly one of these three constructors. But like a struct or Python class, FilePositions can hold data too. And the data held in an ADT value depends on the particular constructor used — if you know the constructor, you (and the compiler) know what kind of data is stored there.

ADT values are consumed in a style commonly called “pattern matching”, but I prefer to think about it as more like “case analysis”. I love it because it makes a lot of things explicit that you already had to be keeping track of in your head anyway. For example, let’s think about binary trees. In Python you might define a tree type like this:

class Tree:
    __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
    def preorder(self):
        # First, the tree might be empty
        if self.value is None: return []
            # Either the left or right subtrees might be empty
            if self.left is None: left_pre = []
            else: left_pre = self.left.preorder()
            if self.right is None: right_pre = []
            else: right_pre = self.right.preorder()
            return left_pre + [self.value] + right_pre

We have a lot of “if” statements there because there are a lot of possibilities. Let’s look at an equivalent in Haskell:

-- we could make trees that hold any type if we wanted, but for
-- simplicity let's stick to integers.
data Tree = Empty | Branch Int Tree Tree
preorder :: Tree -> [Int]
preorder Empty = []
preorder (Branch val left right) = preorder left ++ [val] ++ preorder right

Because we’re using algebraic data types, there’s no need to do any manual conditional checks to see what kind of tree we have — we know that a tree is in either one of two states (it’s empty or it has a value, a left tree and a right tree (either of which could be empty)), and we can tell what kind of tree we have just by looking at the constructor. We also don’t have to handle a bunch of unnecessary possibilities that exist in the python program — for example, is there a difference between Tree(3, None, None) and Tree(3, Tree(None,None,None), Tree(None,None,None))? In Haskell, we don’t need to make a decision: we only have one way to represent a tree containing just 3 (Branch 3 Empty Empty).

Algebraic data types will spoil you quickly. They’re such a nice way to represent data, and case analysis/pattern matching is such a nice way to consume it, that programming without them when you need them can start to feel like a chore.

  1. Except, of course, that this is C and enum values are just integers — so you could use them as integers if you wanted to. 

Impressions of Mercury

I’ve been using Mercury for a while and I think I’ve gotten enough experience to talk a bit about my first impressions.

  • state variables — useful but hacky. Basically, Mercury’s version of haskell’s side effect sequestering involves threading a useless unique variable through all IO predicates (much like GHC’s implementation of Haskell’s IO monad, actually). So !IO (the name can be anything, not just IO) is preprocessed into something like IO1, IO2, except that the next time you write it it becomes IO2, IO3 and so on. The entire exercise seems a bit pointless to me since it’s all a hack to get things to occur in the order you wrote them. It’s no worse than any other language, though — it just doesn’t tickle my aesthetic sense of “a principled way to handle side effects”.
  • DCG — a bit like state variables. Instead of writing foo(A, B, !Var) :- do1(!Var), do2(B, BOut), do3(BOut, A, !Var)., you write foo(A, B) --> do1, { do2(B, BOut) }, do3(BOut). It’s not clear why you need to have both of these, or why it’s preferred to use state variables instead of DCG for writing IO predicates. DCG is kind of fun to write though.
  • I wish there was a way to get multiple clauses to desugar to nested if statements instead of plain disjunctions. The haskell style where you write f ConstructorOne = ...; f (ConstructorTwo bleh) = ...; f _ = ... produces nondeterministic or multi-solution predicates, when you usually want either deterministic or semideterministic (at most one solution).
  • Thinking about determinism is fun, though. See Typechecker-directed Epiphanies — I’m getting to the point where I understand how the determinism checker works.
  • Modes are interesting. Essentially, any given predicate might have several different arguments that make sense as “outputs”. In prolog, if I remember correctly, you could just use any argument as an output, even if the code you wrote to define the predicate causes an infinite loop when you try to solve for that particular variable. In Mercury, you have to declare some set of modes for each predicate — a mode is basically “If you want to solve for this set of variables, you need this other set of variables to have a known form, and this mode of the predicate has at least (zero|one) solution and (can|can’t) have multiple solutions.” And then, this is the cool part: Mercury checks to see that each mode you declare is valid. So if you say :- mode Foo(in, out, out) is nondet. :- mode Foo(in, out, in) is semidet., Mercury will actually check that Foo can provide zero or more values for the second and third arguments if the first argument is known, and that it can provide zero or one value for the second argument if the first and third are known. And this is just scratching the surface; there’s even cooler things you can do by defining custom “insts” (instantiation states). I could probably write a whole blog post about how amazing modes are.
  • I’m not actually making very good use of the logic programming style — almost all of my predicates are deterministic or semideterministic and could easily be rewritten as functions. It’s kind of fun to say eval(Arg, Env, ArgOut), eval(Body, [Arg | Env], AppOut) instead of AppOut = eval(Body, [eval(Arg, Env) | Env]), but it’s a superficial kind of fun, like wearing a halloween costume instead of normal street clothes. I wonder if this is because I’m just not good at taking advantage of logic programming or because logic programming isn’t very good for this kind of problem?
  • Unfortunately, a lot of the cooler prospects of the languages are still unimplemented. Things like unique modes on data type fields and partial instantiation states are just not supported yet — as I understand it, if you try to write code that uses these features, you’ll get a compile-time or runtime error. This is really disappointing, but luckily the language as it exists now is already pretty nice to program in.

Typechecker-directed epiphanies

As I get more experience with powerful type systems like that of Idris and Mercury, I’m noticing a strange phenomenon. These type checkers deal with powerful logics, but the checkers themselves are not very smart; they can only verify a property if it’s syntactically obvious. And if you don’t have much experience with such a type checker, and haven’t learned the quirks of exactly what “syntactically obvious” means, programming in that language can be a chore. It’s been a while since I felt lost in Idris, but since lately I’ve been learning Mercury, I’m getting reacquainted with the despair of “Why won’t you accept this obviously-correct code, compiler?”

But as you get more familiar with what exactly the compiler checks, your relationship with it starts to change. The question changes from “Why can’t the stupid compiler see this?” to “Well, how do I know my code is correct?” And something that very often happens is, once I’ve thought for a few moments about how I know what’s going on, it’s immediately clear how to rewrite the code so that the compiler knows what’s going on.

But more importantly: sometimes, when I’ve taken a moment to think rigorously, I realize that my code isn’t correct. Maybe the Mercury predicate that is supposed to be deterministic actually has multiple solutions — not just the way I wrote it but the way I meant it, and I have to come up with a different plan for writing the predicate because my old one is flawed. And I would never have noticed it before because as far as I can tell, the code is obviously correct.

I admit that stupid typecheckers verifying complicated properties is a bit of a usability problem for people inexperienced with the typechecker. I have felt that pain and frustration, and I know it isn’t pleasant.

But I think it might be worth it. Once the pain goes away, you’re left with an obligation to strengthen your understanding of your code — to go from “This obviously does what I want it to do” to “Here, Stupid Compiler, you can’t understand my higher level thought processes, so let me walk you through it.”