repository·master·Indexed 18 days ago
https://github.com/guicho271828/triviaA pattern matching compiler for Common Lisp designed as a drop-in replacement for Optima. It includes the Trivia.Balland2006 optimizer, which reduces conditional tests through Fusion, Interleaving, and Swapping transformations. The library supports custom pattern definitions via `defpattern` and provides a configurable optimization system.
Trivia.Balland2006 implementation focuses on reducing the number of conditional checks (tests) in pattern matching compilation, as these often involve costly function calls. While the original Balland (2006) paper also addresses assignment optimization (like Constant Propagation or Let-Fusion), this implementation skips those because modern Common Lisp implementations (SBCL, CCL) handle them automatically. Instead, it focuses on three primary transformation rules: Fusion, Interleaving, and Swapping.Fusion reduces redundant tests by identifying common checks across different match clauses. If multiple clauses share a common predicate (e.g., both check if a variable is a cons), the optimizer merges these into a single check and then uses a nested match* to handle the specific differences in the subsequent branches.
;; Original: Two clauses both checking (consp it)
(match1 what
((guard1 it (consp it) (car it) (guard1 x (= 1 x)) (cdr it) (guard1 y (null y))) body1)
((guard1 it (consp it) (car it) (guard1 x (stringp x)) (cdr it) (guard1 y (null y))) body2))
;; Optimized: One (consp it) check, then nested match*
(match what
((guard1 it (consp it) (car it) #:car (cdr it) #:cdr)
(match* (#:car #:cdr)
(((guard x (= 1 x)) (guard y (null y))) body1)
(((guard x (stringp x)) (guard y (null y))) body2))))Interleaving optimizes matches when the predicates form an exhaustive partition of a type. For example, if a variable is known to be a list, and the clauses check for cons and null, the optimizer can replace the second check with a wildcard _ because if it isn't a cons, it must be null.
;; Original: Explicitly checking both cons and null
(match1 what
((guard1 it (consp it)) body1)
((guard1 it (null it)) body2))
;; Optimized: Using a wildcard for the exhaustive case
(match1 what
((guard1 it (consp it)) body1)
(_ body2))You can execute the system's test suite and benchmark suite using ASDF commands.
To run tests:
(asdf:test-system :trivia)To run benchmarks:
(asdf:test-system :trivia.benchmark)Trivia is a pattern matching compiler compatible with Optima. It is designed to act as a drop-in replacement for 99% of Optima's usage, often providing better performance. To switch from Optima to Trivia, update your package definition to use :trivia instead of :optima.
(defpackage :playwithit
(:use :cl
:trivia)) ; Changed from :optima
(in-package :playwithit)
(match '(something #(0 1 2))
((list a (vector 0 _ b))
(values a b)))
;; --> SOMETHING, 2The Balland2006 optimizer is the default. However, you can specify a different optimizer in the lexical environment using a declare form with the trivia:optimizer keyword.
(declare (trivia:optimizer :trivial))*trace-optimization* flag can be used to enable debug printing during the fusing and grounding operations of the optimizer. This is useful for inspecting how pattern matching rules are being applied.*trace-optimization*Trivia is highly extensible. You can use defpattern to implement your own patterns. Trivia's defpattern is powerful enough to implement the entire unmodifiable core pattern language of Optima within itself.
(defpattern cons (a b)
(with-gensyms (it)
`(guard1 (,it :type cons) (consp ,it) (car ,it) ,a (cdr ,it) ,b)))