Identify Side Effects And Refactor Fearlessly

When we refactor code how can we be confident that we don't break anything?

3 of the most important things that allow us to refactor fearlessly are:

  • Side effect free - or pure - expressions
  • Statically typed expressions
  • Tests

In this article we will solely focus on the aspect of side effects and strictly speaking on how to identify them. Being able to identify side effects in our programs clearly is the precondition for eliminating them.

Why avoid side effects?

Continue reading →

PureScript Case Study And Guide For Newcomers

Have you ever wanted to try out PureScript but were lacking a good way to get started?

If you

  • Have some prior functional programming knowledge - maybe you know Haskell,Elm,F#,or Scala,etc.
  • Want to solve a small task with PureScript
  • And want to get started quickly

This post is for you!

In this post we will walk through setting up and implementing a small exemplary PureScript application from scratch.

Continue reading →

Elm And The Algorithm Of Music

In this article I would like to present a minimal implementation of a music data type and everything that is needed to turn that into audible sound from an Elm application.

We will see how to transcribe an existing composition - an excerpt from Chick Corea's Children's Songs No. 6 - and listen to the result right here,embedded in this article.

From a music data type to performance

My colleague Jonas recently pointed out the presentation Making Algorithmic Music by Donya Quick to me. Donya Quick shows how she uses the Haskell library Euterpea to produce algorithmic music.

It got me really excited about the idea of porting this to Elm and to be able to use this in web applications.

In the following we will see the core data types and algorithms from Euterpea ported to Elm. To focus on the core concepts the implementation is stripped down to the minimum that is required to transcribe and perform an existing polyphonic piece of music (for a single instrument).

Continue reading →

Interactive Command Line Applications In Scala –Well Structured And Purely Functional

This post is about how to implement well structured,and purely functional command line applications in Scala using PureApp.

PureApp originated in an experiment while refactoring out some glue code of an interactive command line application. At the same time it was inspired by the Elm Architecture Pattern,and scalaz's SafeApp,as well as scalm.

To show the really cool things we can do with PureApp,we will implement a self-contained example application from scratch.

This application translates texts from and into different languages. And it provides basic user interactions via the command line.

The complete source code is compiled with tut. Every output (displayed as code comments) is generated by tut.
Continue reading →

How To Use Applicatives For Validation In Scala And Save Much Work

In this post we will see how applicatives can be used for validation in Scala. It is an elegant approach. Especially when compared to an object-oriented way.

Usually when we have operations that can fail,we have them return types like Option or Try. We sequence operations and once there is an error the computation is short circuited and the result is a None or a Failure.

Applicatives allow us to compose independent operations and evaluate each one. Even if an intermediate evaluation fails. This allows us to collect error messages instead of returning only the first error that occurred.

A classic example where this is useful is the validation of user input. We would like to return a list of all invalid inputs rather than aborting the evaluation after the first error.

Scala Cats provides a type that does exactly that. So let's dive into some code and see how it works.

Continue reading →

Parsers in Scala built upon existing abstractions

After some initial struggles,the chapter Functional Parsers from the great book Programming in Haskell by Graham Hutton,where a basic parser library is built from scratch,significantly helped me to finally understand the core ideas of parser combinators and how to apply them to other programming languages other than Haskell as well.

While I recently revisited the material and started to port the examples to Scala I wasn't able to define a proper monad instance for the type Parser[A].

The type Parser[A] alias was defined like this:

type Parser[A] = String =>Option[(A,String)] // defined type alias Parser 

To test the monad laws with discipline I had to provide an instance of Eq[Parser[A]]. Because Parser[A] is a function,equality could only be approximated by showing degrees of function equivalence,which is not a trivial task.

