Forem: Morgan Kenyon

Supervised v. Unsupervised v. Reinforcement Learning: An Introduction

Morgan Kenyon — Mon, 18 May 2020 00:38:41 +0000

Machine Learning powers a lot of what we do. Currently there are three main categories of machine learning, supervised learning, unsupervised learning and reinforcement learning.

Let’s talk a bit about them and what differentiates them.

Machine Learning

Machine learning (ML) is the scientific study of algorithms and statistical models that computer systems use to perform a specific task without using explicit instructions. ~ Wikipedia

I am a professional software developer who mainly writes web apps.

When I want a computer to do something, I have to explicitly code for that. If I don’t tell a computer to do something it will never do it.

Machine Learning on the other hand, allows computers to perform tasks that they themselves learn.

You throw data at a computer and it learns patterns from that data. (hopefully)

This has substantial power and also drawbacks. At times computers can surprise or surpass our intellect, but there are lot of tasks computers can’t currently solve.

Broadly speaking, there are three main categories of machine learning:

Supervised Learning
Unsupervised Learning
Reinforcement Learning

Supervised Learning

Our first category is supervised learning. For me personally, this is the easiest category to learn and understand.

In supervised learning, the data that the algorithm trains on has both input and output.

One good example of this is the MNIST Database of Handwritten Digits, the “hello world” of machine learning. This database is a collection of handwritten digits in input and output pairs. The input is the image, and the output is the answer of what digit is in the photo.

When using supervised learning, the algorithm uses the input to make a prediction and compares the prediction against the expected output.

If it’s incorrect, the algorithm will modify itself in some way to make better predictions in the future.

Supervised learning is powerful and simple if you have the data that you need. If you don’t have neatly labeled data, or if your data is poorly labeled, then supervised learning is not going to be as effective.

Unsupervised Learning

Our next category is unsupervised learning. In contrast to supervised learning, unsupervised learning has input but no expected output.

Unsupervised algorithms automatically learning patterns or groupings that exist in the data.

For instance, in a 2012 Google study, researches just threw 10 million YouTube thumbnails at their “brain.” Over the course of three days it began to recognize pictures of cats.

No one told the brain to look for cats or recognize cats. Cats all look rather similar, so the brain remembered that pattern and taught itself how to identify it.

It’s also how a lot of modern NLP models are trained. Just throw lots of text (like the entire English wikipedia) at it and allow it to figure out how to make sense of it.

Unsupervised learning is great when you have a lot of data and a lot of compute power to find patterns in your data.

Reinforcement Learning

Reinforcement learning tries to model problems similarly to the way that humans live our lives. Reinforcement learning learns how to optimize an agents behavior based on the presence or absence of some reward.

For instance in my real life, I go to work because I receive a paycheck every two weeks. The reward (the paycheck) influences my behavior (continuing to be a good employee).

A good example is game playing bots. There’s an environment (the board), the agent takes actions, and receives a reward at the end of the game (win, loss or tie). The agent plays a lot of games to learn what actions lead to better rewards.

One good example of this is DeepMind learning to play Atari games. Raw pixel data was fed into the rl algorithm, it’s reward function was the game score, and it learned how to “play” the game to improve it’s reward.

Deep Learning

One last thing that’s worth mentioning is deep learning. Deep Learning is a sub domain of all of these categories. The label Deep Learning can be applied to any algorithm that specifically uses a multi-layer neural network, a deep network.

For instance, there are numerous ways to solve problems using reinforcement learning. If you’re specifically using a neural network, then you can say you’re using deep reinforcement learning.

If you’re playing around with neural networks, you can usually call it “deep”. But if you’re using some other machine learning algorithm to solve your problem, you wouldn’t call it “deep.”

Final Thoughts

Machine Learning is an exciting field. If you’re just starting out with machine learning, fast.ai has a great free course to help you explain the basics. I’m currently reading Grokking Deep Reinforcement Learning to bump up my reinforcement learning!

If you’re interested in learning more about machine learning, follow me on twitter, I’ll be learning, writing and tweeting about it as I do it.

Optimizing our Perfect Tic-Tac-Toe Bot

Morgan Kenyon — Sun, 10 May 2020 18:41:23 +0000

In my last post, we built a tic-tac-toe bot that would never lose a game! It was great, except it was really slow. It took over 30 seconds to determine the first move.

Lets optimize that using a simple technique to prune the amount of searching we perform for each move!

Our Problem

Why is our bot slow? It’s slow because it’s dumb. There’s no intelligence to how it goes about searching boards.

Lets take the following game board.

It’s X’s turn, what is X going to do? Obviously they’re going to play in the bottom right corner and win.

But our bot sees 5 potential moves X can make, and evaluates each one equally. It eventually picks the bottom right corner as the best move, but not before seeing and comparing all 5 moves against each other. Evaluating all moves equally leads us to do a lot of unnecessary work, which is the main performance problem.

Alpha Beta Pruning – Intuitively

If you recall back to when we discussed our minimax algorithm, one of our players is attempting to maximize the score and the other is attempting to minimize the score. We search the entire tree, alternating taking the max or min at that level to determine the optimal game score.

Lets take the following simple tree. Player 1 has the first choice and wants to maximize their score. Player 2 will then take a turn and wants to minimize their score. And notice that our last node doesn’t have a value.

Why doesn’t our last node have a value? It’s empty to demonstrate that the value actually doesn’t matter. We don’t need that node’s value to make the optimal decision.

Here’s how we would calculate it.

To calculate the score for the left sub tree, we take the min(-2,3) = -2. So if we go left, we would end up with a score of -2.

Evaluating the one node of the right sub tree, we find a -10. -10 is worse than our left sub tree. We would rather take that -2 score than a -10.

Even though we don’t know every node’s value, we know enough to stop further exploration.

That’s the core idea, stop searching down a particular tree when we are guaranteed to get a worse result than what we already have.

In this example, we saved exploring one node, not a big deal. The benefit comes in avoiding having to search entire subtrees. In more complicated games, such as Chess or Go, with branching factors of ~35 or ~250, anything we can avoid searching is a win!

Alpha Beta Pruning Pseudocode

Now that we’ve discussed the idea behind alpha beta pruning, lets look at the pseudocode.

The algorithm introduces two new variables, called alpha and beta (hence the name of the algorithm), that track each players current state.

alpha – tracks the lowest score for the maximizing player, initialized to negative infinity.
beta – tracks the highest score for the minimizing player, initialized to positive infinity.

Lines 12 and 20 hold the potential to stop evaluating whenever it’s useless to. Whenever the lowest score for the maximizing player (alpha) is greater than the highest score for the minimizing player (beta), we stop evaluating.

If we get to the point where we realize, “hey this is worse than what we already know”, we stop searching. When we choose to stop searching down a path, we say that we’re pruning. Hence the name of the algorithm.

Lets take a look at what this looks like in our tic-tac-toe bot.

AbBot – AlphaBeta Bot

Lets start by taking another look at our invincibot.

For every board, we:

Generate the legal moves (line 27)
Search down the subtree of each potential move (lines 30-36), keeping track of the value that each subtree has (candidate_choices).
We only stop whenever someone either wins or the game is tied (lines 19-25)
Determine the max and min moves (lines 38-41)
Then return the corresponding move depending on whether the player is looking for max or min (lines 45-48) Point #3 is the important step, we only stop when the game ends. We need a better way to stop searching.

