Institut für Informatik Deductive Databases
Prof. Dr. Stefan Brass Push Method



Bottom-Up Evaluation with the "Push Method"

First Prototype of an Abstract Machine for Bottom-Up Evaluation



Source code, version from September 19, 2017:

This is the first prototype implementation of an abstract machine for bottom-up evaluation that I recently proposed. I have implemented just enough to be able to execute two benchmarks for a first performance test. Not all proposed machine instructions are implemented yet. Furthermore, the test programs are currently generated in main memory, the reading and writing of "BAM"-programs from/to files still has to be implemented. However, first performance tests are very encouraging: In the two tested benchmarks (TCFF and Join1) the slowdown compared to native machine code was only a factor of 1.5. This is better than the difference that was observed for Prolog code compiled to the WAM vs. native code. I certainly will condtinue the implementation task and also will do tests to check whether the many instructions for special cases are really important for the performance.


Contents of the Directories:


Installing the Software:


Using the Program:

The program has compiled in a number of tests and benchmarks. The test/benchmark can be selected with a command line argument. A list of tests is printed if the program is called with the option -l. The most important benchmarks are:

The program is called in the form bam <Options> <Test/Benchmark IDs>. It understands the following options:

Note: The current version writes a file "alert" with error messages and object dumps (in debug mode). I will soon add an option to suppress this. For the time being, one needs write permission for the directory in which one executes bam because of this error log file (which is opened even if there are no errors).


Stefan Brass (, December 18, 2017

Original URL:   [XHTML 1.0]   [CSS]   [Links]   [Legal Info]