Domain Modeling For Better Contracts

In the post about communicating contracts through enforcing endpoint contracts, we took a look at some basic types which are available in Signet. Today we are going to talk about how to add more information to your types by creating your own data types.

Last week we took a look at how to build types as sets with characteristic functions. This week we will apply that information in order to add extra information to our types.

By this point I’m certain there are plenty of people who are thinking I’ve gone completely off the rails. Javascript, after all, is a dynamically typed language. Don’t burden yourself with all of this type stuff and just write some code!

Although this is true, most people view types as a constraint which only causes pain. Though this might be true if you are coming from a language like Java which contains lots of artificial constraints around type creation, and after all is said and done, the types are still weak and restrictive.

On the other hand, if we consider types as a way to add a layer of correctness checking and a tool for communicating with others, types become less a restriction and more a tool we can use to make our programs better. Good types will make a program transparent and predictable. These are traits we definitely want in our programs.

Just as a refresher, let’s have a look at where we left off with our purchase API from the enforcing endpoints blog post. This way we have a common position to understand where we started and where we’re going.

Now that we have our API defined with regard to basic types, we can start to ask more meaningful questions. Instead of asking things like “what does this function do,” we can ask directed questions to inform our programming better: What kind of numbers are they? What is in the array? What kind of argument must the function take?

The last two questions are easiest to answer since we don’t have to look any farther than higher-kinded types. This is, of course, scary sounding the first time you hear it. I had no clue what a higher-kinded type was the first time I heard the word. Fortunately, many of you may already be familiar with them even if you don’t know the word. Java and C# both support higher-kinded types.

Higher-Kinded Types and You

First and foremost, let’s discuss what a higher-kinded type actually is. (It’s a type.) Once we have a better grasp on that, we will use it in code to make everything a little more clear.

A higher-kinded type is simply a type which takes a type as an argument and returns a type. I know, that sounds weird. How does a number take a string and return a type? I asked the same thing.

It turns out, however, that it’s not nearly as foreign as it might seem. One very common type we rarely think about in Javascript which could easily be handled as a higher-kinded type is an array. An array is, itself, a type, but it contains values which are also typed. This means, if we had a language to express it, we could declare an array which contains only a single type.

As it turns out, there are potentially infinite different types which are, or could be, higher-kinded. In this post we are going to look at just two: array and function. With the type signature language available with signet, we can explicitly declare an array type as needed. This means we can do things like the following.

We can see both of the tested arrays are completely valid Javascript arrays, but the second is not an array of exclusively numbers. There are ways we could create an array which would support numbers and strings, but that’s beyond the scope of this post.

Just like we can declare information about arrays, we can also say something about the expectations around a function. Instead of simply saying a value is “function,” we can actually say a value is a “function which takes a number.” In much the same way we declare our types in arrays, our function type declaration is “function.”

Now that we have an expanded type language to draw upon, let’s update our API and clarify the communication of our domain model.

Subtyping With Characteristics

Now we just have the ‘number’ type scattered everywhere throughout our code. Although this is better than nothing, it would be SO MUCH better if we actually knew something about those numbers. What do they mean? How are they used? What are the constraints?

It turns out we have just the thing to remedy this pain, it’s called characteristic functions. As we know from our earlier discussions on characteristics, we can add richness to our type system through set-describing predicate functions. (Protip: all predicates describe sets)

Before we dive into creating new types willy-nilly, let’s take a moment to account for the different number types we have. By properly identifying the actual domain language we care about, we can create better types which will allow us to clearly describe our application to people who might know nothing about it.

Ultimately, we care about tax, price, amount of tax to pay (tax amount) and purchase total. If we were to simplify this list a bit, we can identify a couple of distinct bits of information.

First let’s consider tax. Tax is a percentage amount. Since, where I live, taxes are always greater than or equal to 0%, but always less than 100%, I am going to say tax is a percent value which will always fall between 0 and 1. For example, in San Diego, sales tax is currently around 8% or 0.08.

Now, we can take a look at price, tax amount and purchase total. Each of these is a value which is related to a value an amount our customer will be paying. This means we can roll these all into some aspect of price. We will say a price value will be greater than or equal to 0. This describes our data pretty accurately for the moment, so let’s go with that.

With our base types sorted out in a way we can jump off from, we can start building characteristics. By clearly defining our characteristics, we give our new types programmatic meaning. Let’s see what our basic characteristic functions will look like for price and percent.

The other piece of this puzzle is, we need to register our types with Signet. Fortunately, this is a simple process. We know that each of these types is actually a number, so we can simply use the subtype function and declare these two functions as new types, inheriting from number. This is also why we didn’t need to test each value to see if it is a number, our subtyping will guarantee we only verify numbers.

We can use our price type to create our other two types by simply aliasing them and using the price definition to ensure our data constraints are clear.

Let’s have a look at our updated API and see how our types are coming along!

Duck Typing our Object

At this point, our API is pretty clear, but there is still one last type which just doesn’t quite convey the information we want to know. Our array of purchases is still described, simply, as an array of objects. This could be much better, if only there were a way to check it.

As it turns out, the Go language has popularized the notion of object similarity through duck typing and that is precisely what we are going to do here. If we know enough information, we can tell whether our object satisfies the Liskov substitution principle, and can be used in place of our intended object.

Signet provides a means to perform duck typing as well, so we don’t have to build our characteristic function from the ground up every time, because that could end up being a LOT of repeated code. Let’s build a duck typing characteristic and finish up our API types.

Now we have a name for our purchase object type, which means we can easily check whether our array of purchases actually adheres to our expectations. Plus this will provide a way for others to understand what we intended when we wrote the code, making it much easier to write new code against the existing API.

Wrapping Things Up

Although this just scratches the surface of using types in your program, hopefully this exercise helps you communicate intent and define a clear domain model. By taking core types we already know and applying a small amount of predicate logic, we surface a new way to talk about our program and the data we use.

Instead of simply using old code as a reference for what it does, add a little annotation, a little bit of logic and get a lot more bang for your buck. In the end, types don’t make everything correct all the time, but they do a lot to make you and others like you a lot more awesome!

Comments Off on Domain Modeling For Better Contracts

Typed Thinking in Javascript

Javascript is a dynamically typed language. I suspect this is not news to anyone reading this. The reason this is important, however, is I have heard people say Javascript is untyped. This statement is most definitely false. Javascript has and supports types, it simply does not actively expose this to the world at large.

Javascript is in good company when it comes to dynamically typed languages. Python and Ruby are also popular languages which are dynamically typed. Other venerable languages which are dynamically typed include Clojure, Elixir, Io and Racket. People coming from statically typed languages often say that Javascript’s dynamic typing is a hindrance to good programming. I disagree. Bad programming is a hindrance to good programming. I feel programmers coming from the languages listed above would probably agree.

What’s the Difference?

Several popular languages today, including C#, Java and C++, are statically typed. This means the programmer declares the values they plan on using to accomplish a task when they define a method. There are distinct benefits to this kind of programming, specifically, the compiler can quickly determine whether a method call is valid. This kind of validation is useful and can prove a good tool for programmers, no doubt.

