How to deploy a compiled iOS static library that uses other libraries

I recently ran into an issue that had me stumped for quite some time and wanted to capture the solution here both to help anyone in a similar situation and for future reference, or if someone wants to provide a comment to let me know I’m doing it all wrong and point me in the right direction!

What I wanted to achieve was to create a compiled static library that could then be published to cocoapods for easy use now there are plenty of resources that describe how to create a static library that uses other libraries and deploy it as source, one of the better ones I was using was at sigmapoint however none describe how to deploy as a compiled library, hence why I’m writing this post.

After working my way through the posts above I had my library with a Podfile, that had my dependency:

pod 'AFNetworking', '~> 2.2'

And had set my MyLib.podspec to have the listed dependency:

s.dependency 'AFNetworking', '~> 2.2'

Then in my app I added MyLib to the Podfile:

pod 'MyLib', :path => '../pods'

And then came across around 270 duplicate symbols errors, sigh.

My reasoning as to why this was happening is that in the MyLib cocoapods is compiling the AFNetworking code into libPods.a and this is being used to produce MyLib.a, then when the app is being compiled it too also has the reference to AFNetworking and is also trying to compile it into libPods.a however as it is alread in MyLib.a it runs into duplicate symbols errors.

So in order to solve this I did the following:

  1. Changed MyLib so it did not use a Podfile and instead just brought down just the header files for AFNetworking for the version I’m targeting and added them to the search path config
  2. Removed binary link to libPods.a from MyLib
  3. Did a pod update against my app and hey presto it build successfully!

What this does is allow MyLib to compile using the header files of AFNetworking but to not compile any of the concrete AFNetworking code into MyLib and instead AFNetworking only gets compiled in at the app compilation stage.

The importance of performing spike solutions

Firstly we should discuss what is a spike solution? Well according to The Art of Agile Development[Shore & Warden 2007]:

A spike solution, or spike, is a technical investigation. It’s a small experiment to research the answer to a problem.

The Extreme Programming site defines them as:

A spike solution is a very simple program to explore potential solutions. Build the spike to only addresses the problem under examination and ignore all other concerns.

Spikes

These two definitions line up perfectly and also go on to present one major point that must be made before continuing:

Spike/Spike solutions should never be committed into the main codebase

They should be treated as throw away code, once you have your answer it has served it’s purpose (if you must have the code under source control make sure it’s completely separate to the main trunk!).

I also want to clarify how I see the difference between spike solutions and prototyping which could appear very similar, prototyping usually encompasses a much larger goal such as putting some quick static front-end screens together to gauge the UX whereas spike solutions in contrast help to answer a specific technical question such as will EF be able to map to our legacy Users table correctly. This means that spike solutions should require a lot less time to complete and we should probably be time-boxing how long we spend on a particular spike to ensure this.

Now that we have defined what a spike solution is I want to go through a subset real world example (with name changes) that demonstrates there effectiveness when certain situations arise.

XMHELL

Back Story

Fubar DIY Stores Ltd has an e-commerce site that lists all the products available that can be bought, when a product is displayed reviews are also shown and new ones submitted, this was managed in house previously but now they have decided to use a popular global third party service Haveyoursay and they have assured them that they can provide a like for like data match to what we currently have stored.

So in order to bring in the reviews from Haveyoursay twice a day the reviews will be exported as an XML file, we have been tasked with using this exported XML file to import the reviews into the Fubar DIY Stores database so that they can then be retrieved along with the product data.

Making a start

For this example we will only be concentrating on the import of the XML file and ignoring the subsequent steps.

So we have completed a rough architecture of all the moving parts we roughly know which objects we need an how they need to collaborate with each other, essentially there will be a coordinating object that knows what steps need to be performed in which order, this will be the ReviewImportCoordinator and has a method that will start the import PerformImport taking in the XML file path.

We know also that we need an object that ReviewImportCoordinator will collaborate with to read the XML file and bring back a trusty XmlDocument object that we can then use to parse the data we need and then save to the DB.

So we start writing our unit tests first for ReviewImportCoordinator and stub our IXmlReviewFileReader this has a method that takes the import file path and returns us our XmlDocument object and we continue with our unit testing of the import process.

Setting ourselves up for a fall

It seems were doing everything right, we have broken the responsibilities up into separate objects and are using TDD/BDD against our import process. However we have jumped the gun here and are making some big assumptions about how we go about reading the XML file which will have an impact on how our ReviewImportCoordinator does it’s work.

Just enough design

This is were people new to agile get it wrong and start jumping into the code rather than doing some design up front, agile does not tell you to do any design is tells us not to big design up front were we try and guess everything about the system before any code is written.

Our first task should be to get a copy of the XML file this will get rid of our assumptions about how to handle the XML import, so after chatting to the stakeholder we get a copy of the XML file and good job we did as we hit a potential hurdle, the file is around 450MB this new discovery should start us asking questions:

  • Is this a one off or are they all going to be around this size?
  • How much memory will be used if we load this into an XML DOM?
  • Will the machines that are running the import be impacted by the extra memory usage?

