reduce-equations

Readme


# Reduce Equations #

This package provides a command `reduce-equations` which reads in a list of
equations from stdin, performs some simplification, and writes the results to
stdout.

For example, given the equations `a = b`, `b = c` and `a = c`, one of these will
be removed as it can be inferred from the other two. Similarly, given equations
`f a = g`, `f b = g` and `a = b`, one of the first equations will be removed as
it can be recovered by subtitution.

All of the real work is done by [QuickSpec](https://hackage.haskell.org/package/quickspec)
This package just provides stdio and machine-friendly formatting.

## Formats ##

All IO is encoded in JSON. Both stdin and stdout should contain a single array
of equations. The following example gives a single equation, which if written in
a more human-friendly form, would be `plus x x = times x 2`:

```
[
 {"relation": "~=",
  "lhs":      {"role": "application",
               "lhs":  {"role": "application",
                        "lhs":  {"role":   "constant",
                                 "type":   "Int -> Int -> Int",
                                 "symbol": "plus"},
                        "rhs":  {"role": "variable",
                                 "type": "Int",
                                 "id":   0}},
               "rhs":  {"role": "variable",
                        "type": "Int",
                        "id":   0}},
  "rhs":      {"role": "application",
               "lhs":  {"role": "application",
                        "lhs":  {"role":   "constant",
                                 "type":   "Int -> Int -> Int",
                                 "symbol": "times"},
                        "rhs":  {"role": "variable",
                                 "type": "Int",
                                 "id":   0}},
               "rhs":  {"role":   "constant",
                        "type":   "Int",
                        "symbol": "two"}}}
]
```

### Equations ###

An equation is an object with the following values:

 - `relation`: This is used mostly to identify that we've got an equation. In
   practice, this is always `"~="` (what that means is up to you).
 - `lhs`: this is a `term`, supposedly the left-hand-side of the equation,
   although the only difference from `rhs` is the name.
 - `rhs`: this is a `term`, just like `lhs` except it's the right-hand-side.

Example:

```
{"relation": "~=",
  "lhs":     {"role": "application",
              "lhs":  {"role":   "constant",
                       "type":   "Bool -> Bool",
                       "symbol": "not"},
              "rhs":  {"role": "application",
                       "lhs": {"role":   "constant",
                               "type":   "Bool -> Bool",
                               "symbol": "not"},
                       "rhs": {"role": "variable",
                               "type": "Bool",
                               "id": 0}}},
  "rhs":     {"role": "variable",
              "type": "Bool",
              "id":   0}}
```

### Terms ###

A term is an object containing a `role`, which is one of `"constant"`,
`"variable"` or `"application"`. The other fields depend on what the term's
`role` is:

 - Constants
    - `type`: The type of the constant, a string written in Haskell's type
      notation. This is taken from the given function descriptions. For example
      `"Int -> (Int -> Bool) -> IO Float"`
    - `symbol`: The name of the constant, as a string. For example `"reverse"`.
 - Variables
    - `type`: The type of the variable, a string written in Haskell's type
      notation. The types can be made up, but they should be consistent (e.g.
      both sides of an equation should have the same type; application should be
      well-typed; etc.). Unification of polymorphic types isn't supported; types
      are identified syntactically. For example `"[Int]"`.
    - `"id"`: A numeric ID for the variable. IDs start at `0`. Used to
      distinguish between multiple variables of the same type. Variable ID only
      matters within a single equation. For example, to represent three integer
      variables we might use `{"role": "variable", "type": "Int", "id":0}`,
      `{"role": "variable", "type": "Int", "id":1}` and
      `{"role": "variable", "type": "Int", "id":2}`.
 - Applications
    - `lhs`: A term representing a function to apply.
    - `rhs`: A term representing the argument to apply the `lhs` function to.
      Functions are curried, so calling with multiple arguments should be done
      via a left-leaning tree.

## Implementation Notes ##

We co-opt the equation-reducing machinery of the
[QuickSpec](https://hackage.haskell.org/package/quickspec-0.9.6) library to do
the actual reduction. This relies heavily on existential types and Haskell's
[Typeable](https://hackage.haskell.org/package/base-4.9.0.0/docs/Data-Typeable.html)
mechanism.

Since the incoming equations may have arbitrary types, and GHC doesn't let us
define custom `Typeable` instances, we perform a conversion step:

 - Once an array of equations has been parsed, we recurse through the terms and
   switch out each distinct type with a freshly-generated replacement, of the
   form `Z`, `S Z`, `S (S Z)`, etc. (these are just Peano numerals, e.g. see
   https://en.wikipedia.org/wiki/Successor_function )
 - We provide special functions `getRep` and `getVal` to plumb these Peano types
   into QuickSpec's machinery, convincing it that we have a signature of
   well-typed terms.
 - We reduce the given equations, with their switched-out types, to get a
   reduced set.
 - We switch back the types for presentation purposes, pretty-printing to JSON.

Repository

Clone this repository using: 
  git clone http://chriswarbo.net/git/reduce-equations.git

Branches

Generated by git2html.