DEV Community: Andrey Frolov

Parsers for Dummies

Andrey Frolov — Sat, 07 May 2022 12:09:23 +0000

Here are my notes about parsers. They are not particulary academic, but I hope they can help someone dig into amazing parsing concepts. The high level overview of compilers can be found right here.

What is lexing?

It's a process of dividing a string into words (tokens).

A very important part of the job of the lexer is dealing with whitespace. Most of the times you want the lexer to discard whitespace. Otherwise, the parser would have to check for the presence of whitespace between every single token, which would quickly become annoying. Sometimes, you also want to wipe out all the comments on lexer stage as they don't make any sense for parsing grammar.

What is parsing?

It's a process of text processing. In our case, it's a program, which somehow understands the grammar of an actual string.

Parsers groups

Let's start by splitting parsers into two big groups

Hand-written parsers — parsers that you write manually.

Examples:

recursive decent parsers

Automatically generated — there are parser generators, these tools can take the grammar of your language and produce a result.

Examples:

LL(1) .. LL(K)
LR(K): SLR(1) LALR(1)
GLR
PEG

Parsing tools are traditionally designed to handle context-free languages, but sometimes, the languages are context-sensitive. This might be the case to simplify the life of programmers or simply because of bad design.

A typical example of context-sensitive elements are the so-called soft keywords, i.e., strings that can be considered keywords in certain places, but otherwise can be used as identifiers.

Language and Grammar

Let's create our brand new language:

Alphabet: Σ = {x,y} (set of characters)
Language: L(Σ) = {x, y, xx, xy .. }

So, language is also a set of some random combinations of two characters from an alphabet set.

In a nutshell, a grammar is a set of restrictions or constraints applied to an alphabet.

Formal grammar

G = (N, T, P, S)
N — non terminals (variables)
T — terminals (specific character or symbol)
P — productions — rules of the grammar
S — starting symbol

Let's take an example and try to apply our new knowledge about grammar.

⭢ in other words, mean "is can be defined as"
ε, epsilon means nothing or an empty string



S ⭢ xZ
Z ⭢ y

So let's start to read this as a sentence:

Starting symbol (S) is can be defined as xZ
where x is terminal and Z is non-terminal
After that let's take a look at the second production (Z ⭢ y)
Let's make a substitution or apply derivation



S ⭢ xZ ⭢ xy

Derivation — a sequence of production rules, in order to get the input string.

Context free grammar

These grammars are used for parsing programming languages, so to come under the definition of context-free grammar, grammar should use these rules:

Only non-terminals on LHS (left hand side)
No context on LHS
RHS: mix of non-terminals and terminals

BNF notation

Such notations are treated as BNF notations



S : xZ
Z : y

or they can look something like this:



<postal-address> ::= <name-part> <street-address> <zip-part>

      <name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL> | <personal-part> <name-part>

  <personal-part> ::= <initial> "." | <first-name>

 <street-address> ::= <house-num> <street-name> <opt-apt-num> <EOL>

       <zip-part> ::= <town-name> "," <state-code> <ZIP-code> <EOL>

<opt-suffix-part> ::= "Sr." | "Jr." | <roman-numeral> | ""
    <opt-apt-num> ::= <apt-num> | ""

Derivations process

Substitution sequence to retrieve an actual string. Let's take a look at this kind of grammar.



E : E + E
  | E * E
  | number

| — means or
number — is any valid number

Let's start a derivation process:



E ⇒ E + E
  ⇒ number + E
  ⇒ number + E * E
  ⇒ number + number * E
  ⇒ number + number * number
  ⇒ 2 + 5 * 3

So, we always replace the left most non-terminal, but let's try replacing the rightmost non-terminal:



E ⇒ E + E
  ⇒ E + E * E
  ⇒ E + E * number
  ⇒ E + number * number
  ⇒ number + number * number
  ⇒ 2 + 5 * 3

The left most derivation is used in LL parsing and recursive decent parsing.

On the other side, right most derivation can be more powerful and cover more complex languages (LR parsing).

Parse trees

A parse tree is a representation of the code closer to the concrete syntax. It shows many details of the implementation of the parser. For instance, each rule usually corresponds to a specific type of a node.

Let's build a parse tree for the above example. In the case of the left most derivation we get the following result:

And in the case rightmost derivation we get the following result:

So, if we try to DFS (depth first search) on such trees we get a kind of non-determinism. So, these kind of grammars are called ambiguous grammars as there are have multiple ways to build a sequence of derivations.

Ambiguous grammars

Why is ambiguous grammars a problem? Because you can get different results from executing your expression.

Here are the reasons why grammar can be ambiguous:

Operator precedence

Let's take an example from our previous paragraph:

The result of this parse tree will be 17.

And if we take a look at the one on the right.

The result will be 21. So it's wrong because the multiplication operator (*) has more precedence than the plus operator (+).

Associativity

Let's take a look at this kind of grammar and build some parse trees:



