blog

Explanation of liftA2 in JavaScript

April 16th, 2013

This came out of the recent JS Promises debate. @ForbesLindesay was confused by liftA2, so I thought I’d try to explain it.

I’ll tweak @pufuwozu’s examples so that they return values.

// Promises (called when both succeed)
liftA2(readFile('hello.txt'), readFile('world.txt'), function(hello, world) {
 return hello + ' ' + world;
});
// Optional values (only inserted into database when both exist)
liftA2(optionalUsername, optionalPassword, function(username, password) {
 return {username: username, password: password);
});
// Arrays (function called for each element of each array)
liftA2([1, 2, 3], [4, 5, 6], function(a, b) { 
  return a + b;
});

In the first example, we have 3 arguments:

  • two Promises of Strings
  • a function that takes 2 Strings and builds them into another string

In this instance, liftA2 returns a Promise of String. This Promise, when evaluated, evaluates the two input Promises and runs their resulting values through the input function.

In the second example, we have 3 arguments:

  • two Options of Strings
  • a function that takes 2 Strings and builds them into an Object.

In this instance, liftA2 returns an Option of Object. If both input Options are “some”, it runs them through the function to generate “some” of the resulting. If either input is “none”, the function is not called and “none” is returned.

In the third example, we have 3 arguments:

  • two Arrays of Numbers
  • a function that takes 2 Numbers and adds them together to form another Number.

In this instance, liftA2 returns an Array of Number. Each element in the resulting array is the sum of one Number from the first Array and one Number from the second Array. Each combination of an element in the first and the second is run through the function.

Let’s look at those types (using Haskell type syntax, as JavaScript doesn’t have types). a -> b just means a function that takes an ‘a’ and returns a ‘b’. The brackets denote ‘tuples’ – approximating JavaScript argument lists.

  • (Promise String, Promise String, (String, String) -> String)) -> Promise String
  • (Option String, Option String, (String, String) -> Object)) -> Option Object
  • (Array Number, Array Number, (Number, Number) -> Number)) -> Array Number

Note that there is ONE implementation of liftA2, not one for each datatype. Just one. So, how can one function deal with data of vastly different type? It all comes down to a pattern – Applicatives.

Promise, Option and Array are all Applicatives (as are all Monads). liftA2 takes two arguments of the same type of Applicative, with the same parameter type (actually the universal type in javascript). It “extracts” the values from the Applicatives, runs them through the function, then “boxes them back up” into a value of the applicative type.

So, what does it mean to “extract” and “box back up”? Well, that depends on the Applicative! It’s what makes one Applicative different from another! That’s exactly why liftA2 can apply to such vastly different data structures – because the relevant differences have been encapsulated in their implementation of Applicative.

So, what’s the type of this liftA2 function in JavaScript?

for all Applicatives f. for all types a, b, c. (f a, f b, f c, (a, b) -> c) -> f c

If you look at the types above, you’ll notice they all match this pattern, hence they all meet the requirements to call liftA2.

So, what does it require to be an Applicative?

  • You need to be a Functor, so you need a ‘map’ function.
  • You need a “point” function that wraps a value in the applicative.
  • You need an “ap” function of this type: for your Applicative f. for all types a, b, c. (f a, f b, f ((a, b) -> c)) -> f c

And, what does liftA2 look like? Courtesy of @pufuwozu

function liftA2(pa, pb, f) {
  return ap(pb, map(pa, function(a) {
    return function(b) {
      return f(a, b);
    };
  }));
}

That’s it? Really? That’s all it takes? For real. So much power, so little code. That’s the power of abstractions.

 

On Options of Options

April 16th, 2013

Following a recent discussion on JS Promises, I wanted to point out what an Option of Option would mean, from a type algebra point of view.

This article and this video  provide a good introduction to type algebra. As they discuss, we can define a type by an expression which is equivalent to the number of possible values of that type.

Void is 0, Unit is 1, Boolean is 2, Int is 2^32. What about Option?

Recall that Option x is either “none” or “some x”, for all types x. This makes it 1 + x.

So, say a type q has 3 values. An Option of q can have “none” or one of the 3 values – i.e. 4 possible values.

So, then an Option of Option of x = 1 + (1 + x) = 2 + x. This corresponds to:

  • the outer Option is none (1 value)
  • the outer Option is some, but the inner is none (1 value)
  • the outer Option is some, and the inner is some of type x (x values)

So, an Option of Option of x is really just: (special value 1) or (special value 2) or x. In other words: 2 + x, which is equivalent to:

data Option3 x = A | B | C x

