{"id":256,"date":"2016-06-09T08:18:19","date_gmt":"2016-06-09T08:18:19","guid":{"rendered":"http:\/\/www.rangakrish.com\/?p=256"},"modified":"2016-06-09T11:06:00","modified_gmt":"2016-06-09T11:06:00","slug":"pattern-matching-with-optima-lisp-library","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2016\/06\/09\/pattern-matching-with-optima-lisp-library\/","title":{"rendered":"Pattern Matching with Optima Lisp Library"},"content":{"rendered":"

In the previous two posts, we looked at external tools and libraries that can be used along with Opusmodus<\/strong><\/a> for algorithmic composition. In this post, I want to introduce\u00a0another interesting Lisp library called Optima<\/strong><\/a>.<\/p>\n

Optima is a powerful library for pattern matching. Often, when we talk of pattern matching, the topic revolves around regular expressions<\/a>. No doubt, regular expressions are quite\u00a0powerful 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<\/strong><\/a> by Peter Norvig<\/strong>. The Lisp code used in the book is available here<\/a>. It is a great\u00a0place to start if you are new to S-expression pattern matching.<\/p>\n

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\u00a0its capabilities.<\/p>\n

The main top-level matcher is the match<\/strong><\/em> macro:<\/p>\n

match argument &body clauses<\/strong><\/em><\/p>\n

Here, the argument is matched against clauses. Each element of the clauses is of the type<\/p>\n

(<pattern> . <action>)<\/strong><\/em><\/p>\n

If the argument matches the <pattern><\/strong><\/em>, the corresponding <action><\/strong><\/em> is evaluated and the value returned from match<\/strong><\/em>. <action><\/strong><\/em> is an implicit progn<\/strong><\/em>.<\/p>\n

Let us start by looking at a very simple example:<\/p>\n

(match 1<\/strong><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 (0 “Zero”)<\/strong><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 (x (print x) (1+ x)))<\/strong><\/p>\n

In this example, argument<\/strong><\/em> is 1. There are two clauses. The first clause has a constant pattern of 0<\/strong><\/em>, and if it matches the incoming argument, then “Zero”<\/strong><\/em> is returned. In this case, the second clause pattern will match. It is a variable pattern and will match any argument. The <action><\/strong><\/em> here is printing the matched value as bound to the variable x<\/strong><\/em> and then returning one plus that value<\/em>. 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)<\/strong><\/em> is executed as part of any clause, then that clause is deemed to have failed.<\/p>\n

(match 100\u00a0<\/strong><\/em><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 (100 (print “matches 100”) (fail))<\/strong><\/em><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 (x x))<\/strong><\/em><\/p>\n

In this case, the first pattern matches, but because the action invokes (fail)<\/strong><\/em>, the first clause failed<\/strong> 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).<\/p>\n

If no pattern matches the incoming argument, match<\/strong><\/em> returns nil. If you explicitly wish to handle the no match<\/strong> case, you can have the special pattern otherwise<\/strong><\/em> as the last pattern, which will match any argument.<\/p>\n

(match 1<\/strong><\/em><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 (0 “Zero”)<\/strong><\/em><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 (2 2)<\/strong><\/em><\/p>\n

(otherwise -1))<\/strong><\/em><\/p>\n

This will return -1<\/strong><\/em>. Since the order of clauses is important and since otherwise<\/strong><\/em> matches everything, it usually makes sense to keep\u00a0it\u00a0in\u00a0the last clause.<\/p>\n

(match 2<\/strong><\/em><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 (0 “Zero”)<\/strong><\/em><\/p>\n

(otherwise -1)<\/strong><\/em><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 (2 2))<\/strong><\/em><\/p>\n

This will return -1<\/strong><\/em> and not 2<\/strong><\/em>, even though the last clause is a better match. So watch out.<\/em><\/p>\n

Instead of otherwise<\/strong><\/em>, 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 “_”<\/strong> which denotes an unnamed<\/em> variable.<\/p>\n

