-*- eval: (ispell-change-dictionary “english”) -*-
Conformist is a pattern matching library, that i started as a part of my CAS.
As a real programmer i don’t present realized features, i speaking about my plans.
- Pattern matching for S-expression with placeholders, like `:symbol`, `:list` and another.
- Flexible system of placeholders.
- Pattern grouping (see chapter “thoughts” in org-file).
Very simple library, but soon i will expand it.
matchp takes pattern as first argument and data for matching as second. Pattern can contain:
- Placeholders a special keywords, that describes type of symbol(s), that must be in the on position of placeholder.
- Concrete values.
conformist don’t have built-in placeholders collection, you can define it on your own.
Nothing interesting here at all.
(defsystem "conformist"
:description "conformist is a pattern matching library"
:version "0.1"
:author "Centrix14"
:license "GNU GPL v3"
:depends-on (:asdf)
:components ((:file "conformist")
(:file "placeholders" :depends-on ("conformist"))
(:file "matching" :depends-on ("conformist"))
))
(defsystem "conformist/examples"
:description "Examples for conformist library"
:depends-on (:asdf :conformist)
:components ((:file "examples")))Just a package description.
(defpackage :conformist
(:use :common-lisp)
(:export :matchp
:placeholderp
:define-placeholder
:redefine-placeholder
:remove-placeholder
:get-recognition-predicate
:get-shift-function
:*placeholders*))(defpackage :conformist-examples
(:use :common-lisp :conformist))As i already said matchp works with placeholders. Placeholder has to characteristics:
- Recognition predicate a function that returns
tif her argument matched specified placeholder. - Shift function is a function that returns number of elements that must be skipped in given sequence.
Recognition predicate and shift function stored in list that is a value for placeholder key.
(in-package :conformist)
(defvar *placeholders* (make-hash-table :test #'equal))I think that user mustn’t work with *placeholders* directly, so i give him a corresponding function.
(defun define-placeholder (placeholder recognition-predicate shift-function)
(if (gethash placeholder *placeholders*)
(format t "You try to redefine an existing placeholder~%")
(setf (gethash placeholder *placeholders*) (list recognition-predicate
shift-function))))Since we can add placeholders, we can remove them. This functionality provided by remove-placeholder.
(defun remove-placeholder (placeholder)
(if (gethash placeholder *placeholders*)
(remhash placeholder *placeholders*)
(format t "You try to remove unexisting placeholder~%")))Also we can redefine placeholders, so redefine-placeholder do it.
(defun redefine-placeholder (placeholder recognition-predicate shift-function)
(if (gethash placeholder *placeholders*)
(setf (gethash placeholder *placeholders*) (list recognition-predicate
shift-function))
(format t "You try to redefine unexisting placeholder~%")))All placeholders logic is implemented, but for further work we need some access functions.
First function in this group is a get-recognition-predicate, that returns recognition predicate for given placeholder.
(defun get-recognition-predicate (placeholder)
(values (first (gethash placeholder *placeholders*)) placeholder))Another function is get-shift-function and i think there is no need in any other words about it.
(defun get-shift-function (placeholder)
(values (second (gethash placeholder *placeholders*)) placeholder))placeholderp is a predicate that returns t if given value is a placeholder.
(defun placeholderp (data)
(if (gethash data *placeholders*)
t
nil))Ok, now we have basics of placeholders and can write a function that compares some data with given placeholder (we suppose that given placeholder is a real placeholder).
(defun does-placeholder-matches-data (placeholder data)
(funcall (get-recognition-predicate placeholder) data))If you ask me, why this code so simple and not flexible, i give an answer: this is a temporary solution, soon i will make it more complicated.
Well, now we can take chance on me (sorry for ABBA-speaking). Now we can describe matching mechanism. Here, we begin from the most simple function, that returns t, if some symbol a matches another symbol b.
(in-package :conformist)
(defun does-a-matches-b (a b)
(format t "~a ~a~%" a b)
(if (placeholderp a)
(does-placeholder-matches-data a b)
(equal a b)))As you can see this function uses does-placeholder-matches-data function of a is a placeholder, or just returns equivalence of symbols.
Following code is quite ugly but this version is much faster and more lightweight. It’s not the edge of optimization, but closer to it than previous code.
(defun matchp-unsafe (pattern data)
(let ((pattern-index 0)
(data-index 0)
(pattern-len (length pattern))
(data-len (length data)))
(loop while (and (< pattern-index pattern-len)
(< data-index data-len))
do
(let ((pattern-elm (elt pattern pattern-index))
(data-elm (elt data data-index)))
(if (listp pattern-elm)
(unless (matchp-unsafe pattern-elm data-elm)
(return-from matchp-unsafe nil))
(unless (does-a-matches-b pattern-elm data-elm)
(return-from matchp-unsafe nil)))
(if (placeholderp pattern-elm)
(setf data-index (funcall (get-shift-function pattern-elm)
data
data-index))
(incf data-index))
(incf pattern-index)))
t))At least, i define matchp function, as a safe version of unsafe mathcp.
(defun matchp (pattern data)
(if (and (listp pattern)
(listp data))
(matchp-unsafe pattern data)))Before we can use matching, we must add placeholders and function for them.
(in-package :conformist-examples)
(defun skip-one (data index)
(declare (ignore data))
(1+ index))
(defun skip-symbols (data index)
(format t "index: ~a~%" index)
(let ((elm (elt data index)))
(loop while (< index (length data)) do
(unless (symbolp elm)
(return-from skip-symbols index))
(setf elm (elt data index))
(incf index)))
(format t "skip: ~a~%" (1- index))
(1- index))
(defun add-placeholders ()
(map nil #'define-placeholder
(list :symbol :list :symbols)
(list #'symbolp #'listp #'symbolp)
(list #'skip-one #'skip-one #'skip-symbols)))
(defun remove-placeholders ()
(maphash (lambda (key value)
(declare (ignore value))
(remhash key *placeholders*))
*placeholders*))Current version of matchp is very simple. Here is an examples of usage (all of them returns t).
(defun test1 ()
(values
;; :list placeholder describes list
(matchp '(:list) '((1 2 3)))
;; :symbol placeholder describes one symbol
(matchp '(:symbol) '(a))
;; placeholders may be nested
(matchp '(:symbol (:symbol :list)) '(a (b (c d))))
;; you can mix placeholders and values
(matchp '(a :symbol (b :list c)) '(a / (b (1 2 3) c)))))
;; :symbols placeholder describes one or more symbols
(defun test2 ()
(matchp '(a :symbols) '(a b c d)))(defun make-tests ()
(add-placeholders)
(test1)
)- [X] Make
*placeholders*hash table - [X] Separate system to different files
- [ ] Add error system
- [ ] Add classes
- [ ] Add
:lists,:symbolsand:etcplaceholders - [X] Reduce recursion
- [ ] Add grouping
- [ ] Expand examples
How grouping must work? Generally, grouping provide a new list, that can be one-to-one matched to given.
Some examples.
Pattern: (:symbol :symbol) Data: (a b) Grouping: ((a) (b)) Pattern: (:list :list) Data: ((1 2 3) (a b c)) Grouping: (((1 2 3)) ((a b c))) Pattern: (:symbol :list) Data: (a (1 2 3)) Grouping: ((a) ((1 2 3))) Pattern: (:symbols) Data: (a b c) Grouping: ((a b c)) Pattern: (:lists) Data: ((1 2 3) (4 5 6)) Grouping: (((1 2 3) (4 5 6))) Pattern: (:symbols :lists) Data: (a b c (1 2 3) (4 5 6)) Grouping: ((a b c) ((1 2 3) (4 5 6)))