DEV Community: Kabisa Software Artisans

Learning functional programming #5: Parsing arrays and numbers

Matthijs Groen — Thu, 25 Mar 2021 00:00:00 +0000

This post is part 5 of the series "Learning Functional Programming using JavaScript". When the next part will be published, a link to part 6 will be added here in the top.

Earlier parts: part 1, part 2, part 3, part 4.

This is a continuation of the Functional Programming challenge I gave myself:
Write a JSON parser in JavaScript, using
the parser combinator principles from the blogpost of Scott Wlaschin.

At this point, we are able to parse null, true, false, strings and
numbers. In this post we will complete the initial implementation by adding
support for arrays and objects.

In the previous post we rewrote the .reduce to use our own. To promote this
behavior, I wanted to get rid of all calls to 'objects'. So I added a new rule
to the ESLint config in my package.json:

{
  "eslintConfig": {
    "rules": {
      "no-restricted-syntax": [
        "error",
        {
          "selector": "CallExpression[callee.type=MemberExpression][callee.property.name!='log']",
          "message": "Not allowed to call object members, except console.log()"
        }
      ]
    }
  }
}

In production code, I would use system functions rather than rolling my own, but here we are just doing it for ~~science!~~ learning functional programming concepts. I will reflect on things like this in a later post.

While this test for console.log is not fool proof, it will start warning about
.map, .join and .concat. So lets start rewriting them:

// before
const toList = mapResult((result) => [result[0]].concat(result[1]));
// after
const toList = mapResult((result) => [...[result[0]], ...result[1]]);

Be sure to wrap result[0] into an array. In our parser results, this toList
is to flatten a list that has the form of: [a, [b, [c, d]]. So each time it is
a list being appended to a single value.

// before
const toString = mapResult((result) => result.join(""));
// after
const reduceWithStart = (reducer) => (start) => (tail) =>
  doReduce(reducer)(start)(tail);
const join = (a) => (b) => String(a) + String(b);
const toString = mapResult(reduceWithStart(join)(""));

I created a reduceWithStart that is a variant of the already made reduce (see
previous post), but this time you can provide a start value for the result. This
is so that empty lists are converted to empty strings.

Considering we extracted 2 helper functions, the code of the toString is
actually a bit shorter!

// before
const stringParser = (string) =>
  addLabel(string)(chain([...string].map((char) => characterParser(char))));
// after
const map = (transform) => ([head, ...tail]) =>
  head ? [transform(head), ...map(transform)(tail)] : [];

const stringParser = (string) =>
  addLabel(string)(chain(map(characterParser)([...string])));

Here I made a map function, just like we created the reduce before (see
previous post). There are other functions using .map that I needed to convert:

// before
const escapedCharParser = choice(
  specialCharacters.map(([match, result]) => parseStringResult(match)(result))
);

// after
const escapedCharParser = choice(
  map(([match, result]) => parseStringResult(match)(result))(specialCharacters)
);

Apart from the small change in order (transform before the list) the setup is
basically the same.

// before
const anyOf = (string) => choice([...string].map(characterParser)([...string]));

// after
const anyOf = (string) => choice(map(characterParser)([...string]));

So that was not that hard, and now we are able to enforce another rule!

Now, onto parsing arrays!

Parsing an JSON array

As Scott Wlashin explains in his excellent series,
there is a problem with parsing an array as can be seen in the EBNF notation:

value = object | array | number | string | "true" | "false" | "null";
array = "[", [ value, { ",", value } ], "]";

A value could be an array, and an array consists of value! there is a
circular reference here. How can you write a parser that needs to parse itself
as well?

Scott Wlashin fixes this by using a
forward declaration. A
forward declaration is a placeholder, that will be replaced later on.

I tried to follow this pattern in my implementation as well:

const forwardReference = (impl = () => [FAILED, "Unfulfilled"]) => [
  (stream) => impl(stream),
  (update) => (impl = update),
];

const [valueParser, updateValueParserRef] = forwardReference();
console.log(valueParser("hello")); // [ Symbol(Failed), 'Unfulfilled' ]
updateValueParserRef(characterParser("h"));
console.log(valueParser("hello")); // [ 'h', [ 'e', 'l', 'l', 'o' ] ]

The linter didn't complain, my implementation worked, so I was happy! Time to
start parsing that array! (No worries, this will be done properly later 😉)

These are some examples we should be able to parse:

[null, 1, 3  , [ true ] ]
[ "string [ , ", false]

As you can see from these examples, in and around the brackets [] and the
seperator , we can have all kinds of whitespace that does not matter. So we
need some way to ignore those:

const whitespace = " \n\t";
const whitespaceParser = many(anyOf(whitespace));

const ignoreTrailingSpaces = (parser) => andThenLeft(parser)(whitespaceParser);

const arrayStart = ignoreTrailingSpaces(characterParser("["));
const arrayEnd = ignoreTrailingSpaces(characterParser("]"));
const arraySep = ignoreTrailingSpaces(characterParser(","));

console.log(arrayStart("[    null, 1 ]")); // [ '[', [ 'n', 'u', ...

Nice! The spaces are ignored and the next character is waiting to be parsed. Now
we can define our array value parser that makes use of the forward reference:

const arrayValue = ignoreTrailingSpaces(valueParser);

Now we need some parser that can parse a list, divided by seperators. By
combining parsers, we are looking for something like this:

const arrayValues = sepBy(arraySep)(arrayValue);

That ideally would ignore the seperators in the result, and make a flat list of
the result of the values.

Let's build one:

const sepBy = (sepParser) => (parser) => andThen(parser)(sepParser);

const dummyArrayValueParser = sepBy(arraySep)(nullParser);
console.log(dummyArrayValueParser("null,    null,   null"));
// [ [ null, ',' ],
//   [ 'n', 'u', 'l', 'l', ',', ' ', ' ', ' ', 'n', 'u', 'l', 'l' ] ]

After a seperator, we always need to find another element:

const sepBy = (sepParser) => (parser) =>
  andThen(parser)(andThenRight(sepParser)(parser));

const dummyArrayValueParser = sepBy(arraySep)(nullParser);
console.log(dummyArrayValueParser("null,    null,   null"));
// [ [ null, null ], [ ',', ' ', ' ', ' ', 'n', 'u', 'l', 'l' ] ]

But those separators and values can be repeated N times:

const sepBy = (sepParser) => (parser) =>
  andThen(parser)(many(andThenRight(sepParser)(parser)));

const dummyArrayValueParser = sepBy(arraySep)(nullParser);
console.log(dummyArrayValueParser("null,    null,   null"));
// [ [ null, [ null, null ] ], [] ]

Yes! now to flatten that list, by using toList:

const sepBy = (sepParser) => (parser) =>
  toList(andThen(parser)(many(andThenRight(sepParser)(parser))));

But what if the array would be empty?

const dummyArrayValueParser = sepBy(arraySep)(nullParser);
console.log(dummyArrayValueParser(""));
// [ Symbol(Failed), "Error parsing 'null':", 'Unexpected EOF' ]

console.log(dummyArrayValueParser("null"));
// [ [ null ], [] ]

So our implementation would require at least one value. So we rename the
function to sepBy1 and create a new one that would accept 'no values'

const sepBy1 = (sepParser) => (parser) =>
  toList(andThen(parser)(many(andThenRight(sepParser)(parser))));

const sepBy = (sepParser) => (parser) =>
  orElse(sepBy1(sepParser)(parser))(resultParser([]));

So now our array parser is complete!

const arrayValues = sepBy(arraySep)(arrayValue);
const arrayParser = addLabel("array")(
  between(arrayStart)(arrayEnd)(arrayValues)
);

We can test it out by fulfilling our forward reference by calling updateValueParserRef:

updateValueParserRef(
  choice([
    nullParser,
    boolParser,
    numberParser,
    quotedStringParser,
    arrayParser,
  ])
);

// parsing our examples:
console.log(valueParser("[null, 1, 3  , [ true ] ]"));
// [ [ null, 1, 3, [ true ] ], [] ]

console.log(valueParser('[ "string [ , ", false]'));
// [ [ 'string [ , ', false ], [] ]

We can now already parse a decent subset of JSON. The only thing missing right now, is
objects.

Parsing JSON objects

The EBNF definition for a JSON object is as follows:

object = "{", [ string, ":", value, { ",", string, ":", value } ], "}";

So, "Between" brackets, are key-value pairs "seperated" by a comma. The
key-value pair is a String, ":", value. I think we already have all ingredients
for this one! Maybe we need to add some code to produce the end result, but
parsing wise we should already be close!

const objectStart = ignoreTrailingSpaces(characterParser("{"));
const objectEnd = ignoreTrailingSpaces(characterParser("}"));
const objectPairSep = ignoreTrailingSpaces(characterParser(","));
const objectKeyValSep = ignoreTrailingSpaces(characterParser(":"));
const objectKey = ignoreTrailingSpaces(quotedStringParser);
const objectValue = ignoreTrailingSpaces(valueParser);
const objectKeyValue = andThen(andThenLeft(objectKey)(objectKeyValSep))(
  objectValue
);

const objectParser = between(objectStart)(objectEnd)(
  sepBy(objectPairSep)(objectKeyValue)
);

console.log(objectParser('{ "hello": "world", "fp": true }'));
// [ [ [ 'hello', 'world' ], [ 'fp', true ] ], [] ]

The default result is already a list of key-value pairs. Now to put them into an
object:

const toObject = doReduce((result) => ([key, value]) => ({
  ...result,
  [key]: value,
}))({});

const objectParser = mapResult(toObject)(
  between(objectStart)(objectEnd)(sepBy(objectPairSep)(objectKeyValue))
);

console.log(objectParser('{ "hello": "world", "fp": true }'));
// [ { hello: 'world', fp: true }, [] ]

Now to update our value choice, so that objects are included:

updateValueParserRef(
  choice([
    nullParser,
    boolParser,
    numberParser,
    quotedStringParser,
    arrayParser,
    objectParser, // new!
  ])
);

const jsonParser = (stream) =>
  onSuccess(
    andThenRight(whitespaceParser)(valueParser)(stream)
  )(([result, remaining]) =>
    remaining.length > 0
      ? [FAILED, "Unexpected characters:", remaining]
      : result
  );

// data is our challenge data, see post 1
console.log(jsonParser(data)); // Works!

I added a jsonParser to check after parsing if there are no remaining
characters left. If there are, return an error. If not, return the parsed
result.

Now I only need to build our get function to get value from our data, to
complete the challenge, and we need to check if we can tick a box for all the
rules we applied.

Getting data out of our JSON structure

In the definition of the challenge, there were 3 calls that we should be able to
do:

{
  "goals": [
    "get(data)(\"using.disallowed.0\") should result in \"No dependencies\"",
    "get(data)(\"points.full-json\") should result in 1000",
    "get(data)(\"jsonTypes.2\") should result in false"
  ]
}

The thing is, the argument from the get is also a string that needs to be
parsed! (separted by . dots).

And we made just the tools to do that...

const pathElementParser = toString(some(satisfy((c) => c !== ".")));
const split = sepBy(characterParser("."))(pathElementParser);

const get = (data) => (path) =>
  doReduce((result) => (item) => result && result[item])(data)(split(path)[0]);

const jsonGet = get(parsedData);

console.log(jsonGet("using.disallowed.0"));
console.log(jsonGet("points.full-json"));
console.log(jsonGet("jsonTypes.2"));

Challenge completed!

But there were some things still bothering me. I did an assignment in the
forward reference, and that felt like cheating. But first lets see how we score
on the restrictions we applied, by looking at the defined ESLint rules of our
package.json...

{
  "eslintConfig": {
    "globals": {
      "Symbol": "readonly",
      "Array": "readonly",
      "String": "readonly",
      "Number": "readonly",
      "console": "readonly"
    },
    "rules": {
      "no-console": "off",
      "no-use-before-define": "error",
      "no-eval": "error",
      "no-implied-eval": "error",
      "no-restricted-globals": ["error", "JSON"],
      "max-statements": ["error", 1, { "ignoreTopLevelFunctions": false }],
      "complexity": ["error", { "max": 3 }],
      "arrow-body-style": ["error", "as-needed"],
      "no-restricted-syntax": [
        "error",
        {
          "selector": "FunctionExpression",
          "message": "Please use Lambda notation () =>"
        },
        {
          "selector": "IfStatement",
          "message": "Try using ternary operator: true ? 1 : 2"
        },
        {
          "selector": "VariableDeclaration[kind=let],VariableDeclaration[kind=var]",
          "message": "Only use constants"
        },
        {
          "selector": "ArrowFunctionExpression[params.length > 1]",
          "message": "Only 1 argument allowed. Please use currying"
        },
        {
          "selector": "CallExpression[callee.type=MemberExpression][callee.property.name!='log']",
          "message": "Not allowed to call object members, except console.log()"
        }
      ]
    }
  }
}

I was checking for usage of const, but I never assigned rules that assignments
where forbidden. I was also missing my "No self referencing recursion" I wanted
to try (see first post).

Time to extend the linting rules some more, but we'll leave that for a next post.

Conclusion

The code so far:

A full JSON parser (only skipped hex chars in strings)
A function to grab values from the JSON structure
Check the full code here

What I learned so far:

Still the code is more the tools to parse than a specific implementation. I like this approach, it makes most of the code re-usable. The 'get' function is an example of reuse.
I followed the original blog of parser combinators quite literally. It helped a great deal in the implementation, but the forward reference felt weird. I had find a way to do it without an assignment in there.

What did I like:

I finished the parser! Everything worked. I never though I would be able to implement it. So far I spent 2 evenings on it.
It felt nice to break loose from the functions already provided in the language, and do an own implementation for it. Its not something you would do in production code, but for a challenge like this, it is cool to also do the most basics of tool building.

What did I not like:

The forward reference. I have to find a better way to do this. (Right now it is cheating by reassigning the incoming function argument).

Next time:

Removing the self referencing recursion
Fixing the forward reference

Learning functional programming #4: Parsing strings and numbers

Matthijs Groen — Wed, 17 Mar 2021 00:00:00 +0000

This post is part 4 of the series “Learning Functional Programming using JavaScript”. When the next part will be published, a link to part 5 will be added here in the top.

Earlier parts: part 1, part 2, part 3.

This is a continuation of the Functional Programming challenge I gave myself: Write a JSON parser in JavaScript, usingthe parser combinator principles from the blogpost of Scott Wlaschin.

So far we defined the challenge, added some rules to adhere, created a character parser and we are able to parse the first literals of JSON: null, true andfalse.

Quoted string parser

Its time for the next type to parse: Strings.

An EBNF notation of a JSON String looks like this:


1
2
3
4
5
6

string = '"',
  { ? Any unicode character except " or \ or control character ?
  | "\", (
    '"' | "\" | "/" | "b" | "f" | "n" | "r" | "t" |
    "u", 4 * ? hexadeximal digit ?
  ) }, '"';