(match 1<\/strong><\/em><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 (0 “Zero”)<\/strong><\/em><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 (2 2)<\/strong><\/em><\/p>\n

(_ -1))<\/strong><\/em><\/p>\n

Simple Patterns<\/b><\/span><\/h2>\n

Let us look at examples of simple patterns involving numbers, symbols and strings.<\/p>\n

(match 12.34<\/strong><\/em><\/p>\n

(x (values (round x))))<\/strong><\/em><\/p>\n

=> 12<\/strong><\/em><\/p>\n

Here, the variable pattern matches anything and the clause returns the rounded value.<\/p>\n

(match “foobar”<\/strong><\/em><\/p>\n

((and (type string) x ) (format nil “Hello – ~A” x)))<\/strong><\/em><\/p>\n

=> “Hello – foobar”<\/strong><\/em><\/p>\n

Notice the use of and<\/strong><\/em> to combine multiple sub patterns, and also the type<\/strong><\/em> qualifier to specify the expected type of argument. Only if the argument is a string, the pattern will match, binding the variable x<\/strong><\/em>\u00a0to 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.<\/p>\n

(match 100\u00a0<\/strong><\/em><\/p>\n

((satisfies evenp) \u2018even)<\/strong><\/em><\/p>\n

((satisfies oddp) \u2018odd))<\/strong><\/em><\/p>\n

=> even<\/strong><\/em><\/p>\n

The satisfies<\/strong><\/em> 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.<\/p>\n

(match 10<\/strong><\/em><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 ((satisfies (lambda (x) (and (> x 0) (< x 100)))) t))<\/strong><\/em><\/p>\n

=> t<\/strong><\/em><\/p>\n

Here the pattern checks if the given number is greater than zero and less than 100.<\/p>\n

You can use not<\/strong><\/em> to check for the negation of a condition:<\/p>\n

(match “hello”<\/strong><\/em><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 ((not (equal “hi”)) t))<\/strong><\/em><\/p>\n

=> t<\/strong><\/em><\/p>\n

Since the argument is \u201chello\u201d<\/strong><\/em> and not \u201chi\u201d<\/strong><\/em>, it succeeds and returns t.<\/p>\n

In addition to and<\/strong><\/em> and not<\/strong><\/em>, we can also use or<\/strong><\/em>:<\/p>\n

(match “hello”<\/strong><\/em><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 ((not (equal “hello”)) \u2018hi)<\/strong><\/em><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 ((or (and (type string) (equal “hello”)) (equal “dear”)) t))<\/strong><\/em><\/p>\n

=> t<\/strong><\/em><\/p>\n

Here, the second clause pattern is satisfied.<\/p>\n

Quite interesting, isn’t it? Well, there are many more pattern matching features in Optima. We will continue our\u00a0discussion in the next post.<\/p>\n