Consider:

You’re writing a cache system (in the form of an associative map) in front of a persistent storage with nullable values. Question: how do you differentiate between “I haven’t cached this value” from “I’ve cached the value and it was null in the database”? The answer is that you can’t use “null” to mean both things, it’s ambiguous. – http://james-iry.blogspot.com.au/2010/08/why-scalas-and-haskells-types-will-save.html

In this example:

  • “special value 1″ is “I haven’t cached this value”
  • “special value 2″ is “I have cached it, but it’s null”
  • otherwise, we have an actual cached value

 

CUPS printer server on Freebsd

January 26th, 2012

Mainly for my own reference. This is how I did it:

  1. Install Avahi (was already installed for netatalk/afp)
  2. Install CUPS per http://www.freebsd.org/doc/en/articles/cups/index.html
    1. Installed without Avahi support, due to some known bug. This prevents CUPS telling Avahi about the printer and requires the service file below.
  3. Magic sprinkles in /usr/local/etc/cups/cupsd.conf:
    1. Add an appropriate “allow” statement to the <Location />, otherwise it denies access
    2. ServerAlias *
  4. Downloaded printer driver file from http://www.openprinting.org/printers
  5. Set up printer via cups weberface.
  6. Tweaked and saved config via cups weberface – note this blats the config so check settings manually
  7. The avahi settings file template from http://wiki.zs64.net/FreeBSD,_CUPS_and_iPad_printing

The “Maybe Cake” puzzle

October 25th, 2011

Here’s a programming puzzle I created, which deals with a bunch of dependent pieces of “optional” data. The idea is to model the constraints in the problem description, and resolve them in order to produce a cake. Solve it in any way you like, in whatever language. I’ve set up a template in Haskell (MaybeCake.hs), so you just have to define one function. I’ve also provided a solution (MaybeCakeAnswer.hs). The Haskell source uses the Maybe data structure, but other solutions may be possible. github repo.

Apologies if my recipes are rubbish – I’m not much of a baker :) Enjoy!

I’d like a cake.

Ideally, I’d like to bake it myself, but if I don’t have the ingredients, I’ll buy one from the bakery (if they have one).

I can make 2 types of cake:

  • My favourite is a mud cake (egg, chocolate, flour).
  • I can also make a flourless cake (egg, chocolate, cocoa).

There might be some chocolate in the fridge or the pantry.
There might be some flour in the pantry.
There might be some cocoa in the pantry.

There might be an egg in the fridge, but I’d prefer a fresh one – maybe my chook laid one?

But I think I saw a taipan around the chicken coup yesterday – hopefully he didn’t get my chook!

So, do I get a cake and, if so, which one?

Entertaining the warranty return department

July 29th, 2011

Dear warranty return department,

Oh dear! My beloved SSD has departed from this world! Like a true rockstar, he shone too bright and died too young! Oh, cruel fate, to be thusly boned. Ask not for whom the bone bones, it bones for thee, dear Vertex. Please take care of my dearly departed as he enters the next world – the warranty return department.

On Wednesday eve, around 6pm, he suffered a heart attack in his sleep, and was henceforth no longer recognised by the bios. Several attempts were made to resuscitate him (in a Dell Poweredge server and Vantec disk dock), but it was too late. The doctors pronounced him dead at 7:54am Friday 29th July.

He will be remembered as a rebel. Ahead of his time – a star performer and a true testament to his generation. He will be missed by friends, family and coworkers alike. May he rest in peace.

Emulating infix operator syntax in javascript

June 18th, 2011

In Maths, we write 1 + 1, but in many programming languages this becomes prefix: +(1, 1) or plus(1, 1) or (plus 1 1) or number(1).plus(1). Many languages directly support an infix notation, e.g. Haskell and Scala. This is particularly nice as a way of unifying the concepts of operators and function while providing a nice syntax for functions with symbolic names like +, -, >>=. I found a way of emulating this in Javascript.

In js, properties of objects can have any name, even if that name is a reserved word or invalid identifier. e.g. {“a” : 3, “><!!”: 3, “private”: 4};. When you refer to a property, you can use either object.property or object["property"]. We’ll exploit the latter.

Example 1: String Split

For a simple example, say I want to split a string by a character.  There’s a function String.prototype.split for this, so I can write:
“a,b,c”.split(“,”)

Let’s change it to a symbolic infix operator. Ideally, we’d like to write:
“a,b,c” | “,”

We can come close:
(“a,b,c”) ["|"] (“,”)

by doing:
String.prototype["|"] = String.prototype.split

