Forem: Vitor

How to create your own Eslint rule with tests, boosting the DX, and code-review

Vitor — Wed, 27 Mar 2024 18:40:00 +0000

Code review is an essential step in every good software development process. At this step, your team can learn, discuss, and detect problems related to code or business logic. A good code review requires attention to detail from the reviewer, and this is where I started to think more about DX (Developer Experience) and how to improve the code review to focus on what matters.

Focus on what matters

I want to remove as many noises as possible during the development process and code review, allowing the developer to focus on what matters. One of the ways to do it is to create a good set of lint rules for your project. It can force a specific code pattern, organize the code, and remove the responsibility from the developer to keep things clear.

Having a team with a good sense of ownership that works on refactoring and improving the DX is crucial.

For each repetitive mistake during the code review should have a pull-request similar to this one:

How to create your own Eslint rule

Setup the project

You can start by creating a new folder containing your eslint package and another project to test your eslint package.

~ mkdir my-eslint-rule
~ cd my-eslint-rule
~ mkdir package
~ cd package

Inside the package folder, start a npm project

npm init

The project's name should contain the prefix eslint-plugin, like eslint-plugin-my-custom-rule.

Creating the rule

The rule should detect the code we want to transform, show an error or alert about the problem, and be auto-fixable.

The rule I'll create for this tutorial will look for console.log calls and refactor it to console.info().

const moveConsoleLogToInfo = (context) => {
  return {
    CallExpression: (node) => {
      if (
        node.callee.type === "MemberExpression" &&
        node.callee.object.name === "console" &&
        node.callee.property.name === "log"
      ) {
        context.report({
          node,
          message: "Use console.info instead of console.log",
        });
      }
    },
  };
};

module.exports = { moveConsoleLogToInfo };

To understand this syntax, I recommend exploring AST Explorer. You will have a better view of how the AST of JavaScript works and how to correlate it with the Eslint syntax:

And then, we can import it into our index.js file.

const { moveConsoleLogToInfo } = require("./move-console-log-to-info");

module.exports = {
  rules: {
    "move-console-log-to-info": {
      create: moveConsoleLogToInfo,
    },
  },
};

At this point, we're ready to install our new eslint rule on our test project.

Outside the package folder, initiate another npm project.

npm init

To install our package, we can tell NPM the package directory. In our case, it will be:

npm install --save-dev ./package

And now you can see your package in package.json:

And then, install lint:

npm install -D eslint

Create .eslintrc.js:

module.exports = {
  env: {
    node: true,
  },
  parserOptions: {
    ecmaVersion: 2018,
    sourceType: "module",
  },
  extends: ["eslint:recommended"],
  plugins: ["my-custom-rule"],
  rules: {
    "my-custom-rule/move-console-log-to-info": "error"
  },
};

Back to your test file, and type console.log to see the magic:

But our rule cannot be fixed by itself. Let's make it possible.

Fixable rule

First, back to package/index.js:

const { moveConsoleLogToInfo } = require("./move-console-log-to-info");

module.exports = {
  rules: {
    "move-console-log-to-info": {
      defaultOptions: [],
      meta: {
        type: "problem",
        messages: {
          defaultMessage: "Move console.log to logger.info",
        },
        fixable: "code",
        schema: [],
      },
      create: moveConsoleLogToInfo,
    },
  },
};

and move-console-log-to-info.js:

const moveConsoleLogToInfo = (context) => {
  return {
    CallExpression: (node) => {
      if (
        node.callee.type === "MemberExpression" &&
        node.callee.object.name === "console" &&
        node.callee.property.name === "log"
      ) {
        context.report({
          node,
          message: "Use console.info instead of console.log",
          fix: (fixer) => fixer.replaceText(node.callee.property, "info"),
        });
      }
    },
  };
};

module.exports = { moveConsoleLogToInfo };

Now, install the package again and restart the eslint server:

And it will keep the content inside the log()

How to create tests

Having tests for your rule will help ensure that your package does not introduce any regression. We'll use Eslint and Jest for this.

Eslint provides RuleTester and Jest because it runs without additional configuration and works well with valid and invalid RuleTester syntax.

Test folder

I won't discuss the folder architecture you'll use to organize your tests. You can check out how I organized a real-world Eslint rule here.

You must follow the name file pattern name.spec.js because Jest will look for .spec files.

// move-console-log-to-info.spec.js