As you can see above, everything is explicitly annotated with a type definition. This kind of annotation is effectively a note to anyone who reads this code, including the compiler, et al, that this function behaves this way. Unfortunately, this convenience comes with a price. Suppose you wanted an add function for any sort of number including mixed arguments…

Modern improvements on type values has helped improve this problem (don’t shoot me, Java people), but it becomes obvious rather quickly that having restricted type flexibility means there is a lot more work which must be done to accomplish a seemingly simple task. We have to make a trade to get this compile-time help from the language.

Dynamic typing, on the other hand, does not have this restriction. In Javascript (or Python, Clojure, etc.) no type annotation is needed. This means the language will perform what is called type inference to do the right thing. Languages like Python or Clojure are less forgiving if types don’t line up correctly. If, for instance, you attempted to add a number and an array in either of these languages, an error would occur and everything would go downhill from there.

Javascript works a little harder to do the right thing; perhaps a little too hard. In a strange twist of fate I, once, attempted to demonstrate that Javascript would throw an error when trying to add a string and a function. Instead I got a string containing the original string, and the source code for the function. Suffice to say, this is not what I expected.

Nevertheless, this kind of type management is both the weakness and the strength of a dynamically typed language. Rather than having to spend time really thinking about strings, ints, doubles, bools and so on, you can spend more time thinking about the way your program works…

Until it doesn’t.

Correctness and Types in a Dynamic World

One of the most important things to consider in Javascript is intent. Although the kinds of strange things can be accomplished by applying common actions to unexpected values can be entertaining, it is not particularly helpful when attempting to write a correct program.

Correctness in programming is when a program performs the expected action and, within the domain of acceptable values, returns the correct output. In other words, an adder would be incorrect if it always returned 9, regardless of the input; an adder which always returned a valid sum would be considered correct.

By considering correctness, we must consider input and output types. Let’s keep using our add function because it’s easy to understand. Above, when we discussed types annotations, we looked at an add function in Java. We said that the input values a and b were both integers and the output is an integer. This forces the idea of correctness upon our function which, actually, could be defined as correct in a broader sense. What if, instead of declaring all of the different types and overloading the function again and again, we made up a new type. Let’s call this type Addable. Suppose we had an addable type in Java and could rewrite our function accordingly:

We can actually define a notation which will help us to understand the correct input/output values of our function. We can say add has a function signature which looks like this: Addable, Addable => Addable. In other words, our function takes two Addable values and returns a new, Addable, value. All of this is true and we could test this function via various methods to prove the specific addition behavior is correct.

This new Addable type is effectively what we get in Javascript with the type “number.” We know that any number can be added to any number, so whether one number is an integer and another is a floating point value, we know they can still be added together. This means we can actually go so far as to eliminate the type annotations altogether and simply write our function as follows:

Of course, the problem we face here is there is no annotation to tell the next programmer what types a and b should be. Moreover, Javascript is quite forgiving and will allow a programmer to pass anything in which might be usable with a “+” operator. There are solutions to each of these, though we will only look at solutions for telling the next programmer what we intended.

Ad Hoc Properties to the Rescue

Under the hood, Javascript shares some really interesting characteristics with Smalltalk. Specifically, everything in Javascript, when managed within the runtime, is an object. This means we can do all kinds of neat things with functions, like assign properties.

What this means is we can actually do something real about making our programming intentions more clear. What if we took our add function and assigned an ad hoc property to the Function object instance called “signature?” By creating a property which declared what the function should do we get two benefits. First, anyone reading the source can immediately see what we meant to do and, second, we can actually create an artifact in our code which can be called upon elsewhere to get immediate feedback on what our behavior should look like. Here’s an example:

Now, looking at our code we can see what add does. It takes two numbers and returns a number. We can use this same property to our advantage elsewhere in our code. If we were planning to use add and wanted to see what the expected input and output are, we can simply output the signature. Here’s how we could do that:

Now we know! Better yet, if add was somewhere deep in a third-party library, we wouldn’t have to dig through third-party code to understand what the contract for add might be.

Thinking Types

The really important idea here is, even if they aren’t expressed in code, types live within everything we do in Javascript. As we develop software, it becomes really easy to simply not think about what a function signature looks like and call it with whatever we have, hoping it does what we expect.

Programming this way is dangerous and can lead to bugs which are hard to triage and fix. Instead of using the spray and pray approach, it is helpful to understand, more fully, what you intend to do and work with the types which are intended in a functions activity.

What this means to the dynamic programmer is, we have to be more vigilant, more cautious and more prepared while solving a problem than someone working with a statically typed, explicitly annotated language.

There are two ideas we must always keep in mind when programming, the goal of a correct program and what we must do to get there. The first idea is related to the company goal related to whatever problem we are actually trying to solve. The second idea encompasses types and actions almost exclusively.

Summary

Regardless of the typing mechanism for the chosen language with which we solve a problem, types are part of the solution. Javascript does not express the value and function types explicitly in the source code, but the types we use are equally important to anything used in a statically typed language.

We can solve the problem of expressing our function signature through using comments or adding a property which can be read and understood by other programmers. This will help alleviate the challenges which arise from misunderstanding source code.

Finally, as we work we must always be aware of the types we are interacting with and how they lead to the solution for whichever problem we are solving at the time. Instead of throwing things at the wall and seeing what sticks, let’s work carefully and with intent to write correct, valid programs.

P.S. If you don’t want to remember all of the metadata stuff you have to do, check out signet.

Objects Are Still Shared State

Dear programmers coming from Classical Object Oriented programming, please stop thinking that encapsulation of variables eliminates the “globalness” of your variable. It’s a hard truth, but you had to hear it from someone; you have a problem. Consider this an intervention.

I had a conversation a couple months ago where I looked at some code a senior developer had written and asked, “why are you using a global variable?” The response I got was “it’s the exposing module pattern, so it’s local and encapsulated. It’s not global.” The variable was a cache object exposed outside of the module; and it was global anyway.

When I say global, it is not about whether the entire program, or the entire world, can access your value, it’s about how your variable gets managed and modified. Really, the problematic aspect of a global variable comes from the fact that global variables, in many popular languages, represent shared, mutable state.

Consider a world where every variable is actually immutable, i.e. once you create a variable, you can’t change the value. In this particular case, a global variable is really nothing more than a globally readable value. You can’t write to it, so you can’t impact the rest of the running program. Is that global variable actually a problem? Decidedly less so, that’s for sure.

Mutating Object State

Let’s take a look at a very simple, though rather common, example of the way variables are often managed inside objects.

There are two things wrong with this if value is actually important to the internal state of the object. First, since Javascript does not support private variables (explicitly, but we’ll come back to that), then this suffers from the Indecent Exposure code smell. Essentially, anyone in the world can directly access and modify the internal state of this object. That’s bad news.

The second issue with this object is the getter actually modifies the internal value of our object and returns a representation of the previous object state. Effectively, our getter is modifying the internal state of the object and lying to us about it.

