Ben Nadel
On User Experience (UX) Design, JavaScript, ColdFusion, Node.js, Life, and Love.
I am the chief technical officer at InVision App, Inc - a prototyping and collaboration platform for designers, built by designers. I also rock out in JavaScript and ColdFusion 24x7.
Meanwhile on Twitter
Loading latest tweet...
Ben Nadel at cf.Objective() 2011 (Minneapolis, MN) with:

Seven Languages In Seven Weeks: Prolog - Day 1

Posted by Ben Nadel
Tags: Prolog

I have just started Prolog - the third language in Seven Languages in Seven Weeks by Bruce Tate. Ruby was a lot fun. The Io language was a lot of fun. Prolog, on the other hand, had me finishing my homework in an awful mood. I'll say it - I was downright angry by the time I got into bed last night. Luckily, there was a new Grey's Anatomy on my DVR, so I was able to level back out before trying to fall asleep.

I spent at least an hour to an hour and a half just trying to figure out how to run a Prolog program from a file. That's an hour and a half of my life that I'll never get back. Sure, I could figure out how to compile a knowledge base; but, as far as distributing the source code over several files, nothing that I did seemed to work. And, to make the matter even more frustrating, even after 40 years of existence, there seemed to be very few easily-Googlable examples for Prolog. Even the Io language had better online examples and that takes into account having to wade through all the completely irrelevant "I/O"-based results.

Breathe. Breathe.

Ok, I'm probably just frustrated that this language requires such a radically different way of thinking about programming. Thanks for letting me vent. I am sure that as the next few days go on, I'll start to feel more comfortable with Prolog. I get the feeling that the Prolog programs are perhaps just too interactive to be called from a file. Yes, you can define your knowledge base in a compiled file; but, when it comes to asking that knowledge base for information, maybe that's just something that must be done from the command line (gprolog in my case).

HW1: Make a simple knowledge base. Represent some of your favorite books and authors.

  • %-- List some books.
  • %-- -------------------------------------------------------- --%
  • book( 'Javascript Patterns' ).
  • book( 'Object-Oriented Javascript' ).
  • book( 'jQuery Enlightenment' ).
  • book( 'Secrets of the JavaScript Ninja' ).
  • book( 'Pro JavaScript Techniques' ).
  • book( 'jQuery In Action' ).
  •  
  •  
  • %-- List some authors.
  • %-- -------------------------------------------------------- --%
  • author( 'Stoyan Stefanov' ).
  • author( 'Cody Lindley' ).
  • author( 'John Resig' ).
  • author( 'Yehuda Katz' ).
  • author( 'Bear Bibeault' ).
  •  
  •  
  • %-- Relate authors to books.
  • %-- -------------------------------------------------------- --%
  • author_book( 'Stoyan Stefanov', 'Javascript Patterns' ).
  • author_book( 'Stoyan Stefanov', 'Object-Oriented Javascript' ).
  • author_book( 'Cody Lindley', 'jQuery Enlightenment' ).
  • author_book( 'John Resig', 'Secrets of the JavaScript Ninja' ).
  • author_book( 'John Resig', 'Pro JavaScript Techniques' ).
  • author_book( 'John Resig', 'jQuery In Action' ).
  • author_book( 'Yehuda Katz', 'jQuery In Action' ).
  • author_book( 'Bear Bibeault', 'jQuery In Action' ).
  •  
  •  
  • %-- Define a rule that says the two people are co-authors if
  • %-- they worked on the same book together (and that the are
  • %-- not the same person).
  • %-- -------------------------------------------------------- --%
  • coauthor( FirstAuthor, SecondAuthor ) :-
  • (FirstAuthor \= SecondAuthor),
  • author( FirstAuthor ),
  • author( SecondAuthor ),
  • author_book( FirstAuthor, SomeBook ),
  • author_book( SecondAuthor, SomeBook )
  • .
  •  
  •  
  • %-- Define a rule that says the two people are NOT co-authors
  • %-- if they have never been co-authors. Yeah, that's some solid
  • %-- logic there :) I'm just playing with nested rules.
  • %-- -------------------------------------------------------- --%
  • notCoauthor( FirstAuthor, SecondAuthor ) :-
  • (FirstAuthor \= SecondAuthor),
  • \+coauthor( FirstAuthor, SecondAuthor )
  • .