const { RuleTester } = require("eslint");
const { rules } = require("../index");

const ruleTester = new RuleTester({ parserOptions: { ecmaVersion: 2015 } });

ruleTester.run("move-console-log-to-info", rules["move-console-log-to-info"], {
  valid: [
    {
      code: 'console.info("My own Eslint rule is working!")',
    },
  ],
  invalid: [
    {
      code: 'console.log("My own Eslint rule is working!")',
      errors: [
        {
          message: "Use console.info instead of console.log",
          type: "CallExpression",
        },
      ],
      output: 'console.info("My own Eslint rule is working!")',
    },
  ],
});

Conclusion

Now you understand why it's important to care about DX, how to use Eslint to make developers focus on what matters with a custom Eslint rule, and how to create automated tests to ensure your rule keeps working well.

If you liked what you saw today, please react to this post and do not forget to follow me on my socials:

X(Formerly Twitter)
Linkedin

References

The Art of Understanding Before Coding

Vitor — Tue, 29 Aug 2023 13:31:45 +0000

Some developers when receives a task starts thinking about implementing the requirements, whether it will be complicated or not, the piece of the code to be refactored, or something like that. You shouldn't think about code before understanding your business.

Split

If you're this developer, I suggest splitting the process of understanding and organizing the task to implement the requirements.

It does not make sense to start doing something you don't understand. If you need to know if you understand something, an excellent way is to write about it or draw the task - using Excalidraw, for example. This process will force you to understand the task, think about problems, and help you ask the right questions. Some questions that would be nice to ask yourself, for example:

For features

Why is this feature important?
- What kind of problem this feature is solving?
Who needs this feature?

For bugs

Conflict the wrong and proper behavior;
Think about what logs are saying;
Understand the nature of the bug
- Does it happen during some specific flow?
- Does it happen for a wrong implemented business logic?
- Can you reproduce it?
If it is from a ticket, what is the customer reporting?

If you think that you understand it, try to draw it. Something like this:

(image from researchgate)

Code

Now that you think about the problem, you can start to think about the implementation. If you are doing it well, you will believe that the code is the more uncomplicated part of the process. And the crucial is to understand what to code.

With it, you can reduce the scope of code debugging and start to visualize your app in chunks instead of wasting time writing or reading something unrelated to your task.

You will probably write less code and deliver your job faster and with more quality. Also, you will improve your knowledge about the business and the code and will be more efficient in helping others in your team.

Conclusion

Ultimately, the deal is that you understand that you would split your task into steps and start by really understanding what and why you are doing.

Don't worry about time. This process can take some time, but the deal is always to try to understand what you are doing.

Banner from unsplash

Is Data Struct about memory?

Vitor — Sun, 27 Aug 2023 19:41:36 +0000

A principle that I try to follow is to think about obvious concepts. Since we are introduced to society, we meet with a lot of concepts that we don't even question. Some authoritary figure like a teacher or a parent tells us things that we just accept.

If you think about data structure, you can relate it immediately to memory. Today, I want to discuss why data structures are not only about memory.

Introduction

For instance, let’s understand that we do not have any problem thinking about data structures to organize data in memory. The problem is never the idea that data structures are indifferent to implementation.

Data Structure is a way to organize, manage, and store data (yes, you can store things in math. If you think about matrices or sets, you can notice that is a way to organize data. In practice, store things is about to organize things). It is a collection of values that we can realize operations. In essence, it is an Algebraic Structure of data.

Algebraic Structure

An algebraic Structure is a set of elements with one or more operations that satisfy some specific properties (axioms). An example is Boolean Algebra, a set with two binary operations, union and intersection. You can follow this link to understand more about Boolean Algebra.

At this point, I want to highlight that algebraic structures are essentially about math. It describes the properties of a set of elements: a group, a ring, an algebra, etc. If you want to dive into this topic, read Algebraic Structures.

It is a big mistake to take an abstract and mathematical concept and reduce it to a simple implementation that needs physical and limited resources. You do not need any computer or memory to understand or use data structures. You need data. And data in math is just a set of elements.

Let's to think about computational models

The root of this problem is that you maybe don't know about computational models. It is a important step because if you think that in computer science we are using math to model computational problems, and computational problems are mathematical problems, you probably never will reduce any computational problem to a phisical and limited resource (like memory).

