DEV Community: Hadrian Hughes

Understanding applicatives in Haskell

Hadrian Hughes — Wed, 10 Apr 2024 00:00:00 +0000

My previous post was about the problem of parsing left-recursive grammars when using the parser combinator pattern in Haskell. In my code examples, I made extensive use of applicatives but didn't explain what they are or how they work. This was partially because their syntax is fairly intuitive when applied to parser construction, but also because I hadn't really grokked them myself---I was relying heavily on that intuitiveness without properly understanding what I was doing. So, I decided to take a deeper look at applicatives, what they are and how they work.

Rather than defining applicatives from the get-go, I'll present how they're used by parser libraries, as this is the way I first became properly aware of them.

Let's say we're building a programming language, and we want to be able to declare variables in the style of C---for example, we might declare an integer like int x;. To represent this in the AST, we might create a type like so:

data VarDecl = VarDecl { varType :: String, varName :: String }

Then to parse this kind of expression, we might create a parser like so:

varDeclP :: Parser VarDecl
varDeclP = VarDecl <$> string <*> string <* symbol ";"

As I mentioned previously, it is fairly intuitive to read this code as "we want to parse a string, then another string, then a semicolon and then use those things to construct a VarDecl." But how exactly does this work? It isn't immediately obvious how the two strings end up populating the varType and varName fields correctly. To understand it, let's break down this parser function piece by piece.

Data constructors are functions

The first important thing to know is that in Haskell, instantiating a data type is done using a data constructor, and these data constructors are just functions. In the snippet above where we define the VarDecl type, we write VarDecl on both sides of the = sign. The instance on the left is defining the name of the type, whereas the instance on the right is specifying the name of the constructor used for instantiating the type. If we wanted to, we could give the constructor a different name from the type, like VarDeclConstructor.

We then specify that VarDecl is a record type by placing the fields we expect between curly braces. It isn't obvious, but we're actually creating a function called VarDecl with the signature String -> String -> VarDecl---a function that takes two strings and returns a VarDecl. The function's arguments are the fields we specified between the curly braces, in the order we specified them.

To explicitly construct a VarDecl for the expression int x; we would use the data constructor like so:

VarDecl "int" "x"
-- This creates a value like
-- VarDecl { varType = "int", varName = "x" }

Understanding data constructors gets us a step closer to understanding how the two strings in varDeclP are used to construct a VarDecl: we're simply passing arguments to a function in the order they appear in the constructor definition.

What is a functor

The next term in the parser is the <$> operator. This is an alias of the fmap function, made into an infix operator. fmap is part of the Functor typeclass---it has the signature:

fmap :: Functor f => (a -> b) -> f a -> f b

It is used to "lift" a function into a functorial context, meaning a function that takes a and returns b becomes a function that takes f a (a in the context of a functor f) and returns f b (b in the context of a functor f).

I won't go into detail about functors here, but they can be thought of as types which can be mapped over. The clearest example of a functor is the list type. For a list, fmap behaves exactly the same as map: replacing f in fmap's signature with list types gives us:

fmap :: (a -> b) -> [a] -> [b]

fmap takes a function from a -> b and gives us back a function that applies that function to each element in a list and then returns the resulting list. Since <$> is an alias for fmap, the following expressions mean the same thing:

fmap f xs == f <$> xs

Importantly, the behaviour of fmap changes based on the particular functorial context of its second argument. Let's add parentheses to our parser to make it clearer how this applies there.

varDeclP :: Parser VarDecl
varDeclP = ((VarDecl <$> string) <*> string) <* symbol ";"

Function application is left-associative, so the parentheses do not alter the function's behaviour, they only highlight the associativity.

The first sub-expression we have is VarDecl <$> string. We are lifting the data constructor VarDecl (which, again, is just a function) into whichever context string is in. Which context is that? The string parser has the signature string :: Parser String, so assuming Parser is a member of the Functor typeclass (it needs to be for the parser combinator pattern to work) we can use it as the second argument to fmap. Let's substitute Parser for f and String for a in the fmap type signature:

fmap :: (String -> b) -> Parser String -> Parser b

This works, but what is the type of b? Well, functions are always curried, and the VarDecl constructor has the signature VarDecl :: String -> String -> VarDecl, so passing a single string argument to it leaves us with a resulting function of type String -> VarDecl---this is b.

fmap :: (String -> (String -> VarDecl)) -> Parser String -> Parser (String -> VarDecl)

Because our VarDecl constructor is a binary function, mapping it over a single argument in the Parser context results in a partially applied function lifted into that context. What we want is to continue passing arguments to the function so we can finish building our VarDecl record, but we'll need another way to invoke it now that it's in the Parser context. Now we're ready to introduce applicatives.

What is an applicative?

An applicative (short for applicative functor) is a special case of functors, where the type of value inside the functor can be a function. For a type to qualify as a member of the Applicative class, it must implement two functions:

pure :: Functor f => a -> f a
<*> :: Functor f => f (a -> b) -> f a -> f b

The pure function takes a value of type a and lifts it into the context of a functor type f. This means that for a Functor f to also be a member of the Applicative class, it must be possible to construct an instance of f from a single value.

The <*> function, called the sequential application operator, takes an applicative value (a function a -> b in a functorial context) and a value of type f a (a in the same context). The value inside the f a argument is fed into the function a -> b inside the applicative, and the resulting b value is returned, still inside the f context. As with functors, the specifics of how this behaviour is implemented is different for each instance of Applicative.

