{"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_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_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},"jetpack_post_was_ever_published":false},"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":2057,"url":"https:\/\/www.rangakrish.com\/index.php\/2020\/07\/19\/calling-lisp-functions-from-elixir\/","url_meta":{"origin":256,"position":5},"title":"Calling Lisp Functions from Elixir","author":"admin","date":"July 19, 2020","format":false,"excerpt":"In the last article\u00a0I showed how we can simulate the idea of Lisp's \"closure\" in Elixir. Today, I would like to demonstrate how we can call Lisp functions from Elixir using the NIF interface. What is the need to integrate Elixir with another language? I can think of two reasons:\u2026","rel":"","context":"In "Elixir"","block_context":{"text":"Elixir","link":"https:\/\/www.rangakrish.com\/index.php\/category\/elixir\/"},"img":{"alt_text":"Using the Lisp Functions","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2020\/07\/Session.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2020\/07\/Session.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2020\/07\/Session.jpg?resize=525%2C300&ssl=1 1.5x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2020\/07\/Session.jpg?resize=700%2C400&ssl=1 2x"},"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}]}}