Forem: Tiemen

Implementing Base64 from scratch in Rust

Tiemen — Mon, 02 Aug 2021 17:59:52 +0000

In this article we're taking a closer look at the Base64 algorithm and implement an encoder and decoder from scratch using the Rust programming language. Base64 is quite an easy to grasp algorithm and certainly fun to implement yourself! Let's dive right in!

What is Base64?

Base64 is an encoding algorithm that was primarily designed to encode binary data for use in text-based algorithms by using 64 different ASCII characters to represent the bits. For example email attachments or embedding image data directly into a img tag.

Base64 works by breaking up the original binary in chunks of 3 bytes (24 bits) and splitting these 24 bits into 4 groups of 6 bits. These 6 bits translate to a number anywhere from 0 (0b000000) through 63 (0b111111) that are mapped to 64 ASCII characters.

The original Base64 alphabet uses A-Z uppercase, a-z lowercase, the digits 0 through 9 and special characters + and /. The = is used for padding at the end of the output string, so that we always end on a multiple of four bytes. This is Base64 in a nutshell, for a thorough deep dive into Base64, give this excellent article a read!

The puzzle pieces

Let's walk through the steps that are required to make encoding into and decoding from Base64 work:

Encoding data to Base64 is fairly simple:

Take the original binary input
Chop this stream up in slices of 3 bytes (24 bits)
Chunk each of these 24 bits again in 6-bit parts
Convert these 6 bits into an index (0-63)
Assign an unique character that can be found at that index in the Base64 table
Append padding characters (=) until we until the total encoded string reaches a multiple of four bytes.
et voila!

Decoding is basically working backwards:

Strip off the padding (=)
Iterate over the remaining bytes in chunks of four bytes
Look up each ASCII character in the table to get the original numeric index
From these indexes, take the upper 6 bits and stitch them back together
You end up with a multiple of 8 bits which is your original data

Let's get to work!

Ok, enough theory already! Let's get to work! Let's setup a new Rust project (binary) and implement our first few modules:

cargo new base64 --bin

Implementing an encoding alphabet

As mentioned previously the default Base64 implementation uses an alphabet containing A-Z, a-z, 0-9, + and /. However I want our alphabet to be configurable, enabling us to provide an Emoji-based alphabet instead for example 👻