Lets implement alpha beta pruning for our tic tac toe bot now to do that.

You’ll notice it’s a mix of my previous bot code with the alpha beta pseudocode. Notable points are:

We initialize our alpha and beta to -100 and 100 (line 59), those values are both small/big enough for our needs.
Lines 40 & 47 hold the potential to stop evaluating early, depending on our alpha and betas.
The rest is pretty much the same.

How Does It Perform?

If you remember from my last post, the optimal game of tic-tac-toe always ends in a tie. When two players play against each other who always pick the best move, the game ties. It’s only when a player makes a mistake that someone will win.

That’s what happened when we played our invincibot against itself, it tied all day long.

When we pit our abbot against itself and against invincibot, it also ties all day long.

abbot (x) vs invincibot (o)
- x wins: 0
- o wins: 0
- ties: 15
invincibot (x) vs abbot(o)
- x wins: 0
- o wins: 0
- ties: 15
abbot (x) vs abbot(o)
- x wins: 0
- o wins: 0
- ties: 15

So our bot makes the same optimal choices, but what about the number of board states explored? We coded our abbot in order to reduce the searching, which would help it play faster.

Here’s the decrease in boards searched through in invincibot compared to our abbot:

1st move: 294,778 => 12,413 => ~95% decrease
2nd move: 31,973 => 1,675 => ~95% decrease
3rd move: 3,864 => 525 => ~86% decrease
4th move: 478 => 44 => ~90% decrease
5th move: 104 => 38 => ~63% decrease
6th move: 26 => 10
7th move: 8 => 6
8th move: 3 => 3
9th move: 1 => 1

This means that roughly 95% of boards that our original bot search through for the first two moves were redundant. That’s an impressive reduction!

Also when two abbots play against each other, the games only takes about 1 sec. Whereas when two invincibots play against each other, the games takes about 1.5 mins. Another impressive reduction.

Final Thoughts

Implementing alpha-beta pruning drastically improved the performance of our bot. I really enjoyed implementing this and seeing this level of improvement.

I think next week I’ll look into implementing a Monte Carlo type search for our bot. While not necessary to solve tic-tac-toe, this technique is vital in tackling more complicated games.

If you’re interested in learning more about game playing bots and machine learning, follow me on twitter, I’ll be learning, writing and tweeting about it as I do it.

Github repo with code samples.

Coding A Perfect Tic-Tac-Toe Bot

Morgan Kenyon — Sun, 03 May 2020 20:10:42 +0000

This article builds upon last week’s minimax searching article. I won’t discuss minimax in depth here, so please check out that article if you have questions about minimax.

Games are fun! Programming computers to play games is also fun!

Today I’m going to walk you through what is takes to write a tic tac toe bot.

Tic tac toe might be a simple game, but it’s useful to teach strategies for how some computers approach playing games.

How Humans Play Tic Tac Toe

Imagine you wanted to play tic tac toe. How would you go about doing that?

You’d first learn the rules. Then start playing games.

Which deciding on a move, you would probably mentally play out how the game would progress.

If I play there, and he plays there, then I could play there, so on and so on.

Over time, you begin to understand which strategies are better or worse.

You begin to gather an intuition about the game.

How Bots Play Tic Tac Toe

On the other hand, how do bots play games? It’s harder for a bot to build an “intuition” about games.

Humans have to program bots how to play games. Historically that’s done via a rules or brute force based approach. Our programs tell bots exactly what to do in each circumstance. That’s changing a bit with the rise of deep learning.

Today we’re going to teach our bot how to play tic tac toe using a brute force solution, minimax searching.

We’ll leverage minimax searching to simulate every possible move and counter move. That way our bot will always pick the best move given a particular game state.

This type of strategy gets computationally infeasible for more complicated games, but useful for solving games of this complexity.

Setting Up Our Game

The first thing that we’ll do is write classes and methods that keep track of our game state. All source code is located on github.

Player

First, we'll define our player enum.

Tic tac toe is a two player game, so naturally we’ll have two players. We’ll also provide a useful property, other, to always allow us to easily get the other player.

Board

Next we’ll turn out attention towards our board. Our board handles most of the logic for running a game. It tracks the history of moves, determines when someone wins and ensures everyone plays according to the rules.

We’ll start of by defining a helper, our board constructor and a print method to print our board.

MARKER_TO_CHAR allows us to convert between how we track our players and how we display them.

Our constructor initializes an empty board and empty moves list.

Here’s what an empty board would look like.

And here’s what it would look like after two turns.

Definitely simple, but effective. Now lets turn out attention to determining if someone has won our game.

Winning

How does someone win a game of tic tac toe? Someone wins if they get three in a row. So these are all winning moves for o.

So we’ll add a method called has_winner() to our board class that checks those 4 cases.

We only check after our game is 5 moves or older, a tic tac toe game is unwinnable before that point.

If it finds a winner it will return that player, else return None indicating that there is no winner yet.

Helper Functions

Then lastly we’ll wrap up our board with several helper functions.

make_move() takes a row, col and player and will mark that space for that player if the space is empty.

get_legal_moves() determines which of the board spaces is unoccupied and returns those spaces in a [row, col] format.

__deepcopy__(), most of the bots that we’re going to build generate copies of boards. This method helps ensure that our simulated boards don’t mess up our real board.

Game

The last class we’ll introduce before diving into bots is our game class. It’s job is to simulate and record stats for games against two different bots.

It can simulate a configurable amount of games. We’ll use this to determine how our bots fair against either other over a larger quantity of games.

Now lets dive into bots!

RandomBot

The first bot we’re going to build makes random moves. It’s the simplest bot.

All it does is take a board, gets the legal moves it could make and picks one at random.

Lets create a runner class to pit two random bots against each other and see how they perform.

If we simulate 1000 games here are the results:

x wins 577 times
o wins 312 times
ties 111 times

You can run this multiple times and the percentages are in this ballpark. Even though both are playing randomly, the x win percentage is higher because x always goes first. X has a first turn advantage.

OneLayer Bot

A random strategy is really bad. Lets make our bot a little smarter. Our next bot looks at the current board, if there is a winning move it will pick it. Otherwise it will default to the random strategy.

The comments describe what our bot is doing. We’re basically performing a one layer search, hence the bot name. Our bot can look one move into the future and pick the best move if it is a win.

Lets create another runner to test our bot, we’ll bit it against the randombot to see whether it improves or reduces winning percentages.

We play 1000 games in each combination of bots. Not surprisingly our onelayerbot improves our odds of winning.

randombot (x) vs. onelayerbot (o)
- x wins: 390
- o wins: 529
- ties: 81
onelayerbot (x) vs randombot (o)
- x wins: 805
- o wins: 109
- ties: 86
onelayerbot (x) vs onelayerbot (o)
- x wins: 689
- o wins: 266
- ties: 45

The first set of results is interesting, our one layer bot is able to reverse the first turn advantage that x has because it has a (marginally) better strategy.

TwoLayer Bot

Lets build another bot that looks two moves into the future. It still picks a winning move if there is one, but it now blocks a winning move for the opponent.