Here, I am providing some facts about books, authors, and the relationship between books and authors (ie. which authors wrote which books). I am also providing two rules about the relationship between authors. In the first, two authors are said to be coauthors if they have ever worked on the same book. In the second, two authors are said to be "not coauthors" if they have never worked on the same book.

The concept behind negated rules is one that I haven't fully understood yet. You'll notice in the second rule, I prefix the nested subgoal with the "\+" operator. This is a negation operator but I don't think it's purely a logical negation in the way that we're use to thinking about it. Rather, it has more to do with being able to not "prove" a given rule.

Here is the GNU Prolog definition of the "\+" operator:

\+ Goal succeeds if call(Goal) fails and fails otherwise. This built-in predicate gives negation by failure.

In general, I found the documentation to be less than useful. I think it explains language constructs in terms that are so new to me that I was not able to easily make sense of them. I often found myself thinking, "What the heck does that mean," after reading an explanation in the documentation. It also didn't help that the documentation contained no examples.

Once I had this knowledge base compiled, I went ahead and tested it to make sure that it was working. First, I queried the book facts:

| ?- book( WhatBooks ).
WhatBooks = 'Javascript Patterns' ? a
WhatBooks = 'Object-Oriented Javascript'
WhatBooks = 'jQuery Enlightenment'
WhatBooks = 'Secrets of the JavaScript Ninja'
WhatBooks = 'Pro JavaScript Techniques'
WhatBooks = 'jQuery In Action'

To query the knowledge base, you have to ask for variables - these are words that start with an uppercase letter, such as WhatBooks. Prolog will then return all the possible values for that variable.

| ?- author( Author ).
Author = 'Stoyan Stefanov' ? a
Author = 'Cody Lindley'
Author = 'John Resig'
Author = 'Yehuda Katz'
Author = 'Bear Bibeault'

You can test for truthfulness, such as "Did Cody Lindley author jQuery in Action":

| ?- author_book( 'Cody Lindley', 'jQuery In Action' ).
no

Or, you can query for the authors of a given book, such as jQuery In Action:

| ?- author_book( Authors, 'jQuery In Action' ).
Authors = 'John Resig' ? a
Authors = 'Yehuda Katz'
Authors = 'Bear Bibeault'

Facts were really easy to set up and test. Rules, on the other hand, were not so friendly. I tried to create a rule that determined if two people were coauthors. It does this by checking to make sure that they are:

  1. Not the same person.
  2. Are both authors.
  3. Have some book that they both authored.

This rule worked pretty well (even if I excluded the author(X) subgoals). I could both test two known values:

| ?- coauthor( 'John Resig', 'Yehuda Katz' ).
yes
| ?- coauthor( 'John Resig', 'Cody Lindley' ).
no

Or, I could query it for matching values:

| ?- coauthor( 'John Resig', Who ).
Who = 'Yehuda Katz' ? a
Who = 'Bear Bibeault'

The notCoauthor() rule, on the other hand, did not want to play nicely with me. Logically, I thought the rule was sound. Since the coauthor() rule was easily queried, I figured I could also easily query the "not" or "fail" of that rule. This, however, does no appear to be the case.

I could explicitly check two values:

| ?- notCoauthor( 'John Resig', 'Yehuda Katz' ).
no
| ?- notCoauthor( 'John Resig', 'Cody Lindley' ).
yes

But, I could not query for all matching values:

| ?- notCoauthor( 'John Resig', Who ).
no

Any attempt to ask for all people who were not coauthors with John Resig simply returned "no." I'm not sure why. I don't have enough of an understanding of the language to know why this query is failing.

HW2: Find all books in your knowledge base written by one author.

This output assumes that "hw1.pl" was compiled within the GNU Prolog console before the knowledge base was queried:

| ?- author_book( 'John Resig', Books ).
Books = 'Secrets of the JavaScript Ninja' ? a
Books = 'Pro JavaScript Techniques'
Books = 'jQuery In Action'

By asking Prolog to "Unify" the author_book() fact - that is, make it true on both sides - it has to return all the values for "Books" that make the rule true.