Computer science problems follow math problems, and we use math to model them. It means that the problem that you're trying to solve, can be modeled by a mathematical problem before you start to think about some computational implementation.

Conclusion

I hope that you understand that data structures are not only about memory. It is a mathematical concept that we use to model computational problems.

This text is a little talk about some ideas that I would like to share. I tried to give some references to help if you want to dive into this topic. Also, it's very important to think about obvious concepts and try to understand why the things are the way they are.

Proving natural numbers are infinity in Coq 🧙🏼

Vitor — Fri, 18 Aug 2023 20:38:11 +0000

Introduction

An interesting fact about math is that you can demonstrate things. A lot of people thinks that demonstrate is exemplify something, but it is not. It's common to see people saying that 1 + 1 = 2, just like one apple plus one apple is two apples. But, this is not a demonstration. A demonstration is a logical proof that something is true, by a formal way. You cannot say that every 1 plus itself is equal to two. Boolean algebra is a good example of this. In Boolean algebra, 1 + 1 = 1. So, you can't say that aways 1 + 1 = 2.

What is Coq?

Coq is a software that allows you to write proofs. It is a proof assistant based on the calculus of inductive constructions. It is a functional programming language based on lambda calculus. I won't talk about lambda calculus and the calculus of inductive constructions, but you can find more information about them on Wikipedia.

What is a formal proof?

A formal proof is a process based on logical rules and axioms used to demonstrate some theorem. The goal is to show an absolute truth that some affirmation is faithful by following strict rules.

The proof

A simple way to prove that natural numbers are infinite is by defining that given a natural number (n: nat), n + 1 will return natural numbers greater than n.

You need to make it because this theorem proves that natural numbers are infinite by showing that given any natural numbers, you can always find a natural number greater than it, by summing $1$ to it.

So, lets to define our theorem in Coq:

Theorem plus_1_natural : forall n : nat, 1 + n = S n /\ S n > n.

The forall keyword means the theorem is valid for all natural numbers. The /\ means the theorem is a conjunction, and the S is the successor function. So, the theorem says that given a natural number n, 1 + n is equal to S n, and S n is greater than n.

Lets to prove the theorem:

Proof.
  intros n.
  split.
  - reflexivity.
  - apply le_n_S. apply le_n.
Qed.

intros n introduces the universal quantifier forall and the arbitrary natural number $n$ as a variable. The split. splits the objective into two subgoals. One for each conjunct /\. The hyphen is to refer to the subgoal. The reflexivity. is to prove that something equals to itself. Like 1 + n = S n, because 1 + n is equal to S n. You can reduce it, like:

1 + 1 = 2.
2 = 2.

Coq have some macros that abstracts some proofs. We can see this reducing using simpl.:

Coq gives us some theorems related to natural numbers ordering, like le_n_S and le_n. These theorems can be used to reduce steps of our proof, replacing them with the applied theorem. In math, the le it is $\leq$, less than or equal.

le_n any natural number is less than or equal to itself. n <= n is a true statement for any natural number n.
le_n_S says that if n <= m, then S n <= S m. So, if n <= n, then S n <= S n.

The apply le_n_S. definition is le_n_S : forall n m : nat, n <= m -> S n <= S m, and le_n that le_n : forall n : nat, n <= n. So, to read the apply le_n_S. apply le_n. is: "Given a natural number n, if n <= n, then S n <= S n". And this is true, because n <= n is true, and S n <= S n is true too. So, the theorem is proved. Qed. means that the proof is finished.

You can also see it on CoqIDE:

Conclusion

You can also show the output of the proof and run the proof. So, lets do it.

You can use Print to show the definition of some theorem, and Eval compute in to run the proof. In the end, our proof will be:

Theorem plus_1_natural : forall n : nat, 1 + n = S n /\ S n > n.
Proof.
  intros n.
  split.
  - reflexivity.
  - apply le_n_S. apply le_n.
Qed.
Print plus_1_natural.
Eval compute in (plus_1_natural 1).

And the output will be:

plus_1_natural = fun n : nat => conj eq_refl (le_n_S n n (le_n n))
: forall n : nat, 1 + n = S n /\ S n > n

= plus_1_natural 1
: 1 + 1 = 2 /\ 2 > 1

This text is a copy paste of the text from my own blog. Please, check it here

Building a JSON Parser from scratch with JS 🤯

Vitor — Tue, 01 Aug 2023 13:59:16 +0000