E : E - E
  | number

So, for mathematical operations, we should have left associativity to avoid errors.

Left recursive rules to the rescue

To fix the problem with associativity, we can use left recursion.

In the context of parsers, an important feature is support for left-recursive rules. This means that a rule starts with a reference to itself. Sometimes, this reference can also be indirect, that is to say, it could appear in another rule referenced by the first one.



E : E - number
  | number

This way, you always get the correct result, in other words, your parse tree will also grow to the left. This statement is correct for left-associative operators.

Enforcing correct precedence

To enforce correct precedence we should find a way to tell the parser which of operators should be executed first. In general, we can fix this by introducing new layers of non-terminals and force + operator come first before * operator.

Let's take a look at some grammar:



E : E + E
  | E * E
  | number

Let's introduce new non-terminals:



E : E + T
  | T;

T : T * F
  | F;

F : number;

Let's take a look at the result tree:

Abstract syntax trees

A parse tree is usually transformed into an AST by the user, possibly with some help from the parser generator. A common help allows us to annotate some rules in the grammar, to exclude the corresponding nodes from the generated tree. Another option is to collapse some kinds of nodes if they have only one child.

This makes sense because the parse tree is easier to produce for the parser since it is a direct representation of the parsing process. However, the AST is simpler and easier to process through the following steps of the program. They typically include all the operations that you may want to perform on the tree: code validation, interpretation, compilation, etc.

So, in other words, root nodes are actually operators in such trees.

So, the result tree is much smaller than the parse tree representation.

Feel free to ask questions, express any opinions or concerns, or discuss your point of view. Share, subscribe, and make code, not war. ❤️

If you'll find an error, I'll be glad to fix it or learn from you — just let me know.

You can DM me on Twitter or connect on LinkedIn. I'm always open to new connections, people, and opportunities.

How We Migrated from Javascript and Flow to TypeScript at Osome

Andrey Frolov — Sat, 23 Apr 2022 11:49:53 +0000

This fairy tale started a long time ago. Often, you make a bet on the wrong horse in life, but, unfortunately, you cannot do anything about it. You're always working with limited information (especially about the future), when making decisions, so essentially you are betting. This is life: sometimes it happens in your personal life and sometimes in your work life. But the only thing that really matters is how you learn from your bets.

One such decision was betting on Flow. If you aren’t aware of what Flow is, it is Facebook's JavaScript language superset that brings types and type system to JavaScript. The idea is pretty straightforward: write your code with a kind of syntactic sugar Flow that takes your files and builds an extended abstract syntax tree (AST), analyze it, and if everything works, transform it into regular JavaScript.

Although, we started developing our apps in 2017/2018, when TypeScript tooling, support, and documentation were not as strong as it is now, and there was no clear winner between Flow and TypeScript. The developers who started it, were more familiar with Flow. The turning point was around 2019, when TypeScript started developing much faster, and Flow was essentially abandoned and we too decided that we should migrate to TypeScript at some point. Flow users will be faced with the following problems:

Undocumented features, that you can only know by diving into Facebook's codebase or Flow source code
Slow compilation process, that blows out your computer
Substantially weak support from the maintainers, regarding your issues and problems
Abandoned userland typing's for npm packages

This list can go on and on but within Y amount of time, we got the idea that we should transition into another superset of JavaScript. Well, if you ask me why, there are a few reasons, which can be divided into two subsections:

Company-specific reasons:

We already utilized TypeScript on the backend and have the required expertise and experience.
We already had contract-first backend programming. Where SDKs for different clients are automatically generated based on specification.
A significant part of our frontend is CRUD-like interfaces, based on backend API. Therefore, we want to use SDK for our frontends with strong typings.

Common sense-based reasons:

Great documentation, many tutorials, books, videos, and other stuff.
Weak type system. It is debatable because it's not like ML typesystem (Reason, Haskell, Ocaml), so it easily provides a clear understanding to people from any background.
Great adoption by the community, most of the packages you can imagine have great TypeScript support.

How has it started?

As far as I know, migration was started by adding tsconfig.json with:



{
  // ...
  "compilerOptions": {
    "allowJs": true
  }
}

This TypeScript flag allowed us to start adding ts and tsx files to our system.

Following this, we began to enable ts rules one after the one (the options below are just for example — choose those which fits to your codebase)

But we already had Flow, so let's fix it and add to .flowconfig



module.name_mapper.extension='ts' -> 'empty/object'
module.name_mapper.extension='tsx' -> 'empty/object'

Now, you are ready to start the migration. Let's go! Wait, it's that easy?

Where did we end up?

Due to a variety of reasons, we ended up hanging in limbo. We had plenty of files in Flow and in TypeScript. It took us several months to understand that it was not okay.

One of the main problems here is that we didn't have a plan as to which files we should start with, how much time and capacity it should take, and a combination of other organizational and engineering-based issues.

Another day, another try

After accepting the fact that the health of our codebase is not okay, we ultimately settled on trying again.