Before you proclaim “I never do that! How very dare you,” keep in mind that this pattern shows up all the time. Popular frameworks like Angular and Ember actually encourage this kind of thing through the controller pattern. This is a sneaky trap that is hard to avoid.

Although we can’t quickly resolve the code smell, let’s take a look at a remedy for the lie that is our “get” method name.

Now we understand and declare what the method does. For some people this is enough and we need to go no further. I, on the other hand, feel this is still rather suspect and would prefer to see a cleaner, more elegant construction.

Separate The Activity

The issue I draw with our updated object is, we have one method which does all the things. This is a really bad idea since it really doesn’t protect the programmer from a micro-god function. (Hey, You can have micro-frameworks and micro-services.) Effectively we have fixed the naming problem, but we haven’t actually resolved the smelly code which lives within our method.

Typically I prefer a single function which will return the current state of affairs and other function, if you MUST, which modifies the internal state. This kind of separation of concerns actually helps to keep object state sane and useful. If not for the exposed internal value of the object, we would be on our way to saner code.

We can see this code actually separates the functionality and has the lovely side effect of making the code more readable. If I were working in a project using an MVC paradigm, I would call this good and move on. We have separated the behaviors and tried to keep everything clean, tidy and meaningful. Our view would be able to access the values it needs and we keep our state management safe from accidental update.

Turn Up The Encapsulation

From here we can start looking at working on our fine detail. Up to now, we have accepted that our internal values are exposed and available for the world to manipulate, AKA Indecent Exposure. It’s time to fix that little bit of nastiness and make our object water- and tamper-proof.

The only way to actually protect a variable from external access in Javascript is through closures. Since functions are objects and objects are built atop function constructors, we can perform a little scope management surgery and make our object really safe and secure. Let’s take a look and see what we can do to lock things down.

This code does a little fiddling around with scope by partially applying the object’s internal state to our get and set functions. This protects our variable from being accessed by the outside world, but allows our get and update methods to access our value freely. When your data must be locked away, this will get you there.

Our Code Goes to 11

In order to finish up this journey, it seemed only right to create a completely pure, immutable object just to see where it would lead us. If we were to really go all the way, we would need to do a little more work to ensure everything still worked as we would expect.

We know the variable “value” maintains a count for some reason, so it will be important to ensure value is always an integer. We also want to make sure the get method always gives the current count. Finally, update should do just that: update the count value. What does it mean to make an update if everything is immutable? Let’s have a look and find out.

This is just chock full pure functions and added behavior. With all of that added behavior, we get something magical. Instead of having an object which is mutable and, ultimately, somewhat unpredictable and hard to test, we end up with an object which has the following properties:

  • Immutable
  • Contains pure methods
  • Has a single, pure, static method
  • Is compositionally built
  • Updates through new object construction

This whole object construction could lead us down many discussions which would get into types, values, mutability, function composition and more. For now, it will suffice to say, this kind of development creates the ideal situation for developing safely and really turns our code up to 11.

The numbers all go to 11.

Summing Up

Although we got a little spacey at the end, the important thing to take away from this whole thing is, any time an object is built and modifies its own state through method calls, the methods are actually relying on shared, mutable state.

Shared mutable state in an object really is just a micro-global and should be viewed as such. This means, any value which can be accessed and modified should be considered unsafe and untrustworthy. Untrustworthy data should never be viewed as the source of truth.

From here forward, if you start to add a variable to an object or module, ask yourself, does this really need to be global, or can I localize it? Perhaps you will find a better way to keep your code clean and easy to reason about.

Comments Off on Objects Are Still Shared State

What is Functional Programming?

For the past couple of years I have been trying to put my finger on a crystalline idea which I could use to explain what functional programming is for someone who doesn’t understand. Along the way I have given lots of explanations, some were merely confusing and others were actually bad. My goal, with this post, is to give a clear, concise picture of what functional programming is really about.

It is common for a programmer, today, to have a good grasp on Classical Object Oriented programming. What this means, at the heart of it, is they understand managing objects through a class and inheritance system. I know I was taught a classical approach when I was in college and many programmers, even those who didn’t attend a formal, degree-granting institution experienced a similar path of education.

Functional programming has, in fact, been around quite a bit longer than object orientation of any kind, but it was largely either implemented in a language that was geared for research, or it was implemented in a college project (typically Lisp) to explore creating a programming language. Due to the academic nature of early functional languages, and the fact that programming, in the large, was something which was still in a discovery process, nobody tried to provide a small idea to state “this is what we are doing.”

With all of this in mind, it is useful to have a setup which will be accurate and, at the same time, descriptive to Classical OO people. I thought about how Scheme was introduced in “The Little Schemer,” and though there was no crystalline idea, the approach really helped to clarify what functional programming really is. With all of this in mind, let’s take a look at the small idea.

Functional programming is made up of three parts:

  • Inquiry
  • Declaration
  • Abstraction

What I mean by this is, though functional programming contains ideas like closures, first class functions, higher-order functions and so on, that is not ACTUALLY what functional programming is. I feel that the person who wrote “The Little Schemer” (nee “The Little Lisper”) understood this clearly. Unfortunately, I have never seen this written anywhere.

The remainder of this post will be an inspection of this three-part idea and how we can look at Javascript and either see or build the pieces we need to make this idea clear.

Inquiry

The first concept in our list is the concept of inquiry. Another way we can say this is, we can ask questions. Conditional blocks are already designed around the idea we want to know if something is true or false, but we construct our conditions with (sometimes) cryptic operators which force people to think while they read the code instead of simply reading the code like English.

We can start by asking very core questions, which are handled by operators in Javascript. Checking the type of a variable in Javascript cloaked in operator soup which creates a long line which someone has to read later. It would be preferable if our expressions were closer to natural language. Here’s a way we can wrap our operator soup and be more expressive about the questions we are asking.

Although these functions are, potentially, a few more characters, they are much more transparent in their intent. By wrapping our operators, the code we write will actually state precisely what it does in English, making the time to understand a program shorter. Here’s taking this a step further:

By wrapping up the original operators in functions, we can actually build on top of them, creating new functions which also read clearly and add quite a bit more utility. One of my all-time favorites in this list is isArray, where we simply ask if our current value is an instance of the base Array object. This really beats the commonly suggested:

typeof value === ‘object’ && Object.prototype.toString.call(value) === ‘[object Array]’

Declaration

It could be said that asking questions is a special case of declaring intent, but I prefer to keep these separate because it helps shine a light on two different aspects of the programming process. Sometimes we want to ask questions, but, often, we really just want to get something done.

The act of getting something done is what I like to refer to as intent. When we create a function, called sum, which sums the numbers in an array, we are actually declaring, in code, that we want to add up a bunch of numbers. In much the same way, we might want all the even numbers from an array. This would lead us to creating a function called getEvens.

This kind of programming is typically referred to as declarative programming. Instead of writing out large blocks of conditions and sprawling loops, we can declare our intent and allow the underlying system to actually interpret our intent and perform the correct action. Let’s have a look at creating a few declarative functions.

