Forem: Lorem Scriptum

Comparison of Type Systems in Front-end Languages: Algebraic data types

Mikhail Medvedev — Wed, 07 Sep 2022 13:39:25 +0000

We've already come across such types as string or number. They are called primitive. These types describe the simplest units of data available in our language. But how do we describe the things listed below? Beforehand you might want to read first part of the series.

Value which can be of different types
Some sequence of values (lists or tuples, for example)
Structures like javascript objects or maps (key-value pairs)

This is where algebraic data types (ADTs) come in. These types are created by a combination of primitive or other algebraic types. In terms of the type system, all types that aren't primitive appear as algebraic. Two common classes of algebraic types are product types (a product, also known as a tuple, or a record, which is just a special case of a record) and sum types (disjointed or disjunctive unions, variant-type.) So, the type algebra is about creating some composite types based on a more primitive one with the help of allowed operators.

We are going to use some speculative metaphor and say that sum and product types (especially in presence of subtyping relations) are a very close equivalent to the sum and product from set theory. Here is some explanation for those who are not familiar with set theory. If we have some finite set of values, for example a = [1, 2, 3] and b = [4, 5, 6], then Sum(a, b) will be c = Sum(a, b) = [1, 2, 3, 4, 5, 6] (which is also called a union), where the value of type c can be any of the given ones. The product is a Casterian product, which means that for our a and b, c = Product(a, b) = [[1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6]], so the values of the type c can be any of the given pairs. Looking ahead, | operators in TypeScript let us make unions, and both ReasonML and PureScript only allow us to make disjoint (or tagged) unions which differ from simple unions in a way that they save information about which set the given element appeared in the sum from.

All the languages mentioned in our article have good support for ADTs.

Union (Sum) Types

What are the practical cases for these typing capabilities? Let's assume you have some collection like

const collection = ["a", 10, { flag: true }];

in JavaScript code, which is not statically typed. If you would like to iterate through such an array, you should probably put some checks manually before starting to work with the value. Also, you won’t be prompted if, for example, you forget to check for one of the variants of the value in the collection.

For example, disjointed unions are useful when used alongside pattern matching. In languages with a more powerful support for pattern matching, you can put type constructors as patterns. Pattern matching gives us the following benefits:

Completeness check. The compiler can give you a warning/error if you have not handled all the pattern variants for which the expression might fit. In the case of disjointed unions, you should explicitly handle all the types included in the union or add a default case.
Extraction of a concrete value type from the union. In our example, after matching, we can work with an explored value like it has an exact type.

We can make a union type in TypeScript for the previous example:

type CollectionItem = string | number | { flag: boolean };

const collection: CollectionItem[] = ['a', 10, {flag: true}]

And with that typing, when we access a collection of items with iteration or by index (which is a trickier thing to do), to work with that value as an item of the exact type, we should remove ambiguity by checking, for example, that typeof collection[index] === 'string'. Only after such a check, the type system would allow you to pass that value where string type is expected. Such checks are still runtime, but the type checker forces you to put such checks in your code.

Also, if the structure of a collection is always the same as in the example, it could be typed as a tuple

type Collection = [string, number, { flag: boolean }];

const collection: Collection = ['a', 10, { flag: true }];

In that case, we can create arrays of type Collection only with the exact order of values (the string value goes first, then a number, and the last one is { flag: boolean }) that need to be exactly the same size. When accessed by index, it will check that the accessed index is not out of bounds, and the type of access value will be inferred without ambiguity. On the other side, if you try to iterate over an array of this type, you'll get the same result as in the previous example — the type of variable will be string | number | { flag: boolean }; and you will have the same capabilities as in the case of manually defined union. What is more, TypeScript enables you to use switch/case as a very poor variant of pattern matching. With its help, we can also remove ambiguity (sadly, for a union of some different record types, you have to add some field that will work as a tag to imitate pattern matching on them)

Variant types are analogs of unions in ReasonML and PureScript. They are close to TypeScript (but closer to the PureScript ones) but different in the following way: you should always define tags (constructors) for each item included into a variant, you can't reuse the already created variant, they involve nominative typing (where TypeScript unions are pure structural). Untagged unions are not allowed, and if you can read them as some value of type C can have features of type B or type A with type C = A | B syntax in TypeScript, in ReasonML and PureScript they read as some value that can be created by one of the constructors from target type. This is because structural typing is not present in the variants.

So the definition of our previous CollectionItem type will look like this:

type flagged = {
  flag: bool
};

type collectionItem = Numeric(int) | String(string) | Rec({flag: true})

type collection = array(collectionItem)

let coll: collection = [|Numeric(10), String("Hello"), Rec({flag: true})|]

Then we can process its items like this:

let o = coll[0]

let a = switch(o) {
  | String(s) => true
  | Numeric(x) => false
  | Rec(r) => r.flag
}

This is what pattern matching looks like in ReasonML. We match values with tags defined at their type. We can also extract values under those tags. If we forget to handle one or more possible cases in a variant type, the compiler will notify us with a warning.

Defining tuples is the same as in TypeScript:

type collection = (int, string, flagged)

let coll: collection = (10, "hello", { flag: false })

The difference lies in the usage — in TypeScript, you continue to work with it as with a limited version of an array. It's different for ReasonML. For example, you can access its items only by destructuring or pattern matching. In both cases, the runtime representation will still be a JavaScript array.

Lastly, here is what our example may look like in PureScript:

data CollectionItem = Numeric Int | Stringy String | Flaggy { flag :: Boolean }

items :: Array CollectionItem
items = [Numeric 10, Stringy "Hello", Flaggy { flag: false }]

processItem :: CollectionItem -> String
processItem (Numeric a) = "Hello"
processItem (Stringy b) = "World"
processItem (Flaggy f) = "Boolean here"

Same thing here — you can only make tagged unions, but it allows inline records, as TypeScript does. The syntax for pattern matching differs as follows: it looks like three separate function realizations. A type checker will force you to cover all cases on the union, but instead of a warning, you'll catch an error if you haven’t covered all variants.

itemsT :: CollTuple
itemsT = Tuple 10 "Hello" { flag: false }

Tuples are defined like this, they are not much different from ReasonML. They do not provide you with array capabilities as TypeScript does. For more information on them, check the PureScript documentation.

Product Types

We've already used some product types in previous examples . We can create records with braces syntax (like { flag :: Boolean }). As we said before, they are just some cases of tuples, but their elements can be accessed via some tag or a key. Tuples are created with square brackets syntax in TypeScript, round brackets in ReasonML, and just by listing items separated by a space.

In general, product types open up an opportunity for us to create complex structures.

Note on Simulatiting Pattern Matching in TypeScript

We have shown some examples of pattern matching in PureScript and ReasonML. Here is an example of how we can simulate it in TypeScript using discriminated unions.

type A = {
    __TAG__: 'A';
    value: string;
}

type B = {
    __TAG__: 'B';
    value: number;
}

type C = A | B;

function foo(param: C) {
    switch(param.__TAG__) {
        case 'A': {
            param.value.toLocaleLowerCase();
        }
        case 'B': {
            param.value.toString();
        }
    }
}

Online compiler if you want to play around

TypeScript ADTs

