fparsec_exercism.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Solving the Protein Translator problem using F# and FParsec\n",
        "\n",
        "This article/workbook is my attempt to solve the [Protein Translation Problem](https://exercism.io/tracks/fsharp/exercises/protein-translation) on _exercism.io_.\n",
        "\n",
        "\n",
        "Last week, I tried this problem using Haskell (you can see the solution [here](https://github.com/tkshill/protein-translation/blob/master/src/ProteinTranslation.hs)) as an exploration of point free style and composition.\n",
        "\n",
        "So let's now attempt this problem another way, using [FParsec](https://www.quanttec.com/fparsec/), a fully functional **parser combinator** library.\n",
        "\n",
        "Without getting too much into the details, Parser Combinator libraries operate on the principle of building parsers for large, complex, or intricate data structure, by _combining_ smaller parsers together.\n",
        "\n",
        "So let's jump in."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Describing the problem space\n",
        "\n",
        "(Taken from exercism):\n",
        "\n",
        "RNA can be broken into three nucleotide sequences called codons, and then translated to a polypeptide like so:\n",
        "\n",
        "RNA: \"AUGUUUUCU\" => translates to\n",
        "\n",
        "Codons: \"AUG\", \"UUU\", \"UCU\" => which become a polypeptide with the following sequence =>\n",
        "\n",
        "Protein: \"Methionine\", \"Phenylalanine\", \"Serine\"\n",
        "\n",
        "There are also three terminating codons (also known as 'STOP' codons); if any of these codons are encountered (by the ribosome), all translation ends and the protein is terminated.\n",
        "\n",
        "All subsequent codons after are ignored, like this:\n",
        "\n",
        "RNA: \"AUGUUUUCUUAAAUG\" =>\n",
        "\n",
        "Codons: \"AUG\", \"UUU\", \"UCU\", \"UAA\", \"AUG\" =>\n",
        "\n",
        "Protein: \"Methionine\", \"Phenylalanine\", \"Serine\"\n",
        "\n",
        "Note the stop codon \"UAA\" terminates the translation and the final methionine is not translated into the protein sequence.\n",
        "\n",
        "Below are the codons and resulting Amino Acids needed for the exercise.\n",
        "\n",
        "\n",
        "AUG -> Methionine\n",
        "\n",
        "UUU, UUC -> Phenylalanine\n",
        "\n",
        "UUA, UUG -> Leucine\n",
        "\n",
        "UCU, UCC, UCA, UCG -> Serine\n",
        "\n",
        "UAU, UAC -> Tyrosine\n",
        "\n",
        "UGU, UGC -> Cysteine\n",
        "\n",
        "UGG -> Tryptophan\n",
        "\n",
        "UAA, UAG, UGA -> STOP\n",
        "\n",
        ""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Defining our goal\n",
        "\n",
        "To call this solution solved, our requirements are as follows:\n",
        "- Define a function `proteins` that accepts a `string`, and returns an [Option type](https://fsharpforfunandprofit.com/posts/the-option-type/) which either produces a List of Strings representing our proteins or `None`. This is the original goal of the exercise.\n",
        "- An additional requirement that our solution stop consuming inputs once the appropriate output has been achieved.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Importing the relevant libraries\n",
        "\n",
        "It turns out we only need to import the FParsec library. Everything else we need is a native function."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "First let's try to download the appropriate packet"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "#r \"nuget: FParsec\"\n",
        "open FParsec"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {},
          "execution_count": 1,
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Defining our domain\n",
        "\n",
        "Let's create some types to represent our domain space. In this case, we just need presentation of our codons and our proteins.\n",
        "\n",
        "We're going to represent our codons as two separate types, `ProteinCodon`s, which can be translated into protein amino acids, and `StopCodon`s, which represent STOP."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "type ProteinCodon = AUG | UUU | UUC | UUA | UUG | UCU | UCC | UCA | UCG | UAU | UAC | UGU | UGC | UGG \n",
        "\n",
        "type StopCodon = UAA | UAG | UGA\n",
        "\n",
        "type Protein = Methionine | Phenylalanine | Leucine | Serine | Tyrosine | Cysteine | Tryptophan\n",
        ""
      ],
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Defining our helper functions\n",
        "\n",
        "We need a few functions to help us out here. `toProtein` takes a `ProteinCodon` and returns the corresponding `Protein`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "let toProtein =\n",
        "  function\n",
        "    | AUG -> Methionine\n",
        "    | UUU -> Phenylalanine\n",
        "    | UUC -> Phenylalanine\n",
        "    | UUA -> Leucine\n",
        "    | UUG -> Leucine\n",
        "    | UCU -> Serine\n",
        "    | UCC -> Serine\n",
        "    | UCA -> Serine\n",
        "    | UCG -> Serine\n",
        "    | UAU -> Tyrosine\n",
        "    | UAC -> Tyrosine\n",
        "    | UGU -> Cysteine\n",
        "    | UGC -> Cysteine\n",
        "    | UGG -> Tryptophan\n",
        "\n",
        "// test\n",
        "\n",
        "toProtein UGG"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": "<div class=\"dni-plaintext\">Tryptophan</div>"
          },
          "execution_count": 1,
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Defining our basic parsers\n",
        "\n",
        "The most complex part of this is our generic `pUnion` parser. Without getting to much into the details, we use the FParsec functions [stringReturn](https://www.quanttec.com/fparsec/reference/charparsers.html#members.stringReturn) and [choice](https://www.quanttec.com/fparsec/reference/primitives.html#members.choice).\n",
        "\n",
        "`stringReturn` accepts a string to parse against and a type to return and makes a Parser of that type. \n",
        "\n",
        "`choice` accepts a sequence of many parsers of the same type and returns a Parser of that type.\n",
        "\n",
        "Together, they define a parametrized parser that accepts a sum type like one of the codons and makes a parser that will compare a string to see if it's representations.\n",
        "\n",
        "Thus we can say `pUnion<ProteinCodon>` and get a parser of type `Parser<ProteinCodon, unit>`, or    `pUnion<Protein>` to get a parser of type `Parser<Protein, unit>`"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "open FSharp.Reflection\n",
        "\n",
        "let pUnion<'t> : Parser<'t, unit> =\n",
        "    let pCase (case:UnionCaseInfo) =\n",
        "        stringReturn case.Name (FSharpValue.MakeUnion(case, [||]) :?> 't)\n",
        "\n",
        "    FSharpType.GetUnionCases typeof<'t> |> Seq.map pCase |> choice"
      ],
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Composing our parsers\n",
        "\n",
        "Now we can start combining some parsers together to get what we want."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "let pProteinString = pUnion<ProteinCodon> |>> toProtein |>> fun p -> p.ToString()"
      ],
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "`pProteinString` above starts with the parser for protein codons `pUnion<ProteinCocon>` and then uses the `|>>` operator to map the parser results to `toProtein` and that map those value to the `ToString` method. The result is a `Parser` capable of checking if a string matches a `ProteinCodon`, but returns a `string` representing a `Protein`. It's full return type is `Parser<string, unit>`."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Let's see what it tells us with a valid input. The `run` function is what we use to actually execute our parsers on some data."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "\n",
        "run pProteinString \"AUG\""
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": "<table><thead><tr><th>Item1</th><th>Item2</th><th>Item3</th></tr></thead><tbody><tr><td><div class=\"dni-plaintext\">Methionine</div></td><td><div class=\"dni-plaintext\">&lt;null&gt;</div></td><td><div class=\"dni-plaintext\">(Ln: 1, Col: 4)</div></td></tr></tbody></table>"
          },
          "execution_count": 1,
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that Item1 is our Protein string. Let's now try an invalid input. Something that shouldn't be parsable into a protein."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "run pProteinString \"UGA\""
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": "<table><thead><tr><th>Item1</th><th>Item2</th><th>Item3</th></tr></thead><tbody><tr><td><div class=\"dni-plaintext\">Error in Ln: 1 Col: 1\nUGA\n^\nExpecting: &#39;AUG&#39;, &#39;UAC&#39;, &#39;UAU&#39;, &#39;UCA&#39;, &#39;UCC&#39;, &#39;UCG&#39;, &#39;UCU&#39;, &#39;UGC&#39;, &#39;UGG&#39;, &#39;UGU&#39;\n, &#39;UUA&#39;, &#39;UUC&#39;, &#39;UUG&#39; or &#39;UUU&#39;\n</div></td><td><div class=\"dni-plaintext\">Error in Ln: 1 Col: 1\nExpecting: &#39;AUG&#39;, &#39;UAC&#39;, &#39;UAU&#39;, &#39;UCA&#39;, &#39;UCC&#39;, &#39;UCG&#39;, &#39;UCU&#39;, &#39;UGC&#39;, &#39;UGG&#39;, &#39;UGU&#39;\n, &#39;UUA&#39;, &#39;UUC&#39;, &#39;UUG&#39; or &#39;UUU&#39;\n</div></td><td><div class=\"dni-plaintext\">&lt;null&gt;</div></td></tr></tbody></table>"
          },
          "execution_count": 1,
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Error! or well, successful error? Out parser successfully rejected the StopCodon string we passed in, and told us it was looking for a string representing a ProteinCodon!\n",
        "\n",
        "Let's make some more parsers."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "let pStopCodon = pUnion<StopCodon> >>% ()\n",
        "\n",
        "let pStopCodonOrEOL = pStopCodon <|> eof"
      ],
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Next, we make the parser for our `StopCodon`, `pStopCodon`. Note that `pStopCodon` parses a `StopCodon`, but then uses the `FParsec` operator `>>%` to ignore that value and return a `unit` instead. This is so we can combine it with the `eol` (end of line) parser in `pStopOrEol`. \n",
        "\n",
        "`<|>` is another `FParsec` operator which takes two parsers and returns a parser that can be either one, so long as they're the same type. Since `eol` returns a unit `()` we needed to get stop to do the same."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "\n",
        "run pStopCodonOrEOL \"UGA\" //valid StopCodon input"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": "<table><thead><tr><th>Item1</th><th>Item2</th><th>Item3</th></tr></thead><tbody><tr><td><div class=\"dni-plaintext\">&lt;null&gt;</div></td><td><div class=\"dni-plaintext\">&lt;null&gt;</div></td><td><div class=\"dni-plaintext\">(Ln: 1, Col: 4)</div></td></tr></tbody></table>"
          },
          "execution_count": 1,
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "\n",
        "run pStopCodonOrEOL \"\" // valid \"end of line\" input"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": "<table><thead><tr><th>Item1</th><th>Item2</th><th>Item3</th></tr></thead><tbody><tr><td><div class=\"dni-plaintext\">&lt;null&gt;</div></td><td><div class=\"dni-plaintext\">&lt;null&gt;</div></td><td><div class=\"dni-plaintext\">(Ln: 1, Col: 1)</div></td></tr></tbody></table>"
          },
          "execution_count": 1,
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "\n",
        "run pStopCodonOrEOL \"xxx\" //invalid input"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": "<table><thead><tr><th>Item1</th><th>Item2</th><th>Item3</th></tr></thead><tbody><tr><td><div class=\"dni-plaintext\">Error in Ln: 1 Col: 1\nxxx\n^\nExpecting: end of input, &#39;UAA&#39;, &#39;UAG&#39; or &#39;UGA&#39;\n</div></td><td><div class=\"dni-plaintext\">Error in Ln: 1 Col: 1\nExpecting: end of input, &#39;UAA&#39;, &#39;UAG&#39; or &#39;UGA&#39;\n</div></td><td><div class=\"dni-plaintext\">&lt;null&gt;</div></td></tr></tbody></table>"
          },
          "execution_count": 1,
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Success. Our parser successfully accepts a `StopCodon` or the end of a string but rejects anything else. Note that our \"unit\" type output from the successful parsers is returned as `<null>`. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "let pProteinStringList = manyTill pProteinString pStopCodonOrEOL"
      ],
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Finally we put it all together in the `pProteinStringList` parser. Here we use the `FParsec` function `manyTill`.\n",
        "\n",
        "`manyTill` is a function that takes a two parsers and will continue to collect values of the first until it hits a value of the second, and then returns the values from the first as a list. This is conveniently, exactly what we need for this challenge!"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Running our solution"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "let proteins s =\n",
        "    match run pProteinStringList s with\n",
        "    | Success (result, _, _) -> Some result\n",
        "    | Failure _ -> None"
      ],
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now we can finally put it all together with our proteins functions which accepts a string and uses the `FParsec` function `run` which is what actually applies our parsers to some string.\n",
        "\n",
        "`run` returns a `ParserResult` which is a success if the input was parsed without error and a `Failure` with error messages if it doesn't. Here we're choosing to ignore all the extra meta data and just convert these to an `option<list<string>>` type."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "proteins \"AUG\" // returns [ \"Methionine\" ]"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": "<table><thead><tr><th>Value</th></tr></thead><tbody><tr><td><div class=\"dni-plaintext\">[ Methionine ]</div></td></tr></tbody></table>"
          },
          "execution_count": 1,
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "proteins \"UGA\" // returns [] "
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": "<table><thead><tr><th>Value</th></tr></thead><tbody><tr><td><div class=\"dni-plaintext\">[  ]</div></td></tr></tbody></table>"
          },
          "execution_count": 1,
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "fsharp"
        }
      },
      "source": [
        "proteins \"AUGUCUUAGAUG\" // returns [ \"Methionine\", \"Serine\" ] "
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": "<table><thead><tr><th>Value</th></tr></thead><tbody><tr><td><div class=\"dni-plaintext\">[ Methionine, Serine ]</div></td></tr></tbody></table>"
          },
          "execution_count": 1,
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Here's the entire solution:\n",
        "\n",
        "Without the comments, it's pretty concise! Most of the code is just setting up our domain! And we haven't had to define any loops, lists, maps, or finicky control logic. Our controls are baked into our data types. Yay parsers!\n",
        "\n",
        "```\n",
        "#r \"nuget: FParsec\"\n",
        "open FParsec\n",
        "\n",
        "type ProteinCodon = AUG | UUU | UUC | UUA | UUG | UCU | UCC | UCA | UCG | UAU | UAC | UGU | UGC | UGG \n",
        "\n",
        "type StopCodon = UAA | UAG | UGA\n",
        "\n",
        "type Protein = Methionine | Phenylalanine | Leucine | Serine | Tyrosine | Cysteine | Tryptophan\n",
        "\n",
        "let toProtein =\n",
        "  function\n",
        "    | AUG -> Methionine\n",
        "    | UUU -> Phenylalanine\n",
        "    | UUC -> Phenylalanine\n",
        "    | UUA -> Leucine\n",
        "    | UUG -> Leucine\n",
        "    | UCU -> Serine\n",
        "    | UCC -> Serine\n",
        "    | UCA -> Serine\n",
        "    | UCG -> Serine\n",
        "    | UAU -> Tyrosine\n",
        "    | UAC -> Tyrosine\n",
        "    | UGU -> Cysteine\n",
        "    | UGC -> Cysteine\n",
        "    | UGG -> Tryptophan\n",
        "\n",
        "let pUnion<'t> : Parser<'t, unit> =\n",
        "    let pCase (case:UnionCaseInfo) =\n",
        "        stringReturn case.Name (FSharpValue.MakeUnion(case, [||]) :?> 't)\n",
        "\n",
        "    FSharpType.GetUnionCases typeof<'t> |> Seq.map pCase |> choice\n",
        "\n",
        "let pProteinString = pUnion<ProteinCodon> |>> toProtein |>> fun p -> p.ToString()\n",
        "\n",
        "let pStopCodon = pUnion<StopCodon> >>% ()\n",
        "\n",
        "let pStopCodonOrEOL = pStopCodon <|> eof\n",
        "\n",
        "let pProteinStringList = manyTill pProteinString pStopCodonOrEOL\n",
        "\n",
        "let proteins s =\n",
        "    match run pProteinStringList s with\n",
        "    | Success (result, _, _) -> Some result\n",
        "    | Failure _ -> None\n",
        "```"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": ".NET (C#)",
      "language": "C#",
      "name": ".net-csharp"
    },
    "language_info": {
      "file_extension": ".cs",
      "mimetype": "text/x-csharp",
      "name": "C#",
      "pygments_lexer": "csharp",
      "version": "8.0"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}