Solving the Protein Translator problem using F# and FParsec
Tags: fsharp, fparsec, exercism, practice
Published: 2021-03-22 13:58:22

This article/workbook is my attempt to solve the [Protein Translation](https://exercism.io/tracks/fsharp/exercises/protein-translation) Problem on exercism.io. The whole thing was done in a [.Net Interactive Workbook](https://github.com/tkshill/protein-translation/blob/master/fparsec_exercism.ipynb).

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.

So let's now attempt this problem another way, using [FParsec](https://www.quanttec.com/fparsec/), a fully functional parser combinator library.

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.

So let's jump in.

## Describing the problem space

(Taken from exercism):

**RNA** can be broken into three nucleotide sequences called codons, and then translated to a polypeptide like so:

_RNA: "AUGUUUUCU"_ => translates to

_Codons: "AUG", "UUU", "UCU"_ => which become a polypeptide with the following sequence =>

_Protein: "Methionine", "Phenylalanine", "Serine"_

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.

All subsequent codons after are ignored, like this:

_RNA: "AUGUUUUCUUAAAUG"_ =>

_Codons: "AUG", "UUU", "UCU", "UAA", "AUG"_ =>

_Protein: "Methionine", "Phenylalanine", "Serine"_

Note the stop codon "UAA" terminates the translation and the final methionine is not translated into the protein sequence.

Below are the codons and resulting Amino Acids needed for the exercise.

- AUG -> Methionine
- UUU, UUC -> Phenylalanine
- UUA, UUG -> Leucine
- UCU, UCC, UCA, UCG -> Serine
- UAU, UAC -> Tyrosine
- UGU, UGC -> Cysteine
- UGG -> Tryptophan
- UAA, UAG, UGA -> STOP

## Defining our goal

To call this solution solved, our requirements are as follows:

- 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.
- An additional requirement that our solution stop consuming inputs once the appropriate output has been achieved.

## Importing the relevant libraries

It turns out we only need to import the `FParsec` library. Everything else we need is a native function.

```fsharp
#r "nuget: FParsec"
open FParsec
```

## Defining our domain

Let's create some types to represent our domain space. In this case, we just need presentation of our codons and our proteins.

We're going to represent our codons as two separate types, `ProteinCodon`, which can be translated into protein amino acids, and `StopCodon`, which represent `STOP`.

```fsharp
type ProteinCodon = AUG | UUU | UUC | UUA | UUG | UCU | UCC | UCA | UCG | UAU | UAC | UGU | UGC | UGG 

type StopCodon = UAA | UAG | UGA

type Protein = Methionine | Phenylalanine | Leucine | Serine | Tyrosine | Cysteine | Tryptophan
```

## Defining our helper functions

We need a few functions to help us out here. `toProtein` takes a `ProteinCodon` and returns the corresponding `Protein`.

```fsharp
let toProtein =
  function
    | AUG -> Methionine
    | UUU -> Phenylalanine
    | UUC -> Phenylalanine
    | UUA -> Leucine
    | UUG -> Leucine
    | UCU -> Serine
    | UCC -> Serine
    | UCA -> Serine
    | UCG -> Serine
    | UAU -> Tyrosine
    | UAC -> Tyrosine
    | UGU -> Cysteine
    | UGC -> Cysteine
    | UGG -> Tryptophan
```

We can test that running this function works

```fsharp
toProtein UGG

Out[1]:
Tryptophan
```

## Defining our basic parsers

The most complex part of this is our generic pUnion parser. Without getting too much into the details, we use the FParsec functions `stringReturn` and `choice`.

[stringReturn](https://www.quanttec.com/fparsec/reference/charparsers.html#members.stringReturn) accepts a string to parse against and a type to return and makes a Parser of that type.

[choice](https://www.quanttec.com/fparsec/reference/primitives.html#members.choice) accepts a sequence of many parsers of the same type and returns a Parser of that type.

We define a helper function `pCase` that takes a union type value and makes a parser for that value specifically, and then we map that function across all cases in a union for full coverage.

Putting it all together, we've defined 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.

```fsharp
open FSharp.Reflection

let pUnion<'t> : Parser<'t, unit> =
    let pCase (case:UnionCaseInfo) =
        stringReturn case.Name (FSharpValue.MakeUnion(case, [||]) :?> 't)

    FSharpType.GetUnionCases typeof<'t> |> Seq.map pCase |> choice
```

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>`

## Composing our parsers

Now we can start combining some parsers together to get what we want.

```fsharp
let pProteinString = pUnion<ProteinCodon> |>> toProtein |>> fun p -> p.ToString()
```

`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>`.

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.

```fsharp
run pProteinString "AUG"

Out[1]:
"Methionine"
```
	
Great! That did exactly what we wanted. It parsed the string representing a codon, but _returned_ the value of the codon converted to a protein, converted to a string. Let's now try an invalid input. Something that shouldn't be parsable into a protein.

```fsharp
run pProteinString "UGA"

Out[1]:
Error in Ln: 1 Col: 1 UGA ^ Expecting: 'AUG', 'UAC', 'UAU', 'UCA', 'UCC', 'UCG', 'UCU', 'UGC', 'UGG', 'UGU' , 'UUA', 'UUC', 'UUG' or 'UUU'
```

Error! or well, successful error? Our parser successfully rejected the `StopCodon` string we passed in, and told us it was looking for a string representing a `ProteinCodon`!

## Let's make some more parsers.

```fsharp
let pStopCodon = pUnion<StopCodon> >>% ()

let pStopCodonOrEOL = pStopCodon <|> eof
```

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`.

`<|>` 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.

```fsharp
run pStopCodonOrEOL "UGA" //valid StopCodon input

Out[1]:
<null>

run pStopCodonOrEOL "" // valid "end of line" input

Out[1]:
<null>
	
run pStopCodonOrEOL "xxx" //invalid input

Out[1]:
Error in Ln: 1 Col: 1 xxx ^ Expecting: end of input, 'UAA', 'UAG' or 'UGA'
```

Success! Our parser successfully accepts a string that represents 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>`.

```fsharp
let pProteinStringList = manyTill pProteinString pStopCodonOrEOL
```

Finally we put it all together in the `pProteinStringList` parser. Here we use the `FParsec` function `manyTill`.

`manyTill` is a function that takes two parsers; it 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!

## Running our solution

```fsharp
let proteins s =
    match run pProteinStringList s with
    | Success (result, _, _) -> Some result
    | Failure _ -> None
```

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.

`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.

```fsharp
proteins "AUG" // returns [ "Methionine" ]

Out[1]:
[ "Methionine" ]

proteins "UGA" // returns []

Out[1]:
[ ]

proteins "AUGUCUUAGAUG" // returns [ "Methionine", "Serine" ]

Out[1]:
[ "Methionine", "Serine" ]
```

And that's it. It all works. Thank you for reading.

## Here's the entire solution:

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!

```fsharp
#r "nuget: FParsec"
open FParsec

type ProteinCodon = AUG | UUU | UUC | UUA | UUG | UCU | UCC | UCA | UCG | UAU | UAC | UGU | UGC | UGG 

type StopCodon = UAA | UAG | UGA

type Protein = Methionine | Phenylalanine | Leucine | Serine | Tyrosine | Cysteine | Tryptophan

let toProtein =
  function
    | AUG -> Methionine
    | UUU -> Phenylalanine
    | UUC -> Phenylalanine
    | UUA -> Leucine
    | UUG -> Leucine
    | UCU -> Serine
    | UCC -> Serine
    | UCA -> Serine
    | UCG -> Serine
    | UAU -> Tyrosine
    | UAC -> Tyrosine
    | UGU -> Cysteine
    | UGC -> Cysteine
    | UGG -> Tryptophan

let pUnion<'t> : Parser<'t, unit> =
    let pCase (case:UnionCaseInfo) =
        stringReturn case.Name (FSharpValue.MakeUnion(case, [||]) :?> 't)

    FSharpType.GetUnionCases typeof<'t> |> Seq.map pCase |> choice

let pProteinString = pUnion<ProteinCodon> |>> toProtein |>> fun p -> p.ToString()

let pStopCodon = pUnion<StopCodon> >>% ()

let pStopCodonOrEOL = pStopCodon <|> eof

let pProteinStringList = manyTill pProteinString pStopCodonOrEOL

let proteins s =
    match run pProteinStringList s with
    | Success (result, _, _) -> Some result
    | Failure _ -> None
```