Advent of Code 2023: Day 6

Hurl is a dynamically-typed programming language that uses exception handling as its only form of control flow. Much of the syntax is unsurprising, but the forms of exception raising and handling deserve close examination.

Here is the canonical way to do conditional branches in Hurl:

try {
    hurl 1 < 2;
} catch (true) {
    println("hooray");
} catch (false) {
    println("what weird machine are you running on this on?");
};

In this example, the hurl keyword raises an exception with the value true, which then is matched by the catch (true) block. There are three forms of the catch block:

• catch (<expr>) { ... } will match if the exception value evaluates equal to <expr>¹
• catch as <identifier> { ... } will match any value and make it available as an <identifier> variable in the catch body
• catch into <identifier> will match any value and assign it to an already-declared variable <identifier>

Hurl has functions, but since we have exceptions, there is no need for that pesky return keyword: we can just hurl the value we want to return:

let add = func(x, y) {
    hurl x + y;
};

try {
    add(3, 4);
} catch as result {
    println(result);
};

There is a second way to throw exceptions: if you toss a value, it will be match against the parent catch blocks, but when that block calls return² execution will resume from after the toss. Crucially, toss can be called multiple times to invoke the parent catch block as many times as desired, which gives us a tool to build continuations.

Making Hurl even more exceptional

Hurl is an exceptional language, but some parts seem unexceptional to me. For example, we only really need the let <ident> part of let <ident> = <value>, since we can write:

# Today's Hurl:
let add = 0;
# Tomorrow's Hurl?
#let add;

try {
    hurl func(x, y) {
        hurl x + y;
    };
} catch into add;

Since the value part is unnecessary and the language is dynamically-typed, I will restrict myself to only ever assigning the value 0 with let, with the hope that this is removed from the language in the future.

Another unexceptional part of the language is the collection of built-in functions for I/O and manipulating numbers, strings and lists. Having such a collection is necessary to make the language practical to use, but they currently evaluate as expressions rather than hurl'ing their results—something that user-defined functions cannot do.

Fortunately, it is not too difficult to build a compatibility layer to remove their special status. Wherever you see FOO_proper, this is a version of the built-in function FOO that hurl's the result rather than evaluating to it. For example:

let read_file_proper = 0;

try {
    hurl func(filename) { hurl read_file(filename); };
} catch into read_file_proper;

Finally, there is no need for builtin comparison operators in the language. We can make these truly exceptional with a three-way comparison operator for numbers:

let lt = 0;
let eq = 0;
let gt = 0;
let cmp = 0;

# Some enums or list unpacking would be neat...
try { hurl 0; } catch into lt;
try { hurl 1; } catch into eq;
try { hurl 2; } catch into gt;

# cmp(a, b) hurls lt (if a < b), eq (if a == b) or gt (if a > b).
try {
    hurl func(a, b) {
        try {
            hurl a < b;
        } catch (true) {
            hurl lt;
        } catch (false) {
            try {
                hurl a > b;
            } catch (true) {
                hurl gt;
            } catch (false) {
                hurl eq;
            };
        };
    };
} catch into cmp;

And for strings (which do not support lexicographic comparison in Hurl) we need an explicit equality function:

let equals = 0;

try {
    hurl func(a, b) {
        hurl a == b;
    };
} catch into equals;

Wait, what was I doing again?

Oh, that’s right, we’ve got an Advent of Code problem to solve. Today we have data about some boat races. Each race has a duration: we can use some portion of this duration to charge our boat, and then we spend the remainder of the duration moving at a speed determined by how long we charged our boat for. If we hold the button for hold of the duration milliseconds, then we will travel hold * (duration - hold) millimeters.

If we wanted to maximise that distance, we'd want the two parts of that multiplication to be as close to each other as possible, so hold would be either floor(duration / 2) or ceil(duration / 2). But that's not our problem: we want to know how many different ways we could beat a competitor who achieved a certain distance (target).

We could do maths to find an analytical solution, but that sounds like work, so let's not. We could also just evaluate every possible hold value, but it seems likely that Part 2 of the problem will make the problem bigger or more complicated, and maybe that would be too slow (but maybe not?). Or we could implement binary search. That sounds more fun.

In order to binary search, we make use of the half-way point: we can split our problem into the intervals [0, floor(duration / 2)] and [ceil(duration / 2), duration]: hold * (duration - hold) will be strictly increasing for the first interval, and strictly decreasing for the second. So we can binary search the first interval for the smallest value of hold where hold * (duration - hold) > target (we start beating the competitor), and the second interval for the smallest value where hold * (duration - hold) <= target (we stop beating the competitor). The difference between these hold values is the number of ways we can beat them.

So anyhow, we need an implementation of binary search. Here’s one using the loop function from Hurl’s standard library:

let binary_search = 0;

