Advanced parser combinators with parser-ts
Tags: typescript, functional
Published: 2022-12-12 04:08:00

In the last part, we used the power of parser combinators to systematically parse strings into dates. However a Parser is unbound in its return type and you can make it returning *anything*.

Today we will be using this ability and combining it with the state monad to draw things on a canvas in clean, modular way.

The problem we will be tackling today will be the turtle.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jnud3j2ypfmh6sv6szin.jpg)

No not that turtle, this one:
https://docs.python.org/3/library/turtle.html
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/moakp9nido1omcorwewf.png)

Python turtles are great, you can give them a list of instructions and these turtles will dutifully execute them to create fine art. As our turtle program will be simpler, we will give our turtle a short name. Meet Bob.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vbnp1r9j2so6ratp3k1a.png)

For simplicity, Bob will only understand a small subset of commands that python turtles can understand. Bob understands the following strings: forward X, left X, right X, penUp and penDown. These commands will respectively move, rotate and give Bob the ability to draw straight lines on a canvas.

To tackle this problem, we will be splitting it up into three parts
- Teaching Bob how to understands strings
- Teaching Bob how to store state
- Teach Bob how to draw on the page

Once we have tackled these three sub problems, we will join them altogether and have our program. 

## Teaching Bob to understand strings
The first problem we will tackle is to teach Bob to understand strings. Building on the [last article](https://dev.to/derp/parser-combinators-in-typescript-with-parser-ts-part-1-46o3), we will use parser combinators. Let's   teach Bob how to understand "forward 10".
```
const forwardStrParser: P.Parser<string, number> = pipe(
  S.string("forward"),
  P.chain(() => S.spaces1),
  P.chain(() => S.int)
);
```

Let's break this down. First (1) we match on the string "forward" with `S.string("forward")`, we then match on one or more spaces with `P.chain(() => S.spaces1))` and finally we have `P.chain(() => S.int)`. Note that we are ignoring the input from the string "forward" and the spaces and we only keep the number at the end.

In the end, we have a Parser that takes in a string and returns back a number. However as Parsers are functors, they have a method `map` which allows us to transform that number into any other type. We will get back to this point later in the article.

## Teaching Bob to store state
Bob needs to know where he is on the canvas, which direction he is facing and whether or not he is currently drawing or not. Let's create a minimal representation of this state:
```
export const INITIAL = {
  dir: 0, // direction our turtle is facing in degrees
  pos: [0, 0], // our initial x,y position
  isDrawing: false // our way of putting the 'pen' up or down.
};
```
From the initial state above, we will need some sort of mechanism to transform that state and extract some sort of output from the new state. Thankfully, we can use the [state monad](https://dev.to/derp/state-monad-in-fp-ts-5c79) to give this to us. 

To summarise, the state monad has a type signature of:
```
State s a :: s -> (a,s)
```

What this says is that all our state monads are state transition functions that take in some initial state and returns back a pair of some output `a` and some new state s.

Let's ignore the output for now and see how we might write the state transition function to move Bob forward `n`.

```
export const forward = (n: number): St.State<State, ?> => (
  state: State
) => {
  const [x, y] = state.pos; // 1
  const dirRadians = degToRad(state.dir);
  const xComponent = Math.cos(dirRadians);
  const yComponent = Math.sin(dirRadians);

  const newState = { //2
    isDrawing: state.isDrawing,
    dir: state.dir,
    pos: [x + n * xComponent, y + n * yComponent]
  };
  return [?, newState]; // 3
};
```

Let's break this down. This is a function that takes in a number `n` spaces to move forward and returns back the state monad `St.State<State,?>`. Now state monads are functions that take in an initial state and return back some output and a new state.

In section 1, we are destructuring the x & y co-ordinate from the current position. We then do some trigonometry to calculate the x & y component based on the current direction of our turtle. Once we have all that, we start constructing our new state in section 2. As moving forward does not change the isDrawing or direction of our turtle, we pass those unchanged from our initial state. Our new co-ordinates are calculated by multiplying the n spaces that we are moving forward by the x & y components. Finally in section 3, we return back our pair of some output (?) and our new state.

## Teaching Bob to draw on the page
In our example, we are using a [canvas API](https://developer.mozilla.org/en-US/docs/Web/API/Canvas_API) to draw on the page. However, one important detail is that we don't want to immediately draw on the page, but instead create a function that will only draw on the page _when executed_.

To do this, we define a `DrawFunction` which has the type signature of
```
type DrawFunction = (context: CanvasRenderingContext2D) => void;
```
That is, this is a function that takes in the context as an argument so that when executed, we can perform side effects like `context.stroke()` drawing our lines on the canvas.

For example, our lineTo function will look like the below.

```
export const lineTo = (x: number, y: number): DrawFunction => (ctx) => {
  ctx.lineTo(x, y);
  ctx.stroke();
};

``` 
Let's break this down. We have a `lineTo` function that takes in the new x & y co-ordinate that we should move to from our previous x&Y co-ordinate stored in the internal canvas state. We then call `lineTo` which adds a new line to the current sub-path inside the canvas state. As this does not actually fill in the line, we will then need to call `stroke` to fill in the line causing the line to appear on the screen. As `lineTo` is a higher order function, the lines won't be drawn until both the `(x,y)` and `(ctx)` arguments are supplied.

## Bringing it all together
In the previous section, we saw how to parse a string, transform state and draw onto a canvas individually. In this section, we will connect them all with the power of functional programming.

First, from our forward string parser, we ended up with a parser from strings to numbers. `forwardStrParser : P.Parser<string, number>`, however as alluded to earlier, Parsers a functors and we can map that number and pass it to our forward function that returns a state monad to get a parser that takes in a string and returns back a state transition.

Ie
```
// forwardStrParser :: P.Parser<string, number>
const forwardParser = pipe(forwardStrParser, P.map(forward));
// forward Parser :: P.Parser<string, S.State<State, ?>>
```

Now we have a parser that takes in a string and returns back state transition function.

From the state transition function, we glossed over the output of each step. What we can do is to return a DrawFunction for each step so as we go through our state transitions, we can build a corresponding DrawFunction. 

Ie
```
export const forward = (n: number): St.State<State, DrawFunction> => (
  state: State
) => {
  // discussed in section 2
  const [x, y] = state.pos;
  const dirRadians = degToRad(state.dir);
  const xComponent = Math.cos(dirRadians);
  const yComponent = Math.sin(dirRadians);

  const newState = {
    isDrawing: state.isDrawing,
    dir: state.dir,
    pos: [x + n * xComponent, y + n * yComponent]
  };

  // **New** Look here below:
  const drawFunction: DrawFunction = state.isDrawing
    ? lineTo(newState.pos[0], newState.pos[1])
    : moveTo(newState.pos[0], newState.pos[1]);

  return [drawFunction, newState];
};
```
Let's break this down. Here we choose between two DrawFunctions depending on our current state. If `isDrawing` is true, we will choose the `lineTo` DrawFunction whereas if it is not, we will choose the `moveTo` DrawFunction. The moveTo function has not been shown above but can be seen in the codesandbox at the end. 

Hence our forwardParser has the final type of `P.Parser<string, S.State<State, DrawFunction>>`.

## Seeing it in action
![A single horizontal black line](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/grjy63i0b8mg847e4wug.png)

```
import { pipe } from "fp-ts/function";
import { run } from "parser-ts/lib/code-frame";
import * as E from "fp-ts/lib/Either";

const initialState: State = {
  isDrawing: true,
  dir: 0,
  pos: [0, 0]
}; // 1

const c = <HTMLCanvasElement>document.getElementById("myCanvas");
let ctx = c.getContext("2d");
if (ctx == null) throw new Error("canvas not found"); 
ctx.lineWidth = 5;
ctx.moveTo(initialState.pos[0], initialState.pos[1]); // 2

const eitherState = run(forwardParser, "forward 100"); // 3
pipe(
  eitherState,
  E.fold(console.error, (state) => { // 4
    const [drawFn, _newState] = state(initialState); // 5
    drawFn(ctx); // 6
  })
);
```
Let's break this down. In (1), we set the initial state of Bob. Note that we are setting isDrawing to be true right off the bat as we want to draw a line instead of just moving Bob.

In (2), we need to get our reference in JS to our HTML canvas element. We then update the context to match our initial state.

In 3, we run the forward parser with our string `"forward 100"`. This returns back either an error message if our string fails to parse or our state transition. If it is an error message, we log the error to the console, however if is our state monad (4), we run the state against the initial state in (5) to get a drawFunction and the updated state. As we are only interested in the drawFunction, we ignore the updated state and we execute the drawFunction by providing the last context argument in (6) causing our line to appear on the screen. 

## Understanding many commands
Currently Bob only understands how to draw lines forwards. We won't cover all the commands here however they all follow a similar pattern in that we create a Parser for every command that we want Bob to understand.

```
forwardParser :: P.Parser<State, DrawFunction>
leftParser :: P.Parser<State, DrawFunction>
rightParser :: P.Parser<State, DrawFunction>
penUpParser :: P.Parser<State, DrawFunction>
penDownParser :: P.Parser<State, DrawFunction>
```

Once we have our parsers, we can join them together with [alt](https://gcanti.github.io/parser-ts/modules/Parser.ts.html#alt) to create our overall turtleParser
```
export const turtleParser = pipe(
  forwardParser,
  P.alt(() => leftParser),
  P.alt(() => rightParser),
  P.alt(() => penUpParser),
  P.alt(() => penDownParser)
);
```

However, this is still a parser that takes in a single string and returns back a single state transition. Ie
```
turtleParser :: P.Parser<State, DrawFunction>
```
If we have many strings in an array, what we can do is run the turtleParser on every string in the array to get back an array of `Either<string,St.State<State, DrawFunction>` and use [sequenceArray](https://gcanti.github.io/fp-ts/modules/Either.ts.html#sequencearray) to convert that into an Either<string, St.State<State,DrawFunction>[]>.

Let's see that in action
```
const cmds: string[]= [
  "forward 100",
  "right 90",
  // ...other commands not shown
]; // 1

const parsed = cmds.map((cmd) => run(turtleParser, cmd)) // 2
// E.sequenceArray :: <E, A>(as: readonly Either<E, A>[]) => Either<E, readonly A[]> // 3
const maybeTransitions = E.sequenceArray(parsed); // 4
```

Let's break that down. In (1), we have our array of strings which we then map into an array of Parsers in (2). Now parsed has the type of `parsed:: E.Either<string, St.State<State,DrawFunction>>[]` however note that we have ended up with an array of Eithers which if we would then manually need to check on whether it was a Left or a Right and then only if it was a Right, would we want to progress. As this is a common task in functional programming, we reach for the utility function sequenceArray(3) which takes in an array of Eithers and runs through them sequentially and checks whether each element is a Left or a Right. If any element is Left, it will return back that result, however if all the elements in the array are Right, then it will collect them all into a single Array. In (4), we call this function on our array `parsed` to get back our `maybeTransitions` which is either an error or an array of State transitions.

```
if (E.isRight(maybeTransitions)) {
  const transitions = maybeTransitions.right;
  const [drawFns, finalState] = St.sequenceArray(transitions)(INITIAL); // 5

  drawFns.forEach((drawFn) => drawFn(ctx as CanvasRenderingContext2D)); //6
  drawTurtle(finalState.pos[0], finalState.pos[1], finalState.dir)(ctx); // 7
} else {
  console.error(maybeTransitions.left);
}
```
Once we have our array of state transitions in (5), we then call the State monad's version of sequenceArray to get back an array of drawFunctions and our final state. We then pass the final argument in all of our drawFunctions in (6) drawing our changes to the canvas. In (7), we draw Bob on our canvas with his position and direction based of our final state at the end of all our state transitions.

In conclusion, we have ended up with a program which neatly separates the concerns of parsing, state and side effects and joined them all with the power of functional programming. If you would like to have a play yourself, please feel free to check out the codesandbox link below:

https://codesandbox.io/s/parser-combinator-example-cjuh40