Pattern Matching with Optima Lisp Library

Written by on June 9, 2016 in LISP, Programming with 0 Comments

In the previous two posts, we looked at external tools and libraries that can be used along with Opusmodus for algorithmic composition. In this post, I want to introduce another interesting Lisp library called Optima.

Optima is a powerful library for pattern matching. Often, when we talk of pattern matching, the topic revolves around regular expressions. No doubt, regular expressions are quite powerful and are widely used. However, in the context of Lisp, we have one more possible use case, that of pattern matching within S-expressions. One of the best introductions to this can be found in the book Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp by Peter Norvig. The Lisp code used in the book is available here. It is a great place to start if you are new to S-expression pattern matching.

Optima is far more powerful and capable than the system described in PAIP. In this and the next few posts, I will walk you through its capabilities.

The main top-level matcher is the match macro:

match argument &body clauses

Here, the argument is matched against clauses. Each element of the clauses is of the type

(<pattern> . <action>)

If the argument matches the <pattern>, the corresponding <action> is evaluated and the value returned from match. <action> is an implicit progn.

Let us start by looking at a very simple example:

(match 1

       (0 “Zero”)

       (x (print x) (1+ x)))

In this example, argument is 1. There are two clauses. The first clause has a constant pattern of 0, and if it matches the incoming argument, then “Zero” is returned. In this case, the second clause pattern will match. It is a variable pattern and will match any argument. The <action> here is printing the matched value as bound to the variable x and then returning one plus that value. Notice that the clauses are tried in the given lexical order, and the first match causes the remaining clauses to be ignored. If the form (fail) is executed as part of any clause, then that clause is deemed to have failed.

(match 100 

       (100 (print “matches 100”) (fail))

       (x x))

In this case, the first pattern matches, but because the action invokes (fail), the first clause failed and the next clause is tried. Since the second pattern is a variable, it matches anything, and the value returned is whatever it matches (i.e., 100).

If no pattern matches the incoming argument, match returns nil. If you explicitly wish to handle the no match case, you can have the special pattern otherwise as the last pattern, which will match any argument.

(match 1

       (0 “Zero”)

       (2 2)

(otherwise -1))

This will return -1. Since the order of clauses is important and since otherwise matches everything, it usually makes sense to keep it in the last clause.

(match 2

       (0 “Zero”)

(otherwise -1)

       (2 2))

This will return -1 and not 2, even though the last clause is a better match. So watch out.

Instead of otherwise, since an unconstrained variable can match anything, you can have it as the last pattern as an escape clause. Even simpler is the use of the underscore character “_” which denotes an unnamed variable.

(match 1

       (0 “Zero”)

       (2 2)

(_ -1))

Simple Patterns

Let us look at examples of simple patterns involving numbers, symbols and strings.

(match 12.34

(x (values (round x))))

=> 12

Here, the variable pattern matches anything and the clause returns the rounded value.

(match “foobar”

((and (type string) x ) (format nil “Hello – ~A” x)))

=> “Hello – foobar”

Notice the use of and to combine multiple sub patterns, and also the type qualifier to specify the expected type of argument. Only if the argument is a string, the pattern will match, binding the variable x to the supplied argument. The action part of the clause essentially concatenates two strings, and this is the value returned from the clause and the match function.

(match 100 

((satisfies evenp) ‘even)

((satisfies oddp) ‘odd))

=> even

The satisfies pattern applies a predicate on the incoming argument to see if it is a valid match. Instead of a predefined predicate you can have a lambda as well.

(match 10

       ((satisfies (lambda (x) (and (> x 0) (< x 100)))) t))

=> t

Here the pattern checks if the given number is greater than zero and less than 100.

You can use not to check for the negation of a condition:

(match “hello”

       ((not (equal “hi”)) t))

=> t

Since the argument is “hello” and not “hi”, it succeeds and returns t.

In addition to and and not, we can also use or:

(match “hello”

       ((not (equal “hello”)) ‘hi)

       ((or (and (type string) (equal “hello”)) (equal “dear”)) t))

=> t

Here, the second clause pattern is satisfied.

Quite interesting, isn’t it? Well, there are many more pattern matching features in Optima. We will continue our discussion in the next post.

Bye, till then. Take care.

Tags: ,


If you enjoyed this article, subscribe now to receive more just like it.

Subscribe via RSS Feed

Leave a Reply

Your email address will not be published. Required fields are marked *