DEV Community: Leo Pfeiffer

Topological Sort with Kahn's Algorithm

Leo Pfeiffer — Thu, 21 Jul 2022 16:20:30 +0000

On a recent project, we were working on a spreadsheet-like tool where users could cross-reference different rows in formula, just like in Excel. We ran into the question of how to order the evaluation of the rows such that the dependencies do not cause any conflict.

For example, imagine we have three rows:

Row id	Formula	Rendered values
`row1`	`manual input`	1, 2, 3
`row2`	`row3` * 2	6, 8, 6
`row3`	`row1` + 1	2, 3, 4

row1 can be rendered directly, as its formula does not depend on any other rows. row2 however, references row3. row3 references row1. Thus in order to render row2, we first need to render row3.

It turns out, this is quite a common problem, for example in resolving the import order of different modules in a project.

We can solve these types of problems using topological sorting, which takes a DAG (directed acyclical graph) and orders its nodes in a way that for every edge x -> y, x comes before y in the ordering.

Kahn's algorithm is one algorithm that can establish this topological order.

Kahn's Algorithm: Theory

The idea behind Kahn's algorithm is simple:

Put all nodes that have no dependencies in your order
Remove all occurrences of those nodes from the dependencies of all remaining nodes. If there are no cycles, this will give you new nodes without dependencies.
Repeat until there are no more nodes left.

For example:

Node	Depends on
`a`	`b`, `c`
`b`	`d`
`c`	`d`
`d`	-

Here's the dependency graph (where x -> y means that x depends on y.

Thus:

d has no dependencies. Put it in the order.
Order = [d]
Remove occurrences of d from the other dependencies. d occurs in the dependencies of b, c. Thus, after removing d from those dependencies, neither b nor c have any dependencies.

b and c have no dependencies. Put then in the order.
Order = [d, b, c]
Remove occurrences of b and c from the other dependencies. Both b and c occur in the dependencies of a. Thus, after removing b and c from those dependencies, a has no more dependencies.

a has no dependencies. Put it in the order. Order = [d, b, c, a]

No more nodes left. Done. Final order = [d, b, c, a]

Kahn's Algorithm: Implementation

For our implementation we assume as input a dictionary where the keys are the node names and the values are a list of all nodes that the depend on the key.

For example, if nodes B and C depend on A, then on entry in the dictionary would be A: [B, C].

Translating the theory from the previous section into Python code, a possible implementation looks like this:



def topological_sort(nodes: dict[str, list[str]]) -> list[str]:
    """
    Topological sort for a network of nodes

        nodes = {"A": ["B", "C"], "B": [], "C": ["B"]}
        topological_sort(nodes)
        # ["A", "C", "B"]

    :param nodes: Nodes of the network
    :return: nodes in topological order
    """

    # Calculate the indegree for each node
    indegrees = {k: 0 for k in nodes.keys()}
    for name, dependencies in nodes.items():
        for dependency in dependencies:
            indegrees[dependency] += 1

    # Place all elements with indegree 0 in queue
    queue = [k for k in nodes.keys() if indegrees[k] == 0]

    final_order = []

    # Continue until all nodes have been dealt with
    while len(queue) > 0:

        # node of current iteration is the first one from the queue
        curr = queue.pop(0)
        final_order.append(curr)

        # remove the current node from other dependencies
        for dependency in nodes[curr]:
            indegrees[dependency] -= 1

            if indegrees[dependency] == 0:
                queue.append(dependency)

    # check for circular dependencies
    if len(final_order) != len(nodes):
        raise Exception("Circular dependency found.")

    return final_order

Let's try this with a slightly more evolved network:

The corresponding input looks like this:



nodes = {
    "A": ["B", "C"],
    "B": ["C", "D"],
    "C": ["F"],
    "D": ["F"],
    "E": ["F"],
    "F": []
}

If we run this we get the following order:



order = topological_sort(nodes)
print(order)

# ['A', 'E', 'B', 'C', 'D', 'F']

Take another look at the graph and convince yourself that that's indeed a correct order that avoids dependency clashes!

Pomodoro Timer for Terminal

Leo Pfeiffer — Mon, 09 May 2022 13:26:35 +0000

The Pomodoro Technique is one of the most popular productivity / time management techniques around.

As programmers, we spend a lot of time in the terminal - and so I decided to build a super simple Pomodoro timer for the terminal.

⬇️ Get it here.

The timer is implemented as a simple shell script, so you can simply source it to use the pomodoro command.



source pomodoro.sh

To start the timer, run:



pomodoro

A pomodoro consists of four work intervals with intermediate breaks:

Work (25 min) - Short Break (5 min)
Work (25 min) - Short Break (5 min)
Work (25 min) - Short Break (5 min)
Work (25 min) - Long Break (25 min)

You can customize the lengths of the work and break intervals.

For example, a work interval of 10 min (600s) with a 1 min (60s) short break and 2 min (120s) long break could be set like this:



pomodoro -w 600 -s 60 -l 120

Beyond the countdown visible in the terminal, you will also get a notification whenever you start a work or break interval. (Notifications are only supported on Mac OS - sorry).

You can turn off the notifications if you want:



pomodoro --quiet

Happy working!

⬇️ You can get the script here.

