## Implication problem

Discussion of Common Lisp

### Implication problem

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

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: 611
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

### Re: Implication problem

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

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: 611
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

### Who is online

Users browsing this forum: No registered users and 1 guest