This is one more time when graphs save the day. Take a look at this picture:

Any codebase is no more than a graph. So, the idea is simple: start your migration from the leaves of the graph and move towards the top of the graph. In our case, it was styled components and redux layer logic.

Imagine you have sum function, which does not have any dependencies:



function sum(val1, val2) {
   return val1 + val2;
}

After converting to TypeScript, you get:



function sum(val1: number, val2: number) {
   return val1 + val2;
}

For example, if you have a simple component written in JavaScript when you convert that specific component, you immediately receive the benefits from TypeScript.



// imagine we continue the migration and convert the file form jsx to tsx
import React from 'react'

// PROFIT! Here's the error 
const MySimpleAdder = ({val1}) => <div>{sum("hey", "buddy")}</div>

// => Argument of type 'string' is not assignable to parameter of type 'number'.

So, let's create another picture but for your current project.

The first step is to install dependency-cruiser.

Use CLI



depcruise --init

Or add .dependency-cruiser.js config manually. I give you an example that I used for a high level overview of such migration.



module.exports = {
  forbidden: [],
  options: {
    doNotFollow: {
      path: 'node_modules',
      dependencyTypes: ['npm', 'npm-dev', 'npm-optional', 'npm-peer', 'npm-bundled', 'npm-no-pkg'],
    },
    exclude: {
      path: '^(coverage|src/img|src/scss|node_modules)',
      dynamic: true,
    },
    includeOnly: '^(src|bin)',
    tsPreCompilationDeps: true,
    tsConfig: {
      fileName: 'tsconfig.json',
    },
    webpackConfig: {
      fileName: 'webpack.config.js',
    },
    enhancedResolveOptions: {
      exportsFields: ['exports'],
      conditionNames: ['import', 'require', 'node', 'default'],
    },
    reporterOptions: {
      dot: {
        collapsePattern: 'node_modules/[^/]+',
        theme: {
          graph: {
            rankdir: 'TD',
          },
          modules: [
            ...modules,
          ],
        },
      },
      archi: {
        collapsePattern:
          '^(src/library|src/styles|src/env|src/helper|src/api|src/[^/]+/[^/]+)',
      },
    },
  },
};

Play with it — the tool has a lot of prepared presets and great documentation.

Tools

Flow to ts — helps to produce raw migration from Flow to TS files and reduces monkey job.
TS migrate — helps convert JS files to Typescript files. A great introduction can be found here.

Analyze and measure

This was not my idea but we came up with the idea of tracking the progress of our migration. In such situations, gamification works like a charm, as you can provide transparency to other teams and stakeholders, and it helps you in measuring the success of the migration.

Let's dive into technical aspects of this topic, we've just used manually updated excel table and bash script that calculates JavaScript/Typescript files count on every push to the main branch and posts the results to the Slack channel. Here's a basic sample, but you can configure it for your needs:



#!/bin/bash

REMOVED_JS_FILES=$(git diff --diff-filter=D --name-only HEAD^..HEAD -- '.js' '.jsx')

REMOVED_JS_FILES_COUNT=$(git diff --diff-filter=D --name-only HEAD^..HEAD -- '.js' '.jsx'| wc -l)

echo $REMOVED_JS_FILES

echo "${REMOVED_JS_FILES_COUNT//[[:blank:]]/}"

if [ "${REMOVED_JS_FILES_COUNT//[[:blank:]]/}" == "0" ]; then

echo "No js files removed"

exit 0;

fi

JS_FILES_WITHOUT_TESTS=$(find ./src  -name ".js" ! -wholename "tests" -print | wc -l)

JS_FILES_TESTS_ONLY=$(find ./src  -name ".js" -wholename "tests" -print | wc -l)

TOTAL_JS_FILES=$(find ./src  -name ".js" ! -wholename "*.snap" -print | wc -l)

JS_SUMMARY="Total js: ${TOTAL_JS_FILES//[[:blank:]]/}. ${JS_FILES_WITHOUT_TESTS//[[:blank:]]/} JS(X) files left (+${JS_FILES_TESTS_ONLY//[[:blank:]]/} tests files)"

PLOT_LINK="<excellink>"

echo $JS_SUMMARY

AUTHOR=$(git log -1 --pretty=format:'%an')

MESSAGE=":rocket: ULTIMATE KUDOS to :heart:$AUTHOR:heart: for removing Legacy JS Files from AGENT Repo: :clap::clap::clap:\n```$REMOVED_JS_FILES```"

echo $MESSAGE

echo $AUTHOR

SLACK_WEBHOOK_URL="YOUR_WEBHOOK_URL"

SLACK_CHANNEL="YOUR_SLACK_CHANNEL"

curl -X POST -H 'Content-type: application/json' --data "{\"text\":\"$MESSAGE\n$JS_SUMMARY\n\n$PLOT_LINK\",\"channel\":\"$SLACK_CHANNEL\"}" $SLACK_WEBHOOK_URL

