soxfox

Allergies is a simpler task than last week’s, based on the concept of bit fields. In this task, any combination of allergies (from a given list) that a person might have is represented as a single integer score. The least significant bit of the integer represents one allergy (eggs, specifically), the next bit represents another (peanuts), and so on. Each bit that is set represents an allergy being present. Additional bits can be ignored.

The two functions in this exercise are (names differ between languages):

My general strategy is to use bit shifts and the bitwise AND operator to implement is_allergic_to, then use that to implement allergies by checking each possible allergy. Where things get interesting is in how I deal with the enumerators themselves.

Languages

Elm

Elm is an ML-like language specifically designed for building web applications. As a functional language inspired by ML, it uses immutable data structures, and everything revolves around writing functions to operate on that data.

The template from Exercism contains a definition of the Allergy type that we use:

module Allergies exposing (Allergy(..), isAllergicTo, toList)

type Allergy
    = Eggs
    | Peanuts
    | Shellfish
    | Strawberries
    | Tomatoes
    | Chocolate
    | Pollen
    | Cats

Unfortunately enums in Elm, unlike those in systems languages, do not have a numeric value (at least not one exposed to the user), so I had to create my own conversion function, as well as a list of all allergies for use in toList (the Elm version of allergies):

allergyToBitmask : Allergy -> Int
allergyToBitmask allergy
    = case allergy of
        Eggs -> 1
        Peanuts -> 2
        Shellfish -> 4
        Strawberries -> 8
        Tomatoes -> 16
        Chocolate -> 32
        Pollen -> 64
        Cats -> 128

allergies : List Allergy
allergies =
    [ Eggs
    , Peanuts
    , Shellfish
    , Strawberries
    , Tomatoes
    , Chocolate
    , Pollen
    , Cats ]

You can see here that instead of converting allergies to their indices, I just converted them straight to the single-bit values that will be used later to check bits in score. This particular way of formatting lists, with commas at the start of each line, instead of at the end of the previous, is common in Elm, and it keeps items nicely aligned. Having to explicitly write out these tables is unfortunate, but I wasn’t able to find much to do to clean this up. There’s seemingly no built in way to get the index of an item in a list, and when I tried working with dictionaries, I found that it’s impossible to make custom types comparable.

import Bitwise

isAllergicTo : Allergy -> Int -> Bool
isAllergicTo allergy score =
    Bitwise.and (allergyToBitmask allergy) score /= 0

Checking if an allergy is present is pretty straightforward. Elm has no bitwise operators, so the function Bitwise.and is used here instead, then I just check if the bit was set (the result was non-zero).

toList : Int -> List Allergy
toList score =
    List.filter (\allergy -> isAllergicTo allergy score) allergies

Creating the list of allergies for a score is pretty easy too, using List.filter and a lambda function.

Most of the code in the Elm version is just there to manage the Allergy type. The main function implementations are pretty nice, but I really wish there were better tools in Elm for dealing with custom types like this.

Lua (Bonus!)

Moving on from Elm to another language that doesn’t have enums with numeric values – in fact, one that doesn’t have enums at all – we have Lua. This one wasn’t featured, but I’d already solved the exercise in the next language. Designed primarily as an embeddable scripting language (the text editor and the terminal I’m writing this post in are both configured with Lua), Lua is a pretty small and simple language. It’s dynamically typed, only has a single type, the table, for representing more complex data, and intentionally keeps unnecessary features out of the language.

Lua has no enums, but thanks to its flexibility, I used this exercise as a chance to add a simple form of enums to Lua. The following function is my implementation of enums:

