Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.10799 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918091397529600 |
|---|---|
| author | Hou, Tyler Arntzenius, Michael Willsey, Max |
| author_facet | Hou, Tyler Arntzenius, Michael Willsey, Max |
| contents | We define a broad class of deterministic stream functions and show they can be implemented as homomorphisms into a "state" monoid. The homomorphism laws are simpler than the conditions of previous semantic frameworks for stream program optimization, yet retain support for rich equational reasoning over expressive dataflow programs, including sequential composition, parallel composition, and feedback. We demonstrate this using examples of partitioned database joins, stratified negation, and a simplified model of TCP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_10799 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Stream programs are monoid homomorphisms with state Hou, Tyler Arntzenius, Michael Willsey, Max Programming Languages Distributed, Parallel, and Cluster Computing We define a broad class of deterministic stream functions and show they can be implemented as homomorphisms into a "state" monoid. The homomorphism laws are simpler than the conditions of previous semantic frameworks for stream program optimization, yet retain support for rich equational reasoning over expressive dataflow programs, including sequential composition, parallel composition, and feedback. We demonstrate this using examples of partitioned database joins, stratified negation, and a simplified model of TCP. |
| title | Stream programs are monoid homomorphisms with state |
| topic | Programming Languages Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2507.10799 |