14 Aug 2010 tampe   » (Journeyer)

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

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!