Since our example data does not have \uXXXX unicode in it, I will skip the implementation of it.

Let us start with parsing the quote:


1
2

const quoteParser = characterParser('"');
console.log(quoteParser('"test"')); // ['"', [ 't', 'e', 's', 't', '"'] ]

The string could contain any character, so having to define them all using thecharacterParser would be madness. Time to change the strategy here, by changing the characterParser into a satisfy method, that parses / consumes the head of our stream when it satisfies a predicate.

What is a predicate?

A Predicate is a function that will simply return true or false based on the input. It is commonly used in [].filter(), [].some() and [].every().


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

const parseError = (message) => (error) => [FAILED, message, error];
const genericParseError = parseError("Error parsing:");

const satisfy = (predicate) => ([head, ...tail]) =>
  head
    ? predicate(head)
      ? [head, tail]
      : genericParseError(`Unexpected '${head}'`)
    : genericParseError("Unexpected EOF");

const addLabel = (label) => (parser) => (stream) =>
  onFailure(parser(stream))(([, , error]) =>
    parseError(`Error parsing '${label}':`)(error)
  );

const characterParser = (character) =>
  addLabel(character)(satisfy((c) => c === character));

Since we now use a predicate that needs to return a true or false to determine if the head of the data must be consumed, it is no longer possible to say which character we were trying to parse. I updated the error message therefor to a real generic one: “Error parsing:”.

After adjusting the addLabel as well, the characterParser would still stay compatible. And now we can create a new parser. The stringCharParser that would ‘satisfy’ on each character except the double quote ".


1
2
3
4
5
6

const stringCharParser = satisfy((c) => c !== '"');

const quotedStringParser = andThenRight(quoteParser)(stringCharParser);

console.log(quotedStringParser('"test"')); // ['t', [ 'e', 's', 't', '"'] ]
console.log(quotedStringParser('""')); // [Symbol(Failed), 'Error parsing:', `Unexpected '"'`]

We could repeat a parser until it fails, to parse all the characters in the string. If it fails, we will return an empty result, to allow empty strings, and create the repeat process using recursion:


1
2

const many = (parser) => (stream) =>
  orElse(andThen(parser)(many(parser)))(resultParser([]))(stream);

The parser will try to apply itself, and on success call itself to try the next character. We are breaking one of the rules of the challenge now: Recursion to own function. For now, I just want to focus on completing the JSON parser, so I will park this challenge for later.

We are able to parse the whole (test) string now:


1
2
3

const quotedStringParser = andThenRight(quoteParser)(many(stringCharParser));

console.log(quotedStringParser('"test"')); // [[ 't', [ 'e', [Array] ] ], ['"'] ]

now only parsing the right quote, by adding a andThenLeft parser:


1
2
3
4
5
6
7
8

const andThenLeft = (parserA) => (parserB) =>
  mapResult((result) => result[0])(andThen(parserA)(parserB));

const quotedStringParser = andThenLeft(
  andThenRight(quoteParser)(many(stringCharParser))
)(quoteParser);

console.log(quotedStringParser('"test"')); // [[ 't', [ 'e', [Array] ] ], [] ]

The whole string is parsed, but the result is not a nice string as hoped. It has a nesting structure, caused by the andThen construct.


1

["t", ["e", ["s", "t"]]];

Lets change that, using the earlier built mapResult:


1

const toList = mapResult((result) => [result[0]].concat(result[1]));

And now wrap it around the andThen call in the many parser, to keep flattening the result:


1
2
3
4

const many = (parser) => (stream) =>
  orElse(toList(andThen(parser)(many(parser))))(resultParser([]))(stream);

console.log(quotedStringParser('"test"')); // [[ 't', 'e', 's', 't'], [] ]

Much better! Now add another mapResult in the quotedStringParser to join all the characters:


1
2
3
4
5
6
7
8

const toString = mapResult((result) => result.join(""));

const quotedStringParser = andThenLeft(
  andThenRight(quoteParser)(toString(many(stringCharParser)))
)(quoteParser);

console.log(quotedStringParser('"test"')); // ['test', [] ]
console.log(quotedStringParser('""')); // ['', [] ]

Simple strings can now be parsed, time for some refactoring:


1
2
3
4
5
6

const between = (parserLeft) => (parserMiddle) => (parserRight) =>
  andThenLeft(andThenRight(parserLeft)(parserMiddle))(parserRight);

const quotedStringParser = between(quoteParser)(
  toString(many(stringCharParser))
)(quoteParser);

The currying of between seems logical, because it semantically looks like a string parser between quote parsers. But I found out it is more logical to have the argument that could change the most to be at the end. This way you can profit the most from “partially applied functions”.


1
2
3
4
5
6

const between = (parserLeft) => (parserRight) => (parserMiddle) =>
  andThenLeft(andThenRight(parserLeft)(parserMiddle))(parserRight);

const quotedStringParser = between(quoteParser)(quoteParser)(
  toString(many(stringCharParser))
);

Lets say we would also like to create a quoted boolean parser, we could do it more easily when the middle section would be its last argument:


1
2
3
4

const quotedParser = between(quoteParser)(quoteParser);

const quotedStringParser = quotedParser(toString(many(stringCharParser)));
const quotedBooleanParser = quotedParser(boolParser);

Lets continue with the escape characters of our string:


1
2

console.log(quotedStringParser('"test\\nmultiple \\"lines\\""'));
// ['test\\nmultiple \\', [ 'l', 'i', 'n', 'e', 's', '\\', '"', '"'] ]

We could start by listing all special characters we have, and what result they should produce. Then create a choice parser, that is a orElse for a list of parsers. (Just like chain is for the andThen)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

const quoteParser = characterParser('"');
const stringCharParser = satisfy((c) => c !== '"' && c !== "\\");
const specialCharacters = [
  ['\\"', '"'],
  ["\\\\", "\\"],
  ["\\/", "/"],
  ["\\b", "\b"],
  ["\\f", "\f"],
  ["\\n", "\n"],
  ["\\r", "\r"],
  ["\\t", "\t"],
];
const choice = (parsers) => parsers.reduce((a, b) => orElse(a)(b));
const escapedCharParser = choice(
  specialCharacters.map(([match, result]) => parseStringResult(match)(result))
);

const quotedStringParser = between(quoteParser)(quoteParser)(
  toString(many(orElse(stringCharParser)(escapedCharParser)))
);
console.log(quotedStringParser('"test\\nmultiple \\"lines\\""'));
// ['test\nmultiple "lines"', [] ]

So the string was in there as well now. I really like how the chain andchoice are alike:


1
2

const chain = (parsers) => parsers.reduce((a, b) => andThen(a)(b));
const choice = (parsers) => parsers.reduce((a, b) => orElse(a)(b));

What I did not like however, was that the function passed into the .reduce had to accept 2 parameters. Time to force us into another direction, by adding yet another selector to our no-restricted-syntax eslint rule, in ourpackage.json:


1
2
3
4
5
6
7
8
9
10
11
12
13

{
  "eslintConfig": {
    "rules": {
      "no-restricted-syntax": [
        "error",
        {
          "selector": "ArrowFunctionExpression[params.length > 1]",
          "message": "Only 1 argument allowed. Please use currying"
        }
      ]
    }
  }
}

The following lines are now giving errors:


1
2

const chain = (parsers) => parsers.reduce((a, b) => andThen(a)(b));
const choice = (parsers) => parsers.reduce((a, b) => orElse(a)(b));

So we build our own, recursive reducer:


1
2
3
4
5
6
7

const doReduce = (reducer) => (start) => ([head, ...tail]) =>
  head ? doReduce(reducer)(reducer(start)(head))(tail) : start;

const reduce = (reducer) => ([head, ...tail]) => doReduce(reducer)(head)(tail);

console.log(doReduce((a) => (b) => a + b)(1)([2, 3, 4])); // 10
console.log(reduce((a) => (b) => a + b)([1, 2, 3, 4])); // 10

The doReduce function will accept a reducer, a start value and a list. The reducer should have the signature acc => elem => {}. The reduce function is a convenient method to use the first value of the list as initial accumulated value.

Having our new reducer function, we are now actually able to write:


1
2

const chain = (list) => reduce((a) => (b) => andThen(a)(b))(list);
const choice = (list) => reduce((a) => (b) => orElse(a)(b))(list);

Which is actually the same as:


1
2

const chain = reduce(andThen);
const choice = reduce(orElse);

🤯

The Number parser

An EBNF notation of a JSON Number looks like this:


1
2
3
4

number = ["-"],
  ( "0" | ? digit 1-9 ?, { ? digit ? } ),
  [".", ? digit ?, { ? digit ? }],
  [( "e" | "E" ), [ "+" | "-"], ? digit ?, { ? digit ? } ];

Lets idenfity the elements:

An optional sign “-“
An integer part
An optional fractional part
An optional exponent part

A number has a lot of optional parts, and a lot of ‘choices’ within them.

Time to introduce new parser tools for them:

AnyOf. Each character in the string is becoming an allowed character. This will help us define ‘digits’
Opt. If parsing fails, succeed anyway. (Thus making the first parse optional)


1
2

const anyOf = (string) => choice([...string].map(characterParser));
const opt = (parser) => orElse(parser)(resultParser([]));