Stop the bleeding of the codebase

Migration is a process; you can't do it in one day. People are fantastic, but at the same time, they have habits, they get tired, and so forth. That's why when you start a migration, people have inertia to do things the old way. So, you need to find a way to prevent the bleeding of your codebase when engineers continue to write JavaScript instead of Typescript. You can do so using automation tools. The first option is to write a script that checks that no new JavaScript files are being added to your codebase. The second one is to use the same idea as test coverage and use it for types.

There is a helpful tool that you can use for your needs.

Set up a threshold, add an npm script and you are ready to start:



"type-coverage": "typescript-coverage-report -s --threshold=88"

Results

Today, there is no Flow or JS code in our codebase, and we are pleased with our bet to use TypeScript, successfully migrating more than 200k files of JavaScript to TypeScript.

Feel free to ask questions, express any opinions or concerns, or discuss your point of view. Share, subscribe, and make code, not war. ❤️

If you'll find an error, I'll be glad to fix it or learn from you — just let me know.

If you want to work with me you can apply here, DM me on Twitter or LinkedIn.

High Level Overview of Compiler Design

Andrey Frolov — Sat, 16 Apr 2022 08:10:07 +0000

Intro

So you have 10 years’ experience with Senior JavaScript web3.0 steampunk software, you’re an entrepreneur, consulting star, and an engineer… but do you ever consider how your computer "reads", "interprets" and "executes" your program? Here's my attempt to make this crucial part of CS easy to understand.

I realize that I'm simplifying a bit and possibly making some inappropriate comparisons, but I'm just trying to give a mental model to myself and other people. Now the disclaimers are done, we can start digging into the rabbit hole, take my hand and let's fly!

High level overview

So, time for a very high level overview of compilers:

High level language — it can be a JavaScript, Python, C++, the name of your lovely language, etc. So, in a nutshell, it's just a string.

Compiler — based on the previous step, you already have in mind the idea that the compiler input is a string, and the result is assembly language. So, we can think about compilers as a simple function that just takes a string and produces another string.



Assembly code string = compiler(high level language string)

The last question is — what is assembly code?

Assembler — is like a manual for different operating systems; in other words, it's a set of instructions for a machine with some specific architecture (e.g. x86 architecture)

And here is our last move:

Machine code — actually just zeroes and ones

But you can mention that I place in the last block two pieces — Loader/Linker.

Just for your information, let's cover them a little bit.

A linker — is a program that combines the object files, generated by the compiler/assembler, and other bits of code to originate an executable file with an .exe extension. In the object file, the linker searches and append all libraries needed for the execution of files. It regulates the memory space that will hold the code from each module.

And the loader is a special program that takes an input of executable files from the linker, loads it to the main memory, and prepares this code to be executed by the computer. The loader allocates memory space to the program. Even it settles down symbolic reference between objects. It is in charge of loading programs and libraries in the operating system. The embedded computer systems don’t have loaders.

(I copied these two definitions from this site)

Deeper into the rabbit hole

So let's take another step and dig into compiler parts, which are much more interesting for us right now.

And another one image to explore:

Lexical analysis — removes whitespaces, useless symbols, and returns stream of tokens. For example:

Input string



SELECT * FROM "docs";

You can think about the stream as an iterator that you can pull for the next token. Here's some pseudocode:



Lexer.next() -> { kind: Keyword, type: "SELECT" }
Lexer.next() -> { kind: Asterisk  }
Lexer.next() -> { kind: Keyword, type: "FROM" }
Lexer.next() -> { kind: Char, value: "\"" }
Lexer.next() -> { kind: String, value: "docs" }
Lexer.next() -> { kind: Char, value: "\"" }

So the lexer represents valid characters from our language or alphabet.

To understand better, let's start parsing a simple string:



x = a + b * c;

So as humans, we can easily parse and understand such statements, but it's not so easy for the computer. We've already covered the purpose of the parser, and let's parse the above statement. Let's try to simplify this:



id = id + id * id

Where's id is an identifier, and if we try to represent it as an array, it can look something like this:



[
  { type: 'id', value: x },
  { type: 'symbol', value: '=' },
  { type: 'id', value: 'a' },
  { type: 'symbol', value: '+' }, 
  { type: 'id', value: 'b' },
  { type: 'symbol', value: '*' },
  { type: 'id', value: 'c' },
  { type: 'symbol', value: ';' },
]

Parser — uses context-free grammar (we will cover this definition in the next part) to create a parse tree.

There's no to be nervous, we're going to introduce a lot of complex definitions and terms, and if you find you're getting a bit lost, it's ok. We will cover everything related to parsing in the next chapters.

So, based on language grammar parser creates parse tree, which helps us find the right execution order of statement.

Let's take a look at an example of some grammar in BNF notation.



S ⭢ id = E
E ⭢ E + T
  |  T
T ⭢ T * F
  | F
F ⭢ id

Based on this grammar, we can build a parse tree:

