Implication problem

Discussion of Common Lisp

Implication problem

Postby Mojave » Wed Jan 14, 2009 1:42 am

Hi, there!

I'm having some problems with a program I have to implement using Lisp, and I was wondering if anyone could give me a few pointers or maybe a bit of code.
The task is this - I have to write a function that receives a list of rules (each rule being stated as '(a b then c), meaning "if a and b are true, then c is true"), a fact, and a list of facts that are considered true. The function should create a "demonstration path" of rules from the first list, proving that the given fact is itself true, starting from the facts from the second list. An example would be:

(prove '( (a b then c) (b c then d) (a b c d then x) ) 'x '(a b)), which should return ((A B THEN C) (B C THEN D) (A B C D THEN X)).

Thanks in advance for any help.
Mojave
 
Posts: 2
Joined: Wed Jan 14, 2009 1:29 am

Re: Implication problem

Postby Ramarren » Wed Jan 14, 2009 2:16 am

This sounds like homework, which I suppose is a good thing because it means that someone somewhere is teaching Lisp ;)

Anyway, what you want here is backward chaining. How much Lisp do you know? It is hard to give just a bit of code without giving a full solution, and that is usually counterproductive for the purpose of learning. I think you would need just a stack or two and a hash table... I think reasoning chain would be most easily maintained with recursion.
Ramarren
 
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

Re: Implication problem

Postby Mojave » Wed Jan 14, 2009 12:34 pm

Yes, homework indeed. I'm in college, studying computer science, so someone was bound to teach us Lisp too at some point :).

Anyway, I actually turned it in earlier today and it turned out ok. I used two functions that called each other, one to prove a rule, the other to "prove" (not the best term, but it'll have to do) a fact, by proving one of the rules defining that fact, and so on until I had only proven facts left in the "pending" stack. I got 95% because in some situations it didn't handle cyclic rules so well (such as '((a then b) (b then c) (c then a)), for example). I can post the code, if you like, but I've got tons of other assignments coming up, so I probably won't be debugging this any longer, now that I've turned it in.

Anyway, thanks for the help!
Mojave
 
Posts: 2
Joined: Wed Jan 14, 2009 1:29 am

Re: Implication problem

Postby Ramarren » Wed Jan 14, 2009 12:49 pm

I hear that more and more places are dropping Lisp as a teaching language and replacing it with Python/Ruby, or in the worst case go all Java all the way, although those don't really qualify as computer science in my opinion. I studied physics anyway, and what programming there is is mostly C++/Fortran, so I learnt Lisp on my own.

Congratulations on the assignment. I'm just curious... How much Lisp is there in your college? Was it a part of some tour through languages, or are there entire courses in it?
Ramarren
 
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland


Return to Common Lisp

Who is online

Users browsing this forum: Google [Bot] and 2 guests