After asking the stakeholder for some other import files they are also around 450MB so this seems to be the expected size for each import, so now we can move onto our crucial question How much memory will be used if we load this into an XML DOM? until we get the answer we have no way of knowing whether the will be an impact on the memory usage.

Time for a spike solution

This is the ideal time for us to write a spike to discover the answer, so we knock together a very quick console app with some hacked together code in the Main method, that simply loads an XmlDocument using one of our supplied import files as the input and a Console.ReadLine() so that it waits for input to allow us to open up task manager and discover how much memory the process is using (we just need a ballpark figure otherwise we could use some profiling tools to get more insight).

static void Main(string[] args) 
{
    XmlDocument.Load(@"c:\haveyoursay\imports\import.xml");
    Console.ReadLine();
}

Getting Feedback

So after we run our spike solution we find that the process is using around 1GB of memory to load the import XML into a DOM, we now have a confident number that we can go back to our stakeholder with in order to find out what impact this will have on the machine running the import.

After discussing with the stakeholder it turns out this machine is already being used to perform other jobs and will suffer badly from having that much memory being taken away from these jobs, so we have to look at streaming the XML file rather than loading it into a DOM so we need to use XmlReader rather than XmlDocument so we can now start to unit test using this knowledge and heading down the right path from the start.

Summary

I hope this demonstrates how we can use spike solutions with a little design up front to help steer us in the right direction, this example was done at the time of implementation you can also use spike solutions as part of estimating when you have to use a unfamiliar technology, library, protocol etc… It can give you a quick way of gauging how difficult it is perform certain tasks to give you a bit more confidence in your estimates.

So next time your stuck with a technical question a spike solution could be just what your after!

Functional Programming & DSL’s Part 3

Tidying up our DSL

In the last part we added filtering of results via the where function and showed how we can compose functions to enable expressive and re-usable criteria but we were left with an somewhat awkward way of calling our functions together, what we need is a function to stitch them together.

Creating query

The 2 functions we have created so far (select & where) when executed return another function that then accepts an array of objects (in our example this is user objects) essentially this allows us to configure how we want the functions to behave before sending them the actual users, this is good because it means that we can treat each function as abiding by the same contract that it will accept an array of objects and return an array of objects so our query function simply needs to call each function in turn and pass the results from one to the next[1].

//+ query :: ([a], [(fun [a] -> [b])]) -> [b]
var query = function (items /*, funs */) {
  var funs = _.rest(arguments);
  return _.reduce(funs, function (results, fun) {
    return fun(results);  
  }, items);
};

The first argument is our array of objects, after that is the functions that will be called with the array of objects, we are using the _.reduce function like we did in the all function in the previous part to call each function in turn and capture the results for every call to feed into the next, this can then be called:

query(users,
      where (all (female, overEighteen)),
      select (id, dob, gender));
//=> [Object]

This is a lot easier to consume and is very close to our ideal DSL, there is still some noise which would be great to get rid of namely parentheses and the semi-colon at the end, lets see how we can improve this.

Enter CoffeeScript

CoffeeScript is a language that transcompiles to JS it has a ton of various features and also cuts down massively on the amount of noise needed compared to standard JS (at present[2]), we can write our expression above as:

query users, 
      where(all female, overEighteen) 
      select id, dob, gender
//=> [Object]

I could almost get rid of all the parentheses but found that if I removed it from the where it short circuited and did not execute the remaining functions, I think this is because it struggles to parse on the all function, so you could rewrite it to this if were really keen:

criteria = all female, overEighteen
query users, 
      where criteria
      select id, dob, gender
//=> [Object]

This is probably as close as we can get to our ideal DSL for querying and I think it’s pretty damn close!

var results = query users                
              where all female, overEighteen
              select id, dob, gender

Extending our DSL

Now we have our building blocks we can start to extend the language of our DSL in this example I’m going to demonstrate how we can add ordering into our query, so we should then be able to write the following:

query users, 
      where(all male, overEighteen)
      orderBy dob
      select id, dob, gender
//=> [Fri Aug 23 1957 00:00:00 GMT+0100 (GMT Daylight Time), Mon Apr 02 1979 00:00:00 GMT+0100 (GMT Daylight Time), Wed Feb 01 1984 00:00:00 GMT+0000 (GMT Standard Time)]

To implement orderBy we can use the _.sortBy function which takes in an array of objects and can either sort on a provided function or on a string name for a property we can use the second approach for this and reuse our functions we use for the select function that return us hardcoded strings:

var sortBy = reverseArgs(_.sortBy);

//+ orderBy :: (fun -> string) -> [a] -> [a]
var orderBy = function (prop) {
  return _.partial(sortBy, prop());      
};

We partially apply over the sortBy function and pass it the returned string from the call to the prop function supplied.

Closing Thoughts