Introduction

A parser can have various applications in everyday life, and you probably use some parser daily. Babel, webpack, eslint, prettier, and jscodeshift. All of them, behind the scenes, run a parser that manipulates an Abstract Syntax Tree (AST) to do what you need - we'll talk about that later, don't worry.

The idea of this text is to introduce the concept of lexing and parsing, implementing them using JavaScript to analyze expressions in JSON. The goal will be to separate this process into functions, explain these functions, and, in the end, have you implement a JSON parser generating an AST.

It's worth noting that my repository is open, and you can access it here.

Lexing

A lexer will be responsible for converting an expression, whatever it may be, into tokens. These tokens are identifiable elements that have an assigned meaning.

You can divide these tokens in several ways, such as identifier, keyword, delimiter, operator, literal, and comment.

{ "type": "LEFT_BRACE", "value": undefined } is an example of a delimiter. { "type": "STRING", "value": "name" } is an example of a literal.

Example: {"name":"Vitor","age":18}



[
  { "type": "LEFT_BRACE", "value": undefined },
  { "type": "STRING", "value": "name" },
  { "type": "COLON", "value": undefined },
  { "type": "STRING", "value": "Vitor" },
  { "type": "COMMA", "value": undefined },
  { "type": "STRING", "value": "age" },
  { "type": "COLON", "value": undefined },
  { "type": "NUMBER", "value": "18" },
  { "type": "RIGHT_BRACE", "value": undefined }
]

Note that in lexical analysis, you separate your expression into tokens, and each token has its identification.

To code this, let's first understand what we will be doing exactly. The idea of the lexer function is to receive an argument of type String and return an Array of tokens, which will be our JSON divided into specific types of information, as we have already seen and discussed.

To achieve this, we will create a variable called current, which will store the current position of the character in the input being analyzed by the lexer. In other words, it represents the position it is currently at in our JSON. Additionally, we will have a constant called tokens, which will be an array that will hold all of our tokens in the end.



export const lexer = (input: string): Token[] => {
let current = 0;
const tokens: Token:[] = [];


}

Now, we need to run a loop that will iterate until all the characters of the input have been processed.

Note that it's possible to refactor all these if blocks into a switch statement. However, I followed an imperative style.



export const lexer = (input: string): Token[] => {
  let current = 0
  const tokens: Token[] = []


  while (current < input.length) {
    let char = input[current]


    if (char === '{') {
      tokens.push(createToken(TOKEN_TYPES.LEFT_BRACE))
      current++
      continue
    }


    if (char === '}') {
      tokens.push(createToken(TOKEN_TYPES.RIGHT_BRACE))
      current++
      continue
    }


    if (char === '[') {
      tokens.push(createToken(TOKEN_TYPES.LEFT_BRACKET))
      current++
      continue
    }


    if (char === ']') {
      tokens.push(createToken(TOKEN_TYPES.RIGHT_BRACKET))
      current++
      continue
    }


    if (char === ':') {
      tokens.push(createToken(TOKEN_TYPES.COLON))
      current++
      continue
    }


    if (char === ',') {
      tokens.push(createToken(TOKEN_TYPES.COMMA))
      current++
      continue
    }


    const WHITESPACE = /\s/


    if (WHITESPACE.test(char)) {
      current++
      continue
    }


    const NUMBERS = /[0-9]/
    if (NUMBERS.test(char)) {
      let value = ''
      while (NUMBERS.test(char)) {
        value += char


        char = input[++current]
      }
      tokens.push(createToken(TOKEN_TYPES.NUMBER, value))
      continue
    }


    if (char === '"') {
      let value = ''
      char = input[++current]
      while (char !== '"') {
        value += char
        char = input[++current]
      }
      char = input[++current]
      tokens.push(createToken(TOKEN_TYPES.STRING, value))
      continue
    }


    if (
      char === 't' &&
      input[current + 1] === 'r' &&
      input[current + 2] === 'u' &&
      input[current + 3] === 'e'
    ) {
      tokens.push(createToken(TOKEN_TYPES.TRUE))
      current += 4
      continue
    }


    if (
      char === 'f' &&
      input[current + 1] === 'a' &&
      input[current + 2] === 'l' &&
      input[current + 3] === 's' &&
      input[current + 4] === 'e'
    ) {
      tokens.push(createToken(TOKEN_TYPES.FALSE))
      current += 5
      continue
    }


    if (
      char === 'n' &&
      input[current + 1] === 'u' &&
      input[current + 2] === 'l' &&
      input[current + 3] === 'l'
    ) {
      tokens.push(createToken(TOKEN_TYPES.NULL))
      current += 4
      continue
    }


    throw new TypeError('I dont know what this character is: ' + char)
  }


  return tokens
}

