Forem: Klemen Slavič

I built a silly Cloudflare Worker web service that helps you do math

Klemen Slavič — Sun, 23 Jul 2023 20:34:34 +0000

I set out to learn something new and mash up two things I've been playing around with — language parsing and serverless functions. The result?

expr.run!

It's a service that lets you do algebraic math using URLs. It parses algebraic expressions in the path and returns a JSON result containing either the result or a parsing error with appropriate status codes.

A GET request like https://expr.run/1+3/2-sqrt(4) will return the result {result:0.5,error:null} and a status code of 200. If you make a typo like https://expr.run/2^3/pi it will return the following value with a status code of 400 and a verbose description of where parsing failed:

{
  "result": null,
  "error": "Error: Expected \"*\", \"+\", \"-\", \"/\", end of input, or whitespace but \"^\" found.\n --> undefined:1:2\n  |\n1 | 2^3/pi\n  |  ^"
}

The algebraic expressions support the following:

+ - * / operators
decimal numbers (in the form of -123.456e-78)
() expression grouping and proper evaluation order
function calls from the Math JavaScript namespace
the constants pi (𝜋) and e (Euler's number)
whitespace between tokens is ignored

That's it!

So, how does it work and what does it run on?

Part 1: parsing algebraic expressions

For this part, I've decided to use Peggy which enables compiling parser expression grammars into JavaScript/TypeScript parsers for use in any JS environment. The grammar I wrote is based on the example provided in the online playground and extended with function calls, floating point numbers and constants.

I won't go into too much detail into how the grammar works, but in essence, parsing starts at the first rule defined in the file, which then breaks down the tokens into smaller and smaller rules until you hit a final token which then returns a parsed value. In this case, the value is just a number, which makes the parsing function also compute the final result instead of creating an AST representation of the expression.

Expression
  = head:Term tail:(_ ("+" / "-") _ Term)* {
      return tail.reduce(function(result, element): number {
        if (element[1] === "+") { return result + element[3]; }
        if (element[1] === "-") { return result - element[3]; }
      }, head);
    }

Term
  = head:Factor tail:(_ ("*" / "/") _ Factor)* {
      return tail.reduce(function(result, element): number {
        if (element[1] === "*") { return result * element[3]; }
        if (element[1] === "/") { return result / element[3]; }
      }, head);
    }

Factor
  = "(" _ expr:Expression _ ")" { return expr; }
  / Constant
  / FunctionCall
  / Number

Constant "constant"
  = "pi"i { return Math.PI; }
  / "e"i { return Math.E; }

FunctionCall "function call"
  = fn:FunctionName _ "(" params:(Expression|.., _ "," _|) ")" {
    return evaluate(fn, params);
  }

FunctionName "function name"
  = _ fn:([a-z]i [a-z0-9_]i*) { return text().trim(); }

Number "decimal number"
  = _ [+-]? [0-9]+ ("." [0-9]+)? ([eE] [+-]? [0-9]+)? { return parseFloat(text()); }

_ "whitespace"
  = [ \t\n\r]*

evaluate is an extra function defined in scope that calls the matching Math.* functions:

function evaluate(fnName: string, params: unknown[]): number {
  if (fnName in Math) {
    if (Math[fnName].length > params.length)
      throw new TypeError(`Math.${fnName} requires ${Math[fnName].length} arguments`);
    return Math[fnName](...params);
  }
  throw new TypeError(`Unknown function: ${fnName}`);
}

Compiling this file into TS requires using a plugin called ts-pegjs which produces the final TS parser:

const peggy = require("peggy");
const tspegjs = require("ts-pegjs");
const { readFile, writeFile } = require("node:fs/promises");
const { resolve } = require("node:path");

const srcDir = resolve(__dirname, "../src/");
const source = resolve(srcDir, "calculator/grammar.pegjs");
const target = resolve(srcDir, "calculator/parser.ts");

readFile(source, "utf8")
  .then((file) =>
    peggy.generate(file, {
      plugins: [tspegjs],
      output: "source",
      format: "es",
    })
  )
  .then((parser) => writeFile(target, parser));

This processes the file grammar.pegjs and transforms it into parser.ts which we can now import from:

import { parse } from './parser.ts';

console.log(parse('1+2+3'));

Great, one problem down, two to go.

Part 2: Cloudflare workers

Cloudflare workers enable you to respond to requests by providing handler functions that receive Request objects and returns promises of Response objects. If you've used the fetch API, these should be quite familiar to you.

The simplest way to create a minimal worker is to export as default an object containing the fetch method:

export default {
  async fetch(request: Request) {
    return new Response('Hello world!');
  }
}

I won't go into detail on how to deploy workers to Cloudflare, you're going to want to RTFM. The free tier lets you use the platform with a generous amount of traffic and CPU time per request.

We'll want our serverless function to do the following:

show instructions in HTML when hitting the root URL;
extract, parse and evalute the expression and return either the result or the parsing error; and
add CORS headers to enable cross-origin fetch requests.

import { parse, PeggySyntaxError } from "./calculator/parser.js";

// this generates the full HTML page, omitted for brevity
const instructions = (baseUrl: string) => `...`;

const CORS_HEADERS = {
  "Access-Control-Allow-Origin": "*",
  "Access-Control-Allow-Methods": "GET,HEAD,POST,OPTIONS",
};

async function handleOptions(request: Request) {
  if (
    request.headers.get("Origin") !== null &&
    request.headers.get("Access-Control-Request-Method") !== null &&
    request.headers.get("Access-Control-Request-Headers") !== null
  ) {
    // Handle CORS preflight requests.
    return new Response(null, {
      headers: new Headers({
        ...CORS_HEADERS,
        "Access-Control-Allow-Headers": request.headers.get(
          "Access-Control-Request-Headers"
        )!,
      }),
    });
  } else {
    // Handle standard OPTIONS request.
    return new Response(null, {
      headers: {
        Allow: "GET, HEAD, POST, OPTIONS",
      },
    });
  }
}

export default {
  async fetch(request: Request) {
    if (request.method == "OPTIONS") {
      return handleOptions(request);
    }

    const url = new URL(request.url);
    const path = url.pathname;

    if (path == "/") {
      return new Response(instructions(url.origin), {
        headers: { "Content-Type": "text/html" },
      });
    }

    const expr = decodeURIComponent(path.replace(/^\//, ""));
    try {
      return new Response(
        JSON.stringify({ result: parse(expr), error: null }),
        {
          headers: new Headers({
            ...CORS_HEADERS,
            "Content-Type": "application/json",
            "Cache-Control": "public, max-age=604800",
          }),
        }
      );
    } catch (err) {
      let message: string;
      if (typeof (err as any)?.format == "function") {
        message = (err as PeggySyntaxError).format([{ text: expr }]);
      } else {
        message = err?.toString() ?? "Unknown error";
      }
      return new Response(JSON.stringify({ result: null, error: message }), {
        status: 400,
        statusText: "Bad request",
        headers: new Headers({
          ...CORS_HEADERS,
          "Content-Type": "application/json",
          "Cache-Control": "public, max-age=604800",
        }),
      });
    }
  },
};

And that's the entirety of the Cloudflare Worker implementation! All that needs doing now is to bundle everything up and deploy to the cloud.

Part 3: bundling and deploying

I used vite to generate both a CommonJS and ES module version bundles for this project using the following configuration (you could get away with just ES if you don't need both):

import { defineConfig } from "vite";
import { resolve } from "node:path";

export default defineConfig({
  build: {
    lib: {
      entry: resolve(__dirname, "src/index.ts"),
      formats: ["cjs", "es"],
      fileName: "index",
    },
    target: "es2020",
  },
});

The tsconfig.json file is quite straightforward:

{
  "compilerOptions": {
    "target": "ESNext",
    "lib": ["ESNext", "DOM"],
    "strict": true,
    "module": "ESNext",
    "moduleResolution": "NodeNext"
  },
  "include": ["src", "tasks"]
}

After building the parser and running vite build the dist directory contains both the CJS and ES versions named index.js and index.cjs.

Using wrangler you can then upload either version to deploy it to the cloud. Before running this command, you'll need to create a worker and use its name and a date appropriate according to their documentation:

wrangler deploy dist/index.js --name <name> --compatibility-date <date>

After deploying the 4-some kilobytes of gzipped code, the worker will be up and running in a matter of seconds and ready to respond to any algebraic problem you can throw at it!

You can also use fetch('https://expr.run/...') in your own apps/web pages to compute things on the fly without having to roll your own parser.

Conclusion

Often times, learning something requires a significant investment in time, but with the right goal in mind, you can make fast progress and be productive without feeling overwhelmed.

Build something silly. Go on, have fun.

Stop wasting bandwidth with React's `useEffect` and `fetch`!

Klemen Slavič — Wed, 21 Jun 2023 12:57:30 +0000

You've been in this situation before. You have a component that needs to fetch some data, which sounds like a no-brainer, right? Just use useEffect() to load the data, set it into state and you're done. You slide the keyboard in front of you and start typing out your component:

// ...

interface Post {
  image: string;
  title: string;
  link: string;
}

function App() {
  const [releases, setReleases] = useState<null | Post[]>(null);

  useEffect(() => {
    fetch(targetUrl)
      .then((response) => response.json())
      .then((data) => {
        const converted = extractThumbnails(data);
        console.log("Got data!", converted);
        setReleases(converted);
      })
      .catch((err) => {
        console.error(err);
        setReleases([]);
      });
  }, []);

  // ...
}

At first glance it seems to work just fine when you load it up in the browser:

However, if you're running this example using React 18 in development and strict mode (like the above example), every useEffect hook runs twice when the component is mounted.

Apparently, it is an all too common problem in React codebases to not correctly handle clean-up when using side effects. There's even an entire page dedicated to why you shouldn't use it for. So the React developers decided to force the useEffect hook to fire twice in development mode to surface problems like these early and break things in an obvious way if not coded correctly.

I may not agree that the behaviour of hooks should change when switching between production and development modes, I do wholeheartedly agree that effect hooks should correctly return clean-up functions when necessary. So let's fix our example.

First off, let's think about why the example above might be problematic in the first place. If the effect runs twice, then two requests will fire and the last one to arrive will be the one to determine what kind of data will be shoved into the state. A race condition.

There are two ways to solve this problem:

ignore the response from the first request; or
cancel the previous request.

If you look at the documentation example on React's documentation page, the authors outline the first solution:

useEffect(() => {
  let ignore = false;
  fetch(targetUrl)
    .then((response) => response.json())
    .then((data) => {
      if (!ignore) {
        const converted = extractThumbnails(data);
        setReleases(converted);
      }
    })
    .catch((err) => {
      console.error(err);
      setReleases([]);
    });
  return () => {
    ignore = true;
  };
}, []);

While this does avoid the race condition, it still fires two requests, the first of which will always be ignored. This will waste bandwidth, of course, but it will prevent the state from being updated twice.

The other problem I have with this solution is that the if (!ignore) check has to be on the last step of the promise chain, meaning the response will always be decoded. You could conditionally throw an error on every promise chain step, but forgetting to do that in an intermediate step will just waste more time on a throwaway result.

Let's look into how to implement the second solution, then. To cancel a request using fetch() , we must create an instance of AbortController and pass its signal property into the configuration. We can then use the controller to call its abort() method when the request needs to be cancelled:

useEffect(() => {
  const controller = new AbortController();
  fetch(targetUrl, { signal: controller: signal })
    .then(response => response.json())
    .then(data => {
      const converted = extractThumbnails(data);
      setReleases(converted);
    })
    .catch(err => {
      if (err.name != 'AbortError') {
        console.error(err);
      }
    });
  return () => controller.abort();
}, []);

When a request is cancelled, the promise rejects with a DOMException whose name property equals "AbortError". Since we can treat request cancellation as an expected error, we only report other errors to the console.

This now results in the following timeline:

The nice thing about this approach is that the promise chain will simply reject at whichever point abort() gets called and doesn't require us to check a variable state at each point in the chain just to avoid wasted work. It also helps with readability — the returned function calls abort() and the promise chain handles that case in the catch() case, as it should.

Now that this problem is solved for the double useEffect execution in dev mode, it also solves the problem of quickly switching between components on a slow network — components won't continue to request and download responses after they're unmounted. On a slow mobile connection, this could mean the difference between an OK experience and a REALLY bad one.

And here's the implementation with AbortController:

Reading and Parsing Large Files in JavaScript the Right Way

Klemen Slavič — Mon, 29 May 2023 21:39:56 +0000

In the previous article in the series, we had a look at Generator Functions that let you generate values in a way that can be consumed by a for...of loop. We used this to create a sequence of natural numbers without having to allocate the entire number set in memory, lazily producing each value when the consumer requests one.

In the same vein, Streams allow for incremental reading of a large chunk of data (or files!). Instead of forcing us to allocate memory for the data, the decoded content and any subsequent results, it allows us to process data as a series of steps on individual slices.

A Gentle Introduction to Streams

Streams come in three variations:

ReadableStream: a stream that can be read from,
WritableStream: a stream that can be written to,
TransformStream: a stream that can take the output of a readable or transform stream and output a transformed result. It is both readable and writable.

The one that will be useful most of the time is ReadableStream. This is also the stream type that is provided by the File and Response objects as an alternative to the more common text() and json() methods that returns a decoded string asynchronously.

As an example, we'll build an application that will can count the number of lines of text for a file dropped into the web page. First, let's look at the core of the problem — how do we read a file using streams?

Consuming a `ReadableStream`

Let's start with a function that takes a File object and reads it from start to end, counting the occurence of line feeds (empty lines also count as a line) and returns the final count:

const countLines = async (file: File): Promise<number> => {
  let count = 1;
  const stream = file.stream().pipeThrough(new TextDecoderStream());
  const reader = stream.getReader();

  try {
    while (true) {
      const { done, value } = await reader.read();
      if (done) break;
      const lineBreaks = value.match(/\n/g)?.length ?? 0;
      count += lineBreaks;
    }
  } finally {
    reader.releaseLock();
  }

  return count;
};

The first thing to note is that files are 8-bit binary streams (Uint8Array) which must first be decoded into UTF-16 strings that JavaScript for string representation. To do this, we pipe the file's ReadableStream<Uint8Array> through a transform stream called TextDecoderStream which converts the byte stream into a stream of strings that we can consume using the reader (an instance of ReadableStreamDefaultReader).

A reader provides the read() method which returns a Promise that resolves to the next chunk in the stream. We can use an infinite loop to read the next chunk and check if the stream has been exhausted by testing the done property on the resolved value. If true, we simply break the loop.

Now that we have a function that can count lines in files, let's build a quick web application that we can demonstrate its functionality. I've decided to use Vite, Preact and @krofdrakula/drop to build the web application shell that uses the above function to display line counts for any file (or multiple files) dropped into the page:

Since the files are read locally and not sent over the wire, you can drop any size files (even hundreds of MB!) and the browser will handle it just fine. It doesn't even have to be text, but the line count will not really make much sense in that case.

Creating Your Own `ReadableStream`

At this point you may be wondering how one can one create a ReadableStream in the first place. A ReadableStream is created using the ReadableStream constructor which takes a configuration object with the following optional methods:

pull(controller): whenever the stream is read, this method is called by the reader in order to produce the next chunk of data. The controller object is used to send values to the consumer of the stream.
start(controller): whenever the stream is constructed, this method is called and can optionally send values via the controller object
cancel(reason?): called when the stream's cancel() method is called with an optional reason. Used to clean up any open handles to resources or similar.

Let's take the example of natural numbers from the previous article and write a ReadableStream that emits all natural numbers up to the given maximum:

const createNaturalNumberStream = (max: number = Infinity) => {
  let i = 1;
  return new ReadableStream<number>({
    pull(controller) {
      if (i <= max) {
        controller.enqueue(i);
        i++;
      } else {
        controller.close();
      }
    },
  });
};

Reading this stream will keep emitting numbers in sequence up until, and including, max.

Transforming Streams Using `TransformStream`

As previously mentioned, TextDecoderStream takes a stream of bytes and converts them to a stream of UTF-16 strings suitable for JavaScript. Streams do not have to provide data in byte arrays or strings, however; they can emit any kind of JavaScript value.

Constructing a TransformStream is achieved similarly to ReadableStream but has a different set of optional methods:

transform(chunk, controller): called whenever a chunk is read from the transform stream. Use controller to emit values to the reader.
start(controller): called when the transform stream is constructed.
flush(controller): called when the source has been consumed and is about to be closed.

To demonstrate the API, let's create a mapping stream that will take a value from the input stream and apply a mapping function on the emitted value. The only method we need to implement is the transform function that takes a chunk and enqueues the mapped value:

const createMapStream = <I, O>(
  mapper: (value: I) => O
): TransformStream<I, O> =>
  new TransformStream({
    transform(value, controller) {
      controller.enqueue(mapper(value));
    },
  });

Using this transformer is simply a matter of piping any compatible readable stream through it:

const evenNumberStream = createNaturalNumberStream().pipeThrough(
  createMapStream((n) => n * 2)
);

Other Streams

CompressionStream: compresses the content of a Uint8Array stream into a new Uint8Array stream
DecompressionStream: does the opposite of the above
FileSystemWritableFileStream: allows writing to an open file system file handle
WebSocketStream: an open standard proposal to allow writing to a web socket as a WritableStream

Converting `ReadableStream`s into Asynchronous Iterables

Admittedly, streams are not as straightforward to consume as a for...of loop, but there is good and bad news.

The good news is that the ReadableStream specification implements Symbol.asyncIterator that allows you to read a ReadableStream using a for await...of loop, e.g.:

for await (const number of evenNumberStream) {
  console.log(number);
}

The bad news is that it currently isn't supported in all JavaScript engines. However, what we can do is leverage what we learned in the previous article regarding generator functions and create a utility function that takes a stream and creates an AsyncGenerator yielding values from the input stream:

const streamToIterable = async function* <T>(
  stream: ReadableStream<T>
): AsyncGenerator<T> {
  const reader = stream.getReader();
  try {
    while (true) {
      const { done, value } = await reader.read();
      if (done) return;
      yield value;
    }
  } finally {
    reader.releaseLock();
  }
};

This makes it possible to consume any stream as an async iterable:

for await (const number of streamToIterable(evenNumberStream))
  console.log(number);

Applied Streamology

In the next installment, we'll have a look at applying our knowledge of streams and generators to read large files in the browser while keeping memory consumption low and the UI responsive while data is being processed.

What Does the Iterator Protocol Have To Do With`for...of`?

Klemen Slavič — Fri, 26 May 2023 22:39:30 +0000

Iterables have been around for a while now and supported on all platforms, and you may have been wondering what they are, how they work and how they can be useful.

This article explains the basics of iterables and the iterator protocol and shows how they can be used.

An Introduction to the Iterator Protocol

You may have used JavaScript's for...of statement to iterate over arrays or Object.entries(), but you may not have known that any object can provide this kind of iteration by implementing the iterator protocol.

An object can be iterated with for...of if it implements the iterator protocol by providing a method called Symbol.iterator. It takes no arguments and returns an iterator.

An iterator is an object that contains the next() method and returns an iterator result. The result object contains two properties:

done: a boolean value that tells the consumer whether the iterator has been depleted
value: the value produced by the iterator

Let's first implement a function that will create an iterator that counts up all natural numbers until max:

const naturalNumbers = (max: number) => {
  let n = 1;

  const next = () => {
    if (n > max) return { done: true };
    const value = n;
    n++;
    return { done: false, value };
  };

  return {
    [Symbol.iterator]() {
      return { next };
    },
  };
};

To use this function without the for...of loop, let's use the iterator protocol to demonstrate what it does under the hood:

const sequence = naturalNumbers(10);

// calling the `@@iterator` method on the sequence returns an iterator
const iterator = sequence[Symbol.iterator]();

// we create an infinite loop...
while (true) {
  // ...that will keep reading the next value from the iterator...
  const { done, value } = iterator.next();
  // ...until the iterator tells us it's done
  if (done) break;
  // else, we print out the value and repeat the loop
  console.log(value);
}

This iterator protocol is what enables the for...of loop to create an iterator from the sequence and loop through each value. We can write the above with a very compact syntax:

for (const n of naturalNumbers(10))
  console.log(n);

While it may look a bit daunting to implement the iterator protocol directly, there is a convenient way to express the same sequence using generator functions.

Creating Iterables using Generator Functions

A generator function can be created using the function* syntax. This enables the use of the yield keyword that pauses execution of the generator function and passes the value given to the yield keyword back to the caller. When the caller requests the next value, the generator function is resumed until it hits the next yield statement. If the generator function returns, the iterator protocol is sent a done: true value.

With this in mind, let's rewrite the sequence as a generator function:

function* naturalNumbers(max: number) {
  let n = 1;
  while (n <= max) {
    yield n;
    n++;
  }
}

Calling this generator function returns an iterable value that can be consumed by the for...of loop just like the previous example.

To understand how the body of this function is executed, it's best to imagine that the function starts paused until the iterator's next() method is called. On the first call, n is set to 1 and we enter the loop for the first time. We yield the value 1 and wait until the next call.

On the second next() call, we resume the function and increment n, return to the top of the loop (since 2 < 10) and yield 2, which pauses the function again.

Up until the final (11th) call of the next() method, we increment n which now becomes 11, the while loop breaks and the function returns, marking the iterator as done.

Why Bother?

Since iterators only produce values when the next() method is called, we can generate huge sequences without having to waste memory creating arrays and storing values. Running new Array(10_000).fill(0) just to create 10k values is much more

A generator for all natural numbers is simply:

function* nat() {
  let i = 1;
  while (true) yield i++;
}

NOTE: eventually, this generator will fail to produce new numbers above Number.MAX_SAFE_INTEGER 64-bit IEEE numbers do not have infinite precision. Use BigInt instead if you REALLY need to go that far.

If you try to iterate over this iterable, the for...of loop will never terminate:

// prepare for a very long wait
for (const n of nat())
  console.log(n);

We could, of course, write a check inside the body of the for...of loop to terminate early, but we can use generator functions to manipulate other iterables.

Let's create a function that will take an iterable and return a new iterable that will at most iterate over the given number of items:

function* take<T>(iterable: Iterable<T>, count: number) {
  let i = 0;
  for (const item of iterable) {
    if (i == count) return;
    yield item;
    i++;
  }
}

We can now take the first 10 natural numbers:

for (const n of take(nat(), 10))
  console.log(n);

Practice Makes Perfect

To get a better feel for generator functions, here are a couple of examples to implement on your own. Post your solutions in the comments and get feedback! 😊

create a generator function that will repeat a value a given number of times: repeat("a", 3) => "a","a","a".
create a mapping generator function that yields transformed values from a given iterable: map(nat(), x => x * 2) => 2,4,6,8,...
create a generator function that takes an iterable and yields every n-th item: every(nat(), 3) => 1,4,7,10,...
create a generator function that takes multiple iterators and yields each iterator by packing their results into an array: zip(nat(), nat()) => [1,1],[2,2],[3,3],...

Up Next

A similar concept called Streams also enables consuming large blocks of data by processing small chunks at a time. Stay tuned for the next article delving into neat little feature.

Want to be able to drag files into a web app? Got ya covered.

Klemen Slavič — Thu, 04 May 2023 21:36:58 +0000

It's 2023. We all know how annoying it is when a web app wants us to provide a file but makes it cumbersome by only letting you do that by clicking on Ye Olde <input type=file>. All modern browsers have supported a much better way to do that for a while now, and this library makes it a snap to use them in any environment, vanilla or framework.

https://github.com/krofdrakula/drop/

The Setup

Install @krofdrakula/drop in your dependencies or use https://esm.sh/@krofdrakula/drop as your module import.

Create some HTML in your page:

<div id="drop_target" style="padding:40px;border:1px solid blue;">
  Drop files here.
</div>

In your JS, grab that element and pass it to the create function:

import { create } from '@krofdrakula/drop';

const dropTarget = document.body.getElementById("drop_target");

create(dropTarget, {
  onDrop: (files) => console.log(files)
});

Open the page in a browser, open dev tools and drag a file into the element you created.

In React-like Components

The create() function returns a cleanup function that can be used in conjuction with useRef and useEffect to correctly set it up:

import { useRef, useEffect } from 'react';
import { create } from '@krofdrakula/drop';

const MyComponent = ({ onDrop }) => {
  const dropTarget = useRef();

  useEffect(() => {
    // you must return the returned function for it to be
    // able to clean up event handlers
    return create(dropTarget.current, { onDrop });
  }, [dropTarget.current, onDrop]);

  return <div ref={dropTarget}>Drop files here.</div>
};

Handy Features

create takes a number of options that let you configure the behaviour of the control:

it exposes various event handlers that let you control the element when the pointer hovers over it when dragging files or without;
it lets you specify parser functions that allow you to convert files dropped onto the element before passing them to the onDrop handler;
it uses the native file picker when clicking on the element by default.

Check out the demo site to see it in action, or read the README for the full Monty.

All of this in a package that fits any application's download limits.

Development

This package currently does everything I needed it to for the cases I knew it should handle. If you decide to try this out and hit a problem, let me know!

Supercharging Autocomplete and Typechecking for JSX Components with Generics!

Klemen Slavič — Mon, 06 Mar 2023 22:07:40 +0000

TL;DR: Skip to the end of the article for a working Stackblitz implementation.

If you've spent any time writing functions and classes in TypeScript, you may have stumbled upon generics which allow you to infer types being passed into a function or class without having to necessarily assign types ahead of time. What you may not have realised is that the same can be applied to JSX components.

Using generics allows JSX components to offer autocompletion and type safety for things that would otherwise have been typed as any due to the highly generic nature of components.

In this article, we're going to use Preact as our JSX library to render components, and we'll build a table rendering component that will infer and typecheck its props based on whatever data we give it.

The Data Model

To start, we'll need to define the shape of data we'll be passing into the table component. To make things simple for the end-user, we'll start with a simple constraint — the data must be an array of objects whose properties are field identifiers:

export type TableData<T extends Record<string, unknown>> = T[];

Try this example in the TS Playground

Because the keys can be associated with any value, table cells will need to be able to render values based on their type. For some values, the end user of the table component might want to control how that field renders its values by providing their own component. To facilitate this, let's create a type that will generate props for a component based on the row type given by the user:

import type { ComponentType } from 'preact';

// a Field is any component that renders a value: <Field>{value}</Field>
export type Field<Value> = ComponentType<{ children: Value }>;

// we create an optional map of field name to component that renders that value
export type FieldRenderers<Row extends Record<string, unknown>> = {
  [Prop in keyof Row]?: Field<Row[Prop]>;
};

Try this example in the TS Playground

The Components

Since we're building the table component from the ground up, let's start with the default field component:

export const DefaultField: FunctionalComponent<{ children: any }> = ({
  children,
}) => {
  if (typeof children == 'number') {
    return <>{children.toLocaleString()}</>;
  } else if (typeof children == 'string') {
    return <>{children}</>;
  } else if (typeof children == 'boolean') {
    return <>{children ? '✅' : '❌'}</>;
  } else if (children instanceof Date) {
    return <>{new Intl.DateTimeFormat().format(children)}</>;
  }
  return <>{children}</>;
};

Try this example in the TS Playground

This component takes a couple of common types like numbers, strings, dates and booleans and renders them according to their default browser locales to nicely format them. It doesn't try to cover all possible types, but enabling the user to provide a custom renderer for a field will take care of that problem. If the value itself is a JSX element, it will also just render the value.

The next step is to create the table component that will tie all of these types together. Let's start with the component signature itself:

export const Table = <Row extends Record<string, any>>({
  data,
  fields = {},
  columnOrder,
}: TableProps<Row>) => {
  /* ... implementation detail in TS playground ... */
};

See the full implementation in the TS Playground

You'll notice that we used a generic parameter called Row to declare a type parameter that we use to pass to the TableProps type. This allows the component to infer the type based on the array being passed into the data prop when the component is used.

Once the data type for data is known from its usage, the rest of the props are adjusted accordingly; fields now only accepts a partial object whose keys match keys in the data array items and columnOrder takes an array of keys. If you try to add other strings or provide other keys, you'll get a type error. Same goes for the cell renderers; it expects a class or functional component that takes children and renders it.

Using the `Table` Component

Now that we've written the Table component, it's time to try out the neat features generics give us as a user.

First, let's define some data without explicitly defining a type for it:

const exampleData = [
  {
    id: 1,
    name: 'Johnny Burger',
    email: 'johnny@example.org',
    bio: 'Lorem ipsum dolor sit amet, consectetur adipiscing elit. Fusce viverra malesuada dui. Vivamus ac aliquet justo, eu laoreet purus. Aliquam pulvinar, nulla ut rhoncus viverra, purus ligula tincidunt orci, a venenatis lacus libero eget urna. Vivamus dictum nunc id ligula iaculis, ac tincidunt turpis auctor. Fusce mollis viverra diam nec hendrerit. Fusce iaculis sed nisl ut cursus. Fusce dapibus mi id lacus dapibus, vel semper mauris rutrum. Maecenas mattis tincidunt leo non pulvinar. Maecenas nibh nulla, dapibus quis est sit amet, accumsan viverra sem. Fusce a fringilla lacus. Maecenas iaculis justo non finibus finibus. Quisque aliquam ultrices lacus eget porta.',
  },
  {
    id: 2,
    name: 'Henrietta Biggles',
    email: 'beagle@example.org',
  },
];

Try this example in the TS Playground

If you open the playground and hover over the type, you'll see that the inferred type is:

const exampleData: ({
    id: number;
    name: string;
    email: string;
    bio: string;
} | {
    id: number;
    name: string;
    email: string;
    bio?: undefined;
})[];

// ...or simplified a bit:

const exampleData: {
    id: number;
    name: string;
    email: string;
    bio?: string;
}[];

If we pass this data to the Table component, nothing notable happens other than rendering the table:

import { render } from 'preact';
import { Table } from './table';

const exampleData = [
  {
    id: 1,
    name: 'Johnny Burger',
    email: 'johnny@example.org',
    bio: 'Lorem ipsum dolor sit amet, consectetur adipiscing elit. Fusce viverra malesuada dui. Vivamus ac aliquet justo, eu laoreet purus. Aliquam pulvinar, nulla ut rhoncus viverra, purus ligula tincidunt orci, a venenatis lacus libero eget urna. Vivamus dictum nunc id ligula iaculis, ac tincidunt turpis auctor. Fusce mollis viverra diam nec hendrerit. Fusce iaculis sed nisl ut cursus. Fusce dapibus mi id lacus dapibus, vel semper mauris rutrum. Maecenas mattis tincidunt leo non pulvinar. Maecenas nibh nulla, dapibus quis est sit amet, accumsan viverra sem. Fusce a fringilla lacus. Maecenas iaculis justo non finibus finibus. Quisque aliquam ultrices lacus eget porta.',
  },
  {
    id: 2,
    name: 'Henrietta Biggles',
    email: 'beagle@example.org',
  },
];

render(
  <Table data={exampleData} />,
  document.body
);

Try this example in the TS Playground

And here's where all that effort starts to pay off. We want to do two things:

We want emails to be linked using the mailto: protocol for easy access; and
We want to truncate the bio field if it is longer than 50 characters.

Let's create two components that will do this for us:

const Email: FunctionalComponent<{ children: string }> = ({ children }) => (
  <a href={`mailto:${children}`}>{children}</a>
);

const Truncate: FunctionalComponent<{ children: string | undefined }> = ({
  children = '',
}) => <>{children.length > 50 ? `${children!.slice(0, 50)}…` : children}</>;

Let's use these components to render the values in the two fields. If we now use the fields prop on the Table component, we'll get autocomplete that suggests the field names from the example data!

Try this in the TS Playground

The same also applies for the columnOrder which constrains the array of strings passed to only contain keys from the data passed to the component.

Working Example

To wrap things up, I've put together a working Stackblitz example where you can play around with the developer experience of using the component itself. Can you think of other examples that could benefit from type inference? Leave a comment!

Reproducible randomness and its applications

Klemen Slavič — Sun, 13 Nov 2022 21:55:45 +0000

Cover page by cottonbro studios

While these comic strips might seem absurd, they actually carry deep insight into random numbers and how they're generated and used. Don't get me wrong; the joke is funny, but there's more to it than you may think.

Throwing dice in code

Randomness in programs is tricky — computers are ruled by determinism which means that a computer with the same inputs can only generate the same output every time. For true randomness, it needs an outside source to derive sequences of true random numbers. The physical processes involved in generating these sources of entropy are often too slow for typical usage, and not all hardware allows for such true random sources.

There is a faster compromise, though — algorithms called Pseudorandom Number Generators, or PRNG for short.

To generate a sequence of pseudorandom numbers, you must provide a seed value to the algorithm. The simplest way to think about what this value represents is to imagine a large book filled with random digits. Picking a seed value means flipping to a particular page of that book, finding the correct line and column on the page and start reading the sequence left-to-right, top-to-bottom, reading as many digits at a time as required. When you reach the end of the book, you flip to the first page and continue from there.

It might surprise you that a printed book was the source scientists and engineers used to obtain large amounts of random numbers for experimental purposes before the advent of accessible computing machines. The book contained sequences that were guaranteed to satisfy all of the important randomness criteria known at the time. You can even buy the book they used and try it for yourself! It sure beats rolling dice or flipping coins.

A million base-10 digits isn't really that much when you consider modern computers, however — the entire sequence would fit on a single floppy disk. The problem with such a relatively short sequence is that it loops back onto itself after using up enough digits. To generate a 64-bit floating number you'd need to use 20 base-10 digits at a time ( $log10264≈20log_{10} 2^{64} \approx 20$ ), which means that this random number sequence can only generate 50,000 numbers before the cycle starts again.

PRNGs works slightly differently. A seed value sets up the internal state which is used to shuffle bits around every time a new number in the sequence is generated. The idea is that a good PRNG algorithm will produce an impossible-to-guess sequence while satisfying as much of the criteria tests for randomness as possible. That way, the PRNG effectively writes the book of numbers while you're reading it, but the book doesn't need to be stored anywhere, and every seed value generates a different book.

Note: Some PRNGs may appear random, but given enough of its output, researchers have managed to deduce the PRNGs internal state, therefore making the sequence predictable, which is why it is important to use cryptographically secure PRNGs seeded with true random numbers.

Depending on the chosen algorithm, the book the PRNG writes could be very long — $2^{19937}-1$ bits in the case of Mersenne Twister used in the examples below. But there are as many different sequences as there are seed values, so you can be sure not to run out of fresh unpredictable sequences of numbers any time soon. Crucially, the same seed value will always produce the same book.

Unpredictable yet reproducible

To see this in action, let's take a look at a side-by-side comparison between a seeded PRNG and the built-in Math.random() function in JavaScript:

In this example, the left column of names is picked using values from a Mersenne Twister generator set up with the initial seed value from the input field. In the right column, picking is done using Math.random() which is seeded by the browser for you (and no way for you to configure).

You'll notice that every time you rerun the example the left column always produces the same list of names given the same seed value. The right column generates a new list of names each time the page loads or you press the button.

The problem with the solution on the right is that after you press the button, the original pseudorandom sequence is gone and there is no way to reproduce it. If you happen to notice an interesting sample and you accidentally miss the opportunity to capture that state, then you're out of luck. With a seed value, all you have to do is capture that number and use it to rebuild the state.

This property also makes things like game world sharing possible by simply sharing a single short string or number and running the same algorithms to produce the same results everywhere.

At the end of the day, if you wanted randomness every time you boot up, you could simply choose a new seed every time by using an external value like Date.now(), Math.random() * Number.MAX_SAFE_INTEGER or some other means.

A practical example

Sometimes, the sheer number of different combinations of inputs might make it infeasible to do a thorough review of the runtime behaviour of a program. In those cases, having generators on hand to generate lots of unpredictable input could help spot problems that you hadn't anticipiated.

In order to make things easier to manage and compose, let's explore a construct in JavaScript called generators, which will let us control and orchestrate generating large amounts of data easily and without the need for writing hundreds of loops.

JavaScript generators and generator functions

To create a generator, we can leverage JavaScript generator functions. The nice thing about generator functions is that they evaluate lazily, meaning that users pull values from them rather than populating a collection like an array ahead of time. A generator function can use yield to emit a value, which pauses its execution until the next value is requested.

Note: The difference between generator functions and generators is that invoking a generator function will return a generator. A generator is an object with at least the next() method that returns an object with the properties { done, value }. If done is true, then the generator has finished generating its sequence and will no longer emit values, which also terminates iteration. This API is called the Iterator protocol and any object mathching this API can be used in a for...of loop.

Let's start with a simple example that takes a starting number and an increment step to generate an infinite sequence of integers:

function* int(start = 0, step = 1) {
  let i = start;
  while(true) {
    yield i;
    i += step;
  }
}

const generator = int();

for (const n of generator) {
  console.log(n);
}

In this example, calling int() returns a generator. When the for...of loop calls the next() method, the generator runs the function body until it hits a yield keyword which pauses the generator and emits the next value. If the generator function returns, no more values are emitted.

Note: There is more to generator functions than is described here. yield statements return values passed to the next() method to provide two-way communication between the generator and consumer. A generator function can also delegate to other generators using yield*. They can yield Promises and take advantage of await statements and enable asynchronours iteration.

`take`

Most of the time, we'd like to limit the amount of items in the generated sequence without having to write for loops, so we'll define a take generator function that terminates the sequence when the limit is reached or the underlying generator is exhausted:

const take = function* (count, generator) {
  for (let i = 0; i < count; i++) {
    const { value, done } = generator.next();
    if (done) return;
    yield value;
  }
  generator.return?.();
};

const first10Numbers = take(10, int(1));

// will print [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
console.log([...first10Numbers]);

Note: The return?.() call signals to the wrapped generator that we are done consuming its values. This enables generators to clean up any side effects they may have created, like closing network connections, or cleaning up any open resources like I/O handles or caches. The nullish coalescing operator is there to protect in cases where the generator does not provide that function.

`zip`

For convenience, let's also define a zip generator. Zipping in this context means taking multiple generators, requesting a value from each of them and emitting a single value as an array of all of the values. This makes it easy to group results from multiple generators into a single value:

const zip = function* (...generators) {
  while (true) {
    const results = [];
    for (const g of generators) {
      const v = g.next();
      if (v.done) {
        generators.forEach(g => g.return?.());
        return;
      }
      results.push(v.value);
    }
    yield results;
  }
}

const sumsTo10 = zip(int(0, 1), int(10, -1));

// will print [[0, 10], [1, 9], [2, 8], [3, 7], [4, 6]]
console.log([...take(5, sumsTo10)]);

`map`

Next we'll create a mapgenerator that returns a generator that translates values from the underlying generator using the provided mapping function:

const map = function*(mapper, generator) {
  for (const value of generator)
    yield mapper(value);
}

/**
 * Returns an ordinal representation of an integer. Only works
 * with positive integers.
 */
const intToOrdinal = n => {
  if (n % 10 == 1 && n % 100 != 11) {
    return `${n}st`;
  } else if (n % 10 == 2 && n % 100 != 12) {
    return `${n}nd`;
  } else if (n % 10 == 3 && n % 100 != 13) {
    return `${n}rd`;
  }
  return `${n}th`
};

const ordinals = map(intToOrdinal, int(1));

// will print ['1st', '2nd', '3rd', '4th', '5th']
console.log([...take(5, ordinals)]);

Creating random number-driven generators

So far, we've only dealt with regular sequences, but that doesn't mean we can't use our PRNG to generate an (almost) never-ending stream of random numbers:

import mt from 'mersennetwister';

const rnd = function* (seed) {
  const prng = new mt(seed);
  while(true) yield prng.real();
}

// will always print [1125387415, 2407456957, 681542492]
console.log([...take(3, rnd(1337))]);

To make this more reusable, let's create a generator that takes an array and seed value and returns a generator that will randomly pick values from that array:

import mt from 'mersennetwister';

const fromArray = function* (arr, seed) {
  const prng = new mt(seed);
  while(true) yield arr[prng.int() % arr.length];
}

const sample = ['apple', 'pear', 'banana', 'kiwi'];

// will always print ["kiwi", "pear", "apple"]
console.log([...take(3, fromArray(sample, 1337))]);

Putting it all together

With these utilities, we can compile a sample data set as arrays to generate fake personal information to use in our app. We start by creating the generators for first and last names separately:

import * as data from './data/people';
import { fromArray } from './utils';

export const firstNames = (seed) => fromArray(data.firstNames, seed);

export const lastNames = (seed) => fromArray(data.lastNames, seed);

export const fullNames = (seed) => map(
  n => n.join(' '),
  zip(firstNames(seed), lastNames(seed + 10))
);

So what is going on here? firstNames and lastNames return generators for first and last names respectively, and fullNames composes them and returns a generator that emits values with both joined with a space.

We can use these generators to quickly build up a mock application that shows the generated personal info as a list of avatars:

This example is immediately usable as a review tool, a performance benchmark and as a smoke testing tool. You can immediately see a myriad of first and last name combinations and generate a ton of them to measure how fast they render. For example, there is a bug in the mapping function that extracts initials from the generated names that is immediately apparent:

Hint: JavaScript strings are encoded using UTF-16, index access in strings always returns a 16-bit value (a code unit) along that boundary. If you think you can crack it, fork the example and post your solution in the comments!

Being able to reproduce this state easily by simply sharing a few parameters means the developer can now exactly trace where the mistake is without having to guess where the problem lies.

Adopting seeded PRNG in your own project

While this generator-based approach can work well when building up your own data generation pipeline or niche data set (it has for me on several occasions on large commercial projects), it might sometimes be easier to adopt other generation libraries that provide sensible and realistic data already included in the example set. Here are a few libraries that I've used in the past to leverage seeded randomness:

faker — the controversial grandaddy of fake data generation
fiona — a leaner library with a similar feature set

Beyond sequences

While PRNG sequences are useful for discrete data generation, they can use them as a tool to combine with other techniques like interpolation which produce contiguous multi-dimensional fields. These can be used to produce textures that can mimic natural materials or model organic-looking structures based off of a few simple mathematical expressions. But that is a topic we can address in a future article.

Arrays, the slow parts — we can do better

Klemen Slavič — Wed, 27 Mar 2019 21:34:59 +0000

Cover photo by Dan Deaner via Unsplash

There are many advantages to arrays as a data structure that make them ideal for certain scenarios, but make them quite unflatteringly slow when using their built-in methods in others. In this article, we'll have a look at some alternative data structures that makes the job much more efficient.

The right tool for the right job

In the previous article we explored Big-O notation so that we can make better decisions about how to analyze our algorithms to achieve better performance. We know that arrays are great when you're accessing an element by index (O(1)), and are great to use when mutations occur at the end of the array (O(1)), so if we can avoid mutations at the beginning of long arrays, our code will perform best. We can even improve the performance of shift() and unshift() by slicing up the array into multiple parts, with the overhead of having to keep track of indices of elements in each slice separately. Laborious, but depending on the choice of slicing, it might be quite fast.

There's one operation that seems to be unavoidably slow for arrays, though: indexOf(), and its related functions, find(), findIndex() and includes(). The latter three functions are just convenience functions that use indexOf() internally, so their performance is identical, if we ignore the cost of the function passed as the parameter.

The O(n) performance means that an array twice as big will take twice as long to search. We can do better. Much better.

Values, variables and references

You may be aware that JavaScript has two types of values: primitives and objects. Variables can refer to these primitives and objects by assigning those values to a name. When a variable references a value, we say that it contains a reference to the value.

const a = 3;     // variable `a` points to the primitive value `3`
const b = {};    // variable `b` points to an object instance

The difference between primitives (like null, undefined, booleans, strings and numbers) and all the other objects is that primitives are immutable -- only one copy ever exists at any given time within the same environment, and they cannot be changed after they're created. No matter how many times you create the same string or number, the result will be the same:

const a = 3;     // we create the integer `3` and assign it to `a`
const b = 3;     // `3` already exists, so `b` points to the same number

const c = 'hello';   // we create the string 'hello' and assign to `c`
const d = 'hello';   // 'hello' exists, so `d` points to the same string

When we say that we compare references, we mean using strict equality (===), which compares two values to see if they are pointing to (referencing) the same thing. Given the above, we should expect the following to all be true:


    
const a = 'hello';
const b = 'hello';

console.assert(a === b);
console.assert(a === 'hello');
console.assert('hello' === b);
console.assert('hello' === 'hello');

console.log('All good!')

Still with me? Here's where it gets interesting: whenever you create an object (i.e. not a primitive value), JavaScript allocates new memory for the object, regardless of what it contains, and returns a reference to it. A reference is a kind of unique address for that value, a way for the runtime to know where to look for a value when needed.

And yes, arrays are objects too, so the same rules apply. Let's put it to the test:


    
const check = (a, b, msg) => console.log(msg + (a === b ? ': yes' : ': no'));

const a = {};
const b = {};

const c = b;

// check that comparing the value to itself works
check(a, a, 'a and a');
check(b, b, 'b and b');

// what about combinations?
check(a, b, 'a and b');
check(a, {}, 'a and new');
check({}, b, 'new and b');

// what about newly created objects?
check({}, {}, 'new and new');

// what about variables with the same reference assigned?
check(c, b, 'c and b');

Even if the objects contain the same primitive values with the same keys, they will have unique references.

There are two data structures that take advantage of this property to great effect: Set and Map.

Keeping track of references using `Set`

Conceptually, references are numbers that JavaScript uses to find the values in memory for a particular value. Those numbers are hidden inside the internals of the JavaScript engine, but some built-in objects have access to them and this enabled them to provide some unique capabilities.

With arrays, checking that a value is present in it requires searching the elements one by one and seeing if any of the references match the one we're searching for. Set, on the other hand, uses references as numbers to search for a number using binary search trees.

Imagine you have a huge pile of manuscript pages on your desk. You know the pile is ordered, but some of the pages are missing, so you don't have a good idea of where exactly a particular page is, if it is in the pile at all.

You can peek at the top and bottom pages and see that they range between 1 and 1000. Someone asks you to check if page 314 is in the pile. How would you search?

Going from top to bottom would mean it would take you up to 314 steps, so that's not quite efficient. But what if we just pick the middle of the pile to see how close we are?

Let's split the pile roughly in the middle and look at the top page of the bottom half. We discover it's page 562:

|1.....................562.....................1000|
                        ^

Hm, that means it must be in the top part. Let's split the top part again:

|1.........193.........562|
            ^

OK, too far, it's in the lower half now:

          |193...397...562|
                  ^

Close! At this point, would you just flip through the pages to try to find the elusive 314 or continue to split the pile? How do you know when to stop? Which approach would be faster, assuming that splitting the pile takes as much time as flipping a single page? How many steps would you need to finish the task by only splitting the pile?

Let's test this out in code and see how well it performs against a page-by-page search:


    
// this function creates an array of n numbers with random gaps;
// the array is sorted in ascending order and contains unique numbers
const createPile = n => {
  let start = 0;
  const pile = [start];
  while (pile.length < n) {
    start += 1 + Math.floor(Math.random() * 3);
    pile.push(start);
  }
  return pile;
};

// create an array of 1000 numbers
const pile = createPile(1000);

// uses the list splitting technique described above
// returns [steps, index]
const smartSearch = (needle, haystack) => {
  let steps = 0;
  let min = 0;
  let max = haystack.length - 1;
  while (max - min > 1) {
    steps++;
    if (haystack[min] === needle) return [steps, min];
    else if (haystack[max] === needle) return [steps, max];
    const halfway = Math.floor((min + max) / 2);
    if (haystack[halfway] > needle) max = halfway;
    else min = halfway;
  }
  return [steps, null];
};

// uses a classic for loop from start to finish
// returns [steps, index]
const naiveSearch = (needle, haystack) => {
  for (let i = 0; i < haystack.length; i++) {
    if (haystack[i] === needle) return [i + 1, i];
  }
  return [haystack.length, null];
};

console.log('Smart search [steps, index]', smartSearch(314, pile));
console.log('Naive search [steps, index]', naiveSearch(314, pile));

Depending on the random number list, the list might or might not contain the number 314. You'll notice, however, that there's a stark difference in the amount of steps needed to find (or not find) the value in the random number array.

This approach is called the binary search algorithm. It belongs to a whole family of related algorithms that have different speed and memory tradeoffs that can be applied to specific cases for maximum effect. The expected complexity of the binary search algorithm is O(log2 n). In contrast, includes() uses a linear search algorithm, which has a complexity of O(n).

The Set is a data structure that uses those internal IDs within the JavaScript engine to be able to quickly search through the pile for a given reference and determine if it is in the pile or not.

So how does that compare to Array::includes? Here's a benchmark result on my laptop that compares the runtime performance of using either method on an array of 100k integers:

The higher the op/s (operations per second), the better. In this example on Chrome 73, using a Set to determine whether the chosen number is in the list of numbers is more than 1000 times faster! Here's a link to the benchmark so you can test it out yourself.

Of course, this won't always mean that one method is 1000 times faster; it just means that on the scale of 100k elements, Set ends up being 1000 times faster in this specific example. It will depend on the number of elements you have, and the smaller the set, the less noticeable the difference will be. In most cases involving more than, say, a hundred elements, you should see an improvement of orders of magnitude.

When to use `Set`

If the problem you're solving requires testing whether a given value is part of a set of values, then this is the data structure for you. Here are a couple of examples:


    
const bunchOfNumbers = [1,1,2,3,5,5,7,9,11,15,17,17,17,3,2,2,5,5];

// create the set
const set = new Set(bunchOfNumbers);

console.log('does the set contain 5?', set.has(5));
console.log('does the set contain 16?', set.has(16));

// create an array from the set
const unique = Array.from(set);

// the array created from the set contains only the unique values
console.log('unique values', unique);

Creating associations between values with `Map`

If Set lets you easily look up references in a set, Map lets you associate that reference with another, essentially mapping one value to another. Before we get into it, let's try to model this behaviour using an array.

To do this we'll start with an array containing a pair of values, or a tuple. A tuple is an ordered list of values, and in our case, our tuples will contain a key and a value.

Note: for this example to work correctly, the keys in the tuples must be unique across the list, otherwise duplicates will terminate the search on the first occurence.

// we can use any type of reference as the key, so let's create an object
const three = { value: 3 };

// construct the list as an array of arrays
const list = [
  ['one', 'eins'],
  [2, 'zwei'],
  [three, 'drei']
];

Next, we need a lookup function. This will take a list and a key, and return the associated value, or undefined if not found.

const get = (list, key) => {
  const pair = list.find(
    (pair) => pair[0] === key
  );
  return pair !== undefined ? pair[1] : undefined;
};

Let's test it out:


    
const three = { value: 3 };
const list = [
  ['one', 'eins'],
  [2, 'zwei'],
  [three, 'drei'],
  [null, NaN]
];
const get = (list, key) => {
  const pair = list.find(
    (pair) => pair[0] === key
  );
  return pair !== undefined ? pair[1] : undefined;
};

console.log(get(list, 'one'));         // 'eins'
console.log(get(list, 2));             // 'zwei'
console.log(get(list, three));         // 'drei'
console.log(get(list, '2'));           // undefined
console.log(get(list, { value: 3 }));  // undefined
console.log(get(list, null));          // NaN

Since find() is a linear search, its complexity is O(n), which is far from ideal. And this is where Map can really bring in the big guns.

Just as with Set, it contains a has(key) method which returns a true or false based on reference equality. It also has a get(key) method, which allows us to get the associated value by key.

Now you might be thinking, wait, couldn't we just use objects for this? The answer is yes, so long as all of your keys are strings, otherwise you're setting yourself up for failure. If you wanted to have a lookup by string, a plain old object would do just fine:

const germanNumbers = {
  one: 'eins',
  two: 'zwei',
  three: 'drei'
};

const key = 'one';

germanNumbers[key]; // 'eins'

But this strategy falls flat if you try to assign a key that isn't a string, since all object property lookups get converted to a string first. You wouldn't be able to look up a value given an object reference, since objects are cast to strings, resulting in "[Object object]" by default. And you can't differentiate between 2 (a number) and "2" (a string).

This is the reason we had to implement the list as an array of key, value pairs and use === to compare the values. Map works by letting you assign any reference as the key, not just strings.

Additionally, it enjoys the same speed benefits as Set does, so looking up values in the map also has a complexity of O(log2 n). How about a quick race to see just how fast?


    
const get = (list, key) => {
  const pair = list.find(
    (pair) => pair[0] === key
  );
  return pair !== undefined ? pair[1] : undefined;
};

// create a list of 100k numbers, and create values that represent the number
// to 3 significant digits
const list = Array(100000).fill(0).map((_, n) => [n, n.toPrecision(3)]);

// let's repeat the search this many times
const numberOfLoops = 5000;

const target = 31415;

// time how long it takes to find 3141 using linear search
const linearStartTime = Date.now();
for (let i = 0; i < numberOfLoops; i++)
  get(list, target);

console.log(
  'it took ' + (Date.now() - linearStartTime) + 'ms to find the value for array'
);

// what about a map?
const map = new Map(list);

const mapStartTime = Date.now();
for (let i = 0; i < numberOfLoops; i++)
  map.get(target);
console.log(
  'it took ' + (Date.now() - mapStartTime) + 'ms to find the value for map'
);

When to use `Map`

Map can be used to preserve references in cases where you cannot convert a key to a string, or want to avoid casting other primitive values to strings. Its performance is a little worse than object property or array index access (O(log2 n) instead of O(1)).

The most common use case is when you want to create associations between objects. There are generally two ways you can do this:

you can assign the associated value to a property on the object; or
you can generate unique IDs and use those to look up the values.

The first method can create cyclic references, which makes it impossible to convert those objects to JSON strings. The second requires a lot of bookkeeping for each value being referenced, and can often be impractical and slow to implement.

This is where a Map offers a way out:


    
// let's create some frozen object so we can't cheat and just assign spouses
// as object properties
const Jill = Object.freeze({ name: 'Jill' });
const Jane = Object.freeze({ name: 'Jane' });
const John = Object.freeze({ name: 'John' });
const noone = Object.freeze({});

const married = new Map([
  [Jill, Jane], // we create an association for Jill -> Jane
  [Jane, Jill], // we also create a reverse map for Jane -> Jill
  [John, noone] // John is not married, so John -> noone
]);

// who's married to Jill?
console.log(married.get(Jill));

// is John taken?
console.log(married.get(John));

We can create many different associations by just creating more maps, and we never have to modify the objects.

Caveats to consider when dealing with JSON data

While this means that the values being mapped can still be converted to JSON strings, the Maps themselves cannot, since there is no way to serialize references. In this case, generating unique keys is a necessity, but keeping track of which objects need to have their IDs generated can be handled by another Map instance and used in the replacer function of JSON.stringify(). Similarly, a reviver function can recreate the maps. I wrote an article on this that you might find useful:

Extending JSON for fun and profit

Klemen Slavič ・ Oct 28 '18

#javascript

Conclusion

If your data requires you to iterate over a collection in order to check the presence of a key or to look up a value, you might consider using Set and Map to use as a data structure instead of arrays. They offer a fast and safe way to look up values, and you can iterate over them or convert them back into strings if needed.

Next time, we'll have a look at their weakly-referenced siblings, WeakSet and WeakMap!

Improving security by drawing identicons for SSH keys

Klemen Slavič — Sun, 23 Dec 2018 14:55:35 +0000

If you're ever had to generate an encryption key pair or log into a machine using an SSH client configured with visual host keys, you've probably stumbled upon some random ASCII art gobbledygook like this:

The key fingerprint is:
28:b5:b9:9b:15:0d:ac:04:d8:fc:18:fd:af:1b:65:fd you@somewhere.com
+-----------------+
|   +..           |
|  . +...         |
|     +o.o        |
|    .o.=.o .     |
|    . = S.+ .    |
|     . . +.  .   |
|      . o.    E  |
|       +..       |
|      o ..       |
+-----------------+

That ASCII art is the 16-byte (128-bit) fingerprint of the host key, represented as a procedurally generated image. An identicon, if you will. It was introduced in OpenSSH 5.1 as a way to help humans recognize strings of random characters in a fast and reliable way. If you were to mistakenly connect to a machine with a different host key, you'd be more likely to recognize (or rather, fail to recognize) an image of the key and realise your mistake.

Oh, and if you're curious, you can add VisualHostKey yes to your ~/.ssh/config file to enable this in your shell when connecting to other hosts.

Of imbibing clerics and purses of coins

Before we delve into the algorithm that draws this ASCII art, let's all sit in a circle while I tell the tale of the Drunken Bishop.

Bishop Peter finds himself in the middle of an ambient atrium. There are walls on all four sides and apparently there is no exit. The floor is paved with square tiles, strictly alternating between black and white. His head heavily aching—probably from too much wine he had before—he starts wandering around randomly. Well, to be exact, he only makes diagonal steps—just like a bishop on a chess board. When he hits a wall, he moves to the side, which takes him from the black tiles to the white tiles (or vice versa). And after each move, he places a coin on the floor, to remember that he has been there before. After 64 steps, just when no coins are left, Peter suddenly wakes up. What a strange dream!

Source: The drunken bishop: An analysis of the OpenSSH fingerprint visualization algorithm, D. Loss et al.

With that amusing story out of the way, let's analyse how that relates to our little project. With Peter walking around randomly in a room, he leaves behind coins on tiles he has visited. After 64 moves, some tiles will contain no coins, while some will have one or more coins on them. If we represent the grid as a 2D plot of the number of coins in each tile, we get the SSH visual host key!

The grid

We start off by defining the size of the room. Per the algorithm, the room size is a rectangle 17 tiles wide by 9 tiles long.

const WIDTH = 17;
const HEIGHT = 9;

We define the origin to be in the top left corner, numbering the tiles in columns (x) and rows (y), starting at 0:

            1111111
  01234567890123456   
 +-----------------+ x
0|                 |
1|                 |
2|                 |
3|                 |
4|        S        |
5|                 |
6|                 |
7|                 |
8|                 |
 +-----------------+
 y

We mark the starting position with S = [8, 4].

We'll represent the grid of coin counts as a single-dimensional array that lists the values from left-to-right, top-to-bottom order. That way, if we want to look up a value for a particular position, we can use x and y to calculate the index:

const world = Array(WIDTH * HEIGHT).fill(0);
const coins = world[y * WIDTH + x];

The rules of the game

Since we always want to generate the same walking pattern for our bishop given the same fingerprint, we first have to decide how we're going to turn the fingerprint into a list of commands for the bishop to move. We start by defining the four possible moves the bishop can make:

const MOVES = [
  { x: -1, y: -1 }, // ↖
  { x: 1, y: -1 },  // ↗
  { x: -1, y: 1 },  // ↙
  { x: 1, y: 1 }    // ↘
];

We have now defined four commands associated with the integers 0, 1, 2 and 3. If we create a list of these numbers, we can issue these commands in sequence to move the bishop. To do that, we need to split up the fingerprint into pairs of bits.

Let's start with a single byte. A byte is composed of 8 bits:

a9 = 10 10 10 01 => [01, 10, 10, 10]
     ^  ^  ^  ^      ^   ^   ^   ^
#    4  3  2  1      1   2   3   4

For the purposes of this algorithm, we take the pairs of bits and turn them into an array of integers, from least to most significant (numbered by # in the diagram). To do this, we use a bit of bitwise math.

In case you're unfamiliar with why I chose 3 for the mask: 3 === 0b11 in binary form.

const splitByteIntoCommand = byte => ([
  byte & 3,           //  11   11   11  [11]
  (byte >>> 2) & 3,   //  11   11  [11]  11
  (byte >>> 4) & 3,   //  11  [11]  11   11
  (byte >>> 6) & 3    // [11]  11   11   11
]);

A single byte is represented by two hexadecimal characters, so in order to generate the list of commands from a given host key, we need to split the string into pairs to convert them into a single byte:

const parseCommands = hexString => {
  const commands = [];

  // loop over all the characters in the hex string in steps of 2
  for (let i = 0; i < hexString.length; i += 2) {

    // take a pair of hex characters
    const value = parseInt(hexString.slice(i, i + 2), 16);

    // split the byte into 4 commands and append them to the list
    commands.push(...splitByteIntoCommand(value));
  }

  return commands;
}

We now have a function that can take a host key fingerprint as a 32-character hexadecimal string and convert it to an array of commands.

Making things move

Our bishop now has a world to move in and a list of commands we'd like him to perform. Let's make a function that will take the state of the world, the position of the bishop and a single command to calculate the next state.

// ensures the returned value is always min <= x <= max
const clamp = (min, max, x) =>
  Math.max(min, Math.min(max, x));

const nextPosition = (position, move) => {
  // look up direction to move in the rules lookup
  const delta = MOVES[move];

  // return a new position while ensuring the bishop doesn't stray
  // outside of the room
  return {
    x: clamp(0, WIDTH - 1, position.x + delta.x),
    y: clamp(0, HEIGHT - 1, position.y + delta.y)
  };
};

const step = (world, position, command) => {

  // create a copy of the world state
  const newWorld = Array.from(world);

  // drop a coin in the current position
  newWorld[position.y * WIDTH + position.x] += 1;

  // return the new world state and the next position
  return [newWorld, nextPosition(position, command)];
}

To loop through the list of commands, we'll make another function that will run through the commands, starting with an empty room. This function will just return the state of the world after the given number of steps.

Note: the start and end positions are assigned the values 15 and 16 because we want to be able to see where the bishop started and ended the walk.

const simulate = (commands, steps = commands.length) => {

  // start in the middle of the grid
  const start = { x: 8, y: 4 };

  // set the inital position to the starting position
  let position = start;

  // make the initial world empty
  let world = Array(WIDTH * HEIGHT).fill(0);

  // loop over the requested number of steps
  for (let i = 0; i < steps; i++)

    // calculate the next world state and position
    [world, position] = step(world, position, commands[i]);

  // remember the last position calculated
  const end = position;

  // set the starting position to 15
  world[start.y * WIDTH + start.x] = 15;

  // set the ending position to 16
  world[end.y * WIDTH + end.x] = 16;

  return world;
}

Drawing the grid

So far, we just have a flat array of the number of coins in each tile, but we still have to draw the histogram. The algorithm prescribes the characters that represent the possible values of coins in a tile:

0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
   .  o  +  =  *  B  O  X  @  %  &  #  /  ^  S  E

We can encode the table as a single string:

const SYMBOLS = ' .o+=*BOX@%&#/^SE';

To look up the symbol for a particular number of coins, we can just use the index of the string to give us the symbol to use for that count (the symbol for 4 coins is SYMBOLS[4]).

To draw the world, we'll map the integers to the characters in the string above, then draw the grid by splitting the string into equal length of WIDTH.

const draw = (world, width, height, status = '') => {
  // turn coin counts into histogram symbols
  const drawing = world
    .map(cell => SYMBOLS[cell % SYMBOLS.length])
    .join('');

  // draw the top border
  const result = ['+' + '-'.repeat(width) + '+'];

  // loop through each row
  for (let i = 0; i < height; i++)
    result.push('|' + drawing.slice(i * width, (i + 1) * width) + '|');

  // draw the bottom border
  result.push('+' + '-'.repeat(width) + '+');

  // return the lines, joined with a newline
  return result.join('\n'); 
};

Making it interesting

Showing the end result is great, but it would be interesting to see the bishop actually stumble through the room while it's running. Luckily, the simulation lets us specify the number of steps we want the bishop to perform, so we can just draw the state of the world for each step on every animation frame:

const displayDiv = document.getElementById('display');

const run = (commands, steps = 0) => {
  const world = simulate(commands, steps);
  displayDiv.textContent = draw(world, WIDTH, HEIGHT)
    + `\n${steps} steps`;
  if (steps < commands.length)
    requestAnimationFrame(() => run(commands, steps + 1));
};

Put it all together, and we have an amusing toy to play with!

The making of "This is your brain on JavaScript"

Klemen Slavič — Thu, 20 Dec 2018 21:59:28 +0000

The post was originally published on CodePen.

This is a pen that's been on my mind for a long time, ever since I started following the work of Anders Hoff that deals with natural growth patterns and emergent structures. I was fascinated by how ordered structures and interesting patterns emerge when simulating simple physical and biological rules. It didn't really seem intuitive how this worked, so I decided to explore the rules that would generate something like the images Anders generated in his own work.

Deconstructing systems

When I started thinking about how to implement such a system, I started off with a list of axioms that would help me model such a system. I came up with the following:

An individual cell has no knowledge of the world outside of its immediate neighbourhood.
All cells are identical.
There is no guiding force governing cell organization other than Newtonian physics and biological growth.

With these axioms in place, I started thinking about how multicellular organisms work in terms of growth. Every organism starts off with a single cell which then divides into two, held together by binding proteins embedded in each of the cells' membrane. For simplicity, let's model cell division by creating a new cell that is attached to its parent by a spring, which represents the connection between the two new cells:

    o  ==(division)==>  o~o   ==(physics)==>  o—o
  (cell)           (the new pair)       (the spring relaxes,
                                        separating the cells)

In this diagram, a squiggly line represents a spring under tension, which pushes the cells apart after relaxation. Sounds simple enough. But what about subsequent divisions? Let's take a look at the next stage of development:

    o—o   ==(division)==>   o~[o~o]
      ^(this cell divides)     ^(the new cell appears)

A subsequent division here causes tension in both springs, which will cause the cells to push against each other to resolve the tension. If we use our intuition to model the physics, we expect the tensions to resolve in one of two ways:

                    o
                   / \
   o~[o~o]   =>   o   o   (when the new cell is a little bit
                                    above the line)

   o~[o~o]   =>  o—o—o    (when the new cell is exactly along
                          the line between the original cells)

NOTE: Here we assume that the spring's direction can freely change, as proteins can flow freely along the membrane in any direction.

So far, it seems like a sensible description of growth for a line of cells. We do have to set a couple of physical rules to the system to model it sensibly:

Growth happens in a viscous medium which preventing cells from gliding across space without friction.
Cells cannot occupy the same space at the same time, so cells not connected will still repel each other if too close.

Putting it all together

So let's recap the rules:

Cells can be connected by springs, tending to keep connected cells at a fixed distance.
A cell can divide, which creates a pair of interconnected cells attached to themselves and their original neighbours.
Cells are contained in a viscous medium.

We now have all the building blocks we need to build up the models and equations that will govern the evolution of this system.

The cell

Let's start by defining all the properties a cell has:

class Particle {
  constructor(position) {
    this.position = position;
    this.force = new Vec2d(0, 0);
  }
}

The position and force properties are both instances of Vec2d which I use for vector math. We only need those two because we will assume that the medium the cell is embedded in is so viscous that the velocity of the particle drops to 0 as soon as the force ceases to act on the cell (think honey or molasses). During a simulation step, we sum up all the forces acting on the cell, move the particle in the direction of the force and then reset the force property back to 0 for the next step.

The world

We also want to create an environment in which the cells live:

class Simulation {
  constructor(particles) {
    this.particles = particles;
  }
  // ...

Here, we'll keep track of the particles contained in the world. And, to make things simple, we'll assume that particles next to each other in the array are also connected by a spring. That way, when we insert an element into the middle of the array to simulate cell division, the cell will implicitly be connected to its neighbouring cells:

[a,b,c,d] ==> a—b—c—d

But let's make things interesting and assume that cells connect in a circular structure and the last element in the array is attached to the first one:

              a—b
[a,b,c,d] ==> | |
              d—c

So this means that for every element n we have two neighbours n-1 and n+1 connected by springs. If the value exceeds the range [0, particles.length - 1] we wrap the values so they fit the array.

Constants

We define a couple of static constants on the simulation that defines a couple of important values:

  static get NODE_DISTANCE()      { return 2; }
  static get DISTANCE_CUTOFF()    { return this.NODE_DISTANCE * 8; }
  static get SPRING_COEFFICIENT() { return 0.02; }
  static get REPULSION_FORCE()    { return 4; }

Let's go over these constants to get a better understanding about what they signify:

NODE_DISTANCE: represents the distance (in pixels) between cells that would result in a completely relaxed spring
SPRING_COEFFICIENT: represents the spring's stiffness; the higher the number, the more force is exerted when the spring is stretched or compressed
REPULSION_FORCE: the force of repulsion between individual cells, regardless if the're connected or not
DISTANCE_CUTOFF: represents the maximum distance (in pixels) the cells repel each other; this is to prevent the repulsion from adding up significantly when large numbers of particles are generated.

Of course, these values were chosen completely arbitrarily and through trial and error; you might want to experiement with different values to see how they affect the final shape of the structure.

Calculating forces

We now need to define two types of forces that act on pairs of cells: the spring force and the mutual repulsion.

  static getSpringForce(a, b) {
    let f = Vec2d.sub(a.position, b.position),
        m = f.mag;
    return f.norm().scale((this.NODE_DISTANCE - m) * this.SPRING_COEFFICIENT);
  }

The first function takes two cells and calculates the force that results from the spring acting on the first particle. The equation is simply Hooke's law: F = k(l - m), where l is the relaxed length of the spring (NODE_DISTANCE) and m is the distance between the cells. To calculate the force on the second cell, we just negate the force as prescribed by Newton's Third Law without having to recalculate it.

  static getRepulsionForce(a, b) {
    let f = Vec2d.sub(a.position, b.position),
        m = f.mag;
    return m > this.DISTANCE_CUTOFF ? f.reset(0, 0) : f.norm().scale(this.REPULSION_FORCE / (m * m));
  }

For the repulsion force, we calculate the distance between the cells (m) and use the Inverse-square law to create a force that repels cells from each other: F = k / m^2 (k == REPULSION_FORCE). Because of the inverse square falloff, the cell's influence on others declines quickly with distance, but is very intense when the distance between cells decreases towards 0.

Applying forces and moving particles

Let's move on to going through the particle list and calculating the forces. We make a step(dT) function that will allow us to advance time in the world we've constructed.

Let's start with the beginning:

  step(dT) {
    let t = dT / 4;

Here, we just scale down the time step (passed into the simulation as milliseconds). This can be tuned up or down to slow or speed up the simulation, but if the step is too large, it can lead to instabilities in the simulation. (For a good explanation of errors, see numerical stability in Euler's method.)

    // process mutual repulsion
    for (let i = 0; i < this.particles.length - 1; i++) {
      for (let j = i + 1; j < this.particles.length; j++) {
        // mutual deflection force
        let a = this.particles[i], b = this.particles[j];
        let f = Simulation.getRepulsionForce(a, b);
        a.force.add(f);
        b.force.sub(f);
      }
    }

First, we calculate the repulsion forces between all pairs of cells. The force that getRepulsionForce(a, b) returns is the force acting on particle a, so we add that to the force collector a.force. Due to Newton's Second Law, we must subtract that same force from b.force. This optimization allows us to cut the number of iterations in half, so that this part runs in O(n^2/2) time instead of O(n^2).

    // process linkage
    for (let i = 0; i < this.particles.length; i++) {
      let a = this.particles[i], b = this.particles[(i + 1) % this.particles.length];
      let f = Simulation.getSpringForce(a, b);
      a.force.add(f);
      b.force.sub(f);
    }

This part goes through the chain of elements starting with the first element and calculating the force between it and the next one in the chain. For the last element, it assumes connection with the first one in the array (hence why (i + 1) % this.particles.length). Again, Second Law requires us to add the force to the first cell and subtract from the second.

    // apply movement
    this.particles.forEach(particle => {
      let f = particle.force.clone().scale(t);
      particle.position.add(f);
      particle.force.reset(0, 0);
    });
  }

Finally, we do a bit (okay, A LOT) of cheating: instead of calculating the drag, friction, forces, and integrating twice over the time step to calculate the new position, we instead scale the sum of forces on the particle by the time step and reset the cell's force collector to 0. This simulates the viscosity of the medium while still allowing the cells to move an acceptable distance. (The approach is similar to Euler's method of integration, with the same tradeoff between accuracy and simplicity, and the reason why we want to keep the step size small.)

Initial state

We decided to link the ends of the string of cells into a circular shape, so we need to generate the initial configuration of cells within a circle. We set up an instance of the simulation with a number of particles and a given radius:

// set up the initial world, just start with a circle of 40 particles
var simulation = (() => {
  let n = 40, particles = [], r = 40;
  for (let a = 0; a < 2 * Math.PI; a += 2 * Math.PI / n) {
    particles.push(
      new Particle(
        new Vec2d(
          Math.cos(a) * r,
          Math.sin(a) * r
        )
      )
    );
  }
  return new Simulation(particles);
})();

This returns an instance of our simulated world, filled with 40 particles in a circle of radius 40.

Managing the lifetime of the simulation

We've made our world of cells, now we need to make time run. We set up a requestAnimationFrame loop (the tick(timestamp) function) that will call our simulation step to update physics as time ticks by:

// loop stuff
var lastTime = null, lastGenerated = null;

var tick = timestamp => {
  if (!lastTime) lastTime = timestamp;
  let elapsed = clamp(0, 16, timestamp - lastTime);
  lastTime = timestamp;

Here, we calculate the time that elapsed since last time tick() was called. We limit elapsed to be between 0 and 16 to keep the simulation reasonably stable.

  simulation.step(elapsed);
  update(simulation.particles);

We call step(elapsed) to advance the simulation by this number of milliseconds. We also call the update function that renders the array of particles using D3.

Making the cells divide

  if (!lastGenerated) lastGenerated = timestamp;
  // generate a new particle every 60ms
  if (simulation.particles.length < 800 && timestamp - lastGenerated > 60) {
    let idx = Math.floor(Math.random() * simulation.particles.length),
        nextIdx = (idx + 1) % simulation.particles.length,
        a = simulation.particles[idx],
        b = simulation.particles[nextIdx];
    simulation.particles.splice(
      idx,
      0,
      new Particle(
        a.position.clone().sub(b.position).scale(0.5).add(a.position)
      )
    );
    lastGenerated = timestamp;
  }

This part deals with creating a new cell within the array of particles. Every 60ms it will choose a random index within the array to insert a new cell between the chosen index and the next one. The new cell's position will be halfway between the two cells ((a + b) / 2), which is what we described above (o—o ==> o~o~o) and creates tension in the chain where the cell is inserted, because the distance between the three cells is now half of what it was before cell division.

  requestAnimationFrame(tick);
};

requestAnimationFrame(tick);

Finally, we make sure to call requestAnimationFrame when tick is done and run it for the first time.

D3 rendering

The D3 stuff is pretty straightforward for anyone used to the library, but in case you were wondering, I used the General Update Pattern that Mike Bostock recommends using.

// D3 stuff

var container = document.querySelector('#display'),
    canvas = d3.select(container)
      .append('svg')
      .attr({ width: container.offsetWidth, height: container.offsetHeight });

var update = data => {
  let w2 = container.offsetWidth / 2, h2 = container.offsetHeight / 2;
  let links = canvas.selectAll('line').data(data);
  let particles = canvas.selectAll('circle').data(data);

  // update the links
  links.enter().append('line');

  links.attr({
    x1: d => d.position.x + w2,
    y1: d => d.position.y + h2,
    x2: (d, idx) => data[(idx + 1) % data.length].position.x + w2,
    y2: (d, idx) => data[(idx + 1) % data.length].position.y + h2,
  });

  links.exit().remove();

  // update the particles
  particles.enter().append('circle');

  particles.attr({
    cx: d => d.position.x + w2,
    cy: d => d.position.y + h2,
    r: 3
  });

  particles.exit().remove();
};

Conclusion

All in all, the system described uses only a couple of very rudimentary rules, and the added randomness of cell division makes the system react in unpredictable ways. The resulting patterns, however, appear to emerge as if the "organism" were told to grow in a certain way, even though the code itself exerts no such pressure. It is all self-organisation as a consequence of the laws of nature themselves.

Your move, Creationists. :)

Some lists are not like the others

Klemen Slavič — Thu, 13 Dec 2018 23:29:55 +0000

So far in this series, we've been dealing with arrays as natural containers of values that allows us to treat them as a sequence. But what is an array, really? What makes them tick? Let's find out!

Impostors, impostors everywhere

In JavaScript, an array is a special type of object with a magical property called length and integer strings for keys, starting with 0. A special syntax allows you to create an array by specifying the sequnce of values in square brackets:

const realArray = ['a', 'b', 'c'];

If you look at an array as any other object in JavaScript, you'll notice that you'll get approximately the same shape as the following object:

const fakeArray = {
  '0': 'a',
  '1': 'b',
  '2': 'c',
  length: 3
};

This array will work just fine if we loop over it. 🎵 Don't believe me? Ask the dishes! 🎵


    
const printArray = (name, arr) => {
  const report = [];
  for (let i = 0; i < arr.length; i++)
    report.push(i + " => '" + arr[i] + "'");
  console.log(name, '[' + report.join(', ') + ']');
};

const realArray = ['a', 'b', 'c'];

const fakeArray = {
  '0': 'a',
  '1': 'b',
  '2': 'c',
  length: 3
};

printArray('real array', realArray);
printArray('fake array', fakeArray);

Speaking of ducks, this is called duck typing, if you've ever wondered where the term comes from or what it means. Languages support duck typing in various forms using interfaces, which enables loose coupling while still enforcing object shapes.

Some JavaScript and DOM objects are also array-like but aren't real arrays, like arguments or NodeList. Some libraries took the dynamic nature of objects even further, and appended methods directly onto arrays for convenience (hello, jQuery!).

As long as it looks like an array (and quacks like an array), any code using it will be none the wiser. Well, at least the code that uses integer keys and length to loop over the properties. It won't work with for...of, Array.from() or spreads, which is what we're going to fix next.

Iterators, iterables and `Symbol.iterator`

To improve our disguise, we'll implement the API required for JavaScript to provide iteration capability on our fake array. To do this, let's first take a look at what an iterator is.

An iterator is any object with a method called next(). When you want to get the values from the iterator, you call next() to get an object with two properties:

value: the next value in sequence,
done: a boolean that tells you whether there's more values to give

Given those requirements, let's build a function that creates an iterator that counts from 1 to 5:


    
const createIterator = max => { // take an upper bound to count to
  let count = 1;                // set the initial value to 1
  const iterator = {            // create an object...
    next() {                    // ...that has a next() method
      if (count > max)          // if the current value exceeds the upper bound...
        return { done: true };  // ...tell the caller that there are no more values
      const value = count;      // if not, grab the current value...
      count += 1;               // ...increment the counter...
      return {                  // ...and return an object
        value,                  // with the current value
        done: false             // and tell the caller we're not done yet
      }; 
    }
  };
  return iterator;              // oh yeah, and give the iterator to the caller.
};

const iterator = createIterator(5);

console.log(iterator.next());   // 1
console.log(iterator.next());   // 2
console.log(iterator.next());   // 3
console.log(iterator.next());   // 4
console.log(iterator.next());   // 5
console.log(iterator.next());   // no more values!

Okay, that looks kinda painful to use directly. You could write a while() loop, but it's easy to accidentally cause an infinite loop or have a off-by-one error. We can make this easier to use by making an iterable object.

An iterable object can be consumed in a for...of loop, by Array.from() or the spread operator.

The difference between an iterator and an iterable is that an iterable returns an iterator when calling a specially named property called Symbol.iterator. That is quite a mouthful, so let's write it down step by step:


    
const createIterator = max => {
  let count = 1;
  const iterator = {
    next: () => {
      if (count > max)
        return { done: true };
      const value = count;
      count += 1;
      return {
        value,
        done: false
      }; 
    }
  };
  return iterator;
};

const createIterable = max => {    // start by taking the upper bound
  const iterable = {               // create an object...
    [Symbol.iterator]: () => {     // ...with a [Symbol.iterator] method...
      return createIterator(max);  // ...that creates and returns an iterator
    }
  };
  return iterable;                 // finally, return the iterable
};

// create an iterable that can count to three
const oneToThree = createIterable(3);

// for...of?
for (const n of oneToThree)
  console.log(n);

// spreading?
console.log([...oneToThree]);

So, in order for our fake array to become iterable, we have to add a method that will return an iterator:


    
const fakeArray = {
  '0': 'abc',
  '1': 'def',
  '2': 'ghi',
  '3': 'jkl',
  length: 4,
  [Symbol.iterator]: () => {          // implement the iterable interface
    let i = 0;                        // start counting at 0
    return {                          // return an object...
      next() {                        // ...with a next() method (the iterator)
        const value = fakeArray[i];   // get the current value
        i += 1;                       // increment the counter
        return i <= fakeArray.length  // if we're not out of bounds yet...
          ? { value, done: false }    // ...give the value back...
          : { done: true };           // ...else, signal we're done.
      }
    };
  }
};

for (const element of fakeArray)
  console.log(element);

const realArray = [...fakeArray];
console.log(realArray);

There are three more iterable methods that need to be implemented in order for our fake array to behave as close to the real one as possible:

keys(): returns an iterable for the array's keys,
values(): returns an iterable for the array's values,
entries(): returns an iterable that returns arrays of key-value pairs ([key, value]).

I'll leave it as an exercise for the reader to implement those, along with the other array methods, like map(), filter(), slice(), etc.

There's one last thing to be aware of, though: you'll find it very hard to fool code using Array.isArray() and instanceof Array to check for array types. For our purposes, we only wanted to replicate the behaviour of arrays, not fool JavaScript into believing it's an actual array when it really isn't.

Arrays: the fast and easy parts

Because of the way arrays are constructed, there are certain properties that make arrays preferrable over other data structures in some situations. Arrays are wonderful data structures when you want:

a known amount of values in a list,
to preserve the sequence of values,
access values directly via index positions in the list,
a fast way to append to or pop elements off the end of the list.

If those properties match well with the requirements of the problem you're trying to solve, then arrays are a perfect fit. Go ahead and use them! But that last property is mentioned specifically because there's a fundamental trade-off made there you may not be aware of. Let's take a look at the reason why that would be the case.

Arrays: the costly parts

Our fake array looks like this:

const a = {
  '0': 'first',
  '1': 'second',
  '2': 'third',
  length: 3
};

What would it take to append a new value onto that object?

a['3'] = 'fourth';    // set index 3 to equal the 'fourth' value
a.length = 4;         // update length to 4

With 4 elements in the array, how would we popp the last element off?

delete a['3'];        // remove index 3
a.length = 3;         // update length to 3

It only takes two changes to make each of those operations. So what if we decided to shift the first element off the start of the array? Well, let's try:

const first = a['0'];  // we take the first element out
a['0'] = a['1'];       // we move the second element into first position ...
a['1'] = a['2'];       // ... the third element into second position...
delete a['3'];         // ... and delete the third element
a.length = 2;          // finally, we update the length to 2

// this is what the array looks like now:
{
  '0': 'second',
  '1': 'third',
  length: 2
}

Now think about what this means in terms of the number of operations when the size of the array grows. If we have n elements in the array, how many operations do we need to perform each of the following:

get the number of values in the collection,
get a specific value by index position from the array,
append a single value,
prepend a single value,
remove a value off the end of the array,
remove a value off the start of the array,
searching for a value in the array.

Let's go through them one by one.

`length`

The first one is easy to determine; the array already has a value stored that keeps the count of values: length. Accessing it costs us about the same as accessing an object property:

a.length;

This operation is independent of the array size, since we don't have to count the size of the collection each time we access that property, so let's assign that a cost of 1.

`[index]`

The second one is similar to the first; accessing a string property on a JavaScript object carries a fixed cost similar to length, so let's assign that the same cost, 1.

`push()`

Appending a single value requires two updates: assigning a value to a new index and adding 1 to the length property. That makes the cost equal to 2.

`pop()`

Removing a value from the end of the array also requires two updates (deleting the last index and subtracting 1 from length), so it gets a cost of 2.

`unshift()`

Prepending the array with a value is a little trickier. For each element added to an array of length n, we have to:

increment all index positions of existing values (n operations)
assign the new element to the 0 index (1 operation)
increment length by 1 (1 operation)

Sum it all up, and you get a total cost of n + 2.

`shift()`

Removing a value off the start of the array is similar in cost. For each element removed from an array of n element:

store the first element (1 operation)
decrement all index positions of the rest of the values (n - 1 operations)
decrement length by 1 (1 operation)

The total cost therefore comes down to n + 1.

`indexOf()`

Searching is a more interesting problem to estimate, since it depends on three factors: where you start searching, the way you iterate over the indices and where the found value is. If we could take a reasonable guess about the probable location of the value, we might improve our odds, but let's say that the value has an evenly spread probability among n indices. Assuming we start from the beginning of the array, we have to:

take value at current index (each loop costs 1 operation)
compare reference to the value at selected index
- if found, return index
- else, select next index

In the best case scenario, the first element is the value we're looking for, so we have a total of 1 loop. In the worst case, we would have to reach the very last index to find the value, so the cost would be n. If we average out all the possible scenarios and their costs, we get an average of n / 2 operations.

For reference, if we have to go through a collection of items one at a time without skipping any elements in a sequence to guarantee finding the element, it's called a linear search. This will be important later.

The final cost table

So, let's break down the costs again:

| Array method | Cost  |
|--------------|-------|
| length       |     1 |
| push()       |     2 |
| pop()        |     2 |
| shift()      | n + 2 |
| unshift()    | n + 1 |
| indexOf()    | n / 2 |

And in case you wanted to get a feel for how these methods perform in your chosen JavaScript environment, try out this benchmark that illustrates the difference in performance on an array of 1000 elements.

The Big (and Scary) O Notation

You may have heard of Big O when people discuss runtime performance of algorithms. It is a mathematical expression that allows you to compare the time it takes for algorithms to complete a task given the size of the input, n.

Think of it as a rating, like the ratings we assign to chess players. A rating allows you to compare two chess players to see how well matched they would be if they ever played a match. A chess player with a high rating would probably wipe the floor with someone from a lower tier (assuming they played enough games for their ratings to reflect their real skill).

We can use Big O as a rating for algorithms, with a simple rule: smaller is faster.

Big O is written as O(...) where the parens contain an expression involving the size of the input. To derive this expression, you can count how many steps an algorithm performs for a given size n. Let's update our table by using the Cost column as our starting point:

| Array method | Cost  | Big-ish O |
|--------------|-------|-----------|
| length       |     1 | O(1)      |
| push()       |     2 | O(2)      |
| pop()        |     2 | O(2)      |
| shift()      | n + 2 | O(n + 2)  |
| unshift()    | n + 1 | O(n + 1)  |
| indexOf()    | n / 2 | O(n / 2)  |

There is a rule for Big O: we don't care about small inputs, we only want to know how to compare performance for big inputs. You know, inputs the size of bank bailouts, as n approaches ridiculous. There are three steps to perform when reducing the expression to Big O:

expand all expressions,
anything times n^x is just n^x (a * n^x ~ n^x)
cross out everything but the highest power of n

Note: this is a very naive and simplistic reduction of the limit theorem. Formally, the task is to simplify the expression for lim(n->Inf) f(n). The steps above are broadly useful for most algorithms you may encounter on a daily basis.

Let's take a hypothetical example. If we have a list of n values. We have to compare each element to every other element in the list, and we have to go through the entire list twice. To do that, we need to:

for every element, we perform n-1 comparisons (cost 1 each),
we repeat this for n elements (n times the cost of step 1),
repeat the process once more (double the cost – 2).

So our final cost is 2 * (n * (n - 1)) operations. First we expand that expression by multiplying the two factors:

2 * (n * (n - 1)) = 2n * (n - 1) = 2n^2 - 2n

We cross out all factors of powers of n:

2n^2 - 2n  ~~~  n^2 - n

And finally, we cross out everything but the highest power of n, and we're left with Big O notation:

n^2 - n   ~~~  O(n^2)
      ^ ignore

Now we can derive real Big O values for our array methods:

| Array method | Cost  | Big O |
|--------------|-------|-------|
| length       |     1 | O(1)  |
| push()       |     2 | O(1)  |
| pop()        |     2 | O(1)  |
| shift()      | n + 2 | O(n)  |
| unshift()    | n + 1 | O(n)  |
| indexOf()    | n / 2 | O(n)  |

Anticipating problems

Big O allows us to estimate how long something will take when the input grows in size. For O(1), no matter how large the input grows, it should not noticeably impact our performance (unless limited by hardware or the JS runtime).

It also allows us to estimate how slow our program will be when the size of our input data grows. Let's say that generating a report currently takes 30 seconds for a thousand customers. If our report generation complexity is O(n), then growing the company by 100% should increase that time by 100% as well. This may or may not be acceptable, but at least you can now anticipate problems and predict how soon you might be hitting your limits.

Sometimes, algorithms can be changed to leverage other types of data structures that perform better than arrays on some tasks, making O(n) seem painfully slow in comparison.

Wrapping up

We've now seen how the array works in JavaScript. By carefully reasoning about what the built-in methods do, we've been able to derive Big O performance envelopes that we can use to estimate how fast our programs will run when using arrays as the primary data structure.

Up next, we'll look at some of the other built-in data structures and see how we can improve on some of the shortcomings of arrays, and dip our toes into more interesting problems.

Until next time!

Photo by Mike Alonzo on Unsplash

So you have a bunch of things to do. Why not build a pipeline?

Klemen Slavič — Sun, 18 Nov 2018 00:39:32 +0000

When developing software, it's a good idea to write code that reads well. And, like any good storyteller, you want to leave out details that aren't important. You also want to leave breadcrumbs for the reader to get at the details when they need to.

Sit back, grab a hot drink, and let's get straight into it.

The elements of a good story

What do stories, procedures, processes, functions and algorithms have in common?

They all have a start, a middle and an end.

When we describe procedures, we start by describing the prerequisites and materials that we need to execute, the inputs of the procedure. We describe the steps needed to execute the procedure. When all is said and done, the description also includes the expected result, the output.

If you're thinking that that sounds remarkably like a function call, you're absolutely correct. But if that deduction escapes you, don't worry, this article is a process by which you'll become familiar with the concept. 😁

Defining inputs

Let's put our cosplay suit on. Your role in this story will be that of an analyst who is tasked with delivering reports on selected subreddits. You will be given a list of subreddits to generate several types of reports based on the page.

Your task will be to generate a few reports for every given subreddit front page:

the median of the word count for each post
the median of the number of comments for each post
the ratio of posts with images attached vs. all posts

As for the URL, take your pick, but in this example, we'll be using /r/dataisbeautiful:

https://www.reddit.com/r/dataisbeautiful/

When you're done having a look, try out the JSON URL so you'll get a feeling for how the data is structured:


    
const fetch = require('node-fetch');


    
const url = 'https://www.reddit.com/r/dataisbeautiful.json';
fetch(url)
  .then(response => response.json())
  .then(json => console.log(json));

Defining steps

So first things first – we need to break the problem down into well-defined steps. The more granular, the easier they will be to understand, debug and reuse. The rule of the game is do one thing and do it well.

Let's take the first report and write down the steps. The more granular, the better.

generate URL
fetch JSON data
extract posts
extract post text and title for each post
generate a word count for each text
calculate median value for all texts

Ideally, you'd have tests for each of these steps. For brevity, I'm omitting the tests in this article, but this would definitely not fly if I were reviewing your code in a code review!

Step 1: generate URL

This one is simple: take a Reddit URL, remove the trailing slash (if any) and append the .json string.

const getRedditJSONUrl = url => url.replace(/\/?$/, '.json');

Step 2: fetch JSON data

A simple call with fetch and converting the response to JSON does the trick.

const fetchData = url => fetch(url).then(response => response.json());

Step 3: extract posts

We know that every page contains the data.children property which holds the array of posts we're interested in.

const extractPosts = redditPage => redditPage.data.children;

Step 4: extract post text for each post

The title in each post can be found in the data.title attribute, and the text in data.selftext. We'll concatenate them using a newline, \n.

const extractPostTextAndTitle = post => post.data.title + '\n' + post.data.selftext;

Step 5: generate word count for each text

This one is a bit tricky. There's no quick way to reliably count the number of words, so we're going to use a more sophisticated utility function from NPM, @iarna/word-count.

Note that we are still creating a function that wraps the library function. This is to isolate ourselves from the library in case we need to change out the implementation, or if the function call changes from refactoring on our side of the code.

const _wordCount = require('@iarna/word-count');

const countWords = text => _wordCount(text);

Step 6: calculate the median

To calculate the median of a set of numbers, we order them from smallest to largest. The median is the value that splits the ordered set into two equal halves. For sets with an odd count of values, it will be the middle value. For evenly counted sets, it will be the midpoint between the two values in the center.

Here's the median value of an odd and an even set of numbers:

[1 1 2 3 5 8 13] ~ size = 7
       ^ median = 3

[1 1 2 3 5 8 13 21] ~ size = 8
        ^ median = (3+5)/2

Here's the implementation:

const numberValueSorter = (a, b) => a - b;

const calculateMedian = list => {
  // an empty list has no median
  if (list.length == 0) return undefined;

  // sort the values
  const sorted = Array.from(list).sort(numberValueSorter);

  if (sorted.length % 2 == 0) {
    // we're dealing with an even-sized set, so take the midpoint
    // of the middle two values
    const a = sorted.length / 2 - 1;
    const b = a + 1;
    return (list[a] + list[b]) / 2;
  } else {
    // pick the middle value
    const i = Math.floor(sorted.length / 2);
    return list[i];
  }
}

Connecting the steps

Now that we have the steps in place, let's just write out the code in classic, imperative style so we get a better understanding of what the process looks like.


    
const fetch = require('node-fetch');
const _wordCount = require('@iarna/word-count');

const getRedditJSONUrl = url => url.replace(/\/?$/, '.json');
const fetchData = url => fetch(url).then(response => response.json());
const extractPosts = redditPage => redditPage.data.children;
const extractPostTextAndTitle = post => post.data.title + '\n' + post.data.selftext;
const countWords = text => _wordCount(text);
const numberValueSorter = (a, b) => a - b;
const calculateMedian = list => {
  if (list.length == 0) return undefined;
  const sorted = Array.from(list).sort(numberValueSorter);
  if (sorted.length % 2 == 0) {
    const a = sorted.length / 2 - 1;
    const b = a + 1;
    return (list[a] + list[b]) / 2;
  } else {
    const i = Math.floor(sorted.length / 2);
    return list[i];
  }
}


    
const URL = 'https://www.reddit.com/r/dataisbeautiful/';

// because some of the steps require resolving Promises, we'll
// use an async function so we can await the result
(async () => {
  // step 1
  const jsonURL = getRedditJSONUrl(URL);

// step 2 – needs awaiting
  const pageData = await fetchData(jsonURL);

// step 3
  const posts = extractPosts(pageData);

// step 4 – we need to map over the elements of the array
  const texts = posts.map(extractPostTextAndTitle);

// step 5 - same here
  const wordCounts = texts.map(countWords);

// step 6
  const median = calculateMedian(wordCounts);

console.log('Median word count for ' + URL, median);
})();

As far as storytelling goes, the flow seems all over the place. Instead of simply listing the steps, we call each step in turn, saving the intermediate result and handing the result to the next step.

There's also a couple of gotchas in that story; some require awaiting results, some require wrapping calls with map to process each item.

What if we could just connect these steps into something that would pass these results down the chain? he asks with a twinkle in his eye.

Enter the pipeline

Here's where we need to introduce a new concept – the pipeline function. Let's start by analysing our original process that takes a subreddit URL and generates a median word count for the page:

const getMedianWordCountReport = async subredditUrl => {
  /* something something spaceship */
  return 'voilá!';
};

We said that our process is defined by the six steps described above. Let's assume pipeline exists and write the fantasy code that lets us create the process function from sequence of steps:

const getMedianWordCountReport = pipeline(
  getRedditJSONUrl,
  fetchData,
  extractPosts,
  map(extractPostTextAndTitle),
  map(countWords),
  calculateMedian
);

const URL = 'https://www.reddit.com/r/dataisbeautiful/';

// it's an async function, so we need to wait for it to resolve
getMedianWordCountReport(URL)
  .then(median =>
    console.log('Median word count for ' + URL, median)
  )
  .catch(error => console.error(error));

Ah, but what about that map() function there? It's just the Array::map function changed so that it is curried with the mapping function before accepting the array:

const map = mapper => array => array.map(mapper);

So far, so good. We now know what the function should do, we just need to define it. Let's start by defining its signature:

const pipeline = (...steps) => {  // take a list of steps,
  return async input => {         // return an async function that takes an input,
    return input;                 // and eventually returns a result
  };
};

We've created a function that takes an arbitrary number of functions (steps) and returns an async function, the process function.

For every step, the function should take the last intermediate result, feed it to the next step, and save that intermediate result.

If there are no more steps, return the last intermediate result.

Ready? Go!

const pipeline = (...steps) => {    // take a list of steps defining the process
  return async input => {           // and return an async function that takes input;
    let result = input;             // the first intermediate result is the input;
    for (const step of steps)       // iterate over each step;
      result = await step(result);  // run the step on the result and update it;
    return result;                  // return the last result!
  };
};

You might be thinking, "no, that can't be it. Is that really all of it?"

Yep. Try it yourself:


    
const fetch = require('node-fetch');
const _wordCount = require('@iarna/word-count');

const getRedditJSONUrl = url => url.replace(/\/?$/, '.json');
const fetchData = url => fetch(url).then(response => response.json());
const extractPosts = redditPage => redditPage.data.children;
const extractPostTextAndTitle = post => post.data.title + '\n' + post.data.selftext;
const countWords = text => _wordCount(text);
const numberValueSorter = (a, b) => a - b;
const calculateMedian = list => {
  if (list.length == 0) return undefined;
  const sorted = Array.from(list).sort(numberValueSorter);
  if (sorted.length % 2 == 0) {
    const a = sorted.length / 2 - 1;
    const b = a + 1;
    return (list[a] + list[b]) / 2;
  } else {
    const i = Math.floor(sorted.length / 2);
    return list[i];
  }
}


    
const map = mapper => array => array.map(mapper);

const pipeline = (...steps) => {
  return async input => {
    let result = input;
    for (const step of steps)
      result = await step(result);
    return result;
  };
};

const getMedianWordCount = pipeline(
  getRedditJSONUrl,
  fetchData,
  extractPosts,
  map(extractPostTextAndTitle),
  map(countWords),
  calculateMedian
);

const URL = 'https://www.reddit.com/r/dataisbeautiful/';

getMedianWordCount(URL)
  .then(median => console.log('Median word count', median));

Streamlining the pipeline

We have a few bends in the pipeline that we'd like to straighten out. There is a point where the result changes from a single value to a list of values (extractPosts) and back again (calculateMedian). It would be nicer if we could group together functions that have to deal with individual items.

In order to do that, let's create a composition function that will take a number of steps meant to process a single value and string them together to operate on a list of values:

const map = (...mappers) =>                 // take an array of mappers,
  array =>                                  // and return a function that takes an array;
    array.map(                              // map each item of the array
      item => mappers.reduce(               // through a function that passes each item
        (result, mapper) => mapper(result)  // and runs them through the chain of mappers
      )
    );

Now, there is a caveat to this function: the mapper functions passed into this map function must be synchronous. For completeness, let's assume that each mapper might be an async function and should be treated accordingly.

const map = (...mappers) =>
  async array => {                      // we now have to return an async function
    const results = [];
    for (const value of array) {        // for each value of the array,
      let result = value;               // set the first intermediate result to the first value;
      for (const mapper of mappers)     // take each mapper;
        result = await mapper(result);  // and pass the intermediate result to the next;
      results.push(result);             // and push the result onto the results array;
    }
    return results;                     // return the final array
  };

Now that we've solved that edge case, we can reformulate our process function by grouping the two single-item functions into a single step:


    
const fetch = require('node-fetch');
const _wordCount = require('@iarna/word-count');

const getRedditJSONUrl = url => url.replace(/\/?$/, '.json');
const fetchData = url => fetch(url).then(response => response.json());
const extractPosts = redditPage => redditPage.data.children;
const extractPostTextAndTitle = post => post.data.title + '\n' + post.data.selftext;
const countWords = text => _wordCount(text);
const numberValueSorter = (a, b) => a - b;
const calculateMedian = list => {
  if (list.length == 0) return undefined;
  const sorted = Array.from(list).sort(numberValueSorter);
  if (sorted.length % 2 == 0) {
    const a = sorted.length / 2 - 1;
    const b = a + 1;
    return (list[a] + list[b]) / 2;
  } else {
    const i = Math.floor(sorted.length / 2);
    return list[i];
  }
}
const pipeline = (...steps) => {
  return async input => {
    let result = input;
    for (const step of steps)
      result = await step(result);
    return result;
  };
};


    
const map = (...mappers) => async array => {
  const results = [];
  for (const value of array) {
    let result = value;
    for (const mapper of mappers)
      result = await mapper(result);
    results.push(result);
  }
  return results;
};

const getMedianWordCount = pipeline(
  getRedditJSONUrl,
  fetchData,
  extractPosts,
  map(
    extractPostTextAndTitle,
    countWords
  ),
  calculateMedian
);

const URL = 'https://www.reddit.com/r/dataisbeautiful/';

getMedianWordCount(URL)
  .then(median => console.log('Median word count', median));

And it still works!

Forking pipelines

So now we have a pipeline function that we can use to declaratively construct a single function that describes our process. But so far, we've only covered one of the three original goals we were tasked in our cosplay scenario.

Oh noes!

Let's write up all of the processes to take stock of what we still have to do.

const getMedianWordCount = pipeline(
  getRedditJSONUrl,
  fetchData,
  extractPosts,
  map(
    extractPostTextAndTitle,
    countWords
  ),
  calculateMedian
);

const getMedianCommentCount = pipeline(
  getRedditJSONUrl,
  fetchData,
  extractPosts,
  map(countComments),
  calculateMedian
);

const getImagePresentRatio = pipeline(
  getRedditJSONUrl,
  fetchData,
  extractPosts,
  map(hasImageAttached),
  calculateRatio
);

OK, so we need to write up a couple of steps so that we have all the functions available to assemble the processes. Let's add them now:

const countComments = post => post.data.num_comments;

const hasImageAttached = post => post.data.post_hint == 'image';

const calculateRatio = array => {
  if (array.length == 0) return undefined;
  return array.filter(value => !!value).length / array.length;
};

With that done, let's see if this all runs:


    
const fetch = require('node-fetch');
const _wordCount = require('@iarna/word-count');

const getRedditJSONUrl = url => url.replace(/\/?$/, '.json');
const fetchData = url => fetch(url).then(response => response.json());
const extractPosts = redditPage => redditPage.data.children;
const extractPostTextAndTitle = post => post.data.title + '\n' + post.data.selftext;
const countWords = text => _wordCount(text);
const numberValueSorter = (a, b) => a - b;
const calculateMedian = list => {
  if (list.length == 0) return undefined;
  const sorted = Array.from(list).sort(numberValueSorter);
  if (sorted.length % 2 == 0) {
    const a = sorted.length / 2 - 1;
    const b = a + 1;
    return (list[a] + list[b]) / 2;
  } else {
    const i = Math.floor(sorted.length / 2);
    return list[i];
  }
}
const pipeline = (...steps) => {
  return async input => {
    let result = input;
    for (const step of steps)
      result = await step(result);
    return result;
  };
};
const map = (...mappers) => async array => {
  const results = [];
  for (const value of array) {
    let result = value;
    for (const mapper of mappers)
      result = await mapper(result);
    results.push(result);
  }
  return results;
};

const countComments = post => post.data.num_comments;

const hasImageAttached = post => post.data.post_hint == 'image';

const calculateRatio = array => {
  if (array.length == 0) return undefined;
  return array.filter(value => !!value).length / array.length;
};

const getMedianWordCount = pipeline(
  getRedditJSONUrl,
  fetchData,
  extractPosts,
  map(
    extractPostTextAndTitle,
    countWords
  ),
  calculateMedian
);

const getMedianCommentCount = pipeline(
  getRedditJSONUrl,
  fetchData,
  extractPosts,
  map(countComments),
  calculateMedian
);

const getImagePresentRatio = pipeline(
  getRedditJSONUrl,
  fetchData,
  extractPosts,
  map(hasImageAttached),
  calculateRatio
);


    
const URL = 'https://www.reddit.com/r/dataisbeautiful/';

// now we need to call all three processes and report the final count
Promise.all([
  getMedianWordCount(URL),
  getMedianCommentCount(URL),
  getImagePresentRatio(URL)
]).then(([medianWordCount, medianCommentCount, imagePresentRatio]) => {
  console.log(
    'Results for ' + URL,
    { medianWordCount, medianCommentCount, imagePresentRatio }
  );
});

Great, we now know that we can build processes with these building blocks. There is a slight problem, though. Each process has to do much of the same things, and it seems wasteful to have to have each process fetch the same data and go through the same motions every time.

Let's create a fork function to handle that problem.

Ideally, we'd like to split the pipeline into specific pipelines for each process, then join them together to get the end result. Let's write some fantasy code to make the goal a bit clearer:

const getMedianWordCount = pipeline(
  map(
    extractPostTextAndTitle,
    countWords
  ),
  calculateMedian
);

const getMedianCommentCount = pipeline(
  map(countComments),
  calculateMedian
);

const getImagePresentRatio = pipeline(
  map(hasImageAttached),
  calculateRatio
);

// this is a convenience function that associates names to the results returned
const joinResults = ([
  medianWordCount,
  medianCommentCount,
  imagePresentRatio
]) => ({
  medianWordCount,
  medianCommentCount,
  imagePresentRatio
});

// the process function, now with forking!
const getSubredditMetrics = pipeline(
  getRedditJSONUrl,
  fetchData,
  extractPosts,
  fork(
    getMedianWordCount,
    getMedianCommentCount,
    getImagePresentRatio
  ),
  joinResults
);

According to the above requirements, the fork function takes a series of pipelines.

At this point, I would advise you to go ahead and try to write your own implementation of fork, given the above constraints. Your implementation might be very similar to the extended map.

Here's my take on the fork function:

const fork = (...pipelines) =>       // a function that takes a list of pipelines,
  async value =>                     // returns an async function that takes a value;
    await Promise.all(               // it returns the results of promises...
      pipelines.map(                 // ...mapped over pipelines...
        pipeline => pipeline(value)  // ...that are passed the value.
      )
    );

If it looks confusing, don't worry. It takes a lot to unpack what the function does.

The trick is to remember that Promise.all() takes an array of promises and returns a promise that resolves when all of the values have resolved. The result is the array of promise results in the same order. If any of the values isn't a promise, it just treats it as an immediately resolved promise with that result.

The final result

So, will the fork work and save us the extra overhead? Let's see.


    
const fetch = require('node-fetch');
const _wordCount = require('@iarna/word-count');

const getRedditJSONUrl = url => url.replace(/\/?$/, '.json');
const fetchData = url => fetch(url).then(response => response.json());
const extractPosts = redditPage => redditPage.data.children;
const extractPostTextAndTitle = post => post.data.title + '\n' + post.data.selftext;
const countWords = text => _wordCount(text);
const numberValueSorter = (a, b) => a - b;
const calculateMedian = list => {
  if (list.length == 0) return undefined;
  const sorted = Array.from(list).sort(numberValueSorter);
  if (sorted.length % 2 == 0) {
    const a = sorted.length / 2 - 1;
    const b = a + 1;
    return (list[a] + list[b]) / 2;
  } else {
    const i = Math.floor(sorted.length / 2);
    return list[i];
  }
}
const pipeline = (...steps) => {
  return async input => {
    let result = input;
    for (const step of steps)
      result = await step(result);
    return result;
  };
};
const map = (...mappers) => async array => {
  const results = [];
  for (const value of array) {
    let result = value;
    for (const mapper of mappers)
      result = await mapper(result);
    results.push(result);
  }
  return results;
};
const countComments = post => post.data.num_comments;
const hasImageAttached = post => post.data.post_hint == 'image';
const calculateRatio = array => {
  if (array.length == 0) return undefined;
  return array.filter(value => !!value).length / array.length;
};
const fork = (...pipelines) => async value => await Promise.all(pipelines.map(pipeline => pipeline(value)));


    
const getMedianWordCount = pipeline(
  map(
    extractPostTextAndTitle,
    countWords
  ),
  calculateMedian
);

const getMedianCommentCount = pipeline(
  map(countComments),
  calculateMedian
);

const getImagePresentRatio = pipeline(
  map(hasImageAttached),
  calculateRatio
);

// this is a convenience function that associates names to the results returned
const joinResults = ([
  medianWordCount,
  medianCommentCount,
  imagePresentRatio
]) => ({
  medianWordCount,
  medianCommentCount,
  imagePresentRatio
});

const getSubredditMetrics = pipeline(
  getRedditJSONUrl,
  fetchData,
  extractPosts,
  fork(
    getMedianWordCount,
    getMedianCommentCount,
    getImagePresentRatio
  ),
  joinResults
);

const URL = 'https://www.reddit.com/r/dataisbeautiful/';

getSubredditMetrics(URL)
  .then(results => console.log('Report for ' + URL, results));

One last magic trick

Still with me? OK, remember when we started our cosplay that we wanted to generate these reports for a list or URLs, not just one? Can we create a sort of process of processes that would take an array or URLs and return an array of reports?

Maybe.

Let's break down the problem. We have an array of URLs. We know we can pass each URL through the pipeline and get back a promise that resolves to the report. If we map the array of URLs with the pipeline, then we get back an array of promises.

And we already know how to resolve an array of promises!

const distribute = pipeline =>  // distribute takes a pipeline,
  values =>                     // and returns a function that takes a list of values;
    Promise.all(                // it returns a promise of all the values...
      values.map(pipeline)      // ...passed through each pipeline
    );

Yup, I think that does it! Let's try it out by passing an array of URLs to see how it does:


    
const fetch = require('node-fetch');
const _wordCount = require('@iarna/word-count');

const getRedditJSONUrl = url => url.replace(/\/?$/, '.json');
const fetchData = url => fetch(url).then(response => response.json());
const extractPosts = redditPage => redditPage.data.children;
const extractPostTextAndTitle = post => post.data.title + '\n' + post.data.selftext;
const countWords = text => _wordCount(text);
const numberValueSorter = (a, b) => a - b;
const calculateMedian = list => {
  if (list.length == 0) return undefined;
  const sorted = Array.from(list).sort(numberValueSorter);
  if (sorted.length % 2 == 0) {
    const a = sorted.length / 2 - 1;
    const b = a + 1;
    return (list[a] + list[b]) / 2;
  } else {
    const i = Math.floor(sorted.length / 2);
    return list[i];
  }
}
const pipeline = (...steps) => {
  return async input => {
    let result = input;
    for (const step of steps)
      result = await step(result);
    return result;
  };
};
const map = (...mappers) => async array => {
  const results = [];
  for (const value of array) {
    let result = value;
    for (const mapper of mappers)
      result = await mapper(result);
    results.push(result);
  }
  return results;
};
const countComments = post => post.data.num_comments;
const hasImageAttached = post => post.data.post_hint == 'image';
const calculateRatio = array => {
  if (array.length == 0) return undefined;
  return array.filter(value => !!value).length / array.length;
};
const fork = (...pipelines) => async value => await Promise.all(pipelines.map(pipeline => pipeline(value)));

const getMedianWordCount = pipeline(
  map(
    extractPostTextAndTitle,
    countWords
  ),
  calculateMedian
);

const getMedianCommentCount = pipeline(
  map(countComments),
  calculateMedian
);

const getImagePresentRatio = pipeline(
  map(hasImageAttached),
  calculateRatio
);

// this is a convenience function that associates names to the results returned
const joinResults = ([
  medianWordCount,
  medianCommentCount,
  imagePresentRatio
]) => ({
  medianWordCount,
  medianCommentCount,
  imagePresentRatio
});

const getSubredditMetrics = pipeline(
  getRedditJSONUrl,
  fetchData,
  extractPosts,
  fork(
    getMedianWordCount,
    getMedianCommentCount,
    getImagePresentRatio
  ),
  joinResults
);


    
const distribute = pipeline => values => Promise.all(values.map(pipeline));

const URLs = [
  'https://www.reddit.com/r/dataisbeautiful/',
  'https://www.reddit.com/r/proceduralgeneration/'
];

const getAllReports = distribute(getSubredditMetrics);

getAllReports (URLs)
  .then(results => {
    const reports = results.map((report, idx) => ({
      url: URLs[idx],
      report
    }));
    console.log(reports);
  });

...and they lived happily ever after.

Congratulations on making it this far! You've successfully gone through the process of designing & developing an entire system of asynchronous coordination mechanisms from scratch, which is no easy feat.

Just to wrap things up, let's extract the general utility functions that we've used to build up our process functions and make them available as modules:

export const pipeline = (...steps) =>
  async input => {
    let result = input;
    for (const step of steps)
      result = await step(result);
    return result;
  };

export const map = (...mappers) =>
  async array => {
    const results = [];
    for (const value of array) {
      let result = value;
      for (const mapper of mappers)
        result = await mapper(result);
      results.push(result);
    }
    return results;
  };

export const fork = (...pipelines) =>
  async value =>
    await Promise.all(
      pipelines.map(pipeline => pipeline(value))
    );

export const distribute = pipeline =>
  values =>
    Promise.all(
      values.map(pipeline)
    );

Using just these four functions we've managed to build out a complete suite of generic primitives that can process a finite amount of work in under 350 characters of minifed code. 😉

You can get out of that cosplay costume now.

Forem: Klemen Slavič

I built a silly Cloudflare Worker web service that helps you do math

expr.run!

Part 1: parsing algebraic expressions

Part 2: Cloudflare workers

Part 3: bundling and deploying

Conclusion

Stop wasting bandwidth with React's `useEffect` and `fetch`!

Reading and Parsing Large Files in JavaScript the Right Way

A Gentle Introduction to Streams

Consuming a ReadableStream

Creating Your Own ReadableStream

Transforming Streams Using TransformStream

Other Streams

Converting ReadableStreams into Asynchronous Iterables

Applied Streamology

What Does the Iterator Protocol Have To Do With`for...of`?

An Introduction to the Iterator Protocol

Creating Iterables using Generator Functions

Why Bother?

Practice Makes Perfect

Up Next

Want to be able to drag files into a web app? Got ya covered.

The Setup

In React-like Components

Handy Features

Development

Supercharging Autocomplete and Typechecking for JSX Components with Generics!

The Data Model

The Components

Using the Table Component

Working Example

Reproducible randomness and its applications

Throwing dice in code

Unpredictable yet reproducible

A practical example

JavaScript generators and generator functions

take

zip

map

Creating random number-driven generators

Putting it all together

Adopting seeded PRNG in your own project

Beyond sequences

Arrays, the slow parts — we can do better

The right tool for the right job

Values, variables and references

Keeping track of references using Set

When to use Set

Creating associations between values with Map

When to use Map

Caveats to consider when dealing with JSON data

Extending JSON for fun and profit

Klemen Slavič ・ Oct 28 '18

Conclusion

Improving security by drawing identicons for SSH keys

Of imbibing clerics and purses of coins

The grid

The rules of the game

Making things move

Drawing the grid

Making it interesting

The making of "This is your brain on JavaScript"

Deconstructing systems

Putting it all together

The cell

The world

Constants

Calculating forces

Applying forces and moving particles

Initial state

Managing the lifetime of the simulation

Making the cells divide

D3 rendering

Conclusion

Some lists are not like the others

Impostors, impostors everywhere

Iterators, iterables and Symbol.iterator

Arrays: the fast and easy parts

Arrays: the costly parts

Consuming a `ReadableStream`

Creating Your Own `ReadableStream`

Transforming Streams Using `TransformStream`

Converting `ReadableStream`s into Asynchronous Iterables

Using the `Table` Component

`take`

`zip`

`map`

Keeping track of references using `Set`

When to use `Set`

Creating associations between values with `Map`

When to use `Map`

Iterators, iterables and `Symbol.iterator`

`length`

`[index]`

`push()`

`pop()`

`unshift()`

`shift()`

`indexOf()`