dumaiu/trivia

Pattern Matcher Compatible with Optima

• 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.

Trivia : 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.

Dependency & 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)

trivia's Issues

`:trivia` doesn't export `assoc`

As a pattern keyword, it should be accessible at least, and probably reexported from :cl.

Allow recursive pattern-matching in `alist` pattern keys

From derived.lisp, we have:

(defpattern alist (&rest args)
  "alist and plist patterns expand into a collection of assoc and property patterns, respectively, connected
by an and pattern.  Example: (alist (:key1 . _) (:key2 . value))"
  `(and ,@(mapcar (lambda-match0
                    ((cons key pattern)
                     `(assoc ,key ,pattern)))
                  args)))

It'd be preferable to be able to write the pattern to pass a :test arg to (assoc).

A way to capture the residual, unspecified elements of `alist`, `plist`, or `assoc` patterns

With, for instance, alist* | plist* patterns which, in imitation of list*, would expect an aggregating rest parameter as last place:

(alist* ('foo . foo) ... *rest)

• For assoc, which has keyword parameters, perhaps add :rest?
• TODO: What about duplicates? In this example:

(match '((foo . 1) (bar . 2) (foo . 3))
  ((alist* ('foo . foo) *rest)
    ...))

would *rest be bound to

'((bar . 2) (foo . 3))

or

'((bar . 2))

?