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.
Implication problem
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.
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.
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!
.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!
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?
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?