This code may seem complicated, but it's actually quite simple. Inside my loop, I start by defining the variable char, which will store the character currently being analyzed in that iteration of the loop. Then, for each type of character, we want a specific action.

If the char is equal to {, we push into the tokens array, passing to it the ENUM of Tokens, which will be the name of each token.



export enum TOKEN_TYPES {
  LEFT_BRACE = 'LEFT_BRACE',
  RIGHT_BRACE = 'RIGHT_BRACE',
  LEFT_BRACKET = 'LEFT_BRACKET',
  RIGHT_BRACKET = 'RIGHT_BRACKET',
  COLON = 'COLON',
  COMMA = 'COMMA',
  STRING = 'STRING',
  NUMBER = 'NUMBER',
  TRUE = 'TRUE',
  FALSE = 'FALSE',
  NULL = 'NULL',
}

In the function createToken, it only returns an object with the type or value if it exists.



export const createToken = (type: TOKEN_TYPES, value?: string): Token => {
  return {
    type,
    value,
  }
}

After that, it increments +1 to the current variable to move to the next char in our string. This process is quite repetitive and straightforward. I won't explain each one of them, but it's worth paying attention to those that deviate a bit from the pattern.



if (char === '"') {
  let value = ''
  char = input[++current]
  while (char !== '"') {
    value += char
    char = input[++current]
  }


  char = input[++current]
  tokens.push(createToken(TOKEN_TYPES.STRING, value))
  continue
}


if (
  char === 't' &&
  input[current + 1] === 'r' &&
  input[current + 2] === 'u' &&
  input[current + 3] === 'e'
) {
  tokens.push(createToken(TOKEN_TYPES.TRUE))
  current += 4
  continue
}


if (
  char === 'f' &&
  input[current + 1] === 'a' &&
  input[current + 2] === 'l' &&
  input[current + 3] === 's' &&
  input[current + 4] === 'e'
) {
  tokens.push(createToken(TOKEN_TYPES.FALSE))
  current += 5
  continue
}


if (
  char === 'n' &&
  input[current + 1] === 'u' &&
  input[current + 2] === 'l' &&
  input[current + 3] === 'l'
) {
  tokens.push(createToken(TOKEN_TYPES.NULL))
  current += 4
  continue
}

If the char is equal to ", we enter a loop to continue reading the subsequent characters until we find another quotation mark, as this indicates the end of the string. All the characters read during this loop are concatenated into the "value" variable. Then, a new token is added to the "tokens" array.

The other lines are used to set boolean values. If the current character is "f" and the subsequent characters form the word false, we add false to the tokens array. The same process is repeated for true.

In all cases, the current variable is incremented to point to the next character to be processed, just like we did throughout the rest of our code.

Parsing

A parser is responsible for transforming a sequence of tokens into a data structure, in this case, an AST.

Illustration of an AST taken from the book "Modern Compiler Implementation in ML."

An Abstract Syntax Tree (AST) is a data structure that represents the syntactic structure of a program. Within the AST, there are several nodes, and each node represents a valid syntactic construct of the program. For example:



parser: {
  "type": "Program",
  "body": [
    {
      "type": "ObjectExpression",
      "properties": [
        {
          "type": "Property",
          "key": {
            "type": "STRING",
            "value": "name"
          },
          "value": {
            "type": "StringLiteral",
            "value": "Vitor"
          }
        },
        {
          "type": "Property",
          "key": {
            "type": "STRING",
            "value": "age"
          },
          "value": {
            "type": "NumberLiteral",
            "value": "18"
          }
        }
      ]
    }
  ]
}

This is the AST of the JSON I exemplified at the beginning. In this example, we have a total of 8 nodes. The Program node represents the main program. ObjectExpression represents an object, Property represents a property within an object, consisting of a key and a value. STRING represents a string used as a key, StringLiteral represents a string within a property, and NumberLiteral represents a numeric value within a property.

Through an AST, it's possible to optimize code, transform one code into another, perform static analysis, generate code, and more. For example, you could implement a new syntax, create a parser, and generate JavaScript code that would execute normally.

To generate our AST, we will need a function that receives our array of tokens, iterates through it, and generates the AST according to the tokens it encounters. For this purpose, we will create a function called walk, which will traverse the tokens and return the nodes of the AST.



export const parser = (tokens: Array<{ type: string; value?: any }>) => {
    let current = 0;


    const walk = () => {
        let token = tokens[current];


        if (token.type === TOKEN_TYPES.LEFT_BRACE) {
            token = tokens[++current];


            const node: {
                type: string;
                properties?: Array<{ type: string; key: any; value: any }>;
            } = {
                type: 'ObjectExpression',
                properties: [],
            };


            while (token.type !== TOKEN_TYPES.RIGHT_BRACE) {
                const property: { type: string; key: any; value: any } = {
                    type: 'Property',
                    key: token,
                    value: null,
                };


                token = tokens[++current];


                token = tokens[++current];
                property.value = walk();
                node.properties.push(property);


                token = tokens[current];
                if (token.type === TOKEN_TYPES.COMMA) {
                    token = tokens[++current];
                }
            }


            current++;
            return node;
        }

The first check we perform is whether the current token is {. If it is, we create a new node of type ObjectExpression and iterate through the following tokens, adding them as properties of the object until we find the end of the key, which is }. Each property is represented by a node of type Property. This Property type has a value that is generated by the walk() function, which is called recursively.

Note that I use tokens[++current]. This is to advance the cursor to the next token. And if a token of type , (comma) is found, we advance the cursor again to skip the comma.

The rest of the code is quite similar to what I've just explained, so it's worth the effort to look and try to understand or implement the rest on your own. It's not very complex.

Finally, I create the constant ast, which will contain the type Program and the body of the AST, generated by the walk() function. The while loop ensures that current does not exceed the size of the tokens array.

After that, we simply return the AST.



export const parser = (tokens: Array<{ type: string; value?: any }>) => {
  let current = 0


  const walk = () => {
    let token = tokens[current]


    if (token.type === TOKEN_TYPES.LEFT_BRACE) {
      token = tokens[++current]


      const node: {
        type: string
        properties?: Array<{ type: string; key: any; value: any }>
      } = {
        type: 'ObjectExpression',
        properties: [],
      }


      while (token.type !== TOKEN_TYPES.RIGHT_BRACE) {
        const property: { type: string; key: any; value: any } = {
          type: 'Property',
          key: token,
          value: null,
        }


        token = tokens[++current]


        token = tokens[++current]
        property.value = walk()
        node.properties.push(property)


        token = tokens[current]
        if (token.type === TOKEN_TYPES.COMMA) {
          token = tokens[++current]
        }
      }


      current++
      return node
    }


    if (token.type === TOKEN_TYPES.RIGHT_BRACE) {
      current++
      return {
        type: 'ObjectExpression',
        properties: [],
      }
    }


    if (token.type === TOKEN_TYPES.LEFT_BRACKET) {
      token = tokens[++current]


      const node: {
        type: string
        elements?: Array<{ type?: string; value?: any }>
      } = {
        type: 'ArrayExpression',
        elements: [],
      }


      while (token.type !== TOKEN_TYPES.RIGHT_BRACKET) {
        node.elements.push(walk())
        token = tokens[current]


        if (token.type === TOKEN_TYPES.COMMA) {
          token = tokens[++current]
        }
      }


      current++
      return node
    }


    if (token.type === TOKEN_TYPES.STRING) {
      current++
      return {
        type: 'StringLiteral',
        value: token.value,
      }
    }


    if (token.type === TOKEN_TYPES.NUMBER) {
      current++
      return {
        type: 'NumberLiteral',
        value: token.value,
      }
    }


    if (token.type === TOKEN_TYPES.TRUE) {
      current++
      return {
        type: 'BooleanLiteral',
        value: true,
      }
    }


    if (token.type === TOKEN_TYPES.FALSE) {
      current++
      return {
        type: 'BooleanLiteral',
        value: false,
      }
    }


    if (token.type === TOKEN_TYPES.NULL) {
      current++
      return {
        type: 'NullLiteral',
        value: null,
      }
    }


    throw new TypeError(token.type)
  }


  const ast = {
    type: 'Program',
    body: [],
  }


  while (current < tokens.length) {
    ast.body.push(walk())
  }


  return ast
}



const tokens = lexer('{"name":"Vitor","age":18}')
console.log('tokens', tokens)
const json = parser(tokens)


console.log('parser:', JSON.stringify(json, null, 2))

Parsing can be fun, but in reality, it's not often written, and you probably don't need to write your own parser. If you are implementing a programming language, for example, there are already various tools that can do this job for you, such as OCamllex, Menhir, or Nearley.

It's also essential to note that, as this is an introductory article, I didn't cover the different tokenization and parsing techniques, such as LR(0), LR(1), SLR(1), etc. However, be aware that these techniques exist, and you can research more about them. There are also many books that cover these topics.

If you want to see how the AST of popular languages looks, I recommend the AST Explorer. It supports various languages, and you can view the complete AST and navigate through the nodes. If you want to go further, you can try to copy some logic from an existing parser and implement it in your own, such as calculating an expression according to precedence order, for example: 1 + 2 * 3 (which is 7, not 9).

If you're interested in learning more, I recommend the book "Modern Compiler Implementation in ML." Despite the title being in ML, you can study from it without necessarily writing ML code, as there are other versions written in C, C++, and Java.

Why are you writing slow code?

Vitor — Tue, 06 Dec 2022 12:59:42 +0000

Introduction

In this post, we will explore the concept of algorithm efficiency and how to measure this efficiency using big O notation. Additionally, we will see how this can help us write more performance code. Big O notation allows us to evaluate the performance of an algorithm according to the size of its data set.

What is big O notation and algorithm efficiency?

Algorithm efficiency is the ability to solve a problem in a reasonable time and with efficient use of computational resources such as processing and memory. Big O notation is a way of measuring the efficiency of an algorithm, describing the asymptotic behavior of a function. This means that we can evaluate the rate of growth of the function, comparing it to other algorithms.

Big O notation is represented by the letter O and is used as follows: Θ(f(n)), where f(n) is the measure by which the size of the input (n) increases. For example, an algorithm that grows quadratically, that is, increases proportionally to the square of each additional input, is represented by Θ(n²).

Constant time: Θ(1)
Linear time: Θ(n)
Logarithmic time: Θ(log(n))
Quadratic time: Θ(n²)

Big O notation in code

Suppose you have a list and need to find a certain element 'x'. This algorithm is called sequential search.

Another example is when you need to sort a list. This algorithm is called insertion sort.

// linear time
function sequentialSearch(arr: number[], x: number) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === x) {
      return i
    }
  }
  return -1
}

