On Wed, Apr 4, 2012 at 11:52 PM, Ludovic Courtès
<address@hidden> wrote:
Hi Stefan,
Stefan Israelsson Tampe <address@hidden> 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 of it.
Any idea why there’s 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’d be reluctant to use (or include in Guile) a logic
programming system that uses an interface different from that of Kanren,
because (1) there’s a book explaining that interface, and (2) it’s very
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’s?
Thanks,
Ludo’.