[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
guile-log and delimeted continuations
Stefan Israelsson Tampe
guile-log and delimeted continuations
Thu, 26 Sep 2013 17:14:17 +0200
KMail/4.9.5 (Linux/3.5.0-30-generic; KDE/4.9.5; x86_64; ; )
Hi all, I just wanted to chime in with a discussion, regarding logic
programminung in scheme. Most scheme folks would like to use kanren
for this and I would say a huge chunk of written logic programs have
been done in prolog. So wouldn't it be cool to combine the two
iterfaces. This is what I'm currently working on in guile-log. I
already have a kanren interface and I would like to get at least
iso-prolog up and running before I release a new version of
guile-log. So what's interesting with this task.
1. Function references and scheme hygiene.
2. How to support prolog exceptions.
Prolog has a way of using, it looks, symbols in datastructures to
function predicate and function goals. This is not the scheme way and
I am trying to insert the function objects directly in the data
structures. That in the end is much saner. But I suspect that this
imply some deviation from iso-prolog intentions. With this approach
hygiene and sanity is preserved to some degree. One could get a
unified and theoretically ok foundation by demanding that all symbols
are quoted, just as in scheme, or if one uses defined functions it
yields the function refernces else the symbol. These twosolutions means
that not many prolog code will need to be rewritten. The approach I've
taken is to mainly force less common (I suspect) prolog code written
that transfers a definition written in list context where symbols are
used into a functor context e.g. code like
X = [a | _]. #a -> 'a
Y =.. X.
will not work.
If we had written in stead
Y =.. [a | _]. # a -> a
e.g. the second case will import a as a object. The problem is that 
is not treated uniformly and is just the best hack I could think of to
solve the issue.
2) Exceptions is interesting in the kanren world. It's one of the
benefits of guile-log that always track thingies in a stack, although
a large body may be pushed out to a funcitonal list construct just as
in vanilla kanren, but some control stuff is always managed by, in
practice a small stack. Implementing Exceptions in kanren with
ordinary schme expressions may lead to the tree search to explode
memory wise (everything is tail call's in kanren), so we need a
special catch and throw like construct. Now to implement this we
should look how guile does it in principle and boorow the
semantcs. Now what guile is using is delimeted continuations. And a
good idea would be to implement a prolog version if that. How?
Well we stor a pair (tag, fkn) in the stack and at abort we will just
scan the stack for the fisrt match and issue fkn, fkn has the signature
(fkn next args ...)
next is a data-structure that can be used skan to the next match in
the stack and args are the args comming from the abort. The nice
thingie with guile-log is that we can get the continuation directly in
scheme via <state-ref> and restore the state via <state-set!> so we do
not need to construct the continuation at this low level. next can be
used if we find out that want to re-abort without doing anything. This
is what's needed in the lower level at an abort, at an instantiation
we just need to hookin the pair in the control stack.
We would like to construct a continuation, howso? This will demand
some trickery but in the end we would get it to work like
(lambda () code ...)
(lambda (kk a ...)
kk will be a meta continuation e.g. the state will be stored and a real
continuation will be made by issuing k = (kk), we would still need to
unwind explicitly (we will be at the state of the abort) and the we
can use k just as a normal fact e.g. (k X Y Z). the meaning of issuing
the continuation is that we will continue at the old state and when
the (lambda () code ...) successes it will copy X Y Z to their values,
reinstantiate the state at the beginning of (k X Y Z) and then unify
the interpretation of X Y Z with the copied values. and continue after
(k X Y Z) NICE!
Anyway this is all words, I need to go into the fog and implement the
stuff. All cheers and have a nice day/night!
- guile-log and delimeted continuations,
Stefan Israelsson Tampe <=