Exploring Prolog – day 1

Advanced Software Development assignment

Advanced Software Development (ASD for short) has an assignment which requires me to write a blog about me exploring a new programming paradigm besides the typical one thought at school (object-oriented).

We have the choice of picking one of the following five languages: Prolog, Scala, Erlang, Clojure and Haskell. Last year I picked Haskell with its functional programming paradigm, but due to time constraints, I couldn’t finish the assignment in time. Instead of trying something I’ve already done once, I thought I should pick something different and see what the other languages are like. Thus, I decided that this time around, I will look into Prolog.

The assignment consists of three parts:

  • Picking a language and paradigm (already done that)
  • Writing (IT) blog posts about my experiences and opinions related to this selected language and paradigm, while working my way through the Prolog chapter in the book “Seven Languages in Seven Weeks” by Bruce A. Tate (referred to as “the book” from now on). Conveniently enough, I already have this blog in a rather unknown corner of the internet I can use. At times, I will also try to compare various features of the language with the programming languages and paradigms I already know.
  • Defining a challenge befitting the selected language and paradigm and blogging my hardships and problems along with it.

Prolog

Prolog is a logic programming language. Various resources on the internet mention that it’s good for Natural Language Processing and Artificial Intelligence, but when I did a quick Google search on Prolog’s real world applications with the query “what can Prolog solve”, I most notably got puzzle-related results such as a Sudoku-solver. Admittedly, I could’ve worded that query better. For this assignment, I will use the same tool as the book uses: “GNU Prolog”.

The book mentions that data in Prolog is in the form of logical rules: facts, rules, queries.

A fact is a basic assertion about some world. This is the first time the book introduces the term “world”. I think another word for this could be “domain” or “context” or the likes. A rule is an inference about the facts in that world, while a query is a question about that world.

Example: likes

The book starts with a basic example:

Lines 1-3 are the “facts” while line 5 is a rule. Lines 1-3 define some very simple facts such as “wallace likes cheese” or “grommit likes cheese”.

I saved this as a .pl file and then double clicked it to run it in GNU Prolog, because during the installation, GNU Prolog associated .pl files with itself. After running the file, I had the option to give my own input because I see an input cursor blinking after the “| ?- ” characters in my Prolog console.

I inputted my query as the following: “likes(wallace, cheese)” but after hitting return, all that happened is my cursor jumping to a new line. Moments later, I noticed that I was missing a period at the end of the statement. I suppose the “.” means “end of statement”, so that the user can input statements in multiple lines. Once I got the query correct, I got a “yes” as output. Changing the parameters a bit (“cheese” to “cheesea” which is supposed to be a typo) gave me a “no”. Yes and no – synonyms for true and false in the programming world.

Lines 1-3 aren’t very exciting compared to line 5. There is a lot to say about line 5 which I’ll try to keep short. According to the book, the rule is called “friend/2” which is a shorthand for “friend with 2 parameters. X and Y are the parameters in this case, while “:-” probably is Prolog’s assignment characters. Then you see three blocks divided by commas: “\+(X = Y)”, “likes(X, Z)” and “likes(Y, Z)”. The book says that X and Y cannot be the same, which is what “\+” is for it seems.

As for the “likes”, I assume they’re like function calls which return a yes or no. When the results of these three blocks is a “yes”, then you get a “yes” as the output of “friend”. However: nowhere in the “friends” call you specify “Z”. This rule checks that if two persons like the same Z (thing), then they are friends. What Prolog does there is check every single fact with Wallace and Grommit and see if they have a matching object they like. For example, Wallace and Grommit like cheese. Therefore, “friend(wallace, grommit).” returns a “yes”. You don’t specify “cheese” anywhere, Prolog “just knows” that they both like cheese.

For the sake of experimentation, I changed line 5 to
“friend(X, Y) :- (X = Y)”
This should mean that a person is a friend with itself. When I called this as “friend(wallace, wallace).”, I got a “yes”. This confirmed to me that a negation indeed is written as a “\+”.

Interestingly enough, the code example can be visualized as a tree of some sorts:

Where an arrow out is the output. And if at some point one of the arrows contains “no”, then the block the arrow is pointing at would also output a “no”. I imagine this can go infinitely deep. To test this I changed the example a bit, which also could be represented with the following tree.

Example: food

The book proceeds to a second example related to food:

A food has a type, and a food has a flavor. You find out if the food has a given flavor by querying for: the food, and the flavor. What the function does is check if a given food’s type and a given flavor’s type match up.

The book introduces a new keyword: “What”, then proceeds to call the fact as following: “food_type(What, meat).” which returns a prompt from the console: “What = spam ?”. From this point on, I can press ; to go to the next alternative, or a to list all alternatives. Prolog is telling me that spam is meat, but that there are more. When I hit ; I see “sausage”. But this is all executed in a fact. What about a rule, in this case, “food_flavor”?

When I call “food_flavor(What, sweet).”, I’m essentially asking “what food is sweet?” Then I get the following results: “jolt” and “twinkie”. This is actually pretty interesting because Prolog finds out if a food is sweet by looking at the given flavor, then searches the given flavor by matching a flavor’s food type with the food in food_type.

I like how this wildcard-like variable is called “What” because you can almost make it a humanly readable inquiry: What food has a sweet food flavor?

Example: map coloring

The idea is that there are 3 colors: red, green and blue. Each state has a color but adjacent states may not have the same colors touching each other. So for example, Mississippi and Tennessee may not have the same color, or Alabama may not have the same color as its surrounding states. First all color combinations are defined in “different” as a fact. Same color combinations are not allowed. Calling this code:
“coloring(Alabama, Mississippi, Georgia, Tennessee, Florida).”
produces the following output:

Alabama = blue
Florida = green
Georgia = red
Mississippi = red
Tennessee = green ? ;

And 5 more combinations. The fact that it managed to find color combinations without any algorithm is something I have a hard time wrapping my mind around. All this code does is defining facts and rules and it manages to find all the alternatives. Yet I have a hard time understanding how the code really works, because the book doesn’t explain the code in-depth. Maybe figure it out later on when I have more experience.

Example: unification

This final example introduces a new character: the equals sign (“=”). In Java or C#, = is used to assign something to a variable (var x = 1). But in Prolog, it means “Find the values that make both sides match.” Calling:
“dorothy(lion, tiger, bear).”
produces the following output: “yes”. But calling:
“dorothy(One, Two, Three).” produces:
“One = lion
Three = bear
Two = tiger”

I suppose to “unify” one, two and three, Prolog ‘changes’ them into lion, tiger and bear, respectively. Same with X, Y, Z in dorothy – those three get changed into lion, tiger, bear when the rule is invoked. I guess that’s what is also happening at the map coloring example. The state names get mapped to red, green, blue, hence it output [State] = [Color]. It’s actually a unification output.

If I call:
“dorothy(One, Two, bear).” it only outputs:
“One = lion
Two = tiger”
There is no bear, as it’s already “the same”.

Self study

I shall put the solutions in a source code file, but document any challenges or problems I encounter below.

One thing I had to figure out is allowing values with spaces in them. To do this, I put the strings in double quotes, but I got a character array as the book name output rather than the book name itself. Then it dawned on me that I could also use single quotes and that indeed was the proper solution.

The book told me to make a genre table but it wasn’t put to use in any of the assignments, so I made an extra one which can also be found in the source file: “find all genres a specified instrument is used in”. It finds all the genres an instrument is used in, based on which musician used it.

Thoughts so far

Prolog is quite interesting so far. It is somewhat reminiscent of a database where you have a bunch of records and you can execute queries, yet something feels ‘different’ about it. I still can’t wrap my mind around the Map Coloring example. I know one way or another, unification is involved, but unfortunately the book doesn’t explain it very well. It felt like that example was there for the sake of glorifying Prolog like “look at the kind of complicated problems Prolog can solve!”.

Yet, I believe in Prolog’s power. In the self study of day 1, I added my own challenge where I find all genres a specified instrument is used in, which could be done in 2 lines of code or so. Compared to that, here’s the C# version I quickly put together.

Quite the difference, isn’t it? In Prolog I don’t need to define data structures or tie together two structures with an algorithm. Instead of that, all I need to do is define a rule.