To make it configurable, let's figure out a common API that we can implement our configurable alphabets against. We're describing this API in what Rust calls a trait (comparable to an Interface in Java, Go or C#).

Defining our Alphabet trait

There are basically three operations that our alphabet should be able to perform; Going from an index to a character, going from a character back to the original 6-bit index and getting the character used for padding.

Let's create a new src/alphabet.rs file inside our project and get going:

pub trait Alphabet {
    fn get_char_for_index(&self, index: u8) -> Option<char>;
    fn get_index_for_char(&self, character: char) -> Option<u8>;
    fn get_padding_char(&self) -> char;
}

Defining the classic Base64 alphabet implementation

Now that we wrote the contract of what an alphabet should be able to perform, let's create the classic Base64 alphabet first.
Like we talked about in the beginning of this post, the classic alphabet uses a-z, A-Z, 0-9 plus +, / and = for padding.

We're creating an empty struct and call it Classic, this will act as the type to call the methods on. Let's also supply an implementation for the Alphabet trait and place all this into the same src/alphabet.rs file for now.

// ... snip trait declaration

pub struct Classic;

const UPPERCASEOFFSET: i8 = 65;
const LOWERCASEOFFSET: i8 = 71;
const DIGITOFFSET: i8 = -4;

impl Alphabet for Classic {
    fn get_char_for_index(&self, index: u8) -> Option<char> {
        let index = index as i8;

        let ascii_index = match index {
            0..=25 => index + UPPERCASEOFFSET,  // A-Z
            26..=51 => index + LOWERCASEOFFSET, // a-z
            52..=61 => index + DIGITOFFSET,     // 0-9
            62 => 43,                           // +
            63 => 47,                           // /

            _ => return None,
        } as u8;

        Some(ascii_index as char)
    }

    fn get_index_for_char(&self, character: char) -> Option<u8> {
        let character = character as i8;
        let base64_index = match character {
            65..=90 => character - UPPERCASEOFFSET,  // A-Z
            97..=122 => character - LOWERCASEOFFSET, // a-z
            48..=57 => character - DIGITOFFSET,      // 0-9
            43 => 62,                                // +
            47 => 63,                                // /

            _ => return None,
        } as u8;

        Some(base64_index)
    }

    fn get_padding_char(&self) -> char {
        '='
    }
}

First things first, we define an empty struct called Classic, such a type in Rust-land is called a zero-sized-type. Due to the lack of fields, it will only exist in Rusts type system, once the compiler chewed its way through our code, there will be no trace of this struct anymore! It is however a very neat way of passing trait implementations around and that is why we are using it.

Following the struct declaration are a few constants followed by the implementation of the Alphabet trait on our Classic struct. The implementation itself makes use of the fact that characters in the ASCII alphabet are defined mostly in sequence. For example: A through Z uppercased have indexes 65 through 90, the same is true for both a through z lowercased and the digits 0 through 9.

We make use of this by pre-calculating an offset between our Base64 index (0-63) and the index in the ASCII alphabet (65-90, 97-122, etc). Then using the match operator match on a specific range, apply the correct offset and return the result as a byte.

Mission accomplished 💪

Building the Encoder! 🙌

Now that we have defined how our alphabet should work, let's get on to building the encoder part of our project. We'll create a new module inside src/encoder.rs and bring the Alphabet trait and Classic implementation into scope:

use crate::alphabet::{Alphabet, Classic};

The next step is setting up a few smaller functions that will take on the heavy lifting of the encoding part.

Splitting it up!

Let's start with our split function:

fn split(chunk: &[u8]) -> Vec<u8> {
    match chunk.len() {
        1 => vec![
            &chunk[0] >> 2,
            (&chunk[0] & 0b00000011) << 4
        ],

        2 => vec![
            &chunk[0] >> 2,
            (&chunk[0] & 0b00000011) << 4 | &chunk[1] >> 4,
            (&chunk[1] & 0b00001111) << 2,
        ],

        3 => vec![
            &chunk[0] >> 2,
            (&chunk[0] & 0b00000011) << 4 | &chunk[1] >> 4,
            (&chunk[1] & 0b00001111) << 2 | &chunk[2] >> 6,
            &chunk[2] & 0b00111111
        ],

        _ => unreachable!()
    }
}

As you can see in the function signature, the split function takes a slice of bytes (&[u8]) and returns a Vec<u8>. It converts the input of up-to 3 bytes into an output of up-to 4 bytes. Essentially converting the 8-bit unsigned integers into 6-bit.

To achieve this, we use bitwise operations to shuffle the bits around. In case of a 1-byte input, we return two bytes where the first 6 bits of the input byte are returned as the first output byte, the last two bits of the input byte are returned as the second byte. In case of a 3 byte input, we follow the same kind of steps to piece different parts of the bytes together to form 4 output bytes each holding 6 bits of information.

Encoding using our Alphabet

Now that we have a mechanism to convert from 8-bit numbers to 6-bit numbers, let's slice the input data into 3-byte chunks and run them through our split function. Once they're split, we can convert each chunk by looking up the 6-bit number in our alphabet:

pub fn encode_using_alphabet<T: Alphabet>(alphabet: &T, data: &[u8]) -> String {
    let encoded = data
        .chunks(3)
        .map(split)
        .flat_map(|chunk| encode_chunk(alphabet, chunk));

    String::from_iter(encoded)
}

The encode_with_alphabet function shown above takes the alphabet to encode against en the original input string to encode. The first step is to slide the input in 3-byte chunks and feeding it into our split function that will return a Vec<u8> of maximum 4-bytes.

Passing each 6-bit number to encode_chunk using flat_map will ensure we're flattening the Vec<char> while we're at it and lastly we consume the iterator by passing it to String::from_iter!

Note: For that last trick (using String::from_iter to build a string from an iterator) to work, we'll need to bring FromIterator trait into scope, see:

use std::iter::FromIterator;

encode_chunk internals

As promised, let's zoom in a bit on the encode_chunk function we're using above. The function signature tells us that this function will take anything that implements the Alphabet trait (which our Classic alphabet does) and a chunk of our bytes (more specifically the Vec<u8> that came rolling out of the split function earlier.

fn encode_chunk<T: Alphabet>(alphabet: &T, chunk: Vec<u8>) -> Vec<char> {
    let mut out = vec![alphabet.get_padding_char(); 4];

    for i in 0..chunk.len() {
        if let Some(chr) = alphabet.get_char_for_index(chunk[i]) {
            out[i] = chr;
        }
    }

    out
}

This function starts off by setting up a Vec<char> that acts as our output buffer, to make our lives easier we're pre filling the buffer with 4 padding characters. Note that we tagged the buffer as mutable so we can overwrite the padding characters with actual data as we're going along.

Inside our loop we take the 6-bit number, look up the character in our alphabet by index and replace the padding symbol with the actual data, if available. At the end of the loop we just return the output buffer.

That's it! That's all there is to do to get your data Base64 encoded! I wont bore you with the tests but for those interested, check em out on the repo

Decoding

Now that we can turn any arbitrary binary blob into a easy-to-transmit Base64 string, we obviously want to retrieve our original data from the encoded blob, otherwise we just built a data corrupter ;)

Let's implement our decoder in a separate module in src/decoder.rs. Much like with our encoder we're going to need our Alphabet trait together with our Classic implementation. Let's bring these into scope, like so:

use crate::alphabet::{Alphabet, Classic};

Let's dive right in and define a decode_using_alpabet function that, much like our encode_using_alphabet function takes the alphabet to do the decoding against and the encoded string to perform the decoding on.

pub fn decode_using_alphabet<T: Alphabet>(alphabet: T, data: &String) -> Result<Vec<u8>, io::Error> {
    // if data is not multiple of four bytes, data is invalid
    if data.chars().count() % 4 != 0 {
        return Err(io::Error::from(io::ErrorKind::InvalidInput))
    }

    let result = data
        .chars()
        .collect::<Vec<char>>()
        .chunks(4)
        .map(|chunk| original(&alphabet, chunk) )
        .flat_map(stitch)
        .collect();

    Ok(result)
}

The first thing we do is run a quick check if the data is indeed a multiple of four bytes, which is one of the characteristics of base64 encoded data. If it does not match these requirements, we'll return an error. When the data is valid, we split the string into its chars and slice it in chunks of 4 char's. Each slice is fed through the original function that will fetch the original char from the alphabet which is flat_map'ed through the stitch function.

Getting the original

fn original<T: Alphabet>(alphabet: &T, chunk: &[char]) -> Vec<u8> {
    chunk
        .iter()
        .filter(|character| *character != &alphabet.get_padding_char())
        .map(|character| { 
            alphabet
                .get_index_for_char(*character)
                .expect("unable to find character in alphabet")
        })
        .collect()
}

The original function takes an Alphabet trait object again and a slice of chars (maximum of 4-bytes). It filters the padding characters and uses the looks up the left-over characters in our alphabet. Returning a Vec of bytes as the original data.

Stitch it back together

Pretty much as a reverse of split we're taking the various bits from two or more bytes and put it back together much like a carefully constructed Lego Millennium Falcon. It takes a Vec of bytes and returns another Vec of bytes, containing a maximum of three 8-bit numbers.

fn stitch(bytes: Vec<u8>) -> Vec<u8> {
    let out = match bytes.len() {
        2 => vec![
            (bytes[0] & 0b00111111) << 2 | bytes[1] >> 4,
            (bytes[1] & 0b00001111) << 4,
        ],

        3 => vec![
            (bytes[0] & 0b00111111) << 2 | bytes[1] >> 4,
            (bytes[1] & 0b00001111) << 4 | bytes[2] >> 2,
            (bytes[2] & 0b00000011) << 6,
        ],

        4 => vec![
            (bytes[0] & 0b00111111) << 2 | bytes[1] >> 4,
            (bytes[1] & 0b00001111) << 4 | bytes[2] >> 2,
            (bytes[2] & 0b00000011) << 6 | bytes[3] & 0b00111111,
        ],

        _ => unreachable!()
    };

    out.into_iter().filter(|&x| x > 0).collect()
}

And this is how that looks in a schematic:

Nice! The encoder and decoder are done! For completeness we obviously also included tests for our decoder ✨✨

Piecing it together

Notice that we wrote all these pieces but our fn main() still has the placeholder println!("Hello, world!"); in it? This is obviously unacceptable, so let's get back to it and crank out a simple CLI that will take a command line argument and read from STDIN 💪

First things first; let's convert our fn main() function so that it will return a Result type. We do this to make our lives easier in terms of error handling, you'll see why in a bit!

fn main() -> Result<(), CLIError> {

}

Notice that we're returning an empty tuple (or unit in Rust) for the success type and a CLIError as the error type, however we have not yet defined our CLIError. Let's do that right now before the compiler yells at us:

use std::fmt;

enum CLIError {
    TooFewArguments,
    InvalidSubcommand(String),
    StdInUnreadable,
    DecodingError,
}

impl std::fmt::Debug for CLIError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match &self {
            Self::TooFewArguments =>
                write!(f, "Not enough arguments provided"),

            Self::InvalidSubcommand(cmd) =>
                write!(f, "Invalid subcommand provided: \"{}\"", cmd),

            Self::StdInUnreadable =>
                write!(f, "Unable to read STDIN"),

            Self::DecodingError =>
                write!(f, "An error occured while decoding the data"),
        }
    }
}

In the code above we define the enum CLIError that describes pretty much everything that can go wrong when calling our binary. For example; for whatever reason reading from the STDIN is not successful or we're calling our executable without providing a valid subcommand. Notice that in the case of the unknown subcommand we're also keeping track of what exactly is passed, giving our users a bit more context around the error.

Notice that next to defining our CLIError we also make it implement the Debug trait. This trait pretty much describes how the variants inside the enum can be turned into a printable string when returned as part of the error type.

The next step is writing a few functions that will make reading from STDIN, encoding and decoding a bit easier:

use std::io::{self, Read};

fn read_stdin() -> Result<String, CLIError> {
    let mut input = String::new();
    io::stdin()
        .read_to_string(&mut input)
        .map_err(|_| CLIError::StdInUnreadable)?;

    Ok(input.trim().to_string())
}

fn encode(input: &String) -> String {
    encoder::encode(input.as_bytes())
}

