Seamless Deductive Inference via Macros

Arash Sahebolamri, Thomas Gilray, Kristopher Micinski

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present an approach to integrating state-of-Art bottom-up logic programming within the Rust ecosystem, demonstrating it with Ascent, an extension of Datalog that performs well against comparable systems. Rust's powerful macro system permits Ascent to be compiled uniformly with the Rust code it's embedded in and to interoperate with arbitrary user-defined components written in Rust, addressing a challenge in real-world use of logic programming languages: The fact that logical programs are parts of bigger software systems and need to interoperate with other components written in imperative programming languages. We leverage Rust's trait system to extend Datalog semantics with non-powerset lattices, much like Flix, and with user-defined data types much like Formulog and Souffle. We use Ascent to re-implement the Rust borrow checker, a static analysis required by the Rust compiler. We evaluate our performance against Datafrog, Flix, and Souffle using the borrow checker and other benchmarks, observing comparable performance to Datafrog and Souffle, and speedups of around two orders of magnitude compared to Flix.

Original languageEnglish (US)
Title of host publicationCC 2022 - Proceedings of the 31st ACM SIGPLAN International Conference on Compiler Construction
EditorsBernhard Egger, Aaron Smith
PublisherAssociation for Computing Machinery, Inc
Pages77-88
Number of pages12
ISBN (Electronic)9781450391832
DOIs
StatePublished - Sep 19 2022
Event31st ACM SIGPLAN International Conference on Compiler Construction, CC 2022 - Virtual, Online, Korea, Republic of
Duration: Apr 2 2022Apr 3 2022

Publication series

NameCC 2022 - Proceedings of the 31st ACM SIGPLAN International Conference on Compiler Construction

Conference

Conference31st ACM SIGPLAN International Conference on Compiler Construction, CC 2022
Country/TerritoryKorea, Republic of
CityVirtual, Online
Period4/2/224/3/22

Keywords

  • Ascent
  • Datalog
  • Logic Programming
  • Program Analysis
  • Rust
  • Static Analysis

ASJC Scopus subject areas

  • Hardware and Architecture
  • Signal Processing
  • Software

Fingerprint

Dive into the research topics of 'Seamless Deductive Inference via Macros'. Together they form a unique fingerprint.

Cite this