local function enum(...)
    local t = { all = {} }
    local all = t.all
    for i, name in ipairs { ... } do
        t[name] = i - 1
        all[#all+1] = name
    end
    return t
end

This won’t cover every possible use of enums that you might ever want, but it does exactly what I need it to. I can use the enum function with as many string arguments as necessary to create a table that maps those strings to successive numbers, and provides a convenient way to iterate over them.

local Allergy = enum(
    "eggs",
    "peanuts",
    "shellfish",
    "strawberries",
    "tomatoes",
    "chocolate",
    "pollen",
    "cats"
)

local function allergic_to(score, which)
    return (score & (1 << Allergy[which])) ~= 0
end

Using this I make the enum, and allergic_to is pretty easy to write. Indexing the Allergy table converts strings to the corresponding value, then the logic is the same as usual.

For the final part, list, I wanted to use the same higher-order functions that I’m used to in other languages, so I wrote a quick version of filter to use:

local function filter(l, f)
    local r = {}
    for _, v in ipairs(l) do
        if f(v) then
            r[#r+1] = v
        end
    end
    return r
end

local function list(score)
    return filter(Allergy.all, function(a) return allergic_to(score, a) end)
end

It just iterates over each item, calls a function, and if the function returns true (or anything other than false and nil), adds it the the output table. Implementing list is then basically the same as in Elm, with slightly different syntax.

While this isn’t true metaprogramming as someone coming from Lisp might be used to, where you can treat code as data, I find that Lua’s simple design plus powerful table structure means that treating data as data might be enough.

Rust

🦀🦀🦀🦀 Rust time! 🦀🦀🦀🦀 I’m a huge fan of Rust, and I’ve been waiting for it to make an appearance here. While I’m yet to find a “perfect” programming language, Rust falls solidly into the “pretty excellent” category. It’s a general purpose programming language, and is particularly popular for systems programming, but has found applications just about everywhere. Writing this blog post, I use at least three tools that are built at least partially with Rust – my terminal emulator, the SVG rasteriser that makes the OpenGraph cards, and Firefox (yep, several components in Firefox are Rusty!) – and I feel like that number will probably increase over time.

For this exercise, I get to show off one really neat feature of Rust. I mentioned my Lua solution didn’t involve true metaprogramming, but this one certainly does! I’ve pulled in the enum-iterator crate, which allows me to automatically generate the code to iterate through all of the allergies.

use enum_iterator::{all, Sequence};

pub struct Allergies(u32);

#[derive(Debug, PartialEq, Clone, Copy, Sequence)]
pub enum Allergen {
    Eggs,
    Peanuts,
    Shellfish,
    Strawberries,
    Tomatoes,
    Chocolate,
    Pollen,
    Cats,
}

These are the types that get used for this exercise. Allergies is a simple wrapper type that allows the type system to ensure we only use values of this type in the expected places – this sort of thing helps avoid confusion when using the same primitive types for multiple specialised purposes, and gives you the option of adding helper functions to these primitive types. Allergen is a plain enum with several traits (pretty much like interfaces in many OOP languages) automatically implemented by derive. derive uses procedural macros to generate code at compile time, cutting down on the amount of boilerplate you need to write.

The first two, Debug and PartialEq are required for Exercism’s tests, so I won’t go into details on those here. Clone and Copy allow me to make copies of the data as needed – Clone adds the clone method to values, to explicitly clone them, and Copy (which requires Clone to be implemented first) allows values of this type to be implicitly copied by just copying the raw bits, which works well for simple and small types.

Those four derive macros are provided by the Rust standard library, but the next one comes from the external crate. Sequence is the derive macro I mentioned that allows me to easily iterate over enum values without writing the boilerplate code myself!

The actual functions here get implemented as methods on Allergies inside an impl Allergies block. The internals of Allergies are not public, so the first thing to write is a new function to create Allergies values, which is very simple, since it’s just a wrapper type:

pub fn new(score: u32) -> Self {
    Self(score)
}

The is_allergic_to function is basically the same as I’ve shown so far, except that getting the numeric value of an enum is as simple as casting it to a number with as u32.

pub fn is_allergic_to(&self, allergen: &Allergen) -> bool {
    self.0 & (1 << *allergen as u32) != 0
}

Finally, the implementation of allergies is a one-liner, thanks to the enum-iterator crate:

pub fn allergies(&self) -> Vec<Allergen> {
    all::<Allergen>().filter(|a| self.is_allergic_to(a)).collect()
}

I just use all from that crate to get an iterator over the enum values, filter it down like the other solutions, and collect into a Vec, since iterators are a lazy type that need to be consumed like this to get an actual list.

The Rust standard library doesn’t always have everything you need, but there’s a good chance that a third party crate will, and Exercism supports a lot of useful crates.

Nim

Nim is a language I introduced back in week 2, but to recap: modern language, Pythonic syntax, compiles to C, excellent standard library. I saved Nim for last because it has a really beautiful trick that makes this exercise incredibly easy!

Sets are supported not as a standard library collection, but as a language feature in Nim, and they are stored as bit fields. (There is also a more typical hash set in the standard library.) Our allergy score is a bit field – maybe you see where I’m going with this? The track maintainers realised this, and used a set as the return type for allergies, leaving very little work for me to do.

Step 1: Define the enum. (* means export.)

type
  Allergen* = enum
    Eggs, Peanuts, Shellfish, Strawberries, Tomatoes, Chocolate, Pollen, Cats

Step 2: Cast.

proc allergies*(score: int): set[Allergen] =
  cast[set[Allergen]](score)

Step 3: Use allergies to implement isAllergicTo:

proc isAllergicTo*(score: int, allergen: Allergen): bool =
  allergen in allergies(score)

That’s it. The allergy score is a Nim set, I just have to cast it to one, then I can use that to check single elements with efficient bit field operations.

This bit field set type would be really handy for interacting with C APIs that use bit fields to specify a set of flags, and I imagine that’s part of why it was created. Nim has once again impressed me, but once again I doubt I’ll use it for too much outside of Exercism.

Final Thoughts

I’m glad I finally got a chance to use Rust in #48in24, and I think that it worked quite well for this task! I had decided not to pull in Rust as a bonus language, because it would have taken away a chance to try other languages, but if I find another task where it would work well, I might show it off again.

Thanks for reading, hopefully you learned something new!