JavaScript and Type Thinking
At the heart of functional thinking is to ask about the meaning of things. In the case of functions, it’s reasoning about their return values. But, that’s actually insufficient, as important as is, to give the full answer.
Basically, a function is a relation between a set of inputs -a domain- and a set of outputs -a codomain- (along with a fundamental constraint: the same inputs always produces the same outputs). So we have also to ask, in addition of the return value, about the permissible inputs and outputs of a function. In the world of programming, that leads us straight to reasoning about types.
It maybe be surprising to talk about types in a dynamic language like JavaScript, without static/explicit typing. The truth is, consciously or subconsciously, you are always reasoning with your types, JavaScript still has to check your types, although this is delayed until execution (late binding). And you still has to think of what operations you can invoke on this or that variable.
In this post i’ll (try to) show you that type thinking is more than tagging a variable with a data type to get those precious compiler messages, and more importantly, you don’t have to work with a statically typed language in order to reason about your program types (just as you don’t need to work in a purely functional language in order to do functional thinking).
The post use a Haskell-like syntax to denote functions type signature :
=> ‘f : a -> b’ means f is a function that takes an argument of type a and returns a result of type b. a and b are considered generic types
=> Multiple arguments are enclosed in parentheses : ‘f : (a, b) -> b’
=> ‘a | b’ denotes an union type either of type ‘a’ or type ‘b’.
=> ‘Future a’ means a ‘Future’ parametrized with a generic type ‘a’
Error handling revisited
You may recall in the post about Futures how we solved the error handling problem: we introduced the concept of failure to our Future type, thus derived the new operations for error handling: ‘fmapError’ and ‘flatMapError’.
The truth is that i’m not fully convinced with the above solution (i’m pretty sure any FP guy would think the same thing).
First with more concepts comes more complication, we’d have to deal with more cases both in our semantic model and our implementation. IMO, a ‘Future’ has to deal only with one thing, describing values that will occur in the future and nothing more. Any meaning that may be given to this values must be defined in their proper computational context. FP is all about expressing complex things out from composing simpler things (while in contrast, imperative programming is often about expressing simple things using more complex things under the hood).
And after all, errors are not necessarily a proper concept of Futures but are relevant to any function, be it synchronous or asynchronous.
Second reason is practical, actually i’d rather classify errors into 2 kinds:
- Semantic errors are integral part of the problem space (like converting a string to a number that may fail if the string is not a valid numeric representation)
- Runtime errors are errors that typically arise from bugs in the code (type error, undefined function name, …)
Observe this code from the definition of ‘fmap’
Future.prototype.fmap = function(fn) {
// ...
try {
fut.complete( fn(val) );
}
catch(err) {
fut.fail(err);
} }
The ad-hoc catch statement inside ‘fmap’ will catch both error types — semantic and bugs — and fail the future with whatever error is caught. While i find it natural to fail the Future with an expected erroneous result of a function call, i don’t think it’s same for bugs or runtime errors.
Third and more fundamentally, the solution isn’t really in the spirit of functional thinking, which is all about defining functions.
A try/catch block makes sens only if we are thinking in terms of executable statements, but in denotational thinking there is not such a meaning to the above code. Denotational world is made of relations between things without reference to any execution model.
So how do we deal with errors in functional terms? it’s quite simple, and you may already know it, just consider the simple code below, what’s the type of the following ‘toNumber’ function
const toNumber = str => Number(str)Before you answer, consider what happens if you run this expression?
toNumber("not a number") // => NaNExecuting the equivalent code in a language like Java will immediately throw a ‘ NumberFormatException’ at your face but above instead it returns a curious ‘NaN’ type. Believe it or not, but the JavaScript solution is more or less similar to what we may do in a purely functional language.
In the Java case, we say that ‘toNumber’ is a partial function. Indeed, it can’t give an answer to all inputs. So the function just raises an exception. Put another way, the function isn’t defined over the full domain of strings but only those representing valid number representations.
What JavaScript does actually is simulating a common pattern in FP : extending the codomain of the function— the set of its permissible outputs — so the function can actually return either a valid number or the curious ‘NaN’ value.
Let’s apply the same trick to our error handling problem: If a function may return some error, we just extend it’s codomain to permit errors as return values; So we also define a new type
Result a = Success a | Error ObjectThe meaning of above is: ‘Result’ defines, for each underlying type ‘a’, a new type that is either a ‘Success’ holding a value of the same type ‘a’ or an ‘Error’ holding an error object. Both sides of the definition are called variants of the Result type. Think of ‘Success’ and ‘Error’ as specializations of the more abstract ‘Result’ giving us more information about a given ‘Result’ value.
You can view ‘Result’ as another box type, just like ‘Array’ or ‘Future’ defined in the previous post. And by box, i mean it gives a context to an underlying value. If you take only a value of type ‘a’, its meaning is nothing more than that given by its type. Now, put it inside a ‘Success’ box, and the meaning is enriched, it now denotes a successful result of a computation.
This makes a subtle and important difference, you can move a ‘Result’ all around within your code without any loss of its initial context. Contrast this with inline error handling when you have to deal with the error as soon as it occurs, otherwise you lose its context (a typical problem in node async functions, where errors can get lost if you forget to handle them in place).
‘Result’ is an example of what we call Algebraic Data Types or just ADTs, which are basically types formed by composing other types. ‘Success’ and ‘Error’ are also called constructors because they give us concrete instances of the ‘Result’ type (actually they are more factory functions than traditional JavaScript constructors).
A possible implementation of ‘Result’ in JavaScript is given below:
// private constructor
function Result(isError, data) {
this.isError = isError;
this.data = data;
}// public factories
Result.Success = val => new Result(false, val);
Result.Error = err => new Result(true, err);
Here is an example of usage with a Future and an async node function
// readFileF : (String, Object) -> Future (Result String)
function readFileF(file, options) {
var f = new Future();
fs.readFile(file, options, (err, data) => {
const res = err ? Result.Error(err) : Result.Success(data);
f.complete(res);
});
return f;
}Since ‘readFile’ may fail, we wrap its result in a Result type to denote its outcome (Success or Error).
In final, we obtain a value of type ‘Future (Result String)’, a Future holding the eventual Result of the file read operation.
As with Future, Result type is a Functor instance (let’s call its mapping method ‘map’ as in Arrays):
// map : (Result a, a -> b) -> Result b
Result.prototype.map = function(f) {
return this.isError ? this : Result.Success( f(this.data) );
}above, ‘map’ applies the function only to successful values and forward errors.
The peer function to handle errors do the inverse, catching and transforming errors while forwarding successful results:
// mapError : (Result a, a -> b) -> Result b
Result.prototype.mapError = function(f) {
return this.isError ? Result.Success( f(this.data) ) : this;
}Result is also a Monad, we define the sequencing operation ‘chain’ (which is more sounding than flatMap)
// chain: (Result a, a -> Result b) -> Result b
Result.prototype.chain = function(f) {
return this.isError ? this : f(this.data);
}Like ‘map’, ‘chain’ captures and transforms valid results while forwarding errors.
And the error handling equivalent which do the inverse
// chainError : (Result a, a -> Result b) -> Result b
Result.prototype.chainError = function(f) {
return this.isError ? f(this.data) : this;
}In the same spirit of the first post, we lift normal functions to act on values of type Result.
// lift1 : (a -> b) -> (Result a -> Result b)
Result.lift1 = f => (res => res.map(f))// error equivalent
Result.liftError = f => ( res => res.mapError(f) )
For lifting functions with more than 1 argument, since Result is a Monad instance, we can apply the same trick used with Future: using the sequencing operation (chain) to collect arguments, for example here is ‘lift2’ which lifts 2-ary functions
// lift2 : ( (a, b) -> c ) -> ( (Result a, Result b) -> Result c )
Result.lift2 = f => ((res1, res2) =>
res1.chain( v1 =>
res2.chain( v2 =>
Result.Success(v1, v2)
)
))Or we can cheat by looking directly inside the Result box
// lift : ( (a, b, ...) -> x ) -> ( (Result a, Result b, ...) -> Result x )
Result.lift = function(f) {
return (...args) => {
for(var i = 0, len = args.length; i < len; i++) {
var ai = args[i];
if(ai.isError) return ai;
}
return Result.Success( f.apply(this, args) )
}
}‘lift’ proceeds only if all its arguments are successful otherwise it returns the first error encountered.
Here is an example of counting the length of a file content.
// String -> Future (Result Number)
readFileF('test.txt').map( s => s.length );We can even implement the error handling operations as methods of Future
// this : Future (Result a)
// f : Result a -> Result b
Future.prototype.fmap = function(f) {
var fut = new Future();
this.ready( res => fut.complete(f(res)) );
return fut;
} // f : a -> b
// mapSuccess, mapError: (Future(Result a), f) -> Future(Result b)
Future.prototype.mapSuccess = function(f) {
return this.fmap( Result.lift(f) );
}Future.prototype.mapError = function(f) {
return this.fmap( Result.liftError(f) );
}// fut: Future (Result Number)
fut = readFileF('invalid path')
.mapSuccess( s => s.length )
.mapError( () => -1 )
To catch errors in monadic computations
// f : a -> Future (Result b)
// flatMapSuccess : (Future (Result a), f) -> Future (Result b)
Future.prototype.flatMapSuccess = function(f) {
return this.flatMap(
res => res.isError ? Future.unit(res) : f(res.data)
)
};Future.prototype.flatMapError = function(f) {
return this.flatMap(
res => res.isError ? f(res.data) : Future.unit(res)
);
}; // requestF : String -> Future (Result String)
resultF = requestF('/url1')
.flatMapError( res => requestF('/url2') )
Recursive ADTs
The type definition of Result is quite simple: a disjoint union between 2 other types. But the real power of ADTs lies elsewhere.
Consider the definition below, ubiquitous in functional programming literature, and quite similar to a linked list definition as found in imperative languages
List a = Empty | Cons a (List a)The above annotation can be read as:
- ‘List’ is a type that defines, for each underlying type ‘a’, a new type which can be either:
- an ‘Empty’ list, or
- a ‘Cons’ of 2 values :
- the first, its head, is of the underlying type ‘a’ and the second, its ‘tail’, is another List of ‘a’.
‘List’ is a typical example of a recursive type, i.e. a type that may be defined in terms of itself.
The form ‘List a = Empty | Cons a (List a)’ — borrowed from Haskell syntax — looks a clean and concise way to express things. Unfortunately, JavaScript doesn’t have syntax support for ADTs. We can still implement them using functions and objects, like we did early, but i propose another solution: a helper function that can make an ADT with a more concise syntax using ES6 object literals
function List() {}
adt(List, {
Empty : new List(), // a singleton
Cons : (head, tail) => ({head, tail}) // a factory function
});Not as concise as the Haskell definition but still better than verbose object creations (If you are interested here is the source code of ‘adt’).
An interesting property of types like List is that implementing operations on them follows naturally their recursive nature, take a look at the below definitions of some familiar list operations:
The well known ‘map’ function to transform list elements through a mapping function ‘f’
// map : (a -> b, List a) -> List b
function map(f, list) {
return list.isEmpty ? List.Empty
: List.Cons(f(list.head), map(f, list.tail))
}The ‘filter’ function can be defined the same way
// aBoolean : Object (JavaScript view of truth)
// filter : (a -> aBoolean, List a) -> List a
function filter(f, list) {
return list.isEmpty ?
List.Empty
: (f(list.head) ?
List.Cons(list.head, filter(f, list.tail))
: filter(f));
}‘take’ which takes the first ‘n’ items from the beginning of the list
// take : (Number, List a) -> List a
function take(n, list) {
return this.isEmpty || n < 1 ?
List.Empty
: List.Cons(list.head, take(n-1, list.tail))
}The usage of recursion in all the definitions above is a fundamental pattern in recursive types. It is a typical case of pattern matching because we are matching each variant in the type in order to decide what to do.
Infinity via Laziness
Another useful property of recursive types is the ability to define infinite data structures. Consider for example this function which builds an infinite list from a single value
// repeat : a -> List a
repeat = val => List.Cons( val, repeat(val) )// takes 5 'Hi's
take(5, repeat('Hi'))
If you run this code in JavaScript, you’ll soon get a “Maximum call stack size exceeded” error.
This simple example illustrates the most fundamental difference between (purely) functional and imperative languages.
In order to evaluate the ‘take(5, repeat(‘Hi’))’ call, JavaScript starts from inside; as detailed in the sequence below
- evaluate take(5, repeat(‘Hi’)) leads to evaluating the 2 given arguments
- evaluate the 1st argument 5
- evaluate repeat(‘Hi’) which expands to List.Cons( ‘Hi’, repeat(‘Hi’) )
- again evaluate the 2 arguments of List.Cons, starting with ‘Hi’
- then evaluate repeat(‘Hi’) which brings us back to step 3
And so on, since there is no terminating condition to break the recursive calls the program will, theoretically, never terminates.
In a typical FP language like Haskell the evaluation will starts from outside. Evaluation of ‘take(5, repeat(‘Hi’))’ will not evaluate the given arguments immediately, instead the runtime expands the body of ‘take’. In FP jargon, we say that expression ‘take(5, repeat(‘Hi’))’ is substituted with the equivalent definition.
In the example above, we can trace the evaluation by respectively subsituing terms in the experssion by their corresponding definitions. Here is an illustration of the first steps
1 => take(5, repeat('Hi'))2 => *repeat('Hi')*.isEmpty || 5 < 1 ?
List.Empty
: List.Cons(*repeat('Hi')*.head,
take(5-1, *repeat('Hi')*.tail))// expands *repeat('Hi')*
3 => List.Cons('Hi', repeat('Hi')).isEmpty || 5 < 1 ?
List.Empty
: List.Cons(List.Cons('Hi', repeat('Hi')).head,
take(5-1, List.Cons('Hi', repeat('Hi')).tail)) 4 => List.Cons(List.Cons('Hi', repeat('Hi')).head,
take(5-1, List.Cons('Hi', repeat('Hi')).tail))5 => List.Cons('Hi', take(4, repeat('Hi')))6 => List.Cons('Hi', take(4, **same as in step 2**))
Note how the evaluation of ‘repeat(‘Hi’)’ is delayed until the step 3, where we look into the list in order to decide if it’s empty or not. Also note how the expansion from the step 3 gives us only ‘List.Cons(‘Hi’, repeat(‘Hi’))’ instead of the entire list. We don’t actually need the full/infinte list in order to evaluate if the list is empty or not, the returned ‘List.Cons(‘Hi’, …)’ expression is sufficient by itself.
So completing the sequence of evaluations above will expand repeat(‘Hi’) only when necessary, as we are advancing in our process. Once we reach the step where ‘n == 0’ , the ‘take’ expression will yield the ‘List.Empty’ result so no further evaluation will take place.
We say pure FP languages are lazy. They defer evaluation of expressions until necessary. In the example above, the need to evaluate the second argument will not occur until the take function start looking inside the given list to make a decision (if empty stop taking, if not continue taking). “start looking inside” in FP jargon is called pattern matching because we are matching the List ADT with each of its variants. This is the reason we say that in FP, evaluation is essentially driven by pattern matching.
In contrast, languages like JavaScript are said to be strict, or with eager evaluation because expressions like in function arguments will be evaluated immediately.
Although JavaScript is not a lazy language, it’s easy to define infinite types by simulating laziness. Back to the List example, we modify the list definition
List a = Empty
| Cons a (List a)
| Lazy () -> List aThe new definition adds a new variant, a List can now also be a ‘Lazy’ list with a thunk : a getter function taking no input and returning a ‘List’. This way, the thunk function can express our meaning without actually evaluating it, we’ll decide ourselves when to force its evaluation. In fact, you can use this trick to transform any expression ‘x’ by simply putting ‘() =>’ in front of it(eg. ‘x+y’ will become ‘() => x+y’ and if x and y are themeslves lazy values the expression becomes ‘() => x()+y()’).
The new definition using our adt helper function is
function List() {}
adt( List, {
Empty : new List(),
Cons : (head, tail) => ({head, tail}),
Lazy : thunk => ({thunk})
})Now we can create an infinite list by making the 2nd argument to ‘repeat’ a lazy list
repeat = val => List.Cons(val, List.Lazy(() => repeat(val)))Here is an example on how to define the ‘filter’ function given the new definition
// filter: (a -> aBoolean, List a) -> List b
function filter(pred, list) {
return list.isEmpty ? List.Empty
: list.isCons ?
( pred(list.head) ?
List.Cons(list.head, filter(pred, list.tail)
: filter(pred, list.tail)
)
/* isLazy */ List.Lazy( () => filter(pred, list.thunk())
}In the case of a lazy list, we just return another lazy list that reflects the filter on the materialized list.
The question here, when to force the evaluation of a lazy list?
We’ve seen that in FP languages, evaluation is principally driven by pattern matching, but in our precise case, that’s entirely up to us. We could implement all list functions lazily like in ‘filter’ above, but it obviously doesn’t make sense, sooner or later we’ll have to do something with the real values.
For example, we can decide to force evaluation in the ‘take’ function (making it a strict function in a certain term)
// take : (Number, List a) -> List a
function take(n, list) {
return list.isEmpty || n < 1 ? List.Empty
: list.isCons ? List.Cons(list.head, take(n-1, list.tail))
: /* isLazy */ take(n, list.thunk()) // forces evaluationHere is an example that builds an infinite list of natural numbers, then takes the first 5 odd ones.
// an infinite list of natural numbers
nats = start => List.Cons(start, List.Lazy(() => nats(start+1)))// an infinite list of odd naturals
odds = filter(n => n%2, nats(0))// 5 first odd naturals
fiveodds = take(5, odds)
Recursive ADTs offers a more concise way to define operations using pattern matching and recursion, but in the cons part, if you have a big List, recursion can be a problem in the case of languages like JavaScript (here is a useful link to read more about this). This is not a problem in functional languages like Haskell which handle recursive calls quite efficiently.
Conclusion
ADTs are muchmore than just a syntax sugar or a repackaging of the existing OOP types. They offer a conceptual basis to reason about your program entities, forcing you to think explicitly about your function’s domains and codomains.
Simple ADTs like the ‘Result’ type, can serves as a context that enriches the meaning of simple values with additional information (is this value an error or a success value ?)
Recursive ADTs can offer a powerful abstraction to model complex data structures and implement their operations in a beautiful and concise code.