fn decode(input: &String) -> Result<String, CLIError> {
    let decoded = decoder::decode(input).map_err(|_| CLIError::DecodingError)?;

    let decoded_as_string = std::str::from_utf8(&decoded)
        .map_err(|_| CLIError::DecodingError)?;

    Ok(decoded_as_string.to_owned())
}

Note the read_from_stdin function also returns a Result<String, CLIError>. It will attempt to read from STDIN and write the contents to a string. If this succeeds it will return the Ok variant with the string value, but if this fails, we will map the error to a CLIError::StdInUnreadable error which will be pretty printed in our console.

The next two functions (encode and decode) are pretty much just wrappers around our library functions encoder and decoder that will take in a reference to a string and return a owned string. To ensure we are able to use our encoder and decoder modules, let's link them to the main executable:

mod alphabet;
mod decoder;
mod encoder;

Final stretch! Let's fill in our main() function:

fn main() -> Result<(), CLIError> {
    if std::env::args().count() < 2 {
        return Err(CLIError::TooFewArguments);
    }

    let subcommand = std::env::args()
        .nth(1)
        .ok_or_else(|| CLIError::TooFewArguments)?;

    let input = read_stdin()?;

    let output = match subcommand.as_str() {
        "encode" => Ok(encode(&input)),
        "decode" => Ok(decode(&input)?),
        cmd => Err(CLIError::InvalidSubcommand(cmd.to_string())),
    }?;

    println!("{}", output);

    Ok(())
}

As you can see we can make a functional CLI within just a few lines of pure Rust without pulling in external dependencies. By using the Result<T, E> type and the question mark operator (?) we're essentially short-circuiting the returned Result types only continuing down the happy path, or returning the error as the return value of the containing function in case of an error.

That is it! That is all we need to make a fully functioning Base64 implementation from scratch in Rust and wrap it in a CLI tool. Usage:

# encoding
echo 'fluffy pancakes' | cargo run -- encode
> Zmx1ZmZ5IHBhbmNha2Vz

# and the reverse
echo 'Zmx1ZmZ5IHBhbmNha2Vz' | cargo run -- decode
> fluffy pancakes

Thank you for reading! The finished project can be found on GitHub :)

Originally posted at https://tiemenwaterreus.com/posts/implementing-base64-in-rust/

Huffman coding from scratch with Elixir

Tiemen — Fri, 04 Sep 2020 12:03:18 +0000

Huffman coding is a pretty straight-forward lossless compression algorithm first described in 1992 by David Huffman. It utilizes a binary tree as its base and it's quite an easy to grasp algorithm. In this post we walk through implementing a Huffman coder and decoder from scratch using Elixir ⚗️

How does Huffman work?

In this example we assume the data we are compressing is a piece of text, as text lends itself very well for compression due to repetition of characters.

The algorithm in its core works by building a binary tree based on the frequency of the individual characters. Placing characters with a higher frequency closer to the root of the tree than characters with a lower one.

The Huffman code can be derived by walking the tree until we find the character. Every time we pick the left-child, we write down a 0 and for every right-child a 1. Repeat the process for each character in the text, and voila!

Decoding the text is as simple as starting at the root of the tree and traverse down the left-child for every 0 you encounter and pick the right-child for every 1. Once you hit a character, write it down and start over with the remainder of the bits.

For an excellent explanation on the Huffman Coding algorithm, give this explainer video by Tom Scott a watch!

Let's get to work: Setting up the project

Ok! Let's begin by generating a new Mix project using mix new huffman. cd huffman into the project root and open up the lib/huffman.ex file. This file contains our Huffman module. Replace the contents of the file with a single function declaration encode/1 like so:

defmodule Huffman do
  def encode(text \\ "cheesecake") do
  end
end

This function accepts the text we like to compress and defaults to "cheesecake" because, why not 🤷

Frequency analysis

The first step in Huffman coding is a simple frequency analysis. For each character in the given text, count how many times it is used in the text. This is a rather crucial part of the encoding algorithm as this determines where the characters are placed in the binary tree.

For example; when encoding the word "cheesecake" we can already see that certain characters appear more than others. e is used four times whereas the c appears only twice.

Let's write some code that does the frequency analysis for us. Update our encode/1 function to match the following:

def encode(text \\ "cheesecake") do
  frequencies =
    text
    |> String.graphemes()
    |> Enum.reduce(%{}, fn char, map ->
      Map.update(map, char, 1, fn val -> val + 1 end)
    end)
end

This code above splits the input string into graphemes (individual characters) and stores the count per character in a map using Map.update/4.

Popping into an iex shell and running Huffman.encode now gives us the following output:

%{
  "a" => 1,
  "c" => 2,
  "e" => 4,
  "h" => 1,
  "k" => 1,
  "s" => 1
}

Sorting the characters

Since order is important when building our tree, we need to sort the list of characters by their frequency. Luckily Elixir's Enum module comes to the rescue. Add the following code to our Huffman.encode/1 function:

queue = 
  frequencies
  |> Enum.sort_by(fn {_char, frequency} -> 
    frequency 
  end)

By passing the map with frequencies to Enum.sort_by/2, we sort the map using its values (the frequencies). This outputs:

[
  {"a", 1}, 
  {"h", 1}, 
  {"k", 1}, 
  {"s", 1}, 
  {"c", 2}, 
  {"e", 4}
]

Building the tree

Before we can neatly build a tree, we need to determine which kinds of nodes we have. We have a Leaf node which holds a single character and a Node which contains a left- and a right child. Each child on its own can be another Node or a Leaf.

Let's define two structs to model these types of nodes at the top or our module:

defmodule Node do
  defstruct [:left, :right]
end

defmodule Leaf do
  defstruct [:value]
end

Note: Make sure you define the two structs within our current Huffman module to avoid naming clashes with the built-in Node.

The next step is to iterate over our list of sorted characters and convert them to Leaf nodes. Extend our Huffman.encode/1 function like this:

  queue =
    frequencies
    |> Enum.sort_by(fn {_node, frequency} -> frequency end)
+   |> Enum.map(fn {value, frequency} -> 
+        {
+          %Leaf{value: value}, 
+          frequency
+        }
+   end)

Now that we have an ordered set of Leaf nodes, we can build up the rest of the binary tree. Define a new function to do exactly this:

defp build([{root, _freq}]), do: root

defp build(queue) do
  [{node_a, freq_a} | queue] = queue
  [{node_b, freq_b} | queue] = queue

  new_node = %Node{
    left: node_a,
    right: node_b
  }

  total = freq_a + freq_b

  queue = [{new_node, total}] ++ queue

  queue
  |> Enum.sort_by(fn {_node, frequency} -> frequency end)
  |> build()
end

Since this is a recursive function we need an exit condition, otherwise we are looping forever. In our case we are done building the tree when there is only a single root-node in the queue. The second clause is a bit more beefy, let's break it down:

First thing we do is pop two nodes of the queue by pattern matching the tuple {node, frequency} as the head of the list, and matching the rest of the list again as queue. Doing this twice gives us two nodes and their frequencies we can work with.
The next step is combining these two nodes in a parent Node and tallying up the frequencies so we can prepend it to the queue.
The next step is sorting the queue again to make sure the items with the lowest frequency are at the head of the queue.
The last step is to call build/1 again so this process starts all over again.

Calling our build/1 function at the end of our Huffman.encode/1 function passing the queue of items results in:

%Huffman.Node{  
  left: %Huffman.Leaf{value: "e"},
  right: %Huffman.Node{
    left: %Huffman.Leaf{value: "c"},    
    right: %Huffman.Node{
      left: %Huffman.Node{
        left: %Huffman.Leaf{value: "k"},
        right: %Huffman.Leaf{value: "s"}
      },
      right: %Huffman.Node{
        left: %Huffman.Leaf{value: "a"},
        right: %Huffman.Leaf{value: "h"}
      }
    }
  }
}

The output above shows a tree structure where the character e is placed more towards the root of the tree and the character a is placed more towards the bottom. Each node in our tree is either a Leaf with the actual character or another Node. Drawn out this looks like:

Encoding the text

Now that we have the Huffman tree all setup and ready to go, let's focus on encoding the text using Huffman coding. The process of doing so is quite simple:

Look up each character of the text in our binary tree and keep track of each step while traversing down the tree. Each time we traverse down the left-child, write down a 0 and each time we traverse down the right-child write down a 1. Once we find the character in the tree, the path we wrote down is our Huffman code.

An example

So for example, in our tree above, the letter "c" has the code 10 since at the first node we take the right branch and then the left branch and voila. Similarly for the character "s" the code is 1101 since for the first two nodes, we take the right branch, then the left and lastly the right one again.

Code

First things first, we should be able to look up a character in the binary tree and keep track of its path while doing so.

defp find(tree, character, path \\ <<>>)

defp find(%Leaf{value: value}, character, path) do
  case value do
    ^character -> path
    _ -> nil
  end
end

defp find(%Node{left: left, right: right}, character, path) do
  find(left, character, <<path::bitstring, 0::size(1)>>) ||
    find(right, character, <<path::bitstring, 1::size(1)>>)
end

In the code example above we defined a function with two different clauses and a function header. The function header is just so that we can define a default value for the path which we set to an empty binary.

The first clause executes when passed in a Leaf node. The only thing we need to do is compare its value to the character we are looking for. When they match, return the path, else return nil.

The second clause matches on Nodes and calls find/3 with each child of the node, passing in an updated path. So when recursing on the left-child, we update the path with a 0. The || (or) operator makes sure that either of the two paths is returned.

Now that we can look up a single character in our binary tree, let's iterate over all the characters in the text and replace them with their Huffman code. Add the following function to our Huffman module:

defp convert(text, tree) do
  text
  |> String.graphemes()
  |> Enum.reduce(<<>>, fn character, binary ->
    code = find(tree, character)

    <<binary::bitstring, code::bitstring>>
  end)
end

This function simply breaks the text into graphemes and iterates over each grapheme by calling Enum.reduce/3. Starting off with an empty binary, we can simply append to it for each character we find.

Now wire it all up and call our convert/2 function at the bottom of our Huffman.encode/1 function passing the original text and the tree.

The encode/1 function now looks like:

def encode(text \\ "cheesecake") do
  frequencies =
    text
    |> String.graphemes()
    |> Enum.reduce(%{}, fn char, map ->
      Map.update(map, char, 1, fn val -> val + 1 end)
    end)

  queue =
    frequencies
    |> Enum.sort_by(fn {_node, frequency} -> frequency end)
    |> Enum.map(fn {value, frequency} -> {%Leaf{value: value}, frequency} end)

  tree = build(queue)
  {tree, convert(text, tree)}
end

As you can see it returns a tuple containing the tree and the encoded text. It returns the tree because we need this in the next step to decode the text to its original form again.

Calling Huffman.encode now results in the following:

{
  %Huffman.Node{
   left: %Huffman.Leaf{value: "e"},
   right: %Huffman.Node{
     left: %Huffman.Leaf{value: "c"},
     right: %Huffman.Node{
       left: %Huffman.Node{
         left: %Huffman.Leaf{value: "k"},
         right: %Huffman.Leaf{value: "s"}
       },
       right: %Huffman.Node{
         left: %Huffman.Leaf{value: "a"},
         right: %Huffman.Leaf{value: "h"}
       }
     }
   }
 }, <<188, 213, 216>>}

Where the second element of the tuple (<<188, 213, 216>>) is our compressed data.

Quick size comparison

iex(1)> <<188, 213, 216>> |> bit_size()
24 # variable bit length per char, but max 4 bits in this scenario

iex(2)> "cheesecake" |> bit_size()
80 # 10 chars * 8 bits per char = 80 bits

Using our Huffman module, encoding the string "cheesecake" results in a binary blob of only 24 bits. Each character in our binary tree is reachable in max. four steps, so each character is encoded in 4 bits or less. Using ASCII encoding each character takes 8 bits.

However, in order to decompress the text, we need access to the same tree we used to compress the text. Meaning that if we want to send the compressed data over the wire or store it to disk, we need need to account for additional space for the tree too.

Decoding

Now that we have coded ourselves the ability to encode text using Huffman coding, we also should have a way to decode the data back to its original form.

Decoding the data is quite straight-forward: all we need is our original Huffman tree and the encoded binary blob from the previous steps.

We use the binary blob as some sort of turn-by-turn navigation through our binary tree. From the top of the tree, traverse down the left-child when encountering a 0 in the data and traverse down the right-child when finding a 1.

Repeat this process until we hit a Leaf node. Write down the value of the Leaf and repeat with the remainder of the bits.

Code

First things first, we need a function that can walk the tree following the instructions in the compressed data, until we hit a Leaf node.

defp walk(binary, %Leaf{value: value}), do: {binary, value}

defp walk(<<0::size(1), rest::bitstring>>, %Node{left: left}) do
  walk(rest, left)
end

defp walk(<<1::size(1), rest::bitstring>>, %Node{right: right}) do
  walk(rest, right)
end

In the code above we define a walk/2 function that takes the encoded binary and the tree and walks the tree. For every Node it encounters it looks at the next bit of the data to determine whether it should traverse down the first-child (found a 0) or traverse down the right-child (found a 1).

It keeps doing that until it finds a Leaf node, then it returns the remainder of the data and the character that belongs to that code.

Now that we have a function that can walk to the first available Leaf node following the instructions of the data, we want to call this function recursively as long as there's more binary data available.

Let's define another function:

def decode(tree, data, result \\ [])

def decode(_tree, <<>>, result), 
  do: List.to_string(result)

def decode(tree, data, result) do
  {rest, value} = walk(data, tree)
  decode(tree, rest, result ++ [value])
end

The decode/3 function above has two clauses. The last one basically walks the tree until it finds the first Leaf node, stores its character value in a list (result) and recurses with the remainder of the binary data.

The first clause matches once we have no binary data left to decode. It passes the result to List.to_string/1 concatenating the items in the list together forming a string.

The end result

That's all there is to it! We built ourselves a Huffman Coder and Decoder using ~90 lines of Elixir:

defmodule Huffman do
  defmodule Node do
    defstruct [:left, :right]
  end

  defmodule Leaf do
    defstruct [:value]
  end

  def encode(text \\ "cheesecake") do
    frequencies =
      text
      |> String.graphemes()
      |> Enum.reduce(%{}, fn char, map ->
        Map.update(map, char, 1, fn val -> val + 1 end)
      end)

    queue =
      frequencies
      |> Enum.sort_by(fn {_node, frequency} -> frequency end)
      |> Enum.map(fn {value, frequency} -> {%Leaf{value: value}, frequency} end)

    tree = build(queue)
    {tree, convert(text, tree)}
  end

  def decode(tree, data, result \\ [])

  def decode(_tree, <<>>, result),
    do: List.to_string(result)

  def decode(tree, data, result) do
    {rest, value} = walk(data, tree)
    decode(tree, rest, result ++ [value])
  end

  defp walk(binary, %Leaf{value: value}), do: {binary, value}

  defp walk(<<0::size(1), rest::bitstring>>, %Node{left: left}) do
    walk(rest, left)
  end

  defp walk(<<1::size(1), rest::bitstring>>, %Node{right: right}) do
    walk(rest, right)
  end

  defp build([{root, _freq}]), do: root

  defp build(queue) do
    [{node_a, freq_a} | queue] = queue
    [{node_b, freq_b} | queue] = queue

    new_node = %Node{
      left: node_a,
      right: node_b
    }

    total = freq_a + freq_b

    queue = [{new_node, total}] ++ queue

    queue
    |> Enum.sort_by(fn {_node, frequency} -> frequency end)
    |> build()
  end

  defp find(tree, character, path \\ <<>>)

  defp find(%Leaf{value: value}, character, path) do
    case value do
      ^character -> path
      _ -> nil
    end
  end

  defp find(%Node{left: left, right: right}, character, path) do
    find(left, character, <<path::bitstring, 0::size(1)>>) ||
      find(right, character, <<path::bitstring, 1::size(1)>>)
  end

  defp convert(text, tree) do
    text
    |> String.graphemes()
    |> Enum.reduce(<<>>, fn character, binary ->
      code = find(tree, character)

      <<binary::bitstring, code::bitstring>>
    end)
  end
end

Next steps

There's several improvements we can make to this implementation. For example, when encoding the text and looking up the Huffman code in the tree, we don't have to walk the tree for every character. We can do a full traversal once and keep track of each character and its Huffman code in a map.

Also building up the queue can be improved. We don't have to keep sorting the queue after every insert, rather have a look at a proper priority queue.

For an implementation that also serializes the tree to be written to disk or network, head over to the GitHub repository

Thanks for reading! 🤘

Originally posted at https://tiemenwaterreus.com/posts/compession-and-huffman-coding-with-elixir/

From BitString to Base2 with Elixir

Tiemen — Thu, 02 Jul 2020 23:00:35 +0000

If you ever worked with the BitString type in Elixir you're probably familiar with the <<104, 101, 108, 108, 111>>-like notation. This is basically a compact notation of printing each byte as their decimal notation. Converting them to a string of ones and zeroes is as easy as combining a BitString generator with some functions from the Enum module, and voila:

defmodule Bits do
  def as_string(binary) do
    for(<<x::size(1) <- binary>>, do: "#{x}")
    |> Enum.chunk_every(8)
    |> Enum.join(" ")
  end
end

Calling the function defined above like:

Bits.as_string("Hello, dev.to")
"01001000 01100101 01101100 01101100 01101111 00101100 00100000 01100100 01100101 01110110 00101110 01110100 01101111"

Where every 8 bits are separated with a space for readability, we can clearly see the patterns of the ASCII table, where:

H = 0100 1000
e = 0110 0101
l = 0110 1100
etc.

🙌

originally posted on https://tiemenwaterreus.com/posts/from-bitstring-to-base2-elixir/

Configuring Kitty

Tiemen — Sun, 07 Jun 2020 16:07:58 +0000

I love the Kitty terminal emulator for its speed! Ever since I started doing more work in the terminal, it became painfully clear to me that the standard terminal.app on Mac and even iTerm2 (although an amazing product!) were not cutting it anymore for me in terms of speed.

However, since I started using Kitty, I noticed how used I was to some of the shortcuts that "just work" when using terminal.app and iTerm2. In this short post we'll go over some configuration settings to make Kitty behave more like iTerm2 and have the best of both worlds!

What we'll be configuring

cmd + arrow keys for jumping to beginning or end of the line.
alt + arrow keys for jumping between words.
Only vertical splits by default
Switching between Tabs (Kitty calls them Windows) by using cmd + 1-9 numeric keys
Some visual tweaks

Relevant config

# don't draw extra borders, but fade the inactive text a bit
active_border_color none
inactive_text_alpha 0.6

# tabbar should be at the top
tab_bar_edge top
tab_bar_style separator
tab_separator " ┇"

# open new split (window) with cmd+d retaining the cwd
map cmd+d new_window_with_cwd

# open new tab with cmd+t
map cmd+t new_tab_with_cwd

# new split with default cwd
map cmd+shift+d new_window