Also the implementation of tailRecM was challenging. (I couldn't figure it out.)

Using existing abstractions

Continue reading →

Strongly Typed Configuration Access With Code Generation

Most config libraries use a stringly typed approach.

Some handle runtime failures due to invalid configuration schemas by leveraging data types like Option or Result to represent missing values or errors. This allows us to handle these failures by either providing default values or by providing decent error messages.

This is a good strategy that we should definitely stick to.

However,the problem with default values is that we might not even notice if the configuration is broken. This could potentially fail in production. In any case an error e.g. due to a misspelled config property will be observable at runtime at the earliest.

Wouldn't it be a great user experience (for us developers) if the compiler told us if the configuration schema is invalid? Even better,imagine we could access the configuration data in a strongly typed way like any other data structure,and with autocompletion.

Moreover,what if we didn't have to write any glue code,not even when the configuration schema changes?

This can be done with the costs of an initial setup that won't take more than probably around 5 minutes.

Continue reading →

Error and state handling with monad transformers in Scala

In this post I will look at a practical example where the combined application (through monad transformers) of the state monad and the either monad can be very useful.

I won't go into much theory,but instead demonstrate the problem and then slowly build it up to resolve it.

You don't have to be completely familiar with all the concepts as the examples will be easy to follow. Here is a very brief overview:

Continue reading →

Use lambdas and combinators to improve your API

If your API overflows with Boolean parameters,this is usually a bad smell.

Consider the following function call for example:

toContactInfoList(csv,true,true) 

When looking at this snippet of code it is not very clear what kind of effect the two Boolean parameters will have exactly. In fact,we would probably be without a clue.

We have to inspect the documentation or at least the parameter names of the function declaration to get a better idea. But still,this doesn't solve all of our problems.

The more Boolean parameters there are,the easier it will be for the caller to mix them up. We have to be very careful.

Moreover,functions with Boolean parameters must have conditional logic like if or case statements inside. With a growing number of conditional statements,the number of possible execution paths will grow exponentially. It will become more difficult to reason about the implementation code.

Can we do better?

Sure we can. Lambdas and combinators come to the rescue and I'm going to show this with a simple example,a refactoring of the function from above.

This post is based on a great article by John A De Goes,Destroy All Ifs — A Perspective from Functional Programming.

I'm going to take John's ideas that he backed up with PureScript examples and present how the same thing can be elegantly achieved in Scala.

Continue reading →

Modelling API Responses With sbt-json –Print Current Bitcoin Price

I'm currently working on an sbt plugin that generates Scala case classes at compile time to model JSON API responses for easy deserialization especially with the Scala play-json library.

The plugin makes it possible to access JSON documents in a statically typed way including auto-completion. It takes a sample JSON document as input (either from a file or a URL) and generates Scala types that can be used to read data with the same structure.

Let's look at a basic example,an app that prints the current Bitcoin price to the console.

Continue reading →

'https://fonts.googleapis.com/css?family=Droid+Sans|Droid+Sans+Mono|Open+Sans:400,600,700';.elm-music-play-button,.elm-music-stop-button{margin:2px;}span.n{color:#96C71D;}table.pre,pre.fssnip,pre{line-height:13pt;border:1px solid #d8d8d8;border-collapse:separate;white-space:pre;font:9pt'Droid Sans Mono',consolas,monospace;width:90%;margin:10px 20px 20px;background-color:#212d30;padding:10px;border-radius:5px;color:#d1d1d1;max-width:none;}.shariff{display:block !important;clear:both}.shariff ul{display:flex;flex-direction:row;flex-flow:row wrap;padding:0 !important;margin:0 !important}.shariff li{height:35px;box-sizing:border-box;list-style:none !important;overflow:hidden !important;margin:5px !important;padding:0 !important;text-indent:0 !important;border-left:0 none !important}.shariff a{position:relative;display:block !important;height:35px;padding:0;margin:0;box-sizing:border-box;border:0;text-decoration:none;background-image:none !important;text-align:left;box-shadow:none;cursor:pointer}.shariff .shariff-icon svg{width:32px;height:20px;padding:7px 1px;box-sizing:content-box !important}.shariff-button::before{content:none !important}.shariff .shariff-buttons.theme-round li{width:35px !important;height:35px;border-radius:50%;margin:5px}.shariff .theme-round a{position:relative;height:35px;border-radius:50%}.shariff .theme-round .shariff-icon svg{display:block;margin:auto;padding:8px 1px}.shariff .theme-round .shariff-icon svg path{fill:#fff}.shariff.shariff-align-flex-start ul{justify-content:flex-start;align-items:flex-start}.widget .shariff.shariff-widget-align-flex-start ul{justify-content:flex-start;align-items:flex-start}.widget .shariff li{border:0;font-weight:400}.widget .shariff .theme-default a,.widget .shariff .theme-color a,.widget .shariff .theme-grey a,.widget .shariff .theme-round a{color:#fff;display:block;font-weight:400}@media only screen and (max-width:360px){.shariff .shariff-buttons li{width:35px}.shariff .shariff-buttons .shariff-icon svg{display:block;margin:auto}}@media only screen and (min-width:361px){.shariff .shariff-buttons li{width:125px}}@media screen{@font-face{font-family:'FontAwesome';src:url(/wp-content/themes/editor/inc/fontawesome/fontawesome-webfont.eot);src:url(/wp-content/themes/editor/inc/fontawesome/fontawesome-webfont.eot) format('embedded-opentype'),url(/wp-content/themes/editor/inc/fontawesome/fontawesome-webfont.woff) format('woff'),url(/wp-content/themes/editor/inc/fontawesome/fontawesome-webfont.ttf) format('truetype'),url(/wp-content/themes/editor/inc/fontawesome/fontawesome-webfont.svg) format('svg');font-weight:normal;font-style:normal;}.fa{display:inline-block;font-family:FontAwesome;font-style:normal;font-weight:normal;line-height:1;-webkit-font-smoothing:antialiased;-moz-osx-font-smoothing:grayscale;}@-moz-keyframes spin{0%{-moz-transform:rotate(0deg);}100%{-moz-transform:rotate(359deg);}}@-webkit-keyframes spin{0%{-webkit-transform:rotate(0deg);}100%{-webkit-transform:rotate(359deg);}}@-o-keyframes spin{0%{-o-transform:rotate(0deg);}100%{-o-transform:rotate(359deg);}}@keyframes spin{0%{-webkit-transform:rotate(0deg);transform:rotate(0deg);}100%{-webkit-transform:rotate(359deg);transform:rotate(359deg);}}.fa-times:before{content: "\f00d";}.fa-folder:before{content: "\f07b";}.fa-folder-open:before{content: "\f07c";}.fa-navicon:before,.fa-reorder:before,.fa-bars:before{content: "\f0c9";}#simple-social-icons-2 ul li a,#simple-social-icons-2 ul li a:hover,#simple-social-icons-2 ul li a:focus{background-color:#999 !important;border-radius:3px;color:#fff !important;border:0px #fff solid !important;font-size:18px;padding:9px;}}

Functional Monadic Parsers ported to C#

While taking the MOOC Introduction to Functional Programming by Erik Meijer on edX the current lecture greatly increased my interest in functional parsers. Functional parsers are about the essence of (functional) programming because they are about the concept of composition which is one of the core concepts of programming whatsoever.

The content of the lecture is closely related to the chapter 8 Functional Parsers of the book Programming in Haskell by Graham Hutton. It starts out with the definition of a type for a parser and a few very basic parsers.

I'm totally amazed by the simplicity, the elegance and the compositional aspect of these examples. I find it impressive how primitive but yet powerful these simple parsers are because they can easily be combined to form more complex and very capable parsers.

As an exercise, out of curiosity, and because of old habits I implemented the examples from the book in C#.

At the end of this post there will be an ultimate uber-cool parser example of a parser for arithmetic expressions.

The complete code from this post can be found here on GitHub.

Here is what I got:

The parser type

The type is just a function that takes a string as input and returns a list of tuples of a value of any type and a string:

public delegate List<Tuple<T, String>> Parser<T>(String inp);

The first item of the tuple represents a parsed value and the second item is the remaining unconsumed part of the input string. The fact that the return type is a list indicates that the result can also be empty if the parser fails. Otherwise, if the parser succeeds, the result will always be a singleton list.

Basic parsers

Here are the three most basic parsers.

Return always succeeds and returns the value that it was instantiated with as well as the unconsumed input string.

Failure always fails and therefore returns an empty list.

Item returns the first character of the input string as well as the remaining unconsumed input.

public static Parser<T> Return<T>(T v)
{
    return inp => new List<Tuple<T, string>> { Tuple.Create(v, inp) };
}

public static Parser<T> Failure<T>()
{
    return inp => new List<Tuple<T, string>>();
}

public static readonly Parser<char> Item = 
    inp => String.IsNullOrEmpty(inp)
        ? Failure<char>()(inp)
        : Return(inp[0])(inp.Substring(1));

Instead of calling the parsers directly we will use an application function Parse to abstract from the representation of parsers:

public static List<Tuple<T, string>> Parse<T>(this string input, Parser<T> p)
{
    return p(input);
}

Note: In C# we don't really need this. I think, in Haskell this is needed because the parsers will be instances of the Monad type class.

Sequencing

Next we need a function to combine multiple parsers. This can be done with Bind which takes a parser and a function that returns another parser based on the result of the first parser. If the first parser fails, the whole computation will fail. Otherwise the function will be applied to the result of the first parser and return a parser that then will be applied to the unconsumed remaining input string.

public static Parser<T2> Bind<T1, T2>(this Parser<T1> p, Func<T1, Parser<T2>> f)
{
    return inp =>
    {
        var result = inp.Parse(p);
        return !result.Any() 
            ? Failure<T2>()(inp)
            : result.First().Item2.Parse(f(result.First().Item1));
    };
}

Hers is an example:

var p = Parsers.Item.Bind(
        x => Parsers.Item.Bind(
            _ => Parsers.Item.Bind(
                z => Parsers.Return(new string(new[] { x, z })))));

var result = "abc".Parse(p); 
Check.That(result).ContainsExactly(Tuple.Create("ac", String.Empty));                

LINQ query syntax

Now I added two functions Select and SelectMany to get some LINQ syntax sugar.

By adding Select the Parser<T> type becomes a Functor because now we can map functions over it. The function will be applied to the inner value when the parser is applied.

public static Parser<TResult> Select<TSource, TResult>(this Parser<TSource> source, Func<TSource, TResult> selector)
{
    return inp =>
    {
        var result = inp.Parse(source);
        return !result.An
            ? Failure<TResult>()(inp)
            : Return(selector(result.First().Item1))(result.First().Item2);
    };
}

SelectMany is needed so that we can use the LINQ query syntax instead of using Bind which similar to the do-Notation in Haskell.

public static Parser<TResult> SelectMany<TSource, TValue, TResult>(this Parser<TSource> source, Func<TSource, Parser<TValue>> valueSelector, Func<TSource, TValue, TResult> resultSelector)
{
    return source.Bind(s => valueSelector(s).Select(v => resultSelector(s, v)));
}

Here is an example of the use of the LINQ query syntax:

var p = 
    from x in Parsers.Item
    from _ in Parsers.Item
    from z in Parsers.Item
    select new string(new []{x,z});

var result = "abc".Parse(p); 
Check.That(result).ContainsExactly(Tuple.Create("ac", String.Empty));

Choice

Another way of combining parsers is to apply one parsers and if it fails apply another one with the Choice function:

public static Parser<T> Choice<T>(this Parser<T> p, Parser<T> q)
{
    return inp =>
    {
        var result = inp.Parse(p);
        return !result.Any()
            ? inp.Parse(q)
            : result;
    };
}

Derived primitives

We can now create other simple parsers by combining what we have so far.

First we define a parser that takes a predicate and parses the first character if the predicate holds:

 public static Parser<char> Sat(Predicate<char> p)
{
    return Item.Bind(c => p(c) ? Return(c) : Failure<char>());
}

Now we can combine Sat to create single character parsers for numeric, upper and lower case, alphabetic, alphanumeric or specific characters:

public static readonly Parser<char> Digit = Sat(Char.IsDigit);

public static readonly Parser<char> Lower = Sat(Char.IsLower);

public static readonly Parser<char> Upper = Sat(Char.IsUpper);

public static readonly Parser<char> Letter = Sat(Char.IsLetter);

public static readonly Parser<char> AlphaNum = Sat(Char.IsLetterOrDigit);

public static Parser<char> CharP(char c)
{
    return Sat(x => x == c);
}

The parser CharP can now be composed to a parser that matches a string:

public static Parser<string> StringRec(string str)
{
    return String.IsNullOrEmpty(str)
        ? Return(String.Empty)
        : from a in CharP(str[0])
          from b in StringP(str.Substring(1))
          from result in Return(str)
          select result;
}

Also two very useful parsers are Many and Many1 that apply a parser as many times as possible, where Many allows zero or more and Many1 requires at least one successful application.

public static Parser<List<T>> Many<T>(this Parser<T> p)
{
    return p.Many1().Choice(Return(new List<T>()));
}

public static Parser<List<T>> Many1<T>(this Parser<T> p)
{
    return p.Bind(v => p.Many().Bind(vs => Return(new List<T> { v }.Concat(vs).ToList())));
}

The problem with recursion

In C# we have a little problem here. StringRec is defined as a recursive function and Many and Many1 are defined as mutually recursive functions. That means that they are defined in terms of each other. This is a beautiful and elegant thing. But since the C# compiler is not very good at supporting recursive structures, stack overflow exceptions are likely to happen already with relatively small input strings (> a few thousand characters).

Therefore we have to define those functions as non-recursive.

Here is another non-recursive version of Many:

public static Parser<List<T>> Many<T>(this Parser<T> p)
{
    return inp =>
    {
        var state = Tuple.Create(new List<T>(), inp);

        while (true)
        {
            var newState = p(state.Item2);
            if (!newState.Any())
                break;
            state = Tuple.Create(state.Item1.Concat(new[] { newState.First().Item1 }).ToList(), newState.First().Item2);
        }

        return Return(state.Item1)(state.Item2);
    };
}

This looks almost like an unfold operation over the input string. But I couldn't really figure out how to refactor out a yet underlying pattern here. I'm not sure if that is possible at all or makes sense. (Maybe the list concatenation can be abstracted out?)

The non-recursive string parser looks like this:

public static Parser<string> StringP(string str)
{
    return inp => !inp.StartsWith(str)
        ? Failure<string>()(inp)
        : Return(str)(inp.Substring(str.Length));
}

Identifiers, numbers and spaces

Now we can define parsers for identifiers, numbers and spaces:

public static readonly Parser<int> Nat = Digit.Many1().Bind(n => Return(Int32.Parse(String.Concat(n))));

public static readonly Parser<string> Ident =
    from c in Lower
    from cs in AlphaNum.Many()
    from result in Return(String.Concat(new[] {c}.Concat(cs)))
    select result;

public static readonly Parser<Unit> Space = Sat(Char.IsWhiteSpace).Many().Select(x => Unit.Value);

Handling spacing

To be able to ignore arbitrary number of spaces before or after tokens to be parsed we define a parser Token:

public static Parser<T> Token<T>(this Parser<T> p)
{
    return
        from before in Space
        from t in p
        from after in Space
        from result in Return(t)
        select result;
}

Now we can combine Token with other parsers:

public static readonly Parser<string> Identifier = Ident.Token();

public static readonly Parser<int> Natural = Nat.Token();

public static Parser<string> Symbol(string xs)
{
    return inp => inp.Parse(StringP(xs).Token());
}

Example: Parsing a list of integers

Now the first example of a useful parser is a parsers for non-empty lists of integers (in Haskell syntax) that ignores spacing around tokens. A correct example of this syntax could be this:

[ 1,  2    , 3,  4 ,   5   ]

We can combine the parser like this:

var p =
    from ign1 in Parsers.Symbol("[")
    from n in Parsers.Natural    
    from ns in (from ign2 in Parsers.Symbol(",") from n2 in Parsers.Natural select n2)
                        .Many()
    from ign3 in Parsers.Symbol("]")
    select (new[] { n }.Concat(ns));

var result = "[ 1,  2    , 3,  4 ,   5   ]".Parse(p);

Check.That(result.First().Item1).ContainsExactly(1, 2, 3, 4, 5);

// this shoudld fail
var result2 = "[1,2,]".Parse(p);
Check.That(result2).IsEmpty();

Example 2: Parsing arithmetic expressions

The next example will be a parser for arithmetic expressions with addition and multiplication like this or 2 + 3 * 4 or this (2 + 3) * 4.

In my opinion, it is the ultimate uber-cool parser example because it really shows the power of the composability of parsers and FP in general.

Grammar

The grammar for these kinds of expressions looks like this :

 expr ::= term (+ expr | \epsilon) \

 term ::= factor (* term | \epsilon) \

 factor ::= (expr) | nat \

 nat ::= 0 | 1 | 2 | \dots \

Implementation

Expr, Term and Factor are defined in terms of each other. Therefore the implementation is recursive.

What is really remarkable is that this parser tuple of Expr, Term and Factor is only composed of other general purpose primitives!

public static Parser<int> Expr()
{       
    return     
        from t in Term()
        from r in
           (from _ in Parsers.Symbol("+")
            from e in Expr()
            from r in Parsers.Return(t+e)
            select r)
                .Choice(Parsers.Return(t))
        select r;
}

public static Parser<int> Term()
{
    return
        from f in Factor()
        from r in
           (from _ in Parsers.Symbol("*")
            from t in Term()
            from r in Parsers.Return(f*t)
            select r)
                .Choice(Parsers.Return(f))
        select r;
}

public static Parser<int> Factor()
{
    return
       (from ign1 in Parsers.Symbol("(")
        from e in Expr()
        from ign2 in Parsers.Symbol(")")
        from r in Parsers.Return(e)
        select r)
            .Choice(Parsers.Natural);
}

Also, please note that there is an obvious, visible, direct mapping between the grammar and the implementation.

Here are a few tests:

[TestCase("42", 42)]
[TestCase("(((((42)))))", 42)]
[TestCase("1+1", 2)]
[TestCase("(1+1)", 2)]
[TestCase("1*1", 1)]
[TestCase("1*2", 2)]
[TestCase("(1*2)", 2)]
[TestCase("2*3+4", 10)]
[TestCase("2*(3+4)", 14)]
[TestCase("2 * 3 +  4", 10)]
[TestCase("2*(     3+ 4)  ", 14)]
[TestCase("2*3-4", 6)] // leaves "-4" unconsumed
[TestCase("((1))*(2+(((3)))*(4+(((5))+6))*(((7*8)))+9)", 2531)]
public void ArithmeticExpressions_should_succeed(string inp, int expected)
{
    var result = inp.Parse(ArithmeticExpressions.Expr());
    Check.That(result.First().Item1).IsEqualTo(expected);
}

[TestCase("-1")]
[TestCase("()")]
[TestCase("(5")]
[TestCase("(1+2")]
[TestCase("(1+2()")]
public void ArithmeticExpressions_should_fail(string inp)
{
    var result = inp.Parse(ArithmeticExpressions.Expr());
    Check.That(result).IsEmpty();
}