HW3: Make a knowledge base representing musicians and instruments. Also, represent musicians and their genre of music.

  • %-- List some musicians.
  • %-- -------------------------------------------------------- --%
  • musician( sarah ).
  • musician( gina ).
  • musician( fionna ).
  • musician( samantha ).
  • musician( felicity ).
  •  
  •  
  • %-- List some instruments.
  • %-- -------------------------------------------------------- --%
  • instrument( voice ).
  • instrument( piano ).
  • instrument( guitar ).
  • instrument( flute ).
  • instrument( bongos ).
  •  
  •  
  • %-- List some genres.
  • %-- -------------------------------------------------------- --%
  • genre( pop ).
  • genre( folk ).
  • genre( rock ).
  • genre( jazz ).
  • genre( classical ).
  •  
  •  
  • %-- Link musicians to instrucments.
  • %-- -------------------------------------------------------- --%
  • plays( sarah, voice ).
  • plays( sarah, guitar ).
  • plays( gina, guitar ).
  • plays( gina, voice ).
  • plays( fionna, flute ).
  • plays( samantha, voice ).
  • plays( samantha, bongos ).
  • plays( samantha, flute ).
  • plays( felicity, flute ).
  •  
  •  
  • %-- Link musicians to genres.
  • %-- -------------------------------------------------------- --%
  • targets( sarah, pop ).
  • targets( gina, pop ).
  • targets( gina, folk ).
  • targets( fionna, classical ).
  • targets( samantha, rock ).
  • targets( samantha, pop ).
  • targets( felicity, classical ).
  • targets( felicity, jazz ).
  •  
  •  
  • %-- Create a rule for guitarists.
  • %-- -------------------------------------------------------- --%
  • guitarist( Person ) :-
  • musician( Person ),
  • plays( Person, guitar )
  • .
  •  
  •  
  • %-- Create a rule for soulful musician.
  • %-- -------------------------------------------------------- --%
  • soulful_musician( Person ) :-
  • musician( Person ),
  • plays( Person, voice ),
  • plays( Person, guitar ),
  • targets( Person, folk )
  • .

As you can see, I am providing some facts about musicians, instruments, genres, and some rules about what makes someone a guitarist or a soulful musician. Once I had this knowledge base compiled, I wanted to test to make sure it was working:

| ?- musician( Who ).
Who = sarah ? a
Who = gina
Who = fionna
Who = samantha
Who = felicity

| ?- guitarist( Who ).
Who = sarah ? a
Who = gina

| ?- soulful_musician( Who ).
Who = gina ? a

Up until now, all of my queries have all been for a single fact or rule. Knowledge base queries, however, can also be compound; that is, queries can contain multiple subgoals. For example, my queries can check for both a rule and a fact:

| ?- soulful_musician( Who ), plays( Who, voice ).
Who = gina ? a
no
| ?- soulful_musician( Who ), plays( Who, flute ).
no

First, I am looking for soulful musicians who also play "voice." This result in "gina". Then, I query for soulful musicians who also play "flute." However, since there are no musicians that match both these constraints, Prolog simply returns with a "no."

When it comes to subgoals, the comma (,) between subgaols means "and". In the previous query, the comma meant soulful musician AND flutist. In a query, the semi-colon (;) means "or." We can rework the above query to look for musicians who are either soulful OR who are flutists:

| ?- soulful_musician( Who ); plays( Who, flute ).
Who = gina ? a
Who = fionna
Who = samantha
Who = felicity

As you can see, this found the single soulful musician - gina - and the three flutists - fionna, samantha, and felicity.

HW4: Find all musicians who play the guitar.

This output assumes that "hw3.pl" was compiled within the GNU Prolog console before the knowledge base was queried:

| ?- plays( Who, guitar ).
Who = sarah ? a
Who = gina

I started off this blog post with some belly-aching, so I don't want to end in the same way. Rather, I want to stay open minded about the next two days. I am sure that as Bruce Tate leads me into the depths of Prolog, I'll start to come around. More likely than not, my misgivings are nothing more than a result of Prolog's radical departure from a more "traditional" programming model.




Reader Comments

I remember doing some Prolog in a programming languages class in college. It didn't click for me until an assignment to write a differentiation function, and then told that "for bonus points" we should be able to integrate with the same function. The two-way nature of Prolog finally sold me on it, and even though I haven't touched it in years, I still have fond memories.