# switch between next and previous splits
map cmd+]        next_window
map cmd+[        previous_window

# clear the terminal screen
map cmd+k combine : clear_terminal scrollback active : send_text normal,application \x0c

# jump to beginning and end of word
map alt+left send_text all \x1b\x62
map alt+right send_text all \x1b\x66

# jump to beginning and end of line
map cmd+left send_text all \x01
map cmd+right send_text all \x05

# Map cmd + <num> to corresponding tabs
map cmd+1 goto_tab 1
map cmd+2 goto_tab 2
map cmd+3 goto_tab 3
map cmd+4 goto_tab 4
map cmd+5 goto_tab 5
map cmd+6 goto_tab 6
map cmd+7 goto_tab 7
map cmd+8 goto_tab 8
map cmd+9 goto_tab 9

See the full config in my Dotfiles and see all available configuration options here.

Cheers! 🐈

crosspost from https://tiemenwaterreus.com/posts/configuring-kitty/

Linear Regression with Elixir, Phoenix and LiveView. Part II

Tiemen — Mon, 25 May 2020 18:40:39 +0000

In the previous post we walked through setting up a fairly simple linear regression algorithm that uses the slope-intercept form and gradient descent to fit the best line possible over a list of given datapoints. In this part we will make this interactive using Phoenix LiveView and a SVG element in the browser.

Kicking things off

In the previous post we've scaffolded a Phoenix LiveView application using mix phx.new --live --no-ecto but up until now we only focused on the non-phoenix parts. Let's begin by starting our development server and see what we're setup with out-of-the-box:

Either iex -S mix phx.server or mix phoenix.server will do. I like the former better because it drops us immediately into an IEx session we can use to inspect, validate or just doodle around.

Visiting http://localhost:4000 will greet us with a default Phoenix LiveView page:

Now open your favorite editor and look under lib/linreg_web/live. This is where the LiveView modules and their templates live. Go ahead and add two files to this folder: regression_live.ex and regression_live.html.leex.

Setting up the LiveView module and its template

Now that we have a new module for our logic, go ahead and open the regression_live.ex file to start coding our module.

defmodule LinregWeb.RegressionLive do
  use LinregWeb, :live_view

  @impl true
  def mount(_params, _sesion, socket) do
    {:ok, socket}
  end
end

This is the most barebones version of a LiveView module we can write. It defines a new module called RegressionLive which uses the LiveView parts of our application. Its behaviour specifies only one required function mount/3 to kick things off. It knows, by convention, to render the regression_live.html.leex template.

Now, to actually show something in the browser, we'll need to write some HTML. Open the template file regression_live.html.leex and add some basic HTML:

<h1>Hello, LiveView!</h1>

And lastly, in order to be able to view it, we need to hook the LiveView module up to our router. Locate the router.ex file living in lib/linreg_web/ and find the line where it says:

live "/", PageLive, :index

This line tells Phoenix to mount the LiveView module on the root route ("/"), hook it up to the PageLive module and mark it as the :index action.In other words, if there's a request made to our root route, we'll render the PageLive live module.

We want to change that to our own module and see our friendly greeting:

live "/", RegressionLive, :index

Now refresh our browser and be greeted with our own module:

Collecting datapoints

Now that we have a basic LiveView setup, we can start working on collecting datapoints to let our model learn against. Let's begin by rendering a SVG plane on screen.

Open our live template (regression_live.html.leex) and write the following code:

<svg phx-click="add_point" width="800" height="800"></svg>

This sets up an empty SVG element with a with and height of 800px. Another important thing that we've added here is the phx-click attribute. This is the LiveView magic that will make it interactive! This ties an event listener to this element that will react to click events on the SVG element and will send off an event called add_point.

Let's setup the eventhandler itself. Open up the regression_live.ex module again and write the following function in there:

@impl true
def handle_event("add_point", params, socket) do
  IO.inspect(params, label: "params")
  {:noreply, socket}
end

The function definition above has three parameters. The first one is the event name, followed by the parameters of that event and lastly the socket which holds our state and causes the template to re-render if anything changes.

All this function does is print out the parameters when the "add_point" event comes in. Let's try it out by refreshing the page and clicking anywhere on the SVG element. The terminal running your Phoenix app should now show something along the lines of:

params: %{
  "altKey" => false,
  "ctrlKey" => false,
  "detail" => 1,
  "metaKey" => false,
  "offsetX" => 549,
  "offsetY" => 227,
  "pageX" => 832,
  "pageY" => 367,
  "screenX" => 832,
  "screenY" => 465,
  "shiftKey" => false,
  "x" => 832,
  "y" => 367
}

It's right there in the offsetX and offsetY where we get our coordinates witin the SVG.

Scaling the data

The coordinates that will come in will be between 0 and 800. Our linear regression algorithm works better with smaller numbers. To make this work we'll need to scale our coordinates down to between 0 and 1. I've added a convenience function called map/5 that takes the original value alongside its original scale and maps it to the second given scale. For example:

map(5, 0, 10, 0, 1) # 0.5

I've wrote this function in the module linreg/math.ex so we can use it both in our Live module to scale the coordinates down as well as in our template to scale the coordinates back up to their original.

defmodule Linreg.Math do
  def map(value, in_min, in_max, out_min, out_max) do
    out_min + (out_max - out_min) * ((value - in_min) / (in_max - in_min))
  end
end

Then I imported the module into our lib/linreg_web.ex module under view_helpers/0:

  defp view_helpers do
    quote do
      # Use all HTML functionality (forms, tags, etc)
      use Phoenix.HTML
      #... snip


      alias LinregWeb.Router.Helpers, as: Routes
+     import Linreg.Math, only: [map: 5]
    end
  end

Importing it in our view_helpers will make it available in both our _live modules as well as our .leex templates, which are exactly the places where we'll need them.

Adding points to our training data

Head back to our regression_live.ex module and find the mount/3 function. This function is executed once (upon hitting the route). This is also the place where we can assign an initial state to our socket. Let's use this hook to initialize an empty model and an empty data struct to collect our datapoints in, like so:

def mount(_params, _sesion, socket) do
  socket =
    socket
    |> assign(model: Linreg.Model.new())
    |> assign(data: Linreg.Data.new())

  {:ok, socket}
end

Now in every handler where we have access to the socket, we also have access to this state in the assigns map. For the next step, we need to go back to our handle_event/3 function and add some logic in and around that function:

  def handle_event("add_point", params, socket) do
    {:noreply, add_point(params, socket)}
  end

  defp add_point(%{"offsetX" => x, "offsetY" => y}, socket) do
    data =
      socket.assigns
      |> Map.get(:data)
      |> Data.add_point(map(x, 0, 800, 0, 1), map(y, 0, 800, 1, 0))

    assign(socket, data: data)
  end

In the add_point/2 function we're grabbing the x and y values and assign them to the data struct stored in our socket.

Also note the call to map/5 in there. We're calling it twice since we're scaling both the X and Y axis down. The X axis from 0 - 800 to 0-1 and the Y axis from 0 - 800 to 1 - 0. We flipped the Y axis so that it Y = 0 is on the bottom of the SVG.

Drawing our input

With our RegressionLive module storing inputs, let's adjust the template so it will render all points it has stored. Open up the regression_live.html.leex template and make some edits:

~ <svg phx-click="add_point" width="800" height="800">
+  <%= for {x, y} <- @data.points do %>
+  <circle
+    cx="<%= map(x, 0, 1, 0, 800) %>"
+    cy="<%= map(y, 0, 1, 800, 0) %>"
+    r="5"
+    fill="#24DA5E"
+  />
+  <% end %>
~ </svg>

It will now iterate over all the points in the data struct and passing them through the map/5 function to map the coordinates to 0 - 800 again. It looks like:

Drawing the predicted line

Now that we have a canvas that renders our collected points, let's hook it up to our linear regression algorithm and let it draw its predicted line.

To draw that line, we need to know the Y value for X = 0 to get the starting point, and Y when x = 800 (the width of our canvas), as our end point, to draw a line between those two points. We'll store both those values on the socket too as start_y and end_y:

  def mount(_params, _sesion, socket) do
    socket =
      socket
      |> assign(model: Linreg.Model.new())
      |> assign(data: Linreg.Data.new())
+     |> assign(start_y: 0)
+     |> assign(end_y: 0)

    {:ok, socket}
  end

In our template we can use these values to draw the line:

  <svg phx-click="add_point" width="800" height="800">
    <%= for {x, y} <- @data.points do %>
    <circle
      cx="<%= map(x, 0, 1, 0, 800) %>"
      cy="<%= map(y, 0, 1, 800, 0) %>"
      r="5"
      fill="#24DA5E"
    />
    <% end %>
+  
+  <line
+    x1="0"
+    y1="<%= map(@start_y, 0, 1, 800, 0) %>"
+    x2="800"
+    y2="<%= map(@end_y, 0, 1, 800, 0) %>"
+    stroke-width="1"
+    stroke="#2477DA"
+  />
  </svg>

We've added a line element which takes two X and Y pairs to indicate the start and end points of the line. As you can see these points are passed through our map/5 function as well before using them in the template.

Learning

When adding new points we like our model to run the training adjusting its weights and on its turn adjusting the predicted line. To run the training, add the following two functions to our RegressionLive module:

defp learn(%{assigns: %{data: data, model: model}} = socket) do
  if length(data.points) >= 2 do
    model = Model.train(model, data, learning_rate: 0.1, epochs: 500)
    assign(socket, model: model)
  else
    socket
  end
end

defp update_prediction(%{assigns: %{model: model}} = socket) do
  socket
  |> assign(start_y: Model.predict(model, 0))
  |> assign(end_y: Model.predict(model, 1))
end

The first one: learn/1 will take the socket and pattern match the training data and the model from the socket. Then, only if there's two or more points in the training set, it'll call the Model.train/3 function. In this case we're calling it with a learning rate of 0.1 and we'll train it for 500 epochs, but feel free to play with these numbers and observe the output change.

The other function update_predicton/1 simply takes the socket to pattern match the model out of there, and assigns the start_y and end_y values in the socket based on the updated model's prediction for X = 0 and X = 1.

Now to use these functions, let's revisit our add_point/2 function one last time:

defp add_point(%{"offsetX" => x, "offsetY" => y}, socket) do
  data =
    socket.assigns
    |> Map.get(:data)
    |> Data.add_point(map(x, 0, 800, 0, 1), map(y, 0, 800, 1, 0))

- assign(socket, data: data)
+ socket
+ |> assign(data: data)
+ |> learn()
+ |> update_prediction()
end

Done

And we're done! We've built a linear regression algorithm in Elixir and made it interactive and visual using LiveView!

You can find the full code on GitHub. Feel free to play around with it and make it better! Thanks for reading :)

