Skip to main content

Learning Prolog

I'm not quite sure exactly I was searching for, but somehow I serendipitously stumbled upon the site learnprolognow.org a few months ago. It's the home for an introductory Prolog programming course. Logic programming offers an interesting way to think about your problems; I've been doing so much procedural and object-oriented programming in the past decade that it really took effort to think at a higher level!

I found the most interesting features to be definite clause grammars (DCG), and unification. Difference lists are very powerful and Prolog's DCG syntax makes it easy to work with them. Specifying a grammar such as:
s(s(NP,VP)) --> np(NP,X,Y,subject), vp(VP,X,Y).

np(np(DET,NBAR,PP),X,Y,_) --> det(DET,X), nbar(NBAR,X,Y),
  pp(PP).
np(np(DET,NBAR),X,Y,_) --> det(DET,X), nbar(NBAR,X,Y).
np(np(PRO),X,Y,Z) --> pro(PRO,X,Y,Z).

vp(vp(V),X,Y) --> v(V,X,Y).
vp(vp(V,NP),X,Y) --> v(V,X,Y), np(NP,_,_,object).

nbar(nbar(JP),X,3) --> jp(JP,X).

pp(pp(PREP,NP)) --> prep(PREP), np(NP,_,_,object).

jp(N,X) --> n(N,X).
jp(jp(ADJ,JP),X) --> adj(ADJ), jp(JP,X).

det(det(DET),X) --> [DET], {lex(DET,det,X)}.

pro(pro(PRO),X,Y,Z) --> [PRO], {lex(PRO,pro,X,Y,Z)}.

v(v(V),X,Y) --> [V], {lex(V,v,X,Y)}.

prep(prep(PREP)) --> [PREP], {lex(PREP,prep)}.

n(n(N),X) --> [N], {lex(N,n,X)}.

adj(adj(ADJ)) --> [ADJ], {lex(ADJ,adj)}.
allows me to parse a statement for grammatical correctness, produce a parse tree, and determine where the point of failure is if it isn't grammatical.
?- s(X,[the,man,shoots,he],Y).
X = s(np(det(the), nbar(n(man))), vp(v(shoots))),
Y = [he]
The power of unification is highlighted by the append/3 predicate, a "function" whose primary purpose is to concatenate two lists. By providing partial lists and pattern structures, append can not only be used to concatenate, but also split a list, double it, and even test an element for membership.
is_member(X,Y) :- append(_,[X|_],Y).
?- is_member(4,[1,2,3,4,5]).
Yes
I have to say working through the course has made me a better programmer. It exposed me to new ways of thinking about old problems which broadened my "programmer toolset." I feel more comfortable working with immutable variables and recursion, too-- both concepts which I knew but subconsciously shied away from.

One of the difficulties of self-study though is the lack of teacher and classmates to ask questions and verify solutions. I purchased the printed version of the course to check my work but was dismayed to see it only contains answers for the chapter exercises. I've decided to make my solutions to the practical sections available for other self-learners.

I definitely recommend setting aside some spare time and working your way through the course if you haven't been exposed to Prolog somewhere in your studies or career already.
Labels:

Comments

  1. Tiago CavaleiroJanuary 17, 2011 at 2:36 PM

    Thank you very much. I couldn't find the solutions anywhere.

    ReplyDelete
  2. Timothy BoronczykJanuary 17, 2011 at 8:24 PM

    You're welcome. Good luck with your studies!

    ReplyDelete
  3. AnonymousMarch 14, 2011 at 7:41 AM

    Thanks for the solutions, you did the world a favor! :]

    ReplyDelete
  4. DanielApril 15, 2011 at 8:09 AM

    Thanks a ton for your solutions to the practical sessions!

    ReplyDelete
  5. AnonymousApril 24, 2011 at 7:46 PM

    You are a god among men, a man among mice, a mouse among inferior creatures!

    ReplyDelete
  6. kishore1November 17, 2011 at 4:54 AM

    inv (List1, ResultingList).
    inv ([2 , 1 , 0 , 0.25 ] , R).
    R = [ 0.5, 1, inf, 4.0 ]. % 1/2 = 0.5, 1/1 = 1, etc.

    ReplyDelete
  7. AnonymousDecember 7, 2011 at 2:24 PM

    super thanks!!

    ReplyDelete
  8. ProfVersaggiMarch 24, 2012 at 7:38 PM

    A BIG thank you from the Netherlands! You've just made my learning experience a lot better! :-)

    ReplyDelete
  9. AnonymousApril 18, 2012 at 9:02 AM

    thanks man >>A BIG thank you from EGYPT
    will bw happe to connect u

    ReplyDelete
  10. AnonymousApril 21, 2012 at 8:00 AM

    Thank you so much! I'm struggling to write my project for school and this'll help me so much =) Prolog looks awesome!! Greetings from Turkey =)

    ReplyDelete
  11. AnonymousOctober 4, 2012 at 8:32 PM

    I have also started working through LPN, and I found an interesting hitch in the Chapter 4 Practical section, specifically under Section 4.5.

    mysubset/2, as it stands, will give a positive match for mysubset([a,a],[a]), even though technically [a,a] is not a subset of [a]. Noting this, my solution rewrites member/2 such that it removes the matched element and returns the rest in a third argument.

    % member_rem(member, list, giveback).
    member_rem(X, Y) :- member_rem(X, Y, _) % member_rem/2 acts like member/2
    member_rem(H, [H|T], T).
    member_rem(X, [Y|Ys], [Y|G]) :- member_rem(X, Ys, G).
    % mysubset_rem(subset, superset).
    mysubset_rem([], _).
    mysubset_rem([X|Xs], Y) :- member_rem(X, Y, G), mysubset_rem(Xs, G).
    % mysuperset_rem(superset, subset).
    mysuperset_rem(X, Y) :- mysubset_rem(Y, X).

    For those who need a commentary: the "giveback" in member_rem/3 is another variable that is kept until member_rem matches the first case, after which it 'returns'--in massive quotes because I am an imperative programmer to the death--the tail of that list, i.e. missing the head element.

    I'm sure that the writers of the book probably meant the same solution that you got, which I had found as well, but I just think it's interesting that it should be deficient in such a subtle way.

    ReplyDelete
  12. AnonymousNovember 18, 2012 at 4:40 PM

    Thank you so much! You made my day!

    ReplyDelete
  13. AnonymousDecember 23, 2012 at 5:25 PM

    Thanks!

    ReplyDelete
  14. Confused GuyMarch 13, 2013 at 10:07 AM

    Excellent. Thanks for this. I'm working my way through the course online and I was looking for the solutions.

    ReplyDelete
  15. AnonymousAugust 20, 2013 at 6:07 AM

    Thanks from France :)

    ReplyDelete
  16. UnknownNovember 13, 2013 at 6:29 PM

    Thank you very much !!!! You really help interested students :)

    ReplyDelete
  17. fei erDecember 1, 2013 at 1:01 AM

    In the Learn Prolog Now book, 3.4 practical session question 2, if the user wants to count the number of transit and find all the possible traveling routes by type of vehicle.
    How to do? Thanks.

    ReplyDelete
  18. AnonymousJune 9, 2014 at 11:26 AM

    where are the solutions?

    ReplyDelete
  19. GilliamJanuary 7, 2015 at 2:18 PM

    Big thanks from Belgium ;)

    ReplyDelete
  20. AnonymousApril 8, 2015 at 12:16 PM

    Thank you so much!!! I was struggling especially with 3.4 practical session (travel(valmont, losAngeles,X) problem. Very kind of you to share this knowledge with the rest of us.
    Greetings from Greece,
    Christos G.

    ReplyDelete
  21. AnonymousAugust 10, 2016 at 4:52 PM

    Hi Timothy!
    Thank you for the solutions. :) I just wanted to quickly point out that you are missing the answer to Exercise 3.1. It was a text-based question, so I thought you may have skipped it by accident (your answers to Chapter 3's exercises start off with the Matryoshka dolls question, which is 3.2, not 3.1). Anyway, thank you very much!

    ReplyDelete
  22. AnonymousDecember 3, 2016 at 9:25 PM

    Your solution to 3.2 doesn't seem to work. Can't figure that one out :/

    ReplyDelete

Post a Comment

Popular posts from this blog

Writing a Minimal PSR-0 Autoloader

An excellent overview of autoloading in PHP and the PSR-0 standard was written by Hari K T over at PHPMaster.com , and it's definitely worth the read. But maybe you don't like some of the bloated, heavier autoloader offerings provided by various PHP frameworks, or maybe you just like to roll your own solutions. Is it possible to roll your own minimal loader and still be compliant? First, let's look at what PSR-0 mandates, taken directly from the standards document on GitHub : A fully-qualified namespace and class must have the following structure \<Vendor Name>\(<Namespace>\)*<Class Name> Each namespace must have a top-level namespace ("Vendor Name"). Each namespace can have as many sub-namespaces as it wishes. Each namespace separator is converted to a DIRECTORY_SEPARATOR when loading from the file system. Each "_" character in the CLASS NAME is converted to a DIRECTORY_SEPARATOR . The "_" character has no special ...
6 comments
Read more

Composing Music with PHP

I’m not an expert on probability theory, artificial intelligence, and machine learning. And even my Music 201 class from years ago has been long forgotten. But if you’ll indulge me for the next 10 minutes, I think you’ll find that even just a little knowledge can yield impressive results if creatively woven together. I’d like to share with you how to teach PHP to compose music. Here’s an example: You’re looking at a melody generated by PHP. It’s not the most memorable, but it’s not unpleasant either. And surprisingly, the code to generate such sequences is rather brief. So what’s going on? The script calculates a probability map of melodic intervals and applies a Markov process to generate a new sequence. In friendlier terms, musical data is analyzed by a script to learn which intervals make up pleasing melodies. It then creates a new composition by selecting pitches based on the possibilities it’s observed. . Standing on Shoulders Composition doesn’t happen in a vacuum. Bach wa...
7 comments
Read more