So, imagine all values are enclosed in () and all operators enclosed in [""] – we take this on as syntactic noise, but otherwise we have the desired syntax. The key thing is really getting rid of the “.” to make it look more of an operator than “invoking a method on an object”.

Example 2: >>= on Maybe

>>= is the monadic bind operator in Haskell. If you don’t fully understand that sentence, please stop reading and go learn it, it kicks ass and is far more important than this post :)

My favourite monad is Maybe. Here’s a simple example of binding over Maybes in Haskell:

f = \x -> if (x > 3) then Just(x + 1) else Nothing;
g = \y -> y >>= f >>= f

In javascript, it’s tricky to write the monad abstraction, but simple to write specific monads – you just have to repeat yourself a lot. I’ve cooked up a very basic Maybe in Javascript which defines a >>= operator. The equivalent example looks like this:

var f = function(x) {  return x > 3 ? Just(x + 1) : Nothing; };
var g = function(y) {  return (y) [">>="] (f) [">>="] (f); };

The code is up at https://github.com/techtangents/jsinfix

Type Algebra: 2+2 = 2*2

May 27th, 2011

“Since 2*2 == 2+2, then (Boolean, Boolean) is equivalent to Boolean | Boolean” – Tony Morris

Word.

Below is how you can construct these two types in Haskell, and show their equivalence. It’s interesting the different ways each type encodes the same data. One encodes the two booleans as the first and second member of the pair, whereas the other encodes one boolean as “which constructor did you pick” and the other as “what boolean did you pass to the constructor”. I think the names of the two constructors (“TrueAnd” and “FalseAnd”) highlight how the encoding works.

module BoolEquivalent where

import Test.QuickCheck

data B2 = TrueAnd Bool | FalseAnd Bool
 deriving (Eq, Show)

data P2 = P2 (Bool, Bool)
 deriving (Eq, Show)

pToB :: P2 -> B2
pToB (P2 (True, x)) = TrueAnd x
pToB (P2 (False, x)) = FalseAnd x

bToP :: B2 -> P2
bToP (TrueAnd x) = P2 (True, x)
bToP (FalseAnd x) = P2 (False, x)

instance Arbitrary B2 where
 arbitrary = oneof $ return `fmap` [TrueAnd True, TrueAnd False, FalseAnd True, FalseAnd False]

instance Arbitrary P2 where
 arbitrary = oneof $ (return . P2) `fmap` [(True, True), (True, False), (False, True), (False, False)]

prop_inverse1 :: B2 -> Bool
prop_inverse1 x = (pToB . bToP) x == x

prop_inverse2 :: P2 -> Bool
prop_inverse2 x = (bToP . pToB) x == x

go = do
 quickCheck prop_inverse1
 quickCheck prop_inverse2

Dependently-typed, fine-grained effect types for safe parallelism

May 2nd, 2011

Pure functions are parallelisable. That is, two pure functions may be run in parallel or in sequence, and yield the same result (provided that there is no data dependency between the two).

Impure functions do not have this property. As they contain side effects, evaluation order matters. When attempting to parallelise, parallel sequences of effects may have interrelations which result in different semantics when run in parallel or in sequence.

Yet, we can intuit that some effects are safe to parallelise. Take for example, the following haskell functions:

write1 :: IO ()
write1 = writeFile “/tmp/file1″ “a”

write2 :: IO ()
write2 = writeFile “/tmp/file2″ “b”

both :: IO ()
both = write1 >> write2

“both” writes the two files in sequence… however, writing them in parallel would give the same output. Contrast to the following:

write1 :: IO ()
write1 = writeFile “/tmp/file1″ “a”

write2 :: IO ()
write2 = writeFile “/tmp/file1″ “b”

both :: IO ()
both = write1 >> write2

As ‘write1′ and ‘write2′ are both writing to the same file, order of execution matters, and it is not safe to parallelise.

So, one set of functions is safe to parallelise, but the other is not. If the programmer wants to take advantage of parallelism, it is up to them to guarantee the safety of it. This is risky. It would be better if there was a static guarantee, checked by the compiler. Let’s encode this information in the type system.

All of the above functions are of type IO (). This is a very broad type – any effect can be performed within IO. We need more specific types, for specific effects.

Firstly, we can identify that the writeFile function performs file IO. Let’s consider an effect type “FileIO”. So, writeFile’s type would become “FilePath -> String -> FileIO ()”. This doesn’t solve the problem above, however, imagine if we had a similar effect type “NetworkIO”. A function of type “NetworkIO ()” could safely run in parallel with a function of type “FileIO ()”, since network and file IO will not impact each other.

