>> Attached to this message is version 2, release #1 of Logic Box.
>
> I think I remember reading your original post when you first wrote this
> in Haskell, a lot of it sounded very familiar...

Yep. It's from a chapter in the book "The Fun of Programming". (It's 
about FUNctional programming, see? See what they did there? >yawn<)

> Runs fine here, opened it up and was thinking what it could be useful
> for ... could it be used to solve Sudoku puzzles?

It... could. Perhaps. With some serious modifications.

Of course, /the/ canonical logic programming language is Prolog. 
Apparently when people first saw that thing back in the 1970s, everybody 
suddenly thought that human-level AI was just around the corner.

Logic Box doesn't have quite the same capabilities as Prolog. But the 
general idea is that you give Prolog "facts". You can then write 
"queries", and it uses logical deduction to solve them (much like Logic 
Box performs logical deduction).

For example, you might program in a family tree, and then ask queries 
like "Who is the most common ancestor of Jim and Fred?" or "Is Sam 
related to Jack?" Just like Logic Box, you don't actually /tell/ Prolog 
how to answer the question, you only tell it what it means for two 
people to be "related", and who is immediately related to who. The 
Prolog deduction system can them work out everything else from that. 
[Eventually...]

I gather people use this for things like diagnostic systems. You program 
in all the medical conditions and what their symptoms are. A doctor can 
then query the system with the symptoms presented, the system can decide 
which tests could be most diagnostic in eliminating similar illnesses, etc.

Watching Prolog at work, it's almost /frightening/ how much stuff it can 
figure out by itself, seemingly by magic. Indeed, before I wrote Logic 
Box, Prolog appeared to /be/ magic. It looks like the machine is almost 
/intelligent/ in it's ability to answer question; no wonder people saw 
it and thought that AI would be a solved problem any minute now.

But in fact, it's just a machine following a deterministic decision 
procedure. (It's possible that the human brain fits the same 
description, of course...) Sometimes it seems to pluck answers out of 
the air as if by magic. But other times, it utterly fails to answer 
questions which it looks like it "should" be able to figure out. Because 
it /isn't/ thinking, it's just blindly running a program.

And thus, 40+ years later, we still don't have WOPR, Skynet, HAL, Jonny 
5, Kit or any other similar AI. We don't have anything remotely close to 
it. (I was watching War Games the other day... Christ that film has some 
ancient hardware!)

> Also how hard would it be to add support for arithmetic operators? Then
> you would have an equation solver, which arguably would be more useful.

Yeah, if you've been paying attention, you'll have noticed that 
ultimately everything boils down to equality predicates. There are no 
other comparison operators (e.g., less than or greater than), and there 
are no functions operating on expressions (e.g., no arithmetic).

In a sense, Logic Box /already/ implements arithmetic. If you consider a 
list as representing a number (i.e., the length of the list), then the 
LJoin{} predicate implements addition. AND SUBTRACTION, by the way. 
Because logic programming is like that. And if you implement a predicate 
for performing a Cartesian product of lists [should be hard to do], that 
would implement multiplication. AND DIVISION.

Be careful what you wish for, however: Recall that a 5th-order 
polynomial is potentially impossible to solve. Even limiting ourselves 

impossibility of proving statements about integers, and the 
impossibility of Hilbert's tenth problem (it is impossible to even 
decide /if/ a Diophantine equation has /any/ solutions, never mind 
/find/ them).

So yes, I probably can implement some arithmetic into Logic Box. But 
there are limits to what is computable. I'm kinda curious to see how 
that works out...

If you've been paying attention, you'll notice that there's no NOT 
operator. Because how would that work? The equality predicate works by 
adding information until a solution is found or we have to give up, and 
all the other predicates basically work by running equality predicates 
[ultimately]. What would the solution to, say, "NOT x = 5" look like? 
There would have to be some way of representing INequalities in a 
solution. And then we would have to figure out how such inequalities 
combine and so forth.

Adding operators like "less than" or "greater than" would be even 
harder. Logic Box would have to know a bunch of theorems about integers. 
Stuff like "x > 5 & x < 4 is impossible".

I think it would be an interesting project to see what things can or 
cannot be incorporated. But I doubt I'd try to program it as an 
interactive solver; more likely as a batch processing system which gives 
no status information. (That's obviously drastically easier to code.) 
I'd probably do it in Haskell too. (Because then I can spend more time 
concentrating on the theoretical tractability of a confluent set of 
transformation rules, and less time worrying about uncaught class cast 
exceptions due to invariants that the puny Java type system is too 
feeble to enforce...)

> Having written something like this is also very good for CVs and job
> interviews :-)

...and you think I'm doing this because...? ;-)

Post a reply to this message