kanren (and other 'new prologs')

Recently, I stumbled upon KANREN, a logic programming system implemented on
top of Scheme, and certain claims by its authors that, frankly, seem too
good to be true.  http://kanren.sourceforge.net/

Unlike Prolog, KANREN has a set-theoretic semantics, and despite this fact,
it is much faster (at least in solving the Zebra puzzle) [1]. We know that
Prolog is a compromise between the desire to implement correct First-Order
Logic (or at least its Horn-clauses-only subset) and the desire to have
something that runs reasonably fast. Prolog does not do occurs check, and
it has issues with NOT and OR.

So how can KANREN do "the right thing" and yet be fast? I tried reading
KANREN documentation to answer this question for myself. They lost me soon
after the definition of the BNF grammar for Antecedent [2].

So here are my questions, in case anyone might know the answers:


* What is the catch ?!

* I tried, but couldn't find any mention of ZFC axioms in KANREN sources.
In what sense does it have a set-theoretic semantics?

* Is KANREN similar to Mercury? (typing, determinism declarations)


Thanks!



[1] It's actually been said that KANREN running on top of an /interpreted/
Scheme solves Zebra faster than SWI-Prolog

[2] My familiarity with Prolog, Scheme macros and functional programming did
not help. I can imagine what it might be like for people trying to /learn/
logic programming by learning KANREN.

In article <2433356.sVPrANugId@yahoo.com>,
alex goldman  <hello@spamm.er> wrote:
>So here are my questions, in case anyone might know the answers:

I don't have any answers, sorry.   In the past, I did play around with
Schelog, which is truly slower than native prologs even after my best effort
s.
I, too, was troubled by the things that can cause failure in Prolog
(lack of an occurs check, and depth-first search iterating indefinitely
when a breadth-first search would find the answer) that students evidently
learn to program around.  I do not understand Kanren, either; perhaps you
can summarize later what you find out in response to your inquiry.

Is there a possibility that Friedman and Kiselyov have finally come up with
the correct approach to logic programming, in the same way that Flatt and
others may have come up with the correct approach to macros and module
systems?  If so, we live in exciting times!

Newsgroups trimmed; I don't want my ignorance to start a flame-war with
the prologlodytes.

Brad

alex goldman wrote:

> ...
> [1] It's actually been said that KANREN running on top of an /interpreted/
> Scheme solves Zebra faster than SWI-Prolog

This is Petite Chez, not a vanilla scheme interpreter that fits
on a 3x5 index card.

Aziz,,,

PS. Followup set

Hi Alex,

I told Dan Friedman about your interest in Kanren.  He would be happy
to answer all of your questions if you email him at his 'dfried'
address.  Dan doesn't post to newsgroups, but perhaps you can summarize
what you learned from him.

Hope this helps.

Cheers,

--Will

alex goldman wrote:
> Recently, I stumbled upon KANREN, a logic programming system
implemented on
> top of Scheme, and certain claims by its authors that, frankly, seem
too
> good to be true.  http://kanren.sourceforge.net/
>
> Unlike Prolog, KANREN has a set-theoretic semantics, and despite this
fact,
> it is much faster (at least in solving the Zebra puzzle) [1]. We know
that
> Prolog is a compromise between the desire to implement correct
First-Order
> Logic (or at least its Horn-clauses-only subset) and the desire to
have
> something that runs reasonably fast. Prolog does not do occurs check,
and
> it has issues with NOT and OR.
>
> So how can KANREN do "the right thing" and yet be fast? I tried
reading
> KANREN documentation to answer this question for myself. They lost me
soon
> after the definition of the BNF grammar for Antecedent [2].
>
> So here are my questions, in case anyone might know the answers:
>
>
> * What is the catch ?!

Here are some candidates:

- KANREN is part of a course on "Programming Languages", but the (IMO)
unfortunate students may never learn the simplicity (and perplexity) of
programming in Prolog (or indeed in any other programming language than
Scheme) because:

- KANREN isn't Prolog. It isn't logic programming. It's "logic-oriented
programming" according to the site. Everything is coded in

