とてもやさしい関係・関数プログラミング入門

とてもやさしい関係・関数プログラミング入門

This tutorial will guide you through the magic and fun of combining relational programming (also known as logic programming) with functional programming. This tutorial does not assume that you have any knowledge of Lisp, Clojure, Java, or even functional programming. The only thing this tutorial assumes is that you are not afraid of using the command line and you have used at least one programming language before in your life.

このチュートリアルは魔法のようで面白い関係プログラミング（論理プログラミングとしても知られています）と関数プログラミングへとあなたを案内します。 このチュートリアルはあなたがLisp、Clojure、Javaの知識、さらには関数プログラミングの知識さえも持っていることを前提としていません。 このチュートリアルが前提としていることはあなたがコマンドラインを使うことを嫌がらないことと、今までの人生で少なくとも1つのプログラミング言語を使ったことがあることだけです。

作業中

This tutorial is very much a work in progress. It's possible to get through the first parts and learn something, but expect a considerable amount of fleshing out in the next couple of weeks.

このチュートリアルはまだまだ作業中です。 その前編を読み終えて何かを学ぶことはできますが、次の2、3週間のうちにかなりの量が追加されるであろうことは覚悟しておいてください。

なぜ論理プログラミングなのか

What's the point of writing programs in the relational paradigm? First off, aesthetics dammit.

関係パラダイムでプログラムを書くことの目的は何でしょう。 第一は、あの美学です。

Logic programs are simply beautiful as they often have a declarative nature which trumps even the gems found in functional programming languages. Logic programs use search, and thus they are often not muddied up by algorithmic details. If you haven't tried Prolog before, relational programming will at times seem almost magical.

論理プログラムは関数プログラミング言語の有する宝石にさえも勝る宣言的な性質を持っていることが多く、単純に美しいです。 論理プログラムは検索を用いるので、アルゴリズムの詳細によってごちゃごちゃしていないことが多いです。 もしあなたが以前Prologに挑戦したことがないのであれば、関係プログラミングはときどきほとんど魔法のように見えるでしょう。

However, I admit, the most important reason to learn the relational paradigm is because it's FUN.

しかしながら、関係パラダイムを学ぶ最も重要な理由はそれが「楽しい」からだ、ということは認めます。

第一歩

Ok, we're ready to begin. Type lein repl or cake repl, this will drop you into the Clojure prompt. First lets double check that everything went ok. Enter the following at the Clojure REPL:

はい、始める準備はできました。 lein replまたはcake replと入力すれば、Clojureのプロンプトに入ることができるでしょう。 最初にすべてがうまく動いていることを再確認しましょう。 Clojure REPLで次のコードを入力してください。

