Stream programs are monoid homomorphisms with state
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _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 |