Insights into your git commits: Git Commit Analyzer

Leo Pfeiffer — Sun, 08 May 2022 13:56:40 +0000

I love analytics and I love git - so I built a git commit analyzer 🙌

The web app works with your local git repository and also integrates with GitHub.

Try it out here or check out the repository on GitHub.

Overview

The Git Commit Analyzer reads your git log, parses it into its components and then allows you to explore it with a number of neat visualizations.

You can also choose to import a project directly from GitHub.

Implementation

If you're interested in how I implemented the web app, hopefully this section gives some insight.

From the landing page of the web app, the user can either choose to upload a git log from a local repository or continue with the GitHub integration. In each case, the data is fetched, validated, and the user can proceed to the dashboard. On the dashboard, the user can create custom visualizations for the repository.

Technologies

The web app is implemented using Vue.js and JavaScript. I'm using Bulma as a pure CSS framework. The web app is deployed on the free tier of Netlify. I used Jest and Vue Test Utils for unit testing the implementation. The visualizations of the dashboard are implemented with Vue Plotly.

Setting up an OAuth workflow can be somewhat tedious. Luckily, Pizzly offers an amazingly simple way to take care of this. Pizzly provides a proxy server for over 80 OAuth integrations and you can deploy your own instance for free on Heroku (as I did).

To summarize:

JavaScript
Vue.js as a web framework
Vue Test Utils for testing
Vue Plotly for visualizations
Bulma as a CSS framework
Pizzly to handle GitHub OAuth
Netlify for deployment

Git log parsing

The raw git log file is split into individual commits using regular expressions and converted into Commit objects, which look something like this:



class Commit:
  hash: String
  authorName: String
  authorMail: String
  timestamp: Date
  message: String
  nodes: Array[Node]

class Node:
  path: String
  additions: Integer
  deletions: Integer

If the git log is imported from GitHub, the JSON history is converted into the Commit objects in a similar way.

GitHub integration

Importing the commit history from GitHub is generally pretty straightforward with the official GitHub API. However, setting up a full OAuth workflow in order to authenticate yourself to the GitHub API can make the process more laborious.

During the development, I stumbled over Pizzly, an open source service that acts as a proxy service to over 80 commonly used APIs, among them GitHub. You can deploy your own Pizzly instance to Heroku for free and use it to manage all your API calls.

The OAuth workflow reduces to a few lines of code:



import Pizzly from "pizzly-js";

// get environment variables
const HOST = process.env.VUE_APP_PIZZLY_HOST
const SECRET = process.env.VUE_APP_PIZZLY_SECRET_KEY

// create pizzly instance and integration instance
const pizzly = new Pizzly({host: HOST, publishableKey: SECRET})
const githubApi = pizzly.integration('github')

/**
* Perform the OAuth workflow using the GitHub API.
* @return authId
**/
const authenticate = function() {
    return githubApi.connect()
}

Call the authenticate function, and Pizzly will take care of your authentication.

To give an example, you can get the names of the repositories from a certain page of the API, you can call the following function. You also need to pass the authId, returned during the authentication workflow.



/**
* Get the names of the repositories of a given page of the GitHub API.
* @param page (Number) page to get
* @param perPage (Number) entries per page
* @param authId (String) authentication ID from the auth workflow
* @return (Array) repository names 
**/
const getRepoPage = function(page, perPage, authId) {
    return githubApi
        .auth(authId)
        .get('/user/repos', {
            headers: {"Content-Type": "application/vnd.github.v3+json"},
            query: {"page": page, "per_page": perPage, "visibility": "all"}
        })
        .then(res => res.json())
        .then(jsn => jsn.map(e => e.name))
}

Pretty neat, don't you think?

Data wrangling

When building the dashboard, I wanted to give the user as much freedom as possible to pick and chose which metrics to visualize. In terms of a simple 2D plot, this means the user should be able to choose which variable lives on each axis as well as if the data should be grouped by a third variable.

Implementing this was lots of fun! Using the parsed git log containing the Commit objects (as described above), I defined a number of functions that can be applied to an array of commits.

These functions fall into two categories: key and value functions.

Key functions take a Commit object and extract a certain key value (e.g. the hash, date, author etc.). Value functions take an array of Commit objects and summarize them by a single value (e.g. number of commits, additions, deletions).

With this setup, we can take an array of Commit objects, and aggregate it by a certain key function using a value function. For example, we could get the number of commits (value) per author (key).

Consider the following LogHandler class, which defines aggregateBy and groupBy as well as the value function vfNumCommits and the key function kfAuthorName.



class LogHandler {
    constructor(gitlog) {
        this.data = [...gitlog.log]
    }

    // Key function for name of author
    static kfAuthorName(obj) {
        return obj.authorName
    }

    // Value function for number of commits
    static vfNumCommits(array) {
        return array.length
    }

    /**
     * Group by a key function.
     * @param keyFunc: function to get the key per commit
     * */
    groupBy(keyFunc) {
        return this.data.reduce((agg, next) => {
            const curKeyValue = keyFunc(next)
            curKeyValue in agg ? agg[curKeyValue].push(next) : agg[curKeyValue] = [next]
            return agg
        }, {})
    }