// quadratic time
function insertionSort(arr: number[]) {
  for (let i = 1; i < arr.length; i++) {
    let currentVal = arr[i]
    for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      arr[j + 1] = arr[j]
    }
    arr[j + 1] = currentVal

    console.log(arr)
  }

  return arr
}

Both codes work and solve the proposed problem, but one is more performative than the other. The first code is linear, which means that the for loop will be executed a number of times directly proportional to the size of the array. This means that if the array has n elements, the loop will be executed n times, which can be represented by Θ(n).

The advantage of this approach is that, in case of larger arrays, the code will run faster, as the number of iterations is proportional to the size of the array. This makes the time complexity of the code limited by the size of the array, resulting in a less steep growth chart compared to a code with quadratic complexity. In other words, the first code is more performative and efficient in situations where the array can be very large.

The second code is an example of quadratic complexity Θ(n²). This means that the for loop inside the for loop will be executed a number of times proportional to the square of the size of the array. In other words, if the array has n elements, the inner loop will be executed n * n times, which can be represented by Θ(n²).

The implications of this complexity are that, in larger arrays, the growth chart will be steeper, resulting in slower and more complex code as the input gets larger.

Now, let's see some examples of code with logarithmic complexities O(log(n)) and O(n log(n)).

Suppose you receive a list of numbers and need to find a certain number x in the list. To do this, you can use the binary search algorithm, which has complexity O(log(n)).

