Introduction

Krikata is an experimental framework to quickly build a parser and interpreter for Domain Specific Languages. It evaluates left to right, is right associative, and strongly typed, with an expression's type being fully dependent on the context in which it is evaluated. Krikata is primarily intended for running commands, and its execution is inherently asynchronous.

This book is split into two parts: A tutorial where two example languages are gradually built up and made more complex to introduce different parts of Krikata, and a Reference that can be read in any order.

Example: Hello World

We step through the process of defining, parsing and executing a language using a trivial Hello World program. The program consists of two functions: hello and hi, of which the former takes a string as argument. When executed, the program greets the provided argument. For example:

> hello world
"Hello world! It is a great day today!"
> hello moon
"Hello moon! It is a great day today!"
> hi
"Hi mysterious person!"

Defining the language

A Krikata language consists of a top level expression, which in turn consists of nested other expressions. Expressions have a certain Typescript type, which is what will be returned upon execution.

const greeting = new Type<string>("greeting");

greeting.setFunctions([
  Constant("hi", () => `Hi mysterious person!`),
  Func("hello")
    .arg(primitives.string)
    .setExec((value: string) => `Hello ${value}! It is a great day today!`),
]);

Let's deconstruct this:

1. We construct a new Krikata Type named greeting.
2. The Typescript type parameter of greeting is string. This means when running the program, this expression will evaluate to a string.
3. We give greeting an array of functions:
   1. The first function, hi, takes no arguments. When it is executed, it will return a constant string.
   2. The second function, hello, takes one argument, a string. This is accomplished using the primitives.string expression, which evaluates to a TypeScript string. This value will be passed to the function's executor, and it is used to customise the string that is returned.

Inspecting the language

In the previous step we defined our greeting expression, a type consisting of two functions. We can now create a new language from this expression, appropriately called greet.

const greet = new Language("greet", greeting);

Krikata can automatically generate a grammar for greet in an approximate BNF notation.

const grammar = greet.grammar();
console.log(grammar.format());

l.greet:
 | <t.greeting> EOI

t.greeting:
 | "hi"   
 | "hello" <p.string>

We see our two expressions. First the language greet, which expects a greeting type followed by the special End-Of-Input, and second the greeting type itself, which matches either the string hi or the string hello followed by a primitive string.

Parsing and executing

With our language greet defined and inspected, we can now parse and execute a program. Parsing requires a Parser, which can easily be constructed from a process's command line arguments. Note that execution returns a Promise and has to be awaited.

try {
  const parseResult = greet.parse(Parser.fromArgv());

  console.log(await parseResult.execute());
} catch (error) {
  if (error instanceof Error) console.log(`${error.name}: ${error.message}`);
}

We can now run the program from a terminal (after compiling it with typescript).

$ node cli.js hi
Hi mysterious person!
$ node cli.js hello world
Hello world! It is a great day today!

$ node cli.js
Error: Parser finished but expected type <t.greeting>.
$ node cli.js hello
Error: Parser finished but expected type <p.string>.
$ node cli.js hi world
Error: Unexpected token "world" at index 1.

Example: Calculator

In this chapter we will incrementally build up a basic calculator. As a starting point we trivially adapt the language greet from the previous chapter, into the language calc.

const value = new Type<number>("value");

value.setFunctions([
  Func("add")
    .arg(primitives.number)
    .arg(primitives.number)
    .setExec((left, right) => left + right),
  Func("mul")
    .arg(primitives.number)
    .arg(primitives.number)
    .setExec((left, right) => left * right),
  Constant("pi", () => 3.14),
]);

const calc = new Language("calc", value);

This language has the following grammar:

l.calc:
 | <t.value> EOI

t.value:
 | "add" <p.number> <p.number>
 | "mul" <p.number> <p.number>
 | "pi" 

Running the language like before gives:

> add 1 5
6
> mul 9 5
45
> pi
3.14

Recursion

Our current language can either add or multiply two numbers. However, the result of an addition can not be used in a multiplication and vice-versa, since the arguments of both functions are primitive numbers. We also can't add or multiply using Pi.

> add pi 1
Error: Unexpected token "pi" at index 1 for type <p.number>

We can change this by changing the arguments of add and mul to value, making them recursive.

  Func("add")
    .arg(value)
    .arg(value)
    .setExec((left, right) => left + right),

However, we now have a new problem, as we can only use recursion.

> add 1 2
Error: Unexpected token "1" at index 1 for type <t.value>
> add pi pi
6.28

We could solve this problem using a separate function, for example im for immediate, but this is annoying to use.

  Func("im")
    .arg(primitives.number)
    .setExec((val) => val),

> add im 5 im 10
15

Instead, value has an optional default expression, which will be parsed if none of its functions matched the input.

value.setDefault(primitives.number);

This gives the desired functionality:

> add 5 mul 6 7
47
> 5
5