Semantic analyzer — validates the parse tree to find grammar errors.

Intermediate code generator — produces three-address code

For example, it can look something like this:



t1 = b * c;
t2 = a + t1;
x = t2;

Code optimizer (CO) — optimizes three-address code.



t1 = b * c;
x = a + t1;

Target code generator — creates a code that the assembler can understand.

Some random pseudo architecture:



mul R1, R2
add R0, R2
mov R2, x

where a = R0, b = R1, c = R2

Feel free to ask questions, express any opinions or concerns, or discuss your point of view. Share, subscribe, and make code, not war. ❤️

If you'll find an error, I'll be glad to fix it or learn from you - just let me know.

You can DM me on Twitter or connect on LinkedIn. I'm always open to new connections, people, and opportunities.

OpenAPI spec (swagger) v2 vs v3

Andrey Frolov — Fri, 27 Aug 2021 06:54:40 +0000

It's just a compilation of other materials that I combined around the internet.

I've copied the image this from this article

Multiple Hosts

OpenAPI 2.0 allowed specifying a single host and basePath, and yet the schemes attribute allows specifying both http and https, therefore effectively enabling two hosts that only vary in the scheme. In the OpenAPI.vNext, the working branch of the spec repo, a new root level hosts object contains an array of objects that contain host, basePath, and scheme properties.

By structuring this as an array of objects, any number of root URLs for the API can be supported, and it allows for a clearer correlation of the scheme, host, and basePath properties. It also reduces the number of root level properties required, simplifying the document structure.

Additionally, the host, basePath, and scheme may be overriden at the path item level. This should make it easier to incorporate functionality provided on a separate host into an API description.

URL Structure

Currently, Swagger 2 lets you define schemes, a host and a baseUrl, which is combined into your URL. Now, you can have multiple URLs, and they can be defined anywhere—meaning you can have just one at the base like before, or a specific endpoint can have its own server if the base URL is different.

Additionally, path templating is now allowed. In OpenAPI 3, this was only allowed in the actual endpoint URLs. You define the templates with a variable property.

Swagger 2



info:
  title: Swagger Sample App
host: example.com
basePath: /v1
schemes: ['http', 'https']

OpenAPI 3



servers:
- url: https://{subdomain}.site.com/{version}
  description: The main prod server
  variables:
    subdomain:
      default: production
    version:
      enum:
        - v1
        - v2
      default: v2

