{"id":2620,"date":"2021-11-28T08:36:15","date_gmt":"2021-11-28T03:06:15","guid":{"rendered":"https:\/\/www.rangakrish.com\/?p=2620"},"modified":"2021-11-28T08:36:15","modified_gmt":"2021-11-28T03:06:15","slug":"understanding-the-unify-function-in-newlisp","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2021\/11\/28\/understanding-the-unify-function-in-newlisp\/","title":{"rendered":"Understanding the “unify” Function in “newLisp”"},"content":{"rendered":"

Unification<\/strong><\/em> between two symbolic expressions involves finding substitutions for variables (if any) in the expressions such that the expressions match<\/strong><\/em>\u00a0after applying the substitutions. This is a powerful idea and is quite common in logic programming languages such as Prolog<\/strong><\/em>.<\/p>\n

Interestingly, “newLisp”<\/strong><\/em> has a buil-in function called “unify”<\/strong><\/em><\/a> that can be used for unifying two expressions. In this article, let us go over several examples of this function.<\/p>\n

Let us start with a simple case involving atomic<\/strong><\/em> elements:<\/p>\n

\"Unifying<\/a>
Unifying “atomic” expressions<\/strong><\/figcaption><\/figure>\n

The “unify”<\/strong><\/em> function returns a “bindings”<\/strong><\/em> list, that is, a list of possible substitutions for the variables, if any. If the two expressions cannot be unified, it returns nil.\u00a0<\/span><\/p>\n

In the above case, there is a match only when the two expressions are identical<\/strong><\/em>. Since there are no variables in the expressions, if the match<\/strong><\/em> is successful, an empty list is returned.<\/p>\n

It gets interesting when we introduce one or more variables<\/strong><\/em> in the expressions. Variables start with an uppercase letter in order to distinguish them from other elements of the expression.<\/p>\n

\"Expressions<\/a>
Expressions with Variables<\/strong><\/figcaption><\/figure>\n

In the first case above, the variable “X”<\/strong><\/em> can be directly unified with the literal “Hi”<\/strong><\/em>. The third case shows that we can have variables in both expressions. The next four cases involve only variables, no literals. The reason the last case fails is because of mismatch between the number of elements in each expression.<\/p>\n

We can use the special symbol “_”<\/strong><\/em> as a variable to match any single element, but it does not get bound to what it matches. See the following examples:<\/p>\n

\"Using<\/a>
Using Underscore<\/strong><\/figcaption><\/figure>\n

As you can guess, the last two expressions fail because of mismatch in the number of elements.<\/p>\n

The “unify”<\/strong><\/em> function optionally takes a third parameter – a binding list. This is used as needed when unifying the first two expressions.\u00a0<\/span><\/p>\n

\"Passing<\/a>
Passing an Optional Bindings List<\/strong><\/figcaption><\/figure>\n

If the binding list includes variables other than those present in the first two expressions, then those are also included in the final list of bindings:<\/p>\n

\"Extra<\/a>
Extra Variables in the Bindings List<\/strong><\/figcaption><\/figure>\n

Here are some examples with “_”<\/strong><\/em> in the binding list (not a common scenario):<\/p>\n

\"Bindings<\/a>
Bindings List Contains “_”<\/strong><\/figcaption><\/figure>\n

The first fails because of inconsistent bindings. When the first two arguments unify, the bindings will be ‘((A 1) (B 2)). However, the third parameter forces ‘(A 10), which is different from ‘(A 1). This cannot be true and hence the unification fails.<\/p>\n

The remaining cases use “_”<\/strong><\/em> and hence there is no inconsistency. In the last case, the extra binding ‘(C _) is ignored because the variable “C”<\/strong><\/em> does not occur in the first two expressions and “_”<\/strong><\/em> is just a place holder with no concrete value.<\/p>\n

In practice, the third argument is often another “unify”<\/strong><\/em> expression, in which case, its result will be used as the binding list for the main\u00a0“unify”<\/strong><\/em>.<\/p>\n

\"Nested<\/a>
Nested “unify”<\/strong><\/figcaption><\/figure>\n

Do you see why the second case fails? It forces “P”<\/strong><\/em> and “Y”<\/strong><\/em> to take different bindings (due to the nested “unify”<\/strong><\/em>), and this cannot satisfy the unification of the first two expressions.<\/p>\n

I hope the functionality of “unify”<\/strong><\/em> in “newLisp”<\/strong><\/em> is reasonably clear from the discussion so far. Do check it out when you get time.<\/p>\n

Have a wonderful Thanksgiving weekend!<\/strong><\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Unification between two symbolic expressions involves finding substitutions for variables (if any) in the expressions such that the expressions match\u00a0after applying the substitutions. This is a powerful idea and is quite common in logic programming languages such as Prolog. Interestingly, “newLisp” has a buil-in function called “unify” that can be used for unifying two 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_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[297,17],"tags":[148,300],"class_list":["post-2620","post","type-post","status-publish","format-standard","hentry","category-newlisp","category-programming","tag-prolog","tag-unification"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-Gg","jetpack-related-posts":[{"id":2632,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/12\/12\/the-net-eval-function-in-newlisp\/","url_meta":{"origin":2620,"position":0},"title":"The “net-eval” Function in “newLisp”","author":"admin","date":"December 12, 2021","format":false,"excerpt":"One of the cool\u00a0things about \"newLisp\" is that despite its small fooprint, it comes with a lot of functionality built-in. For instance, if you are interested in distributed computing, it is pretty easy to get started. In this article, I will touch upon the net-eval function\u00a0that allows an expression to\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"Two Servers","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/12\/Servers-300x253.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2580,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/10\/17\/some-interesting-features-of-newlisp\/","url_meta":{"origin":2620,"position":1},"title":"Some Interesting Features of “newLisp”","author":"admin","date":"October 17, 2021","format":false,"excerpt":"newLisp is a general-purpose scripting language with a Lisp-like syntax. That is one of the reasons I wanted to take a closer look at the language. It has a compact footprint, small resource requirements, and can easily be embedded. It is available on multiple platforms, and on my Windows machine,\u2026","rel":"","context":"In "newLisp"","block_context":{"text":"newLisp","link":"https:\/\/www.rangakrish.com\/index.php\/category\/newlisp\/"},"img":{"alt_text":"\"amb\" Function","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/10\/example1.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2610,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/11\/14\/currying-in-newlisp\/","url_meta":{"origin":2620,"position":2},"title":"Currying in “newLisp”","author":"admin","date":"November 14, 2021","format":false,"excerpt":"In the last two articles, I discussed what I believe are some interesting features of \"newLisp\". Today's topic is \"currying\", another useful feature. For those of you who are new to this topic, I had earlier written about \"currying\" in Mathematica here. You may want to take a look at\u2026","rel":"","context":"In "newLisp"","block_context":{"text":"newLisp","link":"https:\/\/www.rangakrish.com\/index.php\/category\/newlisp\/"},"img":{"alt_text":"Example of Currying","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/11\/Example1-300x141.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2593,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/11\/01\/implicit-indexing-and-slicing-in-newlisp\/","url_meta":{"origin":2620,"position":3},"title":"Implicit Indexing and Slicing in “newLisp”","author":"admin","date":"November 1, 2021","format":false,"excerpt":"In traditional Lisp (Common Lisp), when evaluating an S-expression list, the first element in the \"functor\" position must be a function or valid operator. newLisp\u00a0relaxes this requirement and allows the first element to be a context symbol type, a list, an array, or an integer. For today's discussion, let us\u2026","rel":"","context":"In "newLisp"","block_context":{"text":"newLisp","link":"https:\/\/www.rangakrish.com\/index.php\/category\/newlisp\/"},"img":{"alt_text":"List Indexing","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/11\/list1-300x141.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":3573,"url":"https:\/\/www.rangakrish.com\/index.php\/2024\/12\/17\/using-prolog-to-solve-the-word-transformation-puzzle\/","url_meta":{"origin":2620,"position":4},"title":"Using Prolog to Solve the Word Transformation Puzzle","author":"admin","date":"December 17, 2024","format":false,"excerpt":"In today\u2019s article, I want to share an interesting word puzzle, and then show how to solve it in Prolog. Here is the puzzle: You are given two words of the same length. You have to transform the first word into the second word, by changing only one letter at\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/www.rangakrish.com\/index.php\/category\/programming\/"},"img":{"alt_text":"Our Dictionary","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2024\/12\/prolog1-300x280.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2922,"url":"https:\/\/www.rangakrish.com\/index.php\/2022\/10\/06\/why-learn-prolog\/","url_meta":{"origin":2620,"position":5},"title":"Why Learn Prolog?","author":"admin","date":"October 6, 2022","format":false,"excerpt":"There are several programming languages in use today and a simple google search will throw up interesting recommendations of a subset of these languages to learn, usually based on popularity ranking. As is expected, the popularity of a programming language varies over time and hence a language that was in\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/www.rangakrish.com\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/2620","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=2620"}],"version-history":[{"count":0,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/2620\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=2620"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=2620"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=2620"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}