Here is a set of examples of different ADTs in TypeScript. TypeScript allows you to create intersection types. In set theory, intersections operate like logic and — if you have two sets, the intersection between them will only contain elements that belong to both sets. In TypeScript, an intersection operator & makes a new type by merging all fields of the two types. ReasonML and PureScript don’t have this operation. Practically, intersections in TypeScript combine all properties from two types into a new type. It's like combining two interfaces via the extend keyword. The intersection is useless for primitive types (including literal types) as that will lead to unknown or to a type that is impossible to create. For example, type NumberString = number & string is unknown, same for type OneAndTwo = 1 & 2, as there is no value that is string and number (belongs to both sets at one time) or value that is both numbers one and two at the same time.

But if we create some union with common properties from literals, their intersection will not be empty: type Two = (1 | 2) & (2 | 3) will be literal type 2.

type A = {
    field1: string;
}

type B = {
    field2: string;
}

type intersection = A & B;

type union = A | B;

type tuple = [A, B];

const intersectionValue: intersection = {
    field1: 'Hello',
    field2: 'World',
}

const unionValue1: union = intersectionValue;

unionValue1.field1; // not allowed because at this place you don't know what part of union your value belongs to

const unionValue2: union = {
    field1: "Hello",
}

const unionValue3: union = {
    field2: "World",
}

const unionValue4: union = {}

const tupleValue: tuple = [{ field1: "Hello" }, { field2: "World" }];
const tupleValue2: tuple = [{ field1: "Hello" }, { field2: "World" }, { field2: "World" }];

Here you can check how the compiler will or won't allow you something based on the composite types you create.

Also, TypeScript's special types never and unknown have some interesting capabilities related to union and intersection. Again, if we refer to set theory, unknown will behave like a set that contains all other values and will be the supertype for all other types. And never is a set which contains no values, or an empty set. So in case of respective operations, they work as identity elements (an identity element is an element that leaves the second element unchanged when being used in some binary operation):

type A<T> = T | never // == T
type B<U> = U & unknown // == U

If you check the online compiler, you'll see that A = T and B = U — the operation is simplified to T and U with identity elements removed from it, as in these cases, they don't bring any useful type information. And if we change the operators, we get the opposite:

type A<T> = T & never
type B<U> = U | unknown

A<T> = never and B<U> = unknown - no information on T and U saved.

Interaction of Subtyping and Type Algebra

Such behavior can be easily described using set theory. Let's start with never. A union of two sets is a set where each element belongs to one of the parent sets or to both at once. So unknown is the set of all possible values, a union with it will always be the same set, as any value belongs at least to unknown, practically losing all useful information about the more restrictive one. This happens because, as you might have noticed, in values typed as a union of some types, you can access the only intersection of its properties (fields), and property containing all the possible values does not intersect with any other one. There is a good example of that behavior in the TypeScript documentation:

It might be confusing that a union of types appears to have the intersection of those types’ properties. This is not an accident — the name union comes from type theory. The union number | string is composed by taking the union of the values from each type. Notice that given two sets with corresponding facts about each set, only the intersection of those facts applies to the union of the sets themselves. For example, if we had a room of tall people wearing hats, and another room of Spanish speakers wearing hats, after combining those rooms, the only thing we know about every person is that they must be wearing a hat.

An opposite effect is observed for intersection with unknown — as it is the set of all values that belong to both parent sets, an intersection of any type with unknown is like an intersection of some set with the set of all values, thus only values from the more restrictive one go into the resulting set.

Now let's get to never and the empty set. A union of some non-empty set A with an empty set will always result in a set that is equivalent to A, as there is nothing to take from the empty one. An intersection will always result in the empty set itself, as there is no value that can satisfy the rule to be in both sets at once (if it could, the empty set would not really be empty.) So never behaves exactly the same way as the empty set when combined with other types.

There is also a more general rule (it also works for the TypeScript types): an intersection of a subset and a superset always consumes a supertype, and a union of such types always consumes a subtype. And here is the last thing: an intersection of two sets creates a subset of both (it is valid for the TypeScript types) and a union of two sets creates a superset of both sets (it is also valid for types.)

type A = { field1: string }

type B = { field2: string }

type AB = A & B

function expectA(val: A) {
    return val
}

function expectB(val: B) {
    return val
}

const aB: AB = {
    field1: "Hello",
    field2: "World",
}

expectA(aB)
expectB(aB)

With some type A and its supertype B, we are allowed to pass A, where B is expected. So the example above underlies this rule and shows us that an intersection is a subtype of other types.

If we change type AB = A & B to type AB = A | B, checks won't pass anymore as a type AB will become a supertype of A and B. Here is a Playground if you want to check yourself.