Notice that a single number is now also a valid program. We can see this in the updated grammar.

l.calc:
 | <t.value> EOI

t.value:
 | "add"      <t.value> <t.value>
 | "mul"      <t.value> <t.value>
 | "pi"      
 | <p.number>

Repetition

Since we can use the result of an addition in another addition, we can theoretically add any amount of numbers together. This is not a very nice way of dealing with the problem.

> add 1 add 2 add 3 add 4 5
15

Instead we can use Repeat which evaluates to an array of of its inner type.

  Func("sum")
    .arg(new Repeat(value))
    .setExec((args: number[]) => args.reduce((sum, next) => sum + next, 0)),

> sum 1 2 3 4 5
15
> sum
0
> sum 1 2 3 mul 4 5
26
> mul 2 sum 3 4 5
24
> mul sum 3 4 5 2
Error: Parser finished but expected type <t.value>.

Notice how the last example didn't work. This is because Repeat parses until the end of input is reached, meaning the 2 is consumed by sum and not given as an argument to mul. This can also be seen in the grammar. We fix this in the next chapter.

l.calc:
 | <t.value> EOI

t.value:
 | "add"      <t.value>   <t.value>
 | "mul"      <t.value>   <t.value>
 | "sum"      <r.t.value>
 | "pi"      
 | <p.number>

r.t.value:
 | <t.value> * EOI

Advanced Repetition

If we want nested repetition that doesn't consume the whole input, we need a way to end the scope of a Repeat. This is accomplished using a special value given to the constructor. We also wrap the repeat into a separate type so we can easily add other array-manipulating functions.

const repeatNumber = new Repeat(value, "-");

const arr = new Type<number[]>("arr");
arr.setDefault(repeatNumber);

We use a - here as common scope characters like ),] and ; are used by shells like bash and would need to be escaped in a cli.

> mul sum 1 1 1 2
Error: Parser finished but expected type <t.value>.
> mul sum 1 1 1 - 2
6

For fun we add some more array functions.

arr.setFunctions([
  Func("repeat")
    .arg(value)
    .arg(value)
    .setExec((amnt, val): number[] => Array<number>(amnt).fill(val)),
  Func("range")
    .arg(value)
    .setExec((max): number[] =>
      Array.from({ length: max }, (_, index) => index),
    ),
  Func("double")
    .arg(arr)
    .setExec((vals) => vals.map((val) => val * 2)),
]);

> mul 2 sum range 5
20
> sum double range 5
20

l.calc:
 | <t.value> EOI

t.value:
 | "add"      <t.value> <t.value>
 | "mul"      <t.value> <t.value>
 | "sum"      <t.arr>  
 | "pi"      
 | <p.number>

t.arr:
 | "repeat"    <t.value> <t.value>
 | "range"     <t.value>
 | "double"    <t.arr>  
 | <r.t.value>

r.t.value:
 | <t.value> * EOI
 | <t.value> * "-"

Reference

This section provides a reference to different Krikata concepts.

Primitives

Krikata currently comes with 4 built-in primitives: number, int, string and bool.

The first two are parsed using parseFloat and then checked by Number.isFinite and Number.isInteger respectively.

A string matches one token generated by the Parser. If Parser.fromArgv() is used, this means a string is one argument as parsed by the shell.

A bool matches exactly true or false. It is trivial to create a bool with different names, for example T and F like so:

const mybool = new Type<boolean>("mybool", [
  Constant("T", () => true),
  Constant("F", () => false),
]);

Example:

> number 5.37
5.37
> number 6.06e5
606000
> int 6
6
> string hello
hello
> bool true
true
> mybool F
false

Example grammar:

l.calc:
 | <t.value> EOI

t.value:
 | "number" <p.number>
 | "int"    <p.int>   
 | "string" <p.string>
 | "bool"   <p.bool>  
 | "mybool" <t.mybool>

t.mybool:
 | "T"
 | "F"

Async Execution

As Krikata is mainly intended for running commands, both the Language and all intermediate executions are inherently asynchronous, with all Promises being awaited before being passed to other functions.

If the program contains a repetition, there are two main ways of awaiting it. Either we regard it as a sequential process with every sub-expression being executed and awaited in order, or as a parallel process where all promises are started at the same time. The default behaviour using Repeat is sequential, parallel execution is possible using Parallel, which otherwise functions identically.

The difference can be seen in the following example.

const sleep = Type.fromFunc(Constant("sleep", () => setTimeout(10)));

const run = new Type<void>("run", [
  Func("repeat")
    .arg(new Repeat(sleep))
    .setExec(() => undefined),
  Func("parallel")
    .arg(new Parallel(sleep))
    .setExec(() => undefined),
]);

const lang = new Language("sleep", run);

> repeat sleep sleep sleep sleep sleep
took: 51.198ms
> parallel sleep sleep sleep sleep sleep
took: 9.398ms