25 Jul 2011 tampe   » (Journeyer)

Ordering the functional Ilands

note I use the word continuation below for a closures. This is not exactly what is meant by a continuation in scheme but the used closure function as a sort of delayed computation. Then
this computation object is passed as an argument to various functions until it under the right circumstances is evaluated. So call CPS semantics. Continuations can be implemented to a large degree with the help of this technique though.

Using the guile-2.0 virtual machine and adding a few opcodes targeting the evaluation of prolog programs yields quite good performance (from a few tests maybe less then 2x of gprologs VM). This is accomplished although continuations allocated from the heap are used. The conclusion is that this overhead is not too visible compared to the VM overhead. Actually the version I use combine setjmp like sematics for backtracking with continuation that represents a delayed computation and hence lead to slightly less need of heap compared to using continuations for the backtracking as well.

How are these features used? let's consider the quest of a tree search to solve for example the n-queens puzzle. What features do we have? Well for one thing we need variables that we can set to values that should be visible down the tree as we go out on a limb. If then a failure in the search is signaled we would like to go back and the movie for the values of a variable should be played backwards in order to restore a state at a branch point further up so the search can continue. Another thing is the need to sequence facts, first A should be true, then B and so on. lets write this as

(%and% A B ...)

Another basic building block is to model a branch point e.g. try A, if fail then try B etc. e.g.

(%or% A B ...)

finally we need a way to express that we fail if the fact is true e.g.

(%not% A)

In code %and% could be translated as

(compute (%and% A B) CC Fail)
(compute A (/.(Fail2) (compute B CC Fail2)) Fail)

where CC represents what should be computed after (%and% A B) have been computed (/.(arguments ...) code ...) can be looked at like a definition of a function with associated variables inside A B etc. captured e.g. the variable addresses is stored in them. This happens indirectly as in scheme or If you look at /. the creation as a creation of a object from a compute (used variables would then have to be passed explicitly on in the constructor arguments). Fail is the backtracker and is a continuation or can be a setjmp like backtracking. Let's assume that it is the continuation computation that represents whats need to be done if the computation fails. Now over to %or%

(compute (%or% A B) CC Fail)
(compute A CC (/.() (unwind) (compute B CC Fail)))

Note here that we need to unwind the variables int the failur computation ((/. ()) e.g. run the movie backwards before we restart computing the next branch. Also the failure computation does not have any arguments.
And finally %not%,

(compute (%not% A) CC Fail)
(compute A (/.(Fail2) (Fail)) (/.() (unwind) (CC Fail)))

Note here as well if we success e.g. A fails, we will undo any changes to the variables.

This is a closer look at some of the elements needed to construct prolog like semantics. There are something left like unifications and matching But this is a description to better understand the thoughts flowing out on my posts.

Now I have made a little macro package that outputs from a scheme like language pure c-code. I added closures without a correct set! semantics, allocating the closures from the heap. Also a tail call trampoline framework was added. The generated code is three times slower then compiled gprolog and also it's quite obvious that a lot time is lost due to a hefty use of gc and the heap. So this system did not have a significant improvement compared to the VM approach with a setjmp semantics replacing the failure continuation computation. My next quest will therefore be to modify the macro package to allow allocating the closures from a stack instead. Here the key fact to note are that the Failure continuation should be able to reset to the same position on the stack at a branch. In all there should be hope that memory consumption can be bounded enough to make it practical.

Have fun

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!