user=> (require 'clojure.core.logic)

The REPL should print nil and it should return control to you. If it doesn't file an issue for this tutorial and I'll look into it. If all goes well run the following:

REPLはnilを出力して制御をあなたに返すはずです。 もしそれがこのチュートリアルについての問題を記録していなければ私はそれを調査します。 もしすべてがうまく動いていれば次のコードを実行してください。

user=> (load "logic_tutorial/tut1")

You'll see some harmless warnings, then run the following:

あなたは無害な警告をいくつか見るでしょう。それから次のコードを実行してください。

user=> (in-ns 'logic-tutorial.tut1)

Your prompt will change and you're now working in a place that has the magic of relational programming available to you. The REPL prompt will show logic-tutorial.tut1, we're going show tut1 to keep things concise.

プロンプトは変わり、あなたが今作業をしているのは関係プログラミングの魔法を使うことのできる場所です。 REPLのプロンプトはlogic-tutorial.tut1を示していると思いますが、私達は簡略化のためにtut1と示すことにします。

質問と解答

Unlike most programming systems, with relational programming we can actually ask the computer questions. But before we ask the computer questions, we need define some facts! The first thing we want the computer to know about is that there are men:

多くのプログラミングシステムと異なり、関係プログラミングでは私達はコンピューターに本当に質問をすることができます。 しかしコンピューターに質問をする前に、私達はいくつかの事実を定義しなければなりません。 私達が最初にコンピューターに知ってほしいことは、世の中には男性というものが存在するということです。

tut1=> (defrel man x)
#'tut1/man

And then we want to define some men:

そして次に私達は何人かの男性を定義しなければなりません。

tut1=> (fact man 'Bob)
nil
tut1=> (fact man 'John)
nil

Now we can ask who are men. Questions are always asked with run or run*. By convention we'll declare a logic variable q and ask the computer to give use the possible values for q. Here's an example.

これで私達は誰が男性なのかを尋ねることができます。 質問にはいつもrunまたはrun*を使います。 慣習として私達は論理変数qを宣言してコンピューターにqの取り得る値を教えてくれるよう求めます。 次に例を示します。

tut1=>  (run 1 [q] (man q))
(John)

We're asking the computer to give us at least one answer to the question - "Who is a man?". We can ask for more than one answer:

私達はコンピューターに対して「誰が男性なのか」という質問への解答を1つだけ教えてくれるよう頼んでいます。 私達は2つ以上の解答を求めることもできます。

tut1=> (run 2 [q] (man q))
(John Bob)

Now that is pretty cool. What happens if we ask for even more answers?

さてこれは非常にクールです。 私達がもっと多くの解答を求めた場合にはどうなるのでしょうか。

tut1=> (run 3 [q] (man q))
(John Bob)

The same result. That's because we’ve only told the computer that two men exist in the world. It can't give results for things it doesn't know about. Let's define another kind of relationship and a fact:

同じ結果です。 なぜなら私達はコンピューターに世の中には2人の男性がいるとしか教えなかったからです。 コンピューターは知らないことについて解答することはできません。 他の種類の関係と事実を定義してみましょう。

tut1=> (defrel fun x)
#'tut1/fun
tut1=> (fact fun 'Bob)
nil

Let's ask a new kind of question:

新しい種類の質問をしてみましょう。

tut1=> (run* [q] (man q) (fun q))
(Bob)

There's a couple of new things going on here. We use run*. This means we want all the answers the computer can find. The question itself is formulated differently than before because we're asking who is a man and is fun. Enter in the following:

ここではいくつかの新しいことが起きています。 私達はrun*を使いました。 これは私達がコンピューターの見付けることのできるすべての解答を求めているということを意味します。 質問それ自身は前とは違う形で定式化されています。なぜなら私達は男性であり かつ 面白い人は誰なのかを尋ねているからです。 次のコードを入力してください。

tut1=> (defrel woman x)
#'tut1/woman
tut1=> (fact woman 'Lucy)
nil
tut1=> (fact woman 'Mary)
nil
tut1=> (defrel likes x y)
#'tut1/likes

Relations don't have to be a about a single entity. We can define relationship between things!

関係は1つの存在についてのものであってはいけません。 私達が定義できるのは存在と存在との間の関係です。

tut1=> (fact likes 'Bob 'Mary)
nil
tut1=> (fact likes 'John 'Lucy)
nil
tut1=> (run* [q] (likes 'Bob q))
(Mary)

We can now ask who likes who! Let's try this:

これで私達は誰が誰を好きなのかを尋ねることができます。 次のコードを試してみましょう。

tut1=> (run* [q] (likes 'Mary q))
()

Hmm that doesn't work. This is because we never actually said who Mary liked, only that Bob liked Mary. Try the following:

うーん、これは動きません。 これは私達が Maryが好意を抱いている人 についてはまったく言及しておらず、言及しているのはBobがMaryを好きだということだけだからです。 次のコードを試してみましょう。

tut1=> (fact likes 'Mary 'Bob)
nil
tut1=> (run* [q] (fresh [x y] (likes x y) (== q [x y])))
([Mary Bob] [Bob Mary] [John Lucy])

Wow that's a lot of new information. The fresh expression isn't something we've seen before. Why do we need it? By convention run returns single values for q which answer the question. In this case we want to know who likes who. This means we need to create logic variables to store these values in. We then assign both these values to q by putting them in a Clojure vector (which is like an array in other programming languages).

おお、たくさんの新しい情報が出てきました。 fresh式はこれまでに見たことがありません。 なぜこれが必要なのでしょうか。 慣習によりrunは質問への解答となる1つの値をqとして返します。 今回私達が知りたいのは誰が誰を好きなのかということです。 これは私達がそれらの複数の値を記憶しておくための論理変数を作らなければならないということを意味しています。 それから私達はそれらの値の両方をClojureのベクター（他のプログラミング言語における配列のようなもの）に入れてqに代入します。

Try the following:

次のコードを試してみましょう。

tut1=> (run* [q] (fresh [x y] (likes x y) (likes y x) (== q [x y])))
([Mary Bob] [Bob Mary])

Here we only want the list of people who like each other. Note that the order of how we pose our question doesn't really matter:

ここでは私達はお互い好き同士である人のリストだけを求めています。 私達がどのような順番で質問をしたかはまったく問題ではないことに注意してください。

tut1=> (run* [q] (fresh [x y] (likes x y) (== q [x y]) (likes y x)))
([Mary Bob] [Bob Mary])

いくつかの家系

We've actually predefined some interesting relations in the tut1 file that we'll try out first before we take a closer look:

私達は実際にいくつかの面白い関係をtut1ファイルの中で事前に定義しています。詳しく見る前にまずは試してみましょう。

tut1=> (fact parent 'John 'Bobby)
nil
tut1=> (fact male 'Bobby)
nil

We can now run this query:

これで私達はこの問い合わせを実行することができます。

tut1=> (run* [q] (son q 'John))
(Bobby)

Let's add another fact:

事実をもう一つ追加してみましょう。

tut1=> (fact parent 'George 'John) 
nil
tut1=> (run* [q] (grandparent q 'Bobby))
(George)

Huzzah! We can define relations in terms of other relations! Composition to the rescue. But how does this work exactly?

できました。 私達は他の関係を使って新しい関係を定義することができます。 合成のおかげです。 しかしこれは厳密にはどのように動いているのでしょうか。

Let's take a moment to look at what's in the file. At the top of the file after the namespace declaration you'll see that some relations have been defined:

ファイルに何が書いてあるのか、ちょっと見てみましょう。 ファイルの先頭の名前空間の宣言の後にいくつかの関係が定義されていることが分かるでしょう。

(defrel parent x y)
(defrel male x)
(defrel female x)

After this there are some functions:

その後にはいくつかの関数があります。

(defn child [x y]
  (parent y x))

(defn son [x y]
  (all
    (child x y)
    (male x)))

(defn daughter [x y]
  (all
    (child x y)
    (female x)))

We can define relations as functions! Play around with defining some new facts and using these relations to pose questions about these facts. If you're feeling particularly adventurous, write a new relation and use it.

私達は関係を関数として定義することができます。 いくつかの新しい事実を定義してそれらの事実についての質問をするためにそれらの関係を使って遊んでみましょう。 もしあなたがもっと冒険をしてみたいと思うのであれば、新しい関係を書いてそれを使ってみてください。

プリミティブ

Let's step back for a moment. core.logic is built upon a small set of primitives - they are run, fresh, ==, and conde. We're already pretty familiar with run, fresh, and ==. run is simple, it let's us run our logic programs. fresh is also pretty simple, it lets us declare new logic variables. == is a bit mysterious and we've never even seen conde before.

ちょっと後戻りしてみましょう。 core.logicは少数のプリミティブの上に成り立っています。それらはrun、fresh、==、condeです。 私達は既にrun、fresh、==についてはかなり知っています。 runは単純で、それは論理プログラムを実行（run）します。 freshも非常に単純で、それは新しい論理変数を定義します。 ==には少し謎があり、condeについてはこれまでに見たことがありません。

単一化

Earlier I lied about assignment when using the == operator. The == operator means that we want to unify two terms. This means we'd like the computer to take two things and attempt to make them equal. If logic variables occur in either of the terms, the computer will try to bind that logic variable to what ever value matches in the other term. If the computer can't make two terms equal, it fails - this is why sometimes we don't see any results.

以前==演算子を使ったときに私は代入について嘘を言いました。 ==演算子は2つの要素を単一化しなければならないということを意味します。 これは私達がコンピューターに2つのものを選んでそれらを等しくなるよう試みてもらうということを意味します。 もしどちらかの要素に論理変数が現れた場合、コンピューターはその論理変数を他の要素に合うすべての要素に束縛します。 もしコンピューターが2つの要素を等しくできなければ、単一化は失敗します。これが、私達がときどき1つも結果を得られなかった理由です。

Consider the following:

次のコードを検討してください。

tut1=> (run* [q] (== 5 5))
(_.0)

Whoa, what does that mean? It means that our question was fine, but that we never actually unified q with anything - _.0 just means we have a logic variable that was never bound to a concrete value.

おっと、これはどういう意味でしょうか。 これは私達の質問は正しいのですが、qを実際に何らかの値と単一化することができないということを意味します。_.0は単に私達が具体的な値に束縛することができない論理変数を持っているということを意味します。

tut1=> (run* [q] (== 5 4))
()

It's impossible to make 5 and 4 equal to each other, the computer lets us know that no successful answers exist for the question we posed.

5と4とを等しくすることは不可能であり、コンピューターは私達のした質問に対する正しい答えは存在しないということを知らせてくれます。

tut1=> (run* [q] (== q 5) (== q 5))
(5)
tut1=> (run* [q] (== q 5) (== q 4))
()

Once we've unified a logic variable to a concrete value we can unify it again with that value, but we cannot unify with a concrete value that is not equal to what it is currently bound to.

私達は一度論理変数を具体的な値に単一化した後にその値でもう一度単一化することができますが、今束縛されている値と等しくない具体的な値で単一化することはできません。

Here's an example showing that we can unify complex terms:

これは私達が複合的な要素を単一化することができることを示す例です。

tut1=> (run* [q] (fresh [x y] (== [x 2] [1 y]) (== q [x y])))
([1 2])

This shows that in order for the two terms [x 2] and [1 y] to be unified, the logic varialbe x must be bound to 1 and the logic variable y must be bound to 2.

これは2つの要素、[x 2]と[1 y]とを単一化するためには、論理変数xを1に束縛し論理変数yを2に束縛しなければならないということを示しています。

Note: it's perfectly fine to unify two variable to each other:

注意。2つの変数を互いに単一化することは問題なく可能です。

tut1=> (run* [q] (fresh [x y] (== x y) (== q [x y])))
([_.0 _.0])
tut1=> (run* [q] (fresh [x y] (== x y) (== y 1) (== q [x y])))
([1 1])

複数の世界

By now we're already familiar with conjuction, that is, logical and.

もう私達は結合、つまり、論理 積 については良く知っています。

(run* [q] (fun q) (likes q 'Mary))

We know now to read this as find q such that q is fun and q likes Mary.

私達は今これをqが面白くて かつ qがMaryを好きであるようなqを見付けよと読むことを知っています。

But how to express logical or?

しかし論理 和 はどのように表現するのでしょうか。

(run* [q]
  (conde
    ((fun q))
    ((likes q 'Mary))))

The above does exactly that - find q such that q is fun or q likes Mary. This is the essence of how we get multiple answers from core.logic.

上のコードはまさにqが面白いか または qがMaryを好きであるようなqを見付けよということになります。 これは私達がどのようにしてcore.logicから複数の解答を得るのかということの本質です。

手品

By now we're tired of genealogy. Let's go back to the cozy world of Computer Science. One of the very first things people introduce in CS are arrays and/or lists. It’s often convenient to take two lists and join them together. In Clojure this functionality exists via concat. However we're going to look at a relational version of the function called appendo. While appendo is certainly slower than concat it has magical powers that concat does not have.

もう私達は家系には飽きてしまいました。 親しみやすいコンピューター科学の世界に戻りましょう。 人々がコンピューター科学で最初の頃に紹介するのは配列および、またはリストです。 2つのリストを取ってそれらを結合することは便利なことが多いです。 Clojureにおいてこの機能はconcatとして存在しています。 しかしながら私達はappendoと呼ばれるその関数の関係プログラミング版を見てみようと思います。 appendoは確かにconcatより遅いのですがconcatの持っていない魔法の力を持っています。

First we'll want to load the next tutorial and switch into it's namespace.

まず私達は次のチュートリアルを読み込んでその名前空間に切り替えなければなりません。

Note: Since core.logic 0.6.3, appendo has been included in core.logic itself.

注意。core.logic 0.6.3以降では、appendoはcore.logic自体に取り込まれています。

tut1=> (in-ns 'user)
nil
user=> (load "logic_tutorial/tut2")
nil
user=> (in-ns 'logic-tutorial.tut2)
nil

Relational functions are written quite differently than their functional counterparts. Instead of return value, we usually make the final parameter be output variable that we'll unify the answer to. This makes it easier to compose relations together. This also means that relational programs in general look quite different from functional programs.

関係プログラミングの関数はその関数プログラミング版とはまったく違う形で書かれています。 値を返す代わりに、私達は通常最終的な引数を単一化の結果である出力値とします。 これは関係プログラムが一般的に関数プログラムとまったく異なって見えるということをも意味しています。

Open src/logic-tutorial/tut2.clj. You'll find the definition for appendo.

src/logic-tutorial/tut2.cljを開いてください。 appendoの定義が見付かるでしょう。

(defn appendo [l1 l2 o]
  (conde
    ((== l1 ()) (== l2 o))
    ((fresh [a d r]
       (conso a d l1)
       (conso a r o)
       (appendo d l2 r)))))

We can pass in logic variables in any one of it's three arguments.

私達は3つの引数のどれにでも論理変数を渡すことができます。

Now try the following:

では次のコードを試してください。

tut2=> (run* [q] (appendo [1 2] [3 4] q))
([1 2 3 4])

Seems reasonable. Now try this:

合っているように見えます。 ではこれを試してください。

tut2=> (run* [q] (appendo [1 2] q [1 2 3 4]))
([3 4])

Note that appendo can infer it's inputs!

appendoはその入力も推測できるということに注意してください。

There’s actually a short hand for writing appendo, we can write it like this. This is pattern matching - it can decrease the amount of boiler plate we have to write for many programs.

私達はこのように書くこともできますが、本当はappendoには簡略化した書き方があります。 それはパターンマッチングです。これにより私達が他の多くのプログラムで書かなければならない定型的な部分を書かずに済むのです。

ゼブラ

There's a classic old puzzle sometimes referred to as the Zebra puzzle, sometimes as Einstein's puzzle. Writing an algorithm for solving the constraint is a bit tedious - relational programming allows us to just describe the constraints and it can produce the correct answer for us.

ゼブラパズルまたはアインシュタインのパズルという名前でときどき言及される古典的なパズルがあります。 その制約を解決するためのアルゴリズムを書くことは少し退屈です。 関係プログラミングを使うと単に制約を記述するだけでそれが正しい解答を生成してくれます。

The puzzle is described in the following manner.

パズルは次の方法で記述されます。

If you look in src/logic_tutorial/tut3.clj you'll find the following code:

src/logic_tutorial/tut3.cljを見れば、次のコードが見付かるでしょう。

(defne righto [x y l]
  ([_ _ [x y . ?r]])
  ([_ _ [_ . ?r]] (righto x y ?r)))

(defn nexto [x y l]
  (conde
    ((righto x y l))
    ((righto y x l))))

(defn zebrao [hs]
  (macro/symbol-macrolet [_ (lvar)]
    (all
     (== [_ _ [_ _ 'milk _ _] _ _] hs)                         
     (firsto hs ['norwegian _ _ _ _])                         
     (nexto ['norwegian _ _ _ _] [_ _ _ _ 'blue] hs)       
     (righto [_ _ _ _ 'ivory] [_ _ _ _ 'green] hs)         
     (membero ['englishman _ _ _ 'red] hs)                    
     (membero [_ 'kools _ _ 'yellow] hs)                      
     (membero ['spaniard _ _ 'dog _] hs)                      
     (membero [_ _ 'coffee _ 'green] hs)                      
     (membero ['ukrainian _ 'tea _ _] hs)                     
     (membero [_ 'lucky-strikes 'oj _ _] hs)                  
     (membero ['japanese 'parliaments _ _ _] hs)              
     (membero [_ 'oldgolds _ 'snails _] hs)                   
     (nexto [_ _ _ 'horse _] [_ 'kools _ _ _] hs)          
     (nexto [_ _ _ 'fox _] [_ 'chesterfields _ _ _] hs))))

That is the entirety of the program. Let's run it:

これがプログラムのすべてです。 これを実行してみましょう。

tut3=> (run 1 [q] (zebrao q))
([[norwegian kools _.0 fox yellow] [ukrainian chesterfields tea horse blue] [englishman oldgolds milk snails red] [spaniard lucky-strikes oj dog ivory] [japanese parliaments coffee _.1 green]])

But how fast is it?

しかしこれはどれ位の速さで実行されるのでしょうか。

tut3=> (dotimes [_ 100] (time (doall (run 1 [q] (zebrao q)))))

On my machine, after the JVM has had time to warm up, I see the puzzle can be solved in as little as 3 milliseconds. The Zebra puzzle in and of itself is hardly very interesting. However if such complex constraints can be described and solved so quickly, core.logic is very likely fast enough to be applied to reasoning about types! Only time will tell, but I encourage people to investigate such applications.

私のマシンでは、JVMがウォームアップをするための時間を取った後、このパズルがわずか3ミリ秒で解かれることが分かりました。 ゼブラパズルはそれ自身とても面白いというものではありません。 しかしながらそのような複雑な制約を記述してこれほど速く解決できるのであれば、core.logicはおそらく型推論に用いることができるほど速いことになるでしょう。 時間だけが教えてくれるでしょうが、私は人々がそのような使い方を研究することを奨励します。

次のステップ

Hopefully this short tutorial has revealed some of the beauty of relational programming. To be sure, relational programming as I've presented here has its limitations. Yet, people are actively working on surmounting those limitations in more ways than I really have time to document here.

きっとこの短いチュートリアルは関係プログラミングの美しさを少しは明らかにしたことでしょう。 確かに、ここで私が示した関係プログラミングは限定されたものです。 ですが、人々は私がこの文書を書いているときよりももっと多くの方法でこれらの制限を乗り越えることに積極的に取り組んでいます。

While you can get along just fine as a programmer without using relational programming, many aspects of the tools we use today will seem mysterious without a basic understanding of how relational programming works. It also allows us to add features to our languages that are otherwise harder to implement. For example the elegant type systems (and type inferencing) found in Standard ML and Haskell would be fascinating to model via core.logic. I also think that an efficient predicate dispatch system that gives ML pattern matching performance with the open-ended nature of CLOS generic methods would be easily achievable via core.logic.

あなたは関係プログラミングを使うことなくプログラマーとして非常にうまくやっていますが、私達が今日使っているツールの多くの側面は関係プログラミングがどのように動くのかについての基本的な理解がなければ不可解に見えるでしょう。 関係プログラミングを使えば、そうでなければ実装することが困難であるような機能を言語に追加することができます。 例えばStandard MLとHaskellの有するすばらしい型システム（と型推論）を、 core.logic を使って作ることは魅力的でしょう。 私はまたCLOSの総称的なメソッドの自由な本質とともにMLにパターンマッチングの性能を与えた効率的な述語ディスパッチシステムも core.logic を使えば簡単に手に入れることができるとも考えています。

リソース

If you found this tutorial interesting and would like to learn more I recommend the following books to further you understanding of the relational paradigm.

もしあなたがこのチュートリアルを面白いと感じてもっと学びたいと思うのであれば、関係パラダイムをさらに理解するために次の本を私は勧めます。

• The Reasoned Schemer
• Paradigms of Artificial Intelligence Programming
• Prolog Programming For Artificial Intelligence
• Concepts, Techniques, and Models of Computer Programming