# Refinery

`refinery`

provides a series of language-independent building blocks for creating automated, type directed program synthesis tools.
It is currently used to power the automatic code synthesis tool Wingman For Haskell.

## Introduction

If you are already familiar with the idea of tactics, feel free to skip ahead to the Usage section.

What exactly do we do when we sit down and write a program? Sure, we may have lofty ideas about
what it may do in the end, but I'm talking about the actual process of writing a program.
For instance, take the following (rather silly) example:

```
pairing :: (a -> b) -> (a -> c) -> a -> (b,c)
pairing = _
```

The first thing we might do is look at the type, see that we are writing a function, and introduce the arguments.

```
pairing :: (a -> b) -> (a -> c) -> a -> (b,c)
pairing f g a = _
```

Then, we see that we are trying to make a pair type, so we will introduce a pair constructor.

```
pairing :: (a -> b) -> (a -> c) -> a -> (b,c)
pairing f g a = (_, _)
```

Then, we will see that we need to produce a `b`

and a `c`

, and we have two functions in scope that do that, so may as well
try them!

```
pairing :: (a -> b) -> (a -> c) -> a -> (b,c)
pairing f g a = (f _, g _)
```

Now, we need an `a`

, and we have one in scope, so let's use that!

```
pairing :: (a -> b) -> (a -> c) -> a -> (b,c)
pairing f g a = (f a, g a)
```

Now, this entire process of writing this function was entirely mechanical. We just looked at the type of the hole,
looked at what we had in scope, and applied some simple edits to get some more holes, and repeated. This feels
like we could automate this!

Now, a "tactic" is exactly this. We can think of it morally as something like the following type: `(Type -> [Type], [Expr -> Expr])`

.
In short, they break the hole down into a bunch of smaller holes, and combine expressions that fit into those holes into one big expression!
This library provides the means for creating simple tactics for *any* language you can cook up, as well as "tactic combinators", which have
a similar flavor to parser combinators. Parser combinators let us compose small atomic parsers together to form larger ones, and Tactic
combinators let us compose together small tactics to create sophisticated tools for automatic program synthesis.

## Usage

Let's walk through the usage of this library with a small example. The full source code of this example can be found in `tests/Spec/STLC.hs`

.

First, let's import the main module, along with some MTL stuff:

```
import Data.List
import Control.Monad.Identity
import Control.Monad.State
import Refinery.Tactic
```

Now let's define a teeny tiny simply typed lambda calculus:

```
-- Expressions in simply typed lambda calculus, along with holes
data Term
= Var String
| Hole
| Lam String Term
| Pair Term Term
deriving (Show, Eq)
-- Types in our version of simply typed lambda calculus
data Type
= TVar String
| Type :-> Type
| TPair Type Type
deriving (Show, Eq)
```

Now, we are going to need to define the idea of a "type in a context", commonly referred to as a "Judgement".

```
newtype Judgement = [(String, Type)] :- Type
deriving (Show)
```

Now, a bit of boilerplate is required to tell `refinery`

how to generate holes.
Most of the time, you will need to have a fresh source of variables for your holes, or you
may need to run effects when you generate them. However, in the name of simplicity, let's just use
`Identity`

```
instance MonadExtract Term String Identity where
hole = pure Hole
unsolvableHole _ = pure Hole
```

Now for our first tactic:

```
type T a = TacticT Judgement Term String Int Identity a
-- Tactic for solving holes of type (a,b)
pair :: T ()
pair = rule $ \goal ->
case goal of
(hys :- TPair a b) -> Pair <$> subgoal (hys :- a) <*> subgoal (hys :- b)
_ -> unsolvable "goal mismatch: Pair"
```

Now, there is a *lot* going on here, so let's take it apart piece by piece:
To start, let's look at `TacticT`

. The first type parameter is the "goal" type.
We can think of this as the thing that we are trying to "solve". For us, this
is `Judgement`

, as we are going to need to know exactly what is in scope at a given point.

The next type parameter is what the tactic is going to synthesize, commonly referred to as the
"extract".

The next three type parameters are decidedly less exciting. They represent the type of errors, the
type of the state, and the base monad. We need to have a way of generating unique names, so let's
just use `Int`

as our state to accomplish this.

<!-- FIXME: Better explanation -->
That final type parameter is the type that the tactic during the course of execution. We will discuss this further in the future,
so if you are confused, feel free to ignore this type parameter for now.

Next, we call `rule`

to create a "basic" tactic, that lets us inspect the current goal, and create a bunch of subgoals via `subgoal`

.
As we are trying to tell `refinery`

how to synthesize pairs, we case on the type of the hole. If it is a pair type, we create two
new goals, one for each component of the tuple type, and then combine the solutions to those subgoals together with a pair constructor.
If the type does not match, then we throw an error via `unsolvable`

.

Now, finally, we need a way of solving goals of the form `a -> b`

.

```
lam :: T ()
lam = rule $ \case
(hys :- (a :-> b)) -> do
name <- gets show
modify (+ 1)
body <- subgoal $ ((name, a) : hys) :- b
pure $ Lam name body
_ -> unsolvable "goal mismatch: Lam"
```

This is where the state comes in. We look up the current state, show it for use as a name,
and then increment it so that our names are unique. We then create a subgoal for `b`

,
and add our new fresh name into scope, specifying that it has type `a`

.
We then get the result of the subgoal and put it in a `Lam`

constructor along with our fresh name.

Finally, let's define a tactic for solving a goal by using something in scope.

```
assumption :: T ()
assumption = rule $ \ (hys :- a) ->
case find (\(_, ty) -> ty == a) hys of
Just (x, _) -> pure $ Var x
Nothing -> unsolvable "goal mismatch: Assumption"
```

Now, for something really exciting. Let's write a tactic that can synthesize expressions for this language. Now that we have our building blocks, this
is very easy!

```
auto :: T ()
auto = do
many_ lam
(pair >> auto) <|> assumption
```

Before explaining how exactly this *works*, let's look at what it does!

```
λ> solutions auto ([] :- (TVar "a" :-> TVar "b" :-> (TPair (TVar "a") (TVar "b")))) 0
> [Lam "0" (Lam "1" (Pair (Var "0") (Var "1")))]
```

As we can see, it generated the right thing! Let's now step through *how* exactly it did this.
To start, `many_`

is a "tactic combinator". It takes a tactic as it's first argument, and
will run it repeatedly until it fails. This will result in a single subgoal that looks something like

```
[("0", TVar "a"), ("1", TVar "b")] :- (TPair (TVar "a") (TVar "b"))
```

Now, for the magic. The bind for `TacticT`

will run the second tactic on *every* subgoal created by the first.
With this crucial piece of information, we can begin to see how `auto`

works. Once `many_ lam`

is executed,
we execute both `pair >> auto`

and `assumption`

against the subgoal generated, and collect all of the
solutions found by both branches together. `pair`

will generate 2 subgoals, and then `>> auto`

will apply
`auto`

recursively to *both* of those subgoals.

## References

`refinery`

is based roughly on Algebraic Foundations of Proof Refinement