There’s a few minor changes to path items, too. They now can accept a description. Also you can now give each path its own base URL (http://login.example.com, for example).

URL verbs

You’re no longer allowed to define a request body for GET and DELETE (which matches how RESTful APIs work). Lastly, there's support for TRACE.

Components

Swagger 2 had the concept of definitions, however they were somewhat arbitrary and weren’t as well-defined. OpenAPI 3 attempts to standardize the concept into components, which are definable objects that can be reused multiple places.

Open API spec 3.0 provides components object which can contain:

schemas
parameters
responses
examples
security schemes
links
request bodies
headers
callbacks

This component object won’t affect the API until it is referenced somewhere in the API.

Advantage : If multiple operations of an API needs similar input structure the the input structure can be defined under component as request bodies and can be reused in multiple paths. Similarly headers, responses and so on can be reused.



"components": {
  "schemas": {
    "Category": {
      "type": "object",
      "properties": {
        "id": {
          "type": "integer",
          "format": "int64"
        },
        "name": {
          "type": "string"
        }
      }
    },
    "Tag": {
      "type": "object",
      "properties": {
        "id": {
          "type": "integer",
          "format": "int64"
        },
        "name": {
          "type": "string"
        }
      }
    }
  },
  "parameters": {
    "skipParam": {
      "name": "skip",
      "in": "query",
      "description": "number of items to skip",
      "required": true,
      "schema": {
        "type": "integer",
        "format": "int32"
      }
    },
    "limitParam": {
      "name": "limit",
      "in": "query",
      "description": "max records to return",
      "required": true,
      "schema" : {
        "type": "integer",
        "format": "int32"
      }
    }
  },
  "responses": {
    "NotFound": {
      "description": "Entity not found."
    },
    "IllegalInput": {
      "description": "Illegal input for operation."
    },
    "GeneralError": {
      "description": "General Error",
      "content": {
        "application/json": {
          "schema": {
            "$ref": "#/components/schemas/GeneralError"
          }
        }
      }
    }
  }
}

Request format

One of the most confusing aspects of Swagger 2 was body/formData. They were a subset of parameters—you could only have one or the other—and if you went with body, the format was different than the rest of the parameters. (You could only have on body parameter, the name was irrelevant, the format was different, etc.)

Now, body has been moved into its own section called requestBody, and formData has been merged into it.

In addition, cookies has been added as a parameter type (in addition to the existing header, path and query options).

Swagger 2



"/pets/{petId}":
  post:
    parameters:
    - name: petId
      in: path
      description: ID of pet to update
      required: true
      type: string
    - name: user
      in: body
      description: user to add to the system
      required: true
      schema:
        type: array
        items:
          type: string

OpenAPI 3



"/pets/{petId}":
  post:
    requestBody:
      description: user to add to the system
      required: true
      content:
        application/json: 
          schema:
            type: array
            items:
              $ref: '#/components/schemas/Pet'
          examples:
            - name: Fluffy
              petType: Cat
            - http://example.com/pet.json
    parameters:
      - name: petId
        in: path
        description: ID of pet to update
        required: true
        type: string

The new requestBody supports different media types (content is an array of mimetypes, like application/json or text/plain, although you can use / as a catch-all).

For parameters, you have two options on how you want to define them. You can define a schema (like in 2.0), which lets you describe the item. Or, if it’s more complex, you can use content, which is the same as requestBody.

Request body content negotiation

The 3.0 release features a requestBody that supports content negotiation so that you can define different schemas and examples for various media types. The requestBody allows web services to accept and return data in different formats, such as images, plain text, XML, and JSON. It also allows you to provide one or multiple examples.

Examples

The requestBody has a lot of new features. You can now provide an example (or array of examples) for requestBody. This is pretty flexible (you can pass in a full example, a reference, or even a URL to the example).

Linking

Linking is one of the most interesting additions to OpenAPI 3. It’s a bit complicated, but potentially incredibly powerful. It’s basically a way of describing “what’s next”. (For people familiar, it's in the same vein as HATEOAS / Hypermedia APIs.)

Let’s say you get a user, and it has an addressId. This addressId is pretty useless by itself. You can use links to show how to “expand” that, and get the full address.



paths:
  /users/{userId}:
    get:
      responses:
        200:
          links:
            address:
              operationId: getAddressWithAddressId
              parameters:
                addressId: '$response.body#/addressId'

See what’s happening there? In the response from /users/{userId}, we get back an addressId. The links describes how we can get an address by referencing the $response.body#/addressId.

Another usecase is pagination. If you fetch 100 results, links can show how to get results 101-200. It’s flexible, which means it can handle any pagination scheme from limits to cursors.

To this end, the 3.0 draft specification introduces the links object in order to describe which new resources may be accessed based on the information retrieved from an initial resource. This is not necessarily hypermedia-driven in that, the URLs to the new resources have not been embedded in the returned payload, but they are constructed based on rules defined in OpenAPI Specification. A new expression syntax has been introduced to allow information from a response to be correlated with parameters in the linked operation.

Security

A bunch of changes to security! It’s been renamed, OAuth2 flow names have been updated, you can have multiple flows, and there’s support for OpenID Connect. The basic type has been renamed to http, and now security can have a scheme and a bearerFormat.

Swagger 2



securityDefinitions:
  UserSecurity:
    type: basic
  APIKey:
    type: apiKey
    name: Authorization
    in: header
security:
  - UserSecurity: []
  - APIKey: []

OpenAPI 3



components:
  securitySchemes:
    UserSecurity:
      type: http
      scheme: basic
    APIKey:
      type: http
      scheme: bearer
      bearerFormat: TOKEN
security:
  - UserSecurity: []
  - APIKey: []

Callbacks

Webhooks leverage HTTP in an publish/subscribe pattern, and they have become a popular pattern among API providers, including Slack, GitHub, and many other popular services. Webhooks are simple to use and fit nicely into an existing HTTP-based style of API. However, one criticism of the OpenAPI spec was that it had no way to describe an outbound HTTP request and its expected response. The new callback object makes this possible. A callback object can be attached to a subscribe operation in order to describe an outbound operation that a subscriber may expect.

JSON Schema

A number of requests were made to expand the subset of JSON Schema that the OpenAPI spec allows to include more complex features of JSON Schema. In the 2.0 spec process, the potential tooling complexities around code generation prompted the exclusion of anyOf and oneOf. However, many users have requested relaxing that constraint, even though it would compromise tooling support for those features. This is one of the great challenges in spec design, and it is never easy when making choices like this to know whether it is better to give people sharp tools that they could cut themselves with, or to rely on experience to say no, the burden of this responsibility is too great. While OpenAPI 2.0 took the more conservative approach, the user base has grown more experienced, so some of the restrictions are being lifted, and users will have to make smart choices.

Type Can Now Be An Array

In previous versions of OpenAPI, type could only be a single string. But in JSON Schema, type can be an array of strings. There is no workaround for this in version 2.0, but in version 3.0, you can select multiple types using oneOf:



oneOf:
  - type: string
  - type: integer

With OpenAPI 3.1, the specification now supports type as an array:



type: [string, integer]

Nullable is No More

Neither OpenAPI 2.0 nor 3.0 support null as a type, but JSON Schema does support type null. OpenAPI 3.0 includes the field name nullable, which you can set to true if you want the value to be null:



type: string
nullable: true

However, support for type null has been added in version 3.1, and nullable has been removed.



type: [string, "null"]

Links that was used for an article

Why automation releases tools is great bullshit for your end-users

Andrey Frolov — Tue, 17 Aug 2021 13:35:50 +0000

There are a bunch of tools that take your commits and converts them into release, like semantic-release. There's nothing wrong with the tools and their authors literally. It's fantastic tools that are mostly used the wrong way.

In a nutshell, the idea of any of these tools is pretty basic. They take your commits and generate releases base on your git history.

But take a breath before adding such a solution into your daily project workflow. Firstly ask yourself, do I write my git messages for end-users describing the motivation and changes of public API, or am I just putting internal stuff there?

So, the main idea of this post is if you don't write releases by yourself, you don't care about the end-users; you don't help them; you just add a fancy tool for yourself, nothing more.

Compile a first program

Andrey Frolov — Tue, 10 Aug 2021 14:55:45 +0000

1) Create a file sum.ml

2) Write this code

