summaryrefslogtreecommitdiff
path: root/semiring
diff options
context:
space:
mode:
Diffstat (limited to 'semiring')
-rw-r--r--semiring/src/lib.rs51
1 files changed, 40 insertions, 11 deletions
diff --git a/semiring/src/lib.rs b/semiring/src/lib.rs
index 7d12d9a..9d096db 100644
--- a/semiring/src/lib.rs
+++ b/semiring/src/lib.rs
@@ -1,14 +1,43 @@
-pub fn add(left: usize, right: usize) -> usize {
- left + right
+#![warn(missing_docs)]
+//! This crate defines the expected behaviours of semirings and
+//! semiring parsers. Some standard semirings are also implemented,
+//! such as the boolean, the counting, and the derivation forest
+//! semirings. Moreover, this crate also defines the behaviours of a
+//! parser, with the formalism of an "item-based description". See
+//! the paper [Parsing
+//! inside-out](https://arxiv.org/abs/cmp-lg/9805007) by Joshua
+//! Goodman. To be more precise, it defines the behaviours of an
+//! "item interpreter" that executes "items" in a chosen semiring.
+//! Finally, it provides a default implementation of an item
+//! interpreter.
+//!
+//! The crate *chain* will implement a parser using the item-based
+//! description. Specifically, it will produce items as it parses the
+//! input string. Then we can execute these items by any interpreter.
+
+/// A semiring is equipped with two operations: the addition and the
+/// multiplication. It also has additive and multiplicative
+/// identities. Also the two operations are supposed to be
+/// associative, and the multiplication is supposed to be distributive
+/// over the addition. But the addition is not required to be
+/// commutative, and is usually not indeed commutative.
+pub trait Semiring {
+ /// The additive identity.
+ fn zero() -> Self;
+
+ /// The multiplicative identity.
+ fn one() -> Self;
+
+ /// The addition.
+ fn add(&mut self, other: impl AsRef<Self>);
+
+ /// The multiplication.
+ fn mul(&mut self, other: impl AsRef<Self>);
}
+// TODO: Implement boolean semiring
+// TODO: Implement counting semiring
+// TODO: Implement derivation forest semiring
+
#[cfg(test)]
-mod tests {
- use super::*;
-
- #[test]
- fn it_works() {
- let result = add(2, 2);
- assert_eq!(result, 4);
- }
-}
+mod tests {}