I hope this has been a helpful demonstration of how we can use FP with JS (and some CS to get a cleaner syntax) to enable creation of DSL’s I know some may be thinking that this seems like quite a bit of work to get working however I think the following need to be taken into account:

  • A lot of the functions we ended it up writing were general purpose and will either be re-used in other areas or already be provided for in other FP libraries functions like reverseArgs would not even be needed if underscore had it’s arguments geared up for partial application and prop are going to be useful in lots of other places.
  • Like I demonstrated in part 1 this query DSL is not specific to any particular object type and can be applied to any objects this is in contrast to OOP which tends to be built with specific types to work against
  • The actual code needed when lumped together is 84 lines which is not a great amount[3] considering the nice maintainable DSL that your left with

The final code can be found on jsfiddle


  1. You could also call this function pipeline but query fits closer to the querying domain
  2. If you look at what’s in the pipeline for JS a lot of the features CS offers will be added directly to JS, also after spending time looking at FP with JS some of the features offered by CS become less in demand (array comprehensions for example if you have map)
  3. I would imagine using some other FP libraries and having someone more experience with FP than I’am you could probably halve this :)

Functional Programming & DSL’s Part 2

Previously…

We managed to get a select function that enabled us to work towards our ideal querying DSL, we also found that although in this example we are using user objects the select function can be used against any object type and demonstrates that in FP a lot more emphasis is put on functions working against specific data structures and that the objects are not associated with particular types but become simple datasets.

Moving onto where

The next step is to see how we can restrict results, if we re-acquaint ourselves with our ideal DSL for querying it looked like this:

var results = query users                
              where all male, overEighteen
              select id, dob, gender

To start with if we simplify the where function so that it deals with a single predicate[1] we end up with:

//+ where :: (fun a -> boolean) -> [a] -> [a]
var where = function (pred) {
  return function (items) {
    return _.filter(items, pred);      
  };
};

We utilise the _.filter function which as you can guess takes an array of items and then a predicate and will return a new array of the items that pass the predicate supplied, as with the other underscore functions we are having to write more code because of the argument ordering, I will use the reverserArgs function I created in part 1 to solve this:

var filter = reverseArgs(_.filter);

var where = function (pred) {
  return _.partial(filter, pred);
};

Our new where can partially apply over the predicate supplied and then we just need the items to be provided. This can now be called like so:

var male = where(function (u) { return u.gender === 'm'; });
_.first(male(users));
//=> {id: 1, username: "jbloggs", dob: Wed Feb 01 1984 00:00:00 GMT+0000 (GMT Standard Time), displayName: "Joe Bloggs", gender: "m"…}

This works well for a single predicate however we want to be able to specify multiple predicates to filter on any number of criteria and this is were all comes into play:

//+ all :: [(fun a -> boolean)] -> a -> boolean
var all = function (/* preds */) {
  var preds = _.toArray(arguments);
  return function (item) {
    return _.reduce(preds, function (result, next) {
      return result && next(item);    
    }, true);
  };
};
  1. It accepts a number of predicates that will be used to test an individual item against
  2. A closure is returned that accepts a single item
  3. We use the _.reduce function to enumerate our predicates the first thing we check is that we are still returning true for the current item and if so we check the item with the next predicate[2]
  4. The end result will either be true or false depending if the item met all the predicate conditions or not

I have a feeling there is a better way this can be expressed in a more succinct way and would be happy if anyone can demonstrate this in the comments :) Let’s take it for a test drive:

var male = function (u) { return u.gender === 'm'; };
var firstnameIsJuan = function (u) { return (/^juan/i).test(u.displayName); };
var criteria = all (male, firstnameIsJuan);
_.map(users, criteria);
//=> [false, false, false, true, false]

Although a bit convoluted it does demonstrate that the 3rd user in our array is correctly being identified as being male and with a first name of ‘Juan’, because this conforms to a predicate we can now plug it into our where function:

var results = where(all (male, firstnameIsJuan));
_.first(results(users));
//=> {id: 4, username: "jfranco", dob: Mon Apr 02 1979 00:00:00 GMT+0100 (GMT Daylight Time), displayName: "Juan Franco", gender: "m"…}

The results have 1 item that is as expected our 3rd entry in the users array.

Composing Expressions

One of the nice aspects of this approach is how you can compose together expressions to make them fit the problems we are trying to solve in a nice readable way and also enable re-use, say for starters we have some functions already written to check values:

//+ isMale :: string -> boolean
var isMale = function (gender) { return gender === 'm'; };

//+ checkAgeAgainstDate :: (number, date) -> boolean
var checkAgeAgainstDate = function (age, date) {
  return new Date(
          new Date().setFullYear(
              new Date().getFullYear() - age)) > date; 
};

Now at the moment these functions take in primitive values we are using user objects that have these primitive values inside them, our first try at re-using the functions above may look like this:

//+ male :: a -> boolean
var male = function (u) { 
  return isMale(u.gender); 
};

