And so we unify the universes and continues just as
before
How cool it is to have fun and do something useful. Well
at least on the paper. My main focus for some time is to
learn scheme and help out for that community. It's a really
nice experience - thanks for that.
Anyhow I just entered a new project on Advogato - guile
unify - which is may latest contribution. I've been hacking
on it for some months, and feel that it got some interesting
twists. so what is it?. Well it's exploring the combination
of scheme and prolog.
One of the unique features of scheme that have etched
its pattern in my brain is continuations - mainly because it
was so hard to grok that call/cc stuff when I first
encountered it. And this is a really interesting combination
to breed in this marriage between a schemer and a prologur.
prolog is a combination of a variable stack, tree
search, and unifying matches. To introduce continuations one
probably end up with needing redo trees. A path from the
root of the tree out to a leaf is passing variable "set
commands" in such a way that the state of variable stack is
restored from a blank base setup at the leaf, where a
closure is found ready to take a continuation action. By
making a tree one can save some on
memory and perhaps also on time. Got this working and
prompted me give the project some light.
Now, actually I'm lying. Pure continuation will come,
but I'm targeted the method for a limited kind of
continuation. e.g. a postpone command.
Consider writing a chess solver. Now you build up state
information in various structures as you go and would like
to use that information to draw strategic conclusions for a
certain move. You may want to cut unstrategic moves, right!
Well actually this may be prompting the developer to do a
lot of tuning to get correct. So an interesting idea is to
store the state of the game, save that continuation on a
list and continue with that list if resources are available.
This approach is more adaptive and probably lead to less
tuning for the developer. To note is that storing this state
for millions of continuations can put a severe strain on
memory and also raise the complexity of the continuation. So
that's why compress all the information in a redo tree very
much like saving a word lexicon effectively may be
interesting - actually, i don't now about this, I just made
it work!! and it was great fun and a challenge to do it.
Consider trying to logically prove a statement. Could be
cool to try to search for a small and elegant solution
before trying those infinite paths. So just monitor stack
usage and postpone at the points where stack reaches above a
level, and continue to the next level if needed then on.
Just write the usual prolog stuff and insert a few
commands and you will have it. Nah not implemented but hey
look at.
An example in prolog comes here,
prun() :- L = [[[5],2],1,[3,4]],
postpone_frame,
X is 0,
pk(X),
f(L,X).
f([H|L],N) :- !, postpone,
N is N + 1,
g(H,L,N).
f(H,N) :- pk([H,N]), fail.
g(H,L,N) :- f(H,N).
g(_,[H|L],N) :- g(H,L,N).
g(_,[],_) :- fail.
And entering prun leads to the sequence
(1 1),(2 2),(3 2),(4,2),(5,3)
Yea, trivial, but it shows how simple to code it. Now it's
actually trivial to make a stack size criteria that will be
a nice hack to try just to see if it improves.
Oh, The speed is not to bad and it is taking advantage of
tail calls, prompt logic and CPS. Turns out CPS is not bad
for speed - but do affect it.
Now, entering true continuation is just a matter of hard
work. I will need to write a special GC for this structure
because, the data-structure is tuned to be good at the
scenario above and true continuation will be a cool
creature, but a second citizen in my view that need some caring.
I will try to find time to talk a little more about the
internals of all this. Maybe it's all a nice sand castle,
maybe it is severely cool. Time will tell. I will continue
to hack on it. If you have any questions or would like to
learn or help, join the guile devel community and ask about
guile unify.
Cheers
Stefan