We can now create the sign parser:


1

const optSign = opt(characterParser("-"));

And the integer parser:


1
2
3
4
5
6

const zero = characterParser("0");
const digitOneNine = anyOf("123456789");
const digit = anyOf("0123456789");

const nonZeroInt = toString(andThen(digitOneNine)(toString(many(digit))));
const intPart = orElse(nonZeroInt)(zero);

We use the toString to concat the results together. And we will use chain to add our individual pieces into a single parser:


1
2
3
4
5
6
7

const numberParser = chain([optSign, intPart]);

console.log(numberParser("-123.45e6"));
// [[ '-', '123'], ['.', '4', '5', 'e', '6'] ]

console.log(numberParser("123.45e-6"));
// [[ [], '123' ], ['.', '4', '5', 'e', '-', '6'] ]

Now the fraction part:


1
2
3
4
5
6
7
8
9
10

const some = (parser) => toList(andThen(parser)(many(parser)));
const point = characterParser(".");
const fractionPart = toString(andThen(point)(toString(some(digit))));
const numberParser = chain([optSign, intPart, opt(fractionPart)]);

console.log(numberParser("-123.45e6"));
// [[ [ '-', '123'], '.45' ], ['e', '6'] ]

console.log(numberParser("123.45e-6"));
// [[ [ [], '123' ], '.45' ], ['e', '-', '6'] ]

Now only the exponent part:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

const e = anyOf("eE");
const optPlusMinus = opt(anyOf("+-"));
const exponentPart = toString(chain([e, optPlusMinus, toString(some(digit))]));

const numberParser = chain([
  optSign,
  intPart,
  opt(fractionPart),
  opt(exponentPart),
]);

console.log(numberParser("-123.45e6"));
// [[ [ [Array], '.45' ], 'e,6' ], [] ]

console.log(numberParser("123.45e-6"));
// [[ [ [Array], '.45' ], 'e,-6' ], [] ]

The exponent part is not quite what we expected. It has returned e,6 instead of e6. This has to do with the toString over the chain function. The rest of the result is also acting like a russion doll. We need to flatten te result during the chain process, to prevent the nested andThen constructs to produce this nested result.


1
2
3
4
5
6
7
8
9
10
11

const chain = reduce((parserA) => (parserB) =>
  mapResult(([resultA, resultB]) => [...resultA, resultB])(
    andThen(parserA)(parserB)
  )
);

console.log(numberParser("-123.45e6"));
// [[ '-', '123', '.45', 'e6'], [] ]

console.log(numberParser("123.45e-6"));
// [[ '123', '.45', 'e-6'], [] ]

Much better! now we should convert it to an actual JavaScript number. To make it easy for use, we will use the Number() to typecast our parsed string to a number. The final number parser now looks like this:


1
2
3
4
5
6
7
8
9
10
11

const numberParser = addLabel("number")(
  mapResult((result) => Number(result))(
    toString(chain([optSign, intPart, opt(fractionPart), opt(exponentPart)]))
  )
);

console.log(numberParser("-123.45e6"));
// [-123450000, [] ]

console.log(numberParser("123.45e-6"));
// [0.00012345, [] ]

This is one seemed quite easy to build, even if a number has a lot of seperate parts.

The implementation so far:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

const FAILED = Symbol("Failed");
const PARSED = 0;
const REMAINING = 1;

const parseError = (message) => (error) => [FAILED, message, error];
const genericParseError = parseError("Error parsing:");

const satisfy = (predicate) => ([head, ...tail]) =>
  head
    ? predicate(head)
      ? [head, tail]
      : genericParseError(`Unexpected '${head}'`)
    : genericParseError("Unexpected EOF");

const onSuccess = (result) => (next) =>
  result[PARSED] !== FAILED ? next(result) : result;

const onFailure = (result) => (next) =>
  result[PARSED] === FAILED ? next(result) : result;

const addLabel = (label) => (parser) => (stream) =>
  onFailure(parser(stream))(([, , error]) =>
    parseError(`Error parsing '${label}':`)(error)
  );

const characterParser = (character) =>
  addLabel(character)(satisfy((c) => c === character));

const combineResult = (resultA) => (resultB) =>
  onSuccess(resultB)(() => [
    [resultA[PARSED], resultB[PARSED]],
    resultB[REMAINING],
  ]);

const andThen = (parserA) => (parserB) => (stream) =>
  onSuccess(parserA(stream))((result) =>
    combineResult(result)(parserB(result[REMAINING]))
  );

const orElse = (parserA) => (parserB) => (stream) =>
  onFailure(parserA(stream))(() => parserB(stream));

const resultParser = (result) => (stream) => [result, stream];

const mapResult = (transform) => (parser) => (stream) =>
  onSuccess(parser(stream))((result) => [
    transform(result[PARSED]),
    result[REMAINING],
  ]);

const andThenLeft = (parserA) => (parserB) =>
  mapResult((result) => result[0])(andThen(parserA)(parserB));

const andThenRight = (parserA) => (parserB) =>
  mapResult((result) => result[1])(andThen(parserA)(parserB));

const between = (parserLeft) => (parserRight) => (parserMiddle) =>
  andThenLeft(andThenRight(parserLeft)(parserMiddle))(parserRight);

const doReduce = (reducer) => (start) => ([head, ...tail]) =>
  head ? doReduce(reducer)(reducer(start)(head))(tail) : start;
const reduce = (reducer) => ([head, ...tail]) => doReduce(reducer)(head)(tail);

const chain = reduce((parserA) => (parserB) =>
  mapResult(([resultA, resultB]) => [...resultA, resultB])(
    andThen(parserA)(parserB)
  )
);
const choice = reduce(orElse);

const toList = mapResult((result) => [result[0]].concat(result[1]));
const toString = mapResult((result) => result.join(""));

const many = (parser) => (stream) =>
  orElse(toList(andThen(parser)(many(parser))))(resultParser([]))(stream);

const stringParser = (string) =>
  addLabel(string)(chain([...string].map((char) => characterParser(char))));

const parseStringResult = (string) => (result) =>
  andThenRight(stringParser(string))(resultParser(result));

const nullParser = parseStringResult("null")(null);
const boolParser = orElse(parseStringResult("true")(true))(
  parseStringResult("false")(false)
);

const quoteParser = characterParser('"');
const stringCharParser = satisfy((c) => c !== '"' && c !== "\\");
const specialCharacters = [
  ['\\"', '"'],
  ["\\\\", "\\"],
  ["\\/", "/"],
  ["\\b", "\b"],
  ["\\f", "\f"],
  ["\\n", "\n"],
  ["\\r", "\r"],
  ["\\t", "\t"],
];
const escapedCharParser = choice(
  specialCharacters.map(([match, result]) => parseStringResult(match)(result))
);

const quotedStringParser = addLabel("string")(
  between(quoteParser)(quoteParser)(
    toString(many(orElse(stringCharParser)(escapedCharParser)))
  )
);

const anyOf = (string) => choice([...string].map(characterParser));
const opt = (parser) => orElse(parser)(resultParser([]));
const some = (parser) => toList(andThen(parser)(many(parser)));
const optSign = opt(characterParser("-"));

const digitOneNine = anyOf("123456789");
const digit = anyOf("0123456789");

const point = characterParser(".");
const optPlusMinus = opt(anyOf("+-"));
const e = anyOf("eE");

const zero = characterParser("0");
const nonZeroInt = toString(andThen(digitOneNine)(toString(many(digit))));
const intPart = orElse(nonZeroInt)(zero);
const fractionPart = toString(andThen(point)(toString(some(digit))));
const exponentPart = toString(chain([e, optPlusMinus, toString(some(digit))]));

const numberParser = addLabel("number")(
  mapResult((result) => Number(result))(
    toString(chain([optSign, intPart, opt(fractionPart), opt(exponentPart)]))
  )
);

Conclusion

The code so far:

We changed our basic characterParser to a more generic satisfy function, and build a new characterParser upon that.
We added more tools to the parsing family:
- some (one or more)
- many (zero or more)
- opt (zero or one)
- anyOf (choice of character parsers)
We can now parse all ‘simple’ types in JSON. null, true, false, stringand number.
We refactored reduce into a curried function
Our parsers now produce a result based on the dynamic input, and of the proper type.
Check the full code here

What I learned so far:

Changing earlier basic functions around is quite easy
We are mainly building ‘tools’ to make a parser, instead of building the actual parser. The JSON specific part is still really small

What did I like:

When building it you really feel a gain in speed. We are working with bigger and bigger parts. It feels like ages when we first started with parsing a single character
The structure of the JSON part implementation is quite on-par with the EBNF definition
Changing the reduce into a curried version was really nice. If actually benefitted readability when being able to write: reduce(orElse)
It starts to feel more and more normal to only have a single argument for a function

What did I not like:

We should also update the .map and .join to curried versions

Next time:

Enforcing the single argument rule
Parsing arrays of values and objects

Learning functional programming #3: Combining parsers

Matthijs Groen — Fri, 05 Mar 2021 00:00:00 +0000

This post is part 3 of the series "Learning Functional Programming using JavaScript". Already read part 3? Part 4 of this Blog Post series is out now!

Earlier parts: part 1, part 2.

At this point, we are able to parse a single character from a string or array of
characters. We have applied a lot of eslint rules to force us to take a more and
more functional approach. In this post, we will start combining the parsers to
create more semantical constructions.

Since I have added a 'single statement' rule, my implementation will start to
deviate from the one in
the parser combinators blogpost from Scott Wlashin.
For more background on parser combinators, please checkout his blogpost.

We established a signature for our parser:

type Stream = string[];
type Success<ResultType> = [ResultType, Stream];
type Failure = [Symbol, string, string];
type Parser<ResultType> = (stream: Stream) => Success<ResultType> | Failure;

andThen parser

To actually parse more than one character, we want to create structure how the
parser should continue when successful or when it fails, by creating 2 more
parsers:

andThen (to chain a parser after a successful first parser)
orElse (to try an alternative parser after a failed attempt of the first parser)

const FAILED = Symbol("Failed");
const PARSED = 0;
const REMAINING = 1;

const parseError = (target) => (error) => [
  FAILED,
  `Error parsing: '${target}'`,
  error,
];

const characterParser = (character) => ([head, ...tail]) =>
  head
    ? head === character
      ? [head, tail]
      : parseError(character)(`Unexpected '${head}'`)
    : parseError(character)("Unexpected EOF");

const aParser = characterParser("a"); // see 'first-parser' post
const bParser = characterParser("b");

const andThen = (parserA) => (parserB) => (stream) => "???";

const abParser = andThen(aParser)(bParser);
console.log(abParser("abcd")); // "???"

We are now just testing out the signature. We want to use 2 parsers, and that
would produce a new parser that accepts the stream.

Just starting on running parserA:

const andThen = (parserA) => (parserB) => (stream) => parserA(stream);

const abParser = andThen(aParser)(bParser);
console.log(abParser("abcd")); // ["a", ["b", "c", "d"]]
console.log(abParser("iabcd")); // [ Symbol(Failed), "Error parsing 'a':", "Unexpected 'i'" ]
console.log(abParser("aibcd")); // ["a", ["i", "b", "c", "d"]]

Now we need to chain parserB to it if successful:

const PARSED = 0;
const onSuccess = (result) => (next) =>
  result[PARSED] !== FAILED ? next(result) : result;

Using this function, I can determine if we had a success. If it is successful,
the parser will execute the next step, providing the result.

And now in action:

const REMAINING = 1;
const andThen = (parserA) => (parserB) => (stream) =>
  onSuccess(parserA(stream))((result) => parserB(result[REMAINING]));

const abParser = andThen(aParser)(bParser);
console.log(abParser("abcd")); // [ 'b', [ 'c', 'd' ] ]
console.log(abParser("iabcd")); // [ Symbol(Failed), "Error parsing 'a':", "Unexpected 'i'" ]
console.log(abParser("aibcd")); // [ Symbol(Failed), "Error parsing 'b':", "Unexpected 'i'" ]