To directly solve the problem above, we need to go more fine-grained. We know that (writeFile f s) will only write to file “s”. Since s is a value, we need dependent types. The type of writeFile now depends on the argument to parameter s.

If we modify Haskell syntax to include dependent types, we could denote this as:

writeFile :: (a :: FilePath) -> String -> FileIO a ()

FileIO is now a type constructor with one value parameter and one type parameter. The value parameter denotes what file the effect is allowed to access.

With this in mind, the two functions above could be written as:

write1 :: FileIO “/tmp/file1” ()
write1 = writeFile “/tmp/file1″ “a”

write2 :: FileIO “/tmp/file2” ()
write2 = writeFile “/tmp/file2″ “b”

The paths are duplicated between the functions’ type signatures and declaration. A new syntax could allow refactoring of this. e.g.

write1 :: a = “/tmp/file1” => FileIO a ()
write1 = writeFile a “a”

write2 :: a = “/tmp/file2” => FileIO a ()
write2 = writeFile a “b”

We now have enough information in the types to know that the two operations are independent, and can be safely parallelised.

So, what would the type of “both” be? “both” is a function that takes no arguments, and writes to files “/tmp/file1” and “/tmp/file2”. Below are a few possible approaches, and the resulting type signatures.

  1. Create a type FileIOs that has a value parameter of type [FilePath].
    write1 :: FileIO [“/tmp/file1”] ()
    write2 :: FileIO [“/tmp/file2”] ()
    both :: FileIOs [“/tmp/file1”, “/tmp/file2”] ()
  2. Just use a FileIO type that takes a list of files.
    write1 :: FileIO [“/tmp/file1”] ()
    write1 :: FileIO [“/tmp/file2”] ()
    both :: FileIO [“/tmp/file1”, “/tmp/file2”] ()
  3. Introduce a scheme of conversions between types. Possible options include:
    1. An implicit conversion. “FileIO child” would automatically widen to “FileIO ancestor”.
    2. An explicit conversion to a Maybe type:
      widen :: (y :: FilePath) -> FileIO x -> Maybe (FileIO y)
    3. An explicit conversion to a common type. e.g.
      extend :: (z = commonAncestor x y) => FileIO x -> FileIO y -> FileIO z
    4. Automatic widening within the effect tracking system.
    5. Any function with parameters of type FileIO x and FileIO y has type FileIO “/”

There are obviously some challenges in implementing these schemes:

  1. Some of the information we want to put in the type system may not be available until runtime – e.g. what is the common parent of two files x and y?
  2. What happens in the case of symbolic links and mounted drives?

These would require further research.

Conclusion

The underlying concept is that of gaining leverage by preserving information. The implementation of “writeFile” has information that denotes that it can only write to one file, however, we throw this information away when we widen to IO. By preserving it and encoding it in the type system, we acquire useful static information about our programs. This can give effectful code some of the priviledges that only pure code currently enjoys, such as parallelism.

I suspect that it would also improve our ability to verify effectful code – a problem I described in a previous post. If I know that a function can only perform file IO in a certain folder, I can test by checking for evidence of filesystem changes in that folder. I know that it didn’t write anywhere else, and I know that it didn’t print to the screen or open network sockets.

Purity and Testability

April 8th, 2011

Only pure functions are truly testable. Moreover, the relationship between purity and testability forms a solid justification for functional programming.

Let me explain…

For starters, what is a pure function? A function without side effects. A function in the mathematical sense. Now, a function is a type of relation (set of ordered pairs), where each element of the domain corresponds to exactly one element of the range. A (total) function is also defined for each element of the domain, unlike a partial function, which is not.

So, what does this mean for testability? It means that I can potentially write a test which runs the function over each element of the domain, and asserts that the correct element of the range is returned. One simple way of doing this is to actually spell out the pairs that consitute the expected definition of the function, then map the function over its domain and zip the results with the domain, and then compare the two.

I’ll give an example with a boolean domain, as it has a small domain. I’ll use Haskell for simplicity.

Let’s look at the function isNot, which flips a boolean.

isNot :: Bool -> Bool
isNot x = if (x == True) False else True

Alternatively, pattern matching gives us a syntax which looks very much like the relation pairs:

isNot’ :: Bool -> Bool
isNot’ True = False
isNot’ False = True

Now, we could test this using the following functions – the both evaluate to True:

testTrue = (isNot True) == False
testFalse = (isNot False) == True

