summaryrefslogtreecommitdiff
path: root/semiring
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2023-02-27 12:36:41 +0800
committerJSDurand <mmemmew@gmail.com>2023-02-27 12:36:41 +0800
commitfbaa420ed550e9c3e7cdc09d4a8ec22bfbd782a6 (patch)
treefad9722825bb3fa796dd52c3fd4a8bf46b958cf9 /semiring
parentafad02bdff111ecccb0077b9c989e869723c231c (diff)
before a major refactor
I decide to adopt a new approach of recording and updating item derivation forests. Since this affects a lot of things, I decide to commit before the refactor, so that I can create a branch for that refactor.
Diffstat (limited to 'semiring')
-rw-r--r--semiring/Cargo.toml5
-rw-r--r--semiring/src/counting.rs43
-rw-r--r--semiring/src/lib.rs16
3 files changed, 60 insertions, 4 deletions
diff --git a/semiring/Cargo.toml b/semiring/Cargo.toml
index 0a82e32..caf6cb0 100644
--- a/semiring/Cargo.toml
+++ b/semiring/Cargo.toml
@@ -6,3 +6,8 @@ edition = "2021"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
+grammar = { path = "../grammar" }
+
+[dev-dependencies]
+grammar = { path = "../grammar", features = ["test-helper"] }
+
diff --git a/semiring/src/counting.rs b/semiring/src/counting.rs
new file mode 100644
index 0000000..9095888
--- /dev/null
+++ b/semiring/src/counting.rs
@@ -0,0 +1,43 @@
+//! This module implements the "counting semiring", which counts the
+//! number of ways a sentence can be derived by a grammar.
+
+use super::*;
+
+/// The counting semiring is a thin wrapper around the natural numbers
+/// with the usual addition and multiplication.
+#[derive(Copy, Clone, Debug, Ord, PartialOrd, Hash, Eq, PartialEq)]
+pub struct Count(usize);
+
+impl Count {
+ /// Wrap the count in the wrapper.
+ pub fn new(count: usize) -> Self {
+ Self(count)
+ }
+
+ /// Extract the count out.
+ pub fn value(&self) -> usize {
+ self.0
+ }
+}
+
+impl Semiring for Count {
+ fn zero() -> Self {
+ Self::new(0)
+ }
+
+ fn one() -> Self {
+ Self::new(1)
+ }
+
+ fn add(&mut self, other: &Self) {
+ self.0 = self.value() + other.value();
+ }
+
+ fn mul(&mut self, other: &Self) {
+ self.0 = self.value() * other.value();
+ }
+
+ fn valuation(_pos: usize, _grammar: &Grammar) -> Self {
+ Self::new(1)
+ }
+}
diff --git a/semiring/src/lib.rs b/semiring/src/lib.rs
index 9d096db..6c0e0d5 100644
--- a/semiring/src/lib.rs
+++ b/semiring/src/lib.rs
@@ -15,6 +15,8 @@
//! description. Specifically, it will produce items as it parses the
//! input string. Then we can execute these items by any interpreter.
+use grammar::Grammar;
+
/// 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
@@ -29,14 +31,20 @@ pub trait Semiring {
fn one() -> Self;
/// The addition.
- fn add(&mut self, other: impl AsRef<Self>);
+ fn add(&mut self, other: &Self);
/// The multiplication.
- fn mul(&mut self, other: impl AsRef<Self>);
+ fn mul(&mut self, other: &Self);
+
+ /// A valuation associates a semiring value from a rule position.
+ ///
+ /// Since a position is not complete without a grammar, we also
+ /// give it a grammar.
+ fn valuation(pos: usize, grammar: &Grammar) -> Self;
}
-// TODO: Implement boolean semiring
-// TODO: Implement counting semiring
+pub mod counting;
+
// TODO: Implement derivation forest semiring
#[cfg(test)]