Ok, the last 2 lines are as expected now. But the first one is incorrect. The
result of the parse should not be 'b', but ['a', 'b'].

We need to combine the result from parser A with parser B:

const combineResult = (resultA) => (resultB) =>
  onSuccess(resultB)(() => [
    [resultA[PARSED], resultB[PARSED]],
    resultB[REMAINING],
  ]);

const andThen = (parserA) => (parserB) => (stream) =>
  onSuccess(parserA(stream))((result) =>
    combineResult(result)(parserB(result[REMAINING]))
  );

console.log(abParser("abcd")); // [ [ 'a', 'b' ], [ 'c', 'd' ] ]
console.log(abParser("iabcd")); // [ Symbol(Failed), "Error parsing 'a':", "Unexpected 'i'" ]
console.log(abParser("aibcd")); // [ Symbol(Failed), "Error parsing 'b':", "Unexpected 'i'" ]

We are now already reusing building blocks! (onSuccess) And we have a correct
result!

orElse parser

const aParser = characterParser("a");
const bParser = characterParser("b");

const orElse = (parserA) => (parserB) => (stream) => "???";

const aOrBParser = orElse(aParser)(bParser);
console.log(aOrBParser("abcd")); // "???"

It will follow the same pattern. But the implementation of this one will already
be a lot faster:

const onFailure = (result) => (next) =>
  result[PARSED] === FAILED ? next(result) : result;

const orElse = (parserA) => (parserB) => (stream) =>
  onFailure(parserA(stream))(() => parserB(stream));

const aOrBParser = orElse(aParser)(bParser);
console.log(aOrBParser("abcd")); // [ 'a', [ 'b', 'c', 'd' ] ]
console.log(aOrBParser("bcde")); // [ 'b', [ 'c', 'd', 'e' ] ]
console.log(aOrBParser("iabcd")); // [ Symbol(Failed), "Error parsing 'b':", "Unexpected 'i'" ]

Wow this one worked immediately! This is because we never modify the stream. We
create a new stream every time. So parserB is able to retry it on exactly the
same data.

All well so far...

The implementation so far:

const FAILED = Symbol("Failed");
const PARSED = 0;
const REMAINING = 1;

const parseError = (target) => (error) => [
  FAILED,
  `Error parsing: '${target}'`,
  error,
];

const characterParser = (character) => ([head, ...tail]) =>
  head
    ? head === character
      ? [head, tail]
      : parseError(character)(`Unexpected '${head}'`)
    : parseError(character)("Unexpected EOF");

const onSuccess = (result) => (next) =>
  result[PARSED] !== FAILED ? next(result) : result;

const onFailure = (result) => (next) =>
  result[PARSED] === FAILED ? next(result) : result;

const combineResult = (resultA) => (resultB) =>
  onSuccess(resultB)(() => [
    [resultA[PARSED], resultB[PARSED]],
    resultB[REMAINING],
  ]);

const andThen = (parserA) => (parserB) => (stream) =>
  onSuccess(parserA(stream))((result) =>
    combineResult(result)(parserB(result[REMAINING]))
  );

const orElse = (parserA) => (parserB) => (stream) =>
  onFailure(parserA(stream))(() => parserB(stream));

Working towards parsing our JSON structure

The challenge was parsing the JSON structure at the top of our file.

An EBNF notation of JSON looks like this:

value = object | array | number | string | "true" | "false" | "null";
string = '"',
  { ? Any unicode character except " or \ or control character ?
  | "\", (
    '"' | "\" | "/" | "b" | "f" | "n" | "r" | "t" |
    "u", 4 * ? hexadeximal digit ?
  ) }, '"';

number = [ "-" ],
  ( "0" | ? digit 1-9 ?, { ? digit ? } ),
  [ ".", ? digit ?, { ? digit ? } ],
  [ ( "e" | "E" ), [ "+" | "-" ], ? digit ?, { ? digit ? } ];

array = "[", [ value, { ",", value } ], "]";
object = "{", [ string, ":", value, { ",", string, ":", value } ], "}";

The most simple type in this format would be the null. So we should start with
parsing that one.

const nParser = characterParser("n");
const uParser = characterParser("u");
const lParser = characterParser("l");

const nullParser = andThen(nParser)(
  andThen(uParser)(andThen(lParser)(lParser))
);

console.log(nullParser("null")); // [ [ 'n', [ 'u', [Array] ] ], [] ]
console.log(nullParser("text"));

We can now verify that the string starts with "null". But we also want the
result of parsing not be a nested construction, we want the literal null as
result. In this case, we do not need to really process the result. We only need
to verify that the string was "null" so that we can return the literal null.

Let's create a parser that would return a specific value as result:

const resultParser = (result) => (stream) => [result, stream];

const returnNullParser = resultParser(null);
console.log(returnNullParser("test")); // [ null, 'test' ]

Now we need the characterParsers to verify that the string "null" is in the
stream, and then return the result:

const resultParser = (result) => (stream) => [result, stream];

const nParser = characterParser("n");
const uParser = characterParser("u");
const lParser = characterParser("l");

const nullParser = andThen(
  andThen(nParser)(andThen(uParser)(andThen(lParser)(lParser)))
)(resultParser(null));

console.log(nullParser("null")); // [ [ [ 'n', [Array] ], null ], [] ]
console.log(nullParser("text")); // [ Symbol(Failed), "Error parsing 'n':", "Unexpected 't'" ]

We can now verify that the string contains "null" but the result now contains
our converted result, but also the parsed text, that is not needed anymore. We
will create a andThenRight function. it will require to parse both results
(like andThen) but will only return the result of the right completed parser.

const andThenRight = (parserA) => (parserB) => (stream) =>
  onSuccess(andThen(parserA)(parserB)(stream))((result) => [
    result[PARSED][1],
    result[REMAINING],
  ]);

const nullParser = andThenRight(
  andThen(nParser)(andThen(uParser)(andThen(lParser)(lParser)))
)(resultParser(null));

console.log(nullParser("null")); // [ null, [] ]
console.log(nullParser("text")); // [ Symbol(Failed), "Error parsing 'n':", "Unexpected 't'" ]

Yes! We did a lot of actions here and it would be great to allow reuse by
refactoring. First: Changing the result of a parser (what andThenRight does)

const mapResult = (transform) => (parser) => (stream) =>
  onSuccess(parser(stream))((result) => [
    transform(result[PARSED]),
    result[REMAINING],
  ]);

const andThenRight = (parserA) => (parserB) =>
  mapResult((result) => result[1])(andThen(parserA)(parserB));

And we could replace the nullParser with the 3 character parsers with this:

const stringParser = (string) =>
  [...string]
    .map((char) => characterParser(char))
    .reduce((a, b) => andThen(a)(b));

const nullParser = andThenRight(stringParser("null"))(resultParser(null));

Much more readable! But the stringParser is now still doing 2 tasks:

convert string characters to a list of character parsers
chain the characters parsers using andThen

We could split this up as well.

const chain = (parsers) => parsers.reduce((a, b) => andThen(a)(b));
const stringParser = (string) =>
  chain([...string].map((char) => characterParser(char)));

const nullParser = andThenRight(stringParser("null"))(resultParser(null));

If we make this one step more generic, we can create the boolean parser as well!

const parseStringResult = (string) => (result) =>
  andThenRight(stringParser(string))(returnResult(result));

const nullParser = parseStringResult("null")(null);

const boolParser = orElse(parseStringResult("true")(true))(
  parseStringResult("false")(false)
);

console.log(nullParser("null rest")); // [ null, [ ' ', 'r', 'e', 's', 't' ] ]
console.log(boolParser("true rest")); // [ true, [ ' ', 'r', 'e', 's', 't' ] ]
console.log(boolParser("false rest")); // [ false, [ ' ', 'r', 'e', 's', 't' ] ]
console.log(boolParser("fase rest")); // [ Symbol(Failed), "Error parsing 'l':", "Unexpected 's'" ]

It works as expected. The problem I have now is the error message is too vague
to know it was from parsing a null or a boolean.

Time to improve the message in an error occurs. Fortunately, this is really
easy. We can use the onFailure we created before to update the error with a
custom message.

const addLabel = (label) => (parser) => (stream) =>
  onFailure(parser(stream))(([, , error]) => parseError(label)(error));

And now we can use this function to wrap it around the stringParser

const stringParser = (string) =>
  addLabel(string)(chain([...string].map((char) => characterParser(char))));

console.log(boolParser("fase rest")); // [ Symbol(Failed), "Error parsing 'false':", "Unexpected 's'" ]

So we have nice messages as well. The composability of the functions really seems
to pay off. The JSON parser seems to come to shape nicely. There are some things
still bothering me about this implementation though and that is that using
JavaScripts own .map and .reduce seem out of place. But we will first try to
get the JSON parser complete, and then look into those functions.

The implementation so far:

const FAILED = Symbol("Failed");
const PARSED = 0;
const REMAINING = 1;

const parseError = (target) => (error) => [
  FAILED,
  `Error parsing: '${target}'`,
  error,
];

const characterParser = (character) => ([head, ...tail]) =>
  head
    ? head === character
      ? [head, tail]
      : parseError(character)(`Unexpected '${head}'`)
    : parseError(character)("Unexpected EOF");

const onSuccess = (result) => (next) =>
  result[PARSED] !== FAILED ? next(result) : result;

const onFailure = (result) => (next) =>
  result[PARSED] === FAILED ? next(result) : result;

const combineResult = (resultA) => (resultB) =>
  onSuccess(resultB)(() => [
    [resultA[PARSED], resultB[PARSED]],
    resultB[REMAINING],
  ]);

const andThen = (parserA) => (parserB) => (stream) =>
  onSuccess(parserA(stream))((result) =>
    combineResult(result)(parserB(result[REMAINING]))
  );

const orElse = (parserA) => (parserB) => (stream) =>
  onFailure(parserA(stream))(() => parserB(stream));

const resultParser = (result) => (stream) => [result, stream];

const mapResult = (transform) => (parser) => (stream) =>
  onSuccess(parser(stream))((result) => [
    transform(result[PARSED]),
    result[REMAINING],
  ]);

const andThenRight = (parserA) => (parserB) =>
  mapResult((result) => result[1])(andThen(parserA)(parserB));

const addLabel = (label) => (parser) => (stream) =>
  onFailure(parser(stream))(([, , error]) => parseError(label)(error));

const chain = (parsers) => parsers.reduce((a, b) => andThen(a)(b));

const stringParser = (string) =>
  addLabel(string)(chain([...string].map((char) => characterParser(char))));

const parseStringResult = (string) => (result) =>
  andThenRight(stringParser(string))(resultParser(result));

const nullParser = parseStringResult("null")(null);

const boolParser = orElse(parseStringResult("true")(true))(
  parseStringResult("false")(false)
);

Conclusion

The code so far:

We can now combine using andThen, orElse, andThenRight, addLabel, and chain
We can return a result using resultParser
We can improve parse error messages using addLabel
We can parse a null, true and false
Check the full code here

What I learned so far:

Currying is actually pretty easy to get used to
Having functions with only one statement doesn't feel like a handicap yet

What did I like:

It's fun building a parser this way
Composition feels powerful
Creating new features seems to profit a lot from existing code, the reuse is nice
Ability to slap on addLabel where needed without worrying about changing the output format

What did I not like:

If you want to have many expressions in a single statement, the code does get harder to read (lots of parentheses)

Next time:

Building a quoted string parser
Building a number parser
Checking out recursion

Learning Functional Programming #2: Creating the first Parser

Matthijs Groen — Fri, 26 Feb 2021 00:00:00 +0000

This post is part 2 of the series "Learning Functional Programming using JavaScript". Already read part 2? Part 3 of this Blog Post series is out now!

Earlier parts: Part 1.

So in the folder where I created my challenge.js file, I added:

git init .
yarn init
yarn add eslint --dev

eslint is a linting tool for ECMAScript, where you can define your own rules
of what you consider to be "good" code.

Now that I added eslint, I could add custom rules, by updating my just generated
package.json file:

{
  "name": "json-parse-fp",
  "version": "1.0.0",
  "main": "index.js",
  "author": "Matthijs Groen <matthijs.groen@kabisa.nl>",
  "license": "MIT",
  "devDependencies": {
    "eslint": "^5.15.1"
  },
  "eslintConfig": {
    "parserOptions": {
      "ecmaVersion": 2018
    },
    "env": {},
    "extends": "eslint:recommended"
  }
}

In eslint, you normally specify an env in which the code will be run, like a
browser, node or worker. This will automatically allow a lot of syntax
specific to such an environment. By not specifying an env, I was restricting a
lot of standard JS. But in this case even too much. Type objects like String,
Array and Number were also disabled, and console.log was also not allowed.

(normally having no console.log is a good thing, it prevents debug or other
info from remaining in your code when it is no longer needed).

But since I was not exporting anything from my file, I needed a way to see some
output of my code. So I enabled console.log manually.

Additions to the eslint config:

{
  "eslintConfig": {
    "globals": {
      "Symbol": "readonly",
      "Array": "readonly",
      "String": "readonly",
      "Number": "readonly",
      "console": "readonly"
    },
    "rules": {
      "no-console": "off"
    }
  }
}

The editor I'm using applies these rules directly, so I would have direct
feedback whether I was breaking any of my own rules.

I even added some more rules to prevent cheating:

{
  "eslintConfig": {
    "rules": {
      "no-use-before-define": "error",
      "no-eval": "error",
      "no-implied-eval": "error",
      "no-restricted-globals": ["error", "JSON"]
    }
  }
}

So now when I would try to lint:

const data = '{ "foo": 42 }';
JSON.parse(data);
eval("JSON.parse(data)");

I would get the output:

  2:1  error  Unexpected use of 'JSON'  no-restricted-globals
  3:1  error  eval can be harmful       no-eval

✖ 2 problems (2 errors, 0 warnings)

Great! Let's start!

Parsing the first character

Just like
the Parser Combinator post,
I started by creating a parser that could only parse a specific single character
from an input (the letter a). On success, it should return the parsed result
and the rest of the input. On failure, it should return an indication that it
failed containing the message what it tried to achieve, and why it failed:

const FAILED = Symbol("Failed");

const aParser = ([head, ...tail]) =>
  head === "a"
    ? [head, tail]
    : [FAILED, "Error parsing 'a':", `Unexpected '${head}'`];

console.log(aParser("abc")); // [ 'a', [ 'b', 'c' ] ]
console.log(aParser("aabc")); // [ 'a', [ 'a', 'b', 'c' ] ]
console.log(aParser("bcd")); // [ Symbol(Failed), "Error parsing 'a':", "Unexpected 'b'" ]

Using the spread operator ([head, ...tail]) I would separate the first
character from the rest, and compare it to the letter "a". Notice that the tail
is automatically transformed into an array of characters.

To change that we could parse more than just the "a", it would be smart to turn
the character we parse into a function argument:

const parser = (character, [head, ...tail]) =>
  head === character
    ? [head, tail]
    : [FAILED, `Error parsing '${character}':`, `Unexpected '${head}'`];

console.log(parser("a", "abc")); // [ 'a', [ 'b', 'c' ] ]
console.log(parser("a", "aabc")); // [ 'a', [ 'a', 'b', 'c' ] ]
console.log(parser("a", "bcd")); // [ Symbol(Failed), "Error parsing 'a':", "Unexpected 'b'" ]

The output of each console.log would be the same. But is it an improvement?

Yes and no.

Yes, we made the character to parse dynamic. And No, because we changed the
function signature.

This last one would seem trivial, but it is not. The reason is that we want to
combine the parser (hence: Parser Combinators). To combine parsers, they should
all follow the same signature. Data string in, and Result and Remaining out, or
an Error with details.

Currying

To get around this issue, we can use a concept, called Currying. As Wikipedia
states it:

In mathematics and computer science, currying is the technique of translating
the evaluation of a function that takes multiple arguments into evaluating a
sequence of functions, each with a single argument.

This would actually mean that our function would not be "data" in, "data" out
like I was used to. It would be "data" in, "function" out. Like a function
factory.

A mathematical example:

const add = (a, b) => a + b;
add(1, 3); // 4

const addCurried = (a) => (b) => a + b;
const addOne = addCurried(1); // new function
addOne(3); // 4
addOne(5); // 6
addCurried(7)(4); // 11

This is a really powerful concept. Not only can we create a function that would
return a letter parser in the parser example, this also means you can capture
some state inside these functions!

Time to update the parser:

const characterParser = (character) => ([head, ...tail]) =>
  head === character
    ? [head, tail]
    : [FAILED, `Error parsing '${character}':`, `Unexpected '${head}'`];

const aParser = characterParser("a");
const bParser = characterParser("b");

console.log(aParser("abc"));
console.log(aParser("abc")); // [ 'a', [ 'b', 'c' ] ]
console.log(aParser("aabc")); // [ 'a', [ 'a', 'b', 'c' ] ]
console.log(aParser("bcd")); // [ Symbol(Failed), "Error parsing 'a':", "Unexpected 'b'" ]
console.log(bParser("bcd")); // [ 'b', [ 'c', 'd' ] ]
console.log(aParser("")); // [ Symbol(Failed), "Error parsing 'a':", "Unexpected 'undefined'" ]

On desktop browsers you can follow along by opening the console and pasting
the code in there.

Hmm that last one is not that nice. It is actually stating it reached the end of
the file, so we change it into an EOF error:

const characterParser = (character) => ([head, ...tail]) =>
  head
    ? head === character
      ? [head, tail]
      : [FAILED, `Error parsing '${character}':`, `Unexpected '${head}'`]
    : [FAILED, `Error parsing: '${character}':`, "Unexpected EOF"];

const aParser = characterParser("a");

console.log(aParser("")); // [ Symbol(Failed), "Error parsing 'a':", "Unexpected EOF" ]

The error is improved, but now the construction of an error is duplicated. Let's
refactor that one:

const parseError = (target) => (error) => [
  FAILED,
  `Error parsing: '${target}'`,
  error,
];

const characterParser = (character) => ([head, ...tail]) =>
  head
    ? head === character
      ? [head, tail]
      : parseError(character)(`Unexpected '${head}'`)
    : parseError(character)("Unexpected EOF");

const aParser = characterParser("a");

console.log(aParser("")); // [ Symbol(Failed), "Error parsing 'a':", "Unexpected EOF" ]

So now I can create a parser for any one character I would like. The next step
would be creating a parser that would be a combination of multiple character
parsers.

But, feeling more confident, it was time to enforce more rules:

Each function could only contain 1 statement.
Each function should be written as a lambda.
No if statements

What is a statement, what is an expression

You can see a statement as a line of code, in JavaScript terminated by a
semi-colon (;).

const aVar = 2;
const myFunc = (number) => number * 6;
const result = aVar + 6 * myFunc(3);

This code has 3 statements: The definition of aVar, myFunc and result. The
myFunc function, has 1 statement: number * 6.

An expression is anything that can return a value: 2, number, 6, aVar,
myFunc(3). So in a single statement, you can use multiple expressions, and
combine them even to produce new values. (using addition + or multiply * for
example).

So the last line is actually 1 statement, containing 4 expressions.

Since we could do quite some work in a single statement, I wanted to limit the
amount of statements for a lambda to 1. With having only 1 statement in a
lambda, you can omit the function body and an explicit return statement.

const multiStatementLambda = (a) => {
  const b = 5;
  return a + b;
};

const singleStatementLamda = (a) => a + 5;

So now our eslint rules in the package.json look like this:

{
  "eslintConfig": {
    "parserOptions": {
      "ecmaVersion": 2018
    },
    "extends": "eslint:recommended",
    "env": {},
    "globals": {
      "Symbol": "readonly",
      "Array": "readonly",
      "String": "readonly",
      "Number": "readonly",
      "console": "readonly"
    },
    "rules": {
      "no-console": "off",
      "no-use-before-define": "error",
      "no-eval": "error",
      "no-implied-eval": "error",
      "no-restricted-globals": ["error", "JSON"],
      "max-statements": ["error", 1, { "ignoreTopLevelFunctions": false }],
      "complexity": ["error", { "max": 3 }],
      "arrow-body-style": ["error", "as-needed"],
      "no-restricted-syntax": [
        "error",
        {
          "selector": "FunctionExpression",
          "message": "Please use Lambda notation () =>"
        },
        {
          "selector": "IfStatement",
          "message": "Try using ternary operator: true ? 1 : 2"
        },
        {
          "selector": "VariableDeclaration[kind=let],VariableDeclaration[kind=var]",
          "message": "Only use constants"
        }
      ]
    }
  }
}

Conclusion

The code so far:

Our parser is now able to parse one character
We've created an input and output format (result and error) for the parser, that other parser should follow as well
Check the full code here

What I learned so far:

Currying

What did I like:

So far was easy! Writing these lines of code only took a few minutes. We've spent more time on setup

What did I not like:

Nothing so far

Next time:

Combining parsers into new ones

Part 3

Part 3 of this Blog Post series is out now!

My journey in learning Functional Programming

Matthijs Groen — Tue, 16 Feb 2021 00:00:00 +0000

This post is part 1 of the series "Learning Functional Programming using JavaScript". Already read part 1? Part 2 and part 3 of this Blog Post series are out now!

Functional Programming

Hi, I'm Matthijs Groen, a frontend developer at
Kabisa and I would like to share my experiences with
diving into the concepts of Functional Programming.

Before we dive into the Functional Programming (FP) goodness, I'd like to share
where I was coming from and why I had so much trouble adjusting to the FP
concepts.

I spent most of my developer life writing object-oriented code and some
procedural code before that. In Object-Oriented programming (at least how I was
taught) how you name objects, methods etc. matters.

I have worked with Ruby on Rails for years. Not only
was everything an object in that language, Rails itself is a framework with
"conventions". These conventions make you productive in some cases, but also
make you feel trapped in others.

3.times do
  puts "This will be printed 3 times"
end

Yes, even a number is an object.

After working with Ruby (doing full-stack), my work changed to be more front-end
only. We used Backbone.js for years. Backbone, just
like Ruby on Rails is Object-Oriented, and follows the Model-View-Controller
pattern.

A few years ago we changed the front-end stack from Backbone.js (in combination
with CoffeeScript) to
Preact, Redux and modern
ECMAScript.

The thing I liked most when I just switched from Backbone.js to Preact was the
way you could nest views. In Backbone this really was a pain. So you would end
up with big templates. In Preact, you make a small reusable component for
everything, and nesting views was actually the way to build up your UI.

It also changed for us where logic lived.

The location of logic was no longer decided by the framework. You could put it
everywhere. This made the business logic totally separate and on its own. Easier
to test, in loose small functions. No framework to have any opinion about it.
Data in, data out. Just functions, and functions calling other functions.

No hidden dependencies, or object hierarchies.

It makes refactoring or moving code around a breeze. Now not only the views were
composable, the whole software became composable.

<HeaderBar theme="blue">
  <SiteMenu />
  <UserProfile user={user} />
</HeaderBar>

Nesting views (Components) in Preact is as easy as nesting HTML self.

First steps...

I really started to like this approach. In the meantime, I got more colleagues
on my team that really were into functional programming.
Elixir, Haskell,
Monoids, Functors, Category theory. I didn't understand half of what they were
saying. And when I asked to explain stuff to me, most of the time it only gave
me headaches...

But I really started to like working with functions only approach. No
getName() that could reply with a different value each time you called it. It
became more predictable. Also working with Redux brought new concepts to the
table such as immutability. Not changing data, but reconstructing new data based
on changes.

An example:

Before:

class Person {
  constructor(firstName, lastName, age) {
    super();
    this.firstName = firstName;
    this.lastName = lastName;
    this.age = age;
  }

  getName() {
    return `${this.firstName} ${this.lastName}`;
  }
  getAge() {
    return this.age;
  }
  increaseAge(amount) {
    this.age += amount;
  }
}