open Base
open Stdio

let rec read_and_accumulate accum =
  let line = In_channel.input_line In_channel.stdin in
  match line with
  | None -> accum
  | Some x -> read_and_accumulate (accum +. Float.of_string x)

let () =
  printf "Total: %F\n" (read_and_accumulate 0.)

3) create dune file

(executable
 (name      sum)
 (libraries base stdio))

4) install Stdio

opam install Stdio

5) Use dune to build the binary

dune build sum.ml

6) Execute the program type some number and hit CTRL+d

./_build/default/sum.exe

Moving on Data structures

Andrey Frolov — Tue, 10 Aug 2021 14:40:58 +0000

Lists

Lists are immutable. Lists let you hold any number of items of the same type.

let l = ["i"; "am"; "list"];;

Tuples

A tuple is an ordered collection of values that can each be of a different type. You can create a tuple by joining values together with a comma.

let a_tuple = (3,"three") ;;
val a_tuple : int * string = (3, "three")
let another_tuple = (3,"four",5.) ;;
val another_tuple : int * string * float = (3, "four", 5.)

Destructuring of a tuple

let (x,y) = a_tuple ;;

(**val x : int = 3
  val y : string = "three" *)

Adding elements in front of list

"French" :: "Spanish" :: languages ;;
(** - : string list = ["French"; "Spanish"; "OCaml"; "Perl"; "C"] *)

Concatenation of two lists

[1;2;3] @ [4;5;6] ;;
(** - : int list = [1; 2; 3; 4; 5; 6] *)

Records

type point2d = { x : float; y : float }

Destructuring of the record

let magnitude { x = x_pos; y = y_pos } =
Float.sqrt (x_pos **. 2. +. y_pos **. 2.)
;;
(* val magnitude : point2d -> float = <fun> *)

Composing records

type circle_desc  = { center: point2d; radius: float }
type rect_desc    = { lower_left: point2d; width: float; height: float }
type segment_desc = { endpoint1: point2d; endpoint2: point2d }

Variant types

type scene_element =
  | Circle  of circle_desc
  | Rect    of rect_desc
  | Segment of segment_desc

Arrays

The mutable guy.

let numbers = [| 1; 2; 3; 4 |] ;;
(* val numbers : int array = [|1; 2; 3; 4|] *)

numbers.(2) <- 4 ;;
(* - : unit = () )*
numbers ;;

(* - : int array = [|1; 2; 4; 4|] *)

The .(i) syntax is used to refer to an element of an array, and the <- syntax is for modification. Because the elements of the array are counted starting at zero, element .(2) is the third element.

What is Unit? Unit it's just a placeholder similar to void in other more mainstream languages

Mutable records

Records, which are immutable by default, can have some of their fields explicitly declared as mutable. Here’s an example of a mutable data structure for storing a running statistical summary of a collection of numbers.

type running_sum =
  { mutable sum: float;
    mutable sum_sq: float; (* sum of squares *)
    mutable samples: int;
  }

Let's write some imperative stuff

let mean rsum = rsum.sum /. Float.of_int rsum.samples
let stdev rsum =
  Float.sqrt (rsum.sum_sq /. Float.of_int rsum.samples
-. (rsum.sum /. Float.of_int rsum.samples) **. 2.)
;;
(* val mean : running_sum -> float = <fun> *)
(* val stdev : running_sum -> float = <fun> *)

let create () = { sum = 0.; sum_sq = 0.; samples = 0 }
let update rsum x =
  rsum.samples <- rsum.samples + 1;
  rsum.sum     <- rsum.sum     +. x;
  rsum.sum_sq  <- rsum.sum_sq  +. x *. x
;;
(* val create : unit -> running_sum = <fun> *)
(* val update : running_sum -> float -> unit = <fun> *)

Take a look into semicolons to sequence operations. When you are working purely functionally, this wasn’t necessary, but you start needing it when you’re writing imperative code.