Lines 21-29 are the new bit. It calculates determines if its opponent can win on it’s next turn. Playing in that space to prevent them from winning.

Again lets create another runner to pit our bots against each other.

randombot (x) vs twolayerbot (o)
- x wins: 50
- o wins: 713
- ties: 237
twolayerbot (x) vs randombot (o)
- x wins: 879
- o wins: 13
- ties: 108
twolayerbot (x) vs twolayerbot (o)
- x wins: 310
- o wins: 164
- ties: 526

Winning percentages continue to go up for our new bot against the random bot. You’ll also notice that when our twolayerbot plays against itself, it ties over half the games. it’s defense is a lot better.

InvinciBot

And lastly, for the moment we’ve all been waiting for, a bot that will never lose a game of tic tac toe.

InvinciBot!!!! 👍👏

How does our bot do it? It implements a minimax search algorithm to calculate every possible combination of move. Therefore, ensuring with precision, to never make a move that would result in a loss.

Because tic tac toe is a rather simple game, if both players always choose the an optimal strategy the game will always result in a tie. Which is why I say our bot will never lose, instead of saying it will always win. If it’s playing against an inferior opponent it will win most of the time!

Our minimax implementation is a recursive depth first search algorithm. For a particular board, it calculates whether each move would result in a win, tie or lose.

Because it simulates every possible move, this bot takes a lot longer to play. Running locally, it takes about 30 secs to make the first move.

Lets put together a runner to test out our bot (this runner took 25 minutes to run locally).

invincibot (x) vs randombot (o)
- x wins: 15
- o wins: 0
- ties: 0
randombot (x) vs invincibot (o)
- x wins: 0
- o wins: 13
- ties: 2
invincibot (x) vs invincibot (o)
- x wins: 0
- o wins: 0
- ties: 15

InvinciBot dominates randombot. It’s not even close. And when invincibots play against each other, the game always ends in a tie. That is the optimal results for a game of tic tac toe. If each player using the best strategy, the game will always tie.

How InvinciBot Plays

I’ll touch briefly on how InvinciBot is so good at tic tac toe. As mentioned before, it’s good (and takes so long) because it uses minimax to search through each possible move.

Here is what a sample search would look like. It generates every possible combination for each player.

I left off most of the board states because I can’t draw that many. But the search doesn’t stop until a particular board ends with a win or a tie. Here’s the number of boards that are generated to pick each move in the game.

1: 294,778
2: 31,973
3: 3,864
4: 478
5: 104
6: 26
7: 8
8: 3
9: 1

To make the 1st move, InvinciBot generates over a quarter of a million potential boards. To make the 9th and last move, there’s only one open spot, so it only generates one board.

As it generates possible board states, it remembers whenever a game ends in a win, tie or lose. Then at each level compares the best outcome for that particular board, ensuring that the player makes the best possible move.

This strategy works well for simple games, but breaks down quickly in more complex games.

Final Thoughts

I really enjoyed making these tic tac toe playing bots! It was fun to see a bot play tic tac toe. While the game is simple, we can still learn a lot of strategies to help us beat other games.

There’s definitely a lot of room for optimization, alpha beta pruning being the logical optimization to make.

If you’re interested in learning more about game playing bots, follow me on twitter, I’ll be learning, writing and tweeting about it as I do it.

I’m currently reading Deep Learning and the Game of Go, this post is inspired by my reading there. Specifically player and printing the board are inspired by that book. I would recommend the book to anyone looking for an in depth introduction to game playing bots.

Please see my github repo for full source code.

Originally published at thesharperdev.com

Implementing Minimax Tree Search

Morgan Kenyon — Sun, 26 Apr 2020 00:54:48 +0000

Game playing is one way to learn machine learning strategies. A most game playing bots involve some searching mechanism. It’s how the bot can “see” which move can result in a favorable outcome down the line.

Lets learn about minimax, a useful technique to build an AI to compete on simple games.

Single Player Tree Searching

Lets play a little game. The object of the game is to end up with the highest number.

For a single turn, one player game the choice is simple.

You go right, end of with a score of 10! That’s the highest possible score in our little game.

Lets make it a little more complicated. Our game now has two turns, what do you choose?

On your first turn, if you make the same decision (pick 10), that will leave you with bad options on your second turn (2 or 3).

To achieve the highest score, you need to pick 1 on your first turn in order to be able to pick 20 on your second turn.

One way to model this, is to start at the bottom and choose the max at each node. If we do that across our entire tree, we determine our max score (20) and which decisions to make (left, left).

Two Player Tree Searching (Minimax)

What if we introduced another player into this game? Now two players are competing to against each other. With a small tweak in the rules.

Player 1 wins if a positive number is chosen.
Player 2 wins if a negative number is chosen.
A tie occurs if 0 is chosen.
Players alternate turns with Player 1 going first.

Lets take the following game.

Player 1 (P1) makes the first choice, then Player 2 (P2) has a turn, and finally Player 1 makes the final pick.

Player 1 wants positive numbers, so they’re looking to maximize their score.

Player 2 wants negative numbers, so they’re looking to minimize their score.

That’s where the term minimax comes from, from players wanting to either minimize or maximize their score.

How could this game play out? If each player choose the best available option to them at the time, the optimal game outcome is 7, which means Player 1 wins!

Lets model this game as well.

Again, Player 1 attempts to maximize their score, Player 2 attempts to minimize their score.

Player 1 goes left, Player 2 goes left, and finally Player 1 goes right landing on a score of 7.

Programming Minimax

Lets implement a minimax search in python!

We first need a data structure to hold our values.

We create a Node class, it can hold a single value and links to a left and right Node.

Then we’ll create a Choice class that represents the players choice.

Next we’ll initialize a tree with the values from the two player game we modeled above.

You’ll notice on line 41, I’m printing the tree. Which outputs the following:

The print_tree function is available on the github repo.

We’ll solve this by coding a recursive depth first search algorithm. The main concerns we want to keep in mind are:

We need to keep track of which players turn it is, I’m using the is_max to track that.
We need to know when to stop our search, in recursion that means we need some base cases.
We want to explore our whole tree. We need some comparison logic to determine which sub tree we will choose to explore.

Our base case will be when our node no longer has any children, we just return the value of the node.

In order to explore our whole tree, we’ll call minimax on each sub tree in our node.

Making sure to reverse is_max because the players alternate turns.

Finally, we compare the results. If we’re maximizing we take the max results, then if we’re minimizing we take the minimum results.

Lets create a little simulator to play our game for us.

Running this outputs the following:

Moving left to node with value -2
Moving left to node with value 3
Moving right to node with value 7
Game ends with a score of 7

Congrats! We’ve correctly demonstrated how to use minimax to optimally solve a simple two player game.

Parting Thoughts

This game is about as simple as it gets. But searching is an integral part to most automated game playing bots. It’s how bots can “see” into the future.

For a challenge, see if you can use minimax to build a tic tac toe playing bot.

As you can imagine, with complicated games (Chess and Go) searching has its limitations due time and memory constraints. Further strategies such as alpha-beta prune and Monte Carlo simulation can help in those cases.

You might have noticed that my base case will only work with nodes that have two or 0 child nodes. The minimax in the git repo will contain code to handle that condition.