Bye, till then. Take care.<\/p>\n","protected":false},"excerpt":{"rendered":"

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\u00a0another 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. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[18,17],"tags":[61,62],"class_list":["post-256","post","type-post","status-publish","format-standard","hentry","category-lisp","category-programming","tag-optima","tag-pattern-matching"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-48","jetpack-related-posts":[{"id":268,"url":"https:\/\/www.rangakrish.com\/index.php\/2016\/06\/29\/pattern-matching-with-optima-lisp-library-part-3\/","url_meta":{"origin":256,"position":0},"title":"Pattern Matching with Optima Lisp Library – Part 3","author":"admin","date":"June 29, 2016","format":false,"excerpt":"In the previous two posts on this topic, I explained some of the basic pattern matching facilities of Optima\u00a0library. There are many\u00a0more advanced features in the library and I will try to discuss them in future posts. In today\u2019s post, I will outline a straightforward application of the library for\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"Optima Example","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2016\/06\/Optima-Example-1024x622.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2016\/06\/Optima-Example-1024x622.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2016\/06\/Optima-Example-1024x622.png?resize=525%2C300 1.5x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2016\/06\/Optima-Example-1024x622.png?resize=700%2C400 2x"},"classes":[]},{"id":263,"url":"https:\/\/www.rangakrish.com\/index.php\/2016\/06\/17\/pattern-matching-with-optima-lisp-library-part-2\/","url_meta":{"origin":256,"position":1},"title":"Pattern Matching with Optima Lisp Library – Part 2","author":"admin","date":"June 17, 2016","format":false,"excerpt":"Let us continue where we left off last time. List Patterns If the incoming argument is a list, then we can use two types of list patterns to match the list elements, namely, list and list*. (match '(a b c)\u00a0 ((list 'a 'b X) X)) => c This list pattern\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2377,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/04\/12\/book-review-programming-algorithms-in-lisp\/","url_meta":{"origin":256,"position":2},"title":"Book Review: Programming Algorithms in Lisp","author":"admin","date":"April 12, 2021","format":false,"excerpt":"Title: Programming Algorithms in Lisp: Writing Efficient Programs with Examples in ANSI Common Lisp Author: Vsevolod Domkin Publisher: Apress Year: 2021 It is only about 5 months since I read and reviewed\u00a0a good book on Lisp written by Micha\u0142 \u201cphoe\u201d Herda. The present book is by Vsevolod Domkin\u00a0and I purchased\u2026","rel":"","context":"In "Book Review"","block_context":{"text":"Book Review","link":"https:\/\/www.rangakrish.com\/index.php\/category\/book-review\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/04\/Book-Cover-209x300.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2927,"url":"https:\/\/www.rangakrish.com\/index.php\/2022\/10\/20\/why-learn-lisp\/","url_meta":{"origin":256,"position":3},"title":"Why Learn Lisp?","author":"admin","date":"October 20, 2022","format":false,"excerpt":"In the last article, I had shared my views on why programmers should learn Prolog, preferably as the first language. What language should one learn next? I strongly pitch for Lisp, to be precise, \u201cCommon Lisp\u201d. Lisp happens to be the second oldest (1958) programming language, only after Fortran (1957)!\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":3312,"url":"https:\/\/www.rangakrish.com\/index.php\/2024\/01\/28\/the-hy-programming-language\/","url_meta":{"origin":256,"position":4},"title":"The Hy Programming Language","author":"admin","date":"January 28, 2024","format":false,"excerpt":"In an earlier article\u00a0I had explained how to execute Python code from within Common Lisp using \u201cCLPython\u201d package. In contrast to that approach, \u201cHy\u201d\u00a0is a Lisp-style language (not compatible with Common Lisp) that is embedded in Python and hence provides seamless interoperability with Python code. Installation is straightforward (it is\u2026","rel":"","context":"In "Hy Language"","block_context":{"text":"Hy Language","link":"https:\/\/www.rangakrish.com\/index.php\/category\/hy-language\/"},"img":{"alt_text":"Hy REPL","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2024\/01\/console-300x148.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2084,"url":"https:\/\/www.rangakrish.com\/index.php\/2020\/08\/16\/pattern-matching-comparing-elixir-and-mathematica\/","url_meta":{"origin":256,"position":5},"title":"Pattern Matching: Comparing Elixir and Mathematica","author":"admin","date":"August 16, 2020","format":false,"excerpt":"One of the things I like about Elixir\u00a0is its support for patterns at the core language level, not through library functions as in most other languages. This contributes to writing cleaner code, in my opinion. \u00a0 Another environment that I am familiar with, namely Mathematica, boasts of (arguably) the most\u2026","rel":"","context":"In "Elixir"","block_context":{"text":"Elixir","link":"https:\/\/www.rangakrish.com\/index.php\/category\/elixir\/"},"img":{"alt_text":"Symbolic Expressions","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2020\/08\/pattern-mm.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2020\/08\/pattern-mm.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2020\/08\/pattern-mm.png?resize=525%2C300&ssl=1 1.5x"},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/256","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/comments?post=256"}],"version-history":[{"count":0,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/256\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=256"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=256"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=256"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}