Incremental computation through constrained memoization.

Overview

comemo

Crates.io Documentation

Incremental computation through constrained memoization.

[dependencies]
comemo = "0.1"

A memoized function caches its return values so that it only needs to be executed once per set of unique arguments. This makes for a great optimization tool. However, basic memoization is rather limited. For more advanced use cases like incremental compilers, it lacks the necessary granularity. Consider, for example, the case of the simple .calc scripting language. Scripts in this language consist of a sum of numbers and eval statements that reference other .calc scripts. A few examples are:

  • alpha.calc: "2 + eval beta.calc"
  • beta.calc: "2 + 3"
  • gamma.calc: "8 + 3"

We can easily write an interpreter that computes the output of a .calc file:

/// Evaluate a `.calc` script.
fn evaluate(script: &str, files: &Files) -> i32 {
    script
        .split('+')
        .map(str::trim)
        .map(|part| match part.strip_prefix("eval ") {
            Some(path) => evaluate(&files.read(path), files),
            None => part.parse::<i32>().unwrap(),
        })
        .sum()
}

impl Files {
    /// Read a file from storage.
    fn read(&self, path: &str) -> String {
        ...
    }
}

But what if we want to make this interpreter incremental, meaning that it only recomputes a script's result if it or any of its dependencies change? Basic memoization won't help us with this because the interpreter needs the whole set of files as input—meaning that a change to any file invalidates all memoized results.

This is where comemo comes into play. It implements constrained memoization with more fine-grained access tracking. To use it, we can just:

  • Add the #[memoize] attribute to the evaluate function.
  • Add the #[track] attribute to the impl block of Files.
  • Wrap the files argument in comemo's Tracked container.

This instructs comemo to memoize the evaluation and to automatically track all file accesses during a memoized call. As a result, we can reuse the result of a .calc script evaluation as as long as its dependencies stay the same—even if other files change.

use comemo::{memoize, track, Tracked};

/// Evaluate a `.calc` script.
#[memoize]
fn evaluate(script: &str, files: Tracked<Files>) -> i32 {
    ...
}

#[track]
impl Files {
    /// Read a file from storage.
    fn read(&self, path: &str) -> String {
        ...
    }
}

For the full example see examples/calc.rs.

License

This crate is dual-licensed under the MIT and Apache 2.0 licenses.

You might also like...
A rust library + CLI tool  that tells you when swas will upload new video through complex calculations
A rust library + CLI tool that tells you when swas will upload new video through complex calculations

A rust library + CLI tool that tells you when swas will upload new video through complex calculations. It also lets you search and play youtube videos of swas and other channels. Searching about youtube channels is also an option. Basically it's a youtube search cli tool written in rust.

McFly - fly through your shell history
McFly - fly through your shell history

McFly - fly through your shell history McFly replaces your default ctrl-r shell history search with an intelligent search engine that takes into accou

Koi is a simple tool built to let you use ChatGPT through the command line

Koi is a simple tool built to let you use ChatGPT through the command line. It adds the ability to let ChatGPT run commands on your computer in order to help you out, or to help you out with complicated tasks.

Burrow is a tool for burrowing through firewalls, built by teenagers at Hack Club.

Burrow Burrow is a tool for burrowing through firewalls, built by teenagers at Hack Club. At its core, burrow is a command line utility written in Rus

An interactive Bayesian Probability Calculator CLI that guides users through updating beliefs based on new evidence.

Bayesian Probability Calculator CLI Welcome to the Bayesian Probability Calculator CLI! This command-line tool is designed to help you update your bel

A GPT-3 access point through Nostr, powered by lightning

Geppeto A Nostr based API for GPT-3, powered on Lightning. The bot listens for event kind 29000 (inspired by NIP-9000) and will query the prompt to th

Terminal UI for leetcode. Lets you browse questions through different topics. View, solve, run and submit questions from TUI.
Terminal UI for leetcode. Lets you browse questions through different topics. View, solve, run and submit questions from TUI.

Leetcode TUI Use Leetcode in your terminal. Why this TUI: My motivation for creating leetcode-tui stemmed from my preference for tools that are lightw

Leptos server signals synced through Server-Sent-Events (SSE)

Leptos Server Sent Events Server signals are leptos signals kept in sync with the server through server-sent-events (SSE). The signals are read-only o

🚀 JavaScript driver for ScyllaDB, harnessing Rust's power through napi-rs for top performance. Pre-release stage. 🧪🔧
🚀 JavaScript driver for ScyllaDB, harnessing Rust's power through napi-rs for top performance. Pre-release stage. 🧪🔧

🚀 JavaScript driver for ScyllaDB. Pre-release stage. 🧪🔧 ⚠️ Disclaimer ⚠️ This repository and the associated npm package are currently in a 🐣 pre-r

Releases(v0.1)
Owner
Typst
Compose papers faster: Focus on your text and let Typst take care of layout and formatting.
Typst
High-performance asynchronous computation framework for system simulation

Asynchronix A high-performance asynchronous computation framework for system simulation. What is this? Warning: this page is at the moment mostly addr

Asynchronics 7 Dec 7, 2022
Verifiable and confidential computation based on ZKP and FHE, powered by risc0 zkVM.

zkFHE Verifiable and confidential computation based on ZKP and FHE, powered by risc0 zkVM. A PoC to demonstrate an approach for private computation on

Emiliano Bonassi 29 Apr 25, 2023
qsv - Performant CLI tool to query CSVs through SQL

qsv Performant CLI tool to query CSVs through SQL Installation After cloning the repository, you can install a binary locally using cargo install --pa

Dermot Haughey 3 Oct 28, 2021
A Rust CLI tool that helps you enforce Git policies through Git hooks both server and client side

GitPolicyEnforcer This is a command line utility written in Rust, that helps you utilize Git hooks, to enforce various policies. It currently supports

Vagelis Prokopiou 4 Aug 14, 2022
Voila is a domain-specific language launched through CLI tool for operating with files and directories in massive amounts in a fast & reliable way.

Voila is a domain-specific language designed for doing complex operations to folders & files. It is based on a CLI tool, although you can write your V

Guillem Jara 86 Dec 12, 2022
Terminal UI that allows Alacritty users to quickly and easily shuffle through provided themes 🦄

Alac-pretty alac-pretty.mp4 If you're like me in that you constantly need to change the colors of your dev environment because visual stagnation reall

Benji Nguyen 17 Aug 29, 2022
FastSSH is a TUI that allows you to quickly connect to your services by navigating through your SSH config.

Connect quickly to your services ?? FastSSH is a TUI that allows you to quickly connect to your services by navigating through your SSH config. Instal

Julien 85 Dec 14, 2022
Learning Rust through Advent of Code 2021 - probably not very clean!

AoC 2021 ======== I'm using AoC2021 as an excuse to learn Rust (and maybe some other languages). Please do *not* use this repository as a good source

Andrew Zhu 0 Dec 8, 2021
A cargo subcommand that displays ghidra function output through the use of the rizin rz-ghidra project.

cargo-rz-ghidra A cargo subcommand that displays ghidra function output through the use of the rizin rz-ghidra project. Install cargo install --git ht

wcampbell 4 Nov 5, 2022
This utility traverses through your filesystem looking for open-source dependencies that are seeking donations by parsing README.md and FUNDING.yml files

This utility traverses through your filesystem looking for open-source dependencies that are seeking donations by parsing README.md and FUNDING.yml files

Mufeed VH 38 Dec 30, 2022