Let's revisit the list functor for a concrete example. To test if lists are a member of the Applicative class, we'll need to see if we can implement the pure and <*> functions. We can implement pure by simply taking some value x and creating a list where x is the only element.

pure :: a -> [a]
pure x = [x]

For sequential application, we need to accept a list of functions a -> b along with a list of a values, apply the each function in the first list to each value in the second, and then return the list of results.

<*> :: [a -> b] -> [a] -> [b]
(f:fs) <*> xs = (f <$> xs) <> (fs <*> xs)
[] <*> _ = []

This recursive implementation takes the list of functions and the list of values, and it maps the first function over the full list of values (using the fmap <$> operator discussed previously). Then it calls itself with the remainder of the list of functions and the full list of values. When finally called with an empty list of functions, it returns an empty list of values. This is not the official implementation, it's only an example to demonstrate that both functions required by the Applicative class can be implemented for lists, and hence, lists are an example of an Applicative type.

`Parser` as an applicative

Returning to our parser function, we've evaluated the first sub-expression and found that it evaluates to the type Parser (String -> VarDecl). We know that Parser is a functor, so this type certainly looks like an applicative, and indeed it is. Following the parser combinator pattern, the Parser type might be defined like so:

data Parser a = Parser { parse :: String -> Maybe (a, String) }

The Parser has a parse method which attempts to construct a value of type a by consuming characters from an input string. If successful, the value is returned in a tuple along with the remainder of the input string. Otherwise, it returns Nothing. Typically Either would be used instead of Maybe to enable more informative errors to be returned, but I'm using Maybe here for simplicity. All parsing errors just result in Nothing.

The pure and <*> functions for this type might be implemented like so:

pure :: a -> Parser a
pure x = Parser $ \input -> Just (a, input)

<*> :: Parser (a -> b) -> Parser a -> Parser b
Parser f <*> Parser g = do
Parser f <*> Parser g = Parser $ \input ->
    case f input of
        Nothing -> Nothing
        Just (f', input') ->
            case g input' of
                Nothing -> Nothing
                Just (val, rem) -> Just (f' val, rem)

The pure function is fairly self-explanatory---it simply takes a value x and uses it to construct a parser that consumes no input and always returns x along with the full input stream.

Sequential application is a little more complicated. This function takes two parsers as its arguments: the first is a parser that attempts to construct a function a -> b; the second is a parser that attempts to construct a value of type a. It runs the first parser on the input, and if it succeeds to construct the function a -> b, it continues by then applying the second parser to the remaining input. If the second parser is also successful in constructing a value of type a, that value is passed to the function a -> b, resulting in a value of type b. This final value is then returned in the form of a parser which always returns that b value without consuming any input. If either of the parsers fail, the whole operation results in Nothing.

This part had me stumped for a while. I couldn't wrap my head around the idea of a function inside a parser. A type like Parser String or Parser Int is intuitive to understand---they're trying to parse strings or integers from their inputs. But how could an unevaluated function be parsed from the text? The key to understanding this is to think of Parser not as a container, but as a name for a particular kind of computation---namely a computation that has access to, and can consume, a stream of input text. The type passed to Parser is the type of value you're trying to construct within that context. That is, Parser (a -> b) is not a parser of functions (which doesn't seem to make much sense), it is a function a -> b resulting from a computation in the Parser context.

With that said, we can now better make sense of our parser function. Again, the sub-expression VarDecl <$> string results in a value of type Parser (String -> VarDecl). We have used the string function to consume a String from the input text, and fed this into the VarDecl constructor, partially applying it and resulting in another function String -> VarDecl. Because this is part of a computation in the Parser context (we lifted VarDecl into that context using fmap <$>), this resulting function is also in the Parser context.

