From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.devel Subject: Re: Inclusion of guile-log II Date: Thu, 5 Apr 2012 08:02:34 +0200 Message-ID: References: <87zkarqi5a.fsf@gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=14dae93408593f4d6404bce84911 X-Trace: dough.gmane.org 1333606058 4645 80.91.229.3 (5 Apr 2012 06:07:38 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Thu, 5 Apr 2012 06:07:38 +0000 (UTC) Cc: guile-devel@gnu.org To: =?ISO-8859-1?Q?Ludovic_Court=E8s?= Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Thu Apr 05 08:07:36 2012 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1SFfr1-0004Rf-Cv for guile-devel@m.gmane.org; Thu, 05 Apr 2012 08:07:31 +0200 Original-Received: from localhost ([::1]:60038 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SFfmY-0005Fp-Ut for guile-devel@m.gmane.org; Thu, 05 Apr 2012 02:02:54 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:53688) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SFfmR-0005DD-Ik for guile-devel@gnu.org; Thu, 05 Apr 2012 02:02:52 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1SFfmI-0004aT-Ew for guile-devel@gnu.org; Thu, 05 Apr 2012 02:02:47 -0400 Original-Received: from mail-iy0-f169.google.com ([209.85.210.169]:39340) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SFfmI-0004Zq-3i; Thu, 05 Apr 2012 02:02:38 -0400 Original-Received: by iajr24 with SMTP id r24so1672222iaj.0 for ; Wed, 04 Apr 2012 23:02:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=xfv3z0PrBH8kjjjz4j012UPN6Pzd8lSkUi7+rQmfB8E=; b=JbowdZnEV5gaEW/uu8OKcr9eJ8VlhxgqB/1OwA4KT/MwAkEkODB6plIgz14FLhpA6o X7TvGR0XDuZzeV0lrB1bOV70HQaHS7DvKQ/jIJ+3B5Yf/EWZtw4PmLT69fZE3P9Ez8ZB BhIe87neU3OTuM9UCGy9JWUZhDUzzMGm9Z+GCMlCIN37YTgvzWaYqZ4KtsC95RY+qnp1 mSbYxLUqNQXQX7V3dGNoOlCrv6mHCaTwlftkLQ9Ov2zCTmU3lZySQM7PdtyLoRZynP44 y+A/XvlprCOjS+iIIuKw85qe5/De8aeyoAo/js2h55oPJjzKvV1UMZUlVb30jHYGwAsU LBNg== Original-Received: by 10.50.189.200 with SMTP id gk8mr846730igc.8.1333605754162; Wed, 04 Apr 2012 23:02:34 -0700 (PDT) Original-Received: by 10.50.242.102 with HTTP; Wed, 4 Apr 2012 23:02:34 -0700 (PDT) In-Reply-To: <87zkarqi5a.fsf@gnu.org> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 209.85.210.169 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:14217 Archived-At: --14dae93408593f4d6404bce84911 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable On Wed, Apr 4, 2012 at 11:52 PM, Ludovic Court=E8s wrote: > Hi Stefan, > > Stefan Israelsson Tampe skribis: > > > If you want independence use kanren. For guile this approach is 10x > faster > > then kanren > > and 10x slower that a compiled prolog. Previously I thought that kanren > has > > a more functional > > fundament and can express amazing things. But i'm now inclined that > > guile-log has a feature > > that are very cool and I will try to explain this feature for the fun o= f > it. > > Any idea why there=92s such a performance difference? > Yes the lookup cost can be substancially higher (in guile-log that's just a one or two dereferenses) but on kanren you need to search an alist of all bindings, the number of lambdas is more for each operations and, maybe not that important but the allocations in guile-log is from a stack, but kanren uses a heap. the unify function in guile-log is in C while the same function is kanren is in scheme. And lastly guile-log is a heavy macrology in order to support cut's but kanren uses no cut and can stay functional, but this means that kanren features more lambda constructions and i'm uncertain if peval can counteract this. N.B. 1, I took a testcase (einstein problem) for kanren on chicken, compiled and compared with the same case on guile using vm operation support. That showd about 5x speed difference in that case. N.B. 2, heavy use of interleaving constructs may insteafd point for kanren as a better method. Especially If we can make use of functional lookup structure with better lookup performance like VLISTS, but I have a version of functional self organizing trees as well which can perform close to a hash lookup mechanism (the datstructure is in C that is) Regardless, I=92d be reluctant to use (or include in Guile) a logic > programming system that uses an interface different from that of Kanren, > because (1) there=92s a book explaining that interface, and (2) it=92s ve= ry > well thought out, concise, elegant, and powerful. > Well if you want to translate prolog programs to scheme guile-log is actually a better fit cause you may want to support cut's, that's why I designed another interface. It's not hard to mimic most of kanren though, It's even simpler. You need to supply a functional version e.g. operations that return a function and use functions in stead of macros in many places. On a lower level kanren uses it's lambda@ constructs e.g. to allow currying, that's sweet but I'm uncertain if that is needed, But yes I plan to support a translational module to higher level kanren! > AIUI Guile-Log uses a different interface, right? What would it take to > implement Kanren=92s? > > Thanks, > Ludo=92. > > > 3 day's of coding perhaps. F.Y.I. i'm going through the reasoned schemer right now and remakes most of the examples in guile-log. That had gave my quite insight and therefore I don't think a translation is that hard. /Stefan --14dae93408593f4d6404bce84911 Content-Type: text/html; charset=windows-1252 Content-Transfer-Encoding: quoted-printable