These rules show us the relation between the TypeScript type system and set theory. They also show us that type algebra operation relates to subtyping as well (we'll have a more precise look at it in the next chapter) and ADT's are in a sub/supertype relation with their parent types.

As we said before, neither PureScript nor ReasonML allows such intersection syntax.

ReasonML Variants (Sum Types)

ReasonML also has a unique feature among the languages we have mentioned. This feature is polymorphic variants. These variants differ from the normal ones a lot:

The constructors are global and exist on their own (one can use them even without a definition.)
There is an ability to extend such variants.
There are type constraints instead of a concrete type.

Let's take an example:

type alignment = [`Good | `Neutral | `Evil];

type reversedAlignment = [`Evil | `Good | `Neutral]

let id = (value: alignment) => value;

let x: reversedAlignment = `Evil

id(x)

let x2 = `Good

id(x2)

type withAdditional = [alignment | `Additional]

let x3: withAdditional = `Evil

let idLower = (value: [> alignment]) => value;

idLower(x3)

Types alignment and reversedAlignment show how you can define a polymorphic variant. For example, we are passing the value of type reversedAlignment into id functions that wait for the value of the alignment type, but we won't get an error (you can check the online compiler), which won't be true for normal variants — with them, we would only be able to pass an exact value type. That's because the polymorphic variants only let you pass the value of any type that has the same constructors (not more, not less, exactly the same). The next part of the example with x2 works because ReasonML didn't infer an exact type for it. Instead, it infers a type constraint [> Good ] which is a so-called lower bound that means all the types that have at least the constructor Good. Passing x3 to id will result in an error because, as we have said before, we need the same constructors. But if we change the signature for the value to be a constraint, that will mean that we need a type with at least all the needed constructors.

Here is another thing about polymorphic variants constraints: there is a hidden type parameter. If you try to

type good = [> `Good]

You'll get an error:

A type variable is unbound in this type declaration.
In type [> `Good ] as 'a the variable 'a is unbound

It can be fixed by an explicit definition of a type parameter with a constraint:

type good('a) = [> `Good] as 'a

and a computed type would be

type good('a) = 'a constraint 'a = [> `Good ];

Such definition with the polymorphic parameter will cause some discomfort when using — you'll need to provide some type in place of a when using it in definitions (this is a basic parametric polymorphism rule for ReasonML, we'll talk about it in the next chapter)

type alignment = [`Good | `Neutral | `Evil];

type onlyEvil = [`Evil];

type good('a) = [> `Good] as 'a

let x = `Good

let process = (value: good(alignment)) => value

process(x)

Here you can check some more patterns that we can match in ReasonML.

Some More Examples in ReasonML

type person = {
  name: string,
  age: int,
};

type pet = {
  name: string,
  age: int,
  owner: person,
};

type t =
  | B(person)
  | D(pet);

let joe = Some(B({name: "Joe", age: 20}));
let jimmy = Some(B({name: "Jimmy", age: 20}));

let getName = (x: option(t)) => {
  switch (x) {
      | Some(B({name: "Joe", age})) => "Joe"
      | Some(D({owner})) => owner.name
      | _ => "42"
  }
};

Js.log(getName(joe));
Js.log(getName(jimmy));

PureScript

Here are some examples of PureScript ADTs:

module Main where

import Prelude

import Effect.Console (logShow)
import TryPureScript (render, withConsole)

data Animal = Monkey Legs | Dog Legs | Spider Legs -- ADT

data Legs = Legs Int

myPet :: Animal
myPet = Monkey (Legs 2)

myPet2 = Monkey (Legs 4)

myPet3 = Dog

myPet4 = Legs 8

myPet5 = myPet3 (Legs 2)

-- showsAnimal :: Animal -> String -- Compile error: not all cases covered
-- showsAnimal (Monkey a) = "Animal is Monkey, it has " <> show a

showsLegs :: Legs -> String
showsLegs (Legs a) = show a <> " legs"

main = render =<< withConsole do
  logShow $ showsLegs(myPet4)

Also, we can define any kind of tuples, for our previous example we could do

data Tuple a b = Tuple a b
pets = Tuple myPet myPet2

and a type class to be able to logShow them

instance showTuple :: (Show a, Show b) => Show (Tuple a b) where
  show (Tuple a b) = "(Tuple " <> show a <> " " <> show b <> ")"

and that would work. But if you'd like to do pets = Tuple myPet myPet2 myPet2, the compiler will notify you of an error instead of inferring 3 items tuple type.

In this example of PureScript code, you can check different things (types inferred for variables, uncomment showsAnimal) and see the type checker reporting an error because you haven’t covered all cases of the pattern).

If you fix showsAnimal to make it cover the whole pattern

showsAnimal :: Animal -> String -- Compile error: not all cases covered
showsAnimal (Monkey a) = "Animal is Monkey, it has " <> show a
showsAnimal (Dog a) = "Animal is Dog, it has " <> show a
showsAnimal (Spider a) = "Animal is Spider, it has " <> show a

You may see that there is another error — No type class instance was found for Data.Show.Show Legs. Type classes are another feature of PureScript which we will cover in the next chapter of this article.

If you want to check what it looks like, you can add the following lines to the previous code:

instance showLegs :: Show Legs where
  show = showsLegs

instance showAnimal :: Show Animal where
  show (Monkey a) = "Animal is Monkey, it has " <> show a
  show (Dog a) = "Animal is Dog, it has " <> show a
  show (Spider a) = "Animal is Spider, it has " <> show a

also, you can remove the showsAnimal definition and replace main with

main = render =<< withConsole do
  logShow $ myPet5

where myPet5 can be replaced with an Animal instance of your choice.

As you can see, all the three languages have support for ADT's and some kind of pattern matching (with TypeScript having a very poor variant with switch). Some have more flexibility at the creation stage, others let you do some cool stuff at the pattern matching stage.

Another kind of ADT is the recursive type. Their use cases look obvious — values with recursive structure.

// TypeScript
const empty = Symbol('empty');

type Empty = typeof empty;

type Tree<T> = Empty | [Tree<T>, T, Tree<T>]
// ReasonML
type tree('a) = Branch(tree('a), 'a, tree('a)) | Empty

// PureScript
data Tree a = Empty | Branch (Tree a) a (Tree a)

Playgrounds: ReasonML, TypeScript

Some Conclusions

ADT is a powerful tool that allows you to create complex types by using the primitive ones or the types that were created with the help of algebra — so you can create something more complex by reusing the one you have already created with a simple set of operators. We can make it even more reusable by combining ADTs and polymorphism.

Comparison of Type Systems in Front-end Languages

Mikhail Medvedev — Wed, 17 Nov 2021 15:36:41 +0000

Introduction

With the stable growth of web projects, developers have found that they need some tools that will make maintaining and writing new code easier. There are various ways to help you to verify and validate code such as tests, contracts, typing, etc. We are going to focus on type systems in different static typing languages useful in web development centering on comparison by a couple of parameters.

We are not going to look for winners or losers because decisions taken on the type systems in languages we are going to discuss didn't come from scratch. If we were going to rate any of these languages objectively, we would need to take into account the whole ecosystem of language, history, advantages, and limitations that appeared in languages because of their design.

Parameters for Comparison

How easily/elegantly different concepts can be expressed with the type system of a chosen language. Elegance is a subjective case, so we handle it this way - if something needs more movement, it means that this case is less elegant in this language.
Support of different features of static typing. Pattern matching, type algebra, type inference, etc. are examples.
If there are any places in the language where the type system doesn't give us any guarantees of soundness/unsoundness. Soundness is an analyzer's ability to prove the absence of errors. If a program is accepted by an analyzer, then the program is guaranteed not to go out of the bounds we put on it with the help of types. For example, if we are going to read or write to some file, we can easily get an error in runtime and if the type system allows encoding of such cases and forces a programmer to put checks on them, we can be ready for such errors. So a sound type system gives us a guarantee that we cover all cases predicted by our types. It is important to note that type systems can not prove the correctness of programs generally. Some of them are powerful enough to use automatic theorems proving and in a certain range can prove correctness.

I'd encourage the reader to be distrustful but not paranoid when someone pledges that type system of language X is sound, but it depends on the kind of software you are working with. Even if it is implementing a type system in which soundness is proven, there is always some space for poor implementations, bugs in the type checker/compiler, etc.

Type System and Type Inference

Type inference is the ability of a language compiler to infer expression type with the help of some rules.

Let's look at it from a historical perspective. We can begin with lambda calculus¹, which is a formal system for expressing computations based on functions and it's equivalent to a Turing machine. It consists of a single transformation rule, which is variable substitution - β-conversion and a single function definition scheme. The central concept of lambda calculus are expressions that can be defined recursively as

< expression > := < name >|< function >|< application >
< function > := λ < name > . < expression >
< application > := < expression >< expression >

This means that there are only two operators (keywords) in it, which are - λ and the dot.

As a deep dive into lambda calculus is not part of this article, there is a multitude of information about it that can be found. The next step will be simply typed lambda calculus², which is the simplest typed interpretation of lambda calculus.

In simply typed lambda calculus, we explicitly state what type of argument there is. There is no space for polymorphism in simply typed lambda calculus, so more complex type systems that allow it appeared later.

Two commonly known systems formalize the notion of parametric polymorphism: System F and Hindley-Milner type system. The most valuable difference between them in the context of this article is type inference, which is generally undecidable in System F and decidable in the Hindley-Milner type system.

This difference comes from the next fact, which is that in System F, polymorphism is explicit, can occur anywhere³, and is impredicative, but in the HM type system, it is implicit, can occur only on the top level⁴, and is predicative. So you can consider the Hindley-Milner system as a kind of restriction for System F, which would allow you more flexibility with types, but it also requires more type annotations.

Valuable property, that comes from limitation on polymorphism in Hindley-Milner types system, is decidable type inference. In opposite in System F it is proven to be generally undecidable i.e type checking is proven to be undecidable in System F without type annotations and that is equivalent to undecidable type inference.⁵

We need some examples here, but I'll show them a bit later.

Another result of the difference between System F and Hindley-Milner is that polymorphism is first-class in System F and it is not in the Hindley-Milner system.

If we look at a parametrically polymorphic type like a function, it takes some type and returns another one. Which property functions in some languages should have to allow us to make higher-order functions? They should be first-class citizens and we need the ability to save them into variables, to pass them into another function, and to return from functions.
In general, we need the ability to manipulate them as other 'data' values. The same goes for polymorphic types. When we need some forms of abstraction, we may need higher-rank types, something like the polymorphic type that takes another mono or polymorphic type and returns another polymorphic type. This feature is disabled in the Hindley-Milner types system.

Let's look at some examples to get a closer touch with it. They include parametric polymorphism, which we'll discuss in later parts of this article:

type Id<A> = (val: A) => A

The previous example shows us the definition of a generic (polymorphic) function type. We introduce parameter A and say that it is any function that takes a value of A and returns a value of A too.

Not let's check how we can't use it

type Id<A> = (val: A) => A

const id: Id = val => val

function applyId(id: Id) {
  return [id(10), id("Hello")]
}

In that TypeScript example, we'll get an error saying that we can't use generic type as is, and we have to pass type argument into it.

If we try to make another type parameter for applyId it won't work (a least when we define it at the top level):

function applyId<T>(id: Id<T>) {
  return [id(10), id("Hello")]
}

You'll get:

error

as you can instantiate applyId with type other than number or string, at the same time its signature is compatible with id function. For real, there are two options in TypeScript to pass function type as a generic one (usage of typeof).

All the previous examples show us how polymorphism can be limited in the Hindley-Milner type system with polymorphic parameters only at the top level, which is practically making only rank-1 polymorphism possible.

Impredicative instantiation is impossible in TypeScript, as we have seen that usage of type parameters forces you to make it monomorphic when used. We can consider impredicative instantiation like higher-order operations, but at type level if we could use generic in such a way that we can pass generic into and get another generic as output.

const id: Id = val => val

function applyId(id: Id) {
  return [id(10), id("Hello")]
}

If we could somehow instantiate Id to be polymorphic, it would be an example of impredicative instantiation.

We can handle limitations if we rewrite type Id as a call signature of an object literal type.

type Id = {
    <T>(val: T): T
}

const id: Id = val => val

function useId(id: Id) {
    return [id(10), id("Hello")]
}

Or type Id = <T>(val: T) => T

Or even inline needed type

const id: <T>(val: T) => T = val => val

function useId(id: <T>(val: T) => T) {
    return [id(10), id("Hello")]
}

Both introduce higher rank polymorphism (in this case rank-2) to us. You might notice that from the definition of Id type, the definition of type parameter moved from top level and same for inline example. As we don't have polymorphic parameters at the top level, we don't have to 'reduce' it to monotype.

type IdOuter<T> = {
    (val: T): T
}

const idOuter: IdOuter = val => val

IdOuter definition is equal to type Id<A> = (val: A) => A and as before it won't allow you to create values before you provide it with some.

These examples don't introduce impredicative instantiation as there are no manipulations with type. We just say that there will be something polymorphic and don't make any additional transformations.

Also, such definitions will block us from the ability to pass non-polymorphic functions.

If we do,

const idNumber = (val: number) => val

function useIdNumber(id: Id) {
    return [id(10)]
}

const result2 = useIdNumber(idNumber)

we'll get an error saying Type 'T' is not assignable to type 'number'. Even if we change to

function useIdNumber(id: Id, val: number) {
    return [id(val)]
}

we defined that parameter id should be polymorphic and it can't be any monomorphic function because it will be possible for such a function to do some logic based on knowledge of that monomorphic type, but we should be able to pass anything there.
For example, with the id function defined as val: T => T we have no information about the type and the only possible realization of id is to return the parameter as is. On the other hand, for functions like val: number => number you can do anything that is allowed to do with numbers.

The last example is

type Id = {
    <T>(val: T): T
}

const id: Id = val => val

function useId<U, P>(id: Id, a: U, b: P) {
    return [id(a), id(b)]
}

which shows us that we can make it with any values and not just number or string and also show why there should not be the possibility to pass non-polymorphic function in place of id. If we could do so and pass any type for a and b type safety would be lost.

Now for ReasonML

let id = x => x
let applyId = id => (id(13), id("Hello"))

Here, we'll get an error saying that incorrect type inferred for the second call of id (wanted int, but get string). This is because the type of polymorphic id in context of being parameter of applyId inferred to a monomorphic one (based of the first usage in body of applyId, type of id 'reduced' to int -> int).

let applyId = (id('a): 'a => 'a) => (id(13), id("Hello"))

We could imagine syntax similar to the above example, but it's not allowed to introduce new type variables like this. We can only help the type system to deduce the desired type by annotating with a concrete type like let applyId = (id: string => string) => [id(13), id("Hello")]. Even if we separate the applyId type definition and its realization, we would not be able to properly type it without providing argument type to it.

type applyId('a) = ('a => 'a) => (int, string)
let apply: applyId = id => (id(10), id("Hello"))

The example above will tell you that The type constructor applyId expects 1 argument(s). We've seen that already for TypeScript examples such as type parameter 'a introduced at the top level and should be 'reduced' to monotype when used. We can't express in ReasonML that the parameter of applyId must be a polymorphic function.

Without annotations, the same inference rules will work in PureScript:

import Data.Tuple

identity id = id

useIdentity id = Tuple (id 10) (id "Hello")

By default, PureScript can't infer the correct type for useIdentity, as it goes beyond Hindley-Milner features. But in PureScript, we are also allowed to annotate useIdentity parameter as polymorphic

import Data.Tuple

identity id = id

useIdentity :: (forall a.  a -> a) -> Tuple Int String
useIdentity id = Tuple (id 10) (id "Hello")

We specified monomorphic return types that exactly match our realisation, but for real we can do something like useIdentity :: forall b c. b -> c -> (forall a. a -> a) -> Tuple b c and useIdentity x y id = Tuple (id x) (id y) and that will be fine. After all, we can use it like x = useIdentity 10 "Hello " identity.

In TypeScript, we can also write it as

useIdentity :: forall b c. b -> c -> (forall a.  a -> a) -> Tuple b c
useIdentity x y id = Tuple (id x) (id y)

or as

useIdentity :: (forall a.  a -> a) -> forall b c. b -> c -> Tuple b c
useIdentity id x y = Tuple (id x) (id y)

Both forms are the same rank, as it doesn't base on which side of the arrow polymorphic parameters occurred. The forall b c. part can be moved to the beginning of definition and the result will be the same.

A Hindley-Milner type system with extensions is the basis for both PureScript and ReasonML type systems, so they can use its inference algorithm (also with extensions if needed), called Damas-Milner algorithm W.

A simple description of the algorithm is that it puts a limitation on a type being inferred until it has available information. The most common type will be inferred. This feature is inherent in the languages of the ML family. For cases that are complicated enough, algorithms won't be able to infer accurate type if we didn't explicitly put type on parts of an inspected expression.

To achieve automatic type inference, Hindley-Milner type system restricts polymorphism where function arguments and elements of structures can only be monomorphic.

A hard description is long enough to take its article and involves the reader to at least have some knowledge of symbolic logic. You can check it here for example here

Let's look at a simple inference example:

iAmANumber =
  let square x = x * x
  in square 42.0

or Inference example for ReasonML:

type a = {
  f1: string,
  f2: string,
}

let x = {
  f1: "Hello",
  f2: "World"
}

We can think about expressions like these as the simplest case of type inference.

Let's look at the simple example of inference in TypeScript.

const inferred = "Hello world"; // Infers literal type 'Hello world' for variable 'inferred'.
const inferred2 = SomeObject.someMethod(); // Infers 'inferred2' type based on return type of someMethod.

Examples of such simple cases may look strange, but some time ago in old versions of popular languages, we didn't have such abilities and it led to redundant verbosity, especially in the case of generics. In actual versions, we can tell the compiler that it should infer the variable type based on the right part of an expression.

Such languages are, for example, Java where you had to write constructions like:

ArrayList<String> myArrayList = new ArrayList<String>();

where the variable list has the type of ArrayList<String> and after we repeatedly write ArrayList<String> to create an instance. The ability to remove such duplication was only added in 2018 in Java 10 by adding local type inference with the var keyword, so you can now write:

var myArrayList = new ArrayList<String>();

There is the same story with C#, which syntax is very similar to Java's, but features for local inference with var keyword were added earlier, in 2007 with C# 3.0.

Also, with C++ things were the same, and the keyword auto with the same idea as previous var was added only in C++11. In C++14, its function was extended to allow inference of return type of functions.

But enough off topic discussion, let's return to our languages.

PureScript is not strictly based on some type system. Instead, it is inspired by some research as its author mentioned⁶. As a result, there is no proof of its soundness, and its type system is a mix of ideas from some research. As one of them is HMF⁷, here and throughout the article we'll use HMF as is because there is no expanded name in research which is an extension of Hindley-Milner type inference with first-class polymorphism. So, it allows explicit polymorphism, effectively taking features of System F. HMF uses Damas-Milner algorithm W with small extensions.

Valuable properties of HMF:

HMF is a conservative extension in that every program that is well-typed in Hindley-Milner, is also a well-typed HMF program, and type annotations are never required for such programs. For example, in Standart ML, you can write an identity function as fun id x = x and its type will be val id = fn : 'a -> 'a, which is the same as we have in PureScript for such function.

Therefore, if we transfer a program with definitions like fun id x = x (and replace some syntax constructions if needed) into language that uses HMF, that program will be typed without any additional annotations and will pass type checking.

In practice, few type annotations are needed for programs that go beyond Hindley-Milner. Only polymorphic parameters and ambiguous impredicative instantiations must be annotated. Both cases can be specified and are relatively easy to apply in practice.

This point comes first from any program that is well-typed in Hindley-Milner, which may have no annotations at all, and it will be well-typed in HMF without changes except some may be syntax-specific and necessity in annotations would break that. We've already seen examples where type annotations are needed and where not. Some more examples:

```PureScript
  import Data.Tuple
  import Data.Int
  identity id = id

  intToString = toStringAs decimal

  useIdentity id x y = Tuple (id x) (id y)

  a = useIdentity intToString 10 10
  b = useIdentity identity 10 10
```

All definitions above don't require any annotations because, but different type will be inferred for useIdentity (`forall a b. (a -> b) -> a -> a -> Tuple b b`) which will make usage like `c = useIdentity identity 10 "Hello"` impossible again.

The type inference algorithm is very close to algorithm W. It does not require unfamiliar operations, which makes it relatively easy to understand and implement. I'd recommend you to check the difference in the paper.

Valuable property: HMF will never infer polymorphic types for parameters automatically (what we've seen in the previous point) and whenever there is an ambiguous impredicative application, HMF always prefers the predicative instantiation and always introduces the least inner polymorphism possible. Being compatible with Hindley-Milner, it will infer the same types as Hindley-Milner would do, so if you want to introduce impredicativity in such cases, you need to annotate that explicitly.

HMF extends Hindley-Milner with regular System F types where polymorphic values are first-class citizens. To support first-class polymorphism, two ingredients are needed: higher-rank types and impredicative instantiation.

With higher-rank types, we've already gotten acquainted while talking about the difference between System F and Hindley-Milner systems. To generalize: without support for higher-rank types only definitions can be polymorphic while parameters can not (this is what you could see with id function examples before).

useIdentity :: forall a. (a -> a) -> Tuple Int String // Rank-1
useIdentity :: (forall a.  a -> a) -> Tuple Int String // Rank-2

Without support for higher-rank types, universal quantifiers (forall) can appear only at the top level and can't be nested.

Impredicative polymorphism allows you to instantiate type variables with not only monomorphic types but with polymorphic types and even self-references (this is why it's called impredicative). Impredicative polymorphism takes the idea of higher-rank types to its natural conclusion - universal quantifiers allowed anywhere in a type.

Higher-rank types always involve some limited form of impredicative polymorphism (where impredicativity only allows for -> constructor).

Example of predicative instantiation

data SomeType a = SomeType a

someValue :: SomeType Int
someValue = SomeType 10

Impredicative instantiation

data SomeType a = SomeType a
data SomeOtherType a = SomeOtherType a

someValue :: SomeType SomeOtherType
someValue = SomeType

Here you'll get an error "Could not match kind Type -> Type with kind Type", which means that you can't pass polymorphic type as a parameter of another polymorphic type (you should get another polymorphic type as a result of such operation).

In reality, even though HMF proposes the usage of impredicative instantiation, PureScript does not fully implement it. Here is an example of HMF paper that won't work:

id x = x
poly (f :: forall a. a -> a) = Tuple (f 1) (f true)

apply f x = f x

someVal = apply poly id

You'll get an error saying, The type variable a has escaped its scope.

You can check some more info about impredicative polymorphism here. It is the documentation for Haskell. However, it gives a good and simple description of the topic.

TypeScript is using the structural type system and has its own set of rules to infer types. In structural type systems, equivalence and compatibility of types are defined by structure, compared to nominative systems, where those properties are defined by types names.

Supertype/subtype relations in such systems are defined by structure too so in TypeScript some type A is considered as a supertype of B if B has at least all fields defined in A with the same types. There are some design decisions in TypeScript based on its structural nature. For example, if you define id function like in ReasonML or PureScript

const id = val => val

its type won't be inferred to a type with variable. Instead, it infers any for the parameter val. TypeScript parametric polymorphism starts to work only when it is explicitly stated somewhere, so in the example above parameter val got any type and all type information will be lost after you apply such id function to any value, as return type will be any too (inferred by the fact that you return val and it has type any).

It is a superpowered type in TypeScript - it is assignable to any other type and vice versa. You can access any fields of any and type checking will always pass. When you are using any, the statically typed world is left behind and to get back to it you can apply type assertion (operator as) to get some new type.

TypeScript won't check that you are doing fine with that, so it is good practice to check that a value typed as any can be properly used as the value of target type. There is a mechanism called type narrowing to help you with that. There is a close, but safer one in TypeScript - unknown. So if any is about 'everything available here', unknown is about 'everything available here, but you can do nothing with that' because unknown is too general.

function whatToDoWithUnknown(item: unknown) {
    // You can do nothing with unknown here. Only type narrowing can help you to make something useful
    return item
}

function whatToDoWithAny(item: any) {
    // No rules zone
    console.log(item.field1)
    const b = item.field2 + item.field3.field5
    // etc.
    return b
}

const a = 10

whatToDoWithAny(a)
whatToDoWithUnknown(a)

Example of type narrowing with type predicates

const a: any = 10

const isNumber = (val: any): val is number => {
    return typeof val === 'number'
}

if (isNumber(a)) {
    // a has 'number' type in this context
}

type A = {
  field1: string
}

type B = {
  field2: string
}

const a = {
  field1: "Hello",
  field2: "World"
}

const isA = (val: unknown): val is A => {
    return typeof val === 'object' && val !== null && 'id' in val
}

const workWithB = (val: B) => {
  console.log(val.field2)
  // console.log(val.field1) - error
  if (isA(val)) {
    console.log(val.field1)
    console.log(val.field2)
  }
}

Therefore, as with any, you can pass anything where unknown type is expected, but after there is nothing to do with that value, it can be converted to 'useful' type only by narrowing or assertion.

In presence of subtyping, unknown is the supertype for everything (as everything can be passed where unknown is expected and unknown itself can't be used anywhere), when with any that rule works vice versa so unknown is more type-safe feature.

There is also an opposite to unknown - never. Never is a subtype for everything so no values of other types can be passed where never expected, so practically you can't directly create values of never type.

There are no such special types in PureScript and ReasonML, so TypeScript has some more presence of set theory and its types, including the set that contains all possible values and empty set into its type system (and some operations with them will work exactly like on sets in set theory, we'll look at them in the next chapter).

type AUnion = unknown | string
type AIntersection = unknown & string

type BUnion = never | string
type BIntersection = never & string

You can check types from the example above at playgroud - they will behave as if you operate with sets.

This is intuitive for structural type systems to be more related to set theory than nominative ones (where PureScript and ReasonML are both mostly nominative). For example, in set theory, some set A will be a subset of some set B if all values from A are also included in B, with no respect to names of that sets or ways of creation for these set - only fact of containing same values generates subset-superset relations (or equivalency).

Additionally, that is close to what we said about structural type systems - subtype/supertype relations based only on structure, not names. If we consider structure as a set of possible values of that type, that relation to set theory becomes more clear.

type A = {
    field1: string
}

type B = {
    field1: string
    field2: string
}

const processA = (val: A) => {
    console.log(val)
}

const b: B = {
    field1: "Hello",
    field2: "World",
}

processA(b)

The simple example above shows how subtyping relations appear in TypeScript - B is considered a subtype of A because there is field1: string in B and by its structure it can be used anywhere, where A is expected.

In the next examples, we can see that there are cases where TypeScript can't infer types in cases where ReasonML and PureScript can do it. On the other side type inference in TypeScript evolves and one of the fresher features - the ability to infer types of class fields based on types of constructor parameters⁸.

Online compiler with next example compared to ReasonML/PureScript, where the correct type of function will be inferred based on its parameters used in the body

function first(a: number, b: number) {
    return a + b;
}

function second(a, b) {
    return first(a, b);
}

second('a', 'b')

In the example above, TypeScript does not infer types for second(a, b) params. They will be any without declarations and type safety will be ruined.

let add = (x, y) => {
  x + y
}

let someF = (x, y) => add(x, y)

let x = someF(1, 1)

add a b = a + b

someF a b = add a b

x = someF 1 2

PureScript and ReasonML on the other side infer the most general type available for whole code from the examples above. The type will include some polymorphic variables (type parameters) and for variable x concrete type (int) will be inferred based on usage of polymorphic functions with literals.

As we said before, the inference is decidable in the Hindley-Milner types system and that is its notable property - the ability to infer the most general type of the program without any hints (like type annotations). This is its very important difference from System F, so by implementing features basic for System F, the inference may appear not available without hints when that features are used, as they are the reason why the inference is undecidable for System F.

We have already seen examples of undecidable inference, once again

useIdentity :: (forall a.  a -> a) -> Tuple Int String
useIdentity id = Tuple (id 10) (id "Hello")

Here we have to annotate the type for useIdentity because HMF won't infer that for you and id will be a monomorphic one.

In official documentation you can read about TypeScript inference.

Also, it would be remiss not to mention TypeScript's literal types.

type OneTwoThree = 1 | 2 | 3
type OnlyA = 'A'

const b: OnlyA = 'B' // error

This feature does not exist in the other languages we are talking about. When you are using a union of literal types, it becomes pretty close to using enums/variants. You can use switch like a very poor version of pattern matching to properly work with concrete values and it also opens you opportunities to interop with something typed as string or number, but if you know that there is a pool of concrete values that should go in, you can type check it at a higher level and still pass your value into for example your literal type type a = 'A' is a subtype of string.

Also, returning to one of the previous examples with id

let values = [id(10), id("Hello")] as const

We can apply as const assertion and many different type will be inferred for us. Without it, we had (string | number)[] and with it, we get [10, 'Hello'] tuple, and literals didn't get widened to their supertypes (number and string). This is another example where literal types can do their job.

ReasonML is a dialect of OCaml which is based on an extension of Standart ML, which in its turn uses the Hindley-Milner system - ML^F⁹.

ML^F differs from Hindley-Milner in a close way to how HMF differs from it. The main idea of ML^F is to add support for first-class polymorphism into the Hindley-Milner system.

Valuable properties of ML^F to note:

ML^F is more powerful than HMF, so any well-typed HMF program is also a well-typed ML^F program. The logic here is the same as in HMF to the Hindley-Milner system. For example, if we have some PureScript code
```
useIdentity :: (forall a.  a -> a) -> Tuple Int String
```
and somehow translate it to languages based on MLF, we'll get a well-typed program.
ML^F goes beyond regular System F types which makes ML^F considerably more complicated. This is the case for programmers that have to understand these types and meta-theory of ML^F, the implementation of type inference algorithm, and the translation to System F (which is important for qualified types).

If compared to HMF, implementation in some languages should be less complex (in theory). I don't think there are any simple examples to show such complexity.

ML^F does not require annotations for ambiguous impredicative applications. For example in PureScript
```
single item = [item]
id x = x

singleId = single id
```
singleId will have type forall a. Array a -> a. However, it could also be typed as Array (forall a. a -> a) and HMF in such a case prefers the type which the Hindley-Milner system would prefer. If you want type Array (forall a. a -> a) for singleId you can annotate it like singleId = (single :: (forall a. a -> a) -> Array (forall a. a -> a)) id. MLF on its side will infer more types without annotations and try to decide such ambiguity in favor of a more general type.

There is also differences in type inference between ML and ReasonML (OCaml) in general:

ML adds a condition into the Hindley-Milner system for generalization (one of the typing rules in Hindley-Milner), which is the so-called value restriction: the type of some variable is generalized only if it has no visible side-effect. ReasonML relaxes the value restriction.
It avoids a scan of the type environment by implementing a level-based generalization algorithm, which is inspired by region-based memory management.

There is good description of how OCaml's type checker works.

HMF ideas are close to ML^F's one and they both have the same pitfall - a programmer is required to make type annotations for cases of such polymorphism. Consequently, it is still leaving the program fully inferable when first-class polymorphism didn't get used because type inference is still undecidable for it.

Neither are silver bullets. They are just tools that may be helpful if you need that higher level of abstraction and if you are ready for trade offs.

There is not much sense and it's very hard or impossible to show examples for all cases of type inference, but it's important to understand that this instrument allows, with help of a type-checker, us to write more expressive and less verbose code but to stay within the framework of static typing.

In conclusion, I can say that in TypeScript there are many more limitations on which things will be inferred for you, such as being structurally typed and allowing explicit forms of polymorphism by design that leaves much more freedom on what different expressions can mean in terms of typing. ReasonML and PureScript have very close inferring capabilities, and both have some features that ruin the ability to infer without additional annotations.

Soundness

TypeScript allows some unsound behavior on purpose. You can check it out at TypeScript notes about it. Also, if you want to take a look at roots of type inference in TypeScript, you can check TypeScript spec, but beware that it's outdated archived and not supported anymore.

Some examples from TypeScript doc:

let x = (a: number) => 0;
let y = (b: number, s: string) => 0;
y = x; // OK
x = y; // Error

This one allows you to set the value of a variable to a function with fewer parameters than expected by that variable type

It will work even with custom types

let processEntity = (a: MyType, b: MyType2) => 0;

let processEntity2 = (c: MyType) => 0;

processEntity = processEntity2

processEntity2 = processEntity // error

However, it won't work if you change the type of parameter c to MyType2. Parameters should follow the same order, here TypeScript won't allow you to make something unexpected.

TypeScript documentation gives a good description of why such behavior allowed

You may be wondering why we allow ‘discarding’ parameters like in the example y = x. The reason for this assignment to be allowed is that ignoring extra function parameters is quite common in JavaScript. For example, Array#forEach provides three parameters to the callback function: the array element, its index, and the containing array.

Another example from TypeScript docs:

enum EventType {
  Mouse,
  Keyboard,
}
interface Event {
  timestamp: number;
}
interface MyMouseEvent extends Event {
  x: number;
  y: number;
}
interface MyKeyEvent extends Event {
  keyCode: number;
}
function listenEvent(eventType: EventType, handler: (n: Event) => void) {
  /* ... */
}
// Unsound, but useful and common
listenEvent(EventType.Mouse, (e: MyMouseEvent) => console.log(e.x + "," + e.y));
// Undesirable alternatives in presence of soundness
listenEvent(EventType.Mouse, (e: Event) =>
  console.log((e as MyMouseEvent).x + "," + (e as MyMouseEvent).y)
);
listenEvent(EventType.Mouse, ((e: MyMouseEvent) =>
  console.log(e.x + "," + e.y)) as (e: Event) => void);
// Still disallowed (clear error). Type safety enforced for wholly incompatible types
listenEvent(EventType.Mouse, (e: number) => console.log(e));

That behavior can be disabled with the strictFunctionTypes compiler option. Why is it considered unsound? If we remove a connection to Event for a simpler example

enum EventType {
  Mouse,
  Keyboard,
}
interface E {
  timestamp: number;
}
interface MyMouseEvent extends E {
  x: number;
  y: number;
}
interface MyKeyEvent extends E {
  keyCode: number;
}
function listenEvent(eventType: EventType, handler: (n: E) => void) {
  if (eventType === EventType.Keyboard) {
      handler({timestamp: 123})
  }
}
// Unsound, but useful and common
listenEvent(EventType.Mouse, (e: MyMouseEvent) => console.log(e.x + "," + e.y));
// Undesirable alternatives in presence of soundness
listenEvent(EventType.Mouse, (e: E) =>
  console.log((e as MyMouseEvent).x + "," + (e as MyMouseEvent).y)
);
listenEvent(EventType.Mouse, ((e: MyMouseEvent) =>
  console.log(e.x + "," + e.y)) as (e: E) => void);
// Still disallowed (clear error). Type safety enforced for wholly incompatible types
listenEvent(EventType.Mouse, (e: number) => console.log(e));

Therefore, you can see it yourself as in the example above we expect x and y in listenEvent(EventType.Mouse, (e: MyMouseEvent) => console.log(e.x + "," + e.y));, but realisation can provide less data and we'll get runtime error.

Another place for unsoundness is optional and the rest parameters

function invokeLater(args: any[], callback: (...args: any[]) => void) {
  /* ... Invoke callback with 'args' ... */
}
// Unsound - invokeLater "might" provide any number of arguments
invokeLater([1, 2], (x, y) => console.log(x + ", " + y));
// Confusing (x and y are actually required) and undiscoverable
invokeLater([1, 2], (x?, y?) => console.log(x + ", " + y));

Here, unsound behavior is almost the same as the previous one in that realization of invokeLater could provide any number of arguments, but we are not forced to rely on that. Instead, we can pass a function that expects 3 params or 4 or 100 and it will pass type check, but all of those parameters may be undefined.

The last thing to note is array and object index access in TypeScript. By default, it is not checked and situations, where you can get undefined, pass type checking.

const a = [1,2,3]

const b = a[42]

Type of b will be inferred to number. You can turn on the noUncheckedIndexedAccess flag to force TypeScript to add undefined to item type when you access it by index.

Being based on ML^F which is sound, doesn't make ReasonML fully sound in practice.

Here are some examples of unsound behavior in OCaml here and here. According to this fact, we can consider that ReasonML as being the dialect of OCaml may have unsound behavior too.

Here you can read more about it.

Example of almost the same code as we used in TypeScript's.

You can see that ReasonML can properly infer types. Also, there is more complex case on ReasonML

I didn't find issues that mention unsoundness in PureScript, but there is no proof that it is fully sound.

Problems with documentation writing

Sergey Golovin — Mon, 09 Aug 2021 11:03:00 +0000

In the picture down below is Stonehenge, one of the most famous architectural monuments in the world!

© 2007 by thegarethwiscombe

It's hard to find anyone who hasn't heard of Stonehenge, yet nobody can say for sure what was the original purpose pursued by the ancient people who built it. In fact, the scientists would be grateful for any text or graphical description from the builders of this monument.

When it comes to “Stonehenges” in a codebase, it can be a great architectural solution that we use every day, building a whole system on top of it without really understanding why we or previous developers built it as they did. Perhaps, they had their reasons, but these are now completely irrelevant. We can't be sure.

However, a lack of understanding regarding the original reason behind implementing a specific element can lead to an occasional increase of complexity.

The importance of documentation

While many developers truly enjoy making and working with projects that have good documentation, they still tend to feel reluctant to write it. This paradox of a situation exists despite us, developers, understanding the importance of documentation. Still, the difficulty of writing and supporting a detailed description of the code does bear its burden. But is there a way to make it easier? I think there is! Let me show you it in this article!

Main problems of documentation writing

The main problem and, perhaps, the root of the rest of the problems is the separation of code and documentation. When we write our code and documentation in different systems (e.g. GitHub and Confluence), we have two different versioning systems for code and documentation. But what does this mean? Well, it can lead to the growth of project support complexity. For instance, every single change in a source code should be manually synchronized with documentation, while every single change in the documentation is to be connected to the source code.

This complexity often stops people from writing documentation at all, they may ask, "Why should we spend our time trying to write documentation for a project in development status?", adding, "We'll write the documentation when we get the completed product". This is possible, but, unfortunately, in real life, a "completed" project is a dead project. All live projects are in continuous development status. Thus, the only way to have good documentation is to write it in parallel with development, making this process as easy as possible with minimal overhead.

Take for example this, at different times and in different places, developers tried to solve this. For instance, Racket language has its own way to keep source code and documentation as close as possible by using Scribble, which allows us to integrate Racket code, including evaluating it inside the documentation:

#lang scribble/manual
@(require (for-label racket))

@title{My Library}

An example of the Racket code:

@racketblock[

(define (nobody-understands-me what)
  (list "When I think of all the"
        what
         "I've tried so hard to explain!"))
(nobody-understands-me "glorble snop")

]

In another example, if you're an Emacs enthusiast, you can use the awesome tool/language called Org Mode, which allows one to write complex documents, evaluate source code of different programming languages, and use the Literate Programming paradigm to keep all your source code within the documentation. Here's an example from its home page.

#+title:  Example Org File
#+author: TEC
#+date:   2020-10-27

* Revamp orgmode.org website

The /beauty/ of org *must* be shared.
[[https://upload.wikimedia.org/wikipedia/commons/b/bd/Share_Icon.svg]]
** DONE Make screenshots
   CLOSED: [2020-09-03 Thu 18:24]

** DONE Restyle Site CSS

Go through [[file:style.scss][stylesheet]]


** TODO Check CSS on main pages 

* Learn Org

Org makes easy things trivial and complex things practical.

You don't need to learn Org before using Org: read the quickstart
page and you should be good to go.  If you need more, Org will be
here for you as well: dive into the manual and join the community!

** Feedback

#+include: "other/feedback.org*manual" :only-contents t
* Check CSS minification ratios

#+begin_src python
from pathlib import Path
cssRatios = []
for css_min in Path("resources/style").glob("*.min.css"):
    css = css_min.with_suffix('').with_suffix('.css')
    cssRatios.append([css.name,
    "{:.0f}% minified ({:4.1f} KiB)".format( 100 *
                      css_min.stat().st_size / css.stat().st_size,
                      css_min.stat().st_size / 1000)])
return cssRatios
#+end_src

#+RESULTS:
| index.css    | 76% minified ( 1.4 KiB) |
| org-demo.css | 77% minified ( 2.8 KiB) |
| errors.css   | 74% minified ( 4.9 KiB) |
| org.css      | 75% minified (10.7 KiB) |

Org Mode is a great solution if your team is familiar with Org Mode and Emacs. Even Github supports Org Mode, and you can use *.org files instead of *.md ones.

On the other hand, another problem arising from the separation of code and documentation is the weak cohesion between code and documentation parts. For example, we can describe a feature in our system, but every single part of the description is about different parts in our source files. This issue leads us to an inability to update certain parts of documentation after changing files connected to the source code or editing specific parts of those source files. Vice versa, while reading documentation, it's difficult to quickly find related source code for a certain paragraph of documentation. Without solving this issue, the complexity of documentation support will grow increasingly with the growth of project size.

But you may disagree and say, "That’s not true.Our API documentation doesn't have problems like that!" and you'll be right! You don't have such problems with API documentation or your Storybook documentation because it's generated from source code or with huge involvement of your source code in it. It has strong cohesion with source code and uses the same version control system as your source code. The only way to make writing project documentation easier, is to use the same set of tools as for code writing.

You can still solve this issue with tools like Scribble or Org Mode, but you'll need to combine different parts of documentation manually, which can be hard in big projects.

Documentation as code

Keeping documentation and code together allows to achieve better control of changes and to make support of documentation easier. But without proper tools, it can be awkward to work with documentation for anybody other than the developers. For example, we can use markdown files for writing documentation, but if we place them near related source files, it will be difficult for managers, analysts, QAs, and designers to find something in this documentation. On the other hand, if we place them into a separate directory with its structure, we will not solve the issue with weak cohesion. In addition, with markdown files, we can't automatically create references from *.md files to particular parts of a source file, or we can't automatically combine all *.md files about the whole feature but written in the perspective of different source files. Let's look at the following example:

.
└── src
    ├── api
    │   ├── auth.js
    │   ├── news.js
    │   └── offers.js
    ├── components
    │   ├── auth.js
    │   ├── header.js
    │   ├── news.js
    │   └── offers.js
    ├── index.js
    └── reducers
        ├── auth.js
        ├── news.js
        └── offers.js

The example shows a simple project. Let's imagine we want to write documentation for our auth feature. The whole feature is implemented in three different files, but by "auth's implementation", all source files, not only api/auth.js or components/auth.js. So, to achieve strong cohesion between code and documentation, we should somehow place different parts of an article about authentication in different files and generate a single article from these parts.

If we do that, and even better, we add links to source code from a generated article, we can solve both problems with weak cohesion and using different versioning tools. But it'll still be a little awkward to use because good documentation should allow you to search through it and edit it.

The solution

I tried finding something which could solve all of these problems, but unfortunately, I hadn't found it. So I wrote my own tool called Fundoc to achieve all described goals and even more. The tool can:

Keep documentation and source code as close as possible.
Use the same version control system for documentation as for code.
Be language agnostic.
Collect all documentation from different repositories in one particular place.
Allow non-programmers to read and write documentation.

So what can Fundoc do? It can generate documentation in two formats: raw markdown files (maybe later I'll add Org Mode support) and mdBook. The main idea behind this tool is to be as straightforward and uncomplicated to use as possible while providing all of the required functionality like search through documentation, documentation editing without the necessity to know the structure of a project, using one version control system, and so on.

But what do I use to keep the simplicity of a tool and the possibility to work with it for non-programmers? I use Github, that's it. Of course, in the future, it's possible to extend support of different services like GitLab, Bitbucket, or something like that. Let me explain how it works. Developers write documentation in source files or in markdown files marking every single documentation part with a simple marker that describes a result article title such as:

// src/api/auth.js

/**
* @Article Authentication
*
* To get authenticated, you should use the `login` function, which returns auth-token to pass it with API requests that require authentication.
*/
const login = (username, password) => {
    // some code here
}

/**
* @Article Authentication
* 
* To log out, use the `logout` method. It will invalidate the auth-token and delete it from cookies.
*/
const logout = () => {
    // some code here
}

And some description for a UI-part:

// src/components/header.js

const Header = props => {
    const { isUserAuthorized } = props

    /**
    * @Article Authentication
    *
    * Only authorized users can see their balance in the header
    */
    return (
        <div>
            ...
            {isUserAuthorized && <UserBalance />}
            ...
        </div>
    )
}

This rather simple example will be compiled into one markdown file:

# Authentication

To get authenticated, you should use the `login` function, which returns auth-token to pass it with API requests which require authentication. [[~]](https://github.com/username/repository/blob/master/src/api/auth.js#L3-L7)

To log out, use the `logout` method. It will invalidate the auth-token and delete it from cookies. [[~]](https://github.com/username/repository/blob/master/src/api/auth.js#L12-L16)

Only authorized users can see their balance in the header. [[~]](https://github.com/username/repository/blob/master/src/components/header.js#L6-L10)

To see more realistic documentation examples you can check out documentation of Fundoc itself or another project that used Fundoc.

In the compiled markdown file, you can see references to the particular parts of the source code. It allows you to find the exact source of every single part of the documentation. It can be useful for non-programmers if they want to edit documentation. If you believe they should still work with git to push their changes, they actually should not. Here's the example of editing documentation in the repository of Fundoc:

So on the gif, we can see that the only thing we need to edit our documentation is GitHub itself. Yes, it still requires an understanding of what GitHub is and the fundamental terms like "commit" and "branch". As practice shows, QAs, managers, designers, and analysts can handle it without any problems. At the same time, this way of working with documentation doesn't require knowing the file structure of a project from non-developers. It's definitely much easier than working with CLI-tools and dramatically easier than trying to synchronize Confluence and source code.

At the end of the article, I wanted to remind you that Fundoc now is in the beta state, and some APIs can change in the future. Otherwise, it already solves many problems and is used in different projects, so you can try to use it as well. If you have any questions or suggestions, feel free to send me them via Github issues or PRs. I'll be glad to make it better with your help!