# Static analysis using functional abstraction

*A look at some functional abstractions that enable static
analysis*.

This is a common problem: you want to write a program that can
explain itself without running it with real data: * A CLI argument
parser that can generate the `--help`

output without
providing it with any actual inputs * A build system that can show you
the dependencies between build steps without running the actual build *
A formula that can visualize itself without providing it with any
data

In other words, we can perform **runtime static
analysis** on the code. Runtime static analysis means that we
must run the program to analyze it, but we don’t have to provide any
user inputs to it.

Some programming languages can use reflection to accomplish some of this, and it’s a bit similar in the sense that you are not running the program with user inputs. But it’s also very different from what I’m talking about here because with reflection you need to create a special program to analyse the code. It also requires support from the runtime which many languages simply don’t have.

## The problem

Let’s first zoom into the issue to understand what the problem is. If we take a normal imperative program like the following:

```
foo :: Effect Number
= do
foo <- baz
x bar x
```

which is the same as this:

`= baz `bind` \x -> bar x foo `

we can observe that in order to evaluate `bar`

we need the
value `x`

from `baz`

. If we want to analyze this
program without running it we are out of luck. In order to feed an
`x`

to `bar x`

we must run `baz`

.

We can also just look at the type signature of `bind`

for
`Monad`

:

```
bind :: m a -> (a -> m b) -> m b
^^^
```

and observe that in the second argument the term `m b`

is
inside a lambda, and these terms of type `m b`

are the ones
that we want to analyze and see statically without running the program.
To make program analysis possible we must use other abstractions which
don’t have the terms inside a lambda.

## Applicative functors

One such abstraction is captured by the
`Apply`

/`Applicative`

type class in
Haskell/PureScript:

```
class Functor f => Apply f where
apply :: f (a -> b) -> f a -> f b
```

In neither of the arguments `f`

is inside a lambda, which
is what we need in order to make static analysis on `f`

possible. The `f`

in the first argument is parameterized by a
pure function `a -> b`

which we don’t need to apply in
order to know what the `f`

is.

There are several ways we can design our `Applicative`

data type so that it supports static analysis. The paper Free Applicative Functors
(PDF) explains one approach using a “Free structure”. The Haskell
package optparse-applicative
uses a similar encoding to implement an argument parser that can
generate a `--help`

page from the program definition. The
PureScript package argparse-basic
on the other hand builds both the help *and* the parser in one
go. Both libraries provide a similar API relying on
`Applicative`

.

## Selective applicative functors

Selective Applicative Functors (PDF) are interesting.

```
class Applicative f <= Selective f where
select :: forall a b. f (Either a b) -> f (a -> b) -> f b
```

First of all we can see that no term `f x`

is inside a
lambda, so that’s good in terms of static analysis. The point of
`Selective`

is that the second effect,
`f (a -> b)`

, is optional. We can’t apply the callback
`a -> b`

if the first effect doesn’t provide an
`a`

. When the first effect returns a `b`

, we can
skip the second effect and just return the `b`

.

We can see that `Selective`

provides a static structure
much like `Applicative`

but it also allows for rudimentary
branching logic – all the branches are “visible” statically. The
`branchS`

combinator is a good example of this:

```
branchS :: forall f a. Selective f => f Boolean -> f a -> f a -> f a
= select (map (bool (Left unit) (Right unit)) i) (map const t) (map const e)
branchS i t e where
= if test then x else y bool x y test
```

There are two possible branches that the computation might take. The
one that is taken depends on the `Boolean`

we get from the
first effect. Since we can enumerate all the values of a
`Boolean`

, we can statically also enumerate all the possible
consequences because neither of the branches are under a lambda
term.

In the paper they explain how Selective Applicative Functors can be used in build systems to calculate dependencies statically without running the build.

## Lifting to Category

There’s one other way to make static analysis possible even in the
presense of dependencies between terms. Basically, you can take the
callback from `bind`

:

```
bind :: m a -> (a -> m b) -> m b
^^^^^^^^^^
```

and lift it to a data type:

```
data Star m a b = Star (a -> m b)
^^^^^^^^^^
```

This eliminates the lambda term from the type you are composing.
Instead of composing terms of `m a`

you are now composing
terms of the shape `a -> m b`

. Essentially here we are
composing “boxes” of inputs and outputs, without the possibility of
knowing what the inputs and outputs are exactly. This forces you to work
with more high level APIs like `Category`

and `Profunctor`

.

The most basic example is the `compose`

function in the
`Category`

type class:

```
compose :: Category cat => cat b c -> cat a b -> cat a c
a2c :: Category cat => cat a c
= compose b2c a2b a2c
```

We can statically analyze the expression `a2c`

and say
that both `a2b`

and `b2c`

are used to compute the
result. The same cannot be said if we write the composition “by hand”
using plain function composition:

```
compose :: (b -> c) -> (a -> b) -> (a -> c)
a2c :: a -> c
= compose b2c a2b a2c
```

The reason, once again, is that the terms we are composing include lambda terms, and we can’t look inside them without applying them to some value.

Now, it might not be useful to analyze the program at this higher
`Category`

level but it could be useful in situtations where
applicative composition is not possible. You could say that with this
approach we can see what boxes are being composed, but we can’t see what
those boxes contain. But remember, boxes can be composed of other boxes!
There are combinators at your disposal from `Category`

and the `Profunctor`

hierarchy which provide ways to do this.

The tradeoff with this kind API is that it is much more high-level and those combinators can be quite difficult to work with, at least it takes some time getting used to. Because it’s so high-level, the analysis you can do on the terms is limited to be on a higher level as well.

## Conclusion

I’ve shown a few ways we can approach runtime static analysis using
functional abstraction. We’ve seen how `Monad`

is doesn’t
have the necessary properties while Applicative Functors do. There is
also Selective Applicative Functors that sit between Applicative and
Monad, which do have similar qualities for doing limited runtime static
analysis. Sometimes we can even reach for a higher level abstraction
with `Category`

and `Profunctor`

to be able to
analyze programs on a higher level. I didn’t even mention Monoids or
Semirings which have good properties for static analysis since they are
even simpler than the ones mentioned in this post. That will have to be
another post!