#Managing the complexity III: using powerful abstractions

In this section I will list a few techniques which allow one to write more modular code and better separate the concerns, by using certain powerful abstractions provided by or possible to have in the Mathematica.

##Higher-order functions

These are functions which take other functions as arguments. In Mathematica, a number of core built-in functions like Map and Apply are higher-order functions.

The utility of this construct can be seen most clearly within the functional programming paradigm. Higher-order functions can be used to parametrize generic functionality, where custom behavior is injected with functional arguments. This allows one to easily separate generic functionality from the specific.

###Trivial example: Select

One trivial example of a built-in higher-order function is Select. We can write a more specific version of Select that would select numbers larger than a threshold by parametrizing Select with an appropriate test function:

ClearAll[mySelect];
mySelect[l_List, threshold_]:=Select[l,#>threshold&]

So that

mySelect[Range[10], 5]

(* {6, 7, 8, 9, 10} *)

Note that the test function #>threshold& is in fact a closure, closed over threshold and created at run-time.

###Example: Gram - Schmidt orthogonalization

In this answer, I gave a possible implementation of the Gram - Schmidt orthogonalization procedure, as a higher-order function

GSOrthoNormalizeGen[startvecs_List, dotF_, plusF_, timesF_]

which takes the functions implementing dot product, addition of vectors and multiplication of a vector by a scalar, as parameters. As a result, it can be used for vectors from any vector spaces - all one have to do is to implement these specific functions. In the linked post there are examples for the space of 3D vectors and space of functions.

What this means in practice is that the generic implementation and the specific parts parametrizing it are completely decoupled, they can (and probably should) live in different parts of the project, or even belong to different sub-projects. Therefore, such generalization actually simplifies the code even if I am only interested in a single type of a vector space.

##Closures

Closures are functions that are created at run-time, and have access to the enclosing environment (variables and functions from it). They can then operate on that environment long after the code execution leaves it. Closures are an effective tool to factor and separate functionality. They realize a form on encapsulation, somewhat similar to objects, but more lightweight - they encapsulate behavior rather than state (although can manipulate the state too).

###Example: approximate derivative of a function

This is a classic example. Here, we construct a function that would approximately compute a derivative of another function, numerically:

approxD[f_, dx_] := Function[x, (f[x + dx] - f[x])/dx]

We can now define it for some function:

dsin = approxD[Sin, 0.2];

and use it:

dsin[0]

(* 0.993347 *)

The whole point is that we don't have to know how dsin was constructed, and all the information associated with the process of its construction - we can just use it. It can be stored somewhere, and then used at some later point, perhaps by a different part of the system. It is this kind of separation of construction and execution of certain behavior that makes closures so effective at factoring apart separate components of the system.

###Example: iterator for Fibonacci numbers

Here is a very simple example of a closure, implementing an iterator of Fibonacci numbers:

makeFibIterator[] :=
 Module[{current = 1, prev = 0},
   Function[Last[{prev, current} = {current, current + prev}]]
 ]

It is closed over local variables current and prev. It retains access to these variables even after the code leaves Module. This is a stateful closure. Here is an example of use:

iter =  makeFibIterator[];
Table[iter[], 10]

(* {1, 2, 3, 5, 8, 13, 21, 34, 55, 89} *)

Once again, note that after we construct an iterator, it can be used at some point later on, perhaps by a completely different part of the system. That part may not care what this iterator is made of, or how it was constructed - it only knows that the iterator returns a next element when called.

###Summary

Closures are a very useful abstraction, that allows one to encapsulate behaviors and use them later on, without bothering about the full execution context for those behaviors (which may no longer be available), since closures still do have access to that context. They can be thought of as very light-weight objects, but the key difference is that they encapsulate behavior rather than state (but can also manipulate internal state if that's the part of the behavior). They usually work together with higher - order functions, being passed to them and called by them.

Closures facilitate information-hiding, because they allow different parts of the system to exchange minimal units of encapsulated behavior, and the less different parts must assume about the other parts, the more they get decoupled, and the more modular the entire code base becomes. At the same time, they protect their internal state much better than the full-fledged objects in the OO paradigm (unless those have no setters, i.e. are read-only), since they don't provide means to change their internal state other than what they do themselves when being executed. The real need of objects arises when one needs more than one closure with a shared mutable state, but in many cases this isn't really necessary and single closures can do just fine.

##ADTs and stronger typing

Defining abstract data types and making the code de facto more strongly typed is an important tool to scale to larger code bases. It allows to automatically exclude large classes of bugs, which otherwise are likely to appear in the course of code evolution. It also often makes the code much more readable, and much easier to reason about.

There are several possibilities for enforcing stronger typing in one's code. Basically, one can:

• Use patterns and argument checks to enforce types

  This is easier to do and is a less formal way to introduce types, which is used in many practical situations. The typing it introduces is similar to a "duck typing", however.

• Use dedicated inert heads as data containers / types

  This method allows one to create truly strong types. It might be an overkill do always do that, but there are cases where this option is great.

###Example: using patterns

I will use a function to pick numbers in a specified interval, from this answer

window[list_,{xmin_,xmax_}]:=
  Pick[list,Boole[xmin<=#<=xmax]&/@list,1]

We may make it better check arguments, de-facto making this piece of code more strongly-typed:

windowTyped[list_List,{xmin_?NumericQ,xmax_?NumericQ}]:=
    Pick[list,Boole[xmin<=#<=xmax]&/@list,1]

We may restrict the arguments even more:

windowTypedStronger[list:{___?NumericQ},{xmin_?NumericQ,xmax_?NumericQ}]:=
  Pick[list,Boole[xmin<=#<=xmax]&/@list,1] 

Note that you can go further and introduce patterns for your types, so that you can use them in many functions to check the arguments. For example, we could've done:

numericListPtn = {___?NumericQ}

and then

windowTypedStronger[list:numericListPtn, {xmin_?NumericQ,xmax_?NumericQ}]:= ...

where you can now use numericListPtn for argument checks in all functions which are supposed to take this type as an argument

###Example: implementing a Cache data type

This section will illustrate how to implement truly strong types. To make this section a bit more useful, I will post here an implementation of a Cache data structure, based on associations. Here is a very crucial helper function:

(* A fast (O(1)) function to remove the first key-value pair in an assoc. Note that Delete or Drop are O(N). Note: a key should NOT be a list *)

ClearAll[deleteFirst];
deleteFirst[assoc_]:=KeyDrop[assoc, Keys@assoc[[{1}]]]

Here goes the main implementation:

ClearAll[Cache, RemoveCache, ClearCache];
SetAttributes[Cache, HoldAll];
Cache[limit_]:= Module[{s=<||>},Cache[s, limit]];
Cache /: KeyExistsQ[Cache[s_, _], key_]:=KeyExistsQ[s,key];
Cache /: Cache[s_,_][key_]:=
  With[{res = s[key]},
    If[!MissingQ[res],AppendTo[s,key->res]];
    res
  ];
Cache /: Normal[Cache[s_,_]]:=s;
(* Note: Append mutates the state and has different semantics here than usual *)
Cache /: Append[c:Cache[s_,limit_], key_-> value_]:=
  Module[{},
    If[Length[s]==limit,s = deleteFirst[s];];
    AppendTo[s,key -> value];
    value
  ];
RemoveCache[Cache[s_,_]]:=CompoundExpression[Remove[s]];
ClearCache[Cache[s_,_]]:= s = <||>;

There are a few things to note from this code:

• The cache objects are strongly typed, they all have the head Cache.
• The Cache head is an inert container for data
• A number of built-in functions were overloaded on Cache data type, using UpValues. In this way, we can use familiar function names without a danger to affect other functionality in the system

The technical part of this implementation is fairly simple. We use the fact that associations are ordered, and when we add a new key-value pair, it is added at the end. The cache is supposed to store n most recent values. To do that, it works as follows: when a value is requested from the cache, and is present there, it moves it at the end (adding the same value again - it is O(1) operation). When we grow the cache to its full capacity, it starts removing key - value pairs from the start. The only tricky part was to have such removal as a fast operation, since Delete and Drop on an association are O(n) even for the first positions).

Here are some examples of use:

Create a cache

cache = Cache[10];

Add some values

Do[Append[cache, i -> i + 1], {i, 1, 10}]

Check what's inside

Normal@cache

(* <|1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5, 5 -> 6, 6 -> 7, 7 -> 8, 8 -> 9, 9 -> 10, 10 -> 11|> *)

Append a key that's already there:

Append[cache, 1 -> 100]

(* 100 *)

We can see that it moved to the right

Normal@cache

(* <|2 -> 3, 3 -> 4, 4 -> 5, 5 -> 6, 6 -> 7, 7 -> 8, 8 -> 9, 9 -> 10, 10 -> 11, 1 -> 100|> *)

Append another key-value

Append[cache, 15 -> 30];
Normal@cache

(* <|3 -> 4, 4 -> 5, 5 -> 6, 6 -> 7, 7 -> 8, 8 -> 9, 9 -> 10, 10 -> 11, 1 -> 100, 15 -> 30|> *)

Do a massive appending (the capacity is only 10)

Do[Append[cache, i -> i + 1], {i, 11, 1000}] // AbsoluteTiming

(* {0.023462, Null} *)

Check the current cache state

Normal@cache

(* <|991 -> 992, 992 -> 993, 993 -> 994, 994 -> 995, 995 -> 996, 996 -> 997, 997 -> 998, 998 -> 999, 999 -> 1000, 1000 -> 1001|> *)

Remove the cache

RemoveCache@cache 

###The role of UpValues

It is important to stress that UpValues are an indispensable tool to overload various functions (built-in or user-defined) on custom data types. They provide the only safe way to do that, in fact.

###More resources

Here are some relevant links

• How to create strong types
• How can I type-check the arguments of a Mathematica function?
• How can this confetti code be improved to include shadows and gravity?

###Summary

Introducing some level of typing is a very useful technique to improve the robustness of your code.

A simpler way to do that is to introduce patterns which expressions belonging to some type should match, and then insert argument checks based on these patterns, into the definitions of those functions which work with these objects. This has an advantage of being simple and quick to do, but a disadvantage that the types introduced in this way won't be in general fully strong and robust.

A somewhat more formal way is to introduce a special head for the type, and then methods working on that head. This is somewhat harder to implement than the first option, but has several advantages: the code is typically more robust and also usually ends up easier to read and understand.