    /**
     * Aggregator for top level keys of the Gitlog object.
     * @param keyFunc: function to get the key per commit
     * @param valueFunc: function to aggregate by
     * */
    aggregateBy(keyFunc, valueFunc) {
        const grouped = this.groupBy(keyFunc)
        Object.keys(grouped).forEach((k) => {
            grouped[k] = {
                value: valueFunc(grouped[k]),
            }
        })
        return grouped
    }
}

If we instantiate LogHandler with our git log, we can call aggregateBy(LogHandler.kfAuthorName, LogHandler.vfNumCommits) we would get an object containing the numbers of commits per author, like this:



{
  "Alice" : {"value" : 42},
  "Bob" : {"value" : 13}
}

Now what if we wanted to further group these results by year, i.e. number of commits for each author for each year.

We can define another method in the LogHandler class, called groupAggregateBy and a key function for the year kfYear.



static kfYear(obj) {
    return obj.timestamp.getFullYear()
}

groupAggregateBy(groupFunc, keyFunc, valueFunc) {
    const grouped = this.data.reduce((agg, next) => {
        const curKey = [keyFunc(next), groupFunc(next)]
        curKey in agg ? agg[curKey].push(next) : agg[curKey] = [next]
        return agg
    }, {})
    Object.keys(grouped).forEach((k) => {
        grouped[k] = {
            key: keyFunc(grouped[k][0]),
            group: groupFunc(grouped[k][0]),
            value: valueFunc(grouped[k])
        }
    })
    return grouped
}

The groupAggregateBy takes an additional argument, groupFunc which can be any key function. Each key created by applying the key function to the array of Commit objects is one group.

Continuing with our example, we would call groupAggregateBy(LogHandler.kfYear, LogHandler.kfAuthorName, LogHandler.vfNumCommits), which would result in the following object:



{
  "[2022,Alice]" : {"key": "Alice", "group": 2022, "value": 2}
  "[2021,Alice]" : {"key": "Alice", "group": 2021, "value": 30}
  "[2020,Alice]" : {"key": "Alice", "group": 2020, "value": 10}
  "[2022,Bob]" : {"key": "Bob", "group": 2022, "value": 10}
  "[2019,Bob]" : {"key": "Bob", "group": 2019, "value": 3}
}

Now, we simply need to implement a key and a value function for any key and value we want the user to have access to.

On the dashboard, the user can then select any of the defined functions, which are then applied to the git log resulting in the transformed data set being used as input to the visualization.

Conclusion and improvements

I had a lot of fun implementing the git commit analyzer and I love the insight I get from it.

There are a number of issues that can still be improved:

Parsing file extensions: this would be a great enhancement to add information about languages used in the repo
Branch info: right now, branch information is ignored by the tool
Session persistence: right now, visualizations are lost during page refreshes
General UX improvements: I've noticed that users who visit the dashboard for the first time don't intuitively realize all the functions

Nonetheless, I hope the tool is fun to use and you can find new insights into your commit history!

Please feel free to reach out with feedback, comments, or ideas for improvements!

Screenshots

Writing an equation parser in Scala

Leo Pfeiffer — Wed, 27 Apr 2022 09:19:48 +0000

I recently started diving into Scala and as a first learning project, I decided to build a functional mathematical expression tokenizer, parser and evaluator. In this post I will walk through the implementation and some of the core algorithms. Feel free to reach out with any questions!

You can find the final project here.

Overview

The goal of the project is to be able to pass a mathematical expression (e.g. 1 + 2 * 3 - 4) to the program and get the value of the expression back (i.e. 3).

Internally, this involves three steps. First, the raw string expression needs to be tokenized into a well-defined format as preparation for further processing. Second, a parser reads the tokens and parses them into a mathematical expression following the usual precedence rules. Lastly, the expression is evaluated by combining its components.

Allowed operations

Let's quickly define what the final program should be able to do.

Numbers should be specified as integers (e.g. 42) or decimals (e.g. 1.23) and should evaluated as doubles.

Negative numbers should be evaluated correctly, but should always be wrapped in parentheses (i.e. write (-42)+2 instead of -42+2).

The following operations should be allowed:

+    Addition
-    Difference
*    Multiplication
/    Division
^    Power

Left ( and right ) parentheses should also be allowed and the resulting precedence should be taken into account.

Defining Expressions

We start by defining the expressions. In total, we will need to define the expressions Number, Difference, Product, Division, and Power.

In fact, each component of an expression is itself an expression. For example, 1 + 2 consists of two expressions of type Number, namely Number(1) and Number(2), as well as a Sum operator.

Moreover, every expression is either of type Number (which wraps a double) or Operator (which has a left and a right expression). Continuing with the example from above, the Sum operator has the left expression Number(1) and the right expression Number(2).

Lastly, we differentiate between regular operators and Commutative operators. A commutative operator does not differentiate between left and right, as the order doesn't matter. For example, x+y always equals y+x (commutative) but x-y does not necessarily equal y-x.

With that in mind, we can define the Expression trait and the Operator trait, which extends Expression.

/** Represents arithmetic expression. */
trait Expression

/** Arithmetic operator */
trait Operator extends Expression {
    val left: Expression
    val right: Expression
}

