unification

unification

[stefan]

Hi,

I did a small try to extend guile to handle unification. The result is in

http:///c-lambda.se/gp.tar.gz

In there is an example of a unification solution of the Einstein riddle.
The solution takes 150ms on my PC. Gnu prolog execute it in about 16ms.
I'm using a c-extension linked in which is a fun play with the tagging system 
in guile (ducks!)

So not so bad. But there is a nice abstraction that lies behind this code that 
can be useful. So I would like to snow in and try to make this abstraction 
solid (You may be scared of the code) and perhaps even faster. What options
do I have to make it as fast and, if you are interested, please reply.

By the way. I can help out as well. My main interest now is in type theory but 
I start to dig into guile now and I would probably be able to help out if you 
like in a short time, as my knowledge matures.

 Are there any suitable tickets to close?

Regards
Stefan

Re: unification

[Ludovic Courtès]

Hello!

stefan <stefan.tampe@spray.se> writes:

> I did a small try to extend guile to handle unification. The result is in
>
> http:///c-lambda.se/gp.tar.gz
>
> In there is an example of a unification solution of the Einstein riddle.
> The solution takes 150ms on my PC. Gnu prolog execute it in about 16ms.
> I'm using a c-extension linked in which is a fun play with the tagging system 
> in guile (ducks!)

I haven’t looked at the code but that sounds like an interesting and
useful project!

If I were you I would write the unification code in Scheme, at least as
a starting point, esp. since I would expect most optimizations to be
done at an algorithmic level.

Then you could implement the hot spots in C, if that turns out to be a
real advantage, or simply wait until Guile gets a native compilation
back-end, JIT, or both.  :-)

> By the way. I can help out as well. My main interest now is in type theory but 
> I start to dig into guile now and I would probably be able to help out if you 
> like in a short time, as my knowledge matures.
>
>  Are there any suitable tickets to close?

You could look at the bugs in
<http://savannah.gnu.org/bugs/?group=guile>, along with posts on
<bug-guile@gnu.org> left unanswered.  And of course, you could do
testing under all possible conditions, or look at the code and improve
the bits that please you.  :-)

Besides, there’s an informal to-do list in the minds of some of us for
2.0, and that list is getting small.

Thanks,
Ludo’.

Pattern matching

[Ludovic Courtès]

Hi,

[Cc: guile-devel.]

Stefan <stefan.tampe@spray.se> writes:

> On Apr 13, 2010, at 1:55 PM, Ludovic Courtès wrote:

>> stefan <stefan.tampe@spray.se> writes:

[...]

> Actually I have some experience in coding unification. Done a version
> for SBCL that is similar to the one suggested that clocks 10x faster
> and on par with gprolog for the coded example.

Heh, SBCL compiles to well-optimized native code.  We’re not there yet,
for sure.

> So this is what I have tried. I defined some hotspot elements in C,
> and coded the logic in scheme. So in a sense I have tried to do what
> you suggest. You could code prolog with these elements if you like and
> 99% of the code would be scheme. But I did not code a full version in
> scheme just to see how it compares, I'll chew on that,

OK, you know what you’re doing very well so you may well be taking the
right approach.  :-)

> I'll very much like to code using pattern matching techniques, I'll
> notice there are some similar tools in your bag here. Can I have a
> short intro intro the possibilities?

In terms of pattern matching, Guile has (ice-9 match), a classical
pattern matcher for Scheme by Andrew K. Wright, and pmatch by Oleg
Kiselyov et al.  These work well but have limitations, such as the fact
that they don’t work on records; well, in theory (ice-9 match) does work
on records but in practice that doesn’t work, notably because it wants
you to use its own record infrastructure.

Because of that the compiler uses its own macro, ‘record-case’, to match
records that are used to represent elements of the various intermediate
languages.  However, it’s pretty limited in that it doesn’t allow you to
match nested elements.  And it doesn’t match types other than records.

So if you’re in pattern matching, you could look into extending, say,
(ice-9 match) to support pattern matching on SRFI-9 records.  It should
be doable since ‘define-structure’ in (ice-9 match) is a syntactic
record API, similar in spirit to SRFI-9.  (There’s a 1995 paper called
“Pattern Matching for Scheme” by Wright et al.)

What do you think?

Thanks,
Ludo’.

Re: unification

[Andy Wingo]

Hi Stefan,

On Tue 13 Apr 2010 13:55, ludo@gnu.org (Ludovic Courtès) writes:

> stefan <stefan.tampe@spray.se> writes:
>
>> I did a small try to extend guile to handle unification. The result is in
>>
>> http:///c-lambda.se/gp.tar.gz
>>
>> In there is an example of a unification solution of the Einstein riddle.
>> The solution takes 150ms on my PC. Gnu prolog execute it in about 16ms.
>> I'm using a c-extension linked in which is a fun play with the tagging system 
>> in guile (ducks!)
>
> I haven’t looked at the code but that sounds like an interesting and
> useful project!

Agreed! I looked briefly at the code, but this is one of my many
ignorant areas.

I would also suggest implementing this in Scheme, as a macro. That way
you program as in prog.scm, but when it's expanded, it expands out to
the exact thing you need to do the job. A macro extends the compiler
with support for a mini-language -- something like prolog in your case.

>> By the way. I can help out as well. My main interest now is in type theory but 
>> I start to dig into guile now and I would probably be able to help out if you 
>> like in a short time, as my knowledge matures.
>>
>>  Are there any suitable tickets to close?

Besides the points Ludovic mentioned, if you are interested you could
try writing a type inferencer for tree-il. Do it as a weak map from
tree-il to some type representation, then propagate down to the leaves
and back. At least, that will work for many cases -- you might know a
better implementation strategy.

Have fun with Guile,

Andy
-- 
http://wingolog.org/

Re: unification

[stefan]

I did a reference implementation of unification code in pure 
scheme. It is just 185 lines of code (the rest is the test case)

see http://c-lambda.se/unify.scm

Some timings for the example
============================
scheme-version     > 2100 ms
c-initial-guile    > ~150 ms
current-best-guile >   73 ms 
sbcl               >   25 ms
gprolog            >  ~20 ms

So I've been able to tweak out 2x in guile + c

So what next?

This is what I will be playing with.
one need apart from a unification primitive also
be able to destruct a pattern into variable references
this can be done in a vm on a stack machine. And I will
now go on to let this vm be the guile vm itself. Later 
on when we the compiler starts to shine, I could hook into
that as well and generate target code. So this litle play will
spill over into being useful for the compiler later.
/Stefan