hellas-ai / hellas-ai/open-hypergraphs

Rewriting Implementation

Open
#9 0 comments 0 reactions 1 assignee Claimed by @random-anon333 View on GitHub
enhancement
Dominant language
Rust
Stars
25
Forks
7
PR merge metrics
No merged PRs in 30d

Description

# Feature: Rewriting for Open Hypergraphs

Consider the following program using a (currently nonexistent) kernel language.

F32(M,N)
●----\ F32(M,N) F32(M,N)
[Map(add)]----●------[Map(negate)]------●
●----/
F32(M,N)

Interpret `Map(f)` as applying the kernel `f` to every element of each input array.
So `add : f32 × f32 → f32` is the kernel, the `Map(add)` goes between *arrays* of `f32`.

We should be able to fuse the two "Map" kernels into one:

F32(M,N)
●----\ F32(M,N)
[Map(add ; negate)]----●
●----/
F32(M,N)

Where `add : negate : f32 × f32 → f32` is the kernel `x y → -(x+y)`

Proposal: we do this by *rewriting*.
There are three parts to implement:

1. Identify a "match" (aka "LHS"): the region of the graph to rewrite (in example above, the two hyperedges `Map(add)`, `Map(negate)`, and their interfaces
2. Compute the result (aka "RHS"): in this case, the single op `Map(add; negate)`
3. Implement *rewriting*: replace LHS with RHS in the graph

# Simple example

Here's a simpler example usable for testing. It corresponds to rewriting `x + (-y) → x - y`

----------------●----\ ---●----\
[add]----●----- ~> [sub]----●-----
----●---[neg]---●----/ ---●----/

# This feature: a PR for open-hypergraphs

Assume both the match and RHS are known, so we only need to implement step (3) from above.
A rough sketch:

- Append the RHS into the graph
- Quotient the RHS interfaces with the match's interface
- Delete all non-interface data of the match

# Acceptance criteria

- Propose API addition for rewriting in the `lax` module
- Datastructures for a `Match` in an open hypergraph
- Unit tests in the open hypergraphs library demonstrating successful rewrites;
- Use evaluation to check rules like `x + (-y) = x - y`.

# References/Glossary

- [Open Hypergraphs library](https://docs.rs/open-hypergraphs/latest/open_hypergraphs/)
- String Diagram Rewrite Theory paper series:
- [I](https://arxiv.org/abs/2012.01847)
- [II](https://arxiv.org/abs/2104.14686)
- [III](https://arxiv.org/abs/2109.06049)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.