const me = new Person("Matthijs", "Groen", 37);
me.getAge(); // 37
me.increaseAge(1);
me.getAge(); // 38
me.getName(); // Matthijs Groen

After:

const me = {
  firstName: "Matthijs",
  lastName: "Groen",
  age: 37,
};

const getName = (person) => `${person.firstName} ${person.lastName}`;
const getAge = (person) => person.age;
const increaseAge = (person, amount) => ({
  ...person,
  age: person.age + amount,
});

getAge(me); // 37
const olderMe = increaseAge(me, 1);
getAge(me); // still 37!
getAge(olderMe); // 38!
getName(me); // Matthijs Groen

There are more benefits:

Since a function only relies on its directly provided input and is not allowed to change that input, not handling the result would actually make the function call as if it never happened.
When you are not allowed to change things, you know what data you are dealing with. It did not change by itself, unless you got new data after calling a function to change the data.
Since this relation of input and output is so strict, you can cache processes better, skipping performance heavy steps.
Reusability is very, very high. Functions have less responsibilities, are generalizing data patterns and allow for great composition into larger solutions.

So I wanted to learn more about these concepts, and practise them. I wanted to
understand all "the fuss".

But there is a big gap coming from an object oriented world, where language were
designed to be easily readable and code was written as if they where stories,
and going to a world where stuff is expressed as math and concepts with strange
names are explained by even stranger names.

fmap :: (a -> b) -> f a -> f b

yep.

A colleague pointed me to
"Functors, applicatives and monads in pictures".
By just reading the article it was hard to make something out of it. It started
to make sense to me only after I opened the browser console and started typing
JavaScript to try and follow along. Learning by doing works better than reading
alone.

Opening the browser developer console
for this series is also a great way to follow along what I am building 🙂

I could replicate the concepts, but I did not understand them, or how it would
help me write better software.

I was intrigued by
a video about Parser Combinators
by Scott Wlaschin, because I work and create DSLs in various projects. It looked
like fun to build something like that for myself.

So I decided to create a challenge for myself, to learn more about Functional
Programming and playing around with the concept of Parser Combinators.

The Challenge

Since I'm more of a learning by doing kind of guy and work only in JavaScript
nowadays, I opened my editor and defined the following challenge in a
challenge.js file:

const data = `
{
  "name": "Functional programming challenge",
  "goal": [
    "create a function that takes one argument that is a path into this JSON struct",
    "get(data)(\\"using.disallowed.0\\") should result in \\"Dependencies\\"",
    "get(data)(\\"points.full-json\\") should result in 1000",
    "get(data)(\\"jsonTypes.2\\") should result in false"
  ],
  "using": {
    "allowed": [
      "Only code in this file",
      "Only functions that take one argument",
      "Ternary operator true ? a : b"
    ],
    "disallowed": [
      "Dependencies",
      "Recursion to own function",
      "JSON.parse",
      "Usage of 'if'",
      "Usage of for/while loops",
      "Usage of functions before they are defined",
      "Host object functions (.split, .map, .reduce, etc)",
      "Multiple statements in a lambda"
    ]
  },
  "hints": [
    "Think about function composition and currying",
    "Think about parser combinators",
    "https://fsharpforfunandprofit.com/posts/understanding-parser-combinators/"
  ],
  "points": {
    "not-trying": 0,
    "started": 5,
    "full-json": 1e3,
    "without-recursion": 1e4
  },
  "jsonTypes": [null, true, false, -0.12]
}
`;

/**
 * So, not like this!
 * no function usage of the host language, no dependencies
 *
 * import get from "lodash/get";
 *
 * const ast = JSON.parse(data);
 * const get = ast => path => get(ast, path)
 * console.log(get(ast)("using.disallowed.0"));
 *
 */

Would I be able to create purely functional code to parse the defined JSON?

Yes, I even added a Recursion to own function in there, after watching
"The next great functional programming language"
just to see if it would really be possible.

In this talk, John de Goes argues that a good programming language could do
without:

Pattern matching, Records, Modules, Syntax, Type classes, Nominative typing,
Data, Recursion

https://www.slideshare.net/jdegoes/the-next-great-functional-programming-language
(see slide 11 for the list)

Having the blogpost of Parser Combinators ready at hand, it would be a simple
exercise of following along and implementing it in JavaScript and trying to
apply a few more rules along the way.

But I was wrong!

I never knew I would learn so much in a few days...

In the upcoming posts I would like to take you along the journey I made into
Functional Programming. This post deliberately ends here, so if you would like
to do the challenge yourself, you can do so without spoilers.

Note:

I originally did this challenge in the beginning of 2019. I revisited this
challenge again in 2020, and did a typescript implementation. (to learn
typescript as well 😄) It does not change the concepts used here, but the
implementation will slightly differ. When it makes sense, typescript parts are
included as well. (full typescript and javascript implementations will be
shared at the end of the series).

My Journey in learning Functional Programming #2

Already read part 1? Part 2 and part 3 of this Blog Post series are out now!

Playing around with ESLint

Matthijs Groen — Mon, 01 Feb 2021 10:11:42 +0000

In order to learn myself Functional Programming (FP) using Javascript, I wanted to restrict myself from cheating and forcing myself to a particular syntax.

To do this, I used ESLint

eslint is a linting tool for EcmaScript, where you can define your own rules
of what you consider to be "good" code.

ESLint has no fixed set of rules. There are recommended configurations for
different environments, but you are free to add or modify your own rules.

I Also gave a presentation @ Kabisa about this subject. So you can also checkout the video below.

style="position:absolute;top:0;left:0;width:100%;height:100%;">

Powerful rule

There is one rule that is really, really powerful: no-restricted-syntax
(https://eslint.org/docs/rules/no-restricted-syntax)

It works like this: The EcmaScript/JavaScript you write is a piece of text that goes through a parser. This parser in turn will create a data model of the code that has been typed. This is called an Abstract Syntax Tree (AST).

You can see this in action using https://astexplorer.net/ (You can explore the AST of many languages there). You can enter code in the left input, and it will show the AST (Abstract Syntax Tree) on the right side.

You can compare this tree a bit like HTML also is a tree of nodes (and
attributes). Following this same concept, you can target specific elements in this tree using a selector (just like in CSS!)

https://eslint.org/docs/developer-guide/selectors

To show you some examples how neat this is:

{
  "rules": {
    "no-restricted-syntax": [
      "error",
      {
        "selector": "CatchClause > BlockStatement[body.length=0]",
        "message": "No empty catch blocks!"
      }
    ]
  }
}

This line will now add an error if you have empty catch blocks.

or this one:

{
  "rules": {
    "no-restricted-syntax": [
      "error",
      {
        "selector": "CatchClause > :not(CallExpression[callee.name=\"logError\"])",
        "message": "Missing error reporting in catch block"
      }
    ]
  }
}

Having the option for a custom message can also give hints of how you want it to
be done:

{
  "rules": {
    "no-restricted-syntax": [
      "error",
      {
        "selector": "FunctionExpression",
        "message": "Please use the lambda () => notation"
      },
      {
        "selector": "VariableDeclarator[id.name=/get.*/] > ArrowFunctionExpression > AssignmentExpression",
        "message": "No assignments in getters"
      },
      {
        "selector": "VariableDeclarator[id.name=/select.*/] > ArrowFunctionExpression[params.0.name!=\"state\"]",
        "message": "First argument of selector should be called state"
      }
    ]
  }
}

No-restricted-syntax

ESLint has a lot of great rules out of the box, but the no-restricted-syntax takes the linting to a whole new level.

There are some things you cannot do however. I wanted to create a rule to
restrict self-referencing recursion. But since I needed the identifier to match, you cannot use placeholders to match it.

I had to create a custom ESLint plugin for this. Fortunately, creating one is really easy, using yeoman and the generator created here.

"Follow the instructions"

Its mainly a "follow the instructions" exercise. There were 2 pitfalls I ran
into:

One was specifying a parser for my rules, because the default parser is ES3, and not a modern JS parser.

So my generated test looked like this:

ruleTester.run("fp-challenge", rule, {
  invalid: [
    {
      code: "const fib = n => n <= 1 ? 1 : fib(n - 1) + fib(n - 2);",
    },
  ],
});

And I needed to add parser options to that test:

ruleTester.run("fp-challenge", rule, {
  invalid: [
    {
      code: "const fib = n => n <= 1 ? 1 : fib(n - 1) + fib(n - 2);",
      parserOptions: { ecmaVersion: 6 },
    },
  ],
});

Before I got the proper error message.

The other pitfall is if you want the user to allow specifying options for your rule, you need to provide a JSON schema to allow valdiation for these options. But the problem is, you need to restart the tests before the provided JSON schema is reparsed. So if you run the tests using yarn test --watch you keep wondering why tests keep failing or keep passing, and not pick up the changes you made to the schema.

I found the Understanding JSON schema
helpful in the defintion of a schema. The main website is confusing to find the right info.

Having a proper ESlint configuration helps in enforcing best practices of your team, and even leave helpful hints to other members just joining your team. It can help capture the spirit of development within the project itself.

Happy linting!

To checkout the plugin I wrote for my FP Challenge, check: https://github.com/matthijsgroen/eslint-plugin-fp-challenge

Rails without tha added sugar

Ariejan de Vroom — Thu, 21 Jan 2021 00:00:00 +0000

A modern web application has many moving parts, Ruby on Rails is no exception. With a new Ruby on Rails 6.1 application there's a lot you get for free.

What you get for free:

Outgoing email handling (action_mailer)
Incoming email handling (action_mailbox)
Text markup / editing in the browser that works (action_text)
Compiling and bundling static assets like CSS, JavaScript, fonts and images (sprockets)
Making use of the whole NPM ecosystem for front-end technology (webpacker)
Background workers (active_job)
Websockets with fallback (action_cable)
An awesome DSL to generate JSON (jbuilder)
Make your application load faster in the browser (turbolinks)
Increase performance by caching expensive computations (bootsnap)
Application pre-loader (spring)
Store files locally or in the cloud (active_storage)

However, there are times you want to start with something simpler, without
the burden of all these extras.

A minimal approach

You could use all the --skip-* options to disable each of these, but
Rails 6.1. packs the --minimal option instead:

rails new my_app --minimal

It should be noted that this does not imply a classic Rails app, as
DHH eloquently put it:

Classic gives it an air of cool that I'm not interested in. It's not about reminiscing of some glorious past. It's just "I want the bare minimum"

That bare minimum is a great starting point if you're not yet ready for all the goodies and
maybe uncertain whether you're going to need them at all. Adding the ones you need later it
just like adding any other gem to your Rails project.

I'm a big proponent of this approach, as less dependencies (you don't use) means your codebase
will be easier to maintain and upgrade in the future.

More points with combos!

If you're really into front-end and would like to use webpacker with a minimal Rails app,
that's possible too. Selecting a specific database adapter is also still possible.

rails new cool_app --minimal --database postgresql webpack=react

Beat Java cold starts in AWS Lambda's with GraalVM

Joery Vreijsen — Mon, 19 Oct 2020 00:00:00 +0000

Let's face it, against all advice from your co-workers, friends, or even family, you still want to build a blazingly fast lambda with Java. Either to prove a point, to win a bet, or because you are just as much a Java geek as me.

With this blogpost I'm going to walk you through pre-compiling your Java lambda with GraalVM [1] to eliminate slow cold-start times.

Cold starts, what, where, and when?

On the first invocation of your lambda, AWS boots up a container with the right runtime before actually calling your code. When using runtimes like NodeJs or Python, the cold start times are between 200-250 ms [2] while with Java it takes atleast 650 ms if not more depending on the specifics of your function code.

Java's cold start is mainly caused by the JVM, which is started by default when using AWS' pre-configured Java runtime. Luckily AWS also provides us the option to create our own custom runtime which allows us to use GraalVM to pre-compile our Java code into a binary that can be ran without the need of a JVM.

Let's get practical

Let's take a simple Java program like our Lambda Authorizer from the previous blogpost [3], which can be found on Github [4], and start enabling it for GraalVM processing.

AWS Lambda Runtime API