Right now seems like a good time to point out, although we took a few extra characters to bundle up our operators in functions, the bodies of all our functions, including sum and filter, which would typically be loops wrapped in a conditional, are actually only a single, very short line. This brevity is NOT because the goal is to be terse, but rather because that is all it takes to express our intended behavior. All of the remaining braces, parentheses and operators are just cryptic language cruft we can abstract away.

Abstraction

Picking up right where we left off, abstraction is the final piece of the functional puzzle. So far we have seen functions floating free, detached from objects and made available just as they are. Abstraction is where we take those functions and really make them shine.

In functional languages, and languages which support functional programming, functions are first class. What this means is, a function is a free-standing entity which is handled as data. In Javascript, this is facilitated by the prototypal inheritance system which actually news up a function object and provides it free from the boilerplate and constraints which are put in place by Classical OO languages.

This first-class, data-centric behavior is what really makes abstractions strong in Javascript. In the declaration section above, we created a function called getEvens, I’ll paste the code below, so it’s handy.

I made sure to bring the isEven function along for the ride because it’s an important part of this puzzle. Inside the getEvens function, we call a method on the values array called “filter.” Filter is an example of what is referred to as a higher-order-function.

Higher-order functions are functions which take a function as an argument with the intent that the function is to be executed (as opposed to treated like a string or number). This means we can write highly abstract, very generic functions like reduce which provide a tremendous amount of power for our programming pleasure.

If we were to write filter ourselves it could look like the following:

That code might be a bit much to choke down, but the idea is we don’t actually have to see it. Fortunately Javascript already has filter already built in. With that in mind there is a real benefit that comes with abstractions like this.

If a generic function has a well defined contract, we can actually change the implementation under the hood. This idea can be seen in Classical OO programming as well, but rarely with the level of genericising we have here. We could write a new filter function which takes advantage of a multi-core processor. We could also use a distributed computing system to compute the result. Ultimately, as long as the function contract remains the same, the calling code will never know the difference!

The abstraction portion of functional programming is a rather expansive topic including higher-order functions, closures, metaprogramming, types and more, but even without digging into all of the various topics, we can see the abstraction model is something that definitely sets functional programming apart from Classical OO.

Summary

This has been a whirlwind survey of some of the bits and pieces of functional programming itself, but hopefully the core ideas of inquiry, declaration and abstraction have clarified what seems to be a rather murky discussion of what functional programming really is.

If there is anything I would like you to take away from this discussion today, it is the idea that the three ideas presented here, for as sparse as they are, actually provide the ability to do tremendously powerful programming, while providing the ability to make code clear and descriptive of intent.

This is merely the tip of the iceberg, but I hope this tickled something in your brain that made you want to go out and learn more. Until next time, happy coding!

Comments Off on What is Functional Programming?

Pattern Matching in Javascript

For more than a year I have been considering the idea of pattern matching in Javascript. I know I am not the only one trying to solve this problem because there are a handful of resources where people have put together propositions for solutions, including a Sweet.js macro called Sparkler, and Bram Stein’s blog post and associated Github repo.

Although I really, really like the idea of a macro to handle pattern matching, I fear people will throw it out immediately since pattern matching by itself is already an, sadly, obscure topic. This means anything that requires a macro package will probably turn the general populace off, especially since I haven’t met anyone in my area who has heard of Sweet.js except me.

Although I like Bram’s approach to handling macros with a function library, it looks like he didn’t get a chance to make much headway. That’s really unfortunate since I think he was headed in a good, although kind of simple direction.

Before we go any further, it is important to discuss the idea of pattern matching for the uninitiated. Pattern matching is a functional means to quickly look at the shape and signature of data and make a programmatic decision based on what is there. In other words, pattern matching is like conditionals which have spent the last 10 years at the gym.

Imagine, if you will, conditional statements which looked like this:

Even this isn’t really powerful enough to truly capture what pattern matching does, but I think it gives a little insight. Nonetheless, if we had a construct which would give us the ability to match on an entire set of conditions within our data structures, the face of Javascript programming would be a very different place.

Pattern matching is not just about reducing keystrokes, but it actually redefines what it means to actually describe and interact with your data altogether. It would do for data structures what regular expressions have done for string manipulation.

Pattern matching is the dream.

So, after doing a lot of thinking, I think I have settled on a means to give this dream the breath of life. Unfortunately, I believe it is unlikely that the path to data Nirvana will be easy. I have a suspicion, this is the same issue Bram encountered. Looking at the ~1400 lines of code that make up the Sparkler macro, pattern matching could be a tricky problem.

Function and Contract

I looked at the Sweet.js macro, Bram Stein’s early exploration and the match behavior in both Scala and Racket. I decided I needed something which felt like fluent Javascript instead of succumbing to the Racket nut which lives inside me, so I opted to avoid the hardcore Lisp syntax. Scala had a closer feel to what I wanted so I kept that in mind. Bram’s example felt close, but a little too muddy and the Sweet.js macro just felt a little too much like operators instead of functions. What I landed on was this, () => () => any; that is to say a function ($match) which returns a function (pattern assembly) which returns the final result of the pattern matching. Here’s an example of a simple exploration, drawing against Bram’s factorial implementation.

It’s easy to see the first call is just $match(n). This returns another function which takes a function as an argument; i.e. $match is a higher-order function which returns a higher order function, which takes a function as an argument, which then does stuff and returns a result. Another way of looking at this is $match is a function which chains to a function which is designed to perform pattern assembly. Once the pattern is assembled, everything is executed and we get a result.

Clear as mud?

Expanding the Concept

This small example seems pretty simple. Check for equality and if nothing works, then use the else clause. This is a little condition-block feeling, but I think people will understand the else clause better than anything else I might have put in there.

Anyway, digging in a little further, I wanted to also be able to quickly and easily match arrays, objects or other things as well. This simple equality checking was not enough, so I started expanding, moving into some sort of factory behavior to create matchers on the fly. This brought me to an example which was a little more interesting and a lot more complex.

Here I am returning a string based on the pattern of a pair (2-valued array) array being treated like a vector. If the first three patterns match, we get a string describing the axes the vector lives on. If the vector is not a pair, or it contains something other than numbers, I want to return a type error with a message explaining the provided vector was invalid.

This bit of logic is significantly more complex than our previous factorial example and leaves us in a place where the code is descriptive, but perhaps not as readable as we would like. Moreover, I thought about what I really want to be able to say and it made more sense to, perhaps, create something of a pattern matching DSL. (domain specific language)

Matching on a DSL

If I was going to invent any kind of simple language for expressing matching behaviors, I wanted it to be less cryptic than regular expressions, but I also wanted it to be terse enough that it didn’t become some giant, sprawling string someone would have to mentally parse to really understand what was happening. What I landed on was a simple near-Javascript expression of what the values should look like when they properly match our criteria. This turns our earlier expression into the following.