Originally published at thesharperdev.com.

Functional Fundamentals: Currying

Morgan Kenyon — Sat, 30 Nov 2019 20:05:56 +0000

Some time ago, I watched a talk that Scott Wlaschin gave at a conference about functional programming. He said often times people who don’t understand functional programming get scared off by the terminology. Terms such as currying, partial application, functor, monad, etc.

It’s easy to think these are super complex concepts, when in reality these terms are just unfamiliar.

Object oriented programming has similar terminology, encapsulation, polymorphism, inheritance, etc. We’ve just been exposed to those terms so they’ve lost their scariness.

Today lets dive into the topic at hand, currying.

Method Parameters in OO Land

In most OO style programming languages, C#, Java, Python, C/C++, etc. A method has a set number of parameters.

Take this C# method for concating strings.

It takes two strings as input, and returns one string.

Every time you call this method you must provide two parameters. If you don’t, the C# compiler complains.

Function Parameters in Functional Land

On the other hand, in most functional style programming languages, F#, Elm, Haskell, etc. Function parameters are defined and leveraged differently.

Here is how we define a function in Elm that needs two strings as input before it can return the output string.

Notice in Elm the definition of the function is on a separate line than the implementation. A lot of functional languages are like that.

Also notice how the definition is in a different format, “string -> string -> string”. If you’ve never been exposed to a functional language before that might be a bit odd.

Defining a similar function in F# is a bit different.

But the signature is the same, here’s a screenshot of this function in VS Code using the the Ionide plugin.