//+ overEighteen :: a -> boolean
var overEighteen = function (u) {
  return checkAgeAgainstDate(18, u.dob);
};

This works but were having to create brand new functions to wrap up the call to the helper functions, notice that in both cases all I’m doing is extracting the correct property from the user object, if I can wrap this action up in a function I can then compose this new function against the corresponding helper function:

//+ prop :: (string, a) -> b
var prop = function (prop, obj) { return obj[prop]; };

It actually ends up being a really simple function thanks to the dynamic nature of JS, we can now create some functions that partially apply over the correct property:

//+ getDob :: a -> date
var getDob = _.partial(prop, "dob");

//+ getGender :: a -> string
var getGender = _.partial(prop, "gender");

I have used a get* prefix so as to not to confuse with the existing functions we use for selecting the properties we want in the select function we saw in part 1[3], Now we use these to compose against:

//+ male :: a -> boolean
var male = _.compose(isMale, getGender);

//+ overEighteen :: a -> boolean
var overEighteen = _.compose(_.partial(checkAgeAgainstDate, 18), getDob);

The _.compose function reads from right to left and makes a new function as you’d expect that will call pass getGender into the isMale function (i.e. equiv. to male(isMale(getGender(user)))[4] the overEighteen function is a little different as I’m actually using partial application again to bind the checkAgeAgainstDate function to use 18 for the age argument I have inlined it here but if you were going to use an over 18 check in other places you could assign it to a new function.

Another example of were composition comes in handy can be demonstrated if we want to return all the female users, typically this would be the approach:

//+ isFemale :: string -> boolean
var isFemale = function (gender) { return gender !== 'm'; };

However we can utilise the existing isMale function an isFemale function is basically the opposite of the isMale function:

//+ not :: boolean -> boolean
var not = function (val) { return !val; };

//+ isFemale :: string -> boolean
var isFemale = _.compose(not, isMale);

First we define a very handy function not that will return the opposite of any value passed to it then using this we can compose the isMale function against not, we can now define and use our female function for querying against:

//+ female :: a -> boolean
var female = _.compose(isFemale, getGender);
var results = where(all (female));
results(users).length;
//=> 2

We now have our where and select functions available but to use them at the moment is quite cumbersome having to use _.compose:

var query = _.compose(select(id, dob), where(all (male)));

In the next part we will look at how to stitch them together and look at how we can get a nice looking DSL.


  1. A predicate in this context is a function that takes a value and returns true or false depending if it meets a certain criteria
  2. This allows us to short circuit the predicate check using the && operator
  3. I could have also scoped them into an object:
    var userprops = {
      dob: _.partial(prop, "dob"),
      gender: _.partial(prop, "gender")
    }
    var male = _.compose(isMale, userprops.gender);
    
  4. If you want to find out more about compose I did a post on it and also it’s cousin sequence

Functional Programming & DSL’s Part 1

Introduction

I have explored DSL’s (Domain Specific Language) many moons ago and at that time I was using Boo (Python based .net language) after reading Ayende’s DSL book, it was a great choice as the language offers a lot of powerful capabilities way beyond C#, in the end I put together a DSL for log4net configuration.

While working my way through FP the topic of creating DSL’s has stood out for me when you start go down the route of FP you essentially build up a DSL around the problems your trying to solve it’s surprising the expressiveness that can be achieved using FP techniques, what I wanted to do was to see how closely I can get to a perfect DSL using FP.

Querying

If we take querying for data as our example[1], first we need some data:

var users = [
  { id: 1, username: 'jbloggs', dob: new Date(1984,1,1), displayName: 'Joe Bloggs', gender: 'm' },  
  { id: 2, username: 'zball', dob: new Date(1964,2,16), displayName: 'Zoe Ball', gender: 'f' },
  { id: 3, username: 'jsmith', dob: new Date(1957,7,23), displayName: 'John Smith', gender: 'm' },
  { id: 4, username: 'jfranco', dob: new Date(1979,3,2), displayName: 'Juan Franco', gender: 'm' },
  { id: 5, username: 'scastle', dob: new Date(1998,10,11), displayName: 'Susan Castle', gender: 'f' }
];

Now if we wanted to query from this data users that were male, over eighteen and only wanted to return the id, dob and gender, the following would be pretty close to a perfect way of expressing this requirement:

var results = query users                
              where all male, overEighteen
              select id, dob, gender             

If we were to express this in an OOP way we would probably be going down the route of a query object:

var results = new UserQuery()
                .gender('m')
                .ageGreaterThan(18)
                .query(users)
                .map(function (user) { return { id: user.id, dob: user.dob, gender: user.gender }; });

And of course you tweak the Query object and add some objects that will help make some of the querying more adaptable and less hardcoded:

var results = new Query()
                .where(new Equal('gender', 'm'))
                .where(new GreaterThan('dob', date.minusYears(18)))
                .restrict(['id', 'dob', 'gender'])
                .query(users);

But there’s a lot of ceremony going on there with objects getting created in a number of places and this is a pretty simple query, let’s see how taking an FP approach pans out, essentially what we have here is a pipeline of actions against a dataset, so lets breakdown each of the actions to see if we can achieve as close to the ideal DSL, first let’s start with select:

//+ select :: [string] -> [a] -> [b]
var select = function (/* props */) {
  var props = _.toArray(arguments);  
  return function (items) {
    return _.map(items, function (item) { 
      return _.pick(item, props); 
    });
  };
};

var selectResult = select('id', 'dob')(users);
console.log(selectResult);

To help with some of functional lifting I’m using underscore _.toArray and _.map don’t need explanation, the _.pick function takes an object and a series of strings for every property to retrieve on the passed object.

Ok this isn’t so bad we know that select is going to be used to specify which properties on the dataset we want returned and being part of the pipeline it is going to be eventually called with the items so I have used currying to set this up. I think we can do better regarding the properties and the moment we are using string literals ideally it would be nice to not have to use strings, we could either specify some variables to act like “constants”:

var id = 'id';
var dob = 'dob';

This works but is incredibly fragile as JS does not support true constants that cannot be mutated, what if we treated them instead of strings but as functions that when executed always returned the same value, we can use the _.partial and _.identity functions to achieve this:

var id = _.partial(_.identity, 'id');
var dob = _.partial(_.identity, 'dob');

id();
//=> id

_.identity will return the exact same value that is passed to it when called, and so I partially apply this function using _.partial specifying the value I always want to return.[2] We now need to change the select function because at the moment it is expecting strings to be passed in not functions:

//+ invoke :: (fun (a) -> b) -> b
var invoke = function (fun) { return fun(arguments); };
var concatResult = _.map([id, dob], invoke);
concatResult()
//=> ["id","dob"]

Here I have defined an simple function that takes a function in and invokes it passing any arguments and returning the result, we can then test this out by using _.map and as we can see correctly returns an array of the results of each function call. Now we can use this new function inside select:

//+ select :: [(fun () -> string)] -> [a] -> [b]
var select = function (/* props */) {
  var props = _.map(_.toArray(arguments), invoke);
  return function (items) {
    return _.map(items, function (item) { 
      return _.pick(item, props); 
    });
  };
};

You can see that props has now been changed so that it is a map for each argument passed in, the next thing we can do is get rid of the need for the anonymous function used in the map the only reason we currently have it there now is to capture the item argument that is then passed to the _.pick function what we can do is get rid of this middle step and have the map pass the item straight through, at present this is tricky because we can’t partially apply this function because it takes the item as the first argument[3], so lets first create a reusable function to allow this:

//+ pick :: [string] -> a -> b
var pick = function (props, item) {
  return _.pick(item, props);  
};

First we create a simple function that swaps the arguments and delegates to the underscore _.pick function.

//+ select :: [(fun () -> string)] -> [a] -> [b]
var select = function (/* props */) {
  var props = _.map(_.toArray(arguments), invoke)
    , picker = _.partial(pick, props);
  return function (items) { 
    return _.map(items, picker); 
  };
};

Next we can now partially apply over the the new pick function supplying the properties we want to pick, this means we can remove the anonymous function, one thing that might stand out is that we have a similar situation with the returned function we are simply using the items argument to then pass onto the _.map function if we could do the same thing we can return a partially applied map, this arguments issue is becoming quite a nuisance instead of having to create a new function from scratch let’s create a reverseArgs[4] function that will return the same function but will reverse it’s arguments when called:

//+ reverseArgs :: fun -> fun -> a
var reverseArgs = function (fun) {
  return function (/* args */) {
    var args = _.toArray(arguments);
    args.reverse();
    return fun.apply(null, args);  
  };
};

//+ map :: (fun a -> b), [a] -> [b]
var map = reverseArgs(_.map);

map follows the same strategy as pick in that it swaps the arguments over and delegates, this now opens the door to allow us to partially apply:

//+ select :: [(fun () -> string)] -> [a] -> [b]
var select = function (/* props */) {
  var props = _.map(_.toArray(arguments), invoke)
    , picker = _.partial(pick, props);
  return _.partial(map, picker);
};

We have managed to remove all the anonymous functions completely and instead are allow functions to call other functions without having to step in between, it now becomes clear what select performs:

  • Takes a number of arguments that are expected to be functions that return string values that will be properties of an object
  • Returns a function that when called with an array items will return an array of objects with only the properties specified populated

We can now start to use this select function:

var selectUsers = select(id, dob);
_.first(selectUsers(users));
//=> {id: 1, dob: Wed Feb 01 1984 00:00:00 GMT+0000 (GMT Standard Time)}

However one thing that is really good about this is that it is in no way tied to a user object, so we can use this for any object type:

var cars = [
    { reg: 'GNS 453A', make: 'Mitsubishi', model: 'Colt Ralliart' },
    { reg: 'HJD 112E', make: 'Ford', model: 'Focus RS' },
    { reg: 'JFS 672F', make: 'Vauxhall', model: 'Corsa VXR' }
];
    
var reg = _.partial(_.identity, 'reg');
var make = _.partial(_.identity, 'make');
    
var selectCars = select(reg, make);
_.first(selectCars(cars));
//=> {reg: "GNS 453A", make: "Mitsubishi"}

As long as I abide by the contract of what select needs it works perfectly for any object. In the next part I will look at where and how we can use it to filter results.


  1. Note that we are using a simple array and an object literal (treated like a map) rather than a user object like we would use in OOP.
  2. I know this is also susceptible to someone changing the variable to another function returning a different value, I have not shown it in the code examples but for all of these they should be inside there own scope which should lessen the likelihood of accidental changes.
  3. The argument ordering is one major annoyance with the underscore.js library as it seems to promote using _.chain based OOP style API rather than partial application & composition FP style, in fact there is a great video on youtube by Brian Lonsdorf which I highly recommend that goes into this in a lot more detail.
  4. We will also be using this for later parts.

Compose & Sequence created using recursion & imperative

Introduction

As I’m making my way further down the rabbit hole of the functional programming paradigm, I have found myself at the topic of recursion and wanted to do a post demonstrating how we can take an imperative operation and turn it into a recursive one but also using a real world example of something useful, hence why I decided that implementing compose & sequence[1] would be a good demonstration, first let’s get acquainted with these 2 functions.

Brief Introduction to Compose & Sequence

In functional programming you typically end up with functions calling other functions that then may also be called by another function[2], so if we had functions a, b and wanted to join them into a function called c:

var c = a(b);

This becomes harder to read as we have more nested calls, ideally we would like to pass the results of one function into another this is where compose and sequence come in, compose works from right to left and sequence left to right:

var c = compose(b, a);
// or
var c = sequence(a, b);

Typically compose is used as a function that takes 2 functions like the above in which case the implementation is trivial:

var compose = function (a, b) {
  return function () {
    return a(b.apply(b, arguments));  
  };
};

It returns a closure and applies on the second function using the arguments passed in and then uses the result of this call to pass to the first function and return the results. We can execute like this:

var print = function (val) { console.log(val); };
var double = function (val) { return val * 2; };

var display = compose(print, double);
display(10);

However in JS we can do much better than this because of its varargs support via the special arguments variable[3] so what I want to do next is go through how we can implement the compose & sequence functions using both an imperative approach or by using recursion.

Imperative Approach

First let’s start by creating the sequence function:

var sequence = function (/* funs */) {
  var funs = Array.prototype.slice.call(arguments);
  var len = funs.length;
     
  return function (/* args */) {  
    var args = funs[0].apply(funs[0], arguments);
    for (var i=1; i < len; i++) {
      args = funs[i](args); 
    }
        
    return args;
  };
};
  1. The sequence function does not specify the arguments explicitly as instead we are going to take multiple functions[4]
  2. The functions supplied are extracted from the arguments variable
  3. A closure is then declared that will be returned to the caller
  4. The argumentsfrom this closure are then used to call the first function supplied
  5. The results of this function call are stored in args variable
  6. The remaining functions passed are then called using a for loop each time the args variable is being mutated to contain the results of each function call
  7. Once the functions have all been executed the value stored in args is returned

The only difference between compose and sequence is that compose runs from right to left so if we can take all the existing code and just make this one bit of behaviour configurable we will save ourselves having to duplicate code:

var stitch = function (reverse) {
  return function (/* funs */) {
    var funs = Array.prototype.slice.call(arguments);
    var len = funs.length;
    
    if (reverse) funs.reverse();
    
    return function (/* args */) {  
      var args = funs[0].apply(funs[0], arguments);
      for (var i=1; i < len; i++) {
        args = funs[i](args); 
      }
    
      return args;
    };
  };  
};

This uses much of the same code as before but this function now takes a reverse boolean that when set to true will perform a reverse on the functions passed in[5], and returns another closure (to take advantage of partial application[6]), we can now implement compose & sequence using this new function:

var compose = stitch(true);
var sequence = stitch(false);

Recursive Approach

In order to understand recursion, you must understand recursion

- Hunter, David (2011)

One section mentioned in Functional Javascript regarding recursion was the rules of thumb (Touretzky 1990) for every recursive function:

  • Know when to stop
  • Decide how to take one step
  • Break the problem into that step and a smaller problem

I will show how each relates to the recursive function of sequence & compose, now first let’s create a sequence function:

var sequence = function (/* funs */) {
  var funs = Array.prototype.slice.call(arguments);
  var recurse = function recurse(funs/*, args */) {
    var args = Array.prototype.slice.call(arguments, 1);  
    if (_.isEmpty(funs))
      return args;
        
      var fun = _.first(funs);
      recurse(_.rest(funs), fun.apply(fun, args));
  };
    
  return recurse.bind(null, funs);
};

First thing to note is that I’m taking advantage of underscore.js[7] this takes away a lot of the menial work.

  1. Like the imperative version we are taking any number of functions so we use the arguments variable to capture the arguments
  2. Next we declare an internal function called recurse, this is the function that will perform the recursion, this function accepts the array of functions as it’s first argument to make it more explicit about what it takes
  3. It first pulls out the arguments supplied, ignoring the first element because this will be the array functions
  4. A check is performed to see if we have removed all the functions from the array, if this is the case we return arguments that were passed in from the last call
  5. Otherwise we use the _.first function which as you might guess returns the first element when passed an array
  6. The we call ourselves, the first parameter we use _.rest which returns an array with the first element removed (we captured this above). The next parameter is calling the current function using the arguments we were supplied.
  7. It then returns a partially applied function[8] bound to the recurse function with the captured functions so it is ready to be executed by the caller

This can then be used in the same way as the imperative version:

var print = function (val) { console.log(val); };
var double = function (val) { return val * 2; };

var display = sequence(print, double);
display(10);

Here is a diagram to help illustrate how the recurse function works using the example above:

And so how does this fit in with the recursion rules of thumb I mentioned previously:

When to stop
_.isEmpty(funs)
Take one step
recurse(_.first(funs)…
Smaller problem
recurse(_rest.(funs)…

One thing to note is that this recursive function is written to enable tail recursion[9] however JS does not have support for this unlike full functional programming languages such as Scheme.

The next step is to enable compose, we can do this by abstracting the order in which the functions are picked:

var stitch = function (take, remove) {
  return function (/* funs */) {
    var funs = Array.prototype.slice.call(arguments);
    var recurse = function recurse(funs/*, args */) {
      var args = Array.prototype.slice.call(arguments, 1);  
      if (_.isEmpty(funs))
        return args;
        
        var fun = take(funs);
        recurse(remove(funs), fun.apply(fun, args));
    };
            
    return recurse.bind(null, funs);
  };
};

Similar to the imperative version we have created a new function called stitch, only this time we accept 2 functions one that will decide how to take a function from the array and another that will decide how to remove a function from the array, now using our good friend partial application we can declare both sequence and compose:

var compose = stitch(_.last, _.initial);
var sequence = stitch(_.first, _.rest);

The compose simply passes _.last (retrieves the last element when passed an array) and _.initial (returns a new array with the last element removed).

Summary

I have demonstrated a couple of ways of how these 2 functions can be implemented there are a whole host of other ways they could be implemented (or you could just use _.compose!) hopefully this will be helpful at this post has certainly helped me get a better understanding of how to apply recursion.


  1. Also known as pipeline in other languages
  2. Functional Composition
  3. The arguments variable
  4. I like to add a comment in the function parentheses to denote the arguments we are expecting just to make it clearer that we are expecting arguments (a handy trick picked up from Functional Javascript)
  5. I know from a micro performance point of view this isn’t as efficient as looping backwards but we are talking a tiny amount of functions that are going to be passed in so I don’t think this is going to be the bottleneck of your application.
  6. You could also change the signature to be function (reverse, /* funs */) and then use bind var compose = stitch.bind(null, true); but I think this nicely separates the configurable part from the actual usage part.
  7. This is JS library that provides functional style functions such as map, reduce etc… just a shame about the argument ordering as it means partial application cannot be applied out of the box.
  8. For more info partial application check out this post
  9. Tail Recursion

The difference between partial application & currying

As I’m working my way through Functional Javascript[1] (currently on chapter 5) I only now feel as though I understand what separates partial application from currying, I believe the main reason is that coming from an OOP background I think it takes quite some time to get used to functions playing such a critical role and the idea of functions taking other functions as parameters and returning functions from functions[2] is a large step away from objects being the focus point they are in OOP.

Once you get passed this first hurdle it then becomes easier to breakdown a Higher-Order Function and to be able to start see the signature[3] and how you can use either partial application or currying to created configured re-usable functions.

To illustrate how we can use currying to create re-usable functions I will need a volunteer function[4]:

var changeCasing = function (items, prop, upper) {
  var results = [];
  var len = items.length;
  for (var i = 0; i < len; i++) {
    var item = items[i];
    var val = item[prop];
    item[prop] = (upper) ? val.toUpperCase() : val.toLowerCase();
    results.push(item);
  }
  return results;
};

If this is not making you scream out use map or at least forEach you may want to come back after learning more about functional programming, aside from the fact this function is not utilizing any functional programming we can still wrap it up to use currying then with some tweaks partial application.

First we need some data to supply to it:

var data = [
    {id: 1, name: 'joe'},
    {id: 2, name: 'bob'},
    {id: 3, name: 'jill'},
];

So if I want to transform the name of the user into upper case as is the case here, it’s simply:

var upperCaseNames = changeCasing(data, 'name', true);

However we have a lot of repeating parameters that are always the same for this data array (the upper bool flag and the property name) we would like to pre-populate these parameters and then just be able to call the function providing the data array.

Currying

We can achieve this by modifying the changeCasing function to this[5]:

var changeCasingCurryable = function (upper) {
  return function (prop) {
    return function (items) {
      var results = [];
      var len = items.length;
      for (var i = 0; i < len; i++) {
        var item = items[i];
        var val = item[prop];
        item[prop] = (upper) ? val.toUpperCase() : val.toLowerCase();
        results.push(item);
      }
      return results;
    }
  }
};

Don’t worry I remember how I felt first time I saw code like this and goes back to my first point, notice however that once we get passed the nested function code the main body has not changed at all and we can call it via:

var upperCaseNames = changeCasingCurryable(true)('name')(data);

There are a few things to note here:

  1. We now have a separate function call for each argument expected
  2. I modified the changeCasing function so that we accept the parameters from right-to-left[6] which is why the upper bool flag is in the first call

Now we can start to reap the benefits of the modified function, let’s got through supplying values for each function call:

var upper = changeCasingCurryable(true);
// now I have a version that will always change the property provided to uppercase
var upperCaseNames = upper('name')(data);

var upperNames = changeCasingCurryable(true)('name');
// now I have a version that will always change the name property to uppercase
var upperCaseNames = upperNames(data);

Each time I’am providing just enough of the values I want to be applied and being handed back a function ready for the next value, once the values are all supplied the body is executed and I get the result back.

If we had to change each function like changeCasing to take advantage of currying this would be a major headache and require a lot of work when working with other libraries luckily we can take advantage of JS’s dynamic nature to build a generic functions that we can apply to a functions we want to curry:

var curry3 = function (fun) {
  return function (third) {
    return function (second) {
      return function (first) {
        return fun(first, second, third);      
      }
    }
  }
};

We can then change the changeCasingCurryable to be:

var changeCasingCurryable = curry3(changeCasing);

This function is explicit about the number of arguments to curry on, you can use the arguments variable to dynamically curry on the remaining arguments however this can cause you issues given the leniency JS has regarding function arguments.[7]

Partial Application

To demonstrate effective use of partial application, I will need to make some adjustments to changeCasing’s signature:

var changeCasing = function (upper, prop, items) {
//...
}

I have swapped the arguments so that the array of items are the last argument, this is the only change we need to make next we need a function we can use to apply partial application:

var partial = function (fun) {
  var partialArgs = Array.prototype.slice.call(arguments, 1);
  return function () {
    var remainingArgs = Array.prototype.slice.call(arguments);
    return fun.apply(fun, partialArgs.concat(remainingArgs));      
  }
};

This function takes the function we want to partially apply and also the parameters we want to fix the returned function then executes the function using the fixed parameters plus the passed into values, this can then be applied to changeCasing:

var changeCasingPartial = partial(changeCasing, true, 'name');
var upperCaseNames = changeCasingPartial(data);

There are a few things worth noting:

  1. Unlike the currying usage we don’t have a function returned for each argument, instead we can fix any number of parameters and the returned function is ready to be executed with the remaining parameters.
  2. Also unlike the currying usage we are dynamically applying the arguments rather than being explicit, this approach works well with JS’s lenient argument approach to function calls as we typically want to provide values for the first few parameters and then be able to provide the remaining at a later point.

Instead of using the custom partial function above you can also make use of the bind function[8] if it is supported in the target runtime, then the changeCasing above would change to:

var changeCasingPartial = changeCasing.bind(null, true, 'name');
var upperCaseNames = changeCasingPartial(data);

Note the context is supplied as the first parameter.

Conclusion

Both currying and partial application are very similar, they both return you back a function that has had one or more values bound to its parameters, however there are some notable differences:

  1. Currying can be performed on each argument in either direction, partial application is only performed left-to-right.
  2. Currying only deals with single argument functions, so we end up with a function for every argument we want to curry on. Partial application can be applied for any number of arguments, so you could provide every expected parameter and then the returned function could be executed with no parameters (although this would be of little use!)

  1. A great book for those wanting to learn about the functional programming paradigm but in a language which you already know
  2. Higher-Order Functions
  3. One way I have found it easier is by using a comment signature notation I have seen being used:
    //+ methodname :: input_type -> return_type
    //+ map :: fun(a -> b) -> [a] -> [b]
    

    I think it is based off other FP languages, to breakdown the map example:

    1. takes a function that expects any type as input and returns any type
    2. next it takes an array of the a type (passed to first function)
    3. finally returns an array of the b type (returned from first function)
  4. I really wanted to try and find a real world example however it always ended up with lots of other techniques detracting away from the main point of the post (I will try and get another post showing real world examples of functional programming in JS)
  5. The reason this is possible in JS is because of closures otherwise the nested function would not be able to capture the argument passed to it’s containing function
  6. Currying can be applied in either direction, I have chosen this direction because partial application always goes left-to-right so it emphasizes one of the key differences
  7. This is a demonstration to illustrate how you can get into trouble when not being explicit with function arguments.
  8. Bind Function