As laid out, a Commutative expression is simply an Operator that doesn't differentiate between left and right. We can achieve this behavior by extending Operator and overriding the equals def and hashCode def accordingly.

/** 
 * Represents operators whose left and right side are commutative,
 * i.e. the order of the LHS and RHS expression does not matter.
 * */
trait Commutative extends Operator {
    def canEqual(a: Any) = a.isInstanceOf[Commutative]

    override def equals(that: Any): Boolean =
        that match {
            case that: Commutative => {
                that.canEqual(this) &&
                ((this.left == that.left && this.right == that.right) ||
                    (this.left == that.right && this.right == that.left))
            }
            case _ => false
        }

    override def hashCode: Int = {
        val prime = 31
        prime + left.hashCode * right.hashCode
    }
}

The actual expression types can now be implemented as case classes that extend any of the Expression traits.

case class Number(n: Double) extends Expression {
    def value = n
}

case class Sum(left: Expression, right: Expression) extends Commutative
case class Difference(left: Expression, right: Expression) extends Operator
case class Product(left: Expression, right: Expression) extends Commutative
case class Division(left: Expression, right: Expression) extends Operator
case class Power(left: Expression, right: Expression) extends Operator

Evaluating these expressions is now almost trivial. Any operator can be evaluated by simply applying the underlying mathematical operation to the left and right sides (which in turn need to be evaluated). For Number expressions, we simply return the underlying value. Scala's pattern matching comes in handy here.

/**
 * Evaluate an expression.
 * @param expression: expression to evaluate
 * @return value of the expression
 * */
def evaluate(expression: Expression): Double = expression match
    case Number(n) => n
    case Sum(left, right) => evaluate(left) + evaluate(right)
    case Difference(left, right) => evaluate(left) - evaluate(right)
    case Product(left, right) => evaluate(left) * evaluate(right)
    case Division(left, right) => evaluate(left) / evaluate(right)
    case Power(left, right) => scala.math.pow(evaluate(left), evaluate(right))

That's the expression implementation done. If we wanted to represent the example 1 + 2 * 3 - 4 from earlier using our implementation, it would give us

Difference(Sum(Number(1), Product(Number(2), Number(3))), Number(4))

We can also express these expressions as a syntax tree. For example, parsing the equation 3+4*2/(1-5)^2^3 creates the following syntax tree.

The final version of Expression.scala can be found here.

Tokenizer

Next, we will take care of tokenizing the raw string expression.

The tokenizer splits the raw expression into its components and encodes each component as a token. The token closely follow the Expression classes defined earlier, however, we will also have to handle parentheses here.

We start by defining a simple abstract class Token and an abstract subclass OperatorToken, which represents operators. Each operator has a precedence (lower precedence operators are evaluated first).

/** Token of an expression */
abstract class Token()

/** Token representing an operator */
abstract class OperatorToken() extends Token {
    /** Precedence value of the operator */
    def precedence: Int
}

Next, we have to handle how the different operators associate. A left associative operator evaluates from left to right, while a right associative takes the opposite direction.

This is implemented using the following three traits.

trait Associates

/** Associates left */
trait Left extends Associates

/** Associates right */
trait Right extends Associates

This gives us all the components to define our actual tokens. NumberToken, LeftParensToken, and RightParensToken extend Token directly. All others are OperatorToken subclasses an also extend an Associates trait. Only the power token (^) associates right, all others associate left.

/** Token representing sum */
case class SumToken() extends OperatorToken, Left {
    def precedence = 2
}

/** Token representing difference */
case class DifferenceToken() extends OperatorToken, Left {
    def precedence = 2
}

/** Token representing product */
case class ProductToken() extends OperatorToken, Left {
    def precedence = 3
}

/** Token representing division */
case class DivisionToken() extends OperatorToken, Left {
    def precedence = 3
}

/** Token representing power */
case class PowerToken() extends OperatorToken, Right {
    def precedence = 4
}

/** Token representing number */
case class NumberToken(n: Double) extends Token

/** Token representing left parenthesis */
case class LeftParensToken() extends Token

/** Token representing right parenthesis */
case class RightParensToken() extends Token

What remains is the function to actually convert a raw string expression into a list of tokens.

The function will have the following signature (we will fill in the body step by step).

/** 
 * Tokenize string expression.
 * 
 * Tokenize a string representation of an arithmentic expression. 
 * 
 * @param rawExpression: String representation of expression.
 * @return List of tokens of the expression.
 * */
def tokenize(rawExpression: String): List[Token] = ???

In the method body, we will have to add the following.

Splitting the raw string expression

    val splitted = rawExpression
        .filterNot(_.isWhitespace)
        .split("(?=[)(+/*-])|(?<=[)(+/*-])|(?=[\\^])|(?<=[\\^])")
        .map(_.trim)

This takes the raw string, splits it into its parts using a regular expression, and removes any whitespace.

Tokenizing string components

The val splitted now contains a list of strings that can be converted into tokens. For that, we define the tokenizeOne function and map it to each element of splitted.

// Regex representing a double.
val numPattern = "(\\-?\\d*\\.?\\d+)".r

/**
 * Tokenize a single string.
 * 
 * @param x: String to tokenize
 * @returns Corresponding token
 * */