On Wed, Apr 4, 2012 at 11:52 PM, Ludovic= Court=E8s <ludo@gnu.o= rg> wrote:
Hi Stefan,

Stefan Israelsson Tampe <stef= an.itampe@gmail.com> skribis:

> If you want independence use kanren. For guile this approach is 10x fa= ster
> then kanren
> and 10x slower that a compiled prolog. Previously I thought that kanre= n has
> a more functional
> fundament and can express amazing things. But i'm now inclined tha= t
> guile-log has a feature
> that are very cool and I will try to explain this feature for the fun = of it.

Any idea why there=92s such a performance difference?

Yes the lookup cost can be substancially higher (in guile-log tha= t's just a one or two dereferenses) but on kanren you need to search an= alist of all bindings, the number of lambdas is more for each operations a= nd, maybe not that important but the allocations in guile-log is from=A0 a = stack, but kanren uses a heap. the unify function in guile-log is in C whil= e the same function is kanren is in scheme. And lastly guile-log is a heavy= macrology in order to support cut's but kanren uses no cut and can sta= y functional, but this means that kanren features more lambda constructions= and i'm uncertain if peval can counteract this.
=A0
N.B. 1, I took a testcase (einstein problem) for kanren on chicken, = compiled and compared
with the same case on guile using vm operation su= pport. That showd about 5x speed difference in that case.

N.B. 2, he= avy use of interleaving constructs may insteafd point for kanren as a bette= r method. Especially If we can make use of functional lookup structure with= better lookup performance
like VLISTS, but I have a version of functional self organizing trees as we= ll which can perform
close to a hash lookup mechanism (the datstructure = is in C that is)

Regardless, I=92d be reluctant to use (or include in Guile) a logic
programming system that uses an interface different from that of Kanren, because (1) there=92s a book explaining that interface, and (2) it=92s very=
well thought out, concise, elegant, and powerful.

= Well if you want to translate prolog programs to scheme guile-log is actual= ly a better fit
cause you may want to support cut's, that's why = I designed another interface. It's not hard to mimic most of kanren tho= ugh, It's even simpler. You need to supply a functional version e.g. op= erations that return a function and use functions in stead of macros in man= y places. On a lower level kanren uses it's lambda@ constructs e.g. to = allow currying, that's sweet but I'm uncertain if that is needed, B= ut yes I plan to support a translational module to higher level kanren!
=A0
AIUI Guile-Log uses a different interface, right? =A0What would it take to<= br> implement Kanren=92s?

Thanks,
Ludo=92.


3 day's of coding perhaps. F.Y.I. i'm going thro= ugh the reasoned schemer right now and remakes most of the examples in guil= e-log. That had gave my quite insight and therefore I don't think a tra= nslation is that hard.

/Stefan
--14dae93408593f4d6404bce84911--