Reply to this Comment

@Andrew,

Now that I got all my gripes out this morning, your comment sounds promising. I'm really trying to keep an open mind here. I *do* think it is cool that you can solve problems in Prolog by simply describing them. I'm looking forward to getting my hands dirty, so to speak.

Reply to this Comment

Good write up Ben. It's good to know I wasn't the only one being tripped up by the negation operator. The wikipedia article http://en.wikipedia.org/wiki/Prolog#Negation has a short but terse explanation about its nature and the way I understand it is that the rules that contain the negation operator can not contain free variables because the interpreter can not guarantee you will get correct results so it errs on the safe side and just refuses to do anything.

Reply to this Comment

@David,

Thanks for the link. That clears it up... and by clears it up, I mean that I read the words and nodded as I read them :) I'm still trying to wrap my head around this stuff.

I just read Day 2 last night, but have not done the homework. Some of the recursion stuff with the [Head|Tail] of lists seems to take a pretty strong mental model to keep in tact. I hope that once I start playing around in the interpreter, it'll start to make more sense.

Reply to this Comment

@Ben,

I agree about the weird semantics. Unification as a computational strategy is making my head spin. I was looking at the list reversing assignment for day 2 and I had no idea how to go about it so I cheated and I'm glad I did because there is no way I would have figured out how to do it on my own. It really feels like I am learning to program all over again. It's a nice feeling.

Reply to this Comment

@David,

Wow, day 2 was demoralizing :) I was able to get the first two done, but the sorting was just impossible for me. I kept at it for like 2 hours before I just gave up. And, when I looked up a solution for Merge Sort, it became clear that I would have NEVER figured that out. Heck, even with the answer, it took me like an hour to translate that answer into my own style.

Prolog seems to make somethings easy and somethings very hard. Of course, I should acknowledge the fact that I have never been great at sorting in any language, even the ones that I am super comfortable with. I suppose it was never going to be easy in Prolog; but, the nature of the language appears to make it even harder.

Reply to this Comment

So you never figured out how to run a prolog program from a file?

Not trying to be annoying. Just curious.

Reply to this Comment

@Seth,

No, I gave up on that. I'm thinking that that's simply not how the language works. I can compile the knowledge base in a file; but I can't figure out how to include one file into another. Even as far as knowledge bases go, I could figure out how to include one knowledge base file into another.

There are constructs that seem to indicate that it is possible; but, nothing worked for me. Maybe it was my version of GNU Prolog? Not sure.

I gave up fighting. Started just compiling a single file and then querying it from the Prolog interpreter.

Reply to this Comment

The thought process does not seem too bad (though I have to admit that I have a decent background in AI - though with LiSP and Smalltalk - zero ProLog).

Anyway, this is the best I can do for executing a prolog "script." First, the script, factorial.pl:

  • % Factorial of 0 is 1
  • factorial(0, 1).
  • % Factorial of N is returned in Result
  • factorial(N, Result) :-
  • N > 0,
  • N1 is N - 1,
  • factorial(N1, Result1), % factorial of preceding number
  • Result is N * Result1. % N * factorial(N-1)
  •  
  • main :-
  • factorial(5, X),
  • write('factorial(5) is '),
  • write(X), nl,
  • halt.

Now, run the script...

  • shell -> gprolog --init-goal "consult('factorial.pl'), main"
  • compiling /home/jhagins/7days/Prolog/factorial.pl for byte code...
  • /home/jhagins/7days/Prolog/factorial.pl compiled, 15 lines read - 1281 bytes written, 5 ms
  • factorial(5) is 120

Note, however, that the interpreter output is also on stdout. I guess before loading the source, the "init" could dup stdout, then close it and have your stuff write to the "new" stdout...

Reply to this Comment

@Jody,

Dangy! You're like a super genius :) That's a pretty cool technique. I just like the idea of being able to hit the up-arrow to re-run the file again and again, as I edit it.

Reply to this Comment

Post A Comment

?
You — Get Out Of My Dreams, Get Into My Comments
Live in the Now
Oops!
Comment Etiquette: Please do not post spam. Please keep the comments on-topic. Please do not post unrelated questions or large chunks of code. And, above all, please be nice to each other - we're trying to have a good conversation here.