/dev/code

I have been doing the ICFP Programming Contest since 2005 under the team name O Caml, My Caml (even if I don't always use OCaml) and it's something I look forward to every year and clear my calendar for. Unlike the past few years, I didn't pull an all-nighter one of the nights, although I went to bed at 3am Saturday morning.

This year's contest was to generate instructions for a flying nanobot to do 3-D printing. I won't go into the details here, you can find them at https://icfpcontest2018.github.io/. One interesting detail, though, is that it allows the nanobot to split itself, but at the end, all the nanobots have to fuse back together (fission & fusion). It was a fun contest, well thought-out, well-specified, and had some helpful tools. Kudos to the folks at Rochester Institute of Technology! It is remarkable how contest organizers year after year are able to come up with tasks where it is reasonable to get something working, but hard to get it to work really well. I usually manage just the "something working".

The source code is available at https://github.com/wutka/icfpcontest2018

I feel a little disloyal to the "functional" part of the contest as this year and last year I used Go. Overall I have been happy with my choice, but there are things I miss.

Although I did some coding to support the fission/fusion, I ended up not using them, which also meant I was unlikely to finish well. I did some reading about splitting blobs into rectangles and such, but in the end went with more of a scanline system. My overall strategy was twofold: 1. Build the model from the bottom up, because you normally can't add a voxel (3-d pixel) unless it is adjacent to another voxel. While the specification lets you put the model in a suspension mode that overrides this requirement, it also has much greater energy requirements and I decided to avoid it. I would just alternate left-to-right/right-to-left along the X axis, front-to-back/back-to-front along the Z axis as it moved from bottom to top along the Y.

Once it finished the scanning on a particular X-Z plane at a give Y, it would check to see if there were places that still need to be filled that can now be filled (for example, if the scanning had to skip a pixel because it had no adjacent voxel and that adjacent voxel was created on the next scan.
The second step was to go from top down looking unfilled spots that can now be filled, and then bottom-up, repeating until there were no changes during a complete pass.

Along the way, I had to write a function to compute the shortest safe path from point to point. During the initial construction, the nanobot sits right above the plane it is constructing so it has total freedom of movement. Once it has to pass through planes that may be filled, it needs to navigate around filled spots. In trying to optimize one failed algorithm, the Go profiler showed that the GetShortestPath function was consuming a huge amount of time with memory allocations, so I made it use more static data, but cleared out some things when they got too big.

After the lightning round was over, the task changed to have two additional types of problems - deconstructing an existing model, and transforming one model to another. For the deconstruction, I jokingly thought I could just reverse the trace file I generated. A minute later, I realized that's exactly what I wanted to do, and I had deconstruction working very quickly. I know in my mind that general approach to transforming would be to delete what doesn't need to be there and add what does, but in the end I just deconstructed the old and constructed the new. The last day of the contest was something of a waste for me. I tried a different approach where instead of just scanning, I would break the plane into blobs and figure out the optimal pattern for tracing through each blob. It generated much more efficient files, but took way more CPU, and as the problems got more complex, it couldn't complete them in a reasonable time. But then I realized that my original algorithm was moving around more than it needed to, and when I fixed that, it turned out to be about as efficient as the blob algorithm, but ran WAY faster.

These are the things about Go that helped me:

Easy byte file I/O The model files you have to read, and the trace files you write are all bytes. I just use ioutil.ReadFile and ioutil.WriteFile to read and write them.

Easy array and slice access and manipulation This is where I get a bit away from the functional part, since I do mutate state quite a bit. I could have done this fairly easily in OCaml, too.

Predictability This isn't so much a plus for Go as a knock on Haskell. While Haskell's purity makes it much easier to reason about functions, its laziness can make it harder to reason about the time and space performance. I say this having happily used Haskell in past contests, but have occasionally had these problems.

GoLand I often use Emacs for OCaml and Haskell, sometimes Vim, but I really prefer GoLand (with a Vim plugin). It has great navigation and refactoring.

These are the things about Go that I wish were different:

No variant data types I often want to define something like a set of commands as a variant data type. The Go way to do that is to define separate structs and switch on the type. It's doable, but ugly, and not very typesafe (you can't detect unhandled cases).

No destructing bind and no tuples Yes, Go does let you return multiple values and bind the results, but I also want to have lists of tuples and such and be able to bind values from them, or to destructure the components of a struct in the function declaration.

So overall, I like Go, but miss features from some functional languages. I think there's an aspect to my feelings about Go that are similar to how I felt about Java in 1996. I was doing mostly C++ in 1996, and Java made a lot of things easier - no more copy constructor semantics, simple collections (this was back when STL was still new and not uniformly implemented), programs crashed with reasonable exceptions instead of Bus Error or Segmentation Fault. It took a while for the verbosity of the language (or lack of expressiveness to be more apparent). One of my pet peeves is that you still can't just declare a map like { "foo": "bar", "baz": "quux" }. I feel that way with Go. I used it to replace some Python programs at first. I love that I can build for all platforms from one machine. I love having a single static binary (usually). It's good that it doesn't take long to learn the language. It interfaces well with the operating system. But, I know that over time, I will get more frustrated with how much I have to do manually (or have to write myself - map, fold, filter for example). There are no generics.

Anyway, regardless of what language I use, I'm looking forward to the 2019 ICFP Programming Contest!