- Scheme (with a little C tossed in). So in the "logic-oriented" part
of the course the LOC count is up by a factor of 5-10 compared to
Prolog. This is

- consistent with current university protocols of forcing students into
the "think less, code more" paradigm. I suppose the students should be
pleased that the instructors didn't regress to Java.

- FWIW Amazon lists reviews of the course text, written by one of the
instructors, at
http://www.amazon.com/exec/obidos/t...=glance&s=books

Those Amazon reviewers who claim to be survivors of the author's class
do not paint a pretty picture.

- The title of the class should perhaps instead be "How to write
programming languages using Scheme".

> [2] My familiarity with Prolog, Scheme macros and functional
programming did
> not help. I can imagine what it might be like for people trying to
/learn/
> logic programming by learning KANREN.

If students enter such a class _fully_aware_ of what is being done (it
isn't really a "Programming Languages" course, it's an advanced
"Scheme's-eye View of Programming Languages") then they might learn a
great deal. OTOH if it is yet-another instance of a core course being
used by an instructor to develop/promote his/her new book/project, then
the students are little more than guinea pigs. In either case they
should get two T-shirts upon completion of the course (one to wear,
another to frame, burn or sell on eBay).

xeo_at_thermopylae wrote:


> Here are some candidates:
>
> - KANREN is part of a course on "Programming Languages",

No.  MiniKanren is used in the course on Programming languages.
MiniKanren is a 2-page implementation of a stripped down version of Full
Kanren.

> but the (IMO)
> unfortunate students may never learn the simplicity (and perplexity) of
> programming in Prolog (or indeed in any other programming language than
> Scheme)

I don't believe the course objective covers "learning to program in
prolog".  The course covers how the different programming paradigms
could be understood.  This includes functional/imperative/logic/OO/...
programming.

> because:
> - KANREN isn't Prolog.

Of course it's not.

> It isn't logic programming. It's "logic-oriented
> programming" according to the site. Everything is coded in
>
> - Scheme (with a little C tossed in).

Why is it a divantage that it's written in scheme given that the
students of the course are already familiar with scheme.  And where did
you get the `little C tossed in' part?  Where in Kanren is C used?

> So in the "logic-oriented" part
> of the course the LOC count is up by a factor of 5-10 compared to
> Prolog.

How did you get these figures?  When was prolog ever used in that
course?  Let me say it again, the course as I understand it is not about
logic programming, but rather about how logic programming works (among
other things).

> This is
> - consistent with current university protocols of forcing students into
> the "think less, code more" paradigm. I suppose the students should be
> pleased that the instructors didn't regress to Java.

I won't bite on this one.

> - FWIW Amazon lists reviews of the course text, written by one of the
> instructors, at
> http://www.amazon.com/exec/obidos/t...=glance&s=books
>
> Those Amazon reviewers who claim to be survivors of the author's class
> do not paint a pretty picture.

What the hell does the EoPL have to do with this thread?

> - The title of the class should perhaps instead be "How to write
> programming languages using Scheme".

What the hell does the course title have to do with Kanren?

> If students enter such a class _fully_aware_ of what is being done (it
> isn't really a "Programming Languages" course, it's an advanced
> "Scheme's-eye View of Programming Languages") then they might learn a
> great deal.

You just said it should have been named `How to write programming
languages using scheme'.  Now you say "it isn't really a programming
languages course".  Make up your mind.

> OTOH if it is yet-another instance of a core course being
> used by an instructor to develop/promote his/her new book/project, then
> the students are little more than guinea pigs.

I won't dignify this statement with a response.

Aziz,,,

Disclaimer: I have nothing to do with this course except that I took the
grad version of it a few years back and my experience completely
contradicts everything mentioned in the post.

xeo_at_thermopylae wrote:

>
> - KANREN isn't Prolog. It isn't logic programming. It's "logic-oriented
> programming" according to the site. Everything is coded in
>

I was promised that one of the authors will answer my questions one of these
days.

In the meantime, my working hypothesis [1] is that in the case of the Zebra
puzzle, apples and oranges probably get compared. We know that Prolog Zebra
can be made significantly faster by adding cuts. KANREN has the so called
soft cuts that reduce the search space in a similar way. So if an
unannotated logic program is compared to "softly cut" one, it may be
unsurprising if the latter is faster.