As we are going to build our own custom runtime, we have to interact with the AWS Lambda Runtime API [5] ourselves.
On this API there are three endpoints that we want to use:

/runtime/invocation/next to get our next invocation,
/runtime/invocation/{AwsRequestId}/response to post the response to a specific invocation (request)
/runtime/invocation/{AwsRequestId}/error to post errors during the invocation (request).

A simple bootstrap class to handle this polling of the AWS Runtime API can be found on Github [6].

Reflection

One of the downsides of pre-compiling with GraalVM is that it can't handle reflection very well, which means that we have to create a reflect.json configuration file, where we can point GraalVM to the classes it should prepare for reflective use. Since we use Jackson as our serialization library we should configure all classes that need (de)serialization in the reflect.json file.

Example entry in the reflect.json configuration file:

[
  ...
  {
    "name": "nl.theguild.lambda.model.DefaultResponse",
    "allPublicMethods" : true
  },
  ...
]

For the complete reflect.json check Github [7]

Compiling the image!

Yes! The interesting part! Now that we prepared our little Java project for native-image compilation let's see how it is done.

First we need to make sure our jar comes with a proper manifest stating our mainClass, which can be done by adding the following config to our pom.xml.

<plugin>
    <artifactId>maven-jar-plugin</artifactId>
    <version>3.0.2</version>
    <configuration>
        <archive>
            <manifest>
                <mainClass>nl.theguild.lambda.Main</mainClass>
            </manifest>
        </archive>
    </configuration>
</plugin>

We then can start creating a simple bash script that will preform all the necessary steps to end up with our custom-runtime zip.

Step 1: Create our jar file.

mvn clean install;

Step 2: Run GraalVM inside a docker container, and mount our project.

docker run --rm --name graal -v $(pwd):/${PATH_TO_PROJECT} oracle/graalvm-ce:19.2.0

Step 3: Install and run GraalVM's native-image command while including our reflect.json configuration, and enabling http.

gu install native-image;
native-image \
    -H:EnableURLProtocols=http \
    -H:ReflectionConfigurationFiles=${PATH_TO_PROJECT}/reflect.json \
    -jar ${PATH_TO_JAR};

Step 4: Move our native image to a folder which we can later on zip for usage in the AWS Lambda.

mkdir /${PATH_TO_PROJECT}/target/custom-runtime;
cp ${BINARY_RESULT} ${PATH_TO_PROJECT}/target/custom-runtime;

Step 5: Create a bootstrap file that instructs AWS on how to run the native image.

AWS defines in their documentation [8] that every custom-runtime should be a zip including a bootstrap shell file that can jump start the function.

In our case that bootstrap file can be a simple one looking something like this:

#!/bin/sh
set -euo pipefail
./${PROJECT_NAME}

Adding all those steps into one single bash script results in the following file:

PROJECT_NAME=aws-enriching-lambda-authorizer
PROJECT_VERSION=1.0.0

# Generate Jar file
mvn clean install;

# Generate Native Image
docker run --rm --name graal -v $(pwd):/${PROJECT_NAME} oracle/graalvm-ce:19.2.0 \
    /bin/bash -c "gu install native-image; \
                  native-image \
                        -H:ReflectionConfigurationFiles=/${PROJECT_NAME}/reflect.json \
                    -jar /${PROJECT_NAME}/target/${PROJECT_NAME}-${PROJECT_VERSION}.jar \
                    ; \
                    mkdir /${PROJECT_NAME}/target/custom-runtime \
                    ; \
                    cp ${PROJECT_NAME}-${PROJECT_VERSION} /${PROJECT_NAME}/target/custom-runtime/${PROJECT_NAME}";

echo -e "#!/bin/sh \n \
set -euo pipefail \n \
./${PROJECT_NAME}" > target/custom-runtime/bootstrap;

# Make bootstrap executable
chmod +x target/custom-runtime/bootstrap;

# Zip
rm $PROJECT_NAME-custom-runtime.zip
cd target/custom-runtime || exit
zip -X -r ../../$PROJECT_NAME-custom-runtime.zip .

HOORAY!

We now have our aws-enriching-lambda-authorizer-custom-runtime.zip that we can use in our AWS Lambda and enjoy our rapid fast cold start timings... WHILE USING JAVA!

Navigate to the AWS Console -> Lambda -> Create function, choose custom-runtime -> use default bootstrap and click create.

Now that we have a lambda, we can go to Actions and upload our zip file, after which we can configure a test-event.

As our authorizer lambda is triggered by the api-gateway we can use the default Amazon API Gateway AWS Proxy event, and simply add an "Authorization": "Bearer 12345" header to the request.

When we now hit test we see our lambda responding in just 283ms, matching the cold-start times of other runtimes, show that to your co-workers, friends, and family!

Source

Github: https://github.com/VR4J/aws-enriching-lambda-authorizer/tree/feature/graal-vm

References

[1] https://www.graalvm.org/docs/introduction/
[2] https://levelup.gitconnected.com

[3] https://www.kabisa.nl/tech/enriching-requests-with-an-aws-lambda-authorizer

[4] https://github.com/VR4J/aws-enriching-lambda-authorizer

[5] https://docs.aws.amazon.com/lambda/latest/dg/runtimes-api.html

[6] https://github.com/VR4J/aws-enriching-lambda-authorizer/blob/feature/graal-vm/src/main/java/nl/theguild/lambda/Main.java

[7] https://github.com/VR4J/aws-enriching-lambda-authorizer/blob/feature/graal-vm/reflect.json

[8] https://docs.aws.amazon.com/lambda/latest/dg/runtimes-custom.html

Browser beats I: synthesizing a kick drum

Luc Engelen — Mon, 25 May 2020 00:00:00 +0000

Because I wanted to gain some experience in working with Angular and NgRx, I started building a sample-based step sequencer that runs in the browser.
To do that, I had to dive into the Web Audio API.
I'll write something about that step sequencer later.
First, I want to take a look at the basics of the Web Audio API and try to synthesize a kick drum.

The basis

At the basis of most syntesized kick drums, there's a sine wave, or something that's close to a sine wave.
The function below produces a sine wave with a frequency of 55Hz that plays for the duration of ten seconds.

const play = () => {
    const audioContextClass = window.AudioContext || window.webkitAudioContext;
    const audioContext = new audioContextClass();

    const sine = audioContext.createOscillator();
    sine.type = 'sine';
    sine.frequency.value = 55;

    sine.start(audioContext.currentTime);
    sine.stop(audioContext.currentTime + 10);
}

It sounds like this:
(You might not hear it over your laptop's speakers. You'll need decent speakers or headphones that are able to reproduce low frequencies.)

When you visualize that sound, as shown below, you'll see why it's called a sine wave.
The left-hand side of the figure shows the waveform, and the right-hand side shows the sound spectrum.

The sound spectrum is almost completely empty, except for a narrow spike at the rightmost end.
This explains why you might not hear the sound over your laptop speakers, for example.
Not all speakers are capable of reproducing sounds at low frequencies.
You can emulate the frequency response of such speakers by applying a high-pass filter.
If you filter out all frequencies below 120Hz, this is what's left of our sine wave:

The graphs below further illustrate that not much is left of the original sound.

What does that mean for our synthesized kick drum?
We'll apply a trick to make your ears believe that there's still some bass to be heard, even when listening to speakers that can't reproduce low frequencies very well.
Instead of a sine wave, we'll start out with a triangle wave.

const play = () => {
    const audioContextClass = window.AudioContext || window.webkitAudioContext;
    const audioContext = new audioContextClass();

    const triangle = audioContext.createOscillator();
    triangle.type = 'triangle';
    triangle.frequency.value = 55;

    triangle.connect(audioContext.destination);

    triangle.start(audioContext.currentTime);
    triangle.stop(audioContext.currentTime + 10);
}

Without further processing, it will look like this:

It's again clear where the name comes from.
It's also clear that there's much more going on in the spectrum graph.

Unfortunately, it sounds a little abrasive, like this:

Ideally, we'd like to process this triangle wave in such a way that it sounds more like the sine wave, without cutting off too much of the high-frequency sounds.
We can do that using a wave shaper.

const distortionCurve = (amount) => {
    const numberOfSamples = 44100;
    const curve = new Float32Array(numberOfSamples);
    const deg = Math.PI / 180;
    for (let i = 0; i < numberOfSamples; ++i) {
        const x = i * 2 / numberOfSamples - 1;
        curve[i] = (3 + amount) * x * 20 * deg / ( Math.PI + amount * Math.abs(x) );
    }
    return curve;
};

const play = () => {
    const audioContextClass = window.AudioContext || window.webkitAudioContext;
    const audioContext = new audioContextClass();

    const triangle = audioContext.createOscillator();
    triangle.type = 'triangle';
    triangle.frequency.value = 55;

    const waveShaper = audioContext.createWaveShaper();
    waveShaper.curve = distortionCurve(5);

    triangle.connect(waveShaper);
    waveShaper.connect(audioContext.destination);

    triangle.start(audioContext.currentTime);
    triangle.stop(audioContext.currentTime + 10);
}

The curve I'm using above comes from a Stack Overflow answer by Kevin Ennis.
In theory, there are multiple Sigmoid functions that you could use.
I only tried this one and stuck with it because I liked the result.

Speaking of results, here are the graphs for this sound:

The triangles look a lot more like sines, and there is still something going on at the higher end of the frequency spectrum.
The resulting sound sounds like this:

The W3C spec gives a good explanation of what's actually going on when you apply a wave shaper with a certain curve.
I won't go into the details here.

What did we achieve with this detour?
If we filter out the low frequencies again to simulate cheaper speakers, we end up with the following sound:

The graphs for this filtered sound are shown below.
When you compare these to the ones for the filtered sine wave shown above, you'll notice that there's still something to hear after removing the low end.
This is enough for you ears to trick you into believing that there's actually some low end left, even when there isn't.

Make it boom

The sound we ended up with sounds a little like "WOOOOOOOOOOH".
Let's turn that into a "WOOOOM".

const play = () => {
    const audioContextClass = window.AudioContext || window.webkitAudioContext;
    const audioContext = new audioContextClass();

    const triangle = audioContext.createOscillator();
    triangle.type = 'triangle';
    triangle.frequency.value = 55;

    const waveShaper = audioContext.createWaveShaper();
    waveShaper.curve = distortionCurve(5);

    const triangleGainNode = audioContext.createGain();
    triangleGainNode.gain.value = 1;
    triangleGainNode.gain.linearRampToValueAtTime(0, audioContext.currentTime + 0.6)

    triangle.connect(waveShaper);
    waveShaper.connect(triangleGainNode);
    triangleGainNode.connect(audioContext.destination);

    triangle.start(audioContext.currentTime);
    triangle.stop(audioContext.currentTime + 1);
}

In the snippet above, you'll see that we're using a gain node to gradually fade out over the course of 600 milliseconds.
The end result sounds like this.

Now that we have something that sounds like "WOOOOM", let's make it sound like "BOOOOM".

const play = () => {
    const audioContextClass = window.AudioContext || window.webkitAudioContext;
    const audioContext = new audioContextClass();

    const triangle = audioContext.createOscillator();
    triangle.type = 'triangle';
    triangle.frequency.value = 220;
    triangle.frequency.exponentialRampToValueAtTime(55, audioContext.currentTime + 0.1);

    const waveShaper = audioContext.createWaveShaper();
    waveShaper.curve = distortionCurve(5);

    const triangleGainNode = audioContext.createGain();
    triangleGainNode.gain.value = 1;
    triangleGainNode.gain.linearRampToValueAtTime(0, audioContext.currentTime + 0.6)

    triangle.connect(waveShaper);
    waveShaper.connect(triangleGainNode);
    triangleGainNode.connect(audioContext.destination);

    triangle.start(audioContext.currentTime);
    triangle.stop(audioContext.currentTime + 1);
}

As shown above, we do that be quickly lowering the frequency of the triangle wave from 220Hz to 55Hz over the course of 100 milliseconds.
The end result sounds like this:

If you want to achieve more of a 90s Euro house vibe, you can drop down from a higher frequency.

