SLDMagic - An Improved Magic Set Technique

A new version with a general bottom-up evaluator is now available. The rules of the meta-interpreter are defined as facts in the program, the partial evaluator would also work with other rules. This is a big improvement over the earlier version. The program actually became shorter by using the new general approach. The new version also recognizes facts which are known to be true at compiletime (i.e. derived unconditionally by the partial evaluator) and removes pure copy rules.

The copy rule elimination could be improved to make the resulting programs still smaller. I will continue to work on this, please visit this page again.

The last update was posted on March 20, 2000.


The Prolog code was written by Stefan Brass, Please contact if you wish to get informed about updates or if you found a bug.

The Program is available under the GNU Public License free of charge, but without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose.

Source Code

The following files are identical except a few lines commented out at the beginning.

(I have tested Version 2 only with SWI-Prolog. Version 1 did run on all these three Prologs. I will do further tests soon.)


After loading the program, call sldmagic(Filename).

Sorry for this brewity. An improved manual will be available soon. Maybe also an example run helps.

Example Inputs

S. Brass: Magic Sets vs. SLD-Resolution. In J. Eder, L. A. Kalinichenko (eds.), Advances in Databases and Information Systems (ADBIS'95), Springer, 1995, 185-203.

S. Brass: SLDMagic - An Improved Magic Set Technique. In: B. Novikov, J. W. Schmidt (eds.): Advances in Databases and Information Systems - ADBIS'96, MEPhI Publishing, Moscow, 1996, 75-83. Also published in Springer Workshops in Computing (1997).

Related Links
Please tell my about further related links by email.

Stefan Brass (, March 20, 2000.