[1] It /is/ a hypothesis, I'm studying, but I don't yet quite understand
KANREN. Please correct me if this is wrong.

alex goldman wrote:

> We know that Prolog Zebra
> can be made significantly faster by adding cuts.

I didn't know that. Can you post a version of zebra with the extra cuts
that make it significantly faster ?

Cheers

Bart Demoen

alex goldman wrote:

> Unlike Prolog, KANREN has a set-theoretic semantics, and despite this fact
,
> it is much faster (at least in solving the Zebra puzzle) [1].

> [1] It's actually been said that KANREN running on top of an /interpreted/
> Scheme solves Zebra faster than SWI-Prolog

The SWI-Prolog interpreter that I have solves the Zebra puzzle
in about 45 millisecs and compiled PDC Prolog solves it in a
matter of microsecs. It's not a hard problem. What's your point
in mentioning it?

% [zebra puzzle] solution by Claude Sammut, PDC declarations added by me.

DOMAINS

HOUSE =  house(COLOR,RESIDENT,PET,BEVERAGE,CARCIN
OGEN)
COLOR = red ; green ; blue ; yellow ; ivory
RESIDENT = norwegian ; ukrainian ; english ; spanish ; japanese
PET = fox ; horse ; snails ; dog ; zebra
BEVERAGE = water ; tea ; milk ; coffee ; orange_juice
CARCINOGEN = kools ; chesterfields ; winstons ; lucky_strikes ; parliaments

HOUSES = HOUSE*

PREDICATES

NONDETERM zebra
houses(HOUSES)
NONDETERM right_of(HOUSE,HOUSE,HOUSES)
NONDETERM next_to(HOUSE,HOUSE,HOUSES)
print_houses(HOUSES)

NONDETERM member(HOUSE,HOUSES)

CLAUSES

zebra :-
houses(Houses),
member(house(red, english, _, _, _), Houses),
member(house(_, spanish, dog, _, _), Houses),
member(house(green, _, _, coffee, _), Houses),
member(house(_, ukrainian, _, tea, _), Houses),
right_of(house(green,_,_,_,_), house(ivory,_,_,_,_), Houses),
member(house(_, _, snails, _, winstons), Houses),
member(house(yellow, _, _, _, kools), Houses),
Houses = [_, _, house(_, _, _, milk, _), _,_],
Houses = [house(_, norwegian, _, _, _)|_],
next_to(house(_,_,_,_,chesterfields), house(_,_,fox,_,_), Houses),
next_to(house(_,_,_,_,kools), house(_,_,horse,_,_), Houses),
member(house(_, _, _, orange_juice, lucky_strikes), Houses),
member(house(_, japanese, _, _, parliaments), Houses),
next_to(house(_,norwegian,_,_,_), house(blue,_,_,_,_), Houses),
member(house(_, _, zebra, _, _), Houses),
member(house(_, _, _, water, _), Houses),
print_houses(Houses).

houses([
house(_, _, _, _, _),
house(_, _, _, _, _),
house(_, _, _, _, _),
house(_, _, _, _, _),
house(_, _, _, _, _) ]).

right_of(A, B, [B, A | _]).
right_of(A, B, [_ | Y]) :- right_of(A, B, Y).

next_to(A, B, [A, B | _]).
next_to(A, B, [B, A | _]).
next_to(A, B, [_ | Y]) :- next_to(A, B, Y).

print_houses([A|B]) :- !,
write(A), nl,
print_houses(B).
print_houses([]).

member(A,[A|_]).
member(A,[_|Y]) :- member(A,Y).

GOAL zebra.

/* [end] */

student wrote:

> alex goldman wrote:
> 
> 
>
> The SWI-Prolog interpreter that I have solves the Zebra puzzle
> in about 45 millisecs and compiled PDC Prolog solves it in a
> matter of microsecs. It's not a hard problem. What's your point
> in mentioning it?

I trust others' judgement whether they can meaninfully time such simple
tasks on their systems:

http://groups-beta.google.com/group...729f02e61d7a865