White noise

If you look at how classic synthesizers emulate kick drums, you'll see that they'll often use a little white noise to give the kicks a little more body.
The Web Audio API doesn't provide (white) noise out of the box, but you can use an audio buffer to create your own.

const generateWhiteNoiseBuffer = (numberOfSamples) => {
    const buffer = audioContext.createBuffer(1, numberOfSamples, audioContext.sampleRate);

    const data = buffer.getChannelData(0);
    for (let i = 0; i < numberOfSamples; ++i) {
        data[i] = Math.random() * 2 - 1;
    }

    return buffer;
}

const whiteNoiseBuffer = generateWhiteNoiseBuffer(audioContext.sampleRate);

const whiteNoiseBufferSource = () => {
    const bufferSource = audioContext.createBufferSource();
    bufferSource.buffer = whiteNoiseBuffer;
    bufferSource.loop = true;
    bufferSource.loopEnd = audioContext.sampleRate
    return bufferSource;
}

Each buffer source returned by the function whiteNoiseBufferSource can only be started once.
The same holds for the oscillator nodes that we've been creating above.
The buffer returned by generateWhiteNoiseBuffer, however, can be reused.
The result sounds like this:

The next step is to apply a fade to this sound, just like we did before.

After that, we cut of most of the higher frequencies using a low pass filter.

const play = () => {

    ...

    const noise = whiteNoiseBufferSource();

    const noiseGainNode = audioContext.createGain();
    noiseGainNode.gain.value = 1;
    noiseGainNode.gain.linearRampToValueAtTime(0, audioContext.currentTime + 0.2);

    const noiseFilter = audioContext.createBiquadFilter();
    noiseFilter.type = 'lowpass';
    noiseFilter.frequency.value = 120;

    noise.connect(noiseGainNode);
    noiseGainNode.connect(noiseFilter);
    noiseFilter.connect(audioContext.destination);

    noise.start(audioContext.currentTime);
    noise.stop(audioContext.currentTime + 1);
};

The end result sounds like this:

End result

Combining the sine-like wave and the filtered white noise leads to the following result:

All you need is a handful of other instruments and you're halfway making the next big dance hit, in your browser.

Conclusion

Let's put the results of all this hard work into action.
First, open Youtube, Spotify or whatever streaming service you like to play your favorite song.
Then, visit https://ljpengelen.github.io/groovid19/kick-snare-hihat.html and press q, w, and e to drum along.
Enjoy!

Browser beats II: synthesizing a snare drum and a hi-hat

Luc Engelen — Mon, 25 May 2020 00:00:00 +0000

In the previous installment of browser beats, we used the Web Audio API to synthesize a kick drum.
This time, we'll look at snares and hi-hats.
Once you know how to synthesize kicks, snares and hi-hats are not far away.

Snare

The snare sound we'll synthesize consists of two components.
One component represents the vibrating skins of the snare drum, the other represents the vibrating snares.
For the first component, we'll use two sine-like waves, one at 185Hz and the other at 349Hz.
I took these values from a MusicTech tutorial.
An article in Sound on Sound mentions 180Hz and 330Hz.
Obviously, you should go with whatever frequencies sound best to you.

const playSnare = () => {
    const lowTriangle = audioContext.createOscillator();
    lowTriangle.type = 'triangle';
    lowTriangle.frequency.value = 185;

    const highTriangle = audioContext.createOscillator();
    highTriangle.type = 'triangle';
    highTriangle.frequency.value = 349;

    const lowWaveShaper = audioContext.createWaveShaper();
    lowWaveShaper.curve = distortionCurve(5);

    const highWaveShaper = audioContext.createWaveShaper();
    highWaveShaper.curve = distortionCurve(5);

    const lowTriangleGainNode = audioContext.createGain();
    lowTriangleGainNode.gain.value = 1;
    lowTriangleGainNode.gain.linearRampToValueAtTime(0, audioContext.currentTime + 0.1)

    const highTriangleGainNode = audioContext.createGain();
    highTriangleGainNode.gain.value = 1;
    highTriangleGainNode.gain.linearRampToValueAtTime(0, audioContext.currentTime + 0.1)

    const snareGainNode = audioContext.createGain();
    snareGainNode.gain.value = 1;

    lowTriangle.connect(lowWaveShaper);
    lowWaveShaper.connect(lowTriangleGainNode);
    lowTriangleGainNode.connect(snareGainNode);
    snareGainNode.connect(audioContext.destination);

    highTriangle.connect(highWaveShaper);
    highWaveShaper.connect(highTriangleGainNode);
    highTriangleGainNode.connect(snareGainNode);

    lowTriangle.start(audioContext.currentTime);
    lowTriangle.stop(audioContext.currentTime + 1);

    highTriangle.start(audioContext.currentTime);
    highTriangle.stop(audioContext.currentTime + 1);
};

Together, these two sound like this:

We could have used pure sines waves here.
There's no need for applying the trick we used for the kick drum.
What you're witnessing here is a sheer waste of processing power due to my unwillingness to refactor this code right now.
Let's just say that I like the slightly more metallic sound of the distorted traingle waves.

We'll use white noise again to represent the second component.
This time, we'll use a filter to cut of all frequencies below 2kHz.

const playSnare = () => {

    ...

    const noise = whiteNoiseBufferSource();

    const noiseGainNode = audioContext.createGain();
    noiseGainNode.gain.value = 1;
    noiseGainNode.gain.linearRampToValueAtTime(0, audioContext.currentTime + 0.2);

    const noiseFilter = audioContext.createBiquadFilter();
    noiseFilter.type = 'highpass';
    noiseFilter.frequency.value = 2000;

    noise.connect(noiseGainNode);
    noiseGainNode.connect(noiseFilter);
    noiseFilter.connect(snareGainNode);

    noise.start(audioContext.currentTime);
    noise.stop(audioContext.currentTime + 1);
};

The filtered noise sounds like this:

Finally, the distorted sines and the noise together sound like this:

Hi-hat

Some filtered white noise is all you need for a hi-hat.
We again cut all frequencies below 2kHz.
This time, the volume should fade to zero in 100 milliseconds.

const playHiHat = () => {
    const noise = whiteNoiseBufferSource();

    const noiseGainNode = audioContext.createGain();
    noiseGainNode.gain.value = 1;
    noiseGainNode.gain.setValueAtTime(1, audioContext.currentTime + 0.001);
    noiseGainNode.gain.linearRampToValueAtTime(0, audioContext.currentTime + 0.1);

    const noiseFilter = audioContext.createBiquadFilter();
    noiseFilter.type = 'highpass';
    noiseFilter.frequency.value = 2000;

    const hiHatGainNode = audioContext.createGain();
    hiHatGainNode.gain.value = 0.3;

    noise.connect(noiseGainNode);
    noiseGainNode.connect(noiseFilter);
    noiseFilter.connect(hiHatGainNode);
    hiHatGainNode.connect(audioContext.destination);

    hiHatGainNode.connect(analyser)

    noise.start(audioContext.currentTime);
    noise.stop(audioContext.currentTime + 1);
};

The end result sounds like this:

Conclusion

The snare and hi-hat we've produced here are pretty basic.
If you want to dig deeper to achieve prettier or more realistic results, the following articles would be good starting points:

Don't forget to put these sounds to the test by playing along with your favorite songs: https://ljpengelen.github.io/groovid19/kick-snare-hihat.html.

You're not stubbing, stupid!

Patrick Baselier — Fri, 17 Apr 2020 00:00:00 +0000

Recently, in a Ruby on Rails project, I was writing a Cucumber scenario that was deleting a resource by having the user clicking a 'Destroy' button. Before the action was executed, the user had to confirm a message shown in a confirmation dialog. You may have seen this dozens of times when scaffolding a Rails application.

Oh and upon deleting, I also had to do a request to an external API (to be more precise: the use case was that of a user unsubscribing, so I had to send a DELETE request to a Mollie API).

So, "nothing new here", I thought. I knew about WebMock, since I wanted to stub the external API request and my test suite was set up to test JavaScript, so I knew I could use the accept_confirm method here that Capybara offers.

Stubbing the request was defined in a support file:

# features/support/webmock.rb

require 'webmock/cucumber'

WebMock.disable_net_connect!(allow_localhost: true)

Before do |_scenario|
  stub_request(
    :delete, 
    %r{https://api.mollie.com/v2/customers/\w+/subscriptions/\w+}
  )
    .to_return(body: {}.to_json)
end

My step implementation looked like this:

# features/step_definitions/general_steps.rb

When('I delete the resource') do
  accept_confirm { click_on 'Destroy' }
end

The test failed! It was telling me that I should stub the DELETE request.

  Real HTTP connections are disabled. Unregistered request: DELETE https://api.mollie.com/v2/customers/...

  You can stub this request with the following snippet:

  stub_request(:delete, "https://api.mollie.com/v2/customers/...").
    ...
    to_return(status: 200, body: "", headers: {})

Wasn't I doing this?

After many (!!!) hours of trying rewriting the stub, rubber ducking with colleagues, writing alternative scenarios, I decided to get rid of the confirmation dialog that was shown to the user. This way I didn't need the accept_confirm and... tadaaa: it worked! My test was passing.

My theory was that accept_confirm executes in a different thread or something in which the stub is not defined (I know a theory can be proven wrong, but this one worked for me).

One way to work around this is, instead of using accept_confirm, is 'overriding' the JavaScript's confirm function:

# features/support/my_world.rb
module MyWorld
  def click_on_and_confirm(locator)
    link_or_button = find(:link_or_button, locator)
    page.evaluate_script('window.confirm = () => true')
    expect(link_or_button['data-confirm']).to be_a(String)
    link_or_button.click
  end
end

World(MyWorld)

# features/step_definitions/general_steps.rb

When('I delete the resource') do
  click_on_and_confirm 'Destroy'
end

This way the DELETE request is being stubbed, you can still show a nice confirmation dialog and your test will pass.

Be aware that during the test, the confirmation dialog will not be shown anymore (due to the 'stubbed' confirm function in JavaScript. Therefor, I added an assertion to check indirectly if the confirmation dialog will be shown (by using the data-confirm attribute added and used by Rails) when clicking the 'Destroy' link or button.

Kubernetes workshop in a box

Pascal Widdershoven — Thu, 09 Apr 2020 08:26:05 +0000

We recently organised an internal Kubernetes workshop at our office. Each participant got their own 3-node Kubernetes cluster and all they needed was a laptop with an SSH client, no other software had to be installed! How? Read on to find out!

Why

I wanted participants to have a real cluster to experiment with, but didn't want to ask everyone to install Minikube. It's heavy weight, can be a bit of a hassle to setup and I just didn't want people to have to mess with stuff like this. Workshops should have a low as possible barrier to entry.

To pull this off I used Kind (Kubernetes In Docker) + a bit of scripting and Unix magic! 💪

The setup

The setup works as follows:

A single, beefy cloud server is used to host all Kubernetes clusters.
Kind creates true Kubernetes clusters inside Docker containers. This way, each cluster is fully isolated from the other clusters and clusters can run side-by-side on a single host machine. Every cluster consists of one master and two worker nodes.
The clusters are (automatically) provisioned in advance to the workshop, as creating the clusters is quite resource intensive and takes a couple of minutes per cluster.
During the workshop participants can claim their own cluster via SSH and then access their private cluster via a new SSH session.

You can see the process from a participant perspective in action below:

Hardware & costs

A Kind cluster is quite resource intensive, though in part it depends on the workloads your workshop participants are running of course. For our workshop with 15 participants we used an AWS m5.8xlarge machine. This machine type has 32 VCPU's and 128GB of RAM. It costs $1,712 per hour (in eu-west-1) and we needed it only for about 3 hours so that's about $5 total 🙂.

In hindsight, this machine was way over provisioned for this number of clusters, so you could go even cheaper 😀

You can use this too to run your own Kubernetes workshops!

We've open-sourced the tooling we built to do this here: https://github.com/kabisa/k8s-workshop-in-a-box. Feel free to use it and if you do please reach out to me I'd love to hear from you! ❤️