crosspost from https://tiemenwaterreus.com/posts/linear-regression-elixir-phoenix-liveview-ii/

Linear Regression with Elixir, Phoenix and LiveView. Part I

Tiemen — Sun, 24 May 2020 14:39:36 +0000

Phoenix LiveView has been around for a bit, but with the release of Phoenix 1.5 it became even easier to get started with it in a new Phoenix app! Simply pass the --live flag when generating a new project and off you go! 🚀

In this two part series we're getting our hands dirty with a basic linear regression algorithm that allows the user to click on a plane to add datapoints and the algorithm figure out the best fitting line through these points.

Upgrading to Phoenix 1.5.0

To kick things off, we first need to get up-to-date with our Phoenix version, if you have not already done this. You can do so by running: mix archive.install hex phx_new

If you rather get LiveView to work on Phoenix 1.4.x, just follow the getting started guide.

Setting up the project

Generating a new project that will help us hit the ground running is as simple as: mix phx.new linreg --live --no-ecto.

Note the two flags there:

--no-ecto skips setting up all Ecto related things since we won't be using them in this project.
--live ensures everything is wired up to use LiveView!

Lastly; cd into the linreg folder and kick-off the Phoenix server by running mix phx.server. You are now greeted by the getting started page over at http://localhost:4000. 🎉

Basic model

Now that we have a new Elixir, Phoenix and LiveView project ready to go, we can get cracking on the real stuff!

First things first, let's define a simple model to hold our data and make our predictions with. A simple struct to hold our weights will do! Fire up your favorite editor and create a new file under lib/linreg/. Let’s call it model.ex by lack of a better name and drop in the following code:

defmodule Linreg.Model do
  defstruct m: 0.0, b: 0.0

  alias __MODULE__

  def new do
    %Model{}
  end

  def predict(%Model{m: m, b: b}, x) do
    b + m * x
  end
end

The module starts off pretty basic. It defines a struct to keep track of two values: M and B and define a function to make predictions based off of the model. For convenience I added a factory function that returns a new empty %Model{} struct.

What is training

Without training, our model would always return 0.0. This is because the weights aren't adjusted yet. There's a variety of ways to let the machine learn the correct values for M and B, but basically it all boils down to:

Let the model make a prediction,
Calculate how far it is off (often called error, loss or cost),
Adjust the weights accordingly and repeat. Repeat until the error is acceptably low.

Gather training data

In order to correctly train our model, we need training data. Training data in our case means a set of X and Y value pairs. The model can learn from these values by making a prediction based on X and see how far it is off by looking at the actual Y value.

In the lib/linreg folder, go ahead and make a new file called data.ex and write the following code:

defmodule Linreg.Data do
  defstruct points: []
  alias __MODULE__

  def new do
    %Data{}
  end

  def add_point(%Data{points: points} = data, x, y) do
    %Data{data | points: [{x, y}] ++ points}
  end
end

In this module we define a struct that holds our training data. A list of X and Y coordinates called points and some utility functions to initialize a new %Data{} struct and to add a point to an existing dataset.

Adjusting the weights

Now that we can record training data, we can implement a training function that adjusts the weights of our model. Open lib/linreg/model.ex and write the following function:

def train(%Model{m: m, b: b} = model, %Data{points: points}, opts \\ []) do
  learning_rate = Keyword.get(opts, :learning_rate, 0.01)

  m_error =
    points
    |> Enum.map(fn {x, y} -> x * (predict(model, x) - y) end)
    |> Enum.sum()
    |> Kernel./(length(points))

  b_error =
    points
    |> Enum.map(fn {x, y} -> predict(model, x) - y end)
    |> Enum.sum()
    |> Kernel./(length(points))

  %Model{model | m: m - m_error * learning_rate, b: b - b_error * learning_rate}
end

The train/3 function takes the current model, training data and a list of options. Then for each point in the training set, it will make a prediction of the Y value given its X value and calculate how far it is off.

It will do this for both the M and the B values. Only difference is that, for M, we’re constraining the result by multiplying it with its input X value. Once we have the errors for each datapoint, we take the average.

Once we have the average error of the model, we adjust each weight by subtracting the average corresponding error multiplied by the learning rate.

The learning rate is a value, often between 0 and 1, which determines how quick the machine learns. It ensures that the adjustments to the weights are done in very small steps as to not overshoot the optimum value. This process is called gradient descent and is a very common technique within machine learning algorithms.

Taking it for a spin

That’s pretty much all there is to it! Now let’s take it for a spin and see how it works. Fire up an IEx shell again and let’s make some predictions.

# Initialize new trainings data and a new model
iex> d = Linreg.Data.new
%Linreg.Data{points: []}

iex> m = Linreg.Model.new
%Linreg.Model{b: 0.0, m: 0.0}

# Add some known data to the training set
iex> d = Linreg.Data.add_point(d, 2, 4)
%Linreg.Data{points: [{2, 4}]}

iex> d = Linreg.Data.add_point(d, 6, 12)
%Linreg.Data{points: [{6, 12}, {2, 4}]}

# Train the model
iex> m = Model.train(m, d)
%Linreg.Model{b: 0.08, m: 0.4}

# Predict our first value
iex> Model.predict(m, 5)
2.08

In the example above we’ve created a model and fed it some pretty straight forward trainings data where Y = 2 * X. We trained our model and let it make a prediction for 5. We expect it to predict 10, however it predicts 2 and some change.. We are getting closer, but the error is still pretty high.

What we see here is the learning rate in effect! We take smaller steps so we don’t overshoot our goal, however that also means that simply iterating over the training set once, will not cut it.

In machine learning; iterating over the trainings set once is referred to as one epoch. In most machine learning algorithms, it requires iterating over your data set many times. Each time shaving some points off of the error, each time perfecting the model’s weights a bit more.

Running the training and prediction functions again yield in values a little closer to what we expect.

Multiple epochs

In order to make training for multiple epochs a little easier, let’s revisit the train/3 function one more time and make it iterate over the entire training set multiple times.

def train(%Model{} = model, %Data{points: points}, opts \\ []) do
  learning_rate = Keyword.get(opts, :learning_rate, 0.01)
  epochs = Keyword.get(opts, :epochs, 100)

  for _epoch <- 1..epochs, reduce: model do
    %Model{m: m, b: b} = model ->
      m_error =
        points
        |> Enum.map(fn {x, y} -> x * (predict(model, x) - y) end)
        |> Enum.sum()
        |> Kernel./(length(points))

      b_error =
        points
        |> Enum.map(fn {x, y} -> predict(model, x) - y end)
        |> Enum.sum()
        |> Kernel./(length(points))

      %Model{model | m: m - m_error * learning_rate, b: b - b_error * learning_rate}
  end
