Re: Background info abot the unfyication tool

[Andy Wingo]

Hi Stefan,

Thanks for this writeup, it was very interesting. I don't come from the
logic programming world, so it was great to hear your thoughts and see
your code. It's clear that you've thought a lot about these problems :)

It's very cool that you were able to come in an hack up performant
solutions. Rock on! Though, with my maintainer hat on, I have to be a
bit more cautious :)

The set of instructions in Guile's VM has been chosen to be appropriate
to Guile's flavor of Scheme, and for Elisp. We could add prolog-type
instructions, yes -- but I would like to avoid it if I can :-)

As you know, the speed of an algorithm depends first of all on how much
it conses, and secondly on the number of instructions that it executes.
So with these considerations in mind, and with the caveat of my
ignorance of logic programming, let's consider your examples :)

On Tue 18 May 2010 19:42, stefan <address@hidden> writes:

> Backtracking.

Guile supports backtracking natively, using escape-only prompts. So in
your example, having used (ice-9 control):
>
> (let ((X (var!))
>       (Y (var!))
>       (L (var!)))
    (let ((frame-nr (make-prompt-tag)))
      (% (if (<u> Q [K a Y  L])
             ...
             (abort frame-nr))
         (lambda (unused-cont)
           (if (<u> Q [X Y])
               ...
               ...))))))
           
Also do you need to actually make variables at runtime? Might binding
them to fresh values or whatever be done at expansion time, and expanded
into the source?

> so, variables are allocated on a stack

On Guile's stack, yes.

> and when new bindings is done the old values is saved on an
> undo-array.

If you need to produce side effects to undo something, use dynamic-wind;
if you just need dynamic scoping, e.g. for detecting cycles, use
with-fluids; and if you don't need to produce effects, the lexical
scoping combined with the abort should serve your purposes.

> 3. REF          - need to quickly tell if the data is a reference to another 
>                   object!!

Interesting. This reminds me of kanren; have you seen it? Perhaps that
is an ignorant reference, though.

> The cool thing though is that we can fix this, 
> basically we mark all arrows (-> a b) that has been visited via a special
> hashmap kind of datastructure

Use with-fluids for that hashmap, if it can be implemented functionally.
This would cons, though.

It is true that currently scheme-only solutions will be slower than
yours, though I suspect that your previous numbers were based on some
implementation misunderstandings. For example, pmatch from (system base
pmatch) is a straightforward matcher that generates all-inlined code
(without closures, I mean).

Check the compilation output of (lambda (x) (pmatch x ((a _) 'a) (b c)
'b)), for example. Granted you can see from that output that we don't
inline (in the copy-propagation sense) as much as we should, and our
basic block ordering is really suboptimal -- but I'd like to focus on
those more general algorithms so that all of Guile will benefit, and
eventually we produce nice tight code.

Let us know how it goes with prompt and abort :) I don't have a link on
hand, but a few months ago I wrote about prompt and abort on my web log,
with links to papers.

Cheers,

A
-- 
http://wingolog.org/