Another example is when you need to sort a list of numbers in a logarithmic way. To do this, you can use the merge sort algorithm, which has complexity O(n log(n)).

These algorithms are more performative and efficient than linear or quadratic approaches in situations where the size of the input can be very large.

// O(log(n))
function binarySearch(arr: number[], x: number) {
  let left = 0
  let right = arr.length - 1

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] === x) {
      return mid
    }
    if (arr[mid] < x) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return -1
}

// O(n log(n))
function mergeSort(arr: number[]) {
  if (arr.length === 1) {
    return arr
  }

  let mid = Math.floor(arr.length / 2)
  let left = arr.slice(0, mid)
  let right = arr.slice(mid)

  return merge(mergeSort(left), mergeSort(right))
}

function merge(left: number[], right: number[]) {
  let result = []
  let i = 0
  let j = 0

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i])
      i++
    } else {
      result.push(right[j])
      j++
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j))
}

Both examples are valid, but they have different time complexities. The first one is O(log(n)), which means that the running time increases logarithmically with respect to the size of the input. In other words, in the worst case, if the array has 8 elements, the algorithm will be executed 3 times. For example: log2(8) = 3.

The second example, O(n log(n)), is a notation that indicates that the running time of an algorithm increases proportionally to the product of the size of the input data and the logarithm of that size. This means that, in the worst case, if the array has 8 elements, the algorithm will be executed 24 times. For example: 8 * log2(8) = 24.

