summaryrefslogtreecommitdiff
path: root/semiring/src/lib.rs
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2023-01-28 10:17:24 +0800
committerJSDurand <mmemmew@gmail.com>2023-01-28 10:22:57 +0800
commitf28155105134b90fd86049c65478d307e0d8dbbc (patch)
tree72b3b4872d5dba89413eca70bcaae9e421def7ee /semiring/src/lib.rs
parente8ea01319b3a9032a3f4f69f65e9ca96562b87b9 (diff)
a prototype of an item derivation forest
It seems to be complete now, but still awaits more tests to see where the errors are, which should be plenty, haha.
Diffstat (limited to 'semiring/src/lib.rs')
-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 {}