Ionide adds the (// string -> string -> string) function definition automatically, you’ll notice it’s the same as Elm’s.

Even though this take two strings as input, I can only give it one and the compiler doesn’t have any problem with it.

The signature of concateWordWith is now “string -> string”.

Or I can it two parameters but in two sets of parenthesis.

Why is that?

The reason is because of currying.

Currying Explained

Currying is a fundamentally different way of handling functional parameters. In OO languages, it’s all or nothing. If a method has 3 inputs, give me 3 inputs or boom! Compile error.

Curried functions offer more flexibility. They let you build up the input parameters over time. You can give one input now. Then later give it another input. Then finally the last one right before it’s used.

Said another way, If a function has 3 inputs and you only give it one, it will return a function that takes 2 inputs. Then you can give that 2 input function one input and it will return a function that takes 1 input. Then you can give that 1 input function one input and it will finally return the output.

So if you see a function that has a signature of “string -> string -> string”, an OO way to describe it would be “a function that takes two strings as input and returns one string as output”. A more functional way of describing would be “a function that takes a string, that returns an intermediate function that takes a string that returns a string.

Because of currying, there’s really no such thing as a multi parameter function in most functional programming languages. If you’re passing multiple parameters, they’re really being applied one at a time to a sequence of intermediate functions. The compiler does this for you automatically.

In fact Wikipedia defines currying as “…the technique of translating the evaluation of a function that takes multiple arguments into evaluating a sequence of functions, each with a single argument”. So breaking every argument down into it’s own separate function.

Why is Currying Useful

So now that you know what currying is, the next logical question is “is it useful”? Is this just one of those “functional” things that only exist to make life more complicated.

In languages that support currying, currying provides a lot of flexibility with how you call functions.

Take the following example in C# that adds 2 to every number in a list.

Pretty simple code. Here’s how you could do it in F# without taking advantage of currying*.

Fairly straight forward. But since F# curries functions, here’s a more functional way of doing it.

The add function takes two inputs, but in this example we give it one input (2). Then let the List.map provide the second input, one for each element of the list.

Granted, that isn’t a world changing difference. In my day job I write C#, so I deal with non-curried functions all the time. But if you spend enough time in a curried language you begin to miss the little shortcuts and niceties.

*Yes, every function is automatically curried, so not technically a true statement. But different from the next example.

Wrapping Up

Currying is an important concept to know when working in functional languages. It’s a great language feature that comes in handy all over the place.

Currying is just one of many concepts that I was never exposed to in the OO world. I hope you take some time to learn functional programming and all the unique features it has to offer.

Sources

How to Write a Brainfuck Interpreter in C#

Morgan Kenyon — Sun, 13 Oct 2019 16:16:17 +0000

I’ve always been somewhat interested in how programming languages are written. Last month I bought Writing An Interpreter In Go, and am about 40% of the way through that book (though my version is in C#). I’ve hand built a tokenizer and am starting to write my own parser.

It’s gotten me curious about programming languages, and I wanted to try my hand at building a brainfuck interpreter. Lets dive in.

Brainfuck

Brainfuck is an esoteric programming langauge. It’s designed to be confusing, hence the name. The language only consists of 8 characters, > < + - . , [ ]. With an internal structure defined by wikipedia as:

The brainfuck language uses a simple machine model consisting of the program and instruction pointer, as well as an array of at least 30,000 byte cells initialized to zero; a movable data pointer (initialized to point to the leftmost byte of the array); and two streams of bytes for input and output (most often connected to a keyboard and a monitor respectively, and using the ASCII character encoding).

Each character in the language is defined as:

< : increment the data pointer (to point to the next cell to the right)
> : decrement the data pointer (to point to the next cell to the left)
+ : increment (increase by one) the byte at the data pointer
- : decrement (decrease by one) the byte at the data pointer.
. : output the byte at the data pointer
, : accept on byte of input, storing its value in the byte at the data pointer
[ : if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the command after the matching ] command.
] : if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the command after the matching [ command.

Here is a program that prints out “Hello World”:

If this is your first esoteric programming language, this definitely throws you for a loop. Since this article is about documenting how to build an interpreter, here’s a great video describing brainfuck to anyone to wants a more visual representation.

So lets see some basic code examples.

Examples

If I wanted to write a single exclamation point, here is a program that would do that:

It uses the + character to add 1 to the current data pointer 33 times, 33 being the ASCII representation for an exclamation point. Then uses the . character to print that single character.

Here are three different programs that print out !?:

The first version generates and prints the exclamation pointer as before, then moves to the next cell and increments data pointer to 63, the ASCII representation for ?, and then prints it.

The second version reuses the cell of the exclamation mark, so it only needs to increment that cell 30 more times. 33 (!) + 30 = 63 (?)

The third version uses the [ and ] brackets to repeat sections of code resulting in smaller programs.

The Interpreter

I’ve named my interpreter Dizzy, because programming in brainfuck can make you dizzy.

Well that aside, there’s not a whole lot of complexity to the interpreter.

Lets start off by creating a class called Interpreter that will be interpreting our program.

It has three instance variables: 1. A byte array to hold any data we might need, 2. A pointer telling us where we are in that array, 3. The input converted into a char array.

Then lets create a scaffold of our Run method, which is a switch statement for each of the 8 valid characters in our language.

In brainfuck, any other characters are just ignored, so anything not in this set of 8 will just be skipped over.

Given our definition above, for > and <, we need to increment and decrement the pointer.

Then for + and -, we need to increment and decrement the current value in our tape referenced by the pointer.

Then our IO characters are also pretty simple:

Finally we need to implement our brackets. Brackets help us repeat or skip sections of a brainfuck program, kind of like a goto statement. That’s why the third program for writing !? was so much shorter, brackets allowed the same section code to be run multiple times.

The only complication here is nested brackets. For a program like [+[+]+]>+, which skips from the first open bracket to the last close bracket, we need to keep track which open/close brackets belong together.

We introduce an int called unmatchedBracketCounter, (defined outside the for loop) which tracks how many pairs of brackets we’ve encountered. If we’re looking for a ] and encounter another [, we know we will have to now pass two ] before we can stop.

Combining all these elements we end up with a single class that can interpret a brainfuck program.

Testing

Now for testing. As someone who codes for a living, I feel very comfortable writing programs in normal programming languages. Brainfuck programs are another matter.

Fortunately I found this great website which has brainfuck programs, can run brainfuck programs, and can generate brainfuck programs as well.

Here are some fun programs that I found on that website.

CALCULATE PI

This calculates Pi to the 15 decimal place. When run the output is 3.14070455282885, which the first 15 digits of PI are 3.14159265358979, which I am using an 8 bit cell, so it seems like I’m experiencing some overflows as called out in the program.

CALCULATE SQUARES

When run this programs outputs all squares up to 10000, 0, 1, 4, 9 16, …, 9801, 1000.

99 BOTTLES OF BEER

When run this prints out the 99 bottles of beer chanty, from 99 all the way to 0.

PRINT ONE ENTERED CHARACTER

And finally a program that takes advantage of user input. Most brainfuck programs that I found didn’t use the input character ,, I wrote one with the help of the text generator mentioned earlier.

Closing Thoughts

There you have it. A interpreter that will run brainfuck programs.

I definitely enjoyed writing this interpreter. The first one that I’ve written from scratch. It was a fun and pretty different programming challenge from what I’m used to.

I hope you enjoyed it and continue to experiment with things that you’re interested in.

Originally published at thesharperdev.com.

C# Design Patterns: The Visitor Pattern

Morgan Kenyon — Sun, 29 Sep 2019 10:35:04 +0000

My last article introduced expressions in C# and explained a bit why they were useful. Today I’m going to build upon that article and introduce you to the Visitor Pattern, a common pattern used when dealing with expressions. If you’re not familiar with expressions or a bit rusty, I would recommend reading the previous article first.

The Visitor Pattern

Wikipedia defines the visitor pattern as "the visitor design pattern is a way of separating an algorithm from an object structure on which it operates".

What does that mean? When I normally define classes in C#, they look something like this.

Inside of my class, I’m defining my data and my methods or algorithms that operate on my class.

But if you’re using the Visitor Pattern, you break apart the class and the methods into something like this.

Now the data and the methods are defined separately, decoupling them has advantages which we’ll see in a moment.

As a note, breaking apart the data and methods in this example really doesn’t do anything for you, also I’m not using the Visitor Pattern terminology, but we’ll explore that next.

Printing Expressions

The code that follows builds upon the example shown in this Wikipedia article.

Lets demo this pattern by defining expressions to represent simple mathematical equations and a visitor to print out our equations.

To start with our pattern, I’m going to define two interfaces. IExpressionVisitor defines what types of expressions our visitor supports. Anything inheriting from IExpression are the objects that are going to be “visited”. The Accept method is the standard name for the method that allows the visitor to be accepted into the IExpression class.

Next lets define our first expression called Literal. It’s responsibility is to hold the number values in our equations.

You’ll notice that it inherits from IExpression, and implements the Accept method, all it does it pass itself into the visitor by the this keyword.

Next I’ll need a Addition expression defined as follows.

I’m defining two IExpressions, Left and Right, to be the two expressions that will be added together.

Now that I have two expressions, I’m going to need a visitor to be able to visit those expressions and print out the equation.

Lets call our visitor InfixExpressionPrinter and give it the following implementation.

This has two methods for how to handle both of my expression types. If it’s a Literal, all I need is to print the value. If it’s an Addition, it generates the values of both the Left and Right expressions and adds them together.

Now lets put that all together in order to print out our expression.

I’m creating a simple Addition equation, calling the Accept method visits the entire expression and prints the equation represented by our expression tree. Running this prints (5+6), which reflects the equation we built with expressions.

We can also print out more complex expressions, such as the following.

Running this outputs (((5+6)+20)+(1+3)), also the mathematical representation of our expression.

The astute reader will notice that our expression printer prints equations in Infix notation. What if we wanted to print Prefix? Or Postfix?

This is really the power of the Visitor Pattern. Since the logic for printing isn’t contained in our expression classes, we’re free to add another printer as long as we inherit from the IExpressionVisitor method.

Lets define a printer for Prefix notation.

When the second example is run using the second equation the result is + + + 5 6 20 + 1 3. Creating a new visitor allows us to convert the same expression into a different output.

Benefits of the Visitor Pattern

As you can see in our examples, printing different forms of the equations doesn’t require any changes to our Literal or Addition classes. The Visitor Pattern allows some other class to define how to print expressions, and it hands off that responsibility to whoever implements the IExpressionVisitor interface.

This is a pretty trivial example of the Visitor Pattern. If you want to see an enterprise example of this pattern, look through the Entity Framework Core code base. It uses this pattern (and a lot more) to turn a Linq statement into a Database specific query.

Instead of simple classes like Literal, Addition, InfixExpressionPrinter and PrefixExpressionPrinter, they have complex classes like SelectExpression, ColumnExpression, OrderingExpression and SqlServerQuerySqlGenerator which contains this method:

That method looks pretty similar to the examples that we created in this article.

Entire SQL projects are devoted to converting expressions into each particular data store. Whether that be SQL Server, Sqlite, Oracle, Postgres or others.

Entity Framework Core obviously has a lot of complexities to it, but like most other software, it’s built upon principles or patterns that most of us can familiarize ourselves. The Visitor Pattern happens to be one of those patterns.

Closing Thoughts

I’ve heard it said that design patterns are “experience reuse”. As an industry, we encounter very common problems across technologies and business domains. Patterns exist to solve those problems that have been born from both pains and successes in the past.

Knowing Design Patterns helps us learn how to avoid making the same mistakes again. Design Patterns are great tools in the developer toolbox and I’m glad to have shared about one today.

Originally published on thesharperdev.com

Github Library

An Introduction to C# Expression Trees

Morgan Kenyon — Mon, 23 Sep 2019 17:14:11 +0000

Expression Trees are an interesting C# language feature that you might not have knowingly used before. Expression Trees are fundamental to Entity Framework being able to turn C# code into SQL queries. So if you’ve ever used Entity Framework then you’ve definitely taken advantage of this language feature.

For example, here is the SelectExpression class in the Entity Framework Core (EF Core) library, searching for the term Expression shows that is exists 652 times in this class, pretty important!

Lately I’ve been interested in how Entity Framework turns C# into SQL and wanted to write an article about Expressions to aid in my understanding of the subject.

As a note, there is a difference between Expression Trees and Expressions, but across the internet and in software, such as Entity Framework, you’ll find both words used to describe Expression Trees. Which makes it a bit confusing and a little hard to google. I'll mainly be using the term Expressions for the remainder of this article.

Why do we need Expressions?

Most of the time, the code we write is intended to be executed in the exact place that we’re writing it.

For example, this method is used to sum numbers.

Whenever this method is called with two numbers, it returns the sum. It always operates inside this method, inside of a C# runtime.

What if I were to tell you that I needed you to write some piece of code that was intended to be run somewhere else? Like a database?

You can’t pass code like this to a database (more realistically, some library that communicates with the database) and expect it to know what to do with it. You need a different way to represent code.

That is what Expression Trees or Expressions are for.

Expression trees represent code in a tree-like data structure, where each node is an expression, for example, a method call or a binary operation such as x < y. ~Microsoft Docs

Expressions are a different format to describe code. They’re a data structure that represents code. They’re also “portable” in the sense that Expressions can be passed around and some other piece of code can investigate it to see what it’s suppose to do.

Here’s an example of the earlier Sum method but now it’s in expression format.

It performs the same functionality, adds two numbers, but it’s defined completely differently. That difference gives it it’s “portability”. The visitor pattern is a common way to investigate an expression to figure out what it contains or means, which I hope to explore soon on this blog.

Both parameters are defined by a ParameterExpression which denotes the type. Those parameters get passed into a BinaryExpression which adds them. Then all three of those Expressions are passed into a Lambda Expression which results in an Expression<Func<int, int, int>>, which is a mouthful.

Expressions can’t be called directly, so in order to use it we need to compile the Expression. Which turns it back into a regular Func which can then be called and the sum returned.

I believe most anything that you can write as regular code can be written as an expression. I wouldn’t recommend it, but I believe it is possible.

Hello World Expression

What would Hello World look like if it was written in Expressions? Something like this.

Lets go through this line by line.

Line 3 defines our “Hello World” message as a constant of type string.

Lines 5-7 defines the call to the method to print the message. The Expression.Call() method takes in two arguments,

Information about the method (line 6), which consists of: the type the method exists on (Console), the method name* (WriteLine), then what are the parameters we can pass to this method, (1 parameter with type string).
The parameter (line 7).

Line 9 pushes that expression into a lambda expression.

Line 11 compiles that expression into an Action.

Line 13 runs the Action.

You’ll notice that the name of the method is a string, so there’s no compiler checking for you on that.

So that’s a Hello World example. Here are some examples of more expressions.

Print Message

Instead of printing “Hello World”, this expression can now print any arbitrary string. The main difference is we’re defining a ParameterExpression instead of a ConstantExpression.

Print Number

Now we’re printing any int. So we’ve updated some of our types and also combining defining our action expression and compiling it.

Finding Max Number

Here we are taking two ints and calling the Math.Max function. Notice that in this example we’re using a Func instead of an Action. Action is only defined for 0 or 1 parameters. Now that we have 2 parameters we have to use Func.

Calculate Slope

This one gets a bit more complicated, 4 parameters. It calculates the slope between two points on a line, (x1, y1) and (x2, y2), using the formula (y2-y1)/(x2-x1).

Extract Order Id

Now instead of dealing with primitives we’re dealing with an Order object that has the property OrderId. Notice that we have to define a MemberExpression to extract a member of a type.

Sum Order Costs

Then the last expression example for today, taking two Order objections and adding the cost for each one.

Final Thoughts

At first building expressions by hand is odd. The expression version definitely takes a lot longer to define, but those extra steps helps an expression be more usable than a line of code that you would find in a normal C# program.

I’m just getting my feet wet with Expressions and will continue to learn and blog about them here.

If you have any questions or observations I’d love to hear about them in the comments below.

Originally published on thesharperdev.com

Resources

An Introduction to Pure v. Impure Functions

Morgan Kenyon — Wed, 11 Sep 2019 17:34:45 +0000

Pure and Impure functions is a very important distinction in functional programming. Most of my university and early work experience was primarily in OOP languages (Java and C#) and I was never aware of this distinction.

Today I wanted to introduce this concept and how it can help write more testable and composable software.

Function Types

Any function is either pure or impure. Wikipedia states that a pure function has the following two properties:

It’s return value is the same for the same arguments.
It’s evaluation has no side effects.

So what exactly does that mean? Lets take the following function:

Given the same x and y, this function will always return the sum of those two ints. If x = 1 and y = 1, it will always return 2. If x = 100 and y = 100, it will always return 200.

But this function:

The output of this function now depends on a third variable z, which is not one of the arguments. Since the function could return a different result for the same inputs it’s now an impure function.

Or this next function:

The sum only depends on it’s inputs, which is good. There’s now a database call, which is a side effect. There’s also the possibility that the database operation can throw an exception. So the database call has introduced some complexity and side effects to our function. Which means it’s also an impure function.

The Testability of a Function

Why is it important to know the distinction between types of functions?

One big reason is that pure functions are inherently testable.

Say I’m your manager, and I tasked you with verify that the following two method’s logic was correct.

The AddPure method is almost trivial to test and verify that it’s working correctly.

On the other hand the AddImpure method presents some challenges.

Where is z defined at?
How can I initialize z?
Do I have to create a class or classes to verify this method?

Testing the AddImpure method is doable, we now have to jump through some hoops because of it’s impureness.

Or if we wanted to test the AddDb method.

We’d now have to deal with a database call in the middle of our function. In an object oriented language, dependency injection is usually what we rely on in order to remove dependencies when we test. Dependency injection allows us to change what type of Db our method is using. If we’re testing, here’s a mock db, if we’re running our app, here’s the real database.

In an object oriented language, that’s the recommended way to make functions testable. But that doesn’t mean it’s the only way to solve this problem.

A More Functional Approach

Lets take a step back and break down our AddDb function. What are its responsibilities?

Summing two numbers and returning the result
Saving the result to a database

Our function does two distinct things. When we are unit testing, what are we attempting to verify? Our unit test is only verifying that responsibility #1 is correct. We use dependency injection to avoid having to deal with responsibility #2.

That begs the question, if we’re only testing half of what our function is doing, and introducing tools in order to avoid dealing with the other half, can we refactor this function?

In languages that have functions as first class citizens, this is pretty easy to do. C# has the ability to define Functions, then pass those functions to methods. We could refactor our function into the following:

So whatever operation we’ve decided to do, that is now being defined outside of our function.

We’ve broken our single function into two functions. There are several great benefits from doing this.

The Sum function is now a pure function.
I can now test my Sum logic without worrying about dealing with the database.
I can also change the behavior of AddFunctional without modifying it. Which means we should rename the function to something more generic.

Because the AddFunctional takes in a function, any function that has the same signature can now be used in this method.

Suddenly my single method supports anything that can conform to the Func signature. Which helps the composability of my application.

Implications on Software Design and Architecture

If this information is new to you, you might be thinking to yourself, “lets make everything pure!” Unfortunately most of the useful things that applications do require using impure functions.

Things like saving and retrieving information to a database, making http requests, etc, those are all impure functions because they violate one or both of the conditions of pure functions.

When writing your application, you should strive to maximize the number of pure methods used. If it’s possible, implement something using a pure method rather than an impure method. Or refactor a single impure method into smaller methods where some are pure, like our database example.

Pure methods make your code easier to reason about and easier to test. Impure methods are usually always required, but knowing the distinction can lead to better software design.

Closing Thoughts

Pure v. impure methods wasn’t something I was aware of until I started learning a functional programming language (F#). Even though I use C# in my day job, learning functional programming techniques has helped me write better software.

In my next post I’ll expand a bit more on this topic. I’ll explain some of the implications and talk about what happens when we start chaining function calls together.

Originallly published at theshaperdev.com

Benchmarking and Exploring C#'s Dynamic Keyword

Morgan Kenyon — Mon, 26 Aug 2019 00:39:24 +0000

Today I wanted to explore and benchmark a C# feature that I've never used before, the dynamic type.

Dynamic v. Static Type Systems

A simple way to group programming languages is based on their type system. A statically typed language will enforce correct usage of types. Usually a compiler will check a types usage, and if you call a method that doesn't exist on a type or some other non allowable way, you'll get a compiler error. Think languages like C++, Java or C#.

On the other hand, a dynamically typed language only checks types at runtime. So if you're incorrectly calling a method that doesn't exist on a class, you won't find out until your application is running. Think languages like JavaScript, Python, Ruby or PHP.

We usually like to think of programming languages as being either dynamic or statically typed, and most languages push you towards one or the other. C# and Python are examples of languages that have the ability to do both. C# has a dynamic keyword that eliminates compile time checks and Python has recently introduced static type checking via mypy.

There are pros and cons to both type systems, I personally favor static typing. But C# gives you the freedom to use dynamic typing.

In my 5 years of professional programming I haven't run into a case yet where I have needed to use the dynamic keyword. But sometimes using the dynamic keyword and bypassing the compiler is really the only feasible option. But they do exist, and to quote the Microsoft docs:

Therefore, you do not have to be concerned about whether the object gets its value from a COM API, from a dynamic language such as IronPython, from the HTML Document Object Model (DOM), from reflection, or from somewhere else in the program. ~ Microsoft Docs

So if you happen to need it, how would you use it and how does it perform?

How to Use Dynamic

Using the dynamic keyword is super easy. Any time you would use a regular type or a var, just use dynamic instead.

Then you can continue to use your dynamic type in place of any other regular type.

The compiler will never throw an error on a dynamic type, but if you aren't careful your program might blow up at runtime if you're using it incorrectly.

Dynamic Performance

Lets try to get a glimpse at the performance characteristics of the dynamic keyword. I'm using the ever useful library BenchmarkDotNet. I've created a couple of examples to compare the performance of dynamic via static typed examples.

I'm summing an int, concatenating a string, then calling a method on both a local object then a local struct. To view and run the benchmark yourself please visit the github repo.

Running these benchmark gives us the following numbers:

The two most useful columns are the Mean and Allocated column. The Mean column indicates how long a benchmark took to run. The Allocated column indicates how much heap memory was allocated for a particular benchmark.

You can see that the dynamic performance was overall worse than actually using types.

For summing of numbers, dynamic was ~18x slower and allocated memory.

The string concat was roughly the same performance, which was a little surprising to me.

Then for the user benchmarks, it was easy to tell that dynamic is not the way to go.

Why is Dynamic Slower??

So overall, using dynamic is not very performant, but what about it makes it slower?

One way we could find out would be to investigate what code is actually compiled. Some features, like the dynamic keyword, extension methods, are natively supported in IL (Intermediate Language), which is what C# gets compiled down into. Before C# is transformed into IL code, it might be first be transformed into some other C# code. What transformations occur for dynamic keywords?

I took the liberty of installing dnSpy. dnSpy is a debugger and .NET assembly editor. It gives us a picture into what the compiler does with our source code.

If you download dnSpy, select the dll of this benchmarking library, it will convert the compiled benchmark back into C# for us to view. So what does it look like?

Dang, that's a lot of extra code the compiler had to generate. The convenience of using the dynamic keyword comes at the cost of all that code.

The SumOneTo100() method is basically the same as we originally wrote it. Which means what we wrote can be easily transformed into IL. But the DynamicSumOneTo100() is a freakin' mess. A lot of transformations had to occur before converting into IL.

I've never seen code like this before. Guessing from the example it seems to be dynamically adding the method that is needed right before it is called.

Our string concat method has even more changes to it, but ironically those changes didn't seem to impact performance as much.

Maybe there's just a one time setup cost of using dynamic types? Or summing numbers is a cheaper operation than concating strings, so it would make sense if there was a larger difference when summing numbers versus concating strings.

I reran the summing numbers benchmark with different values on N. Once when N = 100 (like last time), then also with N = 10,000. If using the dynamic type is just a one time setup, I would imagine that for the N = 10,000 the dynamic and non-dynamic version would be closer in performance.

So after running that benchmark, it turns out my one time setup cost theory was incorrect. The bad performance was roughly the same for a bigger value of N.

I don't really know why the performance of the string benchmark was a lot closer. If anyone out there can help explain why our string benchmark was roughly equivalent while our summing benchmark was drastically different I was love to learn.

Parting Thoughts

This might not be a feature you've ever used before, but it's interesting to know that it's there and what it's basic performance is like.

Overall, if you have a choice to use regular types or dynamic, always go with regular types. The compiler will check your code and then give you better performance.

If you run into a reason to use dynamic, by all means use it, but know that there are tradeoffs for the convenience of not having the compiler check your types.

I’m Morgan Kenyon. I’m a .NET developer working in the DFW area. I love solving a good problem and want to talking about the tech I use. If you found this article helpful or thought provoking leave a comment and lets connect over LinkedIn!

Github Repo

Using Suave and F# to Setup CRUD API Routes

Morgan Kenyon — Mon, 19 Aug 2019 00:51:44 +0000

F# is a community driven Functional-First programming language. It’s a multi-paradigm language and interops nicely with C#, but provides a lot of the functional features that make working with it great!

Lately I’ve spent some time learning F# and through F# discovered Suave:
Suave is a simple web development F# library providing a lightweight web server and a set of combinators to manipulate route flow and task composition.

As stated, Suave is a web framework that can be used to create apis. When I was researching Suave I didn’t find a great article documenting all the basic CRUD actions that should be used in a REST API.

This is my attempt to pass along the knowledge I had to piece together over several internet resources. This is not an end to end app, it just documents how to use Suave to setup the necessary routes needed for a simple CRUD app.

All code will be located on a github repo. One of my friends introduced me to Suave . Some of the things he did on his personal project definitely helped me get started in Suave. He's also further down the F# rabbit hole, so check out his project if you're interested.

F# and Functional Programming Languages

This article isn’t an introduction to F#. If you’re never encountered the language before, some of the examples here might seem a bit different.
If so, welcome to functional programming languages. My short time learning F# has been quite an eye opening experience.

Throughout my professional life I’ve used both Java and C#. But I incorrectly assumed that best practices I learned for Java and C# were overall programming best practices. When in reality they were best practices for an object oriented language.

Functional languages have a very different way of looking at the world. When you start learning a functional language everything is new and the terms can be intimidating.

Some people get scared off by that fact, but I think it’s worth the time to embrace and learn a new paradigm. That will really only benefit you in the long run.

If you’re new to functional and F# and want to get started, here is a hour long conference talk called Functional Design Patterns by Scott Wlaschin. Scott also blogs at fsharpforfunandprofit.com which is a great resource when you’re getting started.

With that short functional evangelism message behind us, lets dive in.

Creating an API

Open up your IDE of choice, I’m using Visual Studio, and create an F# Console App. Use whatever name you prefer, and after creating you should see something similar to the following in your IDE.

Next we’re going to be adding our dependencies. We’ll need to add Suave and Newtonsoft.Json to our project. Right click on “Dependencies” => “Manage Nuget Packages”, then searching for the two nuget packages and installing them.

Modify the Program.fs to be the following to create your first route.

Running that project should open up a console that says it launched on 127.0.0.1:8080. If that’s the case for you, you can point your web browser to http://localhost:8080/ and you should see your “Hello World” message.

I’m also including a postman collection for all routes contained in this example, which is also located on the github repo.

With that simple example out of the way. Lets demo a full CRUD architecture for an answer entity.

Answer CRUD

So, I could talk a lot more about the four different routes, Create, Read, Update and Delete, or I could just show you the code. So here’s how I would accomplish setting up routes in Suave for all four actions.

You can use the Postman collection to play around with each route.

You’ll notice that I have two types, one for new answers and one for answers that already exist.

You’ll see extensive use of the F# forward pipe operator, “|>”. It’s shorthand for “get the result of the previous line and pass it into the function on this line”.

Those two examples perform the same work, but using the forward pipe operator is much more concise and I think is easier to read.

If you need to read variables from the path, like I do in the Get answer and Delete answer routes. You’ll need to use pathScan instead of path when defining the route.

Suave does enforce the data types, so if I attempted to pass a string instead of an int Suave wouldn’t be able to find that route because I’m limiting these routes to be an int.

And lastly I’m a huge fan of how succinct F# is. Once you get used to reading and writing F#, everything can usually be expressed in minimal characters. Writing this in C# would be at least twice as many lines of code, probably more.

Final Thoughts

I enjoyed learning Suave and I hope this article helps you get started faster than I was able to. At the moment I’m really enjoying F# and all it’s functional goodness. Stay tuned for future posts on F# and general dotnet programming!

I’m Morgan Kenyon. I’m a .NET developer working in the DFW area. I find both C# and F# great languages backed by a great ecosystem. I love solving problems and want to continue talking about the tech I use. If you found this article helpful or thought provoking leave a comment and lets connect over LinkedIn!

Github Repo

Benchmarking The Yield Statement in C#

Morgan Kenyon — Tue, 13 Aug 2019 03:24:14 +0000

Lately I've been interested in benchmarking the features of C# that I use everyday. I've found a lot of my thoughts are based on assumptions instead of facts. Today I'm going to be diving into the Yield statement in C# and seeing how it compares against explicitly creating an enumeration.

Code is located via the project's Github repo to see the full benchmark and run it yourself.

BenchmarkDotNet

Attaining accurate and valid benchmark results is not trivial. Earlier in my career I resorted to manually timing if I wanted to get a "benchmark." But that's a pretty naive approach to benchmarking. Luckily there's a great library called BenchmarkDotNet which makes benchmarking easy and does all the hard things for you.

Check their website or an article I wrote for an introduction to the library.

Yield Statement

So what is the yield statement? The Microsoft docs say:

Using yield to define an iterator removes the need for an explicit extra class (the class that holds the state for an enumeration, see IEnumerator for an example) when you implement the IEnumerable and IEnumerator pattern for a custom collection type.

Take a look at the following example:

Both methods return an IEnumerable, but using the yield statement removes the need to create a list to hold our values as we iterate.

When I first saw this I didn't really know what to make of it. How did a simple yield statement transform into a IEnumerable return type?

But after walking through some examples, I began to understand the power of using yield.

Yield Example

Take a look at the following example, what would you expect the output to be?

20 printed lines? 10 for the "Inserting X" and 10 more for the "Yielding X"?

When run, the following is printed:

Inserting 0
Inserting 1
Inserting 2
Inserting 3
Inserting 4
Inserting 5
Inserting 6
Inserting 7
Inserting 8
Inserting 9
Yielding 0
Yielding 1

If you've never used yield before, take a moment to think through what might be happening? We have declared two loops from 0-9, but only one generated all the values.

What allowed yield to stop after 1? Whatever it was, it allowed us to avoid generating 80% of the numbers.

Why does this happen

This behavior occurs because yield only enumerates values when needed. Instead of generating all 10 values, then returning those values for FindOne() to loop over. Our yield method only returns the next value whenever it is requested.

That's worth restating. Yield only returns the next value in the iteration when it is requested. If it's never requested, it's never returned.

In our example, FindOne() enters the foreach loop and starts the first loop. Calls the GetIEnumerabYield() method, the first time through i is 0, it hits the yield statement, returns 0 and pauses there. FindOne() gets the 0, that isn't the value it's looking for, so onto the next iteration of FindOne(). On the second iteration of FindOne(), it calls GetIEnumerableYield() again. GetIEnumerableYield() begins from the yield statement, generates the next value in the sequence, 1, hits the yield statement, returns 1 and pauses again. FindOne() has the value it needs and breaks.

The FindOne() and GetIEnumerableYield() methods are in constant communication. GetIEnumerableYield() is generated values as needed instead of generating them all beforehand.

If whatever is being created is an expensive operation, using yield could potentially save your program a lot of work.

Second Yield Example

Here's another example to get your brain working.

Does this method ever stop running?

Because we're using a yield statement, yes.

Even though we're in an infinite while loop, the FindOne() method will stop requesting values after finding the 1. Because yield methods only generate values as needed, only two iteration of the while loop will ever be performed.

I hope now you're beginning to see some of the possibilities of using a yield statement.

Benchmarking Results

Now that we know a bit about what yield is and how it works, lets turn our attention to answering the question of what it's performance is.

Even though this can be a useful feature, if it's slower we're probably not going to use it. So lets benchmark it.

Here's a simple version of my benchmark. We're basically just going to be generating numbers. One version creates a list, adds to it and returns it. The other just yields those same values. I've created a couple more Benchmarks like this, each one having another layer of nested method calls. If you're curious, all code is on my github.

If I run all my benchmarks, I get the following result:

The important columns to pay attention to is "Mean" and "Allocated". "Mean" is the time it took to run the benchmarks and "Allocated" is the amount of memory used.

For all but the first one benchmark, yield was significantly faster and used significantly less memory. Especially as the amount of work got bigger, yield was by far the better choice.

I was not expecting this big a difference between the two different methods. This benchmark surprised me a bit and I'm going to use yield more in the future because of these results.

Debugging Note

It's worth noting that the one downside I find when using yield is it makes debugging harder. This has honestly been the reason that I've shied away from using it in the past.

At no point is there a list that contains all my values for me to investigate. That list doesn't ever get created, only individual values are yielded when needed.

To be honest, If I'm going to be debugging something for any length of time, sometimes I'll comment out the yield statements and replace them with regular lists. Doing that makes my debugging easier and I can just change it back before checking code in.

Probably not the best habit, but dealing with yields while debugging isn't the easiest thing to do.

If anyone has better strategies, I'd love to hear it.

Parting Thought

Using a yield statement instead of explicitly creating enumerations has benefits of both speed and performance. But I've found a tradeoff between readability and debug-ability.

Before benchmarking yield, I had no clue that there was this much of a difference between techniques. Which goes to show why you should benchmark as a developer. Because what you know or assume may just be false.

Thanks for reading!