let rsum = create () ;;
val rsum : running_sum = {sum = 0.; sum_sq = 0.; samples = 0}
List.iter [1.;3.;2.;-7.;4.;5.] ~f:(fun x -> update rsum x) ;;
(* - : unit = () *)
mean rsum ;;
(* - : float = 1.33333333333333326 *)
stdev rsum ;;
(* - : float = 3.94405318873307698 *)

Refs

Ref is a single mutable variable (hi ma react boys)

let x = { contents = 0 } ;;
val x : int ref = {contents = 0}
x.contents <- x.contents + 1 ;;
- : unit = ()
x ;;
- : int ref = {contents = 1}

Some syntactic sugar for ref

let x = ref 0  (* create a ref, i.e., { contents = 0 } *) ;;
(* val x : int ref = {Base.Ref.contents = 0} *)
!x             (* get the contents of a ref, i.e., x.contents *) ;;
(* - : int = 0 *)
x := !x + 1    (* assignment, i.e., x.contents <- ... *) ;;
(* - : unit = () *)
!x ;;
(* - : int = 1 *)

Nothing magic here, let's implement the ref by ourselves

type 'a ref = { mutable contents : 'a } ;;
type 'a ref = { mutable contents : 'a; }
let ref x = { contents = x } ;;
(* val ref : 'a -> 'a ref = <fun> *)
let (!) r = r.contents ;;
(* val ( ! ) : 'a ref -> 'a = <fun> *)
let (:=) r x = r.contents <- x ;;
(* val ( := ) : 'a ref -> 'a -> unit = <fun> *)

Few words about functions

Andrey Frolov — Tue, 10 Aug 2021 14:40:41 +0000

It's a real big topic but for now let's watch in action basic function declaration

let sum x = function y -> x + y;;

(** just a sum function that has next type *)
(** val sum : int -> int -> int = <fun> *)

How to read such notation
means the type - it's a function
last int before = means return value of function
previous int's means arguments

Let's watch something more complex

Compose function accepts f and g functions and accepts value (x) on which functions should be applied

let compose f g = function x -> f (g x);;

Let's take a glance into high order functions (functional)

Take a look

List.map (function n -> n * 2 + 1) [0;1;2;3;4];;

(** : int list = [1; 3; 5; 7; 9] *)

Recursive functions

let rec sum l =
  match l with
  | [] -> 0                   (* base case *)
  | hd :: tl -> hd + sum tl   (* inductive case *)
;;
val sum : int list -> int = <fun>
sum [1;2;3] ;;
(* - : int = 6 *)

Logically, you can think of the evaluation of a simple recursive function like sum almost as if it were a mathematical equation whose meaning you were unfolding step by step:

sum [1;2;3]
= 1 + sum [2;3]
= 1 + (2 + sum [3])
= 1 + (2 + (3 + sum []))
= 1 + (2 + (3 + 0))
= 1 + (2 + 3)
= 1 + 5
= 6

Variables

Andrey Frolov — Tue, 10 Aug 2021 13:31:56 +0000

It's an expression and ;; says to ocaml treats this line as expression

3 + 4 ;;

And heres variable declaration or let binding

let x = 3 + 4 ;;
(** val x : int = 7 *)

After a new variable is created, the toplevel tells us the name of the variable (x), in addition to its type (int) and value (7).

Also with let you can define a function

let square x = x * x ;;

(** val square : int -> int = <fun> *)

square (square 2) ;;

(** - : int = 16 *)

Function in ocaml is a first class citizen.

Note: ;; is required only in repl, not in your source code.

Installation of utop

Andrey Frolov — Tue, 10 Aug 2021 13:18:11 +0000

Install some of required libraries for next sections

Utop - is an easier-to-use version of OCaml’s standard toplevel (which you can start by typing ocaml at the command line).



opam install base utop

Remark on this from real world ocaml

Write utop in terminal and here we go!



utop

Look into base types

Andrey Frolov — Mon, 09 Aug 2021 15:40:26 +0000

So nothing special here

There are bunch of data types:

floats

Numbers with a floating point

1.1
1.2

ints

300_000
1

OCaml as ruby, elixir does, allow you to place underscores in the middle of numeric literals to improve readability. Note that underscores can be placed anywhere within a number, not just every three digits.

booleans

(1 < 2) = false;;

chars

"a";;

strings (immutable)

"Hello";;

First steps - installation of Ocaml

Andrey Frolov — Mon, 09 Aug 2021 15:29:12 +0000

Installation of package manager

brew install gpatch
brew install opam

Installation of Ocaml

# environment setup
opam init
# put the shel in the right step
eval $(opam env)
# install given version of the compiler
opam switch create 4.12.0
eval $(opam env)
# check you got what you want
which ocaml
ocaml -version

So now you can start a repl and play around it

ocaml

let rec fib n =
    if n < 2 then n else fib (n - 1) + fib (n - 2);;

How to solve problems with opam?

On Linux and macOS, this will be the ~/.opam directory, which means you don't need administrative privileges to configure it. If you run into problems configuring opam, just delete the whole ~/.opam directory and start over.