I reduced the type descriptor for brevity, opting for an angle-bracketed character. Now we can wrap up our expression in a single pattern call and get something the matcher can quickly and easily execute to verify whether the vector matches our requirements or not. This, however, also means I am responsible for generating an AST (abstract syntax tree) for these expressions. Of course, if I am going to do that, it would be best to create one by hand so I can see what I am actually contending with.

Matcher Abstract Syntax Tree

The AST for my matcher language would, ultimately, link in with an underlying state machine of some sort, but I won’t dig that deep right now. Nonetheless, what I ended up with, when constructing an AST is long, but relatively declarative. This means, I could, theoretically, start the entire process NOT at the language level, but instead at a place which people would more readily understand. Let’s have a look at the AST replacement for our matching behavior.

It’s long, and probably overkill for the problem presented here, but it gives us a real view into the guts of the problem and a way out of the mud. This is, also, unfortunately all I could pull together in time for this post, but I feel like we covered a tremendous amount of ground. I will continue to experiment with pattern matching and, perhaps, by next time we could even have a working object model to build our tree with. Until the next post, keep coding!

Comments Off on Pattern Matching in Javascript

Working with Strings and Regular Expressions

An exchange at work got me thinking this last week. Someone said “I really hate regex.” For those of you not in the loop on the lingo, regex means regular expressions. After a little prying, it turned out the reason they didn’t like regular expressions was really rooted in the fact that they didn’t have a chance to use them very often, so the concept is unfamiliar.

In this post I am not going to go into some of the more advanced parts of regular expressions because, a: they complicate things significantly and b: because I’m not experienced enough with them to give good guidance. Foundational regular expressions are still more than enough to discuss for a single blog post, nonetheless. For now, I am going to cover how to leverage a lot of power from a very small subset of the entire set of tools.

Along with this post I am also going to give screen casting another go and provide a bunch of examples in a video which, hopefully, will be a good supplement to the information I will present in my blog. In the video I am using approval testing to demonstrate the output from various regular expressions, which should make applying regex easier to do.

States and Strings

For the brave and the true, let’s start at the beginning. Regular expressions are a form of finite state machine with an accept state. What this means in English is, regular expressions go through a set of predefined states and, if enough of the characteristics are found in a string in the right order, then the pattern is considered a match.

A way to see this in action is the following:

We can see the pattern of characters in the first test string matches the pattern exactly. We expect this to pass. The second string also contains abb roughly in the middle. This means our pattern will also result in a match. The third string comes very close three times, but abb is not actually found anywhere in the entire string. Let’s take a look at the way the search is conducted in the second string since it is the more interesting of the passing two:

What this demonstration is showing is, the pattern matching mechanism starts verifying on a character and will continue to test until either a character does not pass one of the rules or a set of characters matches all of the rules and reaches what is referred to as an accept state. Regardless of how complex a regular expression ever gets, the underlying function always comes back to reaching an accept state or not. This means if something goes horribly awry and you can’t figure out what happened, simplify your expression and build piece by piece, extending the states in your pattern one by one until you get to the pattern you need.

Special Case Behaviors

Regular expressions come with a whole array of special case definitions and characters which match those cases. For now we are going to look at some of the simpler parts which you can use to make your pattern matching more expressive as you go.

The Optional Pattern

The first special case is the optional modifier, ‘?’. By adding a question mark after a character or expression, you can set a rule that the last part of the pattern was optional in nature and may or may not actually exist. A very common example for this is the American versus British spelling of color/colour. Here’s how it works:

Obviously, the last string doesn’t match a valid spelling of color for any English standard defined, so no matches are returned, i.e. the result of the match expression is null. We can also see that both color and colour are considered valid matches, which means match will return correctly matched strings in the matches array.

Testing for Any Character

Sometimes you are less certain about the particular character which you want to match. For instance, let’s suppose we want to find any word which starts with ca, but we don’t care what the last letter is. We can use the ‘.’ pattern to match any word of this form, even if they aren’t valid words. Here’s an example:

The last string actually demonstrates the problem we run up against with regular expressions of this type. Regular expressions are not particularly discriminatory. The only rules we provided were that there must be the characters c and a, followed by another character. “Occam’s” satisfies this just fine even though cam is in the middle of a string of characters.

Initial and Terminating Patterns

Next let’s have a look at two more modifying patterns. We can actually express position of a string by using ‘^’ and ‘$’. The ‘^’ pattern expresses that anything which follows that character must be positioned at the very beginning of the string. ‘$’ is the polar opposite, saying that the string must match and terminate at that point. These are probably easiest seen in action.

As you can see, pattern 1 only matched patterns which started with ca and pattern 2 only matched strings ending with ca followed by another character. This can be really handy for testing that a string either starts or ends with an expected value. The initializing and terminating patterns are also very useful in testing that a given string contains only characters which match an acceptable pattern. This is common for testing things like postal codes, phone numbers and email addresses.

Multiple Patterns

Where ‘?’ will make a pattern optional, there are broader reaching patterns like ‘*’ and ‘+’. The ‘*’ pattern means 0 or more matches of the previous character or pattern are acceptable. Similarly, the ‘+’ pattern means 1 or more matches of the previous character or pattern are acceptable.

With two pattern characters which are so close in meaning, it seems reasonable to ask why both? As it turns out, the case of 1 or more is common enough it is actually quite valuable to address that situation directly.

Any In Matching

The last pattern we are going to cover, quickly, is the match any in case specified as ‘[]’. Anything contained within the brackets will be used as an acceptable match. This means, if you have a very specific set of acceptable characters, it is easy to simply list them all and match against the definition. This is a common use case if numbers and letters are acceptable, but punctuation is not.

Since cabby and cantina both start with ca and contain only letters, they were proper matches for our pattern. Since candl’d (which is basically a nonsense spelling) has punctuation, it is not an acceptable match, so we get null as our match result.

Regex Flags

In Javascript (as well as Perl and potentially other languages) there are flags which accompany a regex search. Up to this point we have been, largely, looking at lower-case matches. In regular expressions, case matters. This means it is useful to be able to declare when case should or should not matter. For example Chris and chris are different strings, so a search for /chris/ won’t match Chris. That’s not helpful when case is unimportant. We can flag a pattern as case insensitive with ‘i’.

The search string remains the same, but by adding the ‘i’ flag, we increase the allowable characters in our search and broaden the results which are returned.

In much the same way ‘i’ allows us to broaden our search by ignoring case, the ‘g’ flag will tell the regular expression engine to find all matches instead of just the first. Let’s have a look at that as well.

As you can see, as we add flags to our search, the results expand to capture more cases and instances. This is especially helpful when trying to replace values or split strings on complex patterns.

Summary

Regular expressions are a fairly rich way to describe string patterns for performing all kinds of matching and checks. Along with matching and checks, regular expressions make it easy to perform complex find and replace operations and string tokenizing.

With particularly complex expressions, regex can look rather cryptic, but when small, focused checks and behaviors are being performed regular expressions can be a great benefit to the programmer for working with strings and reducing pain.

Comments Off on Working with Strings and Regular Expressions

Learning Javascript Differently

