NON-optimized pattern matcher compatible with OPTIMA, with extensible optimizer interface and clean codebase

Upstream URL


Masataro Asai, Manfred Bergmann


  • news! new pattern: lambda-list pattern. Contributed by akssri
  • news! new pattern: number-related patterns, e.g. >, <, =, <= ...
  • news! Inline pattern implemented ! : @, @@ ...
  • news!(04/02/2016) Support for fare-quasiquote is now available. See test/quasiquote for the usage
  • news!(04/22/2016) Added metabang-bind like macros if-match, when-match, unless-match, let-match, let*-match, let-match1
  • news!(05/21/2016) Added support for minor implementations: CMU, ECL, CLISP, ABCL.
  • news!(05/22/2016) Implemented ARRAY, SIMPLE-ARRAY, ARRAY-ROW-MAJOR, ARRAY-ROW-MAJOR* patterns! Multi-dimentional arrays are now more handy!
  • news!(07/21/2016) Added READ, LAST, SPLIT, SPLIT* patterns! Parsing the string is more conveninent.
  • news!(01/21/2017) Added DYNAMIC pattern! Careful use of this pattern can impact the performance sensitive code.
  • news!(04/08/2017) Added a new contrib package TRIVIA.CFFI which provides -> pattern ! Offers convenient access to foreign objects.
  • news!(05/26/2018) Added property!, which only matches when the key is present in a plist.
  • news!(09/06/2018) SPLIT symbol was exported from the trivia.ppcre package.
  • news!(02/19/2019) Added MEMBER pattern. When the argument is a constant, it also adds type declaration.
  • news!(04/24/2019) Improved the compilation of GUARD pattern. It no longer uses the internal hackery.
  • news!(04/24/2019) Balland2006 optimizer is now the default optimizer for the pattern compiler!
  • news!(04/28/2019) Added a progv pattern, which can dynamically alter the dynamic variable the value will be bound to.
  • news!(05/08/2019) Now the optimizer can be specified in the lexical environment via (declare (trivia:optimizer <name>)) (e.g. (declare (trivia:optimizer :trivial))). Implemented through cltl2 API.
  • news!(10/11/2019) The OR1 consistency checking algorithm in Level 1 no longer takes the exponential runtime. Compilation of type-r library is now 10x faster! (patch from @pfdietz)
  • news!(01/01/2021) Added HASH-TABLE-ENTRY, HASH-TABLE-ENTRIES patterns, and corresponding ! suffixed patterns for matching only if key is present in hash table.
  • news!(05/30/2021 Added support for FSet. See tests for how-to.

1Trivia : Trivial Pattern Matching Compiler

Trivia is a pattern matching compiler that is compatible with Optima. It shares the same testing code with Optima and acts as a drop-in replacement for 99% usage. For the basic usage, consult our wiki. Known differences between Optima and Trivia, which are bug, are [[][described here]] (7/31/2016)

(defpackage :playwithit
  (:use :cl 
-       :optima))
+       :trivia))
(in-package :playwithit)

(match '(something #(0 1 2))
  ((list a (vector 0 _ b))
   (values a b)))
;; --> SOMETHING, 2

Patterns compiled with Trivia runs [[][faster than Optima]].

runtime [sec] fibonacci gomoku string-match
optima 11.5 39.8 82.5
trivia [1] 9.68 37.4 1.57

[1]: trivia is using :balland2006 optimiizer

... and Trivia is more extensible. In fact, Trivia's defpattern is able to implement all of unmodifiable, core pattern language in Optima within itself.

(defpattern cons (a b)
  (with-gensyms (it)
    `(guard1 (,it :type cons) (consp ,it) (car ,it) ,a (cdr ,it) ,b)))

Detailed documentation is in github wiki.

2Dependency & Testing

  • Level 0,1 : Alexandria only.
  • Level 2 : Additionally, lisp-namespace and closer-mop.

To run the tests, (asdf:test-system :trivia) .

To run the benchmark, (asdf:test-system :trivia.benchmark)

Dependencies (12)

  • alexandria
  • cffi
  • closer-mop
  • cl-ppcre
  • fare-quasiquote
  • fiveam
  • fset
  • iterate
  • lisp-namespace
  • optima
  • trivial-cltl2
  • type-i
  • GitHub
  • Quicklisp