Working our way from the inside out, the next sub-expression is (VarDecl <$> string) <*> string (including the expression we've already looked at). Here we're using the sequential application operator <*>. Its first argument is the result of the first expression (of type Parser (String -> VarDecl)) and its second argument is the string function which has a type of Parser String. Let's substitute these types into the type signature for the <*> function.

<*> :: Parser (String -> VarDecl) -> Parser String -> Parser VarDecl

Thinking about how the <*> is implemented for the Parser type, this expression will run the first parser to parse a string and use it to partially apply the VarDecl constructor as we've already described. Then it will run the second parser to parse another string, and if successful, it will pass that string into the partially applied function, finally arriving at a value of type VarDecl which it returns still wrapped in the Parser context. Voilà! We've constructed the VarDecl type by composing parsers together.

But hold on, the full function is:

varDeclP = ((VarDecl <$> string) <*> string) <* symbol ";"

There is another part to the expression, a symbol parser which looks for the semicolon that terminates our int x; expression. It is important for the semicolon to be there, but we don't need its value to construct a VarDecl record, so how is this parser incorporated into the function?

This final parser is being applied using an <* operator we haven't looked at yet. This operator is also a part of the Applicative class, but it is not part of the minimal definition. The type signature for this operator is:

<* :: Applicative f => f a -> f b -> f a

This is a function which takes two values both in an applicative context, and just seems to return the first one. This initially seems kind of pointless, but take a look at how it might be implemented.

Parser f <* Parser g = Parser $ \input ->
    case f input of
        Nothing -> Nothing
        Just (x, rem) ->
            case g rem of
                Nothing -> Nothing
                Just (_, rem') -> Just (x, rem')

Although the value produced by the second parser isn't used, we do nonetheless run both parsers, allowing them both to consume input and possibly fail. If the second parser does fail, the whole expression also fails. This is ideal for our case where we want to parse a semicolon but then throw the parsed value away. Let's plug the types from our parser into the type signature for <*.

<* :: Parser VarDecl -> Parser String -> Parser VarDecl

The parser on the left-hand side of the <* is executed and its resulting value is the value returned from the overall expression. The parser on the right-hand side does have to run successfully, but its resulting value has no effect on the output of the overall expression.

The bigger picture

We've looked at how applicatives are used in the parser combinator pattern, but the Applicative class is intentionally abstract so that it can be used in lots of different contexts. In Haskell, I often find myself able to understand an abstraction well enough to use it in a certain context, but unable to fully grasp the essence of what it aims to express.

For example, I've been aware for quite a long time that an applicative is "a function inside a functor". That mental model works well enough when thinking about lists or the Maybe type, because both of those types can be thought of as containers for other values, which is intuitive. However, that understanding tripped me up when it came to learning about parsers; how can a parser be a container for a value, especially when that value is a function? Haskell is unique in that you can often ascertain a lot about what a function does just by looking at its type signature. Of course, this often isn't all the information you need to effectively use it, implementation does matter, but often the essence of an abstraction is best understood by looking at its type.

Take another look at the type of the sequential application operator:

<*> :: Functor f => f (a -> b) -> f a -> f b

It bears a resemblance to the type of the function application operator $:

$ :: (a -> b) -> a -> b

They seem to be expressing the same thing, except the former is in a functorial context. The function application operator $ is a controversial one, because in a simple expression, it doesn't do anything useful. For example, the following expressions are equivalent:

f x == f $ x

The only purpose served by the operator is in longer, more complex expressions where it can be used to disambiguate the precedence of terms. The reason for this is because there is no question of how a function a -> b can be mapped over a value a---this is a pure function and a pure value, so Haskell knows how to evaluate it. This is the essence of applicatives as an abstraction.

The sequential application operator <*> is serving a very similar purpose to the function application operator $, but in the former case, Haskell doesn't know how to apply the function to the argument, because they're both in an applicative context. The <*> operator leverages the applicative type to gain further information about how to map the function over the value.

This is incredibly powerful; we're able to express the composition of potentially very complex logic in terms of simple functions, because the complexity is abstracted away in the type. In the language of category theory, we're able to move into another context (like a parser context) and express morphisms in that context using the syntax and semantics of functions.

After improving my understanding of applicatives, the question occurred to me: "then what is a monad?" That could warrant its own post, monads serve a similar purpose, the difference essentially being that monads can be chained together with the results of one term in the chain depending on the results of the previous terms---this isn't possible with applicatives. In cases where that sort of behaviour isn't needed, applicatives are a more natural fit.

Parsing left-recursion by recursive descent

Hadrian Hughes — Mon, 25 Mar 2024 00:00:00 +0000

I've recently been building a parser for a programming language I'm designing. I'll likely be making future posts about the project as I make more progress, but suffice it to say, the language aims to bridge the divide between the functional and procedural paradigms as discussed in my post A Tale of Two Paradigms. I'm using a Haskell library called Megaparsec, which follows the parser combinator pattern to help with building recursive descent parsers.

A recurring problem

This library is great to work with, and building parsers this way is very intuitive, but I found myself repeatedly running into the same problem: trying to parse left-recursive parts of the grammar led to an infinite recursive loop. It took me a while to properly understand what was happening, but the problem can be formulated as follows.

Any time a rule contains itself as its first term, the parser will fall into infinite recursion. For example, take the following parser function:

expression :: Parser Expression
expression = Expression <$> expression <*> term

Expression represents a type defined as part of the language's abstract syntax tree (AST), and term would be some other parser function. The expression function first attempts to parse an expression, then attempts to parse a term, then passes the results of these two components to the data constructor for the Expression type. Abstractly, this is a valid rule. The problem is that the first thing the function does is call itself, with no base case to break it out of this loop.

The problem becomes clearer if we express it in a more procedural style:

function expression() {
    expression();
    term();
}

The function immediately calls itself, and as such the program will run forever (or until the call stack overflows).

This problem appears frequently when parsing expressions that can be chained. For example, in my language there are structs (data structures with values assigned to predefined fields), and accessing struct fields is achieved using a dot followed by the name of the field. For example, given a struct person that contains a field name, we would access the field using the expression person.name. This simple case would be straightforward to parse. First we would define a type StructAccess to represent this kind of expression.

data StructAccess = StructAccess Text Text

This type takes 2 arguments of type Text. The first represents the name of the struct being accessed, and the second represents the field being selected. The parser for this kind of expression would look like this:

structAccess :: Parser StructAccess
structAccess = StructAccess <$> identifier <*> (dot *> identifier)

And for the expression person.name, it would yield an AST that looks like something like this:

StructAccess "person" "name"

However, we ideally want to be able to chain this operation. For example, let's extend the definition of a person to also include an address field, which is itself a struct:

type Address = {
    street: String,
    town: String,
    postCode: String
}

type Person = {
    name: String,
    address: Address
}

To access a person's postCode the expression should be person.address.postCode. In this expression, we are actually first accessing the address field on the person struct using person.address, and this yields another struct; then we access the postCode field on this address struct by appending the previous expression with .postCode. Thus, we arrive at the full expression person.address.postCode.

To achieve this, we need to change the StructAccess type to a general Expr type.

data Expr = StructAccess Expr Text
          | Identifier Text

This new Expr type is an enum which can represent either a struct access operation, or an identifier (a string that references a struct by name). The specific StructAccess case takes another Expr as its first argument, meaning the left-hand side of the dot can be either a struct referenced by name, or another struct access operation. That is, we can chain the operation.

The AST for this expression would now look something like this:

StructAccess
    (StructAccess (Identifier "person") "address")
    "postCode"

To facilitate this we'd need to extend the structAccess parser like so:

identifierExpr :: Parser Expr
identifierExpr = Identifier <$> identifier

structAccess :: Parser Expr
structAccess = StructAccess <$> (try structAccess <|> identifierExpr) <*> (dot *> identifier)

The parser now attempts to parse a structAccess first (in this case, the sub-expression person.address), and only accept an identifier if this fails. However, this first attempt will never fail, because it will get caught in an infinite recursion. We could use parenthesis to solve this (the expression for accessing the postCode would become (person.address).postCode) but this isn't ideal.

I was stumped on this problem for a while before arriving at a solution I'm quite happy with.

Flatten the grammar

As long as we are using a recursive descent parser, there is simply no way to parse a left-recursive grammar such as this. I realised that to overcome the problem, I would have to change the structure of the AST to something that eliminates the left-recursion. I defined a new type and parser like this:

data FlatStructAccess = FlatStructAccess Text [Text]

structAccess :: Parser FlatStructAccess
structAccess = do
    structName <- identifier
    fields <- some (dot *> identifier)
    return $ FlatStructAccess structName fields

This parser first looks for an identifier, then looks for one or more instances of field selection using the dot operator; it then passes these results to the data constructor for FlatStructAccess. For the expression person.address.postCode, the resulting AST would look like this:

FlatStructAccess "person" ["address", "postCode"]

By eliminating left-recursion, this function is able to successfully parse the expression. However, this wasn't the AST I wanted to end up with. I wanted each StructAccess to select a single field from a struct---chaining the operation would result in a nested AST as outlined earlier. I would have to restructure the AST I had, represented by FlatStructAccess, into the one I wanted, and I had a feeling that would be tedious to figure out. On the contrary, it turns out that Haskell's standard foldl function would do it in one line.

foldl has the signature:

foldl :: (a -> b -> a) -> a -> [b] -> a

For its first argument, it accepts a function that takes an a and a b and returns another a. It's second argument is an a which will be fed into this function, partially applying it, and its third argument is a list of b, the first of which will be passed into the partially applied function to result in a new a. This new a is then fed back into the function, partially applying it again, and this partially applied function is applied to the next b in the list, and so on until the full list has been iterated over, culminating in a final result of type a.

A simple use case for foldl would be to calculate the sum of a list of numbers. In this case the specific signature would be:

foldl :: (Int -> Int -> Int) -> Int -> [Int] -> Int

And it would be applied like foldl (+) 0 [1,2,3]. The result of this expression would be 6.

For our use case, Expr will be substituted for a and Text will be substituted for b.

foldl :: (Expr -> Text -> Expr) -> Expr -> [Text] -> Expr

Remember that data constructors are just functions, and the StructAccess constructor takes 2 arguments of type Expr and Text respectively. StructAccess is a data constructor for the Expr type, so that means the type signature for StructAccess is Expr -> Text -> Expr---the same as the first argument expected by foldl.

For the expression person.address.postCode, foldl will take an initial Expr (namely Identifier "person") and use it to partially apply the StructAccess constructor. It will then take the first item in the list of fields ("address") and pass it to the partially applied function, resulting in StructAccess (Identifier "person") "address". This Expr will then be used to partially apply StructAccess again, and then the final field ("postCode") will be passed to the partially applied function, resulting in the final result: StructAccess (StructAccess (Identifier "person") "address") "postCode".

The final version of the structAccess parser looks like this:

structAccess :: Parser Expr
structAccess = do
    structName <- identifier
    fields <- some (dot *> identifier)
    return $ foldl StructAccess (Identifier structName) fields

By bootstrapping the StructAccess constructor with our structName and then folding it across our fields, we can easily transform our flat AST into the recursive one we want.

Megaparsec actually used to provide a function called chainl1 (documented here), which is an abstraction for this approach. This has since been deprecated and replaced with a helper module called Text.Megaparsec.Expr. I found the approach of this helper module more difficult to wrap my head around, but I may try to rework my solution to use this abstraction in the future.

Intermediate representations

My central takeaway from this experience is that the AST your parser targets needn't be the one you keep. In cases like this, it makes sense to parse to an intermediate representation before reworking the result into the structure you actually want. The purpose of the parser is to transform a string of characters into a meaningful data structure. To whatever extent you can parse directly to the desired AST, you might as well do it, but you can otherwise get to the target AST in multiple steps.

On function composition in JavaScript

Hadrian Hughes — Wed, 06 Mar 2024 00:00:00 +0000

In 2020, there was a proposal to add a "pipe" operator to JavaScript. It is currently in the draft stage, but its syntax has changed substantially from the original proposal. It most closely represents the pipe operator from the language Hack.

The new operator (|>) would not fundamentally add new functionality to JavaScript, but would provide an alternative syntax for chaining function calls. The following expressions would be equivalent:

x |> f(%) |> g(%) == g(f(x))

The most obvious advantage of the left-hand expression is that it represents chained function execution as a clear pipeline of function calls (hence the name), from left to right, which is more intuitive and readable than unravelling a cluster of nested function calls from the inside out. Particularly in cases where lots of functions with long names are being composed, the expression can get quite unwieldy. E.g. something like mapStructure(validate(JSON.parse(json))). In this case, the expression would most likely be split into multiple smaller ones, with intermediate values stored in variables for clarity, like

const obj = JSON.parse(json);
const validated = validate(obj);
const mapped = mapStructure(validated);

But the pipe operator would provide an alternative syntax that arguably makes it clearer what is happening because variables are not introduced into the scope which might be used multiple times. The "pipelined" version of the above would be

json |> JSON.parse(%) |> validate(%) |> mapStructure(%)

However, the original proposal would have more closely resembled the F# forward pipe operator. The previous snippet in the F# style would be

json |> JSON.parse |> validate |> mapStructure

There are pros and cons of each, but I have to say, I prefer the F# version. The placeholder operator % introduces indirection and bloat where the purpose of the proposal is to do the opposite. But regardless of the specifics of the implementation, finding out about this proposal got me thinking about composition in JavaScript more generally, and why this proposal has only come about now.

Methods vs functions

There is already a mechanism in JavaScript for the chaining of certain behaviours that follows a similar structure: object methods.

JavaScript does not have classes, but it uses a prototypal inheritance model to associate pieces of functionality with certain types of object - these are methods. For example, we might create an object type called Person and attach a greet method to it like so:

function Person(name) {
    this.name = name;
}

Person.prototype.greet = function() {
    return `Hello, ${this.name}.`;
}

Now if I create an instance of Person for myself

const me = new Person('Hadrian');

the greet method will use my name without having to take an argument

me.greet(); // => "Hello, Hadrian."

This means that a method is essentially a partially applied function. The greet example above is similar to a function which takes a name, then returns another function which greets that name.

const greet = name => () => `Hello, ${name}.`;

const greetMe = greet('Hadrian');
greetMe(); // => "Hello, Hadrian."

The greet method returns a string, and in JavaScript, strings are also objects with associated methods. Therefore, we could chain the greet method with a method from the String prototype.

const isGreeting = me.greet().startsWith('Hello'); // true

The Array prototype methods are some of the most commonly used, and they lend themselves to being chained together particularly well because they are methods on Array which also return an Array. We might perform a series of array transformations by chaining methods, like so:

const people = [
  { name: 'John' },
  { name: 'Jane' },
  { name: 'Harry' },
  { name: 'Jane' }
];

// Return a list of unique names that start with 'J'
const uniqueJNames = people
    .map(person => person.name)
    .filter(name => name.startsWith('J'))
    .reduce((acc, name) => acc.includes(name) ? acc : [...acc, name], []); // => ['John', 'Jane']

As long as the behaviour you want to compose is encoded in prototype methods, JavaScript allows you to easily create clear, pipeline-esque chains of functionality - but that's a big if.

Why now?

JavaScript is not the most principled language. In most cases, if you don't like a programming language, you can just use a different one; even in the case of Java, which is king of the JVM, there are other languages that can nonetheless exist in that environment, like Clojure and Scala.

On the other hand, JavaScript is the language of the browser, and as such, when the programming zeitgeist moves on to a new paradigm, pressure grows for JavaScript to incorporate elements of that paradigm. As a result, JavaScript is a bit of a Frankenstein. As previously mentioned, JavaScript doesn't have classes, but it does feature class syntax which gives the programmer the option of writing code in a way that feels object-oriented. In truth it is syntactic sugar over the existing prototypal inheritance model.

In recent years, certain aspects of functional programming have become popular, like lambda expressions, immutability and functions as first-class entities. ES6 formally introduced these concepts into JavaScript with new syntax, like arrow functions and the const and let keywords, and they have become central elements of the language - so much so that var is rarely seen and arrow functions might be more widely used than the traditional function syntax.

Prototypal inheritance, by comparison, has fallen out of favour. Although standard prototype methods like the aforementioned Array methods are used as much as ever, it's rare to see custom methods being attached to prototypes in a modern codebase. Instead, functionality is typically encoded into ordinary functions. This explains why the proposal for a pipe operator has only appeared quite recently: prototypal inheritance and the optional class syntax are JavaScript's current options for composition, and we're not using them. However, technically speaking, the pipe operator is not for function composition, but function application.

What is really missing?

As previously mentioned, JavaScript's implementation of lambda expressions (which it calls arrow functions) are used very widely - arguably a little too widely. Although lambda expressions are a feature of functional languages, these languages tend not to promote using them too frequently; they are a tool for encoding particularly unique logic that is unlikely to be repeated. It is usually better to represent complex logic as an expression of simpler functions - by composing them.

Often the syntax for lambda expressions is ugly, and this is my own conjecture, but I suspect it is intentional to discourage using them. The epitome of this can be found in Python:

inc = lambda x : x + 1
inc(1) # => 2

If you really want a lambda expression you'd better spell it out.

In JavaScript, even if we want to compose functions, arrow functions are how we have to do it because there is no built-in way to compose functions independently of their inputs. As previously mentioned, the proposed pipe operator is inspired by Hack, but it is not too dissimilar to the F# forward pipe. But F# has another operator specifically for composing functions. Using this operator we could encapsulate the JSON example from earlier into a named function like so:

let handleJson = JSON.parse >> validate >> mapStructure

There is no need to make any reference to the json variable that will be passed into the function - the functions can be composed independently from their inputs. To do the same thing in JavaScript would require an arrow function, meaning the argument that will be ultimately passed to the function has to be handled explicitly:

const handleJson = json => mapStructure(validate(JSON.parse(json)));

In my opinion, the proposed pipe operator wouldn't add much utility to JavaScript, but a true composition operator would be a welcome addition.

Existing solutions

There are JavaScript libraries which attempt to solve this problem. For example, Ramda includes a pipe function which composes functions just like the F# compose operator. For example, to repeat the previous example of parsing and mapping a JSON structure, the equivalent using Ramda would be the following snippet.

const handleJson = R.pipe(JSON.parse, validate, mapStructure);

This does result in a similarly clean structure that resembles a pipeline - it works well. However, it isn't obvious in which direction the functions are evaluated. It so happens that the functions will be evaluated from left to right, but there is nothing about the syntax that makes that obvious. This wouldn't be any less confusing to someone with a background in a functional language like Haskell, because functional languages vary in their direction of composition. In Haskell, composed functions are evaluated from right to left, like so:

handleJson = mapStructure . validate . JSON.parse
-- equivalent to
-- handleJson json = mapStructure (validate (JSON.parse json))

One advantage of the F# composition operator is that it resembles an arrow, making the flow of execution abundantly clear.

At the end of the day, JavaScript is not a functional language; it's a hodgepodge of different paradigms, one of them being functional. Ideally, a language would have strong principles, meaning updates and feature proposals would rarely be necessary. But JavaScript has a specific role in web development that incentivises it to change with the times - if a new feature would improve the way we currently use the language, then it is a good change. With that said, the pipe operator proposal in its current state is a marginal improvement, if an improvement at all. I think a true composition operator would be a much more valuable addition to the language.

A Tale of Two Paradigms

Hadrian Hughes — Sat, 24 Feb 2024 00:00:00 +0000

Recently I've been thinking about the handling of "side effects" in programming languages. Most (basically all) of the programming languages we use in industry don't include a notion of side effects in their semantics. In procedural and object-oriented languages, a program's behaviour is broken down into procedures or methods, respectively, which consist of statements to be executed. Each of these statements may or may not perform an operation that would be considered a side effect, like logging a message to the console, requesting input from the user, interacting with a web API - basically anything that affects or depends upon something in the world outside the program.

Advocates of functional programming often point to this (correctly, I think) as a fundamental weakness of the most widely used languages, and one of the biggest strengths of functional programming languages like Haskell. In the latter, a program consists entirely of functions, and these functions simply map their arguments to some output and do nothing more. Detractors are then quick to point out (also correctly, I think) that side effects are not a problem, they are the reason we write code. If a language were to disallow I/O altogether, we would have no way of interacting with it, and it would be rendered completely useless. This is true, and this is why I think "side effects" are really more accurately termed, simply "effects".

However, Haskell does have support for effects like I/O, but these kinds of operations are encoded by specific types like the IO type. The function signature foo :: IO a lets the compiler know that when executed, the function foo will perform some effect involving I/O which, if successful, will return a value of type a. That is, foo does not return an a, it returns an instruction for performing an effect whose "happy path" produces an a. This kind of explicit identification of an effect allows the compiler to ensure that each of its possible outcomes are handled safely.

The problem with procedural languages

While Haskell can't guarantee that effects won't produce errors (the real world is unpredictable), it can guarantee that functions are referentially transparent, meaning any function call can be replaced by the output it produces, without affecting the program's behaviour. That is, if a function returns an Int, each instance where that function is called can be treated as if it is an Int. This principle means that functions can always be composed with other functions, and the result will always be predictable; as long as the types match up, the functions compose.

Even in procedural languages that have strong type systems, like Rust, we don't get these same guarantees. A function might say that it returns i32, but that result might be dependent on an API call that could fail or result in different values at different times. Continuing with the example of Rust, we hope that if the function could fail then it would have a return type of Result<i32> (Rust offers the Result type to encapsulate operations that could fail), but that is down to the discretion of the programmer who wrote it - they could just as easily return an erroneous value that is still of type i32, like 0.

The problem with functional languages

All of this to say, I like Haskell and functional programming in general. But the problem is that for the most part, nobody uses them, and I can't really blame them. I've been building side projects and generally playing around with Haskell for a few years now, and I still don't feel that I have as strong an understanding of it as I do of languages that I've used for a fraction of the time. Haskell is steeped in esoteric mathematics, and while it is relevant and interesting, it is also dense and difficult. And furthermore, while it is possible to write working Haskell programs without being able to properly explain why a monad is "just a monoid in the category of endofunctors", trying to convince software engineers to pick up a language so foreign and unintuitive is difficult. The problem is that it is because of its rigorous mathematical backbone that Haskell is so safe.

Procedural semantics result in code that expresses what the computer should do, while functional semantics result in code that describes what things are; the former is more imperative while the latter is more declarative. Neither of these approaches is necessarily superior, but as an engineer, when you know what you want your program to do, having to deconstruct the problem into a kind of library of abstractions which you then recompose into a working program, seems tortuously indirect. From the perspective of practicality, I think this is a point in favour procedural languages (or imperative languages more broadly).

We only become more dependent on software, not less, and I think that the lack of a way of handling effects as what they truly are - dependencies on the fuzzy outside world that are highly likely to fail - is a pressing deficiency that modern languages need to tackle. While Haskell does this, it realistically isn't going to be adopted broadly any time soon, nor is anything like it. However, there doesn't seem to be any reason why correctly representing effects in a type system would be incompatible with an imperative style, and I wonder if there isn't a way for us to reap the benefits of both paradigms.

Software development is not like surgery

Hadrian Hughes — Mon, 19 Feb 2024 00:00:00 +0000

Pair and mob programming are often seen as the gold standard for collaboration. Multiple developers sit around a computer (or on a video call) and combine their efforts to work on a single problem, which reduces the time needed to solve it and allows for immediate feedback---two heads are better than one.

In fact, a previous colleague once told me that he thinks we should be pair or mob programming all the time. He presented his argument as a simple syllogism:

Premise 1: In surgery, a simple instance of human error could be catastrophic for the patient, so surgeons are expected to work as part of a team to decrease their chances of making a mistake.

Premise 2: As software takes over more and more of the systems we all rely on, the consequences of a mistake in software development could be similarly catastrophic.

Conclusion: Software developers should always be mob or pair programming to prevent these kinds of mistakes.

I think the argument is a sound one. It's worth mentioning that each person in an operating theatre has a different role, which isn't typically the case when mob programming, but reducing errors is certainly another major reason for the approach---I wouldn't feel nearly as confident going into surgery if I knew the surgeon would be acting alone.

And it's true that increasingly, a bug in a piece of software can be more than a minor annoyance, and can instead have dire consequences. The recent publicity around the Horizon scandal in the UK has made that clear: a bug in the Post Office's accounting software led to hundreds of postmasters being wrongfully convicted of serious crimes.

But there is a crucial difference between surgery and software that informs why human error is necessarily so dangerous in the former, but not in the latter. If a surgeon makes a mistake that causes damage, that mistake cannot be taken back. It might be possible to fix the damage, but there is no backtracking---the action is final. In an ideal world, the surgeon would make their changes in an isolated environment, like a draft state, then they would hand their work over to another surgeon for review. When the team has taken their time to search for errors and ensure that everything has gone to plan, they would "commit" their changes and they would be applied to the patient for real (you see where I'm going). In such a world, if a surgeon felt that their best work happened when they worked alone, they would be able to do so without consequence; some surgeons might still work in groups, but only if they felt that it was helpful.

Maybe technology will one day make this kind of workflow a reality, but as things currently are, surgeons live in an imperfect world where their changes are always necessarily final. In software on the other hand, we do live in this ideal world. Because of tools like Git, every developer has their own, isolated environment where no matter how much damage they wreak, users of their software will be completely unaffected. It's only once their changes are deployed into production that any mistakes bear fruit (hopefully after a period of thorough peer review where they are caught and fixed). For this reason, even if a developer has worked on a feature completely alone, there is still ample opportunity for their changes to be reviewed by their teammates asynchronously.

My point here is not to suggest that we shouldn't be pairing or mobbing, but that we have the luxury of choosing without putting users of our software at risk. To speak for myself, I am one of those aforementioned people whose best work happens alone. Being surrounded by teammates while trying to reason about a problem creates pressure that distracts me from the task, like someone looking over your shoulder while you type an email. On the other hand, I'm more than happy to pair on a problem with a teammate if they feel it will help them---we should be flexible and consider the differing working styles of our teammates.

This does of course mean that we have a responsibility to perform robust, in-depth peer reviews before our code reaches users. Creating well-structured, intentional commits with meaningful messages is crucial to ensuring that the teammate who reviews your code is able to properly understand it, even when the pull request is large. However, I'd argue that these sorts of practices have benefits beyond enabling flexible styles of teamwork.

During a pairing session, valuable feedback might be given, but it isn't captured. The solution to a problem might be well-understood by the people who worked on it, but down the line a new team member might revisit that same section of code, and will not have any of that context. Git commits and pull requests are captured and stored, enabling communication with future team members, even after the author of the feedback has left the team.

This kind of communication is invisible until it's needed, which I suspect is one of the reasons why pair programming is often pushed for by project managers. The latter is the most visible form of collaboration, which assures those in less hands-on roles that teamwork is indeed happening. But I'd suggest that asynchronous collaboration and communication is more important to ensure continued code quality over long periods of time and despite team changes.

As more and more aspects of our lives are influenced by software, it is absolutely the responsibility of dev teams to ensure that good practices are followed to avoid introducing bugs that could have serious consequences for users. But the intangible nature of our work gives us a kind of flexibility of working styles not enjoyed in many other fields, and we should take advantage of this flexibility to enable developers to contribute fully to collaborative practices while working in the way that works best for them.

Bulletproof React: Understanding The Functional Reactive Approach

Hadrian Hughes — Tue, 21 Apr 2020 20:39:19 +0000

The principles of functional programming are becoming more in fashion every day. More and more traditionally imperative languages are implementing lambda functions, immutability and lazy evaluation. It's exciting to see, and even more encouraging to see that React is at the forefront of these changes.

React has always encouraged functional principles in some capacity; Redux has long been the most popular approach to building large scale apps. However, the advent of React hooks has made it clear that this preference for functional over imperative is very intentional, and it's here to stay. With all that said, I still hear the complaint that Redux is confusing, or seems "magical". There are also plenty of developers who think Redux is made obsolete by React's Context API, and while there's some truth to this, there are still some huge benefits to be gained by using the Redux approach, so I'd like to dedicate a post to demystifying just how it works and to outlining those benefits.

The most obvious benefit of using Redux would be that it moves all of your app state to a single source of truth, making it much easier to ensure that components stay in sync with one another. But there's more. Let's start by laying out all the key components of the Redux architecture.

Notice there is no 'store' entity in the diagram because the store is a transient value passed to the view from the reducer.

The Store

At the core of everything in a Redux app is the store. It's easy to think of the store as a container for all of your state which you can update, but the store is in fact immutable. It's a value passed through your app just like arguments to a function, and the only way to "change" the value is to call the function again with different arguments.

To better visualise this, let's create a very simple functional reactive app in JavaScript.

// <button id="myButton"></button> defined in HTML

function myApp(state) {
  function dispatch() {
    myApp(state + 1);
  }

  const btn = document.getElementById('myButton');
  btn.innerHTML = state;
  btn.onclick = dispatch;
}

myApp(0);

We define our app as a function myApp which accepts our state as its argument. Within the context of myApp we define a closure called dispatch, which simply calls myApp again with updated state (the previous state + 1). We then use our state as the button's text label, and bind dispatch to the button's onclick listener. Finally, we bootstrap the app with a starting state value of 0. Now every time we click the button, its value will increase by 1 as myApp reruns with the updated state.

Simple, right? There's no magic here - this is functional reactive programming in its most basic form.

To bring it back to Redux, the state argument in our example would be the store in Redux. It's immutable - or more to the point, mutating it would have no effect because the app has already consumed it and finished running - and we have to use a dispatcher function to make changes to it. Redux also exposes a dispatch function which we either pass down to components via props, or we use the react-redux higher-order component connect to avoid props drilling. However, Redux's dispatcher function doesn't directly rerun the app, but the extra step is part of what makes it so powerful.

Actions And The Reducer

When the dispatch function is called following a user interaction, it is passed an action. An action consists of a type and a payload. This action is then passed through a reducer function. This is where the magic happens. The following is a simple example of a reducer function:

const initialState = 0;

function reducer(state = initialState, action) {
  switch (action.type) {
    case 'ADD':
      return state + action.payload;
    case 'SUBTRACT':
      return state - action.payload;
    default:
      return state;
  }
}

Our reducer function accepts two arguments: the current state and the action passed to the dispatcher function. We check the action type and apply a transformation based on it. If the type is ADD, we return the current state plus the action payload; if the type is SUBTRACT, we return the current state minus the action payload. This returned value will become the app's new state.

const myAddAction = {
  type: 'ADD',
  payload: 3
};

reducer(5, myAddAction); // This would perform 5 + 3 to return 8

Transforming our state using a reducer function means the state can only be transformed in a finite number of ways, which are all immediately visible when you view this function. No matter what we do, we can't multiply or divide the state without adding a new case to the reducer's switch statement. This is very powerful: no more tracking down where a logic error is coming from. If a state update happens it must be happening in the reducer function; the only question is where the dispatcher function was called from, which is easy to track down using a stack trace.

Side Effects

It's time to go a little deeper into functional terminology (but only a little). Our app is now more deterministic thanks to all state updates being centralised in one function. However, how will our app communicate with the outside world?

In functional programming, any computation which doesn't consist of a function returning an expression based solely on its arguments is called a side effect. An app without side effects is useless; at the very least we need a way for our app to receive input and give output, and since both of these things rely on conditions being met in the outside world (e.g. the code being run in a browser with a DOM API for us to interact with) they would be considered side effects. However, just because our apps rely on side effects doesn't mean we should pretend they don't exist. Thinking proactively about where the side effects in your app are allows you to reduce the number of them you create, and to manage them safely.

Thankfully, React deals with IO for us and allows us to write pure computations safely behind the abstraction of the virtual DOM, but what if we want to get some data from a remote API over HTTP? Typically we'd just place this in a useEffect hook in one of our components, but this is less than ideal. For example, what if we have two of the same component on one page, and both of the instances perform the HTTP request? One of them would be completely redundant. We can program around this using finicky conditionals, but who wants that? Wouldn't it be the icing on the cake to not have to go through the ordeal?

We can solve this by using a Redux middleware. A middleware sits between the dispatcher function and the reducer function. An interaction causes dispatch to be called with an action; the action is then passed through any middlewares we set up, before finally reaching the reducer.

Let's say we're building an app which includes a list of users. On the initial page load we might dispatch an action to fetch the list of users from an API:

{ type: 'FETCH_USERS' }

This isn't an action type which is recognised by the reducer, so it won't trigger a state update. Instead, we tell a middleware to wait for any actions with a type of FETCH_USERS and then perform a get request to the remote API. When a response comes back, the middleware calls the dispatcher function again with a new action:

{
  type: 'SET_USERS',
  payload: users // 'users' is the response body
}

This subsequent SET_USERS action is picked up by the reducer and the app reruns with the new state which includes the fetched list of users. No searching for the component responsible for fetching a piece of data, we know it always happens in a middleware.

The most popular Redux middleware libraries are redux-saga and redux-thunk. They use very different approaches but both have their pros and cons.

In Summary

So what have we gained? In short, transparency and determinism. Each aspect of our app is now clearly defined and has a dedicated place. The view is handled by React, but we can now be sure that it is composed of only pure functions which receive their props and return markup. All state transformations are triggered by actions and performed by the reducer function. All side effects (besides IO which is handled by React) are isolated within middlewares where nothing else depends on their success.

Using this approach, our apps can scale indefinitely with minimal runtime errors and without logic errors becoming impossible to track down and manage.