On Thursday and Friday I was at a convention called Agile Open San Diego. The core idea is people getting together and having two full days of water cooler discussions about agile development and leadership. It’s pretty cool and you should go to one near you. Anyway, something happened on Friday morning: I realized we need a new way of approaching language learning.

Currently there are a number of ways people can learn languages including classes, videos, code schools, code katas and more. The most important thing I have noticed is this: none of these really do a good job of building the language into your brain quickly or permanently.

I have watched people who are new at programming struggle through code katas after working through videos and online learning processes. I think it’s time for something different. Borrowing against the ideas of code cooking and the way martial arts are learned, I created the first form in a series of forms for Javascript learning.

What a Form Is

In in certain martial arts, a form (much like a kata) is a scripted set of motions which help to define a dictionary of movements the practitioner will use when sparring or in a fight situation. The form is important for developing muscle memory and deepening the mental relationship with the art.

When developing a relationship with a new language any experienced programmer picks a project to do which will force them to go through the motions of asking all the questions they need to ask to really understand how the new language ticks. This is the driving idea behind doing code katas. Katas force a programmer to look at the language they are working with and ask the same kinds of questions.

What if the new language is also the FIRST language?

A new programmer won’t necessarily even know the first questions to ask to get to the right questions. This is why katas help sharpen developers but don’t bring new developers up quickly. This is what a form will help to fix. Instead of placing a problem in front of a new developer, it places the code and asks them “what does this do?”

Here’s a quick start video I made to give a better idea:

Creating the First Form

In the language forms design I envisioned a total of (probably) six forms. Of course before there are six, there must be one. I wanted to emulate a system I already understood, which meant that the first form should be the gateway to greater understanding. I wanted to introduce some of the most common aspects of the language and use a problem which had a lot of room to grow.

Ideally, if the language student were to work through only first form, they would have enough knowledge of the language to start solving problems. The solutions may not be elegant and they would likely not seem refined to the veteran programmer, but solutions and doing are the path to greater understanding.

With all of this in mind, I chose a problem which covered interaction with vectors. Though this sounds pretty “mathy,” anyone who has completed an intermediate course in Algebra should be able to understand what is happening. Vectors represent just the right amount of leg room that the problem would be understandable by the accomplished first form student and had plenty to grow on for the third form student.

After choosing a problem that met my needs, I started creating the code. I want first form to represent the way someone would actually work through the problem in an agile environment. This means every step the student takes, there is a test to validate their progress. It becomes far less important for them to sit and scrutinize their code to make sure they got every character right on the first pass since the process is: read the test, write the code, run the code. If the code runs and it looks like what the golden example presents, it must be right. This gives students early comfort through TDD and small-step development.

Leveling

Something I personally have a terrible time with when I am trying to teach someone something is setting aside what I know. I want to give the student everything and have them see why I take such joy in what I do. It doesn’t ever work that way. Instead, I end up overloading them and they have trouble absorbing what I am trying to share.

Lynn Langit encourages the idea of leveling in her Teaching Kids Programming process. Leveling is the idea of presenting a simple idea that does one thing. Once the core idea is understood, then enhancing the idea with a greater concept, while reinforcing the original idea. All programming builds on more foundational concepts. This means that any topic can be taught through a leveling approach.

Language forms should work this way. The first form actually opens with a greeting. This mirrors the kung fu tradition of performing a greeting or salute to Buddha. The greeting is, essentially the foundational Hello World program, TDD style. We could call this a salute to the programming force, or something. I haven’t come up with a name yet, but it’s coming.

After the greeting, the very next thing first form does is it presents the concept of squaring a number. We don’t need to understand the entire process yet and the full problem is largely academic so the student can focus more on growing to solve the entire problem instead of trying to understand what it does. As we said before, katas are great for sharpening problem solving, this is all about developing a relationship with the language itself.

As we move through the process of solving the entire problem, the student will go through the process of small-step design, abstraction, TDD, conditionals, loops, variables, functions and so on. First form is a guided tour though the way a professional programmer works without the fear and intimidation that comes with getting thrown in with the sharks.

Later Forms

After the first form student has successfully grown to proficiency, they will need to move to the next form. Currently, only the first form is complete, but the second and third forms will actually make subsequent passes over the same code that was covered before. This process of enhancing existing code provides direct insight into identifying patterns, refactoring and smoothing out the edges on legacy systems.

Later forms will pull in concepts like closures, object orientation, higher order functions and so on. The process of creating custom types will be brought to the fore and, by the third form, the student will start learning ways to escape common pitfalls and smells by using well known patterns. They will be able to use what they have learned to improvise on solutions and find their way out of sticky situations.

Forms beyond the third are still in the embryonic stage in my mind, so they will come as I discover how to develop them. So far, I know they will likely not cover the same ground, but will, instead, dig into deeper topics like Gang of Four patterns, algorithms and data structures and greater language mastery. Understandably, not all students will want to go this far with a single language, but ideally, this would provide a means for the dedicated language student to open up greater discovery channels they can follow on their own.

In the end, all of the forms should create a comprehensive system for teaching language through immersion, muscle memory, leveling and, in the end, understanding. The forms are made, not to be done once, but to be repeated again and again to develop a comfort with the language without trying to force the student through solving puzzles and toy problems which they may not have the answers for yet.

Check out my progress creating Javascript forms on GitHub.

Comments Off on Learning Javascript Differently

Types and Functions in Javascript

A while ago we talked about creating a custom type in Javascript using object inheritance. There were a couple of fundamental issues with this post: first it was fairly academic and was unlikely to be applicable to the real world; second we didn’t actually do anything with our resulting type.

I decided it was time to revisit the topic, spending less time on the hows of creating a new type more time on the whys. I created a gist with a full definition of a Vector object so we could start looking at how we can interact with a type and why it’s valuable to isolate object-oriented patterns to type system related activities rather than bundling everything in a class because “it’s the way things are done.”

A First Look

Something you might note right away is we have done some fancy finger work with our definition and created a combination of inheritable behaviors and static functions. This gives us the ability to fall back to the factory pattern for our object instead of instantiating it directly in the middle of our code. This kind of action is similar to how someone writing Scala might handle an object.

In fact this very kind of behavior is precisely the reason I really, REALLY want to love Scala. I don’t but I want to.

Vector also has both valueOf and toString methods which override the base object definition behaviors. This is really important since we don’t want some giant object output blob if we stringify our vector. Really, we want something akin to the mathematical representation, so if we can get this kind of behavior: Vector.build(1, 2, 3).toString(); // <1,2,3>

In much the same way we want a sane output when we call toString, valueOf should also give us something useful. Instead of returning the whole vector object, which is not easy to interact with in code, it would be preferable if valueOf actually gave us a meaningful data structure like an array. ValueOf will be especially important as we get into interacting with our vector.

Finally, we want our vector to be something we can interact with directly if necessary. Hiding the data away into a list somewhere is far less useful than putting it somewhere predictable. By using numeric indices on our object, if we reference Vector.build(4, 5, 6)[1]; we get 5, which is what we were hoping for. Our Vector object is looking less and less like a classical object and more like a real type with strong intention driving the API.