However, it is important to remember that the temporal complexity of an algorithm does not necessarily imply higher or lower speed. It is possible that an algorithm with worse complexity is faster than an algorithm with better complexity, depending on the specific input. However, in general, it is safe to say that the lower the complexity, the faster the algorithm will be, as the input increases.

For those who want to delve deeper into the subject, I recommend reading the book “Introduction to Algorithms” by Thomas H. Cormen.

How to grow up and be noticed on your job

Vitor — Mon, 17 Oct 2022 12:06:06 +0000

Ownership

Always leave the code better than you found it
If it's easy to change, change it on the spot
If it's not in production, there's no reason to be afraid of making mistakes
Open issue if your problem is not simple
If it's in production, open an issue to discuss with the team how to solve

Learn in Public

Always use public channels (social media or public channels on Slack)
Make articles about the problems that you have been solving and about what you learned on your day
Ask for feedbacks

Omnipresence

Review as many PR's as you can
Ask why to everything
Participate in all discussions
Discuss with others area, like marketing or something else

Stop thinking about learning curve

Vitor — Thu, 16 Jun 2022 20:53:25 +0000

Why? Because it doesn't care.

You don't need to prepare to learn something. You need more practice and less overthinking. Learning is not linear, and you will not get expected results when you start something.

Read "Study Backwards". You should not start with the technology.

What does Learning Curve mean?

Is a term to define a curve of learning based on what you know and don't know. Example: I want to learn ReactJS, but I don't have ANY knowledge about JS. My curve will be high.

But people lose more time than needed thinking about that. And I will explain why.

What does "learning is not linear" mean?

At school, we learn how to learn wrongly. The system made you think that to know something you need to follow a step-by-step and that this is linear, like a movie or game. And this is not true.

In real life, you probably will need to learn something faster than you can and learn by demand. You won't know the "dependencies" of learning when getting some tasks at your work and don't have a teacher to guide you. At school, you know in advance the content that will be in your test, but this happens only at school.

Example: want to code smart contracts in Rust? Ok, try to start coding. If you slice, probably will think "to code a smart contract in Rust, first I need to learn and know a lot about Rust." And NO, this is wrong. This line of thought creates a snowball and makes you give up. Want to learn about smart contracts in Rust? Ok, code your smart contract, and you will know what you need of Rust to code your project.

In the real world, you shouldn't ever wait for linear things. Is chaotic.

Forem: Vitor

How to create your own Eslint rule with tests, boosting the DX, and code-review

Table of contents:

Focus on what matters

How to create your own Eslint rule

Setup the project

Creating the rule

Fixable rule

How to create tests

Test folder

Conclusion

References

The Art of Understanding Before Coding

Split

Code

Conclusion

Is Data Struct about memory?

Introduction

Algebraic Structure

Let's to think about computational models

Conclusion

Proving natural numbers are infinity in Coq 🧙🏼

Introduction

What is Coq?

What is a formal proof?

The proof

Conclusion

Building a JSON Parser from scratch with JS 🤯

Introduction

Lexing

Parsing

Why are you writing slow code?

Introduction

What is big O notation and algorithm efficiency?

Big O notation in code

How to grow up and be noticed on your job

Ownership

Learn in Public

Omnipresence

Stop thinking about learning curve

What does Learning Curve mean?

What does "learning is not linear" mean?