Gecode glue
The idea of the glue layer proposed here is to provide a clean interaction between a constraint library implemented in C++ and an interpreted language. This part is not Mozart specific and its development only involves C++ coding. There are some things that are general to this integration:
- Garbage collection
- Thread scheduling
- Run time type inference
The only assumption we do on the interpreted language is that it has to provide a way to invoke native functions or procedures. Note how we do not even require object orientation support in the language. In this way, we can design the integration between Gecode and the language in a merely procedural way. Examples of possible languages are Oz itself and Lisp.
Three particular parts need to be designed as part as this glue layer: a search engine, propagator interface and branch interface.
When the idea is that search can be invoked from the language we need to consider several design aspects of Gecode: it uses templates for the distribution strategies. Templates are evaluated at compile time and the appropriate code is generated. This is something we cannot afford. The language is interpreted so we cannot perform any external compilation.
Another fact is the existence of garbage collection in the language. Suppose a constraint problem is being solved. The search engine that is running finding the solution needs to be aware that at some point it needs to react to two particular signals emitted from the interpreter:
- Suspend. This will stop the search engine at fix point. The idea is that the machine will be able to start from this point and complete afterwards.
- Resume. This will start the search engine again to continue the search.
The suspend event will be generated for instance when garbage collection needs to be executed at the virtual machine or, in the case of a concurrent language implementation, other threads need to be interleaved with the search.
An important aspect of this layer is that it does not implies to perform any modification of the Gecode sources. It is more like an extension that can be built with the Gecode public interface.
Propagators are available in Gecode with the inclusion of different modules. Their prototypes are defined in Gecode's public headers. This is one of the parts that have changed the most during the Gecode development. From version to version we usually have new propagators available.
The glue layer for integrating Gecode must provide a way for calling the appropriate procedures to post constraints. As this part of the Gecode API is constantly increasing, we need to provide a way for new releases of Gecode to be functional with this glue layer.
For this it will be very convenient to have a parser that "reads" the appropriate header files in the Gecode distribution and make propagators available at the glue layer. Some aspects to take into account:
- Gecode headers are C++ files. Parsing C++ is not easy.
- A propagator is posted by calling a C procedure that does not return.
- As it is C++ we have static polymorphism. Several procedures have the same name but the compiler "chooses" the right one. We cannot afford this, we only know that at runtime. We need to transform this polymorphism into something that we can dispatch on at run time.
Possible ways of handling this part is by using the AST generated during the compilation of the headers. If we go with this option, we delegate the first item above to the robustness of a real compiler. The AST is also promising because it contains all the information that we need to glue. On this topic, we have considered the possibility of using Clang (http://clang.llvm.org). Its design facilitate the retrieval and traversal of the AST.