try {
    hurl func(lower, upper, fn) {
        try {
            loop(func(locals) {
                try { hurl locals.1; } catch as lower {
                try { hurl locals.2; } catch as length {
                try { hurl floor(length / 2); } catch as half_length {
                try { hurl lower + half_length; } catch as mid {
                try {
                    fn(mid);
                } catch (true) {
                    toss [lower, half_length];
                    try {
                        cmp(half_length, 0);
                    } catch (eq) {
                        hurl false;
                    } catch as ne {
                        hurl true;
                    };
                } catch (false) {
                    length = length - half_length + 1;
                    toss [mid + 1, length];
                    try {
                        cmp(length, 0);
                    } catch (eq) {
                        hurl false;
                    } catch as ne {
                        hurl true;
                    };
                }; }; }; }; };
            }, [lower, upper - lower]);
        } catch as result {
            hurl result.1;
        };
    };
} catch into binary_search;

On each iteration, loop invokes the function in its first argument with the parameter locals, which starts as the second argument ([lower, upper - lower]). Each time the function is invoked, it should toss a new value which will replace locals for the next invocation, and hurl either true or false to indicate if the loop should continue. Finally, loop will hurl locals so the caller can produce a result.

This example also shows off our three-way comparison operator³: we catch eq explicitly, but then aggregate lt and gt into a variable (the name doesn’t matter, but ne aids readability). You will also notice a bunch of faces that look like they want to Hurl (}; }; }; }; };). These are from using catch as blocks in sequence, to avoid the use of let.

Anyhow, we define a distance function and implement lower and upper as functions which do the comparisons used by the binary search, find the two values of hold and subtract them.

let distance = 0;
let ways_to_beat = 0;

try {
    hurl func(hold, duration) {
        hurl hold * (duration - hold);
    };
} catch into distance;

try {
    hurl func(duration, target) {
        try {
            hurl func(hold) {
                try {
                    distance(hold, duration);
                } catch as d {
                    try {
                        cmp(target, d);
                    } catch (lt) {
                        hurl true;
                    } catch as ge {
                        hurl false;
                    };
                };
            };
        } catch as lower {
        try {
            hurl func(hold) {
                try {
                    distance(hold, duration);
                } catch as d {
                    try {
                        cmp(target, d);
                    } catch (lt) {
                        hurl false;
                    } catch as ge {
                        hurl true;
                    };
                };
            };
        } catch as upper {
        try {
            binary_search(0, floor(duration / 2), lower);
        } catch as l {
            try {
                binary_search(ceil(duration / 2), duration + 1, upper);
            } catch as u {
                hurl u - l;
            };
        }; }; };
    };
} catch into ways_to_beat;

That’s the core of the problem, but we also need to parse the input and multiply together the results of multiple races. The second part is fairly straightforward, but parsing the input is a little more tricky, since we have numbers with any number of spaces between them:

Time:      7  15   30
Distance:  9  40  200

There is a split function in the standard library, but it will turn "7 15" into ["7", "", "15"], so we need to be able to remove empty elements. All that’s needed for this is filter(xs, pred) (returns a new list of the items in xs for which pred(item) returned true), but I thought I might need map later⁵, so implemented map_filter_nil(xs, fn) (returns a new list of fn(item) for each item in xs, skipping items when fn returns nil). Unfortunately, while nil is a valid value at runtime, it’s not part of the language syntax, so we need to jump through a hoop to make it accessible:

let nil = 0;
try {
    try {
        hurl func() {};
    } catch as nil_producer {
        hurl nil_producer();
    };
} catch into nil;

And then we can implement map_filter_nil. It might be possible to write this better using one of the other loop functions in the standard library, but I didn’t immediately see anything which would work.

let map_filter_nil = 0;

try {
    hurl func(xs, fn) {
        try {
            loop(func(locals) {
                try {
                    at_proper(xs, locals.1);
                } catch as item {
                    try {
                        try {
                            fn(item);
                        } catch (nil) {
                            hurl locals.2;
                        } catch as value {
                            hurl locals.2 + [value];
                        };
                    } catch as new_list {
                        toss [locals.1 + 1, new_list];
                        try {
                            cmp(locals.1, len(xs));
                        } catch (lt) {
                            hurl true;
                        } catch as ge {
                            hurl false;
                        };
                    };
                };
            }, [1, []]);
        } catch as rv {
            hurl rv.2;
        };
    };
} catch into map_filter_nil;

And then we can construct a split function that drops empty values:

let split_ignoring_whitespace = 0;

try {
    hurl func(string, sep) {
        try {
            split(string, sep);
        } catch as rv {
            map_filter_nil(rv, func(s) {
                try {
                    equals(s, "");
                } catch (false) {
                    hurl s;
                } catch as ne {
                    hurl nil;
                };
            });
        };
    };
} catch into split_ignoring_whitespace;

Part 2

My guess from earlier turned out correct: Part 2 makes the numbers bigger by combining the races into one (in the example above, "7 15 30" is read as 71530 and "9 40 200" as 940200). These numbers don’t seem that big though, so I suspect trying every hold value is perfectly viable.

So there were some minor changes to input parsing, but nothing particularly interesting.

Anyhow, I recommend having a read of Hurl’s documentation, there are a bunch of interesting examples that demonstrate the capabilities of exceptional control flow. And if you’re the kind of person who thinks this is all very sensible, I can also recommend SIGBOVIK, whose 2024 proceedings are how I discovered this language.

As usual, a complete code listing is available in the repository.