Writing Functions for Vectors

Vectors are a mathematical construct which means we have real actions we might want to do with them. In a classical approach to development, we would start adding methods to our Vector and extending the API through dumping a bunch of functionality on our final output data type.

The real world doesn’t work like that. A vector is simply a set of ordered values describing a mathematical idea. Vectors don’t actually do anything and they definitely don’t add or magnitude. At most it makes sense to ask a vector its length and a point at an index. Anything else is really an action we do TO a vector.

A common action to take with a vector is to figure out its size, better known as its magnitude. This is a pretty simple process and is directly related to the Pythagorean theorem we learned in grade school: a2 + b2 = c2 or (a2 + b2)1/2 = c.

Let’s take an implementation of a generic magnitude function for a vector.

I’d like to point out the annotation above the magnitude function. What this says is magnitude is a function which takes a vector and returns a number. The reason this annotation is so important is it describes an action we can take on a Vector type which will return a usable value. Our function is not interested in the object-orientedness of Vector, it assumes Vector is a type just like any other and acts upon it accordingly.

The other particularly important item is where we refer to vector.valueOf(). Vectors don’t get nice functions like reduce, since they aren’t inherited from the Object prototype. Instead, valueOf gives us a Javascript core data type we can interact with. This means we can limit the amount of custom code we must write in order to actually accomplish work with our vector.

Expanding Our Vector Functions

A better example, even, than magnitude when working with vectors is the concept of adding vectors together. In a purely object-oriented world, adding vectors involves either creating an object which has no real relation to vectors aside from the purpose of housing functions which act on vectors, or adding an add method to our vector creating a syntax that looks like this: vector1.add(vector2).

At best this kind of syntax is kind of odd looking since it doesn’t read quite right, where we would probably say something like “add vector1 and vector2,” this says “vector1 add, vector2” which is kind of awkward to write let alone say. What’s worse is there is an implied order of operations here. Vector addition, much like regular addition, is commutative. This means whether we do vector1 + vector2 or vector2 + vector1, we get the same result. It’s a good thing too. Could you imagine if changing the order you added two things together actually changed the outcome? Bad news.

Let’s take a look at a functional implementation to add two vectors. In this case we will, again, make use of the valueOf method and we will also take advantage of the fact that our vectors are indexed appropriately, so we can capture values without needing to perform valueOf just to get an array. Let’s have a look at the code.

Our annotation this time states addVectors is a function which takes two vectors and returns a vector. Add vectors is actually a far more complex operation than taking the magnitude since we have to interact with two different vectors simultaneously, adding the values. Once we have the new values for our resulting vector, we must create a vector to return.

With the kind of variadic behavior our Vector constructor follows, performing this operation in a purely object oriented manner would be rather challenging, though not impossible. By building our Vector object with a factory, we get the added benefit of using the built-in apply function which all functions inherit. This makes creation of a new vector a trivial affair. In the end, we actually manage to accomplish the core computation in the same number of lines as our simpler magnitude computation.

Summary

Javascript’s blended object oriented/functional paradigm provides a lot of power when we redraw computation and type lines. Instead of bundling all functionality into objects and trying to force-fit a single solution, we get the greatest power object-orientation gives us, flexible type definitions, with the power functional programming provides, declarative, powerful computation syntax.

As you develop applications with Javascript take a look at what you are trying to accomplish and consider whether your current work is data- or computation-centric. Let this differentiating characteristic guide your hand and develop your apps to be powerful, clean and well defined.

Comments Off on Types and Functions in Javascript

Math for Programmers: Difference of Sets

Last post we discussed union and intersection of sets. These two functions are common and well used, so they are quite important to understand at a deep level, especially if you work with databases on the regular. It can also be helpful to understand these behaviors if you have lots of sets of simple data which need to be combined in a straightforward way.

Difference Explanation

One last, critical, function which is typically used on two or more sets is the difference operation. The difference of sets can be characterized as A – B where the outcome is the set A with all elements shared with set B removed. We can visualize the difference of sets with the following diagram.

Venn diagram of a difference of sets

Unlike union and intersection which are commutative, the difference of two sets is not. This means that A ⋂ B and B ⋂ A are the same operation; the same can be said for A ⋃ B and B ⋃ A. The difference A – B is not the same as B – A. We can create a concrete example as follows.

Clearly these two differences are distinct and different. It is quite helpful to understand the order result of set difference when trying to apply functionality to it. we can create a function, called difference, and apply it to two sets. The action would behave like the following diagram:

Visualization of a difference function

In order to apply our difference function, we need to use a couple of helper functions we introduced in the last post: unique and buildSetMap. These will be important for isolating unique elements and eliminating or keeping them according to our difference functionality.

Predicates as Sets

We can describe a set by way of a predicate function. Effectively, anything which matches the condition of the predicate can be viewed as part of the set while anything which does not match the predicate is not included. A good example of this kind of set partitioning would be the set of even numbers. We could pick values with a function called isEven, which would give us a set like this: {2, 4, 6, 8, …}.

We can describe a more general purpose predicate which simply tests if a value is contained in a set built by our buildSetMap function. The behavior would be simple: test that any value which is provided exists in our set and does not resolve to undefined. Let’s have a look.

We can, now, easily test if a value is contained in a set. This simplifies our problem significantly. Now all we really care about to take a difference is whether a given value is not contained in our set; i.e. then it is part of the difference.

Javascript has a function, filter, which is very closely related to both the intersection and difference of sets. If we choose a predicate which includes all values contained in a set, filter will return the intersection of the set of all values which match our predicate value and the set of values we are testing. If, on the other hand, we use a predicate which only keeps values which are NOT in the set, we get the difference instead.

We can use the factory pattern to keep our code clean and readable, while building a useful difference predicate function. Let’s have a look at the code that makes this work.

Implementing Difference Function

Now we are ready to take the difference of two sets. We have a difference predicate factory, a unique function and a buildSetMap function. Bringing filter into the mix means the code almost writes itself. Let’s build our difference algorithm.

This difference function will produce the difference of any two lists of primitive values. This means our original example of A – B can be done with a small, easy to read line of code; difference(A, B);.

Symmetric Difference Explanation

There is another difference operation which has a special name in computer science, the symmetric difference. Mathematically a symmetric difference can be written one of two ways, (A – B) ⋃ (B – A) or (A ⋃ B) – (A ⋂ B). Both of these operations resolve the same way, which can be visualized by the following diagram.

Venn diagram of a symmetric difference of sets

To make this more clear, let’s have a look at a concrete example of a symmetric difference using our original sets A and B.

What all of this really means is the symmetric difference takes everything from sets A and B and excludes the elements they share. A common example is a graph of students taking Math and English but none of the students which are taking both. We can create a function symmetricDifference which performs this operation and lives between the definition of sets A and B and the resulting set.

Visualization of a symmetric difference function

Symmetric Difference Implementation