def tokenizeOne(x: String) = x match {
    case "+" => SumToken()
    case "-" => DifferenceToken()
    case "*" => ProductToken()
    case "/" => DivisionToken()
    case "^" => PowerToken()
    case "(" => LeftParensToken()
    case ")" => RightParensToken()
    case numPattern(c: String) => NumberToken(c.toDouble)
    case _ => throw RuntimeException(s""""$x is not legal""")
}

// tokenize each element
val tokenized = splitted.map(tokenizeOne).toList

Handling negative numbers

At this stage, the tokenizer can handle all (valid) input and convert it into a list of tokens. However, we would run into problems later, if we parsed negative numbers (e.g. 1+(-1)) since the - is converted into a DifferenceToken, yet there is not NumberToken to its left.

To handle this, we will walk through the list of tokens, and if we find a (- sequence in the list, we insert a NumberToken(0) between the ( and the -, producing a valid negative number.

The algorithm could be implemented more concisely with a loop, however, I wanted to find a functional implementation. Thus, I came up with the following:

/**
 * Handle negative numbers.
 * 
 * Negative numbers are prefixed with a zero
 * e.g. (-1) -> (0-1)
 * to maintian both a left and right expression of the Difference operator.
 * 
 * @param tokens: list of tokens to handle
 * @returns tokens with inserted zeros
 * */
def handleNegative(tokens: List[Token]): List[Token] = 

    /**
     * Insert prefix zero.
     * 
     * If the token list starts with "(, -" insert a zero.
     * 
     * @param tokens: list of params to check
     * @return token list with inserted zero
     * */
    def insert(tokens: List[Token]): List[Token] = tokens match {
        case a :: b :: rest => {
            a match {
                case _a: LeftParensToken => {
                    b match {
                        case _b: DifferenceToken => _a :: NumberToken(0) :: Nil
                        case _ => _a :: Nil
                    }
                }
                case _ => a :: Nil
            }
        }
        case a :: Nil => a :: Nil
        case _ => Nil
    }

    /** Recursively insert zeros where necessary */ 
    def recur(tokens: List[Token]): List[Token] =
        if tokens.isEmpty then Nil
        else if tokens.tail.isEmpty then tokens
        else insert(tokens) ++ recur(tokens.tail)

    recur(tokens)

The algorithm recursively explores the list. If the list starts with the defined pattern of (-, it returns (0- plus the tail of the list. Else, it simply returns the tail of the list.

In the body of tokenize we now simply call

// handle negative numbers
handleNegative(tokenized)

as the last line.

The final Tokenizer.scala file can be found here

Parser

In this last step, we can finally write the actual parser, that converts the token list into an expression that can be evaluated.

The parser will work in two steps.

Convert the token list from infix to postfix notation
Parse the postfix token list into an expression

Converting infix to postfix

When we input the expression as a raw string, we use what is called infix notation. While this makes sense for human readability, the parsing algorithm of the implementation requires postfix notation.

To given an example, the infix expression (5-6) * 7 expressed in postfix notation is * -5 6 7.

The algorithm to do this conversion used here is called Shunting Yard algorithm. My implementation is based on the pseudo code provided on Wikipedia, but implemented recursively. I won't go into much detail as to how the algorithm works as I think the Wikipedia article does a pretty good job at explaining that.

Let's start by defining the core recursive procedure of the function.

/**
 * Shunting Yard algorithm.
 * 
 * Converts a list of tokens from infix to postfix notation.
 * https://en.wikipedia.org/wiki/Shunting_yard_algorithm
 * 
 * @param tokens: List of tokens in infix notation
 * @return list of tokens in postfix notation
 * */
def shuntingYard(tokens: List[Token]): List[Token] =

    // todo: we will fill in the helper functions later

    /**
     * Recursive method of shunting yard.
     * 
     * @param stack: Stack of tokens left to place
     * @param postfix: Tokens converted to postfix notation
     * @param tokens: Tokens in infix notation
     * @return tokens in postfix notation
     * */
    @tailrec
    def recur(stack: Stack[Token], postfix: List[Token], tokens: List[Token]): List[Token] = 
        tokens match {
            case Nil => postfix ++ stack
            case t :: rest => {
                t match {
                    case n: NumberToken => recur(stack, postfix :+ n, rest)
                    case o: OperatorToken => {
                        if (stack.isEmpty) then recur(stack.push(o), postfix, rest)
                        else {
                            val updated = operatorUpdate(postfix, stack, o)
                            recur(updated._1, updated._2, rest)
                        }
                    }
                    case l: LeftParensToken => recur(stack.push(l), postfix, rest)
                    case r: RightParensToken => {
                        val updated = rightParensUpdate(postfix, stack)
                        recur(updated._1, updated._2, rest)
                    }
                }
            }
        }

    recur(new Stack[Token], List(), tokens)

Essentially, this procedure recursively walks over the token list and depending on the token it encounters, it either places the token on a stack or combines the token with the last token from the step.

Notice that we're still missing some helper functions that were crated to make the core procedure more readable. Insert the following helper functions into shuntingYard before the recur function.

/** Helper method to determine if token if left associative. */
def isLeftAssoc(t: Token): Boolean = t match {
    case a: Left => true
    case _ => false
}

/** Helper method to determine if token if right associative. */
def isRightAssoc(t: Token): Boolean = t match {
    case a: Right => true
    case _ => false
}

/** Helper method to determine if token if left parenthesis. */
def isLeftParens(t: Token): Boolean = t match {
    case a: LeftParensToken => true
    case _ => false
}

/** Helper method to update postfix and stack during operator parsing. */
@tailrec
def operatorUpdate(postfix: List[Token], stack: Stack[Token], o: OperatorToken): (Stack[Token], List[Token]) =
    def matchCond(o: OperatorToken, stack: Stack[Token]): Boolean = stack.head match {
        case o2: OperatorToken => {
            (isLeftAssoc(o) && (o.precedence <= o2.precedence)) ||
            (isRightAssoc(o) && (o.precedence < o2.precedence))
        }
        case _ => false
    }
    if (stack.isEmpty || !matchCond(o, stack)) (stack.push(o), postfix)
    else operatorUpdate(postfix :+ stack.pop, stack, o)

/** Helper method to update postfix and stack during right parens parsing. */
@tailrec
def rightParensUpdate(postfix: List[Token], stack: Stack[Token]): (Stack[Token], List[Token]) =
    if (isLeftParens(stack.head)) {stack.pop; (stack, postfix)}
    else rightParensUpdate(postfix :+ stack.pop, stack)

The shuntingYard function returns a new token list in postfix notation.

Parsing postfix token list into an expression

Given the postfix token list, the second step of the parser converts it into a full expression.

The algorithm is quite simple. It recursively walks through the token lists. If a number token is encountered, it is placed on a stack. If an operator is encountered, the last two elements from the stack are combined accordingly and the resulting expression is put on the stack. Eventually, the stack only contains one expression, which is the final one.

/**
 * Parses RPN to expression.
 * 
 * Takes a list of tokens in RPN and parses the expression representation.
 * https://en.wikipedia.org/wiki/Reverse_Polish_notation
 * 
 * @param tokens: List of tokens in postfix notation
 * @return parsed expression
 * */
def parsePostfix(tokens: List[Token]): Expression = 

    /** Helper method to determine if token is operator. */
    def isOperator(t: Token): Boolean = t match {
        case a: OperatorToken => true
        case _ => false
    }

    /**
     * Recursive method of the algorithm.
     * 
     * @param stack: Stack of expressions to parse
     * @param tokens: Tokens to parse.
     * @return parsed expression
     * */
    @tailrec
    def recur(stack: Stack[Expression], tokens: List[Token]): Expression = tokens match {
        case Nil => stack.pop
        case t :: rest => {
            if (isOperator(t)) t match {
                case t: SumToken => stack.push(Sum(stack.pop, stack.pop))
                case t: DifferenceToken => val x = stack.pop; stack.push(Difference(stack.pop, x))
                case t: ProductToken => stack.push(Product(stack.pop, stack.pop))
                case t: DivisionToken => val x = stack.pop; stack.push(Division(stack.pop, x))
                case t: PowerToken => val x = stack.pop; stack.push(Power(stack.pop, x))
                case _ => throw new RuntimeException(s""""$t" is not an operator""")
            }
            else t match {
                case t: NumberToken => stack.push(Number(t.n))
                case _ => throw new RuntimeException(s""""$t" is not valid here""")   
            }
            recur(stack, rest)
        }
    }

    recur(new Stack[Expression], tokens)

Putting it together

With the shuntingYard and parsePostfix functions in place, we can define the parse function, which we can call to actually perform the parsing.

/**
 * Run the parser.
 * 
 * Converts the tokens to postfix notation and then reverses it to RPN.
 *
 * @param tokens: List of tokens in infix notation
 * @return Parsed expression
 * */
def parse(tokens: List[Token]): Expression =
    val postfix = shuntingYard(tokens)
    parsePostfix(postfix)

And that is the parser done. You can find the final version of Parser.scala here.

Main.scala

To make the project runnable, we need a main method in Main.scala. This is just a few lines:

object Main {
    def main(args: Array[String]) = args match
        case Array(x: String) => printResult(getResult(x))
        case Array() => throw new java.lang.IllegalArgumentException("Too few arguments!")
        case _ => throw new java.lang.IllegalArgumentException("Too many arguments!")

    /** Tokenize and parse expression. */
    def getResult(rawExpr: String): Expression = tokenize(rawExpr).parser
    /** Print the result of the evaluation. */
    def printResult(expr: Expression): Unit = println(expr.eval)
}

Testing the parser

Let's try out the parser on some expressions. Fire up your sbt server and run some examples.

sbt:equation-parser> run "1+2"
3.0

sbt:equation-parser> run "3 * (1 + 2) ^ 7"
6561.0

sbt:equation-parser> run "100 / 8 - (2 * 3) + 4 ^ 3"
70.5

sbt:equation-parser> run "((3 + 2) * (2 + 1)) ^ 2"
225.0

sbt:equation-parser> run "(-42)^3+(-42)"
-74130.0

Seems to work!

(We should probably write some more thorough tests to make sure it actually works, which I did here)

Conclusion

Implementing this Tokenizer/Parser/Evaluator in a functional way in Scala proved to be a very insightful and fun learning project. Maybe it will inspire anyone to build their own parser or improve upon mine.

Feel free to reach out with any comments or feedback!

A/B testing a Vue app with AlephBet

Leo Pfeiffer — Wed, 06 Apr 2022 12:45:53 +0000

In this article, we will set up A/B testing for a simple Vue.js app and process the experiments on a Node.js server, saving them in a SQLite database.

Before we get started, if you need a refresher on A/B testing or want to learn about how A/B testing is used by Netflix to drive user experience, I can recommend this series on the Netflix tech blog.

All code of this post is on Github.

Goal

The idea is to build a simple counter app with a button that increments a counter with every click. The A/B test could (for example) test if users prefer a blue button or a green button.

When the user clicks the button, the event is posted to the node server, which will store the results in a database for later analysis.

While the set up is simple, it should demonstrate the principles involved relatively clearly.

Technologies

Vue 2 app on which we want to perform A/B testing
Node/Express server to process experiment results
SQLite database to store experiment results
AlephBet framework for A/B testing

Setting up the Vue project

First, set up a basic Vue project. We will use Vue 2 here.

vue create client

Next, we will make some changes to the HelloWorld component, which will be the subject of our tests. The Vue component will have a single button and counter. The .is-blue and .is-green CSS classes will be used later for the A/B test.

// client/src/components/HelloWorld.vue

<template>
  <div class="hello">
    <p id="counter"> {{ counter }}</p>
    <button id="increment-btn" @click="increment">Increment</button>
  </div>
</template>

<script>
export default {
  name: 'HelloWorld',
  data() {
    return {
      counter: 0,
    }
  },
  methods: {
    increment: function() {
      this.counter++;
    }
  }
}
</script>

<style scoped>
#counter {
  font-size: xxx-large;
}

#increment-btn {
  border: none;
  padding: 15px 32px;
  font-size: x-large;
  margin: 4px 2px;
  cursor: pointer;
}

.is-blue {
  background-color: #34495e;
  color: white;
}

.is-green {
  background-color: #41b883;
  color: white;
}

</style>

Setting up AlephBet

As mentioned before, we will use AlephBet for managing the A/B tests.

Configuration

First, install the dependency:

npm install alephbet

Next, we can configure our tests. Set up a new file in the Vue project src/analytics/ab-testing.js.

After importing AlephBet, we will set up a wrapper method makeExperiment to create new experiments.

// client/src/analytics/ab-testing.js

const AlephBet = require("alephbet");

/**
 * Set up a new A/B testing experiment with AlephBet
 * @param name Name of the experiment
 * @param variants Object of the experiment variants
 * @param adapter Adapter of the experiment
 * */
const makeExperiment = (name, variants, adapter) => {
    return new AlephBet.Experiment({
        name: name,
        variants: variants,
        tracking_adapter: adapter,
    });
};

AlephBets uses Google Analytics by default as the experiment adapter. Since we want to set up our own backend, we need a custom adapter. For now, we will simply log all events to the console.

// client/src/analytics/ab-testing.js

/**
 * Wrapper for an A/B testing adapter for AlephBet experiments.
 * */
const makeAdapter = () => {
    return {
        experiment_start: async function (experiment, variant) {
            console.log(experiment, variant, 'participate')
        },
        goal_complete: async function (experiment, variant, event_name) {
            console.log(experiment.name, variant, event_name)
        },
    };
};

Defining the variants

Next, we can define our experiment variants. We will store these in a JS object experimentVariants with the key being the name of the experiment.

// client/src/analytics/ab-testing.js

// Experiment variant presets
const experimentVariants = {
    "button color": {
        green: {
            activate: function () {
                document.getElementById("increment-btn").className = "is-green";
            },
            weight: 50,
        },
        blue: {
            activate: function () {
                document.getElementById("increment-btn").className = "is-blue";
            },
            weight: 50,
        },
    },
};

In the inner object, we define two variants blue and green. Each variant has an activate function that is called by AlephBet when the variant is activated for a user. In our case, the activate function adds the .is-green or .is-blue CSS class, respectively, to the increment button.

The weight specifies the likelihood that a user is allocated the variant.

Lastly, export the two wrapper methods and the object with the variants.

module.exports = {
    makeExperiment: makeExperiment,
    makeAdapter: makeAdapter,
    experimentVariants: experimentVariants,
}

Configuring the Vue component

The actual experiment is configured in the HelloWorld component, specifically in the mounted method of the component.

Start by importing the functions we just created as well as AlephBet. We also need to define the variable for the goal in the most outer scope of the component.

// client/src/components/HelloWorld.vue

import {
  experimentVariants,
  makeAdapter,
  makeExperiment,
} from "@/analytics/ab-testing";
import AlephBet from "alephbet";

let goal;
...

The goal variable captures the completion of the goal of the experiment - in this case when the user clicks the button.

In the mounted method, set up the goal with the experiment. We set unique: false since we want every click to be registered and not merely the first click.

// client/src/components/HelloWorld.vue

...
  mounted() {
    const name = "button color";
    const variants = experimentVariants[name];
    const adapter = makeAdapter();
    const experiment = makeExperiment(name, variants, adapter);
    goal = new AlephBet.Goal("button clicked", {unique: false});
    experiment.add_goal(goal);
  },
...

Finally, we need to actually register the goal completion when the button is clicked. As the increment function is called on click, we can simply add one line to that method.

// client/src/components/HelloWorld.vue

...
increment: function() {
      goal.complete()
      this.counter++;
    }
...

That is the basic set up of the client complete. Fire up your application and head over to localhost:8080. You should now either see a blue or a green increment button. AlephBet actually stores the variant in localStorage so that one user is always shown the same variant. Hence, if you'd like to see the other variant, delete the alephbet entry from localStorage and refresh the page (you might have to do this a few times until you randomly get allocated to the other group).

If you open the console, you will also notice that the adapter logs the start of the experiment as well as every goal completion, that is every button click.

Next on the list is the set up of our experiment tracking server.

Node.js server setup

Start by setting up a second directory server on the same level as the client Vue app, then setup the npm project and install the dependencies.

mkdir server
cd server
npm init
npm install express cors sqlite3

index.js

Next, create a file in server called index.js and add the following content:

// server/index.js

const express = require("express")
const app = express()
const cors = require('cors')

app.use(cors())

// Server port
const PORT = 5555;

// Start server
app.listen(PORT, () => {
    console.log(`Server running on port ${PORT}`)
});

// Root endpoint
app.get("/", (req, res, next) => {
    res.json({"message":"Ok"})
});

// A/B testing endpoint
app.post("/track_experiment", (req, res) => {
    const experiment = req.query.experiment;
    const variant = req.query.variant;
    const event = req.query.event;

    if (experiment === null || variant === null || event === null) {
        res.status(400);
        return;
    }

    console.log(experiment, variant, event);
    res.json({"message":"Ok"})
})

// 404 not found for other requests
app.use(function(req, res){
    res.status(404);
});

We won't go into detail here, but essentially we're setting up a simple server running on PORT 5555 with the /track_experiment endpoint, to which we can send our experiment events from the counter app.

database.js

To persistently store the experiment results, we use a simple SQLite database. The setup here is very basic and could (should!) be improved but it is sufficient for this proof of concept.

In the server directory create the following file database.js:

// server/database.js

const sqlite3 = require('sqlite3').verbose()

const DB_FILE = "db.sqlite"

let db = new sqlite3.Database(DB_FILE, (error) => {
    if (error) {
        // Error opening db
        console.error(error.message)
        throw error
    }
    else{
        console.log('Connected to the SQLite database.')

        const sql = `
        CREATE TABLE experiment (
            id INTEGER PRIMARY KEY AUTOINCREMENT,
            name text, 
            variant text, 
            event text
            );
        `
        db.run(sql, (err) => {/* table already exists */});
    }
});

module.exports = db

This sets up a single table experiment with the columns id, name, variant, and event.

Now that we've set up the database, we can fill out the rest of the API endpoint.

Back to index.js

First, import the db object at the start of the file.

// server/index.js
...
const db = require("./database.js")
...

We can now update the /track_experiment to insert the incoming experiment data into the database. The final endpoint should look like this.

// server/index.js

...

// A/B testing endpoint
app.post("/track_experiment", (req, res) => {
    const experiment = req.query.experiment;
    const variant = req.query.variant;
    const event = req.query.event;

    if (experiment === null || variant === null || event === null) {
        res.status(400);
        return;
    }

    // Insert into database
    const sql = 'INSERT INTO experiment (name, variant, event) VALUES (?, ?, ?)'
    const params = [experiment, variant, event];

    db.run(sql, params, function (error, result) {
        if (error){
            res.status(400).json({"error": error.message})
            return;
        }
        res.json({
            "message": "success",
            "data": params,
            "id" : this.lastID
        })
    })
})

...

We can try this out by starting the server node server/index.js and sending a test request to the endpoint with curl.

curl --request POST "http://localhost:5555/track_experiment?experiment=myname&variant=myvariant&event=myevent"

> {"message":"success","data":["myname","myvariant","myevent"],"id":1}%

Success!

Integrating the Vue app with the server

Server and DB are running, thus we can now connect the client to the server.

Head back to the client directory. We will edit the ab-testing.js file.

We first need to add a method to post the event to the tracking server.

// client/src/analytics/ab-testing.js

/**
 * Post an experiment result to the tracking server.
 * */
const postResult = (experiment, variant, event) => {
    let URL = "http://localhost:5555/track_experiment"
    URL += `?experiment=${experiment}&variant=${variant}&event=${event}`
    fetch(URL, {
        method: 'POST'
    }).catch(console.error)
}

Almost done. Now, in the makeAdapter wrapper function we want to use this new method. Update the code as follows:

// client/src/analytics/ab-testing.js

...

const makeAdapter = () => {
    return {
        experiment_start: async function (experiment, variant) {
            postResult(experiment.name, variant, 'participate')
        },
        goal_complete: async function (experiment, variant, event_name) {
            postResult(experiment.name, variant, event_name)
        },
    };
};

...

That's it. Any experiment results will now be posted to the server and saved in the database:

Final thoughts

Setting up basic A/B tests with AlephBet isn't rocket science. While this demo project is fairly simple, I hope it serves as a decent introduction.

Feel free to reach out for feedback!

Happy A/B testing 🎉