end

We made a few changes to the train function. First off: We’re defining an epoch value which will determine how many times we run through the entire training set. Secondly; we wrapped the whole function body in an for comprehension so that we can iterate through the entire training set multiple times, each time adjusting the weights a little bit more.

Note that we’re using a comprehension with the reduce option. This is essentially the same as Enum.reduce/3 but is a little easier on the eyes with larger bodies, but that might just be a matter of taste 😗

More training

Now that we’ve advanced our training function, let’s try it out and see if our predictions will get a little closer this time! Fire up the IEx again (iex -S mix) and run:

iex> d = Linreg.Data.add_point(d, 2, 4)
%Linreg.Data{points: [{2, 4}]}

iex> d = Linreg.Data.add_point(d, 8, 16)
%Linreg.Data{points: [{8, 16}, {2, 4}]}

iex> m = Linreg.Model.train(m, d)
%Linreg.Model{b: 0.22374565348607184, m: 1.966843594782793}

iex> Linreg.Model.predict(m, 5)
10.057963627400037

Hooray! We trained our model the formula Y = 2 * X + 0. More or less. As you can see the values for M and B are still a bit off, but given enough training, these values will approach the correct values more and more.

I’m saying approach here; they will never exactly be 2 and 0. This is mainly due to the learning rate, but floating point arithmetic is also to blame here.

Try for yourself

The previous example is using a learning rate of 0.01 and trains for 100 epochs, these values are overridable in the options and will yield different results. Simply by calling our training function with the options list:

iex> m = Model.train(m, d, learning_rate: 0.1, epochs: 500)

I’ll leave it as an exercise to the reader to play a bit with these values and see what happens.

Closing words

That’s it for this post! We built a machine learning model that can perform linear regressions and trained it using gradient descent in Elixir.

In the next part we’ll look at how we can make this an interactive example using Phoenix Liveview where clicking on a SVG plane will generate training data and let the model predict the best fitting line through those points.

Crosspost from https://tiemenwaterreus.com/posts/linear-regression-elixir-phoenix-liveview-i/

Deleting ranges of docker images using filters

Tiemen — Sun, 08 Sep 2019 21:02:28 +0000

Purging ranges of stale Docker Images using filters

If the output of docker images spans too many lines and you want to tidy it up, but you think docker system prune is like using C4 to open a can of tuna, maybe take docker images's -f flag for a spin!

docker images -f utilises the filter option and it lets you specify some extra search options to select exactly the images you're interested in!

Filter Options

Currently Docker supports a list of filter options, but in this write-up we're only focussing on the before and since filters - go for a full overview of the available filter options to the Docker Docs on Filtering

-f since={image id}
The filter option since takes an image ID and selects all the images that are newer than the given image.

-f before={image id}
Much like since, this tag selects all the images that are older than the given image id.

And to select a whole range of Docker Images, simply stick 'em together!

Example

Enough talking; show me the money! So - imagine the output of docker images looks like the following:

REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
hippo-fe            latest              ec8ec381807d        55 minutes ago      455MB
hippo-backend_api   latest              88a08f954c9f        4 days ago          47.4MB
<none>              <none>              66ee4e399b4a        4 days ago          423MB
<none>              <none>              098006369e17        4 days ago          449MB
<none>              <none>              7010975558a2        4 days ago          449MB
<none>              <none>              75ecd4cee8ef        4 days ago          47.4MB
<none>              <none>              d3942b2482a2        4 days ago          449MB
<none>              <none>              88676747d621        4 days ago          449MB
<none>              <none>              eb522755627b        4 days ago          445MB
<none>              <none>              d62380cf625f        5 days ago          86.3MB
<none>              <none>              21bce955c85b        5 days ago          474MB
spacevim/spacevim   latest              a6b4bb27c4e9        2 weeks ago         1.36GB
<none>              <none>              abf507ccc201        2 weeks ago         106MB
<none>              <none>              79a409b99ca5        2 weeks ago         530MB
<none>              <none>              5fd5b5859b37        3 weeks ago         106MB
<none>              <none>              d93260d7abc3        3 weeks ago         530MB
node                10.16.3-alpine      b95baba1cfdb        3 weeks ago         76.4MB
<none>              <none>              2c62a47471d1        4 weeks ago         106MB
<none>              <none>              3de57027cc18        4 weeks ago         523MB
elixir              1.9.1-alpine        33a0cf122cf7        5 weeks ago         87.6MB
<none>              <none>              e5196ef97445        6 weeks ago         104MB
elixir              1.8.1-alpine        447a8dff23a8        5 months ago        91.1MB
alpine              3.9                 5cb3aa00f899        6 months ago        5.53MB

That's quite the list! Let's say we're no longer interested in the images below the image tagged as hippo-backend_api with image id 88a08f954c9f and the images above spacevim/spacevim with image id a6b4bb27c4e9, how would we go about that using the filters described above?

$ docker images -f before=88a08f954c9f

Would give us all the images that are created before the hippo-backend_api one. Next step would be to select all the Docker images up-to a given image in history:

$ docker images -f before=88a08f954c9f -f since=a6b4bb27c4e9

Gives us all the images in a given range:

<none>              <none>              66ee4e399b4a        4 days ago          423MB
<none>              <none>              098006369e17        4 days ago          449MB
<none>              <none>              7010975558a2        4 days ago          449MB
<none>              <none>              75ecd4cee8ef        4 days ago          47.4MB
<none>              <none>              d3942b2482a2        4 days ago          449MB
<none>              <none>              88676747d621        4 days ago          449MB
<none>              <none>              eb522755627b        4 days ago          445MB
<none>              <none>              d62380cf625f        5 days ago          86.3MB
<none>              <none>              21bce955c85b        5 days ago          474MB

As you can see we're now only given the images in the selected range!

Soo - all we have to do now is tag on the -q flag to solely get a list of image ID's and pipe it into xargs to use them as arguments in the docker rmi -f command...

$ docker images -f before=a6b4bb27c4e9 -f since=88a08f954c9f -q | xargs docker rmi -f

... and voila! If we then run the docker images command again, we'll see that the given range has been deleted:

REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
hippo-fe            latest              ec8ec381807d        2 hours ago         455MB
hippo-backend_api   latest              88a08f954c9f        4 days ago          47.4MB
spacevim/spacevim   latest              a6b4bb27c4e9        2 weeks ago         1.36GB
<none>              <none>              abf507ccc201        2 weeks ago         106MB
<none>              <none>              79a409b99ca5        2 weeks ago         530MB
<none>              <none>              5fd5b5859b37        3 weeks ago         106MB
<none>              <none>              d93260d7abc3        3 weeks ago         530MB
node                10.16.3-alpine      b95baba1cfdb        3 weeks ago         76.4MB
<none>              <none>              2c62a47471d1        4 weeks ago         106MB
<none>              <none>              3de57027cc18        4 weeks ago         523MB
elixir              1.9.1-alpine        33a0cf122cf7        5 weeks ago         87.6MB
<none>              <none>              e5196ef97445        6 weeks ago         104MB
elixir              1.8.1-alpine        447a8dff23a8        5 months ago        91.1MB
alpine              3.9                 5cb3aa00f899        6 months ago        5.53MB

🙌