The domain is {True, False}, and the expected relation is {(True, False), (False, True)}. So, let’s do the map and zip thing. The ‘spellOut’ function does this for any function and any domain.

spellOut :: (a -> b) -> [a] -> [(a, b)]
spellOut f domain = zip domain (fmap f domain)

So, then we can say this, which is a complete test of this function.

test = (spellOut isNot [True, False]) == [(True, False), (False, True)]

Pretty cool, huh? Of course, there are many ways to test a function, this just works well for the demonstration.

Now, what happens if we throw a side-effect into the mix? The mathematical notion of a function has no concept of effects – it’s just a (total) relation between a domain and a range. Mathematical functions are defined, they don’t do things, they just exist. The concept of a side effect is introduced just so that software can do useful things.

In the pure function example, we tested by computing the (domain-value, range-value) pairs, and comparing with our expectations. An impure function still has a domain and range, but it also has other stuff that happens. We can compare domain/range pairs… but how do we test the other stuff?

There is nothing in the return value that indicates what side effect has been performed (I’ll get to effect tracking in a minute). Imagine if we could get a value that definitively represented a side effect that was performed… if that value was part of the return value, then we could compare that value against our expected. No such concept exists – a side effect is something that happened, it can be described, but it cannot be bottled up into a value.

So, what can we do instead? Well, we can execute the side-effecting function, then look for evidence that the expected side effect happened. This is better than nothing, but it is still not a true test of the side effect – you are only looking at some state that could have been influenced by the expected side effect. It’s like investigating crime – looking for clues in a crime scene, relying on witness testimony, maybe you’ll get a conviction, maybe not. Maybe someone is lying. Did a crucial piece of evidence go missing? Did someone alter the crime scene? What if we send an innocent person to jail, or let the guilty party go free?

Perhaps the effect didn’t fire, but some background process did a similar thing (false positive). Perhaps the effect did it’s job, but then a background process reverted it (false negative). There is no way of knowing.

Worse, the Observer Effect comes into play – observing an event changes the event. In our case, in order to observe the side effect, we are performing another side effect. As such, there are two effects occurring, whereas in production there would only be one. Your extra effect could give you false positives or false negatives.

It gets even worse than this! You are looking for clues that a certain effect was performed, but what if the function you’re testing performed another effect? You cannot test that a function does not perform any other effects in addition to the one you are observing.

Now, there is some good news here, in the form of Effect Tracking. Effect Tracking is compiler-enforced acknowledgement of side effects. That is, if a function contains code that can performs a side effect of type X, then X must be part of its type signature. This will tell you that no effects of type Y can occur… but you still have many of the problems above when looking for evidence of type X. Effect Tracking also lets you easily see which functions are pure and which are not. It also encourages you to write more pure functions. And, in Haskell, effects are tracked using monads, so you have all the normal monadic tools available to help you deal with them. The flipside is that, at least initially, it feels like you are spending a lot of time fighting with the effect tracking and going in and out of monadic code… there’s a learning curve, but it does become easier, and the benefits are massive. And I’m definitely up for learning something hard if it improves my code.

So, given all of these problems, I’m of the opinion that side effecting code is not testable. Of course, this comes down to the definition of “testable” and, furthermore, the definition of “test”. What does it mean to test a piece of code? What does it mean for a piece of code to be “tested”?

In the first example, I wrote a test that definitively and exhaustively proved the relationship between the domain and range. That code is tested. No arguments there.

What about a side-effecting function? We can write a “test” that executes the code and does some assertions, but it’s not the same. We haven’t proved anything. Certain defects may have resulted in test failures, and certain correct code may have passed, but we have no guarantees. That’s a far weaker position to be in… but maybe that’s the best we can do. But if it’s the best we can do, we want to write code in a way that minimizes how often we are in this position.

This really highlights the importance of keeping your code as pure as possible. Keeping a clear separation between logic and effect… and pushing that boundary hard. This is the essence of functional programming.

For me, testability is the number one justification for functional programming, and is how I got into it. TDD got me into writing tests, and I eventually realised that the tests were far easier to write, and far more reliable, when the code was pure. Of course, there are many other benefits of functional programming, but this has got to be the knockout punch.

BSD Slice Calculator

April 8th, 2011

The GPART command for FreeBSD does the job, but isn’t that friendly. In particular, specifying partition sizes in logical blocks is confusing. You need to do some planning to figure out your partition layout, and then translate that into gpart commands.

The BSD Slice Calculator helps with this. Plug in the values in the blue cells, and it’ll give you the start and size of each partition in blocks, which you can then plug into gpart. Download it from here (ods spreadsheet).