To create our implementation, I opted for the difference of the union and intersection of A and B. This means we will first compute the union and intersections of our two sets and then take the difference of the two resulting sets.

Once again we see the code practically writes itself. Since we already have functions to perform each of these operations on their own, all we have to do is simply chain them together in a meaningful way and our output simply emerges with nearly no effort at all.

Summary

This closes up the introduction of basic sets and operations including algorithms for acting on lists as sets of data. We discussed how lists and maps relate to sets, what a union and intersection are as well as how to write linear implementation of union and intersection algorithms. We addressed how sets can be defined conceptually with predicate functions and how they interact with concrete sets of data in our programs. Finally, we looked at the difference and symmetric difference operations as well as functions which perform our difference functions in linear time. With all of this closed up, we are ready to start performing more complex manipulations of data using higher order functions which we will discuss in upcoming posts. Until then, keep your code clean and use sets to make your programs better!

Comments Off on Math for Programmers: Difference of Sets

Math for Programmers: Union and Intersection

Last week we talked about sets and how they relate to arrays. This week we will take a look at how to interact with arrays and apply two common mathematical operations on them to produce new, refined sets of data with which we can interact.

Two of the most common and well known actions we can take on sets are union and intersection. The union operation combines two sets and creates a new single set containing the elements of each of the original sets. Intersection is also a combinatorial operation, but instead of combining all elements, it simply returns a set containing the shared elements of each set.

Uniqueness

Before we can address union and intersection, we have to deal with the state of uniqueness. Last week we looked at how an array can be converted into a set by viewing each index and value as a vector. Though this is useful for seeing the relation between mathematical sets and arrays in programming, it is not quite so useful when trying to actually accomplish set operations.

The biggest issue we encounter when looking at an array is that it is more closely related to a vector in nature and behavior. If we discard the importance of array ordering, it becomes a little more set like. Let’s take a look at what this means.

Our second array closely matches our needs for a set, so it would be ideal to have a function which takes an array of values and returns a list with all duplicated values removed. We can annotate this function like this: (array) -> array

Although this function has been implemented in several libraries, it is easy enough to create we’ll just build it here. This not only gives us insight into how a “unique” function could be built, but it also gives us a vanilla implementation of our functionality so as we build on top of our behaviors, we know where we started and how we arrived at our current place.

Now we have a clear way to take any array and create an array of unique values in linear, or O(n), time. This will become important as we move forward since we want to ensure we don’t introduce too much overhead. As we introduce new functions on top of unique, it would be easy to loop over our loop and create slow functions which can be disastrous when we rely on these functions later for abstracted behavior.

Union

To really talk about the union operation it can be quite helpful to take a look at what a union of sets might look like. In words, union is an operation which takes two sets and creates a new set which contains all members, uniquely. This means, the union of {1, 2, 3} and {2, 3, 4} would be {1, 2, 3, 4}. Let’s look at a Venn diagram to see what this means graphically.

Venn diagram of a union of sets

For small sets of values, it is pretty easy to perform a union of all values, but as the sets grow, it becomes much more difficult. Beyond this, since Javascript does not contain a unique function, i.e. the function we built above, nor does it contain a union function, we would have to build this behavior ourselves. This means we have to think like a mathematical operator to create our function. What we really need is a function with accepts two sets and maps them to a new set which contains the union of all elements. Using a little bit of visual mathematics, our operation looks like the following:

Black box diagram of a union function

This diagram actually demonstrates one of the core ideas behind functional programming as well as giving us a goal to work toward. Ultimately, if we had a function called union which we could use to combine our sets in a predictable way, we, as application developers, would not need to concern ourselves with the inner workings. More importantly, if we understand, at a higher abstraction level, what union should be doing we will be able to digest, fairly immediately, what our function should take as arguments and what it will produce. Our union function can be annotated as (array, array) -> array. Let’s look at the implementation.

With our unique function already constructed, this is a pretty trivial function to implement. There is, of course an item of interest here. Union is almost done for us by the concat function. Concat makes the same assumption our original exploration of converting an array to a set does: arrays are sets of vectors, so a concatenation would be an introduction of two sets of vectors into a new set, reassigning the indices in each vector to map to a new unique set.

This concatenation behavior can be quite useful, but it is not a union operation. In order to perform a proper union of the values in each array we will need to ensure all values of the returned array are actually unique. This means we need to execute a uniqueness operation on the resulting set to get our array which is similar to a set. I.e. if we have an array representing set A, [A], and an array representing set B, [B], then union([A], [B]) ~ A ⋃ B.

Intersection

Much like the union operation, before we try to talk too deeply about the intersection operation, it would be helpful to get a high-level understanding of what intersection means. Intersection is an operation which takes two sets and creates a new set which contains only the shared elements of the original sets. This means the intersection of {1, 2, 3} and {3, 4, 5} is {3}. Visually, intersection looks like the following diagram.

Venn diagram of an intersection of sets

The darker region represents the intersection of sets A and B, which, from our first example, is a set containing only the value 3, or {3}. Much like the union operation, we can create a function intersect which takes two sets and returns a new set containing the intersection. We can diagram this in the same way we did with union.

A black box diagram of an intersection function

This diagram shows us the close relation between intersect and union functions. The annotation for our intersection function is, actually, identical to our union function: (array, array) -> array. This means they share the same contract and could be used on the same sets to produce a result which, incidentally, will match the contract for any function which takes a set of values as a list. Let’s have a look at what the implementation of intersect looks like in Javascript.

As expected, the difference between union and intersection is in the details. Where union performed the combination before we performed a unique operation, intersections can only be taken if all of the values are already unique, This means intersections are slightly more computationally complex than a union, however, in the large, intersection is still a linear operation. We know this by performing the following analysis:

  1. unique is O(n) as defined before
  2. reduce is O(n) by the nature of reduction of a list
  3. buildSetMap is also O(n) as it was the defining characteristic of unique.
  4. intersect is the sum of three O(n) operations, or intersection performs 3n operations, making it, also, O(n)

This algorithmic analysis is helpful in understanding the general characteristic of a function and how it will impact execution time in a larger system. Since union and intersect are both O(n) functions, we can easily use them in a chained way, resulting in a new O(n) function. What this also tells us is, union and intersection are sufficiently performant for small sets of data and acceptable for medium sets. If our sets get large enough we might have to start looking at ways to reduce the number of computations needed to complete the process, but that’s another blog post.

Summary

We can actually use our union and intersect functions together to quickly perform complex mathematical behavior on even non-optimal arrays. Since these functions perform normalization on our sets of data, we can use rather poorly defined arrays and still get meaningful results. Let’s take a quick look at a small example where we set A, B and C as poorly defined arrays and then perform A ⋃ B ⋂ C.

In this post we discussed performing union and intersection operations on arrays of data, as well as implementations for each and their performance characteristics. By understanding these core ideas, it becomes easier to understand how data can be quickly and descriptively modified programmatically. This core understanding is useful both for working with arrays inside of your application as well as better understanding the way data is interrelated in database considerations. Now, go munge data and make it work better for you!